# Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 41 references that are in the map.
- First posted on arXiv 3 Jun 2021.

## Builds on (most cited first, 29 of 29)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [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)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [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)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [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)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Lower Bounds for Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/1901.11224/) (2019)
- [Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structure](https://mlsanity.com/paper/1904.10112/) (2019)
- [Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication](https://mlsanity.com/paper/1805.09969/) (2018)
- [On Accelerated Methods for Saddle-Point Problems with Composite Structure](https://mlsanity.com/paper/2103.09344/) (2021)
- [A Stochastic Proximal Point Algorithm for Saddle-Point Problems](https://mlsanity.com/paper/1909.06946/) (2019)
- [DIPPA: An improved Method for Bilinear Saddle Point Problems](https://mlsanity.com/paper/2103.08270/) (2021)

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

- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Federated Minimax Optimization with Client Heterogeneity](https://mlsanity.com/paper/2302.04249/) (2023)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [Multiple Greedy Quasi-Newton Methods for Saddle Point Problems](https://mlsanity.com/paper/2408.00241/) (2024)
- [Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis](https://mlsanity.com/paper/2210.12860/) (2022)
- [Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity](https://mlsanity.com/paper/2405.16126/) (2024)
- [Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2610.04944/) (2026)

## Abstract (arXiv)

This paper considers stochastic first-order algorithms for convex-concave minimax problems of the form minbf xmaxbf yf(bf x, bf y), where f can be presented by the average of n individual components which are L-average smooth. For μx-strongly-convex-μy-strongly-concave setting, we propose a new method which could find a varepsilon-saddle point of the problem in tildemathcal O big(√n(√n+kappax)(√n+kappay)log(1/varepsilon)big) stochastic first-order complexity, where kappaxtriangleq L/μx and kappaytriangleq L/μy. This upper bound is near optimal with respect to varepsilon, n, kappax and kappay simultaneously. In addition, the algorithm is easily implemented and works well in practical. Our methods can be extended to solve more general unbalanced convex-concave minimax problems and the corresponding upper complexity bounds are also near optimal.