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

• arxiv url: http://arxiv.org/abs/2406.04592v2
• Date: Fri, 11 Oct 2024 03:23:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-14 13:29:07.763576
• Title: Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions
• Title（参考訳）: 平滑化と騒音推定を考慮した適応勾配法の収束解析
• Authors: Ruichen Jiang, Devyani Maladkar, Aryan Mokhtari,
• Abstract要約: AdaGradは特定の条件下では$d$でSGDより優れていることを示す。 これを動機として、目的物の滑らかさ構造と勾配のばらつきを仮定する。
• 参考スコア（独自算出の注目度）: 18.47705532817026
• License:
• Abstract: Adaptive gradient methods, such as AdaGrad, are among the most successful optimization algorithms for neural network training. While these methods are known to 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 fact, under standard assumptions of Lipschitz gradients and bounded noise variance, it is known that SGD is worst-case optimal (up to absolute constants) in terms of finding a near-stationary point with respect to the $\ell_2$-norm, making further improvements impossible. Motivated by this limitation, we introduce refined assumptions on the smoothness structure of the objective and the gradient noise variance, which better suit the coordinate-wise nature of adaptive gradient methods. Moreover, we adopt the $\ell_1$-norm of the gradient as the stationarity measure, as opposed to the standard $\ell_2$-norm, to align with the coordinate-wise analysis and obtain tighter convergence guarantees for AdaGrad. Under these new assumptions and the $\ell_1$-norm stationarity measure, we establish an upper bound on the convergence rate of AdaGrad and a corresponding lower bound for SGD. In particular, for certain configurations of problem parameters, we show that the iteration complexity of AdaGrad outperforms SGD by a factor of $d$. To the best of our knowledge, this is the first result to demonstrate a provable gain of adaptive gradient methods over SGD in a non-convex setting. We also present supporting lower bounds, including one specific to AdaGrad and one applicable to general deterministic first-order methods, showing that our upper bound for AdaGrad is tight and unimprovable up to a logarithmic factor under certain conditions.
• Abstract（参考訳）: AdaGradのような適応勾配法は、ニューラルネットワークトレーニングにおいて最も成功した最適化アルゴリズムの一つである。 これらの手法は、確率的凸最適化に有利な幾何の下で、確率的勾配降下(SGD)よりも優れた次元依存を実現することが知られているが、確率的非凸最適化の成功の理論的正当性は、いまだ解明されていない。 実際、リプシッツ勾配と有界雑音分散の標準的な仮定の下では、SGD は $\ell_2$-norm に関する準定常点を見つけるという点で最悪のケース最適(絶対定数まで)であることが知られている。 この制限により、目的物の滑らかさ構造と勾配雑音の分散に関する洗練された仮定を導入し、適応勾配法の座標性によく適合する。 さらに、標準の $\ell_2$-norm とは対照的に、勾配の $\ell_1$-norm を定常度尺度として採用し、座標解析と整合し、AdaGrad のより厳密な収束保証を得る。 これらの新しい仮定と$\ell_1$-normの定常度測度の下で、AdaGrad の収束率と SGD の対応する下界の上限を確立する。 特に、問題パラメータの特定の構成について、AdaGradの反復複雑性が$d$の係数でSGDより優れていることを示す。 我々の知る限りでは、これは非凸条件下でSGD上の適応勾配法が証明可能なゲインを示す最初の結果である。 また,AdaGradに特有な部分と,一般決定論的一階法に適用可能な部分を含む下界を支持することにより,AdaGradの上限は,一定の条件下での対数係数まで厳密かつ改善不能であることを示す。

関連論文リスト

• Gradient Normalization with(out) Clipping Ensures Convergence of Nonconvex SGD under Heavy-Tailed Noise with Improved Results [60.92029979853314]
  本稿では,NSGDCを含まない勾配正規化(NSGDC-VR)について検討する。 両アルゴリズムの理論的結果の大幅な改善について述べる。
  論文  参考訳（メタデータ） (2024-10-21T22:40:42Z)
• 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)
• 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)

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

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