arXiv：cs.LG（机器学习，全量分类）· Jiayi Song, Zi Xu·· 15 小时前AI 评分32
非凸-凹极小极大优化中带方差缩减的随机一阶算法下界
Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
AI 导读
研究为非凸-凹极小极大优化中允许使用方差缩减的随机一阶算法建立了复杂度下界，覆盖零尊重算法类。在联合梯度 L-Lipschitz 连续、对偶域半径 D_Y、初始次优性 Δ、噪声方差 σ² 的设定下，目标精度 ε 的下界为 Ω(L²D_YΔε⁻³+L³D_Y²Δσ²ε⁻⁶)。研究还给出非凸-强凹情形下依赖条件数 κ 的互补下界。
正文
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 $\Delta$. 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 $\sigma^2$ and mean-square smoothness, we prove the lower bound $\Omega\!\left(L^2D_Y\Delta\varepsilon^{-3}+L^3D_Y^2\Delta\sigma^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 $\mu>0$ and condition number $\kappa:=L/\mu$, we obtain $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+L\Delta\kappa\sigma^2\varepsilon^{-4}\right)$ under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant $\bar L$, we obtain $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+\Delta\bar L\sigma\kappa^{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.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.01662 [math.OC] |
| (or arXiv:2610.01662v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.01662 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zi Xu [view email]
[v1]
Thu, 1 Oct 2026 13:24:15 UTC (33 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org