論文の概要: A Primal-Dual Approach to Solving Variational Inequalities with General Constraints
- arxiv url: http://arxiv.org/abs/2210.15659v4
- Date: Sat, 3 Aug 2024 17:54:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-07 20:01:27.675333
- Title: A Primal-Dual Approach to Solving Variational Inequalities with General Constraints
- Title（参考訳）: 一般制約による変分不等式の解法
- Authors: Tatjana Chavdarova, Tong Yang, Matteo Pagliardini, Michael I. Jordan,
- Abstract要約: Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
- 参考スコア（独自算出の注目度）: 54.62996442406718
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational inequalities (VIs) under a limiting assumption that analytic solutions of specific subproblems are available. In this paper, we circumvent this assumption via a warm-starting technique where we solve subproblems approximately and initialize variables with the approximate solution found at the previous iteration. We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of $O(\frac{1}{\sqrt{K}})$ when the operator is $L$-Lipschitz and monotone. In numerical experiments, we show that this technique can converge much faster than its exact counterpart. Furthermore, for the cases when the inequality constraints are simple, we introduce an alternative variant of ACVI and establish its convergence under the same conditions. Finally, we relax the smoothness assumptions in Yang et al., yielding, to our knowledge, the first convergence result for VIs with general constraints that does not rely on the assumption that the operator is $L$-Lipschitz.
- Abstract（参考訳）: Yang et al (2023) は最近、特定のサブプロブレムの分析解が利用できるという限定的な仮定の下で、一般変分不等式 (VIs) を解くために一階勾配法を使う方法を示した。
本稿では,この仮定をウォームスタート法により回避し,前回の繰り返しで見いだされた近似解を用いて変数を近似的に初期化する。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone であるとき、この方法の最後の繰り返しのギャップ関数が$O(\frac{1}{\sqrt{K}})$で減少することを示す。
数値実験では、この手法は正確な手法よりもはるかに高速に収束できることが示されている。
さらに、不等式制約が単純である場合には、ACVIの代替変種を導入し、同じ条件下で収束を確立する。
最後に、Yang et al における滑らかさの仮定を緩和し、つまり我々の知識に従えば、作用素が $L$-Lipschitz であるという仮定に依存しない一般の制約を持つ VI に対する最初の収束結果が得られる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。