論文の概要: Adaptive Gradient Methods Can Be Provably Faster than SGD after Finite Epochs

• arxiv url: http://arxiv.org/abs/2006.07037v1
• Date: Fri, 12 Jun 2020 09:39:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 04:46:03.500540
• Title: Adaptive Gradient Methods Can Be Provably Faster than SGD after Finite Epochs
• Title（参考訳）: 適応勾配法は有限エポック後のsgdよりも高速であることが証明できる
• Authors: Xunpeng Huang, Hao Zhou, Runxin Xu, Zhe Wang and Lei Li
• Abstract要約: 適応勾配法は有限時間後にランダムシャッフルSGDよりも高速であることを示す。 我々の知る限り、適応的勾配法は有限時間後にSGDよりも高速であることを示すのはこれが初めてである。
• 参考スコア（独自算出の注目度）: 25.158203665218164
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adaptive gradient methods have attracted much attention of machine learning communities due to the high efficiency. However their acceleration effect in practice, especially in neural network training, is hard to analyze, theoretically. The huge gap between theoretical convergence results and practical performances prevents further understanding of existing optimizers and the development of more advanced optimization methods. In this paper, we provide adaptive gradient methods a novel analysis with an additional mild assumption, and revise AdaGrad to \radagrad for matching a better provable convergence rate. To find an $\epsilon$-approximate first-order stationary point in non-convex objectives, we prove random shuffling \radagrad achieves a $\tilde{O}(T^{-1/2})$ convergence rate, which is significantly improved by factors $\tilde{O}(T^{-1/4})$ and $\tilde{O}(T^{-1/6})$ compared with existing adaptive gradient methods and random shuffling SGD, respectively. To the best of our knowledge, it is the first time to demonstrate that adaptive gradient methods can deterministically be faster than SGD after finite epochs. Furthermore, we conduct comprehensive experiments to validate the additional mild assumption and the acceleration effect benefited from second moments and random shuffling.
• Abstract（参考訳）: 適応勾配法は高い効率性のために機械学習コミュニティに大きな注目を集めている。 しかし、実際には、特にニューラルネットワークトレーニングにおける加速効果は、理論的には分析が難しい。 理論収束結果と実用性能の間の大きなギャップは、既存の最適化手法のさらなる理解とより高度な最適化手法の開発を妨げる。 本稿では,より穏やかな仮定による新しい解析法である適応勾配法と,より証明可能な収束率に適合するアダグラードからシュラダグラードへ修正する。 非凸対象における$\epsilon$-approximate 1次定常点を求めるために、ランダムシャッフル \radagrad は $\tilde{O}(T^{-1/4})$ と $\tilde{O}(T^{-1/6})$ で大幅に改善された $\tilde{O}(T^{-1/6})$ を、既存の適応勾配法とランダムシャッフル SGD と比較して証明する。 我々の知る限り、適応勾配法が有限エポック後のSGDよりも決定論的に高速であることを示すのはこれが初めてである。 さらに,第2モーメントとランダムシャッフルの利点を生かした軽度な仮定と加速度効果を検証するため,総合的な実験を行った。

関連論文リスト

• A Methodology Establishing Linear Convergence of Adaptive Gradient Methods under PL Inequality [5.35599092568615]
  AdaGrad と Adam は、コスト関数が滑らかで、Polyak-Lojasiewicz の不等式を満たすときに線型収束することを示す。 我々のフレームワークは、他の変種Adamの線形収束解析に利用できる可能性がある。
  論文  参考訳（メタデータ） (2024-07-17T14:56:21Z)
• Adaptive Federated Learning Over the Air [108.62635460744109]
  オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。 解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
  論文  参考訳（メタデータ） (2024-03-11T09:10:37Z)
• High Probability Analysis for Non-Convex Stochastic Optimization with Clipping [13.025261730510847]
  勾配クリッピングは重み付きニューラルネットワークを扱う技術である。 ほとんどの理論上の保証は、予測外解析のみを提供し、性能のみを提供する。 我々の分析は、勾配クリッピングによる最適化アルゴリズムの理論的保証について、比較的完全な図を提供している。
  論文  参考訳（メタデータ） (2023-07-25T17:36:56Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる 新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
  論文  参考訳（メタデータ） (2021-05-13T04:23:07Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
  本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。 我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。 一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
  論文  参考訳（メタデータ） (2020-09-23T20:02:00Z)
• 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)

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

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