論文の概要: On the Convergence of mSGD and AdaGrad for Stochastic Optimization
- arxiv url: http://arxiv.org/abs/2201.11204v1
- Date: Wed, 26 Jan 2022 22:02:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-28 15:15:37.639155
- Title: On the Convergence of mSGD and AdaGrad for Stochastic Optimization
- Title（参考訳）: 確率最適化のためのmSGDとAdaGradの収束性について
- Authors: Ruinan Jin, Yu Xing, Xingkang He
- Abstract要約: 凸降下(SGD)は、過去10年間に機械学習に大きく開発され、広く応用されてきた。
モーメントベースのSGD(mSGD)や適応的勾配最適化(AdaGrad)など、多くの競合や応用においてSGDよりも優れている修正SGD型アルゴリズムもある。
我々は,機械学習における任意の滑らかな(不可能かもしれない)損失関数に対するmSGDとAdaGradの収束解析に着目する。
- 参考スコア（独自算出の注目度）: 0.696125353550498
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As one of the most fundamental stochastic optimization algorithms, stochastic
gradient descent (SGD) has been intensively developed and extensively applied
in machine learning in the past decade. There have been some modified SGD-type
algorithms, which outperform the SGD in many competitions and applications in
terms of convergence rate and accuracy, such as momentum-based SGD (mSGD) and
adaptive gradient algorithm (AdaGrad). Despite these empirical successes, the
theoretical properties of these algorithms have not been well established due
to technical difficulties. With this motivation, we focus on convergence
analysis of mSGD and AdaGrad for any smooth (possibly non-convex) loss
functions in stochastic optimization. First, we prove that the iterates of mSGD
are asymptotically convergent to a connected set of stationary points with
probability one, which is more general than existing works on subsequence
convergence or convergence of time averages. Moreover, we prove that the loss
function of mSGD decays at a certain rate faster than that of SGD. In addition,
we prove the iterates of AdaGrad are asymptotically convergent to a connected
set of stationary points with probability one. Also, this result extends the
results from the literature on subsequence convergence and the convergence of
time averages. Despite the generality of the above convergence results, we have
relaxed some assumptions of gradient noises, convexity of loss functions, as
well as boundedness of iterates.
- Abstract（参考訳）: 最も基本的な確率的最適化アルゴリズムの1つとして、確率的勾配降下(SGD)は、過去10年間に機械学習において集中的に開発され、広く適用されてきた。
修正されたSGD型アルゴリズムは、モーメントベースのSGD(mSGD)や適応勾配アルゴリズム(AdaGrad)など、多くの競合や応用においてSGDよりも優れている。
これらの経験的成功にもかかわらず、これらのアルゴリズムの理論的性質は技術的困難のために十分に確立されていない。
この動機により、確率最適化における滑らかな(非凸かもしれない)損失関数に対するmSGDとAdaGradの収束解析に焦点をあてる。
まず、mSGD の反復体が確率 1 の連結定常点の集合に漸近収束していることを証明する。
さらに,mSGDの損失関数は,SGDの損失関数よりも一定の速度で崩壊することを示した。
さらに、AdaGrad の反復は確率 1 で連結された定常点の集合に漸近的に収束することを示す。
また、この結果は、サブシーケンス収束と時間平均の収束に関する文献から結果を拡張する。
以上の収束結果の一般性にもかかわらず, 勾配雑音, 損失関数の凸性, イテレートの有界性などの仮定を緩和した。
関連論文リスト
- Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。
分析として,勾配の非収束に関連する神話や伝説について考察した。
論文 参考訳（メタデータ） (2023-10-19T17:58:59Z) - 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) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - 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) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳（メタデータ） (2020-12-07T19:14:49Z) - Convergence Analysis of Homotopy-SGD for non-convex optimization [43.71213126039448]
ホモトピー法とSGDを組み合わせた一階述語アルゴリズム、Gradienty-Stoch Descent (H-SGD)を提案する。
いくつかの仮定の下で、提案した問題の理論的解析を行う。
実験の結果,H-SGDはSGDより優れていた。
論文 参考訳（メタデータ） (2020-11-20T09:50:40Z) - Practical Precoding via Asynchronous Stochastic Successive Convex
Approximation [8.808993671472349]
凸非平滑正規化器を用いた滑らかな非研究損失関数の最適化について検討する。
本研究では、SCAアルゴリズムを詳しく検討し、無線ネットワークにおけるリソース割り当てのための非同期版を開発する。
論文 参考訳（メタデータ） (2020-10-03T13:53:30Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Convergence rates and approximation results for SGD and its
continuous-time counterpart [16.70533901524849]
本稿では,非増加ステップサイズを有する凸勾配Descent (SGD) の完全理論的解析を提案する。
まず、結合を用いた不均一微分方程式(SDE)の解により、SGDを確実に近似できることを示す。
連続的手法による決定論的および最適化手法の最近の分析において, 連続過程の長期的挙動と非漸近的境界について検討する。
論文 参考訳（メタデータ） (2020-04-08T18:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。