論文の概要: How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond
- arxiv url: http://arxiv.org/abs/2609.08380v1
- Date: Tue, 08 Sep 2026 07:51:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.611623
- Title: How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond
- Title（参考訳）: 制約付き確率最小問題に対する勾配写像を小さくする方法
- Abstract要約: 勾配写像の観点で準最適度を測定した場合に焦点をあてる。
このギャップを橋渡しして、制約付き凸凹 min-max 問題に対する勾配写像の複雑さを改善する。
- 参考スコア（独自算出の注目度）: 9.865174381229927
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than $\varepsilon$ is $\widetilde{O}(\varepsilon^{-4})$, compared to the near-optimal $\widetilde{O}(\varepsilon^{-2})$ that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to $\widetilde{O}(\varepsilon^{-2})$. We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.
- Abstract（参考訳）: 本研究では,制約付きあるいは規則化された凸凹型min-max最適化と確率的単調変分不等式に対する確率的一階オラクル複雑性について検討した。
我々は、非制約問題に対する勾配ノルムを一般化する最適性の概念として、勾配写像(フォワードバック(英語版)あるいは自然残留(英語版)とも呼ばれる)で亜最適度が測定される場合に焦点を当てる。
この設定では、現在の標準偏差仮定による標準的な非バイアスのオラクルアクセスの下で、勾配写像のノルムを$\varepsilon$ is $\widetilde{O}(\varepsilon^{-4})$ より小さくする最もよく知られた複雑さは、非制約の場合において確立されるほぼ最適の $\widetilde{O}(\varepsilon^{-2})$ と比較する。
このギャップを埋めて、制約付き凸凹 min-max 問題に対する勾配写像の複雑性を$\widetilde{O}(\varepsilon^{-2})$に改善する。
次に、Blum-Gladyshev の仮定を用いて、有界分散のない問題に対して同じ複雑さを証明できるように拡張する。
関連論文リスト
- Solving Stochastic Variational Inequalities without the Bounded Variance Assumption [8.350639529216876]
我々は、有界分散や有界領域仮定なしで変動不等式(VI)を解くアルゴリズムを解析する。
我々の設定では、これはオラクル領域の双分極問題に対してさえ満たされないような、有界な複雑性の仮定で得られていた。
論文 参考訳（メタデータ） (2026-02-05T10:44:04Z) - Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
線形不等式制約を用いた非コンパクト最適化問題に対するスムーズな原始双対アルゴリズムを提案する。
我々のアルゴリズムは、各サンプルの1つの勾配に基づいて、シングルループの反復である。
既存の手法とは異なり、我々のアルゴリズムは自由なサブ、大きなサイズ、パラメータの増加であり、実現可能性を保証するためにデュアル変数更新を使用する。
論文 参考訳（メタデータ） (2025-04-10T09:59:43Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。
提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。
提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文 参考訳（メタデータ） (2021-03-29T18:53:57Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。