論文の概要: Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions

• arxiv url: http://arxiv.org/abs/2406.04592v1
• Date: Fri, 7 Jun 2024 02:55:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-10 15:48:53.511478
• Title: Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions
• Title（参考訳）: 平滑化と騒音推定を考慮した適応勾配法の収束解析
• Authors: Devyani Maladkar, Ruichen Jiang, Aryan Mokhtari,
• Abstract要約: 適応勾配法は間違いなくニューラルネットワークの最も成功した最適化アルゴリズムである。 適応的勾配法は、アダッド・エル・エル・アンド・ジオメトリ(Adad-ell/ell$ geometry)を形作る可能性があることを示す。
• 参考スコア（独自算出の注目度）: 18.47705532817026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adaptive gradient methods are arguably the most successful optimization algorithms for neural network training. While it is well-known that adaptive gradient methods can achieve better dimensional dependence than stochastic gradient descent (SGD) under favorable geometry for stochastic convex optimization, the theoretical justification for their success in stochastic non-convex optimization remains elusive. In this paper, we aim to close this gap by analyzing the convergence rates of AdaGrad measured by the $\ell_1$-norm of the gradient. Specifically, when the objective has $L$-Lipschitz gradient and the stochastic gradient variance is bounded by $\sigma^2$, we prove a worst-case convergence rate of $\tilde{\mathcal{O}}(\frac{\sqrt{d}L}{\sqrt{T}} + \frac{\sqrt{d} \sigma}{T^{1/4}})$, where $d$ is the dimension of the problem.We also present a lower bound of ${\Omega}(\frac{\sqrt{d}}{\sqrt{T}})$ for minimizing the gradient $\ell_1$-norm in the deterministic setting, showing the tightness of our upper bound in the noiseless case. Moreover, under more fine-grained assumptions on the smoothness structure of the objective and the gradient noise and under favorable gradient $\ell_1/\ell_2$ geometry, we show that AdaGrad can potentially shave a factor of $\sqrt{d}$ compared to SGD. To the best of our knowledge, this is the first result for adaptive gradient methods that demonstrates a provable gain over SGD in the non-convex setting.
• Abstract（参考訳）: 適応勾配法は、ニューラルネットワークトレーニングにおける最も成功した最適化アルゴリズムである。 適応勾配法は、確率的凸最適化に好適な幾何の下で確率的勾配降下(SGD)よりも優れた次元依存を達成できることはよく知られているが、確率的非凸最適化の成功の理論的正当性はいまだ解明されていない。 本稿では,勾配の$\ell_1$-normで測定されたAdaGradの収束速度を解析することにより,このギャップを埋めることを目的とする。 具体的には、目的が$L$-Lipschitzグラデーションを持ち、確率勾配分散が$\sigma^2$で有界である場合、最悪のケース収束率を$\tilde{\mathcal{O}}(\frac{\sqrt{d}L}{\sqrt{T}} + \frac{\sqrt{d} \sigma}{T^{1/4}})$とする。 さらに、目的物の滑らかさ構造と勾配雑音のよりきめ細かい仮定と、好ましい勾配$\ell_1/\ell_2$幾何の下では、AdaGrad が SGD と比較して $\sqrt{d}$ の因子をシェービングできることが示される。 我々の知る限り、これは非凸設定におけるSGDよりも証明可能な利得を示す適応勾配法の最初の結果である。

関連論文リスト

• From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
  最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。 本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-10-17T17:59:01Z)
• Directional Smoothness and Gradient Methods: Convergence and Adaptivity [16.779513676120096]
  我々は、最適化の経路に沿った目的の条件付けに依存する勾配降下に対する新しい準最適境界を開発する。 我々の証明の鍵となるのは方向の滑らかさであり、これは、目的の上のバウンドを開発するために使用する勾配変動の尺度である。 我々は,方向の滑らかさの知識を使わずとも,ポリアクのステップサイズと正規化GDが高速で経路依存の速度を得ることを示した。
  論文  参考訳（メタデータ） (2024-03-06T22:24:05Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods [22.052459124774504]
  本研究では,未調整のSGDに対する適応的手法により,スムーズさと情報優位性で問題を緩和することを示す。 この結果から, 指数関数依存性が欠如している場合, 未修正SGDに対する適応手法の理論的正当性について検討した。
  論文  参考訳（メタデータ） (2023-05-21T14:40:43Z)
• The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance [46.15915820243487]
  AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。 AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。
  論文  参考訳（メタデータ） (2022-02-11T17:37:54Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Private Adaptive Gradient Methods for Convex Optimization [32.3523019355048]
  適応的なステップサイズを持つグラディエント Descent (SGD) アルゴリズムの差分プライベート変種を提案・解析する。 両アルゴリズムの後悔に関する上限を与え、その境界が最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-25T16:46:45Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
  我々は、勾配収束法を期待する適応勾配法を証明した。 解析では、非理解勾配境界の最適化において、より適応的な勾配法に光を当てた。
  論文  参考訳（メタデータ） (2018-08-16T20:25:28Z)

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

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