# Revisiting Distributed Sign-Based Variance Reduction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 7 references that are in the map.
- First posted on arXiv 16 Sep 2026.

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

- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Stochastic Sign Descent Methods: New Algorithms and Better Theory](https://mlsanity.com/paper/1905.12938/) (2019)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [Better Convergence Guarantees for Sign-Based Momentum Methods](https://mlsanity.com/paper/2507.12091/) (2025)

## Abstract (arXiv)

Sign-based methods reduce communication costs in distributed environments, but aggregating local signs can introduce bias when data are heterogeneous. As a result, existing sign-based variance reduction methods fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both nonconvex stochastic and finite-sum optimization. We first give a counterexample showing that majority voting can fail to approach stationary points even with exact local gradients. Motivated by this limitation, we propose tracking the global gradient at the server through unbiased compression of recursive gradient increments. As a result, we can obtain the convergence rates of O(√d/K+√ d (a/(nK))1/3) for the ℓ1-norm and O(√a/K+√ a/(nK)1/3) for the ℓ2-norm. Here, K is the iteration number, n is the number of workers, d is the dimension, and a=1+ω, with ω denoting the compressor's relative variance. For finite-sum problems with M components, we combine periodic exact gradient refreshes with compressed component-gradient differences. The resulting total sample complexities are O(M+d√aMε-2) and O(M+a√ M epsilon-2) for ℓ1 and ℓ2 gradient norms at most ε, matching the corresponding bounds in centralized settings.