# An Optimal Multistage Stochastic Gradient Method for Minimax Problems

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2020.

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

- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning](https://mlsanity.com/paper/2108.06869/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergence](https://mlsanity.com/paper/2210.12812/) (2022)
- [Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems](https://mlsanity.com/paper/2210.09382/) (2022)
- [Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning](https://mlsanity.com/paper/2112.11663/) (2021)
- [Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization](https://mlsanity.com/paper/2206.08573/) (2022)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm](https://mlsanity.com/paper/2202.09688/) (2022)
- [Min-Max Optimization under Delays](https://mlsanity.com/paper/2307.06886/) (2023)
- [A Method for Learning Value Systems in Generative AI](https://mlsanity.com/paper/2607.16903/) (2026)

## Abstract (arXiv)

In this paper, we study the minimax optimization problem in the smooth and strongly convex-strongly concave setting when we have access to noisy estimates of gradients. In particular, we first analyze the stochastic Gradient Descent Ascent (GDA) method with constant stepsize, and show that it converges to a neighborhood of the solution of the minimax problem. We further provide tight bounds on the convergence rate and the size of this neighborhood. Next, we propose a multistage variant of stochastic GDA (M-GDA) that runs in multiple stages with a particular learning rate decay schedule and converges to the exact solution of the minimax problem. We show M-GDA achieves the lower bounds in terms of noise dependence without any assumptions on the knowledge of noise characteristics. We also show that M-GDA obtains a linear decay rate with respect to the error's dependence on the initial error, although the dependence on condition number is suboptimal. In order to improve this dependence, we apply the multistage machinery to the stochastic Optimistic Gradient Descent Ascent (OGDA) algorithm and propose the M-OGDA algorithm which also achieves the optimal linear decay rate with respect to the initial error. To the best of our knowledge, this method is the first to simultaneously achieve the best dependence on noise characteristic as well as the initial error and condition number.