# Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 55 references that are in the map.
- First posted on arXiv 29 Jul 2023.

## Builds on (most cited first, 30 of 38)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Reducing Noise in GAN Training with Variance Reduced Extragradient](https://mlsanity.com/paper/1904.08598/) (2019)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/2005.02426/) (2020)

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

- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm](https://mlsanity.com/paper/2310.20369/) (2023)
- [REFINE: Trajectory Representation Learning via Closed-Loop Transcription -- Extended Version](https://mlsanity.com/paper/2609.07206/) (2026)
- [Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games](https://mlsanity.com/paper/2610.07814/) (2026)

## Abstract (arXiv)

This paper considers stochastic first-order algorithms for minimax optimization under Polyak--Lojasiewicz (PL) conditions. We propose SPIDER-GDA for solving the finite-sum problem of the form minx maxy f(x,y)triangleq frac1n sumi=1n fi(x,y), where the objective function f(x,y) is μx-PL in x and μy-PL in y; and each fi(x,y) is L-smooth. We prove SPIDER-GDA could find an ε-optimal solution within mathcal Oleft((n + √n,kappaxkappay2)log (1/ε)right) stochastic first-order oracle (SFO) complexity, which is better than the state-of-the-art method whose SFO upper bound is mathcal Obig((n + n2/3kappaxkappay2)log (1/ε)big), where kappaxtriangleq L/μx and kappaytriangleq L/μy. For the ill-conditioned case, we provide an accelerated algorithm to reduce the computational cost further. It achieves tildemathcal Obig((n+√n,kappaxkappay)log (kappay/ε) log(1/ε)big) SFO upper bound when kappay gtrsim √n. Our ideas can also be applied to a more general setting where the objective function only satisfies the PL condition for one variable. Numerical experiments validate the superiority of proposed methods.