SignSGD 何时以及为何优于 SGD：基于 $\ell_1$-norm 下界的理论研究

基于符号的优化算法，例如 SignSGD 和 Muon，因其在训练大型基础模型方面的卓越性能而受到广泛关注。尽管取得了实证上的成功，但我们仍然缺乏对这些基于符号的方法何时以及为何优于普通 SGD 的理论理解。核心障碍是，在标准平滑度和有限方差条件下，已知 SGD 对于寻找由 $\ell_2$-范数测量的平稳点而言是极小极大最优，从而从根本上排除了标准设置中基于符号的方法的任何复杂性增益。为了克服这一障碍，我们分析了基于符号的优化器，利用 $\ell_1$-norm 平稳性、$\ell_\infty$-平滑性和可分离噪声模型，可以更好地捕获签名更新的坐标性质。在这种独特的问题几何结构下，我们推导了 SignSGD 的匹配上限和下限，并明确描述了 SignSGD 可证明主导 SGD 的问题类别。具体来说，我们将 \emph{SignSGD 的上界}与 \emph{SGD 的下界}进行比较，说明 SignSGD 在 \emph{稀疏噪声} 下有效地将复杂度降低了 $d$，其中 $d$ 是问题维度。此外，我们将这个框架提升到矩阵域，为 Muon 优化器提供等效的最佳下界，证明将符号运算符扩展到矩阵可以保留这种最佳的维度缩放。最后，我们将理论界限与实践联系起来，证明 SignSGD 的理论优越性可以准确预测其在 124M 参数 GPT-2 模型预训练期间的更快收敛。