論文の概要: Stochastic Extragradient: General Analysis and Improved Rates

• arxiv url: http://arxiv.org/abs/2111.08611v1
• Date: Tue, 16 Nov 2021 16:49:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-17 16:18:58.904925
• Title: Stochastic Extragradient: General Analysis and Improved Rates
• Title（参考訳）: 確率外勾配:一般解析と改善率
• Authors: Eduard Gorbunov, Hugo Berard, Gauthier Gidel, Nicolas Loizou
• Abstract要約: Extragradient (SEG) 法は、min-max最適化と変分不等式問題を解くための最も一般的なアルゴリズムの1つである。 我々は,SEGのいくつかの変種を統一的に解析できる新しい理論フレームワークを開発した。 新たなSEG変種に対する我々のレートは、現在の最先端収束保証よりも優れており、制約の少ない仮定に依存している。
• 参考スコア（独自算出の注目度）: 23.29653334470774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Stochastic Extragradient (SEG) method is one of the most popular algorithms for solving min-max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. However, several important questions regarding the convergence properties of SEG are still open, including the sampling of stochastic gradients, mini-batching, convergence guarantees for the monotone finite-sum variational inequalities with possibly non-monotone terms, and others. To address these questions, in this paper, we develop a novel theoretical framework that allows us to analyze several variants of SEG in a unified manner. Besides standard setups, like Same-Sample SEG under Lipschitzness and monotonicity or Independent-Samples SEG under uniformly bounded variance, our approach allows us to analyze variants of SEG that were never explicitly considered in the literature before. Notably, we analyze SEG with arbitrary sampling which includes importance sampling and various mini-batching strategies as special cases. Our rates for the new variants of SEG outperform the current state-of-the-art convergence guarantees and rely on less restrictive assumptions.
• Abstract（参考訳）: 確率的超勾配法(seg)は、様々な機械学習タスクに現れるmin-max最適化と変分不等式問題(vip)を解決する最も一般的なアルゴリズムの1つである。 しかし、SEGの収束性に関するいくつかの重要な質問は、確率勾配のサンプリング、ミニバッチ、非単調な項を持つ単調有限サム変分不等式に対する収束保証など、まだオープンである。 そこで本研究では,SEGのいくつかの変種を統一的に解析できる理論的枠組みを開発した。 リプシッツ性の下でのSame-Sample SEGや一様有界な分散の下での独立サンプルSEGのような標準設定に加えて、本手法は文献でこれまで明らかに考えられていなかったSEGの変種を解析することができる。 特に,SEGを任意のサンプリングで分析し,重要サンプリングと様々なミニバッチ戦略を特殊なケースとして扱う。 新たなSEG変種に対する我々のレートは、現在の最先端収束保証よりも優れており、制約の少ない仮定に依存している。

関連論文リスト

• Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities [40.1331539540764]
  本稿では,3種類のVIPに対してランダムリシャッフル(SEG-RR)を用いたSEGの収束解析を行う。 我々は,SEG-RRが均一な置換サンプリングSEGよりも高速に収束する条件を導出する。 単調な設定では,SEG-RRの解析により,大きなバッチサイズを伴わずに任意の精度で収束が保証される。
  論文  参考訳（メタデータ） (2024-03-11T20:35:52Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• 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)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• 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)
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization [16.714109768541785]
  非非状態におけるSGD不変量を満たすすべての方法について単一の解析を行う。 また、PL条件下での非非状態におけるより高速な線形収束を得るための統一解析も提供する。
  論文  参考訳（メタデータ） (2020-06-12T08:58:03Z)

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

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