betaFeedback

WorksComputer Science

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

Abstract

Finite-sum nonconvex-strongly-concave minimax problems arise in adversarial training and distributionally robust learning. Known lower bounds for these problems cover only linear-span algorithms, zero-respecting algorithms, or a restricted proximal protocol. This leaves open whether unrestricted adaptivity or exact component proximal steps, which return global saddle points of regularized component problems, can improve the polynomial complexity. We show that they cannot. Consider n≥2n\ge2 components with joint mean-squared smoothness LL and condition number κ≥1κ\ge1, and a starting point with primal gap at most ΔΔ and joint gradient norm at most 2LΔ\sqrt{2LΔ}. For ε2/(LΔ)\varepsilon^2/(LΔ) below a universal constant, every randomized adaptive algorithm with exact component values, gradients, and proximal responses requires at least Ω(n+min⁡{n κ,n3/4κ}LΔ/ε2)Ω(n+\min\{\sqrt n\,κ,n^{3/4}\sqrtκ\}LΔ/\varepsilon^2) expected component queries in the worst case to find an ε\varepsilon-stationary point of the value function. A method that uses only component gradients attains this rate up to a factor log⁡2(2+κ)\log^2(2+κ), including its initialization cost. Zhou (arXiv:2610.04944) concurrently proves the same rate for zero-respecting first-order methods. For large condition numbers, our hard instances link primal stages through dual paths whose edges belong to random components, and with high probability a proximal query to a component reveals a path only up to the first edge owned by another component.

Introduction

Finite-sum minimax problems arise when a learning objective is optimized against an adversary or against a worst-case weighting of the training examples, with one component per example, as in adversarial training ([13]), distributionally robust optimization ([15]), and agnostic federated learning ([14]). When the adversary’s objective is concave and carries a strongly convex penalty, the inner maximization

©2026 Yuxing Peng, Zhiqing Tang, and Weijia Jia.

License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. is strongly concave, and we obtain the nonconvex–strongly-concave (NC–SC) problem

min⁡p∈RdpV(p),V(p)=max⁡y∈RdyF(p,y),F=1n∑i=1nFi(1)\min_{p\in\mathbb{R}^{d_p}} V(p),\qquad V(p)=\max_{y\in\mathbb{R}^{d_y}} F(p,y),\qquad F=\frac{1}{n}\sum_{i=1}^{n}F_i \tag*{(1)}

where FF is nonconvex in pp, μ\mu-strongly concave in yy, and the component gradients have joint mean-squared smoothness LL. The condition number κ=L/μ\kappa=L/\mu measures the difficulty of the inner maximization. The goal is a point with a small gradient of the value function VV, also called the primal function [25, 27]. Gradient descent ascent and its variance-reduced variants are standard methods for this problem [10, 11], and the oracle complexity of the problem is the number of component queries that the best method requires in the worst case.

Known lower bounds for finite-sum NC–SC problems cover linear-span algorithms [25], a restricted proximal protocol [7], and zero-respecting algorithms [27]. None of them covers arbitrary randomized adaptive algorithms, which may choose components and query points based on the full transcript and a random seed. An exact component proximal query also carries more information than a gradient. It is available at every legal parameter, for which the regularized component problem is globally convex–concave and has a saddle point, and it returns a global saddle point, which can expose hidden directions that gradients do not reveal. Whether unrestricted adaptivity or exact proximal access can lower the complexity has therefore remained open.

We prove that neither of them changes the polynomial complexity. Write S=LΔ/ε2S=L\Delta/\varepsilon^2 and h(n,κ)=min⁡{nκ,n3/4κ}h(n,\kappa)=\min\{\sqrt{n\kappa},n^{3/4}\sqrt{\kappa}\}. On the class of § 2, whose instances start from a point with primal gap at most Δ\Delta and joint gradient norm at most 2LΔ\sqrt{2L\Delta}, our lower and upper bounds on the oracle complexity are

