# Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 25 references that are in the map.
- First posted on arXiv 1 Jun 2022.

## Builds on (most cited first, 19 of 19)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [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)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD](https://mlsanity.com/paper/1810.04723/) (2018)
- [A Universally Optimal Multistage Accelerated Stochastic Gradient Method](https://mlsanity.com/paper/1901.08022/) (2019)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False](https://mlsanity.com/paper/2006.01510/) (2020)
- [The Physical Systems Behind Optimization Algorithms](https://mlsanity.com/paper/1612.02803/) (2016)

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

- [Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noise](https://mlsanity.com/paper/2606.29554/) (2026)

## Abstract (arXiv)

When solving finite-sum minimization problems, two common alternatives to stochastic gradient descent (SGD) with theoretical benefits are random reshuffling (SGD-RR) and shuffle-once (SGD-SO), in which functions are sampled in cycles without replacement. Under a convenient stochastic noise approximation which holds experimentally, we study the stationary variances of the iterates of SGD, SGD-RR and SGD-SO, whose leading terms decrease in this order, and obtain simple approximations. To obtain our results, we study the power spectral density of the stochastic gradient noise sequences. Our analysis extends beyond SGD to SGD with momentum and to the stochastic Nesterov's accelerated gradient method. We perform experiments on quadratic objective functions to test the validity of our approximation and the correctness of our findings.