論文の概要: First-order methods for Stochastic Variational Inequality problems with
Function Constraints
- arxiv url: http://arxiv.org/abs/2304.04778v2
- Date: Fri, 21 Apr 2023 18:21:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-25 20:22:14.648437
- 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})を提案する。
さらに、これらのアルゴリズムは、結合された関数制約で容易にサドル点問題に拡張できることを示し、上記の場合と同様の複雑性結果が得られることを示す。
我々の知る限りでは、これらの複雑さの多くは初めて文献で得られている。
関連論文リスト
- Global and Preference-based Optimization with Mixed Variables using
Piecewise Affine Surrogates [1.30536490219656]
本稿では,線形制約付き混合変数問題の解法として,新しいサロゲートに基づく大域的最適化アルゴリズムを提案する。
本稿では,2種類の探索関数を導入し,混合整数線形計画解法を用いて実現可能な領域を効率的に探索する。
提案アルゴリズムは,既存の手法よりもよく,あるいは同等の結果が得られることが多い。
論文 参考訳(メタデータ) (2023-02-09T15:04:35Z) - Oracle Complexity of Single-Loop Switching Subgradient Methods for
Non-Smooth Weakly Convex Functional Constrained Optimization [12.84152722535866]
目的関数が弱凸あるいは弱凸である非制約最適化問題を考える。
そこで本研究では,一階調律であり,実装が容易な段階的手法について考察する。
論文 参考訳(メタデータ) (2023-01-30T22:13:14Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - 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 Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization [27.07082875330508]
制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。
このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。
本稿では,新しい不等式制約問題アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-07-12T16:30:34Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-05T18:28:42Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳(メタデータ) (2020-07-07T21:26:35Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳(メタデータ) (2020-06-27T03:05:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。