論文の概要: On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities
- arxiv url: http://arxiv.org/abs/2608.06182v1
- Date: Thu, 06 Aug 2026 15:42:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-07 17:43:06.783968
- Title: On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities
- Title（参考訳）: 単調変分不等式に対する同一サンプルおよび独立サンプル確率外勾配について
- Abstract要約: 本研究では, 単調変分不等式問題(VIP)を, 実現可能な集合上で解くための段階的手法について検討した。
我々は、緩和された仮定の集合の下で、各SEG変種に対する高確率制限ギャップ収束を確立する。
我々は、I-SEGの終点収束がS-SEGに対してほぼ確実に失敗することを保証している既知の非対称な二重ステップサイズ選択を示す。
- 参考スコア（独自算出の注目度）: 15.2286904549704
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.
- Abstract（参考訳）: 本研究では,モノトーン変量不等式問題(VIP)を実現可能な集合上で解くための確率的指数分解法(SEG)について検討した。
漸進性はVIPの基本的アルゴリズムであり、その決定論的収束理論はよく開発されているが、その確率的対向性はいまだに理解されていない。
既存の分析のほとんどは独立サンプルSEG(I-SEG)に焦点を当て、領域がコンパクトであるか確率作用素の分散が一様有界であることを仮定する。
同サンプルSEG(S-SEG)の挙動は、物質的に異なる性質を持つ天然変種である。
本研究は,文学におけるこれらのギャップに対処するものである。
平均リプシッツ性(英語版)と有界分散(英語版)のみはコンパクト集合上でも収束を保証しない。
そして、おそらく非有界な領域に対して、緩和された仮定の集合の下で各SEG不変量に対して高い確率的制限ギャップ収束を確立し、これらの結果に対するある種の根本的な改善が一般に不可能であることを示す。
最後に、I-SEGの終点収束をほぼ確実に保証する既知の非対称な二重ステップサイズ選択がS-SEGに対して失敗することを示し、S-SEGが修正されたステップサイズの下でもほぼ確実に発散する確率的単調VIPが存在する。
関連論文リスト
- 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) - Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。
我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。
全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - 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) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - Stochastic Extragradient: General Analysis and Improved Rates [23.29653334470774]
Extragradient (SEG) 法は、min-max最適化と変分不等式問題を解くための最も一般的なアルゴリズムの1つである。
我々は,SEGのいくつかの変種を統一的に解析できる新しい理論フレームワークを開発した。
新たなSEG変種に対する我々のレートは、現在の最先端収束保証よりも優れており、制約の少ない仮定に依存している。
論文 参考訳（メタデータ） (2021-11-16T16:49:31Z) - Sharp Bounds for Federated Averaging (Local SGD) and Continuous
Perspective [49.17352150219212]
Federated AveragingFedAvg(ローカルSGD)は、Federated Learning(FL)で最も人気のあるアルゴリズムの1つである。
微分方程式(SDE)の観点から、この量を解析する方法を示す。
論文 参考訳（メタデータ） (2021-11-05T22:16:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。