論文の概要: Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities

• arxiv url: http://arxiv.org/abs/2604.07662v2
• Date: Wed, 15 Apr 2026 03:25:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 13:09:57.333556
• Title: Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities
• Title（参考訳）: 単調変分不等式を解くためのパラメータフリー非エルゴディック外部分解アルゴリズム
• Authors: Lingqing Shen, Fatma Kılınç-Karzan,
• Abstract要約: 拘束単調なVIsに対する非漸近的最終定位保証を用いたパラメータフリーの指数分解法を開発した。 このフレームワークをバックトラックラインサーチによりローカルリプシッツ演算子に拡張し,パラメータ自由性を保ちながら同じレートを得る。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monotone variational inequalities (VIs) provide a unifying framework for convex minimization, equilibrium computation, and convex-concave saddle-point problems. Extragradient-type methods are among the most effective first-order algorithms for such problems, but their performance hinges critically on stepsize selection. While most existing theory focuses on ergodic averages of the iterates, practical performance is often driven by the significantly stronger behavior of the last iterate. Moreover, available last-iterate guarantees typically rely on fixed stepsizes chosen using problem-specific global smoothness information, which is often difficult to estimate accurately and may not even be applicable. In this paper, we develop parameter-free extragradient methods with non-asymptotic last-iterate guarantees for constrained monotone VIs. For globally Lipschitz operators, our algorithm achieves an $o(1/\sqrt{T})$ last-iterate rate. We then extend the framework to locally Lipschitz operators via backtracking line search and obtain the same rate while preserving parameter-freeness, thereby making parameter-free last-iterate methods applicable to important problem classes for which global smoothness is unrealistic. Our numerical experiments on bilinear matrix games, LASSO, minimax group fairness, and state-of-the-art maximum entropy sampling relaxations demonstrate wide applicability of our results as well as strong last-iterate performance and significant improvements over existing methods.
• Abstract（参考訳）: モノトン変量不等式 (VIs) は、凸最小化、平衡計算、凸凹サドル点問題に対する統一的な枠組みを提供する。 指数階数型法はそのような問題に対して最も効果的な一階数アルゴリズムの一つであるが、その性能は段数選択に決定的に左右される。 ほとんどの既存の理論は、反復のエルゴード平均に焦点を当てているが、実践的なパフォーマンスは、しばしば最後の反復の非常に強い振る舞いによって引き起こされる。 さらに、利用可能な最終項目保証は通常、問題固有のグローバルスムーズネス情報を用いて選択された固定ステップサイズに依存しており、正確に見積もるのは困難であり、適用できない場合もある。 本稿では,制約付きモノトーン VI に対する非漸近的最終定位保証を用いたパラメータフリーの漸進的手法を提案する。 グローバルなリプシッツ作用素に対して、我々のアルゴリズムは$o(1/\sqrt{T})$ last-iterate rateを達成する。 そこで,このフレームワークをバックトラックライン探索により局所リプシッツ作用素に拡張し,パラメータ自由度を保ちながら同じレートを得ることにより,大域的滑らかさが非現実的な重要な問題クラスに適用する。 両線形行列ゲーム, LASSO, ミニマックス群フェアネス, 最先端の最大エントロピーサンプリング緩和に関する数値実験により, 実験結果の広範な適用性, 性能, 既存手法に対する大幅な改善が示された。

関連論文リスト

• First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints [9.141425189503794]
  フェデレート学習に適した1次ソフトマックス重み付きスイッチング勾配法を提案する。 完全なクライアント参加の下で、我々のアルゴリズムは標準的な $mathcalO(-4)$ Oracle complexity を達成する。 我々は、統一されたエラー分解を提供し、シャープな$mathcalO(logfrac1)$高確率収束保証を確立する。
  論文  参考訳（メタデータ） (2026-03-06T00:14:46Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。 非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
  論文  参考訳（メタデータ） (2020-01-15T16:11:04Z)

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

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