論文の概要: Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions

• arxiv url: http://arxiv.org/abs/2302.14043v2
• Date: Sun, 12 Nov 2023 07:55:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-14 22:15:30.403695
• Title: Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions
• Title（参考訳）: 構造的非単調変分不等式に対するシングルコール確率的漸進法:ウェイカー条件による解析の改善
• Authors: Sayantan Choudhury, Eduard Gorbunov and Nicolas Loizou
• Abstract要約: シングルコール・エクストラグラディエント法は、大規模なmin-max最適化問題を解くための最も効率的なアルゴリズムの1つである。 i)準強単調問題(強単調問題の一般化)と(ii)弱ミンティ変分不等式(単調とミニティVIPの一般化)の2つのクラスに対して収束保証を提供する。 我々の収束分析は、重要なサンプリングと様々なミニバッチ戦略を特別な場合として含む任意のサンプリングパラダイムの下で成り立っている。
• 参考スコア（独自算出の注目度）: 21.681130192954583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Single-call stochastic extragradient methods, like stochastic past extragradient (SPEG) and stochastic optimistic gradient (SOG), have gained a lot of interest in recent years and are one of the most efficient algorithms for solving large-scale min-max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. However, despite their undoubted popularity, current convergence analyses of SPEG and SOG require a bounded variance assumption. In addition, several important questions regarding the convergence properties of these methods are still open, including mini-batching, efficient step-size selection, and convergence guarantees under different sampling strategies. In this work, we address these questions and provide convergence guarantees for two large classes of structured non-monotone VIPs: (i) quasi-strongly monotone problems (a generalization of strongly monotone problems) and (ii) weak Minty variational inequalities (a generalization of monotone and Minty VIPs). We introduce the expected residual condition, explain its benefits, and show how it can be used to obtain a strictly weaker bound than previously used growth conditions, expected co-coercivity, or bounded variance assumptions. Equipped with this condition, we provide theoretical guarantees for the convergence of single-call extragradient methods for different step-size selections, including constant, decreasing, and step-size-switching rules. Furthermore, our convergence analysis holds under the arbitrary sampling paradigm, which includes importance sampling and various mini-batching strategies as special cases.
• Abstract（参考訳）: 近年,seg (stochastic past extragradient) やsog (stochastic progressive gradient) のような単発確率的超勾配法が注目され,様々な機械学習タスクに現れる大規模min-max最適化と変分不等式問題 (vip) を解決するための最も効率的なアルゴリズムの1つである。 しかし、その不確かさにもかかわらず、SPEG と SOG の現在の収束解析は有界な分散仮定を必要とする。 加えて、これらのメソッドの収束特性に関するいくつかの重要な質問は、ミニバッチ、効率的なステップサイズ選択、異なるサンプリング戦略下での収束保証など、まだオープンである。 本稿では,これらの問題に対処し,構造化非単調vipの2つの大きなクラスに対する収束保証を提供する。 (i)準強単調問題(強単調問題の一般化)及び (II)弱いミンティ変量不等式(モノトーンとミンティVIPの一般化) 我々は, 期待残余条件を導入し, その利点を説明し, 従来使用されていた成長条件, 期待共役性, 有界分散仮定よりも厳密に弱い境界を得るためにどのように使用できるかを示す。 この条件を満たし、定数、減少、およびステップサイズ切換ルールを含む異なるステップサイズ選択に対して、シングルコール超グレードメソッドの収束に関する理論的保証を提供する。 さらに, コンバージェンス解析は, 重要サンプリングと様々なミニバッチ戦略を特別な場合として含む任意のサンプリングパラダイムの下で行う。

関連論文リスト

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• 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)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Distributed Stochastic Optimization under a General Variance Condition [13.911633636387059]
  分散最適化は最近、大規模な機械学習問題の解決に効果があるとして、大きな注目を集めている。 我々は、古典的フェデレーション平均化(Avg)を再考し、滑らかな非対象関数に対して、緩やかな分散しか持たない収束結果を確立する。 ほぼ1つの定常収束点も勾配条件の下で成立する。
  論文  参考訳（メタデータ） (2023-01-30T05:48:09Z)
• 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)
• Stochastic Extragradient: General Analysis and Improved Rates [23.29653334470774]
  Extragradient (SEG) 法は、min-max最適化と変分不等式問題を解くための最も一般的なアルゴリズムの1つである。 我々は,SEGのいくつかの変種を統一的に解析できる新しい理論フレームワークを開発した。 新たなSEG変種に対する我々のレートは、現在の最先端収束保証よりも優れており、制約の少ない仮定に依存している。
  論文  参考訳（メタデータ） (2021-11-16T16:49:31Z)
• 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)

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

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