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

Yuxing Peng; Zhiqing Tang; Weijia Jia

cs.LGNov 3, 2026

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

Authors: Yuxing Peng, Zhiqing Tang, Weijia Jia

Organizations: Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China

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.

Figures & tables

	Oracle
Algorithm class	Component gradients	Exact values, gradients and proximal responses	Source
Linear-span or restricted protocol	$\Omega(n+\sqrt{n\kappa}\,S)$ , $\kappa\geq 2n$	$\Omega(n+\sqrt{n\kappa}\,S)$ , $\kappa=\Omega(n)$	Zhang et al. ; Han et al.
Zero-respecting	$\Omega(n+hS)$	–	Zhou
Arbitrary randomized adaptive	$\Omega(n+hS)$	$\Omega(n+hS)$	Thm. 1
Matching upper bound	$O\bigl((n+hS)\log^{2}(2+\kappa)\bigr)$		Thm. 2

Table 1: Bounds on component queries for finite-sum NC–SC problems with joint mean-squared smoothness, for small

\varepsilon

and every

\kappa\geq 1

unless stated;

h=\min\{\sqrt{n}\kappa,n^{3/4}\sqrt{\kappa}\}

and

S=L\Delta/\varepsilon^{2}

. Shaded: this paper. The first row combines Zhang et al. (2021) , for linear-span methods, and Han et al. (2024, Theorem 25) , for their restricted proximal protocol with primal nonconvexity parameter

L

; the second is the concurrent result of Zhou (2026a, Theorem 2) , which also attains this rate up to logarithmic factors from an exact dual maximizer. A dash marks a combination not treated separately. Down the first column the algorithm class grows and the bound reaches

n+hS

; the stronger oracle leaves it unchanged, and component gradients attain it up to the factor

\log^{2}(2+\kappa)

Panel of Figure 1 — Figure 1: A dual path. A query to component $i$ reveals the entire run of consecutive edges owned by $i$ and stops at the first edge with another owner, revealing no later owner or axis. There are order $Mm$ serial searches, each costing order $n$ .

Statement	Proof chain	Appendix
Theorem 3 , lower bound	Lemmas 5 , 6 $\to$ 7 – 9 $\to$ 10 $\to$ 11 $\to$ 12 – 14	A – C
Theorem 1 , $64\leq\kappa\leq 2^{18}\sqrt{n}$	the same chain with two-node paths $\to$ Corollary 16	D.1
Theorem 1 , $1\leq\kappa<64$	Lemmas 17 $\to$ 18 $\to$ 19 $\to$ 20	D.2 , D.3
Theorem 1 , all $\kappa$	Theorem 3 , Corollary 16 , Lemmas 20 , 21	D.4
Corollary 4	Corollary 15	C.2
Theorem 22	Lemmas 23 $\to$ 24 $\to$ initialization, estimators, refinement	E

Table 2: Where each main statement is proved, with the results its proof uses in order. In the first row, Lemmas 5 and 6 calibrate the paths and the forcing, Lemmas 7 – 9 give class membership, Lemma 10 the terminal barrier, Lemma 11 the width and initial budgets, and Lemmas 12 – 14 the legal domain, localization and owner search. The rows below the heavy rule concern upper bounds, which use only component gradients; the accelerated method also uses Catalyst ( Lin et al., 2018 ) and Zhang et al. (2021, Theorems 4.1 and 4.2) .

Min-Max Optimization

Min-max optimization studies algorithms for objectives where one decision-maker minimizes loss while an adversary or opponent maximizes it.

See all 41 papers

Oct 4, 2026

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

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.

Qihao Zhou

Independent Researcher

Min-Max Optimization Oracle Complexity

Ask PDF

Sep 25, 2026

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

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.

Qihao Zhou

Independent Researcher

Oracle Complexity Min-Max Optimization Nonconvex Stochastic Optimization

Ask PDF

Sep 17, 2026

Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization

We study smooth strongly convex--strongly concave minimax optimization in the deterministic unconstrained setting, without assuming a bilinear or separable structure. Although existing multi-loop methods attain near-optimal condition-number dependence, standard single-loop methods generally exhibit a substantial complexity gap. To close this gap, we propose the Single-Loop Predictor--Corrector Extragradient Method with Damped Momentum (PCE-DM), which combines an extragradient prediction--correction scheme with a novel auxiliary feedback recursion for the weaker-curvature variable. PCE-DM uses fixed parameters and two new full-gradient evaluations per iteration after one initialization query, while requiring no inner solves, accuracy schedules, or staged restarts. We develop a Lyapunov analysis that controls the predictor--corrector mismatch through corrected-gradient increments and establish last-iterate linear convergence. Specifically, PCE-DM computes an

\varepsilon

-accurate relative solution, measured by the squared Euclidean distance to the saddle point, within

\mathcal{O}\!\left(\sqrt{κ_xκ_y} \log(2κ_xκ_y/\varepsilon)\right)

full-gradient queries. This result closes the condition-number complexity gap between standard single-loop methods and near-optimal multi-loop methods, matching the known lower-bound order up to logarithmic factors while retaining fixed, explicit single-loop updates. Numerical experiments on regularized linear regression and AUC maximization demonstrate the computational efficiency of PCE-DM.

Minhao Zhang, Zi Xu

Department of Mathematics, Shanghai University, Shanghai 200444, People’s Republic of China

Last-Iterate Convergence Min-Max Optimization Extragradient Methods

Ask PDF

Abstract

Min-Max Optimization

Explore similar work

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

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

Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization