Distributed Variance Reduction with Compressed Communication

Sign-based methods can 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 algorithms fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both 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. The proposed methods obtain the convergence rates of $O(\sqrt{d/K}+\sqrt{d}(a/(nK){)}^{1/3})$ for the ${\ell }_1$-norm and $O(\sqrt{a/K}+\sqrt{a}/(nK{)}^{1/3})$ for the ${\ell }_2$-norm. Here, $K$ is the iteration number, $n$ is the number of workers, $d$ is the dimension, and $a=1+\omega$, with $\omega$ denoting the relative variance of the compressor. 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\sqrt{aM}{ϵ}^{-2})$ and $O(M+a\sqrt{M}{ϵ}^{-2})$ for ${\ell }_1$ and ${\ell }_2$ expected gradient norms at most $ϵ$, matching the corresponding bounds in centralized settings.