2026/06/16 by Binghui Peng
#math.OC #cs.LG #stat.ML
Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices A1,…,An, the operators Wss, Wrs, and Wgd that encode the expected iterate of single-shuffle SGD, random-reshuffle SGD, and gradient descent on a quadratic finite sum should satisfy ‖Wss‖≤ ‖ Wrs‖≤ ‖Wgd‖. 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 ‖Wss‖>‖Wrs‖. \bullet RS-GD inequality holds. For every symmetric Ai with (1-\frac14n2+1)I\preceq Ai\preceq I, one has ‖Wrs‖≤‖Wgd‖. The proof was found via GPT-5.5 Pro extended prompted by the author.