論文の概要: A Primal-dual Approach for Solving Variational Inequalities with
General-form Constraints
- arxiv url: http://arxiv.org/abs/2210.15659v3
- Date: Wed, 29 Mar 2023 08:54:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-30 18:35:31.876749
- Title: A Primal-dual Approach for Solving Variational Inequalities with
General-form Constraints
- Title(参考訳): 一般形式制約付き変分不等式解法に対する原始双対的アプローチ
- Authors: Tatjana Chavdarova, Matteo Pagliardini, Tong Yang, Michael I. Jordan
- Abstract要約: Yang et al. (2023) は最近、一階法により等式と不等式制約で変分不等式 (VIs) を解くというオープンな問題に対処した。
本稿では,各イテレーションで約1つのサブプロブレムを解くウォームスタート手法を採用する。
我々はこの収束を証明し、演算子が$L$-Lipschitz および monotone であるとき、この不正確な-ACVI 法の最後の繰り返しのギャップ関数が $mathcalO(frac1sqrtK)$ で減少することを示す。
- 参考スコア(独自算出の注目度): 81.32297040574083
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Yang et al. (2023) recently addressed the open problem of solving Variational
Inequalities (VIs) with equality and inequality constraints through a
first-order gradient method. However, the proposed primal-dual method called
ACVI is applicable when we can compute analytic solutions of its subproblems;
thus, the general case remains an open problem. In this paper, we adopt a
warm-starting technique where we solve the subproblems approximately at each
iteration and initialize the variables with the approximate solution found at
the previous iteration. We prove its convergence and show that the gap function
of the last iterate of this inexact-ACVI method decreases at a rate of
$\mathcal{O}(\frac{1}{\sqrt{K}})$ when the operator is $L$-Lipschitz and
monotone, provided that the errors decrease at appropriate rates.
Interestingly, we show that often in numerical experiments, this technique
converges faster than its exact counterpart. Furthermore, for the cases when
the inequality constraints are simple, we propose a variant of ACVI named
P-ACVI and prove its convergence for the same setting. We further demonstrate
the efficacy of the proposed methods through numerous experiments. We also
relax the assumptions in Yang et al., yielding, to our knowledge, the first
convergence result that does not rely on the assumption that the operator is
$L$-Lipschitz. Our source code is provided at
$\texttt{https://github.com/mpagli/Revisiting-ACVI}$.
- Abstract(参考訳): Yang et al. (2023) は最近、一階勾配法により等式と不等式制約を持つ変分不等式 (VIs) を解くという開問題に対処した。
しかし、acviと呼ばれる原始双対法が適用できるのは、その部分問題の解析解を計算できる場合であり、一般のケースは未解決のままである。
そこで本論文では,各イテレーションで各サブ問題を解き,前回のイテレーションで得られた近似解を用いて変数を初期化するウォームスタート手法を採用する。
その収束を証明し、このイレクト-アビ法の最後のイテレートのギャップ関数が、演算子が$l$-lipschitz かつ monotone であるときに $\mathcal{o}(\frac{1}{\sqrt{k}})$ の割合で減少することを示した。
興味深いことに、数値実験では、この手法は正確な手法よりも早く収束することが多い。
さらに、不等式制約が単純である場合には、P-ACVIと呼ばれるACVIの変種を提案し、その収束性を同じ条件で証明する。
さらに,提案手法の有効性を多数の実験により実証する。
また、yang 等における仮定を緩和し、我々の知識により、演算子が $l$-lipschitz であるという仮定に依存しない最初の収束結果を与える。
ソースコードは$\texttt{https://github.com/mpagli/Revisiting-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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。