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,,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 W rs W gd.] The conjecture is resolved, 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. RS-GD inequality holds. For every symmetric A i with (1- 1 4n 2+1)I A i I, one has W rs W gd. The proof was found via GPT-5.5 Pro extended prompted by the author.