Research map / Optimization / Optimizers

Sign-Based Optimizers Are Effective Under Heavy-Tailed Noise

NeurIPS 2026 · Optimization › Optimizers · approach: Memory-efficient LLM optimizers · 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.

Proves convergence rates for sign-based optimizers (SignSGD, Lion, Muon, Muonlight) under a generalized heavy-tailed gradient noise model and generalized smoothness, with new ℓ1 and nuclear-norm martingale concentration inequalities.

Problem

Explaining theoretically why sign-based optimizers like Lion and Muon outperform AdamW for LLM training, under heavy-tailed gradient noise where only a finite p-th moment (p in (1,2]) is assumed.

Approach

Introduces a generalized heavy-tailed noise condition whose p-th moment scales with the gradient norm, and generalized (L0,L1)-type smoothness; shows sign operators act as non-Euclidean normalized gradient steps and proves O(T^{-(p-1)/(3p-2)}) rates for SignSGD, Lion, Muon, Muonlight via new ℓ1 and nuclear-norm vector/matrix martingale concentration inequalities.

Key results

• Convergence rate O(T^{-(p-1)/(3p-2)}) established for SignSGD, Lion, Muon and Muonlight under generalized heavy-tailed noise, matching or surpassing prior best-known bounds.
• In nanoGPT pretraining on C4, Muon achieves 1.32x and Lion 1.07x speedup over AdamW.
• Complexity of sign-based methods can improve over normalized SGD by up to a factor of d (vector) or min{m,n} (matrix) in favorable geometry, per the authors' analysis.

Surprising findings

• Classical heavy-tailed noise model (sigma_1=0) can fail to hold even on linear regression, motivating the gradient-dependent noise model.

Limitations

• Rates are derived under generalized smoothness and noise assumptions; the empirical section is limited to GPT-2/nanoGPT pretraining on C4.
• Muon analysis assumes exact Newton-Schulz (zero numerical error); inexact case only sketched via external result.

Experimental setup

Datasets: C4

Benchmarks: C4

Metrics: training loss validation loss validation accuracy speedup ratio over AdamW

Baselines: AdamW NSGD Adam AdaGrad

Builds on: Lion Muon SignSGD Clipped SGD (L0,L1)-smoothness

Closest papers by meaning

• When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds (NeurIPS 2026 · similarity 0.90)
• Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf’s Law (NeurIPS 2025 · similarity 0.89)
• Adaptive Methods through the Lens of SDEs: Theoretical Insights on the Role of Noise (ICLR 2025 · similarity 0.87)
• AlphaDecay: Module-wise Weight Decay for Heavy-Tailed Balancing in LLMs (NeurIPS 2025 · similarity 0.87)
• Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction (NeurIPS 2024 · similarity 0.87)
• Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)