論文の概要: Tight Last-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities

• arxiv url: http://arxiv.org/abs/2204.09228v1
• Date: Wed, 20 Apr 2022 05:12:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-21 15:39:20.583134
• Title: Tight Last-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities
• Title（参考訳）: 制約付き単調変分不等式に対する超勾配法のタイトなラストイテレート収束
• Authors: Yang Cai, Argyris Oikonomou, Weiqiang Zheng
• Abstract要約: 制約付きモノトンおよびリプシッツの変分不等式について, 過次法の最終点収束率を示す。 我々は,2乗法プログラミングのパワーと,指数関数法更新規則の低次元性を組み合わせた新しい手法を開発した。
• 参考スコア（独自算出の注目度）: 4.6193503399184275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The monotone variational inequality is a central problem in mathematical programming that unifies and generalizes many important settings such as smooth convex optimization, two-player zero-sum games, convex-concave saddle point problems, etc. The extragradient method by Korpelevich [1976] is one of the most popular methods for solving monotone variational inequalities. Despite its long history and intensive attention from the optimization and machine learning community, the following major problem remains open. What is the last-iterate convergence rate of the extragradient method for monotone and Lipschitz variational inequalities with constraints? We resolve this open problem by showing a tight $O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergence rate for arbitrary convex feasible sets, which matches the lower bound by Golowich et al. [2020]. Our rate is measured in terms of the standard gap function. The technical core of our result is the monotonicity of a new performance measure -- the tangent residual, which can be viewed as an adaptation of the norm of the operator that takes the local constraints into account. To establish the monotonicity, we develop a new approach that combines the power of the sum-of-squares programming with the low dimensionality of the update rule of the extragradient method. We believe our approach has many additional applications in the analysis of iterative methods.
• Abstract（参考訳）: 単調変分不等式は、滑らかな凸最適化、2プレイヤーゼロサムゲーム、凸凹サドル点問題など、多くの重要な設定を統一し一般化する数学的プログラミングにおける中心的な問題である。 コルペレヴィチ [1976] による過次法は、単調変分不等式を解く最も一般的な方法の1つである。 その長い歴史と最適化と機械学習コミュニティからの注目にもかかわらず、次の大きな問題は未解決のままである。 制約付きモノトンとリプシッツの変分不等式に対する過次法の最後の点収束速度は? 我々は、任意の凸可能集合に対する厳密な$O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergence rate を示すことで、この開問題を解決している。 [2020]. 我々の速度は標準ギャップ関数によって測定される。 この結果の技術的核心は、新しいパフォーマンス尺度である接残差のモノトニック性であり、これは局所的な制約を考慮に入れた演算子の規範の適応と見なすことができる。 単調性を確立するために,超次法の更新規則の低次元性と2乗計画の総和のパワーを組み合わせた新しい手法を開発した。 提案手法は反復的手法の解析に多くの応用があると考えている。

関連論文リスト

• The inexact power augmented Lagrangian method for constrained nonconvex optimization [44.516958213972885]
  この研究は、強大な拡張ラグランジアン用語を導入し、拡大項はユークリッドのノルムを権力へと引き上げる。 その結果, 長期化に低消費電力を用いると, 残余の減少が遅くなるにもかかわらず, より高速な成長が期待できることがわかった。 以上の結果より, 持続時間の短縮には低消費電力が有効であるが, 残留率が低下する傾向が示唆された。
  論文  参考訳（メタデータ） (2024-10-26T11:31:56Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  演算子を期待値とする単調な包摂問題を考える。 分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。 本稿では,不確実性に対処する手法を提案する。
  論文  参考訳（メタデータ） (2020-08-26T02:33:27Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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