論文の概要: Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements

• arxiv url: http://arxiv.org/abs/2501.00511v1
• Date: Tue, 31 Dec 2024 15:49:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 17:12:12.413064
• Title: Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
• Title（参考訳）: Flip-Flop Shuffling と Anchoring による確率的エクストラグラディエント: 改善の可能性
• Authors: Jiseok Chae, Chulhee Yun, Donghwan Kim,
• Abstract要約: ミニマックス最適化では、凸凹(C-C)問題において降下昇降法よりも優れているため、Extragradient (EG)法が広く研究されている。 しかし、EG(SEG)はC-C問題、特に非拘束症例で成功している。
• 参考スコア（独自算出の注目度）: 16.30388653278298
• License:
• Abstract: In minimax optimization, the extragradient (EG) method has been extensively studied because it outperforms the gradient descent-ascent method in convex-concave (C-C) problems. Yet, stochastic EG (SEG) has seen limited success in C-C problems, especially for unconstrained cases. Motivated by the recent progress of shuffling-based stochastic methods, we investigate the convergence of shuffling-based SEG in unconstrained finite-sum minimax problems, in search of convergent shuffling-based SEG. Our analysis reveals that both random reshuffling and the recently proposed flip-flop shuffling alone can suffer divergence in C-C problems. However, with an additional simple trick called anchoring, we develop the SEG with flip-flop anchoring (SEG-FFA) method which successfully converges in C-C problems. We also show upper and lower bounds in the strongly-convex-strongly-concave setting, demonstrating that SEG-FFA has a provably faster convergence rate compared to other shuffling-based methods.
• Abstract（参考訳）: ミニマックス最適化では、凸凹(C-C)問題において勾配降下法よりも優れているため、Extragradient (EG)法が広く研究されている。 しかし, 難治性EG (SEG) はC-C問題, 特に非拘束症例では, あまり成功しなかった。 シャッフル法に基づく確率的手法の最近の進歩に触発され, シャッフル法に基づくSEGの収束性を求めるために, シャッフル法に基づくSEGの非制約有限サムミニマックス問題における収束性について検討した。 解析の結果, ランダムリシャッフルと最近提案されたフリップフロップシャッフルだけではC-C問題にばらつきが生じる可能性が示唆された。 しかし, アンカー法と呼ばれる簡単な手法により, C-C 問題に収束するフリップフロップアンカー法 (SEG-FFA) を開発した。 また,SEG-FFAの収束速度が他のシャッフル法に比べて高いことを示す。

関連論文リスト

• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• 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)
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods [12.173568611144626]
  騒音やステップによって1次サドル勾配降下法(SCSG)が摂動可能であることを示す。 この問題を解決するために、別のステップが提案される。 提案手法は,サドル点に対するCNC-SCSGD法をさらに取り入れることを目的としている。
  論文  参考訳（メタデータ） (2021-03-07T18:09:43Z)
• Accelerated Gradient Methods for Sparse Statistical Learning with Nonconvex Penalties [10.913266721195916]
  ネステロフの加速シミュレーション(AG)は、対物関数を2つ、凸損失とペナルティ関数の2つに最適化する一般的な手法である。 最近のNesterov's AGの提案は一般化しているが、統計学習問題には適用されていない。 本稿では,非AGアルゴリズムを高次元かつスパースな統計的学習問題に適用することを検討する。
  論文  参考訳（メタデータ） (2020-09-22T15:37:09Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)

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

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