論文の概要: Solving Stochastic Variational Inequalities without the Bounded Variance Assumption

• arxiv url: http://arxiv.org/abs/2602.05531v1
• Date: Thu, 05 Feb 2026 10:44:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:08.8895
• Title: Solving Stochastic Variational Inequalities without the Bounded Variance Assumption
• Title（参考訳）: 境界変数推定を伴わない確率的変分不等式の解法
• Authors: Ahmet Alacaoglu, Jun-Hyun Kim,
• Abstract要約: 我々は、有界分散や有界領域仮定なしで変動不等式(VI)を解くアルゴリズムを解析する。 我々の設定では、これはオラクル領域の双分極問題に対してさえ満たされないような、有界な複雑性の仮定で得られていた。
• 参考スコア（独自算出の注目度）: 8.350639529216876
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze algorithms for solving stochastic variational inequalities (VI) without the bounded variance or bounded domain assumptions, where our main focus is min-max optimization with possibly unbounded constraint sets. We focus on two classes of problems: monotone VIs; and structured nonmonotone VIs that admit a solution to the weak Minty VI. The latter assumption allows us to solve structured nonconvex-nonconcave min-max problems. For both classes of VIs, to make the expected residual norm less than $\varepsilon$, we show an oracle complexity of $\widetilde{O}(\varepsilon^{-4})$, which is the best-known for constrained VIs. In our setting, this complexity had been obtained with the bounded variance assumption in the literature, which is not even satisfied for bilinear min-max problems with an unbounded domain. We obtain this complexity for stochastic oracles whose variance can grow as fast as the squared norm of the optimization variable.
• Abstract（参考訳）: 確率的変分不等式(VI)を、有界な分散や有界な領域仮定なしで解くアルゴリズムを解析する。 我々は、モノトーン VI と、弱いミンティ VI の解を持つ非モノトーン VI の2つのクラスに焦点を当てる。 後者の仮定により、構造化された非凸非凸 min-max 問題を解くことができる。 VI の両クラスに対して、期待される残留ノルムを$\varepsilon$ より小さくするために、制限された VI で最もよく知られた $\widetilde{O}(\varepsilon^{-4})$ のオラクル複雑性を示す。 我々の設定では、この複雑性は文献における有界分散仮定(bounded variance assumption)によって得られており、これは非有界領域の双線型 min-max 問題に対してさえ満足していない。 偏差が最適化変数の2乗ノルムと同じ速さで大きくなる確率的オラクルに対して、この複雑さを得る。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Towards Weaker Variance Assumptions for Stochastic Optimization [19.339358874690568]
  次数次法の2乗ノルムを最適化変数の2乗ノルムの2乗ノルムと同程度の速さで成長させることができるような勾配アルゴリズムを解析するための古典的な仮定を再検討する。 関数的制約や正規化された凸凹 min-max 問題を用いて凸問題を解析する。 実現可能な集合の有界性を必要としない最適度測度に対するレートを得る。
  論文  参考訳（メタデータ） (2025-04-14T07:26:34Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  変分不等式(SVIs)の解決は、最適化の中心にある基礎的な問題である。 ほとんどの研究は、その難易度を損なう特定のサブクラスを彫刻することに重点を置いている。
  論文  参考訳（メタデータ） (2025-04-04T13:24:41Z)
• Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements [19.524063429548278]
  Extragradient (SEG) と Gradient Descent Ascent (SGDA) は min-max 最適化と変分不等式問題に対する優越アルゴリズムである。 これらのアルゴリズムに固有の本質的な構造を定量化し定量化するための我々の取り組み。 定数のステップサイズSEG/SGDAを時間同質マルコフ連鎖として再キャストすることにより、大数の第一種法則と中心極限定理を確立する。
  論文  参考訳（メタデータ） (2023-06-28T18:50:07Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• 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)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities [14.848525762485872]
  非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。 これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
  論文  参考訳（メタデータ） (2020-02-20T17:12:49Z)

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

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