← All papers
First page of On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles

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

Yuxing Peng, Zhiqing Tang, Weijia Jia

cs.LG Nov 3, 2026 · v1
A Lean supplement in the arXiv ancillary files machine-checks the existential lower-bound assertions of the main theorem, including key lemmas, using a finite Rademacher construction.
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.

Known lower bounds for finite-sum nonconvex-strongly-concave minimax optimization cover only linear-span, zero-respecting, or restricted proximal algorithms. It was open whether exact component proximal steps or unrestricted adaptivity can improve the oracle complexity.

The authors build hard instances that chain nonconvex primal stages through dual paths. The internal edges of each path are owned by random components, and flat edge penalties hide hidden directions even from exact saddle-proximal responses. A matching upper bound combines SPDE updates, recursive variance-reduced gradients, L-SVRE steps and Catalyst acceleration. The lower-bound existential assertions are formalized in Lean, with a finite Rademacher construction replacing the Haar-distributed axes.

Every randomized adaptive algorithm with exact values, gradients and proximal responses needs Ω(n + min{√n κ, n^{3/4}√κ} LΔ/ε²) component queries. A gradient-only method matches this up to a log²(2+κ) factor. The Lean proof covers expected and fixed-confidence complexity in all three condition-number ranges.

Algorithm classComponent gradientsExact values, gradients, proximalSource
Linear-span or restricted protocolΩ(n+√(nκ) S), κ≥2nΩ(n+√(nκ) S), κ=Ω(n)Zhang et al.; Han et al.
Zero-respectingΩ(n+hS)–Zhou
Arbitrary randomized adaptiveΩ(n+hS)Ω(n+hS)Thm. 1
Matching upper boundO((n+hS) log²(2+κ))Thm. 2
Lower and upper bounds by algorithm class (S = LΔ/ε², h = min{√n κ, n^{3/4}√κ})