論文の概要: Demystifying the Myths and Legends of Nonconvex Convergence of SGD
- arxiv url: http://arxiv.org/abs/2310.12969v1
- Date: Thu, 19 Oct 2023 17:58:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-20 13:47:16.774668
- Title: Demystifying the Myths and Legends of Nonconvex Convergence of SGD
- Title（参考訳）: sgdの非凸収束の神話と伝説の幻想化
- Authors: Aritra Dutta, El Houcine Bergou, Soumia Boucherouite, Nicklas Werge,
Melih Kandemir, Xin Li
- Abstract要約: 勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。
分析として,勾配の非収束に関連する神話や伝説について考察した。
- 参考スコア（独自算出の注目度）: 17.445810977264067
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic gradient descent (SGD) and its variants are the main workhorses
for solving large-scale optimization problems with nonconvex objective
functions. Although the convergence of SGDs in the (strongly) convex case is
well-understood, their convergence for nonconvex functions stands on weak
mathematical foundations. Most existing studies on the nonconvex convergence of
SGD show the complexity results based on either the minimum of the expected
gradient norm or the functional sub-optimality gap (for functions with extra
structural property) by searching the entire range of iterates. Hence the last
iterations of SGDs do not necessarily maintain the same complexity guarantee.
This paper shows that an $\epsilon$-stationary point exists in the final
iterates of SGDs, given a large enough total iteration budget, $T$, not just
anywhere in the entire range of iterates -- a much stronger result than the
existing one. Additionally, our analyses allow us to measure the density of the
$\epsilon$-stationary points in the final iterates of SGD, and we recover the
classical $O(\frac{1}{\sqrt{T}})$ asymptotic rate under various existing
assumptions on the objective function and the bounds on the stochastic
gradient. As a result of our analyses, we addressed certain myths and legends
related to the nonconvex convergence of SGD and posed some thought-provoking
questions that could set new directions for research.
- Abstract（参考訳）: 確率勾配勾配(SGD)とその変種は、非凸目的関数を用いた大規模最適化問題の解法の主要な仕事場である。
SGD の(強く)凸の場合の収束はよく理解されているが、非凸函数に対する収束は弱い数学的基礎の上に立つ。
SGDの非凸収束に関する既存の研究は、予想される勾配ノルムの最小値と(余分な構造的性質を持つ函数に対する)機能的部分最適ギャップに基づいて、イテレートの全範囲を探索することによって複雑さの結果を示す。
したがって、sgdの最後のイテレーションは必ずしも同じ複雑さの保証を保たない。
この論文は、sgdsの最終イテレートに$\epsilon$-stationary pointが存在し、十分な総イテレーション予算が与えられ、イテレートの範囲内だけでなく、既存のイテレートよりもずっと強力な結果が得られることを示している。
さらに,本解析により,sgd の最終イテレートにおける $\epsilon$-stationary point の密度を測定し,目的関数と確率勾配の境界に関する様々な既定仮定の下で古典的 $o(\frac{1}{\sqrt{t}})$ asymptotic rate を回復する。
分析の結果,SGDの非凸収束に関連する神話や伝説に対処し,新たな研究の方向性を定めうる思慮に富んだ疑問を提起した。
関連論文リスト
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。
この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
論文 参考訳（メタデータ） (2023-12-05T15:22:39Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。
集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。
我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
論文 参考訳（メタデータ） (2022-10-13T03:55:04Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - On the Convergence of mSGD and AdaGrad for Stochastic Optimization [0.696125353550498]
凸降下(SGD)は、過去10年間に機械学習に大きく開発され、広く応用されてきた。
モーメントベースのSGD(mSGD)や適応的勾配最適化(AdaGrad)など、多くの競合や応用においてSGDよりも優れている修正SGD型アルゴリズムもある。
我々は,機械学習における任意の滑らかな(不可能かもしれない)損失関数に対するmSGDとAdaGradの収束解析に着目する。
論文 参考訳（メタデータ） (2022-01-26T22:02:21Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and
Interpolation [17.199023009789308]
予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。
本稿では,スムーズな非線形設定への収束のパラダイムを示す。
また,異なるステップサイズ条件の理論的保証も提供する。
論文 参考訳（メタデータ） (2020-06-18T07:05:56Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。