mlsanityData to 7 Oct 2026

Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions

arXiv 2307.15868 ↗First posted 29 Jul 2023math.OC cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

This paper considers stochastic first-order algorithms for minimax optimization under Polyak--Lojasiewicz (PL) conditions. We propose SPIDER-GDA for solving the finite-sum problem of the form minx maxy f(x,y)triangleq frac1n sumi=1n fi(x,y), where the objective function f(x,y) is μx-PL in x and μy-PL in y; and each fi(x,y) is L-smooth. We prove SPIDER-GDA could find an ε-optimal solution within mathcal Oleft((n + √n,kappaxkappay2)log (1/ε)right) stochastic first-order oracle (SFO) complexity, which is better than the state-of-the-art method whose SFO upper bound is mathcal Obig((n + n2/3kappaxkappay2)log (1/ε)big), where kappaxtriangleq L/μx and kappaytriangleq L/μy. For the ill-conditioned case, we provide an accelerated algorithm to reduce the computational cost further. It achieves tildemathcal Obig((n+√n,kappaxkappay)log (kappay/ε) log(1/ε)big) SFO upper bound when kappay gtrsim √n. Our ideas can also be applied to a more general setting where the objective function only satisfies the PL condition for one variable. Numerical experiments validate the superiority of proposed methods.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 38 of its 55 references that are in the map. First posted on arXiv 29 Jul 2023.

Builds on

38 of 55 references.

References · 38

  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  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. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  6. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  7. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  8. 2016Variance-based regularization with convex objectivescited by 153
  9. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  10. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  11. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  12. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
26 more
  1. 2016A Geometric Analysis of Phase Retrievalcited by 92
  2. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  3. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  4. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  5. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  6. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  7. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  8. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  9. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  10. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  11. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  12. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  13. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 39
  14. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  15. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  16. 2019Variance Reduction for Matrix Gamescited by 37
  17. 2014Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learningcited by 35
  18. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  19. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  20. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  21. 2020Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Conditioncited by 19
  22. 2018Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimizationcited by 15
  23. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  24. 2021On Accelerated Methods for Saddle-Point Problems with Composite Structurecited by 13
  25. 2018Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifoldscited by 12
  26. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 0; 2026: 1.

4 papers.

  1. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  2. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  3. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  4. 2026REFINE: Trajectory Representation Learning via Closed-Loop Transcription -- Extended Versioncited by 1