# SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems

arXiv: https://arxiv.org/abs/2205.15084 · HTML: https://mlsanity.com/paper/2205.15084/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2022.

## Built on by (most cited first, 23 of 23)

- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2210.17478/) (2022)
- [Federated Minimax Optimization with Client Heterogeneity](https://mlsanity.com/paper/2302.04249/) (2023)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2304.02441/) (2023)
- [Scaff-PD: Communication Efficient Fair and Robust Federated Learning](https://mlsanity.com/paper/2307.13381/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2503.18317/) (2025)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimization](https://mlsanity.com/paper/2311.00944/) (2023)
- [f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization](https://mlsanity.com/paper/2312.03259/) (2023)
- [Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions](https://mlsanity.com/paper/2405.18577/) (2024)
- [Anchored Langevin Algorithms](https://mlsanity.com/paper/2509.19455/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2307.07113/) (2023)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds](https://mlsanity.com/paper/2509.13628/) (2025)
- [Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems](https://mlsanity.com/paper/2605.08006/) (2026)
- [Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization](https://mlsanity.com/paper/2609.21747/) (2026)
- [Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2609.30877/) (2026)
- [Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations](https://mlsanity.com/paper/2512.01213/) (2025)
- [Learning the Robustness Mechanism with Bilevel Optimization](https://mlsanity.com/paper/2609.35541/) (2026)

## Abstract (arXiv)

We propose a new stochastic method SAPD+ for solving nonconvex-concave minimax problems of the form minmaxL(x,y)=f(x)+Phi(x,y)-g(y), where f,g are closed convex and Phi(x,y) is a smooth function that is weakly convex in x, (strongly) concave in y. Let δ2 denote the variance bound for the unbiased stochastic oracle used within SAPD+ to estimate nablaPhi. When δ>0, for both strongly concave and merely concave settings, SAPD+ achieves the best known oracle complexities: OBig(kappaymaxBig1,fracδ2ε2BigfracLG0ε2Big) for the strongly concave case without assuming compactness of the problem domain, and OBig(fracL3Dy2G0ε4Big(1+fracδ2ε2Big)Big) for the merely concave case, where kappay≥ 1 is the condition number, L is the Lipschitz constant of nabla Phi, G0 is the primal-dual gap of the initial point, and Dy=sup|y|: y∈dom g. We also propose SAPD+ with variance reduction, which enjoys OBig(maxBigkappay,√fracδεBig· (1+kappayfracδε)fracLG0ε2Big) oracle complexity for weakly convex-strongly concave setting --this is the best known upper complexity bound in the literature for this setting and our paper establishes it for the first time. We demonstrate the efficiency of SAPD+ on a distributionally robust learning problem with a nonconvex regularizer and also on a multi-class classification problem in deep learning.