When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds

📄 arXiv: 2605.06615v1 📥 PDF

作者: Hongyi Tao, Dingzhi Yu, Lijun Zhang

分类: cs.LG, cs.AI, cs.CL, math.OC

发布日期: 2026-05-07

备注: Code is available at https://github.com/Dingzhen230/SignSGD_Outperforms_SGD

💡 一句话要点

基于ℓ₁范数下界理论，揭示SignSGD优于SGD的条件与原因

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: SignSGD 优化算法 ℓ₁范数 稀疏噪声 理论分析 深度学习 GPT-2

📋 核心要点

  1. 现有理论无法解释SignSGD等符号优化器在训练大型模型时优于SGD的现象，因为SGD在标准条件下已被证明是最优的。
  2. 论文采用ℓ₁范数平稳性、ℓ∞-光滑性和可分离噪声模型，分析SignSGD的性能，揭示其在特定问题几何下的优势。
  3. 理论分析表明，SignSGD在稀疏噪声下复杂度可降低d倍，且在GPT-2预训练中验证了SignSGD的快速收敛。

📝 摘要（中文）

SignSGD和Muon等基于符号的优化算法在训练大型基础模型时表现出色，但对其优于vanilla SGD的理论理解尚不足。传统的光滑性和有限方差条件下的SGD在ℓ₂范数下是最优的，无法解释符号方法的优势。本文利用ℓ₁范数平稳性、ℓ∞-光滑性和可分离噪声模型分析了基于符号的优化器，更好地捕捉了符号更新的坐标性质。在此框架下，推导了SignSGD的匹配上下界，明确了SignSGD优于SGD的问题类别。通过比较SignSGD的上界和SGD的下界，表明SignSGD在稀疏噪声下可有效降低d倍的复杂度（d为维度）。进一步将该框架扩展到矩阵域，为Muon优化器提供了等价的最优下界，证明了将符号算子扩展到矩阵域保留了维度上的最优缩放。最后，将理论与实践结合，验证了SignSGD的理论优势准确预测了其在124M参数GPT-2模型预训练中的更快收敛。

🔬 方法详解

问题定义：论文旨在解决SignSGD等基于符号的优化算法，在何种条件下以及为何能够超越传统SGD优化算法的问题。现有理论分析主要基于光滑性和有限方差假设，并使用ℓ₂范数来衡量收敛性，这使得SGD在这些条件下已经是最优的，无法解释SignSGD的优越性。因此，需要新的理论框架来解释SignSGD的有效性。

核心思路：论文的核心思路是改变对问题几何的假设，采用ℓ₁范数平稳性、ℓ∞-光滑性和可分离噪声模型。这种新的视角更适合捕捉SignSGD的坐标性质，即SignSGD对梯度的每个分量进行符号化处理。通过这种方式，论文能够推导出SignSGD的上下界，并与SGD的下界进行比较，从而揭示SignSGD在特定条件下的优势。

技术框架：论文的技术框架主要包括以下几个部分：首先，定义了新的问题几何，包括ℓ₁范数平稳性、ℓ∞-光滑性和可分离噪声模型。其次，推导了SignSGD在这种问题几何下的上下界。然后，推导了SGD在相同问题几何下的下界。接着，比较SignSGD的上界和SGD的下界，从而确定SignSGD优于SGD的条件。最后，将理论结果扩展到矩阵域，并应用于Muon优化器。

关键创新：论文最重要的技术创新在于改变了对问题几何的假设，从传统的基于光滑性和有限方差的假设，转变为基于ℓ₁范数平稳性、ℓ∞-光滑性和可分离噪声模型的假设。这种新的假设更适合捕捉SignSGD的坐标性质，从而能够更好地分析SignSGD的性能。与现有方法的本质区别在于，现有方法无法解释SignSGD的优越性，而论文提出的方法能够揭示SignSGD在特定条件下的优势。

关键设计：论文的关键设计包括：1) 采用ℓ₁范数作为收敛性的衡量标准，这与SignSGD的坐标性质相符。2) 假设噪声是可分离的，即噪声在每个坐标上是独立的。3) 将理论结果扩展到矩阵域，从而能够分析Muon优化器的性能。没有特别提到损失函数和网络结构，因为论文主要关注优化算法的理论分析。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文通过理论分析证明，在稀疏噪声条件下，SignSGD的复杂度可以比SGD降低d倍（d为维度）。此外，实验结果表明，SignSGD在124M参数的GPT-2模型预训练中表现出更快的收敛速度，验证了理论分析的有效性。这些结果表明，SignSGD在特定条件下具有显著的优势。

🎯 应用场景

该研究成果可应用于大规模机器学习模型的训练，尤其是在数据维度较高且噪声具有稀疏性的场景下。通过选择合适的优化算法（如SignSGD），可以显著提高训练效率，降低计算成本。该研究对于深度学习、自然语言处理等领域具有重要的实际价值，有助于开发更高效的训练方法，加速模型迭代。

📄 摘要（原文）

Sign-based optimization algorithms, such as SignSGD and Muon, have garnered significant attention for their remarkable performance in training large foundation models. Despite this empirical success, we still lack a theoretical understanding of when and why these sign-based methods outperform vanilla SGD. The core obstacle is that under standard smoothness and finite variance conditions, SGD is known to be minimax optimal for finding stationary points measured by $\ell_2$-norms, thereby fundamentally precluding any complexity gains for sign-based methods in standard settings. To overcome this barrier, we analyze sign-based optimizers leveraging $\ell_1$-norm stationarity, $\ell_\infty$-smoothness, and a separable noise model, which can better capture the coordinate-wise nature of signed updates. Under this distinct problem geometry, we derive matched upper and lower bounds for SignSGD and explicitly characterize the problem class in which SignSGD provably dominates SGD. Specifically, we compare the \emph{upper bound of SignSGD} with the \emph{lower bound of SGD}, illustrating that SignSGD effectively reduces the complexity by a factor of $d$ under \emph{sparse noise}, where $d$ is the problem dimension. Furthermore, we elevate this framework to the matrix domain, providing an equivalent optimal lower bound for the Muon optimizer, proving that extending the sign operator to matrices preserves this optimal scaling with dimensionality. Finally, we bridge our theoretical bounds to practice, demonstrating that the theoretical superiority of SignSGD accurately predicts its faster convergence during the pretraining of a 124M parameter GPT-2 model.