論文の概要: Revisiting the ACVI Method for Constrained Variational Inequalities
- arxiv url: http://arxiv.org/abs/2210.15659v1
- Date: Thu, 27 Oct 2022 17:59:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-28 13:09:52.596976
- Title: Revisiting the ACVI Method for Constrained Variational Inequalities
- Title(参考訳): 制約付き変分不等式に対するACVI法の再検討
- Authors: Tatjana Chavdarova, Matteo Pagliardini, Tong Yang, Michael I. Jordan
- Abstract要約: ACVIは、変動不等式(VIs)を一般制約で解くための、最近提案された一階法である。
演算子が単調であると仮定すれば、同じ保証が成り立つことを示す。
これは、一般的なモノトン VI に対する分析的に導出された最後の点収束速度である。
- 参考スコア(独自算出の注目度): 81.32297040574083
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: ACVI is a recently proposed first-order method for solving variational
inequalities (VIs) with general constraints. Yang et al. (2022) showed that the
gap function of the last iterate decreases at a rate of
$\mathcal{O}(\frac{1}{\sqrt{K}})$ when the operator is $L$-Lipschitz, monotone,
and at least one constraint is active.
In this work, we show that the same guarantee holds when only assuming that
the operator is monotone.
To our knowledge, this is the first analytically derived last-iterate
convergence rate for general monotone VIs, and overall the only one that does
not rely on the assumption that the operator is $L$-Lipschitz.
Furthermore, when the sub-problems of ACVI are solved approximately, we show
that by using a standard warm-start technique the convergence rate stays the
same, provided that the errors decrease at appropriate rates.
We further provide empirical analyses and insights on its implementation for
the latter case.
- Abstract(参考訳): ACVIは変分不等式(VIs)を一般制約で解くための一階法である。
yang et al. (2022) は、演算子が$l$-lipschitz, monotoneであり、少なくとも1つの制約がアクティブであるとき、最後のイテレートのギャップ関数は$\mathcal{o}(\frac{1}{\sqrt{k}})$の割合で減少することを示した。
本研究では、演算子が単調である場合に限り、同じ保証が成り立つことを示す。
我々の知る限り、これは一般単調 VI に対する解析的に導出された最後の点収束率であり、全体として作用素が$L$-Lipschitzであるという仮定に依存しない。
さらに, acviのサブ問題がほぼ解決された場合, 標準ウォームスタート手法を用いることで, 誤差が適切な速度で減少するならば, 収束率が同じであることを示す。
我々はさらに,後者の実装に関する経験的分析と洞察を提供する。
関連論文リスト
- Invex Programs: First Order Algorithms and Their Convergence [66.40124280146863]
Invexプログラムは、固定点ごとに世界最小値が得られる特別な非制約問題である。
そこで我々は,超凸問題における一般収束率を解くために,新しい一階法アルゴリズムを提案する。
提案アルゴリズムは,制約付き凸プログラムを解く最初のアルゴリズムである。
論文 参考訳(メタデータ) (2023-07-10T10:11:01Z) - Escaping limit cycles: Global convergence for constrained
nonconvex-nonconcave minimax problems [46.71914490521821]
本稿では,非コンケーブなミニマックス問題のクラスに対して,新たな漸進型アルゴリズムを提案する。
提案アルゴリズムは制約付き正規化問題に適用可能である。
論文 参考訳(メタデータ) (2023-02-20T08:37:08Z) - Minimax Instrumental Variable Regression and $L_2$ Convergence
Guarantees without Identification or Closedness [71.42652863687117]
インストゥルメンタル変数(IV)回帰の非パラメトリック推定について検討した。
固定IV解に収束できる新しいペナル化ミニマックス推定器を提案する。
ラックス条件下での推定値に対して強い$L$誤差率を導出する。
論文 参考訳(メタデータ) (2023-02-10T18:08:49Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Solving Constrained Variational Inequalities via an Interior Point
Method [88.39091990656107]
制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。
本稿では,2種類の問題においてACVIの収束保証を提供する。
この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
論文 参考訳(メタデータ) (2022-06-21T17:55:13Z) - Simple and optimal methods for stochastic variational inequalities, I:
operator extrapolation [9.359939442911127]
まず,決定論的変分不等式(VI)問題を解決するための演算子外挿法を提案する。
次に、演算子外挿法(SOE)を導入し、その最適収束挙動を異なる不等式 VI 問題を解くために確立する。
論文 参考訳(メタデータ) (2020-11-05T17:20:19Z) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳(メタデータ) (2020-05-12T16:44:27Z) - Inexact and Stochastic Generalized Conditional Gradient with Augmented
Lagrangian and Proximal Step [2.0196229393131726]
我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。
これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。
ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
論文 参考訳(メタデータ) (2020-05-11T14:52:16Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳(メタデータ) (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。