mlsanityData to 7 Oct 2026

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

arXiv 2106.01761 ↗First posted 3 Jun 2021math.OC cs.LGcited by 15

Not on the map. Why?

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.

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

Builds on

29 of 41 references.

References · 29

  1. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  2. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  5. 2016Variance-based regularization with convex objectivescited by 153
  6. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  7. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  8. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  9. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  10. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  11. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  12. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
17 more
  1. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  2. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  3. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  4. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  5. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  6. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  7. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  8. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  9. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  10. 2015An optimal randomized incremental gradient methodcited by 32
  11. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  12. 2019Lower Bounds for Smooth Nonconvex Finite-Sum Optimizationcited by 19
  13. 2019Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structurecited by 15
  14. 2018Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communicationcited by 13
  15. 2021On Accelerated Methods for Saddle-Point Problems with Composite Structurecited by 13
  16. 2019A Stochastic Proximal Point Algorithm for Saddle-Point Problemscited by 6
  17. 2021DIPPA: An improved Method for Bilinear Saddle Point Problemscited by 6

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 7; 2023: 3; 2024: 3.

15 papers.

Sort:

  1. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  2. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  3. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  4. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  5. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 19
  6. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  7. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  8. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  9. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  10. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  11. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 4
  12. 2022Decentralized Stochastic Variance Reduced Extragradient Methodcited by 3
3 more
  1. 2024Multiple Greedy Quasi-Newton Methods for Saddle Point Problemscited by 3
  2. 2022Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysiscited by 0
  3. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0