betaFeedback

Reading v1View latest version

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. 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 nn components with joint mean-squared smoothness LL and condition number κκ, started from a 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 needs Ω(n+min⁡{n κ,n3/4κ}LΔ/ε2)Ω(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+κ)\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.

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 (Madry et al., [13]), distributionally robust optimization (Namkoong and Duchi, [15]) and agnostic federated learning (Mohri et al., [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; gradient descent ascent and its variance-reduced variants are standard methods for the resulting nonconvex–strongly-concave (NC–SC) problems [10, 11]. The oracle complexity of such a problem is the number of component queries that any method must make. Finite-sum lower bounds have been proved for linear-span algorithms [27], a restricted proximal protocol [7] and zero-respecting algorithms [30]; none of them covers arbitrary randomized adaptive algorithms. An exact component proximal query also carries more information than a gradient. It is granted at every legal parameter, for which the regularized component problem is globally convex–concave and has a saddle point; it then returns a global saddle point, which can expose hidden directions that gradients alone cannot reveal. We ask whether such information changes the complexity of the finite-sum problem

min⁡p∈RdV(p),V(p)=max⁡y∈RdyF(p,y),F=1n∑i=1nFi,(1)\min_{p\in\mathbb{R}^{d}} 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 output criterion is a small gradient of the value function VV, also called the primal function [27, 30].

For primal gap Δ\Delta and accuracy ε\varepsilon, put 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 normalized-start class of § 2 and for ε2\varepsilon^2 below a universal multiple of LΔL\Delta, the 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),

so they match up to the factor log⁡2(2+κ)\log^2(2+\kappa). Both bounds cover every κ≥1\kappa\ge1 in the stated accuracy range, with primal-gap and joint-gradient data supplied at initialization.

For large condition numbers, our hard instances chain M≍SM\asymp S nonlinear primal stages through dual paths with m≍κ/n1/4m\asymp\sqrt{\kappa}/n^{1/4} nodes, and each edge of a path is assigned independently to one fixed component, its owner. A query reveals an edge only if it is addressed to the owner, so locating each owner takes on the order of nn component queries, giving

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

Proximal responses threaten this count in two ways. A response is a global saddle point, so one query could reveal edges far beyond the current one; and if the set of legal parameters depended on the component, testing legality alone would reveal owners. A public coordinate, with the same curvature in every component, makes the legal parameters identical for all components. Edge interactions that vanish while the hidden coordinates are small, together with a reflection symmetry, confine the unique saddle to the spans of the current query centers and the blocks already revealed. A query to a component then reveals only its run of consecutive edges and stops at the first edge with another owner. These constructions keep the primal scale LL and the scale L/nL/\sqrt{n} of the dual edge interactions.

Our contributions are as follows.

  • We construct hard instances for exact proximal oracles whose components are individually strongly concave, whose legal responses are unique, and whose legal domain is common to all components (Appendices A–D).

  • We prove the lower bound for every condition number against arbitrary randomized algorithms with exact values, gradients, and legal saddle-proximal responses, using long dual paths, two-node paths, and a flat primal coupling (Theorem 1); it also holds under the protocol of Han et al. [7] (Corollary 4).

  • We match it up to log⁡2(2+κ)\log^{2}(2+\kappa) with a component-gradient method that pays for initialization, snapshots, refreshes, and refinement (Theorem 2).

Concurrent work by Zhou [30] establishes the same polynomial rate for randomized zero-respecting incremental first-order methods. Our lower bound removes the zero-respecting restriction and adds exact values and proximal responses; our upper bound starts from a joint-gradient bound instead of an exact dual maximizer and charges the resulting initialization cost. Wu et al. [23] 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 the lower 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; 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. [27], for linear-span methods, and Han et al. [7], for their restricted proximal protocol with primal nonconvexity parameter LL; the second is the concurrent result of Zhou [30], 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+hSn+hS; the stronger oracle leaves it unchanged, and component gradients attain it up to the factor log⁡2(2+κ)\log^{2}(2+\kappa).

Models and Main Results

This section defines the problem class and the oracles, states our lower and upper bounds, and compares our assumptions with those of prior work.

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. For Y=Rdy\mathcal{Y}=\mathbb{R}^{d_y}, the class F(n,L,μ,Δ)\mathcal{F}(n,L,\mu,\Delta) consists of continuously differentiable finite sums satisfying, globally,

1n∑i∥∇Fi(w)−∇Fi(w′)∥2≤L2∥w−w′∥2,(2)\frac{1}{n}\sum_i\lVert\nabla F_i(w)-\nabla F_i(w')\rVert^2\le L^2\lVert w-w'\rVert^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)\lVert\nabla F(0,0)\rVert^2\le2L\Delta. \tag*{(5)}

All norms are Euclidean; for matrices and multilinear maps, ∥⋅∥\lVert\cdot\rVert is the induced operator norm. (2) is joint mean-squared smoothness, abbreviated as root-mean-square (RMS) smoothness. It implies mean LL-smoothness and component smoothness at most nL\sqrt{n}L. Strong concavity gives a unique maximizer y∗(p)y^*(p) and ∇V(p)=∇pF(p,y∗(p))\nabla V(p)=\nabla_pF(p,y^*(p)). We call the combination of (4) and (5) a normalized start. No bound on the initial primal–dual gap is assumed; that gap is G0=sup⁡yF(0,y)−inf⁡pF(p,0)G_0=\sup_y F(0,y)-\inf_p F(p,0), distinct from (4).

An exact indexed first-order query returns

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

The component saddle-proximal oracle, a proximal point step [18] on one component, additionally returns 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)}

