技术摘要：SS–RS–GD 不等式的解析

问题陈述

本文针对 Yun, Sra, 和 Jadbabaie (COLT 2021) 提出的一个关于应用于有限和二次目标（finite-sum quadratic objectives）的三种优化方案收敛速率的猜想进行了研究。这三种方案分别是：

1. 梯度下降 (GD)： 在每一步都使用全量批次（full batch）。
2. 随机洗牌 (RS) SGD： 每个 epoch 抽取一个新的随机排列组合。
3. 单次洗牌 (SS) SGD： 在初始阶段抽取一个单一的排列，并在所有 $K$ 个 epoch 中重复使用该排列。

对于良态（well-conditioned）对称矩阵 $A_1, \dots, A_n$，作者定义了编码三种方案在 $K$ 个 epoch 后期望迭代值的算子 $W_{SS}$、$W_{RS}$ 和 $W_{GD}$。该猜想认为，对于充分良态的矩阵（具体而言是满足 $(1-\eta)I \preceq A_i \preceq I$），这些算子的谱范数满足以下排序：
$$\|W_{SS}\| \leq \|W_{RS}\| \leq \|W_{GD}\|$$
这种排序意味着 Single-Shuffle 最有效，其次是 Random-Shuffle，而 Gradient Descent 的效率最低（或者说在误差算子的谱半径方面收敛最慢）。

研究方法

本文结合了显式反例构造和谱分析来解决该猜想。

1. 对 SS–RS 不等式的反驳

为了推翻第一个不等式 ($\|W_{SS}\| \leq \|W_{RS}\|$），作者构造了一个特定的反例：

• 维度与参数： 他们固定 $n=3$ 个分量，$K=2$ 个 epoch，且维度 $d=4$。
• 矩阵构造： 他们基于三个单位向量在 $\mathbb{R}^2$ 中定义了秩一投影算子 $P_i$。随后，他们构造了矩阵 $B_i = qI_2 + (1-q)P_i$，并定义最终矩阵为张量积 $A_i = B_i \otimes B_i \in \mathbb{R}^{4\times 4}$。
• 条件性： 通过选择一个足够接近 1 的参数 $q$，可以使 $A_i$ 的条件数任意接近 1，从而满足猜想中“良态”的假设（对于任何提出的常数 $\eta$ 均成立）。
• 谱分析： 作者推导出了 $W_{SS}$ 和 $W_{RS}$ 的特征值关于 $q$ 的精确多项式表达式。他们证明了在靠近 1 的特定 $q$ 范围内，$W_{SS}$ 的最大特征值严格大于 $W_{RS}$ 的最大特征值。

2. 对 RS–GD 不等式的证明

为了证明第二个不等式 ($\|W_{RS}\| \leq \|W_{GD}\|$），作者利用将其归约为单 epoch 界限以及近恒等矩阵分析的方法：

• 归约： 由于 $W_{RS} = R^K$ 且 $W_{GD} = G^{nK}$（其中 $R$ 是排列乘积的平均值，$G$ 是矩阵的平均值），且考虑到这些算子在偶次方下的对称性和正定性，问题归约为证明 $\|R\| \leq \|G\|^n$。
• 归一化： 矩阵经过归一化处理，使得 $C_i = \rho^{-1}A_i = I + X_i$，其中 $\rho = \|G\|$。条件 $(1-\eta)I \preceq A_i \preceq I$ 转化为对扰动矩阵 $X_i$ 的约束。
• 展开与界定： 算子 $\tilde{R}$（$R$ 的归一化版本）被展开为包含 $X_i$ 乘积项的求和式。作者使用 Cauchy-Schwarz 不等式并利用 $\|X_i\|$ 的微小性来限制高阶项的谱范数。
• 条件性常数： 他们确立了如果条件数由 $\eta = \frac{1}{4n^2+1}$ 限制，则洗牌乘积算子的谱范数仍保持在恒等矩阵之下，从而证明了 $\|R\| \leq \rho^n$。

主要贡献与结果

1. 对 SS–RS 不等式的反驳 (定理 2)

本文确定地证明了猜想 $\|W_{SS}\| \leq \|W_{RS}\|$ 是错误的。

• 结果： 存在对称正定矩阵 $A_1, A_2, A_3$，其条件数可以任意接近 1，使得 $\|W_{SS}\| > \|W_{RS}\|$。
• 启示： 在良态情形下，认为 Single-Shuffle SGD 严格优于 Random-Shuffle SGD 的直觉并不具有普适性，即使是在极小的维度（$n=3, d=4$）下也是如此。

2. 对 RS–GD 不等式的验证 (定理 3)

本文证明了在特定的条件约束下，猜想 $\|W_{RS}\| \leq \|W_{GD}\|$ 成立。

• 结果： 对于任何 $n \geq 2, K \geq 1, d \geq 1$，如果对称矩阵满足 $(1 - \frac{1}{4n^2+1})I \preceq A_i \preceq I$，则 $\|W_{RS}\| \leq \|W_{GD}\|$。
• 意义： 这证实了只要问题足够良态，Random-Shuffle SGD 的收敛速度就等于或快于 Gradient Descent。常数 $\eta = \frac{1}{4n^2+1}$ 与维度 $d$ 无关，且独立于 epoch 数量 $K$。

意义与主张

本文声称解决了关于这些优化方案排序顺序的 COLT 开放性问题。

• 猜想的解决： 作者证明了所提议的排序仅部分正确。虽然在良态问题下 RS–GD 关系成立，但 SS–RS 关系即使在最理想（接近恒等矩阵）的条件下也会失效。
• AI 的角色： 作者明确指出，RS–GD 不等式核心证明思路是由 AI 模型 (GPT-5.5 Pro) 生成的，而反例构造及最终手稿的组装由作者及另一款 AI 工具 (Claude Code) 完成。作者负责验证证明过程并润色文本。
• 局限性： 作者指出，RS–GD 不等式中的常数 $\eta$ 可能不是最优的，因为其证明依赖于几何级数界的松弛度。然而，它建立了一个有效的条件半径。相反，对于 SS–RS 不等式，不存在任何正的条件常数能挽救该猜想，因为该反例在任意小的 $\eta$ 下均成立。

这项工作澄清了有限和优化（finite-sum optimization）的理论图景，表明虽然 Random-Shuffle SGD 在温和条件下保持着相对于 Gradient Descent 的优势，但在期望迭代值的谱半径方面，它并不一定能支配 Single-Shuffle SGD。