# Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness

arXiv: https://arxiv.org/abs/2502.07923 · HTML: https://mlsanity.com/paper/2502.07923/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 78 references that are in the map.
- First posted on arXiv 11 Feb 2025.

## Builds on (most cited first, 30 of 58)

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale](https://mlsanity.com/paper/2406.17557/) (2024)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [ReLoRA: High-Rank Training Through Low-Rank Updates](https://mlsanity.com/paper/2307.05695/) (2023)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)

## Built on by (most cited first, 13 of 13)

- [Generalized Gradient Norm Clipping & Non-Euclidean (L0,L1)-Smoothness](https://mlsanity.com/paper/2506.01913/) (2025)
- [Enhancing LLM Training via Spectral Clipping](https://mlsanity.com/paper/2603.14315/) (2026)
- [On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approach](https://mlsanity.com/paper/2506.00181/) (2025)
- [Softsign: Smooth Sign in Your Optimizer For Better Parameter Heterogeneity Handling](https://mlsanity.com/paper/2605.31371/) (2026)
- [Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrization](https://mlsanity.com/paper/2507.09093/) (2025)
- [When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds](https://mlsanity.com/paper/2605.06615/) (2026)
- [LionMuon: Alternating Spectral and Sign Descent for Efficient Training](https://mlsanity.com/paper/2605.19811/) (2026)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)
- [Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises](https://mlsanity.com/paper/2507.13283/) (2025)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)
- [Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives](https://mlsanity.com/paper/2605.11850/) (2026)
- [LionMuon: Alternating Spectral and Sign Descent for Efficient Training](https://mlsanity.com/paper/2609.35297/) (2026)

## Abstract (arXiv)

In recent years, non-convex optimization problems are more often described by generalized (L0, L1)-smoothness assumption rather than standard one. Meanwhile, severely corrupted data used in these problems has increased the demand for methods capable of handling heavy-tailed noises, i.e., noises with bounded kappa-th moment. Motivated by these real-world trends and challenges, we explore sign-based methods in this setup and demonstrate their effectiveness in comparison with other popular solutions like clipping or normalization. In theory, we prove the first-known high probability convergence bounds under (L0, L1)-smoothness and heavy-tailed noises with mild parameter dependencies. In the case of standard smoothness, these bounds are novel for sign-based methods as well. In particular, SignSGD with batching achieves sample complexity tildeOleft(left(fracDelta L0dvarepsilon2 + fracDelta L1d^frac32varepsilonright)left[1 + left(fracσvarepsilonright)^frackappakappa-1right]right), kappa ∈ (1,2]. Under the assumption of symmetric noises, SignSGD with Majority Voting can robustly work on the whole range of kappa ∈ (0,2] with complexity tildeOleft(left(fracDelta L0dvarepsilon2 + fracDelta L1d^frac32varepsilonright)left[frac1kappa2 + fracσ2varepsilon2right]right). We also obtain results for parameter-agnostic setups, Polyak-Lojasiewicz functions and momentum-based methods (in expectation). Our theoretical findings are supported by the superior performance of sign-based methods in training Large Language Models compared to clipping and normalization.