論文の概要: Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity

• arxiv url: http://arxiv.org/abs/2310.17998v1
• Date: Fri, 27 Oct 2023 09:16:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-30 14:22:49.058705
• Title: Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity
• Title（参考訳）: アダムの反復複雑度の上界と下界の間のギャップを閉鎖する
• Authors: Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, Wei Chen
• Abstract要約: 我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
• 参考スコア（独自算出の注目度）: 51.96093077151991
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, Arjevani et al. [1] established a lower bound of iteration complexity for the first-order optimization under an $L$-smooth condition and a bounded noise variance assumption. However, a thorough review of existing literature on Adam's convergence reveals a noticeable gap: none of them meet the above lower bound. In this paper, we close the gap by deriving a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our results remain valid across a broad spectrum of hyperparameters. Especially with properly chosen hyperparameters, we derive an upper bound of the iteration complexity of Adam and show that it meets the lower bound for first-order optimizers. To the best of our knowledge, this is the first to establish such a tight upper bound for Adam's convergence. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate and to convert the first-order term in the Descent Lemma to the gradient norm, which may be of independent interest.
• Abstract（参考訳）: 最近、Arjevaniら。 [1] は 1次最適化において、$L$-smooth条件と有界雑音分散仮定の下で、より低い繰り返しの複雑性を確立した。 しかし、Adamの収束に関する既存の文献の徹底的なレビューでは、顕著なギャップが明らかになっている。 本稿では,adam の新たな収束保証を導出し,l$-smooth 条件と有界雑音分散条件のみを導出することでギャップを解消する。 我々の結果は幅広いハイパーパラメータで有効である。 特に適切に選択されたハイパーパラメータでは、Adamの反復複雑性の上限を導き、一階最適化器の下位境界を満たすことを示す。 我々の知る限りでは、アダムの収束に対するそのような厳密な上限を確立するのはこれが初めてである。 我々の証明は、運動量と適応学習率の絡み合いを扱う新しい手法を利用し、Descent Lemmaの1次項を独立性のある勾配ノルムに変換する。

関連論文リスト

• Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance [23.112775335244258]
  我々はまず,適応学習率を持つAdamの特殊なケースであるRMSPropを分析する。 我々は、勾配ノルムの関数でもある降下補題において、新しい上界一階項を開発する。 RMSPropとAdamの両者の結果は、citearvani2023lowerで確立された複雑さと一致した。
  論文  参考訳（メタデータ） (2024-04-01T19:17:45Z)
• On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond [35.65852208995095]
  我々は,非一様有界な滑らかさの条件下で,AdamがSGDMよりも高速な収束を実現することを示した。 その結果,(1)決定論的環境下では,Adamは決定論的一階の収束率の既知下限を達成でき,一方,GDM(Gradient Descent with Momentum)の収束率は初期関数値に高い順序依存性を持つことがわかった。
  論文  参考訳（メタデータ） (2024-03-22T11:57:51Z)
• High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noise [4.9495085874952895]
  我々はAdamが高い確率で定常点に収束できることを示し、$mathcalOleft(rm poly(log T)/sqrtTright)$を座標ワイドな「アフィン」ノイズ分散の下で表す。 また、Adamの閉包は$mathcalOleft(rm poly(left T)right)$の順序でノイズレベルに適応していることも明らかにされている。
  論文  参考訳（メタデータ） (2023-11-03T15:55:53Z)
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case [0.0]
  本稿では,バニラ・アダムの収束と非エルゴード収束の課題について考察する。 これらの発見は、非ゴーディック最適化問題を解くために、Adamの確固たる理論基盤を構築する。
  論文  参考訳（メタデータ） (2023-07-20T12:02:17Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。 また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
  論文  参考訳（メタデータ） (2023-04-27T06:27:37Z)
• A Novel Convergence Analysis for Algorithms of the Adam Family [105.22760323075008]
  本稿ではAdam, AMSGrad, AdaboundなどのAdamスタイルの手法群に対する収束の一般的な証明を示す。 我々の分析は非常に単純で汎用的なので、より広範な非構成最適化問題の族を解くための収束を確立するために利用することができる。
  論文  参考訳（メタデータ） (2021-12-07T02:47:58Z)
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective [49.17352150219212]
  Federated AveragingFedAvg(ローカルSGD)は、Federated Learning(FL)で最も人気のあるアルゴリズムの1つである。 微分方程式(SDE)の観点から、この量を解析する方法を示す。
  論文  参考訳（メタデータ） (2021-11-05T22:16:11Z)
• Adam$^+$: A Stochastic Method with Adaptive Variance Reduction [56.051001950733315]
  Adamはディープラーニングアプリケーションに広く使われている最適化手法である。 我々はAdam$+$(Adam-plusと発音する)という新しい方法を提案する。 画像分類,言語モデリング,自動音声認識など,さまざまなディープラーニングタスクに関する実証研究により,Adam$+$がAdamを著しく上回ることを示した。
  論文  参考訳（メタデータ） (2020-11-24T09:28:53Z)
• 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)

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

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