mlsanityData to 14 Oct 2026

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

arXiv 2607.22620 ↗First posted 16 Jun 2026math.OC cs.LG stat.MLcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

7 of 11 references.

References · 7

  1. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  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. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  6. 2020Closing the convergence gap of SGD without replacementcited by 57
  7. 2020Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is Falsecited by 16

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026When the noncommutative AM-GM inequality holdscited by 0