math.OCOct 4, 2026

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

Authors: Qihao Zhou

Organizations: Independent Researcher

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 Θ~(n+min⁡{n κ,n3/4κ} LΔε−2)\tildeΘ(n+\min\{\sqrt{n}\,κ,n^{3/4}\sqrtκ\}\,LΔ\varepsilon^{-2}) throughout κ=L/μ≥1κ=L/μ\ge1, under exact dual initialization and for 0<ε2≤c0LΔ0<\varepsilon^2\le c_0LΔ, where c0>0c_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 κ≥nκ\ge\sqrt{n}. For 1≤κ≤n1\leκ\le\sqrt{n}, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains O~(n+n κLΔε−2)\tilde{O}(n+\sqrt{n}\,κLΔ\varepsilon^{-2}) with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most ε2\varepsilon^2. Under individual smoothness, we also prove Ω(n+min⁡{κ,nκ} LΔε−2)Ω(n+\min\{κ,\sqrt{nκ}\}\,LΔ\varepsilon^{-2}) for every κ≥1κ\ge1. It matches the polynomial upper rate for a bilinear subclass when κ≥nκ\ge n; the intermediate-condition-number gap remains open.

Figures & tables

ResultOracle/classComplexity
SREDA [ 10 ] , n≥κ2n\geq\kappa^{2}IFOO~(n+n κ2LΔε−2)\displaystyle\widetilde{O}(n+\sqrt{n}\,\kappa^{2}L\Delta\varepsilon^{-2})
Catalyst [ 1 ]IFOO~((n+n3/4κ)LΔε−2)\displaystyle\widetilde{O}((n+n^{3/4}\sqrt{\kappa})L\Delta\varepsilon^{-2})
This paper, Theorem 1ZR IFOO~(n+min⁡{n κ,n3/4κ}LΔε−2)\displaystyle\boldsymbol{\widetilde{O}(n+\min\{\sqrt{n}\,\kappa,n^{3/4}\sqrt{\kappa}\}L\Delta\varepsilon^{-2})}
Zhang et al. [1]Linear-span IFOΩ(n+nκ LΔε−2)\displaystyle\Omega(n+\sqrt{n\kappa}\,L\Delta\varepsilon^{-2})
Han et al. [2] , Theorem 25PIFO classΩ(n+nκ LΔε−2)\displaystyle\Omega(n+\sqrt{n\kappa}\,L\Delta\varepsilon^{-2})
This paper, Theorem 2Randomized ZR IFOΩ(n+min⁡{n κ,n3/4κ}LΔε−2)\displaystyle\boldsymbol{\Omega(n+\min\{\sqrt{n}\,\kappa,n^{3/4}\sqrt{\kappa}\}L\Delta\varepsilon^{-2})}
Table 1: Component-oracle complexities under averaged smoothness (AS). Upper bounds precede lower bounds. The bold complexities are our matching rates under the accuracy restriction of Theorem 1 .
ResultRangeComplexity
Proximal reduction of Jin et al. [15]all κ\kappaO~((n+nκ)LΔε−2)\displaystyle\widetilde{O}((n+\sqrt{n\kappa})L\Delta\varepsilon^{-2})
RPDA, Theorem 3κ≤n\kappa\leq\sqrt{n}O~(n+n κLΔε−2)\displaystyle\boldsymbol{\widetilde{O}(n+\sqrt{n}\,\kappa L\Delta\varepsilon^{-2})}
Combined upper boundall κ\kappaO~(n+min⁡{n κ,n+nκ}LΔε−2)\displaystyle\boldsymbol{\widetilde{O}(n+\min\{\sqrt{n}\,\kappa,n+\sqrt{n\kappa}\}L\Delta\varepsilon^{-2})}
Peng et al. [6] , minimizationall κ\kappaΩ(n+n LΔε−2)\displaystyle\Omega(n+\sqrt{n}\,L\Delta\varepsilon^{-2})
This paper, Theorem 4all κ\kappaΩ(n+min⁡{κ,nκ}LΔε−2)\displaystyle\boldsymbol{\Omega(n+\min\{\kappa,\sqrt{n\kappa}\}L\Delta\varepsilon^{-2})}
Combined lower boundall κ\kappaΩ(n+max⁡{n,min⁡{κ,nκ}}LΔε−2)\displaystyle\boldsymbol{\Omega(n+\max\{\sqrt{n},\min\{\kappa,\sqrt{n\kappa}\}\}L\Delta\varepsilon^{-2})}
Table 2: Component-oracle complexities for the individually smooth bilinear subclass (IS–B), ( 5 ). Upper bounds precede lower bounds. The bold combined rates match up to logarithms for κ≥n\kappa\geq n and for bounded κ\kappa .
Figure 1: Convergence under averaged smoothness (Table 1 ): running minimum of the envelope gradient against IFO calls; lines show the seed with median finishing cost and bands span three seeds. The light band marks the method of Theorem 1 : RPDA for κ≤n\kappa\leq\sqrt{n} and the Catalyst-type method for κ>n\kappa>\sqrt{n} .
Figure 2: Convergence on the bilinear individually smooth subclass (Table 2 ), with the conventions of Figure 1 . The light band marks the combined upper bound of Table 2 : RPDA for κ≤n\kappa\leq\sqrt{n} and the proximal reduction of Proposition 1 for κ>n\kappa>\sqrt{n} .
More in this topic

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

Explore similar work

CardsList

  1. Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

    Aug 30, 2026Yuxing Peng, Zhiqing Tang, Weijia JiaOracle ComplexityNonconvex Optimization

    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, BNU-HKBU United International College, Zhuhai 519087, China

  2. Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

    Oct 1, 2026Jiayi Song, Zi XuMin-Max Optimization

    Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

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

    Sep 25, 2026Qihao ZhouOracle ComplexityMin-Max Optimization

    Independent Researcher