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

• arxiv url: http://arxiv.org/abs/2403.07723v1
• Date: Tue, 12 Mar 2024 15:01:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-13 21:02:50.717935
• Title: On the Last-Iterate Convergence of Shuffling Gradient Methods
• Title（参考訳）: シャッフル法の最後のIterate Convergenceについて
• Authors: Zijian Liu, Zhengyuan Zhou
• Abstract要約: 対象値に関して勾配法をシャッフルする際の最終点収束率を示す。 我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
• 参考スコア（独自算出の注目度）: 25.831462008050387
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shuffling gradient methods, which are also known as stochastic gradient descent (SGD) without replacement, are widely implemented in practice, particularly including three popular algorithms: 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-understanding 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 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（参考訳）: 置換なしの確率勾配降下法(sgd)としても知られるシャッフル勾配法(shuffling gradient method)は、特に3つの一般的なアルゴリズム(ランダムリシャッフル法(rr)、シャッフル1回法(so)、インクリメンタル勾配法(ig)を含む)を含む、広く実装されている。 経験的成功と比較して、シャッフル勾配法の理論的保証は長い間十分に理解されていなかった。 最近まで、収束率は凸関数の平均イテレートと(計量として二乗距離を用いる)強凸問題に対する最後のイテレートに対して確立されていた。 しかし、関数値ギャップを収束基準として使う場合、既存の理論では、異なる設定(例えば制約付き最適化)で最後の反復の良好な性能を解釈できない。 この実践と理論のギャップを埋めるため、強い凸性がなくても、対象値に対するシュッフリング勾配法におけるラストイテレート収束率を証明できる。 我々の新しい結果は、(ほぼ)既存の最下限と一致するか、あるいは平均的な上限に対して以前の最上限と同速である。

関連論文リスト

• 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)

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

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