Fugu-MT 論文翻訳(概要): On the Last-Iterate Convergence of Shuffling Gradient Methods

論文の概要: On the Last-Iterate Convergence of Shuffling Gradient Methods

arxiv url: http://arxiv.org/abs/2403.07723v3
Date: Thu, 6 Jun 2024 01:52:22 GMT
ステータス: 処理完了
システム内更新日: 2024-06-07 20:52:38.470031
Title: On the Last-Iterate Convergence of Shuffling Gradient Methods
Title（参考訳）: シャッフル法の最後のIterate Convergenceについて
Authors: Zijian Liu, Zhengyuan Zhou,
Abstract要約: 対象値に関して勾配法をシャッフルする際の最終点収束率を初めて証明する。我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
参考スコア（独自算出の注目度）: 21.865728815935665
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Shuffling gradient methods are widely used in modern machine learning tasks and include three popular implementations: Random Reshuffle (RR), Shuffle Once (SO), and Incremental Gradient (IG). Compared to the empirical success, the theoretical guarantee of shuffling gradient methods was not well-understood for a long time. Until recently, the convergence rates had just been established for the average iterate for convex functions and the last iterate for strongly convex problems (using squared distance as the metric). However, when using the function value gap as the convergence criterion, existing theories cannot interpret the good performance of the last iterate in different settings (e.g., constrained optimization). To bridge this gap between practice and theory, we prove the first last-iterate convergence rates for shuffling gradient methods with respect to the objective value even without strong convexity. Our new results either (nearly) match the existing last-iterate lower bounds or are as fast as the previous best upper bounds for the average iterate.
Abstract（参考訳）: シャッフル勾配法は現代の機械学習タスクで広く使われており、Random Reshuffle (RR)、Shuffle Once (SO)、Incrmental Gradient (IG)の3つの一般的な実装を含んでいる。経験的成功と比較して、シャッフル勾配法の理論的保証は長い間十分に理解されていなかった。最近まで、収束速度は凸関数の平均反復率と強い凸問題(計量として2乗距離を用いる)の最終反復率に対して確立されていた。しかし、関数値ギャップを収束基準として使う場合、既存の理論では、異なる設定(例えば制約付き最適化)で最後の繰り返しの良好な性能を解釈することはできない。この実践と理論のギャップを埋めるために、強い凸性をもたずに、目的値に関して勾配法をシャッフルする最初の最終点収束率を証明した。我々の新しい結果は、(ほぼ)既存の最下限の値と一致するか、あるいは、平均的イテレートの前の最上限の速度に等しいかのどちらかです。

関連論文リスト

Last Iterate Convergence of Incremental Methods and Applications in Continual Learning [10.811735264028348]
連続学習における応用により、漸進的勾配法と漸進的近位法の両方の最後の繰り返しに対する収束保証を得る。一般化を伴う連続学習のモデルとしての漸進的近位法について検討し,大惨な忘れ込みを防ぐために大量の正規化が不可欠であると主張している。
論文参考訳（メタデータ） (2024-03-11T16:24:26Z)
Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文参考訳（メタデータ） (2024-02-04T05:54:51Z)
Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文参考訳（メタデータ） (2023-12-13T21:41:06Z)
Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization [21.022322975077653]
等式制約付き連続最適化問題の解法が近年注目されている。収束保証は、ゼロを測定するための勾配の期待値に制限されている。また,SQPアルゴリズムにより生成した予備値,ラグランジュ測度,ステーション測度に対する新たなほぼ収束保証を証明した。
論文参考訳（メタデータ） (2023-08-07T16:03:40Z)
Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文参考訳（メタデータ） (2023-04-23T20:05:09Z)
High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文参考訳（メタデータ） (2023-02-02T10:37:23Z)
On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration [33.247600151322466]
我々は、滑らかな凸関数の標準設定において、AdaGradとその変種についてより深く理解する。まず、制約のない問題に対して、バニラ AdaGrad の収束率を明示的に拘束する新しい手法を示す。第二に、平均的な反復ではなく、最後の反復の収束を示すことのできる AdaGrad の変種を提案する。
論文参考訳（メタデータ） (2022-09-29T14:44:40Z)
Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文参考訳（メタデータ） (2022-04-20T07:14:21Z)
On Almost Sure Convergence Rates of Stochastic Gradient Methods [11.367487348673793]
勾配法で得られるほぼ確実な収束速度が、可能な限り最適な収束速度に任意に近づくことを示す。非客観的関数に対しては、二乗勾配ノルムの重み付き平均がほぼ確実に収束するだけでなく、ほぼ確実に0となることを示す。
論文参考訳（メタデータ） (2022-02-09T06:05:30Z)
Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文参考訳（メタデータ） (2021-10-20T02:25:25Z)
High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文参考訳（メタデータ） (2021-06-28T00:17:01Z)

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

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