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

Abstract

Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices $A_1,\dots ,A_n$, the operators $W_{ss}$, $W_{rs}$, and $W_{gd}$ that encode the expected iterate of single-shuffle SGD, random-reshuffle SGD, and gradient descent on a quadratic finite sum should satisfy \[ \|W_{ss}\|\le \| W_{rs}\|\le \|W_{gd}\|. \] 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 $\Vert W_{ss}\Vert >\Vert W_{rs}\Vert$. $\bullet$ RS-GD inequality holds. For every symmetric $A_i$ with $(1-\frac{1}{4n^2+1})I⪯A_i⪯I$, one has $\Vert W_{rs}\Vert \le \Vert W_{gd}\Vert$. The proof was found via GPT-5.5 Pro extended prompted by the author.