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}\|$.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.22620
curl -X POST /api/v1/records/arxiv/2607.22620/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.22620/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'