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

Researchers provide theoretical proof that sign-based optimization algorithms like SignSGD outperform standard SGD under specific conditions involving ℓ1-norm stationarity and sparse noise, with complexity improvements scaling by problem dimension d. The analysis bridges theory and practice by demonstrating these advantages during GPT-2 pretraining, explaining why sign-based methods succeed in large language model training despite lacking previous theoretical justification.

This research addresses a fundamental gap in machine learning theory: why sign-based optimizers like SignSGD and Muon empirically outperform vanilla SGD in training large foundation models, despite lacking theoretical justification. The breakthrough involves reframing the problem geometry to use ℓ1-norm stationarity and ℓ∞-smoothness rather than standard ℓ2-norm assumptions, which better capture coordinate-wise behavior of signed updates. Under these conditions, the researchers derive matched upper and lower complexity bounds showing SignSGD achieves d-factor improvements under sparse noise, where d represents problem dimensionality.

The theoretical framework carries significant implications for optimization algorithm design. Prior analysis suggested SGD was minimax optimal under standard conditions, making sign-based improvements impossible. By identifying the specific problem geometry where sign operators excel—particularly sparse, coordinate-aligned noise patterns common in neural network training—this work explains real-world performance gaps. The extension to matrix operations through Muon optimizer validation demonstrates the theory generalizes beyond vector-space algorithms.

For machine learning practitioners and researchers, this work provides both legitimacy and guidance. Sign-based methods aren't just empirical curiosities but provably superior under identifiable conditions. The validation on 124M parameter GPT-2 models bridges theory and practice, suggesting these methods will increasingly dominate foundation model training pipelines. Organizations developing large language models may prioritize sign-based optimizers based on this theoretical backing. The research signals that optimization algorithm development remains an active frontier with practical performance gains still available, encouraging further investigation into problem-specific geometric frameworks rather than universal optimization theory.

• →SignSGD achieves d-factor complexity improvement over SGD under sparse noise conditions when using ℓ1-norm stationarity metrics
• →Sign-based methods outperform vanilla SGD specifically when problem geometry features coordinate-wise noise rather than isotropic perturbations
• →Theoretical advantages validated on GPT-2 pretraining align with empirical observations of sign-based optimizer dominance in foundation models
• →Matrix extension through Muon optimizer preserves optimal d-dimensional scaling, generalizing sign-operator benefits beyond vector algorithms
• →Existing minimax optimality proofs for SGD using ℓ2-norms don't prevent sign-based improvements under alternative geometric frameworks