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 42 papers

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
Oct 4, 2026Qihao ZhouMin-Max Optimization Oracle Complexity
Independent Researcher
Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
Sep 25, 2026Qihao ZhouOracle Complexity Min-Max Optimization
Independent Researcher
Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
Sep 17, 2026Minhao Zhang, Zi XuLast-Iterate Convergence Min-Max Optimization
Department of Mathematics, Shanghai University, Shanghai 200444, People’s Republic of China

Oct 4, 2026J/K move · Enter open · S save

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

Qihao Zhou

Independent Researcher

Min-Max Optimization Oracle Complexity

Open paper AskPDF arXiv

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.

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