論文の概要: Beyond the Edge of Stability via Two-step Gradient Updates
- arxiv url: http://arxiv.org/abs/2206.04172v3
- Date: Wed, 26 Jul 2023 10:48:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-27 16:32:18.599395
- Title: Beyond the Edge of Stability via Two-step Gradient Updates
- Title（参考訳）: 2段階の勾配更新による安定性の限界を超える
- Authors: Lei Chen, Joan Bruna
- Abstract要約: Gradient Descent(GD)は、現代の機械学習の強力な仕事場である。
GDが局所最小値を見つける能力は、リプシッツ勾配の損失に対してのみ保証される。
この研究は、2段階の勾配更新の分析を通じて、単純だが代表的でありながら、学習上の問題に焦点をあてる。
- 参考スコア（独自算出の注目度）: 49.03389279816152
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient Descent (GD) is a powerful workhorse of modern machine learning
thanks to its scalability and efficiency in high-dimensional spaces. Its
ability to find local minimisers is only guaranteed for losses with Lipschitz
gradients, where it can be seen as a `bona-fide' discretisation of an
underlying gradient flow. Yet, many ML setups involving overparametrised models
do not fall into this problem class, which has motivated research beyond the
so-called ``Edge of Stability'' (EoS), where the step-size crosses the
admissibility threshold inversely proportional to the Lipschitz constant above.
Perhaps surprisingly, GD has been empirically observed to still converge
regardless of local instability and oscillatory behavior.
The incipient theoretical analysis of this phenomena has mainly focused in
the overparametrised regime, where the effect of choosing a large learning rate
may be associated to a `Sharpness-Minimisation' implicit regularisation within
the manifold of minimisers, under appropriate asymptotic limits. In contrast,
in this work we directly examine the conditions for such unstable convergence,
focusing on simple, yet representative, learning problems, via analysis of
two-step gradient updates. Specifically, we characterize a local condition
involving third-order derivatives that guarantees existence and convergence to
fixed points of the two-step updates, and leverage such property in a
teacher-student setting, under population loss. Finally, starting from Matrix
Factorization, we provide observations of period-2 orbit of GD in
high-dimensional settings with intuition of its dynamics, along with
exploration into more general settings.
- Abstract（参考訳）: Gradient Descent(GD)は、高次元空間におけるスケーラビリティと効率のおかげで、現代の機械学習の強力なワークホースである。
局所的なミニミザーを見つける能力はリプシッツ勾配の損失に対してのみ保証され、そこでは下層の勾配流の'bona-fide'離散化と見なすことができる。
しかし、過パラメータモデルを含む多くのmlセットアップは、上記のリプシッツ定数に反比例する許容しきい値にステップサイズが交差するいわゆる「安定性の限界」(eos)以上の研究を動機付けたこの問題クラスには入らない。
おそらく驚くべきことに、gdは局所的な不安定性と振動行動に関わらず、依然として収束することが実証的に観察されている。
この現象の初歩的な理論的分析は、主に過パラメトリッドな体制に焦点を合わせており、大きな学習率を選択する効果は、適切な漸近的限界の下で、ミニミザー多様体内の「シャープネス・ミニミフィケーション」の暗黙的な正則化と関連付けられる可能性がある。
対照的に,本研究では,2段階の勾配更新の解析を通じて,単純だが代表的な学習問題に着目し,不安定収束の条件を直接検討する。
具体的には,二段階更新の固定点に対する存在と収束を保証する三階微分を含む局所的条件を特徴とし,その特性を教師の学習環境において,人口減少下で活用する。
最後に, 行列因子分解からGDの周期2軌道を高次元的に観察し, ダイナミックスを直感的に観察し, より一般的な設定を探索する。
関連論文リスト
- On the Convergence of Gradient Descent for Large Learning Rates [55.33626480243135]
固定ステップサイズを使用すると収束が不可能であることを示す。
正方形損失を持つ線形ニューラルネットワークの場合,これを証明した。
また、勾配に対するリプシッツ連続性のような強い仮定を必要とせず、より一般的な損失に対する収束の不可能性も証明する。
論文 参考訳（メタデータ） (2024-02-20T16:01:42Z) - Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled
Gradient Descent, Even with Overparameterization [48.65416821017865]
この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。
低ランク物体の条件数に依存しない定数速度で直線的に収束する。
様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
論文 参考訳（メタデータ） (2023-10-09T21:16:57Z) - Convergence of mean-field Langevin dynamics: Time and space
discretization, stochastic gradient, and variance reduction [49.66486092259376]
平均場ランゲヴィンダイナミクス(英: mean-field Langevin dynamics、MFLD)は、分布依存のドリフトを含むランゲヴィン力学の非線形一般化である。
近年の研究では、MFLDは測度空間で機能するエントロピー規則化された凸関数を地球規模で最小化することが示されている。
有限粒子近似,時間分散,勾配近似による誤差を考慮し,MFLDのカオスの均一時間伝播を示す枠組みを提供する。
論文 参考訳（メタデータ） (2023-06-12T16:28:11Z) - Implicit Bias of Gradient Descent for Logistic Regression at the Edge of
Stability [69.01076284478151]
機械学習の最適化において、勾配降下(GD)はしばしば安定性の端(EoS)で動く
本稿では,EoS系における線形分離可能なデータに対するロジスティック回帰のための定数段差GDの収束と暗黙バイアスについて検討する。
論文 参考訳（メタデータ） (2023-05-19T16:24:47Z) - A PDE-based Explanation of Extreme Numerical Sensitivities and Edge of Stability in Training Neural Networks [12.355137704908042]
勾配降下型深層ネットワーク(SGD)の現在の訓練実践における抑制的数値不安定性を示す。
我々は、偏微分方程式(PDE)の数値解析を用いて理論的枠組みを提示し、畳み込みニューラルネットワーク(CNN)の勾配降下PDEを分析する。
これはCNNの降下に伴う非線形PDEの結果であり、離散化のステップサイズを過度に運転すると局所線形化が変化し、安定化効果がもたらされることを示す。
論文 参考訳（メタデータ） (2022-06-04T14:54:05Z) - A Local Convergence Theory for the Stochastic Gradient Descent Method in
Non-Convex Optimization With Non-isolated Local Minima [0.0]
非孤立ミニマは、未探索のままのユニークな挑戦を示す。
本稿では, 勾配降下法の非溶解大域ミニマへの局所収束について検討する。
論文 参考訳（メタデータ） (2022-03-21T13:33:37Z) - Fine-Grained Analysis of Stability and Generalization for Stochastic
Gradient Descent [55.85456985750134]
我々は,SGDの反復的リスクによって制御される新しい境界を開発する,平均モデル安定性と呼ばれる新しい安定性尺度を導入する。
これにより、最良のモデルの振舞いによって一般化境界が得られ、低雑音環境における最初の既知の高速境界が導かれる。
我々の知る限りでは、このことはSGDの微分不能な損失関数でさえも初めて知られている安定性と一般化を与える。
論文 参考訳（メタデータ） (2020-06-15T06:30:19Z) - Convergence and sample complexity of gradient methods for the model-free
linear quadratic regulator problem [27.09339991866556]
本稿では,コントローラの空間を直接探索することにより,未知の計算系に対する最適制御を求める。
我々は、安定化フィードバックゲインの勾配-フローのダイナミクスセットに焦点をあてて、そのような手法の性能と効率を最小化するための一歩を踏み出した。
論文 参考訳（メタデータ） (2019-12-26T16:56:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。