論文の概要: A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition

• arxiv url: http://arxiv.org/abs/2504.03432v1
• Date: Fri, 04 Apr 2025 13:24:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-07 14:46:59.576228
• Title: A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
• Title（参考訳）: 分母条件下での変分不等式に対する多項式時間アルゴリズム
• Authors: Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm, Brian Hu Zhang,
• Abstract要約: 解法 (Stampacchia) 変分不等式 (SVIs) は最適化の中心にある基礎的な問題である。 楕円体の中心から勾配降下ステップを踏み出した後に超平面が得られる楕円体アルゴリズムの新たな変種を導入する。 主な成果のいくつかの拡張と新しい応用を提供しています。
• 参考スコア（独自算出の注目度）: 79.18735797001183
• License:
• Abstract: Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization, with a host of critical applications ranging from engineering to economics. However, this expressivity comes at the cost of computational hardness. As a result, most research has focused on carving out specific subclasses that elude those intractability barriers. A classical property that goes back to the 1960s is the Minty condition, which postulates that the Minty VI (MVI) problem -- the weak dual of the SVI problem -- admits a solution. In this paper, we establish the first polynomial-time algorithm -- that is, with complexity growing polynomially in the dimension $d$ and $\log(1/\epsilon)$ -- for solving $\epsilon$-SVIs for Lipschitz continuous mappings under the Minty condition. Prior approaches either incurred an exponentially worse dependence on $1/\epsilon$ (and other natural parameters of the problem) or made overly restrictive assumptions -- such as strong monotonicity. To do so, we introduce a new variant of the ellipsoid algorithm wherein separating hyperplanes are obtained after taking a gradient descent step from the center of the ellipsoid. It succeeds even though the set of SVIs can be nonconvex and not fully dimensional. Moreover, when our algorithm is applied to an instance with no MVI solution and fails to identify an SVI solution, it produces a succinct certificate of MVI infeasibility. We also show that deciding whether the Minty condition holds is $\mathsf{coNP}$-complete. We provide several extensions and new applications of our main results. Specifically, we obtain the first polynomial-time algorithms for i) solving monotone VIs, ii) globally minimizing a (potentially nonsmooth) quasar-convex function, and iii) computing Nash equilibria in multi-player harmonic games.
• Abstract（参考訳）: 解法 (Stampacchia) 変分不等式 (SVIs) は最適化の中心にある基礎的な問題であり、工学から経済学まで多くの重要な応用がある。 しかし、この表現性は計算硬度を犠牲にしている。 その結果、ほとんどの研究は、その難易度を損なう特定のサブクラスを彫刻することに焦点を当てている。 1960年代までさかのぼる古典的な性質は、ミンティ条件(Minty condition)であり、ミンティVI(MVI)問題は、SVI問題の弱双対である。 本稿では、Minty条件下でのリプシッツ連続写像に対する$\epsilon$-SVIsを解くために、最初の多項式時間アルゴリズム、すなわち、次元$d$と$\log(1/\epsilon)$で多項式的に増大する複雑性を持つアルゴリズムを確立する。 以前のアプローチでは、1/\epsilon$(およびこの問題の他の自然なパラメータ)への指数的に悪い依存が生じるか、強い単調性のような過度に制限的な仮定がなされた。 そこで本研究では,楕円体の中心から勾配降下ステップを踏み出した後に超平面を分離する楕円体アルゴリズムを新たに導入する。 SVI の集合は非凸であり、完全次元ではないとしても成功する。 さらに,本アルゴリズムが MVI 解を持たないインスタンスに適用され,SVI 解の特定に失敗すると,MVI の不実現性の簡潔な証明が生成される。 また、Minty条件が成立するかどうかを決定することは$\mathsf{coNP}$-completeであることを示す。 主な成果のいくつかの拡張と新しい応用を提供しています。 具体的には、最初の多項式時間アルゴリズムを得る。 一 単調な六を解くこと。 二 擬似凸関数(潜在的に非滑らかな)を世界規模で最小化すること、及び 三 マルチプレイヤーハーモニックゲームにおけるナッシュ均衡の計算

関連論文リスト

• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。 解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
  論文  参考訳（メタデータ） (2024-02-07T18:22:41Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints [4.70696854954921]
  非近位ミニマックス問題は近年、機械学習、信号処理など多くの分野に注目が集まっている。 そこで本稿では,非平滑な非畳み込みミニマックス問題の解法としてDAPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-12-09T05:32:30Z)
• Solving Constrained Variational Inequalities via an Interior Point Method [88.39091990656107]
  制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。 本稿では,2種類の問題においてACVIの収束保証を提供する。 この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
  論文  参考訳（メタデータ） (2022-06-21T17:55:13Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
  提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。 提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
  論文  参考訳（メタデータ） (2020-06-03T04:00:52Z)

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

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