CS Paper Radar

On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles

Yuxing Peng, Zhiqing Tang, Weijia Jia

cs.LG ·submitted 2026-11-03 12:40 UTC · v1

Abstract

Finite-sum nonconvex-strongly-concave minimax problems arise in adversarial training and distributionally robust learning. Their known lower bounds cover only linear-span algorithms, zero-respecting algorithms, or a restricted proximal protocol. They leave open the power of exact component proximal steps, whose responses are global saddle points of regularized component problems and can expose directions that gradients do not reveal. We show that neither unrestricted adaptivity nor exact proximal access improves the polynomial complexity. We consider $n$ components with joint mean-squared smoothness $L$ and condition number $κ$, started from a point with primal gap at most $Δ$ and joint gradient norm at most $\sqrt{2LΔ}$. For $\varepsilon^2/(LΔ)$ below a universal constant, every randomized adaptive algorithm with exact component values, gradients, and proximal responses needs $Ω(n+\min\{\sqrt n\,κ,n^{3/4}\sqrtκ\}LΔ/\varepsilon^2)$ component queries in the worst case to find an $\varepsilon$-stationary point of the value function. A method using only component gradients attains this rate up to a factor $\log^2(2+κ)$, including initialization. Zhou (arXiv:2610.04944) concurrently proves the same rate for zero-respecting first-order methods. In our hard instances, every component admits proximal steps with the same step sizes, and a response for a component reveals hidden directions only up to the first one assigned to another component.

Comment
50 pages, including appendices and references. Lean 4 formalization of the lower bounds in the ancillary files

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

cs.LG math.OC ·2026-09-25 ·Qihao Zhou
theory similarity 0.70
Abstract · 20 pages

We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $μ$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-envelope stationarity criterion and the same primal-dual initialization gap. Specifically, when $σ\ge\varepsilon$, the worst-case complexity of zero-respecting algorithms is $Θ(κLGσ^2\varepsilon^{-4})$ in the stated accuracy regime, where $κ=L/μ$, $G$ bounds the initial primal-dual gap, and $σ^2$ bounds the variance of a general unbiased first-order oracle. The lower bound is realized on a smooth problem class with a bounded dual box. Our construction routes each link of a nonconvex zero-chain through a dual gradient of magnitude proportional to $\varepsilon/\sqrtκ$, while an undiscovered primal coordinate prevents stationarity. It also yields the primal-gradient lower bound $Ω(LΔ(\sqrtκ\varepsilon^{-2}+κσ^2\varepsilon^{-4}))$ after combination with the known deterministic bound, where $Δ$ bounds the initial primal function gap.

0.44

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

cs.LG math.OC ·2026-10-04 ·Qihao Zhou
theoryhighly cited similarity 0.69
Abstract · 30 pages, 2 figures, 2 tables

We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is $\tildeΘ(n+\min\{\sqrt{n}\,κ,n^{3/4}\sqrtκ\}\,LΔ\varepsilon^{-2})$ throughout $κ=L/μ\ge1$, under exact dual initialization and for $0<\varepsilon^2\le c_0LΔ$, where $c_0>0$ is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for $κ\ge\sqrt{n}$. For $1\leκ\le\sqrt{n}$, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains $\tilde{O}(n+\sqrt{n}\,κLΔ\varepsilon^{-2})$ with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most $\varepsilon^2$. Under individual smoothness, we also prove $Ω(n+\min\{κ,\sqrt{nκ}\}\,LΔ\varepsilon^{-2})$ for every $κ\ge1$. It matches the polynomial upper rate for a bilinear subclass when $κ\ge n$; the intermediate-condition-number gap remains open.

0.33

Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity

cs.LG math.OCstat.ML ·2026-10-08 ·Mingyi Li, Taira Tsuchiya, Kenji Yamanishi
similarity 0.68
Abstract · 27 pages, 3 figures, 2 tables

We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with $O(δ^{-1}\varepsilon^{-3})$ stochastic gradient queries or $O(dδ^{-1}\varepsilon^{-3})$ function-value queries, where $δ$ is the Goldstein radius, $\varepsilon$ is the stationarity tolerance, and $d$ is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.

0.47

On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

cs.LG stat.ML ·2026-10-14 ·Yuxuan Xia, Xiao-Tong Yuan
theory similarity 0.67
Abstract

Must the dimension and accuracy costs of zeroth-order optimization multiply? Global upper bounds for smooth stochastic nonconvex optimization scale as $O(dε^{-4})$, with both factors separately necessary. We show that their product is unavoidable. We establish an $Ω(dε^{-4})$ lower bound for smooth stochastic nonconvex optimization, yielding an $Ω(dδ^{-1}ε^{-3})$ bound for nonsmooth Goldstein stationarity. Both match the best-known full-space upper bounds, establishing joint minimax optimality in dimension and accuracy. These bounds hold against fully adaptive randomized algorithms with unrestricted queries and outputs, even under arbitrary sample reuse. As a byproduct, we establish noiseless exact-value lower bounds for both smooth and Goldstein stationarity, even against randomized algorithms.

0.24

Generalization Guarantees of Randomized Block Coordinate Descent for Nonconvex Learning

cs.LG ·2026-10-15 ·Ruixi Hu, Liang Wu
similarity 0.66
Abstract

Randomized block coordinate descent (RBCD) is a popular optimization algorithm for many large-scale machine learning problems. The existing theoretical analysis of RBCD mainly focuses on its convergence behavior from an optimization perspective, while its generalization behavior remains less understood for nonconvex problems. In this paper, we establish high-probability generalization guarantees for RBCD with nonconvex objectives. In the general nonconvex setting, we derive bounds on the gradients of both empirical and population risks, requiring only standard smoothness assumptions. With polynomially decaying step sizes, we tune the iteration number to balance optimization and generalization, thereby quantifying how early stopping leads to the optimal convergence rate for the population gradients. In the gradient-dominated setting, we provide bounds in terms of functional suboptimality, which nearly match the optimistic rates in convex and low-noise settings. Finally, we develop dimension-independent bounds for loss functions of a specific structure, making the generalization guarantees applicable to high-dimensional problems.

0.19

Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles

cs.LG math.OCstat.ML ·2026-10-17 ·Qihao Zhou, Shanshui Niu
similarity 0.66
Abstract · 23 pages, 2 figures, 1 table

We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point $x$ satisfying $\mathbb{E}\|\nablaΦ(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2})$ component-gradient calls, where $N$ is the total number of components and $κ$ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length $\tildeΘ(\sqrt{N/κ})$ with batches of size $\tildeΘ(\sqrt{Nκ})$. A single-level reduction shows that the dependence on $N$ and $\varepsilon$ is optimal up to logarithmic factors for fixed $κ$.

0.11

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

cs.LG math.OC ·2026-09-21 ·Dan Garber
similarity 0.66
Abstract

We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.

0.11

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

cs.LG math.OCstat.ML ·2026-10-01 ·Jiayi Song, Zi Xu
theory similarity 0.65
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-squared 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-squared 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.

0.31