Ω((n+h(n,κ)S))andO((n+h(n,κ)S)log⁡2(2+κ)),\Omega\bigl((n+h(n,\kappa)S)\bigr)\quad\text{and}\quad O\bigl((n+h(n,\kappa)S)\log^2(2+\kappa)\bigr),

for n≥2n\ge2, every κ≥1\kappa\ge1, and ε2\varepsilon^2 below a universal multiple of LΔL\Delta, so they match up to the factor log⁡2(2+κ)\log^2(2+\kappa). Both bounds hold for the expected cost and for a deterministic query cap with success probability $2/3 ({xref}Theorems 1 and 2), and for $\kappa\ge 2^{18}\sqrt{n}$ the lower bound also holds under the protocol of {citet}Han et al. [7] ({xref}Corollary 4`).

Where does the factor n3/4κn^{3/4}\sqrt{\kappa} come from at large condition numbers? Our hard instances chain M≍SM\asymp S nonlinear primal stages through dual paths with mm nodes, and each internal edge of a path is assigned independently to one uniformly random component, its owner. A query to another component only rules that component out as the owner, so an algorithm is unlikely to find the owner with far fewer than order nn queries. For the mean FF to carry an edge with weight aa, the owner must carry it with weight nana, which adds a term of order n−1(na)2=na\sqrt{n^{-1}(na)^2}=\sqrt{n}a to the mean-squared smoothness constant and limits aa to at most order L/nL/\sqrt{n}; we take aa of this order. A path with mm nodes and edge weight aa preserves the amplitude of its input from one end to the other up to a constant factor when its strong concavity is of order a/m2a/m^2, and this strong concavity must be at least μ\mu. Paths can therefore have m≍a/μ≍κ/n1/4m\asymp\sqrt{a/\mu}\asymp\sqrt{\kappa}/n^{1/4} nodes. Each of the M(m−1)M(m-1) owner searches costs at least order nn queries in expectation, so the total expected cost is at least of order

n⋅m⋅M≍n3/4κ LΔε2.n\cdot m\cdot M\asymp n^{3/4}\sqrt{\kappa}\,\frac{L\Delta}{\varepsilon^2}.

Exact proximal responses threaten this count in two ways. If the legal parameters depended on the component, testing legality alone would reveal owners; and since a response is a global saddle point, one query could reveal edges far beyond the current one. A public coordinate, with the same curvature in every component, makes the legal parameters identical for all components. A reflection symmetry confines the saddle point of a censored problem, in which the unrevealed hidden directions are set to zero, to the spans of the current query centers and of the blocks already revealed. Edge interactions vanish while the hidden coordinates are small, so with high probability this saddle point is the actual response, and a query to a component reveals only its run of consecutive edges and stops at the first edge with another owner.

Concurrent work by Zhou [27] establishes the same polynomial rate for randomized zero-respecting incremental first-order methods, starting from an exact dual maximizer y∗(0)=0y^{*}(0)=0. Our lower bound removes the zero-respecting restriction, adds exact values and proximal responses, and also holds under that start (§ 2.2). Our upper bound starts instead from a joint-gradient bound and pays for the resulting initialization. Wu et al. [22] prove lower bounds for arbitrary randomized algorithms in the related finite-sum nonconvex–concave (NC–C) problem over a bounded dual domain, with values and gradients only. Table 1 compares these bounds, and § 2.2 compares our assumptions with those of prior work.

Algorithm classComponent gradientsExact values, gradients and proximal responsesSource
Linear-span or restricted protocolΩ(n+nκ S)\Omega(n+\sqrt{n\kappa}\,S), κ≥2n\kappa\ge2nΩ(n+nκ S)\Omega(n+\sqrt{n\kappa}\,S), κ=Ω(n)\kappa= \Omega(n)Zhang et al.; Han et al.
Zero-respectingΩ(n+hS)\Omega(n+hS)–Zhou
Arbitrary randomized adaptiveΩ(n+hS)\Omega(n+hS)Ω(n+hS)\Omega(n+hS)Thm. 1
Matching upper boundO((n+hS)log⁡2(2+κ))O((n+hS)\log^{2}(2+\kappa))Thm. 2

Table 1. Bounds on component queries for finite-sum NC–SC problems with joint mean-squared smoothness, for small ε\varepsilon and every κ≥1\kappa\ge1 unless stated otherwise; h=min⁡{nκ,n3/4κ}h=\min\{\sqrt{n\kappa},n^{3/4}\sqrt{\kappa}\} and S=LΔ/ε2S=L\Delta/\varepsilon^{2}. Shaded: this paper. The first row combines Zhang et al. [25], for linear-span methods, and Han et al. [7], for their restricted proximal protocol with primal nonconvexity parameter LL; the second is the concurrent lower bound of Zhou [27], whose Theorem 1 also gives a matching upper bound up to logarithmic factors from an exact dual maximizer. A dash marks a combination not treated separately. Our lower bound Ω(n+hS)\Omega(n+hS) covers the largest algorithm class and the stronger oracle; a method using only component gradients attains this rate up to the factor log⁡2(2+κ)\log^{2}(2+\kappa).

Models and Main Results

Our lower and upper bounds are stated for the same class of finite sums and the same cost model. They differ in the oracle: the lower bounds allow exact proximal responses, whereas our upper bounds use only component gradients.

Strongly Concave Finite Sums and Exact Indexed Oracles

Write [n]={1,…,n}[n]=\{1,\ldots,n\}, w=(p,y)w=(p,y), and S=LΔ/ε2S=L\Delta/\varepsilon^{2}. With the dual space Y=Rdy\mathcal{Y}=\mathbb{R}^{d_y}, the class F(n,L,μ,Δ)\mathcal{F}(n,L,\mu,\Delta) consists of the finite sums F=1n∑i=1nFiF=\frac{1}{n}\sum_{i=1}^{n}F_i with continuously differentiable components that satisfy, globally,

1n∑i∥∇Fi(w)−∇Fi(w′)∥2≤L2∥w−w′∥2,(2)\frac{1}{n}\sum_i\left\|\nabla F_i(w)-\nabla F_i(w')\right\|^2\le L^2\left\|w-w'\right\|^2, \tag*{(2)}
F(p,⋅) is μ-strongly concave,(3)F(p,\cdot)\text{ is }\mu\text{-strongly concave}, \tag*{(3)}
V(0)−inf⁡pV(p)≤Δ,(4)V(0)-\inf_p V(p)\le\Delta, \tag*{(4)}
∥∇F(0,0)∥2≤2LΔ.(5)\left\|\nabla F(0,0)\right\|^2\le2L\Delta. \tag*{(5)}

All norms are Euclidean; for matrices and multilinear maps, ∥⋅∥\|\cdot\| is the induced operator norm. We call condition (2) joint mean-squared smoothness, or root-mean-square (RMS) smoothness for short. It bounds only an average over the components: it implies that the mean FF is LL-smooth and that each component is at most nL\sqrt{n}L-smooth. By the strong concavity (3), for every pp the function F(p,⋅)F(p,\cdot) has a unique maximizer y∗(p)y^*(p), and ∇V(p)=∇pF(p,y∗(p))\nabla V(p)=\nabla_pF(p,y^*(p)). We call conditions (4) and (5) together a normalized start. They describe the starting point by its primal gap and its joint gradient, without requiring that its dual part be an exact maximizer. We write G0=sup⁡yF(0,y)−inf⁡pF(p,0)G_0=\sup_y F(0,y)-\inf_p F(p,0) for the initial primal–dual gap; it differs from the primal gap in (4), and the class places no bound on it. For a component index ii and a point ww, an exact indexed first-order query returns

O(i,w)=(Fi(w),∇pFi(w),∇yFi(w)).(6)\mathcal{O}(i,w)=(F_i(w),\nabla_pF_i(w),\nabla_yF_i(w)). \tag*{(6)}

The component saddle-proximal oracle performs a proximal point step [18] on one component. For a parameter γ>0\gamma>0, it returns, together with the first-order information (6), a saddle pair of

Hi,γ(p,y)=Fi(p,y)+∥p−pˉ∥2−∥y−yˉ∥22γ(7)H_{i,\gamma}(p,y)=F_i(p,y)+\frac{\lVert p-\bar{p}\rVert^2-\lVert y-\bar{y}\rVert^2}{2\gamma} \tag*{(7)}

where (pˉ,yˉ)(\bar{p},\bar{y}) is the queried center. Since a component may be nonconvex in pp, the regularized problem (7) need not be convex–concave for every γ\gamma, so the oracle answers only at legal parameters. As in Equation (2) and Remark 12(iv) of Han et al. [7], a finite γ>0\gamma>0 is legal when Hi,γH_{i,\gamma} is globally convex in pp and concave in yy and has a saddle point. A saddle pair (p+,y+)(p^+,y^+) satisfies Hi,γ(p+,y)≤Hi,γ(p+,y+)≤Hi,γ(p,y+)H_{i,\gamma}(p^+,y)\le H_{i,\gamma}(p^+,y^+)\le H_{i,\gamma}(p,y^+) for all pp and yy.

One query to either oracle costs one unit, a full gradient costs nn units, and QQ denotes the total cost of a run. At each query, the algorithm chooses the component index, a finite query point and, for a proximal query, a legal parameter based on the entire exact transcript and a private random seed. Its computation and its primal output are unrestricted, and it may stop at a random time. Apart from the oracle answers, the algorithm is given only the dimensions, the target accuracy ε\varepsilon, and the class parameters, which are the same for every instance of the class.

Theorem 1 (Unrestricted lower bound for every condition number). There are universal constants c⋆∈(0,1/2]c_{\star} \in(0,1/2] and c>0c > 0 such that, for n≥2n \ge2, L,μ,Δ>0L,\mu,\Delta> 0, κ=L/μ≥1\kappa= L/\mu\ge1, and

0<ε2≤2−52c⋆2LΔ,(8)0 < \varepsilon^2 \le2^{-52}c_{\star}^2L\Delta, \tag*{(8)}

every algorithm using either exact indexed oracle above, terminating almost surely and guaranteeing E∥∇V(pout)∥≤ε\mathbb{E}\lVert\nabla V(p_{\mathrm{out}})\rVert\le\varepsilon uniformly on F(n,L,μ,Δ)\mathcal{F}(n,L,\mu,\Delta) has worst-case expected cost at least

c(n+min⁡{nκ,n3/4κ}LΔε2).(9)c\left(n+\min\left\{\sqrt{n}\kappa,n^{3/4}\sqrt{\kappa}\right\}\frac{L\Delta}{\varepsilon^2}\right). \tag*{(9)}

A lower bound of the same order holds for success probability 2/32/3 under a deterministic query cap. The hard instances have polynomial dimension, C1,1C^{1,1} components that are individually μ\mu-strongly concave in yy, y⋆(0)=0y^{\star}(0)=0, finite initial primal–dual gap G0G_0, and a unique response at every legal proximal parameter. Their exact legal domain is common to all components, all hidden realizations and all proximal centers.

The accuracy condition (8) asks only that ε2/(LΔ)\varepsilon^2/(L\Delta) be below a universal constant. We prove Theorem 1 in Appendix D, where we obtain c=c⋆2/296c=c_{\star}^2/2^{96}.

References

  1. [1]Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 778–816, 2022.arxiv.org/abs/2102.08352
  2. [2]Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165–214, 2023. doi: 10.1007/s10107-022-01822-7. Revised full version: arXiv:1912.02365v2.
  3. [3]Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. In Advances in Neural Information Processing Systems, volume 32, 2019. Full version: arXiv:1906.10655v2.arxiv.org/abs/1906.10655
  4. [4]Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184:71–120, 2020. doi: 10.1007/s10107-019-01406-y.DOI
  5. [5]Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207–239, 2019. doi: 10.1137/18M1178244.DOI
  6. [6]Cong Fang, Chris Junchi Li, Zhоuchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, volume 31, 2018.arxiv.org/abs/1807.01695
  7. [7]Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. Journal of Machine Learning Research, 25(2):1–86, 2024.
  8. [8]Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex-strongly-concave min-max optimization. In Advances in Neural Information Processing Systems, volume 34, 2021.arxiv.org/abs/2104.08708
  9. [9]Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: From theory to practice. Journal of Machine Learning Research, 18 (212):1–54, 2018.
  10. [10]Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6083–6093, 2020.arxiv.org/abs/1906.00331
  11. [11]Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems. In Advances in Neural Information Processing Systems, volume 33, pages 20566–20577, 2020.arxiv.org/abs/2001.03724
  12. [12]Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization. arXiv:2106.01761v2, 2022.arxiv.org/abs/2106.01761
  13. [13]Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. arXiv:1706.06083.arxiv.org/abs/1706.06083
  14. [14]Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4615–4625, 2019.arxiv.org/abs/1902.00146
  15. [15]Hongseok Namkoong and John C. Duchi. Stochastic gradient methods for distributionally robust optimization with $f$-divergences. In *Advances in Neural Information Processing Systems*, volume 29, 2016.
  16. [16]Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In *Proceedings of the 34th International Conference on Machine Learning*, volume 70 of *Proceedings of Machine Learning Research*, pages 2613–2621, 2017.arxiv.org/abs/1703.00102
  17. [17]Yuxing Peng, Zhiqing Tang, and Weijia Jia. Dense weak hiding: Closing complexity gaps in nonconvex and PL finite-sum optimization under individual smoothness. arXiv:2609.00045v3, 2026.arxiv.org/abs/2609.00045
  18. [18]R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. *SIAM Journal on Control and Optimization*, 14(5):877–898, 1976. doi: 10.1137/0314056.DOI
  19. [19]Roman Vershynin. *High-Dimensional Probability: An Introduction with Applications in Data Science*. Cambridge University Press, 2018. doi: 10.1017/9781108231596.DOI
  20. [20]Blake E. Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In *Advances in Neural Information Processing Systems*, volume 29, 2016. Full version: arXiv:1605.08003v3.arxiv.org/abs/1605.08003
  21. [21]Qilong Wu, Zihao Gu, and Junchi Yang. Lower bounds for nonconvex-concave minimax optimization. arXiv:2609.14233v1, 2026a.arxiv.org/abs/2609.14233
  22. [22]Wendao Wu, Haihan Zhang, Qian Chen, Chenheng Zhang, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouchen Lin. Matching randomized bounds for finite-sum nonconvex-concave optimization. arXiv:2610.16991v1, 2026b.arxiv.org/abs/2610.16991
  23. [23]Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In *Proceedings of the 18th Annual Symposium on Foundations of Computer Science*, pages 222–227, 1977. doi: 10.1109/SFCS.1977.24.DOI
  24. [24]Huiling Zhang, Minhao Zhang, and Zi Xu. Single-loop stochastic projected damped extragradient methods for stochastic nonconvex–(strongly) concave minimax optimization. arXiv:2609.21747v1, 2026.
  25. [25]Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex-strongly-concave minimax optimization. In *Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence*, volume 161 of *Proceedings of Machine Learning Research*, pages 482–492, 2021.arxiv.org/abs/2103.15888
  26. [26]Qihao Zhou. Optimal oracle complexity for finite-sum monotone inclusions. arXiv:2610.05038v1, 2026a.arxiv.org/abs/2610.05038
  27. [27]Qihao Zhou. Near-optimal complexity of finite-sum nonconvex-strongly-concave minimax optimization. arXiv:2610.04944v1, 2026b.arxiv.org/abs/2610.04944

Paper details

vlnc:W_2gu6qpb9
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 14

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT (multiple versions), Anthropic’s Claude

View statement
Looking for related papers…
Contents