破解了随机洗牌与梯度下降收敛性比较的长期未解之谜。
A Resolution of the SS--RS--GD Inequalities
- 通过构造反例推翻了单次洗牌优于随机重洗的猜想。
- 证明了随机重洗在条件数接近1时始终优于梯度下降。
- 借助AI辅助推理，首次严格验证了关键不等式成立。
Yun、Sra 和 Jadbabaie（COLT 2021，开放问题）提出假设：对于条件良好的对称矩阵 $A_1,\dots,A_n$，编码单次洗牌随机梯度下降（SS-SGD）、随机重洗随机梯度下降（RS-SGD）和梯度下降（GD）在二次有限和优化中期望迭代的算子 $W_{ss}$、$W_{rs}$、$W_{gd}$ 应满足 $\|W_{ss}\| \le \|W_{rs}\| \le \|W_{gd}\|$。本文解决该猜想：（1）单次洗牌-随机重洗不等式不成立——当 $n=3$、$K=2$、$d=4$ 时，存在正定矩阵，其条件数可任意接近1，但 $\|W_{ss}\| > \|W_{rs}\|$；（2）随机重洗-梯度下降不等式成立——对所有满足 $\left(1-\frac{1}{4n^2+1}\right)I \preceq A_i \preceq I$ 的对称矩阵 $A_i$，均有 $\|W_{rs}\| \le \|W_{gd}\|$。证明过程由作者借助 GPT-5.5 Pro 扩展提示获得。
原文摘要 · Abstract (English)
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}\|$. $\bullet$ RS-GD inequality holds. For every symmetric $A_i$ with $\bigl(1-\frac1{4n^2+1}\bigr)I\preceq A_i\preceq I$, one has $\|W_{rs}\|\le\|W_{gd}\|$. The proof was found via GPT-5.5 Pro extended prompted by the author.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。