論文の概要: Stochastic Extragradient with Random Reshuffling: Improved Convergence
for Variational Inequalities
- arxiv url: http://arxiv.org/abs/2403.07148v1
- Date: Mon, 11 Mar 2024 20:35:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 23:31:07.516035
- Title: Stochastic Extragradient with Random Reshuffling: Improved Convergence
for Variational Inequalities
- Title（参考訳）: ランダム再帰を伴う確率的超次数--変分不等式に対する収束の改善
- Authors: Konstantinos Emmanouilidis, Ren\'e Vidal, Nicolas Loizou
- Abstract要約: 本稿では,3種類のVIPに対してランダムリシャッフル(SEG-RR)を用いたSEGの収束解析を行う。
我々は,SEG-RRが均一な置換サンプリングSEGよりも高速に収束する条件を導出する。
単調な設定では,SEG-RRの解析により,大きなバッチサイズを伴わずに任意の精度で収束が保証される。
- 参考スコア（独自算出の注目度）: 11.339003302353163
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Stochastic Extragradient (SEG) method is one of the most popular
algorithms for solving finite-sum min-max optimization and variational
inequality problems (VIPs) appearing in various machine learning tasks.
However, existing convergence analyses of SEG focus on its with-replacement
variants, while practical implementations of the method randomly reshuffle
components and sequentially use them. Unlike the well-studied with-replacement
variants, SEG with Random Reshuffling (SEG-RR) lacks established theoretical
guarantees. In this work, we provide a convergence analysis of SEG-RR for three
classes of VIPs: (i) strongly monotone, (ii) affine, and (iii) monotone. We
derive conditions under which SEG-RR achieves a faster convergence rate than
the uniform with-replacement sampling SEG. In the monotone setting, our
analysis of SEG-RR guarantees convergence to an arbitrary accuracy without
large batch sizes, a strong requirement needed in the classical
with-replacement SEG. As a byproduct of our results, we provide convergence
guarantees for Shuffle Once SEG (shuffles the data only at the beginning of the
algorithm) and the Incremental Extragradient (does not shuffle the data). We
supplement our analysis with experiments validating empirically the superior
performance of SEG-RR over the classical with-replacement sampling SEG.
- Abstract（参考訳）: Stochastic Extragradient (SEG) 法は、様々な機械学習タスクに現れる有限サム min-max 最適化と変分不等式問題(VIP)を解決するアルゴリズムの1つである。
しかし,既存のsegのコンバージェンス解析では,各コンポーネントをランダムにリライトし,逐次的に使用するのに対し,既存のsegのコンバーゼンス解析ではその変種に焦点が当てられている。
良く研究された代替型とは異なり、ランダムリシャッフル(SEG-RR)付きSEGは確立された理論的保証を欠いている。
本稿では,3種類のVIPに対してSEG-RRの収束解析を行う。
(i)強い単調。
(ii)アフィン、及び
(iii)単音。
我々は,SEG-RRが均一な置換サンプリングSEGよりも高速に収束する条件を導出する。
モノトーン設定では,SEG-RR解析により,従来の非置換SEGに必要とされる強い要件である大きなバッチサイズを伴わない任意の精度での収束が保証される。
結果の副産物として、Shuffle Once SEG(アルゴリズムの開始時にのみデータをシャッフルする)とIncremental Extragradient(データをシャッフルしない)の収束保証を提供する。
本研究は,SEG-RRの古典的置換サンプリングSEGよりも優れた性能を示す実験により,解析を補完する。
関連論文リスト
- Stochastic Methods in Variational Inequalities: Ergodicity, Bias and
Refinements [19.524063429548278]
Extragradient (SEG) と Gradient Descent Ascent (SGDA) は min-max 最適化と変分不等式問題に対する優越アルゴリズムである。
これらのアルゴリズムに固有の本質的な構造を定量化し定量化するための我々の取り組み。
定数のステップサイズSEG/SGDAを時間同質マルコフ連鎖として再キャストすることにより、大数の第一種法則と中心極限定理を確立する。
論文 参考訳（メタデータ） (2023-06-28T18:50:07Z) - Single-Call Stochastic Extragradient Methods for Structured Non-monotone
Variational Inequalities: Improved Analysis under Weaker Conditions [21.681130192954583]
シングルコール・エクストラグラディエント法は、大規模なmin-max最適化問題を解くための最も効率的なアルゴリズムの1つである。
i)準強単調問題(強単調問題の一般化)と(ii)弱ミンティ変分不等式(単調とミニティVIPの一般化)の2つのクラスに対して収束保証を提供する。
我々の収束分析は、重要なサンプリングと様々なミニバッチ戦略を特別な場合として含む任意のサンプリングパラダイムの下で成り立っている。
論文 参考訳（メタデータ） (2023-02-27T18:53:28Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient
Methods [73.35353358543507]
SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。
本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。
本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
論文 参考訳（メタデータ） (2022-02-15T09:17:39Z) - On the Convergence of mSGD and AdaGrad for Stochastic Optimization [0.696125353550498]
凸降下(SGD)は、過去10年間に機械学習に大きく開発され、広く応用されてきた。
モーメントベースのSGD(mSGD)や適応的勾配最適化(AdaGrad)など、多くの競合や応用においてSGDよりも優れている修正SGD型アルゴリズムもある。
我々は,機械学習における任意の滑らかな(不可能かもしれない)損失関数に対するmSGDとAdaGradの収束解析に着目する。
論文 参考訳（メタデータ） (2022-01-26T22:02:21Z) - Stochastic Extragradient: General Analysis and Improved Rates [23.29653334470774]
Extragradient (SEG) 法は、min-max最適化と変分不等式問題を解くための最も一般的なアルゴリズムの1つである。
我々は,SEGのいくつかの変種を統一的に解析できる新しい理論フレームワークを開発した。
新たなSEG変種に対する我々のレートは、現在の最先端収束保証よりも優れており、制約の少ない仮定に依存している。
論文 参考訳（メタデータ） (2021-11-16T16:49:31Z) - 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 the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - SGD with shuffling: optimal rates without component convexity and large
epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。
我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。
我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文 参考訳（メタデータ） (2020-06-12T05:00:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。