論文の概要: 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}$で提供されている。
関連論文リスト
- The inexact power augmented Lagrangian method for constrained nonconvex optimization [44.516958213972885]
この研究は、強大な拡張ラグランジアン用語を導入し、拡大項はユークリッドのノルムを権力へと引き上げる。
その結果, 長期化に低消費電力を用いると, 残余の減少が遅くなるにもかかわらず, より高速な成長が期待できることがわかった。
以上の結果より, 持続時間の短縮には低消費電力が有効であるが, 残留率が低下する傾向が示唆された。
論文 参考訳（メタデータ） (2024-10-26T11:31:56Z) - Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization [0.0]
我々は、強く凸するが、潜在的に非滑らかな非Lipschitz最適化のための段階的手法を考える。
本稿では,古典的下位段階法,近位下位段階法,スイッチング下位段階法に対する等価な2値記述について述べる。
論文 参考訳（メタデータ） (2023-05-27T01:56:09Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - 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) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - Simple and optimal methods for stochastic variational inequalities, I:
operator extrapolation [9.359939442911127]
まず,決定論的変分不等式(VI)問題を解決するための演算子外挿法を提案する。
次に、演算子外挿法(SOE)を導入し、その最適収束挙動を異なる不等式 VI 問題を解くために確立する。
論文 参考訳（メタデータ） (2020-11-05T17:20:19Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
我々はReLU回帰の根本的な問題を考察する。
目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
論文 参考訳（メタデータ） (2020-05-26T16:26:17Z) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-12T16:44:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。