論文の概要: Primal Methods for Variational Inequality Problems with Functional Constraints

• arxiv url: http://arxiv.org/abs/2403.12859v1
• Date: Tue, 19 Mar 2024 16:03:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-20 13:34:19.966739
• Title: Primal Methods for Variational Inequality Problems with Functional Constraints
• Title（参考訳）: 関数制約付き変分不等式問題の最適解法
• Authors: Liang Zhang, Niao He, Michael Muehlebach,
• Abstract要約: 本稿では,関数的制約付き変分不等式問題に対処する手法として,制約付き勾配法(Constrained Gradient Method, CGM)を提案する。 滑らかな制約下での単調作用素による変分不等式問題に対するアルゴリズムの非漸近収束解析を確立する。 提案アルゴリズムは, 単調・強単調両方の演算子問合せにおいて, プロジェクションに基づく手法の複雑さに適合する。
• 参考スコア（独自算出の注目度）: 25.261426717550293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constrained variational inequality problems are recognized for their broad applications across various fields including machine learning and operations research. First-order methods have emerged as the standard approach for solving these problems due to their simplicity and scalability. However, they typically rely on projection or linear minimization oracles to navigate the feasible set, which becomes computationally expensive in practical scenarios featuring multiple functional constraints. Existing efforts to tackle such functional constrained variational inequality problems have centered on primal-dual algorithms grounded in the Lagrangian function. These algorithms along with their theoretical analysis often require the existence and prior knowledge of the optimal Lagrange multipliers. In this work, we propose a simple primal method, termed Constrained Gradient Method (CGM), for addressing functional constrained variational inequality problems, without necessitating any information on the optimal Lagrange multipliers. We establish a non-asymptotic convergence analysis of the algorithm for variational inequality problems with monotone operators under smooth constraints. Remarkably, our algorithms match the complexity of projection-based methods in terms of operator queries for both monotone and strongly monotone settings, while utilizing significantly cheaper oracles based on quadratic programming. Furthermore, we provide several numerical examples to evaluate the efficacy of our algorithms.
• Abstract（参考訳）: 制約付き変分不等式問題は、機械学習や運用研究を含む様々な分野の幅広い応用において認識されている。 その単純さとスケーラビリティのために、これらの問題を解決するための標準手法として、一階法が登場した。 しかし、それらは一般的に、実現可能な集合をナビゲートするために射影や線形最小化のオラクルに依存しており、複数の機能的制約を含む現実的なシナリオでは計算コストがかかる。 このような機能的制約付き変分不等式問題に対処する既存の取り組みは、ラグランジュ関数を基底とした原始双対アルゴリズムに重点を置いている。 これらのアルゴリズムと理論解析は、しばしば最適ラグランジュ乗数の存在と事前知識を必要とする。 本研究では,最適ラグランジュ乗算器に関する情報を必要とせず,関数的制約付き変分不等式問題に対処する,制約付き勾配法(Constrained Gradient Method, CGM)を提案する。 滑らかな制約下での単調作用素による変分不等式問題に対するアルゴリズムの非漸近収束解析を確立する。 顕著なことに,本アルゴリズムは単調および強単調の両方の演算子クエリにおいて,プロジェクションに基づく手法の複雑さにマッチする。 さらに,アルゴリズムの有効性を評価するために,いくつかの数値的な例を提示した。

関連論文リスト

• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [8.59102802625914]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合、分散と還元のアルゴリズムも検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities [137.6408511310322]
  有限サムコヒーレンシブ変分不等式の問題を考える。 強い単調な問題に対しては、この方法を用いて解への線形収束を達成することができる。
  論文  参考訳（メタデータ） (2022-10-12T08:04:48Z)
• A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization [27.07082875330508]
  制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。 このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。 本稿では,新しい不等式制約問題アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-12T16:30:34Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization [13.170519806372075]
  2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。 最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。 提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
  論文  参考訳（メタデータ） (2021-07-14T08:01:30Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)

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

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