論文の概要: Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2610.01662v1
• Date: Thu, 01 Oct 2026 13:24:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.147934
• Title: Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
• Title（参考訳）: 非凸最小値最適化におけるばらつき低減を伴う確率的一階アルゴリズムの下位境界
• Abstract要約: 非畳み込みミニマックス最適化における一階アルゴリズムの下位境界を確立する。 私たちの貢献は、分散還元を許容するゼロ境界クラスに対する下界である。 これらの結果は、凹凸と凹凸構造をまたいだ複雑さの障壁を同定する。
• 参考スコア（独自算出の注目度）: 2.834413535942792
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an $L$-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most $D_Y$, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most $Δ$. The target accuracy $\varepsilon$ is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter $1/(2L)$. Under an unbiased stochastic first-order oracle with variance at most $σ^2$ and mean-square smoothness, we prove the lower bound $Ω\!\left(L^2D_YΔ\varepsilon^{-3}+L^3D_Y^2Δσ^2\varepsilon^{-6}\right)$. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter $μ>0$ and condition number $κ:=L/μ$, we obtain $Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+LΔκσ^2\varepsilon^{-4}\right)$ under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant $\bar L$, we obtain $Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+Δ\bar Lσκ^{3/2}\varepsilon^{-3}\right)$. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.
• Abstract（参考訳）: 我々は,非凸最小値最適化における確率的一階アルゴリズムの複雑性の低い境界を確立する。 我々の主な貢献は、既存の下界によって課されるアルゴリズム的制約を超えて、分散還元を許容するゼロ参照アルゴリズムクラスに対する下界である。 目的は、L$-Lipschitz連続関節勾配、ユークリッド半径のコンパクト凸二重領域の最大値D_Y$、および双対変数上の目的を最大化して定義される原始値関数であり、初期準最適値は最大$$$Δ$である。 目標精度$\varepsilon$は、パラメータ1/(2L)$の制約付き原始値関数のモローエンベロープの勾配ノルムによって測定される。 最大$σ^2$と平均二乗滑らかさのばらつきを持つ確率的一階オラクルの下では、下界の$Ω\! L^2D_YΔ\varepsilon^{-3}+L^3D_Y^2Δσ^2\varepsilon^{-6}\right)$。 この結果は、分散還元が許された場合でも、精度、二重領域半径、およびオラクルノイズへの依存性を定量化する。 また、非凸-強凸-極小最適化のための補的下界も確立する。 二重強共役パラメータ$μ>0$と条件番号$κ:=L/μ$で、$Ω\! LΔ\sqrtκ\,\varepsilon^{-2}+LΔκσ^2\varepsilon^{-4}\right)$ は有界分散オラクルモデルの下で与えられる。 定数$\bar L$の余分な平均二乗滑らかさ条件の下では、$Ω\! LΔ\sqrtκ\,\varepsilon^{-2}+Δ\bar Lσκ^{3/2}\varepsilon^{-3}\right)$。 これらの結果と合わせて、凹凸と強い凹凸構造の間の複雑性障壁を同定し、主な非凸凸-凹凸境界は分散還元を用いるアルゴリズムに有効である。

関連論文リスト

• Convex Optimization Is Free When Accuracy Is Expensive [18.56538898519597]
  我々は、勾配を正確に評価できないときに凸最適化を研究するが、精度$$$で$-$のように計算が成長するアルゴリズムの階層によってのみ近似される。 損失関数の最小化に要するコストは,問題要求の精度での勾配の1つの評価よりも,$のみに依存する。
  論文  参考訳（メタデータ） (2026-09-28T15:30:18Z)
• Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization [1.6921396880325779]
  我々は,SAPD+の決定論的複雑性における線形条件数依存性が,非連続性最適化に必要であることを証明した。
  論文  参考訳（メタデータ） (2026-09-25T06:34:04Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  両レベル最適化問題の1次解法について述べる。 特に,ペナルティ関数と超目的物との間に強い関連性を示す。 その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
  論文  参考訳（メタデータ） (2023-09-04T18:25:43Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)

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

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