at the queried center (pˉ,yˉ)(\bar p,\bar y). A finite γ>0\gamma>0 is legal when this problem has a saddle and Hi,γH_{i,\gamma} is globally convex in pp and concave in yy, as in (2) and Remark 12(iv) of Han et al. [7]. A saddle pair 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 p,yp,y.

One query to either oracle costs one unit, a full gradient costs nn, and QQ denotes the total cost of a run. Algorithms may choose arbitrary adaptive indices, finite query points, and legal proximal parameters using the entire exact transcript and a private random seed. Their computation and primal output are unrestricted, and stopping may be random. Only the displayed oracle information and common valid class parameters are supplied.

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\}\right)\frac{L\Delta}{\varepsilon^2}. \tag*{(9)}

The same lower order holds for success probability 2/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^{\ast}(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.

We prove Theorem 1 in Appendix D, where we obtain c=c⋆2/296c=c_{\star}^2/2^{96}; the next theorem gives the matching upper rate.

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.DOI
  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/18 M1178244.arxiv.org/abs/1803.06523
  6. [6]Cong Fang, Chris Junchi Li, Zhouchen 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]Jiayi Song and Zi Xu. Lower bounds for stochastic first-order algorithms with variance reduction in nonconvex-concave minimax optimization. arXiv:2610.01662v1, 2026.arxiv.org/abs/2610.01662
  20. [20]Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. doi: 10.1017/9781108231596.DOI
  21. [21]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
  22. [22]Qilong Wu, Zhihao Gu, and Junchi Yang. Lower bounds for nonconvex-concave minimax optimization. arXiv:2609.14233v1, 2026a.arxiv.org/abs/2609.14233
  23. [23]Wendao Wu, Haihan Zhang, Qian Chen, Chenheng Zhang, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouchен Lin. Matching randomized bounds for finite-sum nonconvex-concave optimization. arXiv:2610.16991v1, 2026b.arxiv.org/abs/2610.16991
  24. [24]Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouch en Lin. Sharp fresh-gradient complexity of nonconvex-strongly-concave minimax optimization. arXiv:2610.00229v1, 2026c.arxiv.org/abs/2610.00229
  25. [25]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
  26. [26]Huiling Zhang, Minhao Zhang, and Zi Xu. Single-loop stochastic projected damped extragradient methods for stochastic nonconvex–(strongly) concave minimax optimization. arXiv:2609.21747v1, 2026a.
  27. [27]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
  28. [28]Siqi Zhang, Qilong Wu, and Junchi Yang. Tight lower bounds for stochastic nonconvex-strongly-concave minimax optimization. arXiv:2609.35206v1, 2026b.arxiv.org/abs/2609.35206
  29. [29]Qihao Zhou. Optimal oracle complexity for finite-sum monotone inclusions. arXiv:2610.05038v1, 2026a.arxiv.org/abs/2610.05038
  30. [30]Qihao Zhou. Near-optimal complexity of finite-sum nonconvex-strongly-concave minimax optimization. arXiv:2610.04944v1, 2026b.arxiv.org/abs/2610.04944
  31. [31]Qihao Zhou. Tight stochastic condition-number dependence in nonconvex-strongly-concave minimax optimization. arXiv:2609.30877v1, 2026c.arxiv.org/abs/2609.30877

Paper details

vlnc:W_2gu6qpb9
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