論文の概要: Backtracking Gradient Descent allowing unbounded learning rates
- arxiv url: http://arxiv.org/abs/2001.02005v2
- Date: Wed, 8 Jan 2020 16:50:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-13 20:36:48.870796
- Title: Backtracking Gradient Descent allowing unbounded learning rates
- Title（参考訳）: 非有界学習率を許容する逆追跡勾配降下
- Authors: Tuyen Trung Truong
- Abstract要約: ユークリッド空間上の非制約最適化では、勾配 Descent process (GD) $x_n+1=x_n-delta _n nabla f(x_n)$ の収束を証明するために、通常、学習レート $delta _n$'s が有界であることが要求される。
本稿では,学習率$delta _n$を非有界にする。
この$h$の成長率は、シーケンスの$x_n$の収束を望んでいれば最善であることが示される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In unconstrained optimisation on an Euclidean space, to prove convergence in
Gradient Descent processes (GD) $x_{n+1}=x_n-\delta _n \nabla f(x_n)$ it
usually is required that the learning rates $\delta _n$'s are bounded: $\delta
_n\leq \delta $ for some positive $\delta $. Under this assumption, if the
sequence $x_n$ converges to a critical point $z$, then with large values of $n$
the update will be small because $||x_{n+1}-x_n||\lesssim ||\nabla f(x_n)||$.
This may also force the sequence to converge to a bad minimum. If we can allow,
at least theoretically, that the learning rates $\delta _n$'s are not bounded,
then we may have better convergence to better minima.
A previous joint paper by the author showed convergence for the usual version
of Backtracking GD under very general assumptions on the cost function $f$. In
this paper, we allow the learning rates $\delta _n$ to be unbounded, in the
sense that there is a function $h:(0,\infty)\rightarrow (0,\infty )$ such that
$\lim _{t\rightarrow 0}th(t)=0$ and $\delta _n\lesssim \max \{h(x_n),\delta \}$
satisfies Armijo's condition for all $n$, and prove convergence under the same
assumptions as in the mentioned paper. It will be shown that this growth rate
of $h$ is best possible if one wants convergence of the sequence $\{x_n\}$.
A specific way for choosing $\delta _n$ in a discrete way connects to Two-way
Backtracking GD defined in the mentioned paper. We provide some results which
either improve or are implicitly contained in those in the mentioned paper and
another recent paper on avoidance of saddle points.
- Abstract（参考訳）: ユークリッド空間上の制約のない最適化では、勾配降下過程 (gd) $x_{n+1}=x_n-\delta _n \nabla f(x_n)$ の収束を証明するには、通常、学習レート$\delta _n$'s が有界である必要がある。
この仮定の下で、列 $x_n$ が臨界点 $z$ に収束すると、$|x_{n+1}-x_n||\lesssim ||\nabla f(x_n)||$ が成り立つので、$n$ の大きな値で更新は小さくなる。
これにより、配列を最低限に収束させることもできる。
少なくとも理論的には、学習率$\delta _n$sが有界でないことを許せるなら、より小さな値に収束する方がよいかもしれない。
著者による以前の共同論文は、コスト関数 $f$ に対する非常に一般的な仮定の下で、通常のバックトラッキング gd の収束を示した。
この論文では、学習率$\delta _n$ を非有界にすることを許し、ある函数 $h:(0,\infty)\rightarrow (0,\infty )$ が存在して、$\lim _{t\rightarrow 0}th(t)=0$ と $\delta _n\lesssim \max \{h(x_n),\delta \}$ がすべての$n$ に対してアルミホの条件を満たし、上記の論文と同じ仮定で収束することを証明する。
シーケンス $\{x_n\}$ の収束を望む場合、この$h$の成長率が最良であることが示される。
離散的な方法で$\delta _n$を選択する特定の方法は、上記の論文で定義されたTwo-way Backtracking GDに接続する。
本論文では, サドル点の回避に関する最近の論文において, 改善あるいは暗黙的に含まれているいくつかの結果について述べる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - A note on estimating the dimension from a random geometric graph [2.3020018305241337]
グラフの隣接行列にアクセスする際に、基礎空間の次元$d$を推定する問題について検討する。
また、密度の条件がなければ、$d$の一貫した推定子は$n r_nd to infty$と$r_n = o(1)$が存在することを示す。
論文 参考訳（メタデータ） (2023-11-21T23:46:44Z) - Generalisations and improvements of New Q-Newton's method Backtracking [0.0]
本稿では,新しいQ-Newtonの手法のバックトラッキングのための一般的なフレームワークを提案する。
例えば、1$ または $e_m(x)$'s は必ずしも $nabla 2f(x)$ の固有ベクトルではない。
論文 参考訳（メタデータ） (2021-09-23T14:28:15Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Asymptotic behaviour of learning rates in Armijo's condition [0.0]
x_n$ が非退化臨界点に収束すると、$delta _n$ は有界でなければならない。
これは、Unbounded Backtracking GDに関する最初の著者の結果を補完する。
論文 参考訳（メタデータ） (2020-07-07T16:49:25Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - A fast and simple modification of Newton's method helping to avoid
saddle points [0.0]
この論文は、$f$が$C3$でシーケンス$x_n$であれば、極限点は臨界点であり、サドル点ではなく、収束速度はニュートンの方法と同じである。
論文 参考訳（メタデータ） (2020-06-02T10:38:00Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z) - Some convergent results for Backtracking Gradient Descent method on
Banach spaces [0.0]
bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。
$mathcalC$ を $f$ の臨界点の集合とする。
論文 参考訳（メタデータ） (2020-01-16T12:49:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。