論文の概要: Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions

• arxiv url: http://arxiv.org/abs/2305.18471v1
• Date: Mon, 29 May 2023 09:33:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-31 20:34:58.556149
• Title: Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions
• Title（参考訳）: 非凸対象に対するAdaGradの収束性:単純証明と緩和推定
• Authors: Bohan Wang, Huishuai Zhang, Zhi-Ming Ma, Wei Chen
• Abstract要約: 新しい補助関数$xi$は、AdaGradsイテレーションの数値と分母の間の相関を扱う複雑さを取り除くのに役立つ。 AdaGradは,学習率がしきい値より低い限り,$(L_0)$smooth条件下での収束に成功していることを示す。
• 参考スコア（独自算出の注目度）: 33.50494011522624
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide a simple convergence proof for AdaGrad optimizing non-convex objectives under only affine noise variance and bounded smoothness assumptions. The proof is essentially based on a novel auxiliary function $\xi$ that helps eliminate the complexity of handling the correlation between the numerator and denominator of AdaGrad's update. Leveraging simple proofs, we are able to obtain tighter results than existing results \citep{faw2022power} and extend the analysis to several new and important cases. Specifically, for the over-parameterized regime, we show that AdaGrad needs only $\mathcal{O}(\frac{1}{\varepsilon^2})$ iterations to ensure the gradient norm smaller than $\varepsilon$, which matches the rate of SGD and significantly tighter than existing rates $\mathcal{O}(\frac{1}{\varepsilon^4})$ for AdaGrad. We then discard the bounded smoothness assumption and consider a realistic assumption on smoothness called $(L_0,L_1)$-smooth condition, which allows local smoothness to grow with the gradient norm. Again based on the auxiliary function $\xi$, we prove that AdaGrad succeeds in converging under $(L_0,L_1)$-smooth condition as long as the learning rate is lower than a threshold. Interestingly, we further show that the requirement on learning rate under the $(L_0,L_1)$-smooth condition is necessary via proof by contradiction, in contrast with the case of uniform smoothness conditions where convergence is guaranteed regardless of learning rate choices. Together, our analyses broaden the understanding of AdaGrad and demonstrate the power of the new auxiliary function in the investigations of AdaGrad.
• Abstract（参考訳）: AdaGradはアフィン雑音分散と有界滑らか性仮定のみの下で非凸目標を最適化する単純な収束証明を提供する。 この証明は本質的には、AdaGradの更新の数値と分母の間の相関を扱う複雑さを解消する新しい補助関数 $\xi$ に基づいている。 単純な証明を利用することで、既存の結果より厳密な結果を得ることができ、分析をいくつかの新しい重要なケースに拡張することができる。 具体的には、過剰にパラメータ化されたレジームに対しては、アダグラードに対して$\mathcal{o}(\frac{1}{\varepsilon^2})$の勾配ノルムが$\varepsilon$より小さいことを保証するために、わずか$\mathcal{o}(\frac{1}{\varepsilon^2})$の反復が必要であることを示す。 次に、有界な滑らかさの仮定を捨てて、局所滑らかさを勾配ノルムで成長させることができる$(L_0,L_1)$-smooth条件と呼ばれる滑らかさの現実的な仮定を考える。 また、補助関数 $\xi$ に基づいて、学習率が閾値より低い限り、アダグラードは$(l_0,l_1)$-smooth条件下での収束に成功したことを証明する。 さらに,学習速度の選択によらず収束が保証される均一な平滑性条件とは対照的に,(L_0,L_1)$-smooth条件下での学習率の要件は矛盾による証明によって必要であることを示す。 そこで本研究では,AdaGradの理解を深め,AdaGradの研究における新たな補助機能の力を示す。

関連論文リスト

• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。 また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
  論文  参考訳（メタデータ） (2023-04-27T06:27:37Z)
• A Note on Quantum Phase Estimation [0.0]
  より単純で自己完結したクエリローバウンドの証明を示す。 具体的には,ブール関数解析や逆法の知識を使わずに,基本線型代数から成り立つ。
  論文  参考訳（メタデータ） (2023-04-05T06:05:42Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  最適解への初期距離に依存する有界収束を示す。 AdaGrad-Normのハイバウンドが得られることを示す。
  論文  参考訳（メタデータ） (2023-02-28T18:42:11Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
  論文  参考訳（メタデータ） (2023-02-13T18:13:36Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces [24.52697154861819]
  AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。 我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
  論文  参考訳（メタデータ） (2020-08-14T20:46:38Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。