論文の概要: Solving Constrained Variational Inequalities via an Interior Point Method

• arxiv url: http://arxiv.org/abs/2206.10575v1
• Date: Tue, 21 Jun 2022 17:55:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-22 15:16:40.049587
• Title: Solving Constrained Variational Inequalities via an Interior Point Method
• Title（参考訳）: 内点法による制約付き変分不等式解法
• Authors: Tong Yang, Michael I. Jordan, Tatjana Chavdarova
• Abstract要約: 制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。 本稿では,2種類の問題においてACVIの収束保証を提供する。 この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
• 参考スコア（独自算出の注目度）: 88.39091990656107
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop an interior-point approach to solve constrained variational inequality (cVI) problems. Inspired by the efficacy of the alternating direction method of multipliers (ADMM) method in the single-objective context, we generalize ADMM to derive a first-order method for cVIs, that we refer to as ADMM-based interior point method for constrained VIs (ACVI). We provide convergence guarantees for ACVI in two general classes of problems: (i) when the operator is $\xi$-monotone, and (ii) when it is monotone, the constraints are active and the game is not purely rotational. When the operator is in addition L-Lipschitz for the latter case, we match known lower bounds on rates for the gap function of $\mathcal{O}(1/\sqrt{K})$ and $\mathcal{O}(1/K)$ for the last and average iterate, respectively. To the best of our knowledge, this is the first presentation of a first-order interior-point method for the general cVI problem that has a global convergence guarantee. Moreover, unlike previous work in this setting, ACVI provides a means to solve cVIs when the constraints are nontrivial. Empirical analyses demonstrate clear advantages of ACVI over common first-order methods. In particular, (i) cyclical behavior is notably reduced as our methods approach the solution from the analytic center, and (ii) unlike projection-based methods that oscillate when near a constraint, ACVI efficiently handles the constraints.
• Abstract（参考訳）: 制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。 単目的文脈における乗算器の交互方向法(admm)の有効性に着想を得て,admm を一般化して cvis の一階法を導出し,制約付き vis (acvi) に対して admm ベースの内点法と呼ぶ。 acviの2つの一般的な問題クラスにおける収束保証を提供する。 (i)オペレータが$\xi$モノトーンである場合、及び (ii)単調の場合、制約はアクティブであり、ゲームは純粋に回転しない。 後者の場合、作用素が L-Lipschitz を加算する場合、それぞれが最後のイテレートと平均イテレートに対して $\mathcal{O}(1/\sqrt{K})$ と $\mathcal{O}(1/K)$ のギャップ関数のレートで既知の下界と一致する。 我々の知る限りでは、これは大域収束保証を持つ一般のcVI問題に対する一階内点法の最初のプレゼンテーションである。 さらに、この設定における以前の研究とは異なり、ACVI は制約が自明でない場合に cVI を解く手段を提供する。 経験的分析は、一般的な一階法よりもACVIの明確な利点を示している。 特に (i)分析中心から解に近づくと,循環的挙動が顕著に減少する。 (ii)制約付近で振動する投影法とは異なり、acviは制約を効率的に処理する。

関連論文リスト

• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
  信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。 理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
  論文  参考訳（メタデータ） (2022-07-30T13:05:01Z)
• 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)
• Converting ADMM to a Proximal Gradient for Convex Optimization Problems [4.56877715768796]
  融解ラッソや凸クラスタリングなどのスパース推定では、問題を解くために、近位勾配法またはマルチプライヤー(ADMM)の交互方向法のいずれかを適用します。 本論文では,制約と目的が強く凸であると仮定し,ADMM溶液を近位勾配法に変換する一般的な方法を提案する。 数値実験により, 効率の面で有意な改善が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-22T07:41:12Z)
• On the Convergence of Continuous Constrained Optimization for Structure Learning [30.279796192573805]
  本稿では, 線形, 非線形, 共起ケースにおける構造学習における拡張ラグランジアン法 (ALM) と二次ペナルティ法 (QPM) の収束性を示す。 さらに、軽度条件下で、DAG溶液へのQPMの収束保証を確立する。
  論文  参考訳（メタデータ） (2020-11-23T00:29:37Z)
• Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation [9.359939442911127]
  まず,決定論的変分不等式(VI)問題を解決するための演算子外挿法を提案する。 次に、演算子外挿法(SOE)を導入し、その最適収束挙動を異なる不等式 VI 問題を解くために確立する。
  論文  参考訳（メタデータ） (2020-11-05T17:20:19Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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