# A Resolution of the SS--RS--GD Inequalities

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

## Key facts

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

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

- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (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)
- [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)
- [Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False](https://mlsanity.com/paper/2006.01510/) (2020)

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

- [When the noncommutative AM-GM inequality holds](https://mlsanity.com/paper/2610.04874/) (2026)

## Abstract (arXiv)

Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices A1,dots,An, the operators Wss, Wrs, and Wgd that encode the expected iterate of single-shuffle SGD, random-reshuffle SGD, and gradient descent on a quadratic finite sum should satisfy [ |Wss|≤ | Wrs|≤ |Wgd|. ] The conjecture is resolved, bullet SS-RS inequality fails. Already for n=3, K=2, and d=4, we exhibit explicit PSD matrices whose condition number is arbitrarily close to 1, yet |Wss|>|Wrs|. bullet RS-GD inequality holds. For every symmetric Ai with bigl(1-frac14n2+1bigr)Ipreceq Aipreceq I, one has |Wrs|≤|Wgd|. The proof was found via GPT-5.5 Pro extended prompted by the author.