{"id":"arxiv/2607.22620","url":"https://arxiv.org/abs/2607.22620","tags":["math.OC","cs.LG","stat.ML"],"score":0,"title":"A Resolution of the SS--RS--GD Inequalities","domain":"math.OC","source":"arxiv","authors":["Binghui Peng"],"reviews":0,"subject":"math.OC","summary":"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}\\|$.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-16","reactions":{}}