mlsanityData to 14 Oct 2026

Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization

arXiv 2206.02953 ↗First posted 7 Jun 2022math.OC cs.GT cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

We analyze the convergence rates of stochastic gradient algorithms for smooth finite-sum minimax optimization and show that, for many such algorithms, sampling the data points without replacement leads to faster convergence compared to sampling with replacement. For the smooth and strongly convex-strongly concave setting, we consider gradient descent ascent and the proximal point method, and present a unified analysis of two popular without-replacement sampling strategies, namely Random Reshuffling (RR), which shuffles the data every epoch, and Single Shuffling or Shuffle Once (SO), which shuffles only at the beginning. We obtain tight convergence rates for RR and SO and demonstrate that these strategies lead to faster convergence than uniform sampling. Moving beyond convexity, we obtain similar results for smooth nonconvex-nonconcave objectives satisfying a two-sided Polyak-Lojasiewicz inequality. Finally, we demonstrate that our techniques are general enough to analyze the effect of data-ordering attacks, where an adversary manipulates the order in which data points are supplied to the optimizer. Our analysis also recovers tight rates for the incremental gradient method, where the data points are not shuffled at all.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 36 of its 64 references that are in the map. First posted on arXiv 7 Jun 2022.

Builds on

36 of 64 references.

References · 36

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  3. 2016Generative Adversarial Imitation Learningcited by 1,597
  4. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  5. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  6. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  7. 2019SGD: General Analysis and Improved Ratescited by 207
  8. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  9. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  10. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  11. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 79
  12. 2021Manipulating SGD with Data Ordering Attackscited by 74
24 more
  1. 2020A Game Theoretic Framework for Model Based Reinforcement Learningcited by 73
  2. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  3. 2019How Good is SGD with Random Shuffling?cited by 64
  4. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  5. 2018Negative Momentum for Improved Game Dynamicscited by 60
  6. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  7. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  8. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  9. 2020Closing the convergence gap of SGD without replacementcited by 57
  10. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 45
  11. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  12. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 36
  13. 2020Adversarial Example Gamescited by 34
  14. 2021Proximal and Federated Random Reshufflingcited by 33
  15. 2019Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascentcited by 29
  16. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 27
  17. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  18. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 21
  19. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  20. 2021Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimizationcited by 18
  21. 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 17
  22. 2020Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is Falsecited by 16
  23. 2021Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequalitycited by 16
  24. 2020Optimality and Stability in Non-Convex Smooth Gamescited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

10 papers.

  1. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
  2. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  3. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  4. 2023Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximationcited by 6
  5. 2024Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalitiescited by 5
  6. 2024Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Samplingcited by 1
  7. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 1
  8. 2022Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problemscited by 0
  9. 2024Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimizationcited by 0
  10. 2026CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedulescited by 0