論文の概要: 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よりも証明可能な利得を示す適応勾配法の最初の結果である。
関連論文リスト
- 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) - Variance-reduced Clipping for Non-convex Optimization [24.765794811146144]
グラディエント・クリッピング(Gradient clipping)は、大規模言語モデリングのようなディープラーニングアプリケーションで用いられる技法である。
最近の実験的な訓練は、秩序の複雑さを緩和する、非常に特別な振る舞いを持っている。
論文 参考訳（メタデータ） (2023-03-02T00:57:38Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Generalization Bounds for Gradient Methods via Discrete and Continuous
Prior [8.76346911214414]
次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。
また、あるSGDの変種に対する新しい境界を得ることもできる。
論文 参考訳（メタデータ） (2022-05-27T07:23:01Z) - 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) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。