mlsanityData to 7 Oct 2026

SGDA with shuffling: faster convergence for nonconvex-PL minimax optimization

arXiv 2210.05995 ↗First posted 12 Oct 2022math.OC stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent-ascent (SGDA) is one of the main workhorses for solving finite-sum minimax optimization problems. Most practical implementations of SGDA randomly reshuffle components and sequentially use them (i.e., without-replacement sampling); however, there are few theoretical results on this approach for minimax algorithms, especially outside the easier-to-analyze (strongly-)monotone setups. To narrow this gap, we study the convergence bounds of SGDA with random reshuffling (SGDA-RR) for smooth nonconvex-nonconcave objectives with Polyak-Lojasiewicz (PL) geometry. We analyze both simultaneous and alternating SGDA-RR for nonconvex-PL and primal-PL-PL objectives, and obtain convergence rates faster than with-replacement SGDA. Our rates extend to mini-batch SGDA-RR, recovering known rates for full-batch gradient descent-ascent (GDA). Lastly, we present a comprehensive lower bound for GDA with an arbitrary step-size ratio, which matches the full-batch upper bound for the primal-PL-PL case.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 23 of its 40 references that are in the map. First posted on arXiv 12 Oct 2022.

Builds on

23 of 40 references.

References · 23

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  7. 2020Large-scale Robust Deep AUC Maximization: A New Surrogate Loss and Empirical Studies on Medical Image Classificationcited by 84
  8. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  9. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
  10. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
  11. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  12. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
11 more
  1. 2020Closing the convergence gap of SGD without replacementcited by 56
  2. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  3. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  4. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  5. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  6. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  7. 2020Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Conditioncited by 19
  8. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  9. 2021Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimizationcited by 18
  10. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  11. 2022On Convergence of Gradient Descent Ascent: A Tight Local Analysiscited by 9

Built on by

Cited by year (2026 to 7 Oct)

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

8 papers.

  1. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
  2. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 9
  3. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  4. 2023Mini-Batch Optimization of Contrastive Losscited by 8
  5. 2023On the Training Instability of Shuffling SGD with Batch Normalizationcited by 3
  6. 2024Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Samplingcited by 1
  7. 2024Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimizationcited by 0
  8. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0