論文の概要: First-order methods for Stochastic Variational Inequality problems with Function Constraints

• arxiv url: http://arxiv.org/abs/2304.04778v1
• Date: Mon, 10 Apr 2023 17:07:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-12 17:24:48.855737
• Title: First-order methods for Stochastic Variational Inequality problems with Function Constraints
• Title（参考訳）: 関数制約付き確率変分不等式問題の一階法
• Authors: Digvijay Boob and Qi Deng
• Abstract要約: 変分不等式(VI)は機械学習において重要な問題である。 本稿では,機能制約VI(FCVI)問題に対する新しい一階法を提案する。
• 参考スコア（独自算出の注目度）: 5.830629896477968
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The monotone Variational Inequality (VI) is an important problem in machine learning. In numerous instances, the VI problems are accompanied by function constraints which can possibly be data-driven, making the projection operator challenging to compute. In this paper, we present novel first-order methods for function constrained VI (FCVI) problem under various settings, including smooth or nonsmooth problems with a stochastic operator and/or stochastic constraints. First, we introduce the~{\texttt{OpConEx}} method and its stochastic variants, which employ extrapolation of the operator and constraint evaluations to update the variables and the Lagrangian multipliers. These methods achieve optimal operator or sample complexities when the FCVI problem is either (i) deterministic nonsmooth, or (ii) stochastic, including smooth or nonsmooth stochastic constraints. Notably, our algorithms are simple single-loop procedures and do not require the knowledge of Lagrange multipliers to attain these complexities. Second, to obtain the optimal operator complexity for smooth deterministic problems, we present a novel single-loop Adaptive Lagrangian Extrapolation~(\texttt{AdLagEx}) method that can adaptively search for and explicitly bound the Lagrange multipliers. Furthermore, we show that all of our algorithms can be easily extended to saddle point problems with coupled function constraints, hence achieving similar complexity results for the aforementioned cases. To our best knowledge, many of these complexities are obtained for the first time in the literature.
• Abstract（参考訳）: モノトン変分不等式(VI)は機械学習において重要な問題である。 多数の例において、vi問題にはデータ駆動が可能な関数制約が伴うため、プロジェクション演算子の計算が難しくなる。 本稿では, 確率演算子を用いたスムーズあるいは非滑らかな問題や確率的制約を含む, 様々な条件下での関数制約VI(FCVI)問題に対する新しい一階法を提案する。 まず,演算子の補間と制約評価を用いて変数とラグランジアン乗算器を更新する-{\textt{opconex}} 法とその確率的変種を紹介する。 これらの手法はFCVI問題のいずれかが最適作用素あるいは標本複素量を達成する。 一 決定論的非流動性又は (ii)滑らかまたは非滑らかな確率的制約を含む確率的制約。 特に、我々のアルゴリズムは単純な単一ループ手続きであり、これらの複雑さを達成するためにラグランジュ乗算器の知識を必要としない。 第二に、スムーズな決定論的問題に対する最適演算子複雑性を得るために、ラグランジュ乗算器を適応的に探索し、明示的に有界にする新しい単一ループ適応ラグランジュ外挿法(\texttt{AdLagEx})を提案する。 さらに、これらのアルゴリズムは、結合された関数制約で容易にサドル点問題に拡張できることを示し、上記の場合と同様の複雑性結果が得られることを示す。 我々の知る限りでは、これらの複雑さの多くは初めて文献で得られている。

関連論文リスト

• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• 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)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。 また、単一または2つのミニバッチ誘導体でも機能する。
  論文  参考訳（メタデータ） (2020-06-27T03:05:18Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。 我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。 論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-12T16:44:27Z)

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

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