# Efficient Algorithms for Smooth Minimax Optimization

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2019.

## Built on by (most cited first, 30 of 76)

- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets](https://mlsanity.com/paper/2305.19004/) (2023)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [Distributed Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2210.07588/) (2022)
- [Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization](https://mlsanity.com/paper/2201.07427/) (2022)
- [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022)
- [Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2211.13668/) (2022)
- [Solving a class of non-convex min-max games using adaptive momentum methods](https://mlsanity.com/paper/2104.12676/) (2021)
- [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Convex-Concave Min-Max Stackelberg Games](https://mlsanity.com/paper/2110.05192/) (2021)
- [Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm](https://mlsanity.com/paper/2202.06950/) (2022)
- [On Convergence of Gradient Descent Ascent: A Tight Local Analysis](https://mlsanity.com/paper/2207.00957/) (2022)
- [Can We Find Nash Equilibria at a Linear Rate in Markov Games?](https://mlsanity.com/paper/2303.03095/) (2023)

## Abstract (arXiv)

This paper studies first order methods for solving smooth minimax optimization problems minx maxy g(x,y) where g(·,·) is smooth and g(x,·) is concave for each x. In terms of g(·,y), we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. For strongly-convex g(·, y), forall y, we propose a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in tildeO(1/k2) iterations, improving over current state-of-the-art rate of O(1/k). We use this result along with an inexact proximal point method to provide tildeO(1/k1/3) rate for finding stationary points in the nonconvex setting where g(·, y) can be nonconvex. This improves over current best-known rate of O(1/k1/5). Finally, we instantiate our result for finite nonconvex minimax problems, i.e., minx max1≤ i≤ m fi(x), with nonconvex fi(·), to obtain convergence rate of O(m(log m)3/2/k1/3) total gradient evaluations for finding a stationary point.