# Stochastic Sign Descent Methods: New Algorithms and Better Theory

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

## Built on by (most cited first, 30 of 49)

- [Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be](https://mlsanity.com/paper/2304.13960/) (2023)
- [Optimize Weight Rounding via Signed Gradient Descent for the Quantization of LLMs](https://mlsanity.com/paper/2309.05516/) (2023)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Fine-tuning Language Models over Slow Networks using Activation Compression with Guarantees](https://mlsanity.com/paper/2206.01299/) (2022)
- [TorchAO: PyTorch-Native Training-to-Serving Model Optimization](https://mlsanity.com/paper/2507.16099/) (2025)
- [Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law](https://mlsanity.com/paper/2505.19227/) (2025)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [z-SignFedAvg: A Unified Stochastic Sign-based Compression for Federated Learning](https://mlsanity.com/paper/2302.02589/) (2023)
- [Maximizing Communication Efficiency for Large-scale Training via 0/1 Adam](https://mlsanity.com/paper/2202.06009/) (2022)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (2025)
- [Convergence Rate Analysis of LION](https://mlsanity.com/paper/2411.07724/) (2024)
- [Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques](https://mlsanity.com/paper/2106.03524/) (2021)
- [FedBAT: Communication-Efficient Federated Learning via Learnable Binarization](https://mlsanity.com/paper/2408.03215/) (2024)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [SignSVRG: fixing SignSGD via variance reduction](https://mlsanity.com/paper/2305.13187/) (2023)
- [Federated Learning via Plurality Vote](https://mlsanity.com/paper/2110.02998/) (2021)
- [Shifted Compression Framework: Generalizations and Improvements](https://mlsanity.com/paper/2206.10452/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [FedLion: Faster Adaptive Federated Optimization with Fewer Communication](https://mlsanity.com/paper/2402.09941/) (2024)
- [Better Convergence Guarantees for Sign-Based Momentum Methods](https://mlsanity.com/paper/2507.12091/) (2025)
- [Sign Bit is Enough: A Learning Synchronization Framework for Multi-hop All-reduce with Ultimate Compression](https://mlsanity.com/paper/2204.06787/) (2022)
- [Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEs](https://mlsanity.com/paper/2502.17009/) (2025)
- [LoTA-QAF: Lossless Ternary Adaptation for Quantization-Aware Fine-Tuning](https://mlsanity.com/paper/2505.18724/) (2025)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Distributed Non-Convex Optimization with One-Bit Compressors on Heterogeneous Data: Efficient and Resilient Algorithms](https://mlsanity.com/paper/2210.00665/) (2022)
- [FedREP: A Byzantine-Robust, Communication-Efficient and Privacy-Preserving Framework for Federated Learning](https://mlsanity.com/paper/2303.05206/) (2023)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglers](https://mlsanity.com/paper/2403.14716/) (2024)
- [Masked Random Noise for Communication Efficient Federated Learning](https://mlsanity.com/paper/2408.03220/) (2024)

## Abstract (arXiv)

Various gradient compression schemes have been proposed to mitigate the communication cost in distributed training of large scale machine learning models. Sign-based methods, such as signSGD, have recently been gaining popularity because of their simple compression rule and connection to adaptive gradient methods, like ADAM. In this paper, we analyze sign-based methods for non-convex optimization in three key settings: (i) standard single node, (ii) parallel with shared data and (iii) distributed with partitioned data. For single machine case, we generalize the previous analysis of signSGD relying on intuitive bounds on success probabilities and allowing even biased estimators. Furthermore, we extend the analysis to parallel setting within a parameter server framework, where exponentially fast noise reduction is guaranteed with respect to number of nodes, maintaining 1-bit compression in both directions and using small mini-batch sizes. Next, we identify a fundamental issue with signSGD to converge in distributed environment. To resolve this issue, we propose a new sign-based method, em Stochastic Sign Descent with Momentum (SSDM), which converges under standard bounded variance assumption with the optimal asymptotic rate. We validate several aspects of our theoretical findings with numerical experiments.