Metraipolis › archive › dc_823a035aaedf
Revisiting Distributed Sign-Based Variance Reduction — arXiv:2609.18656
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18656
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T15:04:52.033Z
- SHA-256 of the archived text
c7ab485c9f22f16c0913435e29dc9bfc6bcbe0d2b880c4780e897a849047196d- Stable URL of this page
https://metraipolis.com/documento/dc_823a035aaedf
How to cite
Revisiting Distributed Sign-Based Variance Reduction — arXiv:2609.18656 — arXiv (en), https://arxiv.org/abs/2609.18656 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_823a035aaedf (Metraipolis archive dc_823a035aaedf, sha256 c7ab485c9f22f16c0913435e29dc9bfc6bcbe0d2b880c4780e897a849047196d)
BibTeX
@misc{dc823a035aaedf,
title = {Revisiting Distributed Sign-Based Variance Reduction — arXiv:2609.18656},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18656},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_823a035aaedf; sha256 c7ab485c9f22f16c0913435e29dc9bfc6bcbe0d2b880c4780e897a849047196d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18656. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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(\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 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\sqrt{aM}\epsilon^{-2})$ and $O(M+a\sqrt M\ epsilon^{-2})$ for $\ell_1$ and $\ell_2$ gradient norms at most $\epsilon$, matching the corresponding bounds in centralized settings.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-17 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Optimization and Control (math.OC); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.18656 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T14:08:19.144Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).