Research map / Learning theory and algorithms / Sample complexity

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

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Statistical-query lower bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives matching l1-norm upper and lower bounds for SignSGD under l_inf-smoothness and separable noise, shows SignSGD can beat SGD's lower bound by up to a factor d under sparse noise, and extends the lower bound to Muon.

Problem

When and why sign-based optimizers (SignSGD, Muon) provably outperform SGD in stochastic non-convex optimization, given that SGD is minimax optimal under standard l2 smoothness, variance, and stationarity assumptions.

Approach

Shifts to an l_inf-smoothness, separable coordinate-wise noise model, and l1-norm stationarity; proves tight SignSGD bounds and an SGD lower bound in this geometry, comparing them via a noise density measure phi(sigma)=||sigma||_1^2/(d||sigma||_2^2) to show SignSGD wins under sparse noise. Also transfers the lower bound to Muon via a reduction to SignSGD.

Key results

• SignSGD upper bound Theta(sqrt(L_inf Delta/N) + (||sigma||_1^2 L_inf Delta/N)^{1/4}) matched by a lower bound; SGD lower bound Omega(sqrt(d L_inf Delta/T) + (d ||sigma||_2^2 L_inf Delta/T)^{1/4}), so SignSGD can be up to d times better under sparse noise.
• On nanoGPT-124M pretraining on C4, SignSGD converges substantially faster than SGD, which plateaus early.
• In nanoGPT training the noise density phi falls to about 0.03, while ResNet-20 noise density rises to about 0.7.

Surprising findings

• SGD's loss plateaus early in nanoGPT training while SignSGD keeps converging, attributed to increasingly sparse gradient noise in LLMs.
• The SGD lower-bound proof sketch invokes a coordinate-wise lower bound from prior work and its stochastic term allocation is described as adversarial; the Muon lower bound is stated with O-notation in the theorem although the text says it is a lower bound.

Limitations

• Advantage shown only in the sparse-noise / l_inf-smooth regime; under dense noise SignSGD and SGD are comparable.
• Empirical validation limited to a 124M GPT-2 model and toy quadratics; no large-scale or Muon experiments reported in the excerpt.
• Lower bounds are worst-case constructions; the Muon lower bound relies on a reduction that assumes a specific diagonal-embedded matrix objective.

Experimental setup

Datasets: C4 CIFAR-10

Benchmarks: C4 validation loss (nanoGPT pretraining) CIFAR-10 (ResNet-20 noise density)

Metrics: l1-norm gradient stationarity bound training and validation loss noise density phi(sigma)

Baselines: SGD AdamW Signum

Builds on: SignSGD Muon AdaGrad lower bound under l1 stationarity (Bernstein/Kunstner-style analysis) Arjevani et al. stochastic lower bounds

Closest papers by meaning

• Exact risk curves of signSGD in High-Dimensions: quantifying preconditioning and noise-compression effects (ICML 2025 · similarity 0.91)
• Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction (NeurIPS 2024 · similarity 0.91)
• Phases of Muon: When Muon Eclipses SignSGD (NeurIPS 2026 · similarity 0.90)
• Sign-Based Optimizers Are Effective Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.90)
• Investigating the Role of Weight Decay in Enhancing Nonconvex SGD (CVPR 2025 · similarity 0.88)
• Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.87)