論文の概要: Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance
- arxiv url: http://arxiv.org/abs/2406.04142v1
- Date: Thu, 6 Jun 2024 15:08:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 14:30:04.822557
- Title: Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance
- Title（参考訳）: 確率的ポリアークステップサイズとモーメント:収束保証と実用性
- Authors: Dimitris Oikonomou, Nicolas Loizou,
- Abstract要約: 我々はヘビーボール法(SHB)の更新規則に適した新しいポリアク型変種を提案し,検討する。
MomSPS$_max$ に対して、(仮定なしで)凸および滑らかな問題に対する解の近傍に SHB の保証を提供する。
その他の2つの変種である MomDecSPS と MomAdaSPS は、SHB の最初の適応的なステップサイズであり、事前の知識なしに正確な最小値への収束を保証する。
- 参考スコア（独自算出の注目度）: 10.11126899274029
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic gradient descent with momentum, also known as Stochastic Heavy Ball method (SHB), is one of the most popular algorithms for solving large-scale stochastic optimization problems in various machine learning tasks. In practical scenarios, tuning the step-size and momentum parameters of the method is a prohibitively expensive and time-consuming process. In this work, inspired by the recent advantages of stochastic Polyak step-size in the performance of stochastic gradient descent (SGD), we propose and explore new Polyak-type variants suitable for the update rule of the SHB method. In particular, using the Iterate Moving Average (IMA) viewpoint of SHB, we propose and analyze three novel step-size selections: MomSPS$_{\max}$, MomDecSPS, and MomAdaSPS. For MomSPS$_{\max}$, we provide convergence guarantees for SHB to a neighborhood of the solution for convex and smooth problems (without assuming interpolation). If interpolation is also satisfied, then using MomSPS$_{\max}$, SHB converges to the true solution at a fast rate matching the deterministic HB. The other two variants, MomDecSPS and MomAdaSPS, are the first adaptive step-sizes for SHB that guarantee convergence to the exact minimizer without prior knowledge of the problem parameters and without assuming interpolation. The convergence analysis of SHB is tight and obtains the convergence guarantees of SGD with stochastic Polyak step-sizes as a special case. We supplement our analysis with experiments that validate the theory and demonstrate the effectiveness and robustness of the new algorithms.
- Abstract（参考訳）: Stochastic Heavy Ball Method (SHB) は、様々な機械学習タスクにおける大規模確率最適化問題の解法として最も一般的なアルゴリズムの1つである。
実際のシナリオでは、手法のステップサイズと運動量パラメータをチューニングするのは、極めて高価で時間を要するプロセスである。
本研究は,確率勾配降下(SGD)の性能における確率的ポリアックの段差の最近の利点に着想を得て,SHB法の更新規則に適した新しいポリアック型変種を提案し,検討する。
特に、SHBの反復移動平均(IMA)視点を用いて、3つの新しいステップサイズ選択(MomSPS$_{\max}$, MomDecSPS, MomAdaSPS)を提案し、解析する。
MomSPS$_{\max}$ に対して、SHB の収束保証を凸および滑らかな問題(補間を仮定せずに)の解の近傍に与える。
補間も満たされるなら、MomSPS$_{\max}$ を用いて、SHB は決定論的 HB と一致する高速速度で真の解に収束する。
他の2つの変種であるMomDecSPSとMomAdaSPSはSHBの最初の適応的なステップサイズであり、問題パラメータの事前の知識や補間を仮定することなく、正確な最小値への収束を保証する。
SHBの収束解析は厳密であり、確率的ポリアークのステップサイズを持つSGDの収束保証を得る。
我々は,この理論を検証し,新しいアルゴリズムの有効性とロバスト性を実証する実験で解析を補足する。
関連論文リスト
- A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。
本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文 参考訳（メタデータ） (2024-05-24T21:09:19Z) - Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence
and Variance Reduction [26.9632099249085]
AdaSPSとAdaSLSと呼ばれる2種類の新しいSPSとSLSを提案し、非補間条件における収束を保証する。
我々は, AdaSPS と AdaSLS に新しい分散低減技術を導入し, $smashwidetildemathcalO(n+1/epsilon)$グラデーション評価を必要とするアルゴリズムを得る。
論文 参考訳（メタデータ） (2023-08-11T10:17:29Z) - Sharper Analysis for Minibatch Stochastic Proximal Point Methods:
Stability, Smoothness, and Deviation [41.082982732100696]
我々は,凸複合リスク最小化問題の解法として,近位点法(M-SPP)のミニバッチ変種について検討した。
ミニバッチサイズが$n$で二次数が$T$のM-SPPは、予想外収束の速さを楽しむことを示す。
小さい$n$-large-$T$設定では、この結果はSPP型アプローチの最もよく知られた結果を大幅に改善する。
論文 参考訳（メタデータ） (2023-01-09T00:13:34Z) - Formal guarantees for heuristic optimization algorithms used in machine
learning [6.978625807687497]
グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。
本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
論文 参考訳（メタデータ） (2022-07-31T19:41:22Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳（メタデータ） (2021-11-01T15:43:36Z) - Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants
via the Mirror Stochastic Polyak Stepsize [20.376216873620763]
比較的滑らかで滑らかな凸最適化の下でのミラー降下(SMD)の収束について検討した。
我々は、新しい適応的なステップサイズスキーム、ミラーポリアクステップサイズ(mSPS)を提案する。
論文 参考訳（メタデータ） (2021-10-28T19:49:40Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - The Role of Momentum Parameters in the Optimal Convergence of Adaptive
Polyak's Heavy-ball Methods [12.93796690939018]
適応型Polyak's Heavy-ball (HB) 法は最適な個人収束率を$O(frac1sqrtt)$とする。
新しい解析では,hb運動量とその時間的変動が凸最適化の高速化にどのように役立つかを示す。
論文 参考訳（メタデータ） (2021-02-15T02:57:14Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。