# Improved Algorithms for Convex-Concave Minimax Optimization

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

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

- [Linear Adversarial Concept Erasure](https://mlsanity.com/paper/2201.12091/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization](https://mlsanity.com/paper/2201.07427/) (2022)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Federated Minimax Optimization with Client Heterogeneity](https://mlsanity.com/paper/2302.04249/) (2023)
- [DIPPA: An improved Method for Bilinear Saddle Point Problems](https://mlsanity.com/paper/2103.08270/) (2021)
- [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)
- [Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties](https://mlsanity.com/paper/2305.16186/) (2023)
- [Provable Reset-free Reinforcement Learning by No-Regret Reduction](https://mlsanity.com/paper/2301.02389/) (2023)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization](https://mlsanity.com/paper/2210.17550/) (2022)
- [Extragradient Type Methods for Riemannian Variational Inequality Problems](https://mlsanity.com/paper/2309.14155/) (2023)
- [Fair and Welfare-Efficient Constrained Multi-matchings under Uncertainty](https://mlsanity.com/paper/2411.02654/) (2024)
- [Displacement-Sparse Neural Optimal Transport](https://mlsanity.com/paper/2502.01889/) (2025)
- [EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization](https://mlsanity.com/paper/2508.12479/) (2025)
- [Min-Max Optimization Is Strictly Easier Than Variational Inequalities](https://mlsanity.com/paper/2511.03052/) (2025)
- [Provable Constrained Stochastic Convex Optimization with XOR-Projected Gradient Descent](https://mlsanity.com/paper/2203.11829/) (2022)
- [Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization](https://mlsanity.com/paper/2405.00914/) (2024)
- [Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach](https://mlsanity.com/paper/2410.14592/) (2024)

## Abstract (arXiv)

This paper studies minimax optimization problems minx maxy f(x,y), where f(x,y) is mx-strongly convex with respect to x, my-strongly concave with respect to y and (Lx,Lxy,Ly)-smooth. Zhang et al. provided the following lower bound of the gradient complexity for any first-order method: OmegaBigl(√fracLxmx+fracLxy2mx my+fracLymyln(1/ε)Bigr). This paper proposes a new algorithm with gradient complexity upper bound tildeOBigl(√fracLxmx+fracL· Lxymx my+fracLymylnleft(1/εright)Bigr), where L=maxLx,Lxy,Ly. This improves over the best known upper bound tildeOleft(√fracL2mx my ln3left(1/εright)right) by Lin et al. Our bound achieves linear convergence rate and tighter dependency on condition numbers, especially when Lxyll L (i.e., when the interaction between x and y is weak). Via reduction, our new bound also implies improved bounds for strongly convex-concave and convex-concave minimax optimization problems. When f is quadratic, we can further improve the upper bound, which matches the lower bound up to a small sub-polynomial factor.