論文の概要: Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone
Variational Inequalities and Connections With Cocoercivity
- arxiv url: http://arxiv.org/abs/2110.04261v1
- Date: Fri, 8 Oct 2021 17:16:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-11 16:55:19.714542
- Title: Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone
Variational Inequalities and Connections With Cocoercivity
- Title（参考訳）: 過次法:$O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequality and Connections with Cocoercivity
- Authors: Eduard Gorbunov, Nicolas Loizou, Gauthier Gidel
- Abstract要約: Extragradient Method (EG) Korpelevichは、サドル点と変分不等式問題を解く最も一般的な方法の1つである。
最適化コミュニティにおける長い歴史と重要な関心にもかかわらず、EGの収束に関する重要なオープンな疑問が残っている。
- 参考スコア（独自算出の注目度）: 21.22292220954549
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Extragradient method (EG) Korpelevich [1976] is one of the most popular
methods for solving saddle point and variational inequalities problems (VIP).
Despite its long history and significant attention in the optimization
community, there remain important open questions about convergence of EG. In
this paper, we resolve one of such questions and derive the first last-iterate
$O(1/K)$ convergence rate for EG for monotone and Lipschitz VIP without any
additional assumptions on the operator. The rate is given in terms of reducing
the squared norm of the operator. Moreover, we establish several results on the
(non-)cocoercivity of the update operators of EG, Optimistic Gradient Method,
and Hamiltonian Gradient Method, when the original operator is monotone and
Lipschitz.
- Abstract（参考訳）: extragradient method (eg) korpelevich [1976] はsaddle point and variational inequalities problem (vip) を解く最も一般的な方法の一つである。
最適化コミュニティにおける長い歴史と重要な関心にもかかわらず、EGの収束に関する重要なオープンな疑問が残っている。
本稿では,そのような問題の1つを解き,操作者に対する追加の仮定なしに,モノトーンとリプシッツ vip に対する eg に対する最初のラスト文字 $o(1/k)$ 収束率を導出する。
レートは作用素の平方ノルムを減少させるという点で与えられる。
さらに、元の演算子が単調かつリプシッツであるとき、EG,Optimistic Gradient Method, Hamiltonian Gradient Methodの更新演算子の(非)コヒーレンシ性に関するいくつかの結果を確立する。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - First-order methods for Stochastic Variational Inequality problems with Function Constraints [3.922842284927803]
本稿では,機能制約付き変分不等式(FCVI)問題に対して,スムーズあるいは非スムーズな設定で新しい一階法を提案する。
全てのアルゴリズムは、同じ複雑性を保ちながら、主変数と双変数を結合する関数制約を持つサドル点問題に容易に拡張できる。
論文 参考訳（メタデータ） (2023-04-10T17:07:55Z) - Extragradient-Type Methods with $\mathcal{O} (1/k)$ Last-Iterate
Convergence Rates for Co-Hypomonotone Inclusions [8.0153031008486]
我々は、コヒポモノトン包摂の解を近似するために、よく知られた過次法(英語版)の2つの「ネステロフ加速」変種を開発した。
我々の結果は、ルートフィリング問題に対する最近のハルパーン型手法の代替と見なすことができる。
論文 参考訳（メタデータ） (2023-02-08T14:47:34Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - 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) - Solving Constrained Variational Inequalities via an Interior Point
Method [88.39091990656107]
制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。
本稿では,2種類の問題においてACVIの収束保証を提供する。
この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
論文 参考訳（メタデータ） (2022-06-21T17:55:13Z) - Tight Last-Iterate Convergence of the Extragradient Method for
Constrained Monotone Variational Inequalities [4.6193503399184275]
制約付きモノトンおよびリプシッツの変分不等式について, 過次法の最終点収束率を示す。
我々は,2乗法プログラミングのパワーと,指数関数法更新規則の低次元性を組み合わせた新しい手法を開発した。
論文 参考訳（メタデータ） (2022-04-20T05:12:11Z) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-12T16:44:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。