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 [ |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 |W_{ss}|>|W_{rs}|. \bullet RS-GD inequality holds. For every symmetric A_i with \bigl(1-\frac1{4n^2+1}\bigr)I\preceq A_i\preceq I, one has |W_{rs}|\le|W_{gd}|. The proof was found via GPT-5.5 Pro extended prompted by the author.