論文の概要: Asymptotic behaviour of learning rates in Armijo's condition
- arxiv url: http://arxiv.org/abs/2007.03618v1
- Date: Tue, 7 Jul 2020 16:49:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 20:49:52.013240
- Title: Asymptotic behaviour of learning rates in Armijo's condition
- Title（参考訳）: アルミホ状態における学習率の漸近的行動
- Authors: Tuyen Trung Truong, Tuan Hang Nguyen
- Abstract要約: x_n$ が非退化臨界点に収束すると、$delta _n$ は有界でなければならない。
これは、Unbounded Backtracking GDに関する最初の著者の結果を補完する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Fix a constant $0<\alpha <1$. For a $C^1$ function $f:\mathbb{R}^k\rightarrow
\mathbb{R}$, a point $x$ and a positive number $\delta >0$, we say that
Armijo's condition is satisfied if $f(x-\delta \nabla f(x))-f(x)\leq -\alpha
\delta ||\nabla f(x)||^2$. It is a basis for the well known Backtracking
Gradient Descent (Backtracking GD) algorithm.
Consider a sequence $\{x_n\}$ defined by $x_{n+1}=x_n-\delta _n\nabla
f(x_n)$, for positive numbers $\delta _n$ for which Armijo's condition is
satisfied. We show that if $\{x_n\}$ converges to a non-degenerate critical
point, then $\{\delta _n\}$ must be bounded. Moreover this boundedness can be
quantified in terms of the norms of the Hessian $\nabla ^2f$ and its inverse at
the limit point. This complements the first author's results on Unbounded
Backtracking GD, and shows that in case of convergence to a non-degenerate
critical point the behaviour of Unbounded Backtracking GD is not too different
from that of usual Backtracking GD. On the other hand, in case of convergence
to a degenerate critical point the behaviours can be very much different. We
run some experiments to illustrate that both scenrios can really happen.
In another part of the paper, we argue that Backtracking GD has the correct
unit (according to a definition by Zeiler in his Adadelta's paper). The main
point is that since learning rate in Backtracking GD is bound by Armijo's
condition, it is not unitless.
- Abstract（参考訳）: 定数 $0<\alpha <1$ を固定する。
a $c^1$ function $f:\mathbb{r}^k\rightarrow \mathbb{r}$, a point $x$ and a positive number $\delta >0$ に対し、armijoの条件は$f(x-\delta \nabla f(x))-f(x)\leq -\alpha \delta ||\nabla f(x)||^2$ で満たされる。
これはよく知られたBacktracking Gradient Descent (Backtracking GD)アルゴリズムの基礎である。
x_n+1}=x_n-\delta _n\nabla f(x_n)$ で定義される列 $\{x_n\}$ を考える。
ここでは、$\{x_n\}$ が非退化臨界点に収束すると、$\{\delta _n\}$ は有界でなければならないことを示す。
さらに、この有界性は Hessian $\nabla ^2f$ のノルムと極限点におけるその逆のノルムで定量化することができる。
これは、Unbounded Backtracking GD に関する最初の著者の結果を補完し、非退化臨界点への収束の場合、Unbounded Backtracking GD の挙動が通常の Backtracking GD とそれほど変わらないことを示す。
一方、縮退した臨界点に収束する場合、挙動は大きく異なる場合がある。
私たちは、両方のスケンリオが本当に起こりうることを示すためにいくつかの実験を行います。
論文の別の部分では、バックトラッキングgdが正しい単位を持つと主張する(彼の adadelta の論文で zeiler の定義によれば)。
主なポイントは、バックトラックgdにおける学習レートがarmijoの条件に結びついているため、ユニットレスではないことである。
関連論文リスト
- 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) - Convergence of Gradient Descent with Small Initialization for
Unregularized Matrix Completion [21.846732043706318]
バニラ勾配降下は、明示的な正則化を必要とせず、必ず基底真理$rmXstar$に収束することを示す。
驚くべきことに、収束率も最終的な精度もオーバーパラメータ化された検索ランク$r'$に依存しておらず、それらは真のランク$r$によってのみ支配される。
論文 参考訳（メタデータ） (2024-02-09T19:39:23Z) - 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 Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
我々は、ほとんどの方向において$bfu$と$nu=mathrmpoly(k)$に対して、$n=mathrmpoly(k)$測定を用いて、高い精度で$bfu$を推定するアルゴリズムを開発し、分析する。
数値実験により,非漸近的条件下でも良好な性能が得られた。
論文 参考訳（メタデータ） (2021-10-04T02:10:47Z) - 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) - Coordinate-wise Armijo's condition: General case [0.0]
例えば $f(x,y)=f(x,y)+g(y)$ などである。
すると、$f(x,y)=f(x,y)+g(y)$ のような関数について解析し、実験結果を示す。
論文 参考訳（メタデータ） (2020-03-11T12:17:05Z) - 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) - Backtracking Gradient Descent allowing unbounded learning rates [0.0]
ユークリッド空間上の非制約最適化では、勾配 Descent process (GD) $x_n+1=x_n-delta _n nabla f(x_n)$ の収束を証明するために、通常、学習レート $delta _n$'s が有界であることが要求される。
本稿では,学習率$delta _n$を非有界にする。
この$h$の成長率は、シーケンスの$x_n$の収束を望んでいれば最善であることが示される。
論文 参考訳（メタデータ） (2020-01-07T12:52:00Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。