論文の概要: 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の上限は,一定の条件下での対数係数まで厳密かつ改善不能であることを示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。