論文の概要: 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のサブ問題がほぼ解決された場合, 標準ウォームスタート手法を用いることで, 誤差が適切な速度で減少するならば, 収束率が同じであることを示す。 我々はさらに,後者の実装に関する経験的分析と洞察を提供する。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。