論文の概要: What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
- arxiv url: http://arxiv.org/abs/2110.06914v1
- Date: Wed, 13 Oct 2021 17:50:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-14 14:11:49.440018
- Title: What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
- Title（参考訳）: SGD、ゼロ・ロスの後に何が起こるのか?
--数学的枠組み
- Authors: Zhiyuan Li, Tianhao Wang, Sanjeev Arora
- Abstract要約: SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。
本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。
1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
- 参考スコア（独自算出の注目度）: 35.31946061894308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Understanding the implicit bias of Stochastic Gradient Descent (SGD) is one
of the key challenges in deep learning, especially for overparametrized models,
where the local minimizers of the loss function $L$ can form a manifold.
Intuitively, with a sufficiently small learning rate $\eta$, SGD tracks
Gradient Descent (GD) until it gets close to such manifold, where the gradient
noise prevents further convergence. In such a regime, Blanc et al. (2020)
proved that SGD with label noise locally decreases a regularizer-like term, the
sharpness of loss, $\mathrm{tr}[\nabla^2 L]$. The current paper gives a general
framework for such analysis by adapting ideas from Katzenberger (1991). It
allows in principle a complete characterization for the regularization effect
of SGD around such manifold -- i.e., the "implicit bias" -- using a stochastic
differential equation (SDE) describing the limiting dynamics of the parameters,
which is determined jointly by the loss function and the noise covariance. This
yields some new results: (1) a global analysis of the implicit bias valid for
$\eta^{-2}$ steps, in contrast to the local analysis of Blanc et al. (2020)
that is only valid for $\eta^{-1.6}$ steps and (2) allowing arbitrary noise
covariance. As an application, we show with arbitrary large initialization,
label noise SGD can always escape the kernel regime and only requires
$O(\kappa\ln d)$ samples for learning an $\kappa$-sparse overparametrized
linear model in $\mathbb{R}^d$ (Woodworth et al., 2020), while GD initialized
in the kernel regime requires $\Omega(d)$ samples. This upper bound is minimax
optimal and improves the previous $\tilde{O}(\kappa^2)$ upper bound (HaoChen et
al., 2020).
- Abstract（参考訳）: 確率的勾配降下 (sgd) の暗黙的バイアスを理解することは、特に超パラメータモデルにおいて、損失関数 $l$ の局所最小値が多様体を形成するための重要な課題の1つである。
直感的には、sgdは十分に小さな学習率($\eta$)で勾配降下(gd)を追跡し、勾配ノイズがさらなる収束を妨げるような多様体に近づく。
このような状況下で、ブランら (2020) はラベルノイズのあるsgdが局所的に正規化子のような項を減少させ、損失の鋭さを減少させることを証明した。
本論文は,katzenberger (1991) のアイデアを応用した解析の汎用的枠組みを提案する。
原理上、sgd のそのような多様体周りの正則化効果(すなわち「単純バイアス」)に対する完全なキャラクタリゼーションを、損失関数とノイズ共変性によって共同で決定されるパラメータの制限ダイナミクスを記述する確率微分方程式 (sde) を用いて得ることができる。
これはいくつかの新しい結果をもたらす: (1)$\eta^{-2}$ステップで有効な暗黙のバイアスのグローバル分析、(2020)$\eta^{-1.6}$ステップでのみ有効なbucket et al.(英語版)の局所分析、および(2)任意のノイズ共分散を可能にする。
アプリケーションとして、任意の大きな初期化を行えば、ラベルノイズSGDは常にカーネル体制から逃れることができ、$O(\kappa\ln d)$サンプルしか必要とせず、$\kappa$-sparse overparametrized linear model in $\mathbb{R}^d$ (Woodworth et al., 2020) を学ぶために$O(\kappa$-sparse overparametrized linear model を学ぶことはできない。
この上限はミニマックス最適であり、以前の$\tilde{o}(\kappa^2)$ upper bound (haochen et al., 2020) を改善する。
関連論文リスト
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Topology-aware Generalization of Decentralized SGD [89.25765221779288]
本稿では,分散型Valpha-10安定降下(D-SGD)の一般化可能性について検討する。
D-SGDの一般化性は、初期訓練段階における接続性と正の相関があることを証明した。
論文 参考訳（メタデータ） (2022-06-25T16:03:48Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Generalization Bounds for Gradient Methods via Discrete and Continuous
Prior [8.76346911214414]
次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。
また、あるSGDの変種に対する新しい境界を得ることもできる。
論文 参考訳（メタデータ） (2022-05-27T07:23:01Z) - Understanding Gradient Descent on Edge of Stability in Deep Learning [32.03036040349019]
本稿では,EoS相における暗黙的正則化の新たなメカニズムを数学的に解析し,非滑らかな損失景観によるGD更新が,最小損失の多様体上の決定論的流れに沿って進化することを示した。
以上の理論的結果は実験によって裏付けられている。
論文 参考訳（メタデータ） (2022-05-19T17:57:01Z) - A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。
高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。
提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
論文 参考訳（メタデータ） (2022-02-19T22:12:30Z) - Black-Box Generalization [31.80268332522017]
微分一般化によるブラックボックス学習のための最初の誤り解析を行う。
どちらの一般化も独立$d$,$K$であり、適切な選択の下では学習率がわずかに低下していることを示す。
論文 参考訳（メタデータ） (2022-02-14T17:14:48Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。