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

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

## 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 (most cited first, 30 of 36)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Manipulating SGD with Data Ordering Attacks](https://mlsanity.com/paper/2104.09667/) (2021)
- [A Game Theoretic Framework for Model Based Reinforcement Learning](https://mlsanity.com/paper/2004.07804/) (2020)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Adversarial Example Games](https://mlsanity.com/paper/2007.00720/) (2020)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [SMG: A Shuffling Gradient-Based Method with Momentum](https://mlsanity.com/paper/2011.11884/) (2020)
- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)

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

- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [SGDA with shuffling: faster convergence for nonconvex-PL minimax optimization](https://mlsanity.com/paper/2210.05995/) (2022)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation](https://mlsanity.com/paper/2305.17558/) (2023)
- [Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities](https://mlsanity.com/paper/2403.07148/) (2024)
- [Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling](https://mlsanity.com/paper/2411.05868/) (2024)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems](https://mlsanity.com/paper/2207.12845/) (2022)
- [Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2410.22297/) (2024)
- [CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedules](https://mlsanity.com/paper/2608.14761/) (2026)

## 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.