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

arXiv:2607.22620v1 Announce Type: cross Abstract: Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices A_1,ots,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, ullet 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}|. ullet RS-GD inequality holds. For every symmetric A_i with igl(1-frac1{4n^2+1}igr)Ipreceq A_ipreceq I, one has |W_{rs}|le|W_{gd}|. The proof was found via GPT-5.5 Pro extended prompted by the author.

Source: arXiv cs.LG | 2026-07-28