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

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 $$\mathrm{\parallel }{W}_{ss}\mathrm{\parallel }\le \mathrm{\parallel }{W}_{rs}\mathrm{\parallel }\le \mathrm{\parallel }{W}_{gd}\mathrm{\parallel }\mathrm{.}$$ 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 $\mathrm{\parallel }{W}_{ss}\mathrm{\parallel }>\mathrm{\parallel }{W}_{rs}\mathrm{\parallel }$. $\bullet$ RS-GD inequality holds. For every symmetric $A_i$ with $(1-\frac{1}{4n^2+1})I⪯A_i⪯I$, one has $\mathrm{\parallel }{W}_{rs}\mathrm{\parallel }\le \mathrm{\parallel }{W}_{gd}\mathrm{\parallel }$. The proof was found via GPT-5.5 Pro extended prompted by the author.