論文の概要: First-order methods for Stochastic Variational Inequality problems with Function Constraints
- arxiv url: http://arxiv.org/abs/2304.04778v3
- Date: Fri, 24 May 2024 17:31:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 00:25:27.564896
- Title: First-order methods for Stochastic Variational Inequality problems with Function Constraints
- Title（参考訳）: 関数制約付き確率的変分不等式問題の1次解法
- Authors: Digvijay Boob, Qi Deng, Mohammad Khalafi,
- Abstract要約: 本稿では,機能制約付き変分不等式(FCVI)問題に対して,スムーズあるいは非スムーズな設定で新しい一階法を提案する。
全てのアルゴリズムは、同じ複雑性を保ちながら、主変数と双変数を結合する関数制約を持つサドル点問題に容易に拡張できる。
- 参考スコア（独自算出の注目度）: 3.922842284927803
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The monotone Variational Inequality (VI) is a general model with important applications in various engineering and scientific domains. In numerous instances, the VI problems are accompanied by function constraints that can be data-driven, making the usual projection operator challenging to compute. This paper presents novel first-order methods for the function-constrained Variational Inequality (FCVI) problem in smooth or nonsmooth settings with possibly stochastic operators and constraints. We introduce the AdOpEx method, which employs an operator extrapolation on the KKT operator of the FCVI in a smooth deterministic setting. Since this operator is not uniformly Lipschitz continuous in the Lagrange multipliers, we employ an adaptive two-timescale algorithm leading to bounded multipliers and achieving the optimal $O(1/T)$ convergence rate. For the nonsmooth and stochastic VIs, we introduce design changes to the AdOpEx method and propose a novel P-OpEx method that takes partial extrapolation. It converges at the rate of $O(1/\sqrt{T})$ when both the operator and constraints are stochastic or nonsmooth. This method has suboptimal dependence on the noise and Lipschitz constants of function constraints. We propose a constraint extrapolation approach leading to the OpConEx method that improves this dependence by an order of magnitude. All our algorithms easily extend to saddle point problems with function constraints that couple the primal and dual variables while maintaining the same complexity results. To the best of our knowledge, all our complexity results are new in the literature
- Abstract（参考訳）: モノトン変分不等式(モノトン変分不等式、英: monotone variational Inequality、VI)は、様々な工学および科学分野において重要な応用を持つ一般モデルである。
多くの場合、VI問題はデータ駆動の関数制約を伴うため、通常の射影演算子では計算が難しい。
本稿では,関数制約付き変分不等式(FCVI)問題に対して,確率演算子や制約のある滑らかあるいは非滑らかな設定で新しい一階法を提案する。
本稿では,FCVIのKKT演算子をスムーズな決定論的設定で外挿するAdOpEx法を提案する。
この演算子はラグランジュ乗算器において一様リプシッツ連続ではないので、有界乗算器に導かれる適応2時間スケールのアルゴリズムを用い、最適な$O(1/T)$収束率を達成する。
非滑らかで確率的な VI に対して,AdOpEx 法の設計変更を導入し,部分補間を行う新しい P-OpEx 法を提案する。
O(1/\sqrt{T})$ の速度で収束する(演算子と制約の両方が確率的あるいは非滑らかである)。
この方法は関数制約の雑音とリプシッツ定数に準最適依存を持つ。
本稿では,OpConEx法に導かれる制約外挿法を提案し,その依存性を桁違いに改善する。
すべてのアルゴリズムは, 基本変数と双対変数を結合する関数制約を持つサドル点問題に容易に拡張でき, 同じ複雑性結果を維持することができる。
私たちの知識を最大限に活用するために、複雑性の結果はすべて文献で新しくなっています。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。