Revisiting Distributed Sign-Based Variance Reduction
Abstract
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.
Related
- Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction
- Sign Betting for Misspecified Regression: Variance Adaptivity and Optimal Approximation
- Rank-one variance inflation in polynomial estimation of signal parameters with a sign-preserving fractional-power basis
- Variance Reduction Note 3: The Convergence of PAGE
- Variance Reduction Note 2: The Convergence of SPIDER
BibTeX
@misc{jiang2026revisiting,
title = {{Revisiting Distributed Sign-Based Variance Reduction}},
author = {Wei Jiang and Zechao Li and Lijun Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18656},
eprint = {2609.18656},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18656},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Revisiting Distributed Sign-Based Variance Reduction
AU - Wei Jiang
AU - Zechao Li
AU - Lijun Zhang
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18656
UR - https://arxiv.org/abs/2609.18656
AB - 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.
ER -