# Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 43 references that are in the map.
- First posted on arXiv 1 Jun 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [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)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [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)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Stochastic Sign Descent Methods: New Algorithms and Better Theory](https://mlsanity.com/paper/1905.12938/) (2019)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [Stochastic-Sign SGD for Federated Learning with Theoretical Guarantees](https://mlsanity.com/paper/2002.10940/) (2020)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms](https://mlsanity.com/paper/1906.01736/) (2019)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (2019)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization](https://mlsanity.com/paper/2207.08540/) (2022)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [SignSVRG: fixing SignSGD via variance reduction](https://mlsanity.com/paper/2305.13187/) (2023)
- [Learning Unnormalized Statistical Models via Compositional Optimization](https://mlsanity.com/paper/2306.07485/) (2023)
- [Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/2310.15976/) (2023)

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

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions](https://mlsanity.com/paper/2406.01959/) (2024)
- [Better Convergence Guarantees for Sign-Based Momentum Methods](https://mlsanity.com/paper/2507.12091/) (2025)
- [Convergence Analysis of the Lion Optimizer in Centralized and Distributed Settings](https://mlsanity.com/paper/2508.12327/) (2025)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimization](https://mlsanity.com/paper/2410.14054/) (2024)
- [Error Feedback under (L0,L1)-Smoothness: Normalization and Momentum](https://mlsanity.com/paper/2410.16871/) (2024)
- [Stochastic Approximation with Block Coordinate Optimal Stepsizes](https://mlsanity.com/paper/2507.08963/) (2025)
- [When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds](https://mlsanity.com/paper/2605.06615/) (2026)
- [Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications](https://mlsanity.com/paper/2604.09276/) (2026)
- [DeToNATION: Decoupled Torch Network-Aware Training on Interlinked Online Nodes](https://mlsanity.com/paper/2502.06728/) (2025)
- [Mitigating Heterogeneity-Induced Drift in Hierarchical Sign-Based Federated Learning](https://mlsanity.com/paper/2602.02355/) (2026)
- [Revisiting Distributed Sign-Based Variance Reduction](https://mlsanity.com/paper/2609.18656/) (2026)

## Abstract (arXiv)

Sign stochastic gradient descent (signSGD) is a communication-efficient method that transmits only the sign of stochastic gradients for parameter updating. Existing literature has demonstrated that signSGD can achieve a convergence rate of O(d1/2T-1/4), where d represents the dimension and T is the iteration number. In this paper, we improve this convergence rate to O(d1/2T-1/3) by introducing the Sign-based Stochastic Variance Reduction (SSVR) method, which employs variance reduction estimators to track gradients and leverages their signs to update. For finite-sum problems, our method can be further enhanced to achieve a convergence rate of O(m1/4d1/2T-1/2), where m denotes the number of component functions. Furthermore, we investigate the heterogeneous majority vote in distributed settings and introduce two novel algorithms that attain improved convergence rates of O(d1/2T-1/2 + dn-1/2) and O(d1/4T-1/4) respectively, outperforming the previous results of O(dT-1/4 + dn-1/2) and O(d3/8T-1/8), where n represents the number of nodes. Numerical experiments across different tasks validate the effectiveness of our proposed methods.