論文の概要: On the Last Iterate Convergence of Momentum Methods
- arxiv url: http://arxiv.org/abs/2102.07002v1
- Date: Sat, 13 Feb 2021 21:16:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-16 15:57:23.544175
- Title: On the Last Iterate Convergence of Momentum Methods
- Title（参考訳）: モーメント法の最後の反復収束について
- Authors: Xiaoyu Li and Mingrui Liu and Francesco Orabona
- Abstract要約: 我々は、任意の一定の運動量係数に対して、最後の反復が誤差に苦しむリプシッツおよび凸函数が存在することを初めて証明する。
凸関数と滑らかな関数の設定では、新しいSGDMアルゴリズムが自動的に$O(fraclog TT)$のレートで収束することを示しています。
- 参考スコア（独自算出の注目度）: 32.60494006038902
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: SGD with Momentum (SGDM) is widely used for large scale optimization of
machine learning problems. Yet, the theoretical understanding of this algorithm
is not complete. In fact, even the most recent results require changes to the
algorithm like an averaging scheme and a projection onto a bounded domain,
which are never used in practice. Also, no lower bound is known for SGDM. In
this paper, we prove for the first time that for any constant momentum factor,
there exists a Lipschitz and convex function for which the last iterate of SGDM
suffers from an error $\Omega(\frac{\log T}{\sqrt{T}})$ after $T$ steps. Based
on this fact, we study a new class of (both adaptive and non-adaptive)
Follow-The-Regularized-Leader-based SGDM algorithms with \emph{increasing
momentum} and \emph{shrinking updates}. For these algorithms, we show that the
last iterate has optimal convergence $O (\frac{1}{\sqrt{T}})$ for unconstrained
convex optimization problems. Further, we show that in the interpolation
setting with convex and smooth functions, our new SGDM algorithm automatically
converges at a rate of $O(\frac{\log T}{T})$. Empirical results are shown as
well.
- Abstract（参考訳）: SGD with Momentum (SGDM) は機械学習問題の大規模最適化に広く利用されている。
しかし、このアルゴリズムの理論的理解は完全ではない。
実際、最近の結果でさえも、平均化スキームや有界領域への射影のようなアルゴリズムの変更が必要であり、実際には使われない。
また、SGDMでは下限は知られていない。
本稿では、任意の定数運動量係数に対して、$T$ ステップの後に SGDM の最後の反復がエラー $\Omega(\frac{\log T}{\sqrt{T}})$ に苦しむ Lipschitz および凸関数が存在することを初めて証明する。
この事実に基づいて,<emph{increasing momentum} と \emph{shrinking updates} を用いたFollow-The-Regularized-Leader-based SGDMアルゴリズムの新たなクラスについて検討する。
これらのアルゴリズムでは、制約のない凸最適化問題に対して、最後の反復が最適収束$O(\frac{1}{\sqrt{T}})$であることが示される。
さらに、凸関数と滑らかな関数の補間設定において、我々の新しいSGDMアルゴリズムは自動的に$O(\frac{\log T}{T})$の速度で収束することを示す。
実証結果も示されています。
関連論文リスト
- MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis [27.679514676804057]
オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
論文 参考訳（メタデータ） (2020-10-26T01:33:05Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。