PreprintCited by 508Stochastic Gradient Optimization TechniquesDistributed Control Multi-Agent SystemsSparse and Compressive Sensing Techniques

Sparsified SGD with Memory

Open access
Stich, Sebastian U., Cordonnier, Jean-Baptiste, Jaggi, Martin·2018·arXiv

Abstract

Huge scale machine learning problems are nowadays tackled by distributed optimization algorithms, i.e. algorithms that leverage the compute power of many devices for training. The communication overhead is a key bottleneck that hinders perfect scalability. Various recent works proposed to use quantization or sparsification techniques to reduce the amount of data that needs to be communicated, for instance by only sending the most significant entries of the stochastic gradient (top-k sparsification). Whilst such schemes showed very promising performance in practice, they have eluded theoretical analysis so far. In this work we analyze Stochastic Gradient Descent (SGD) with k-sparsification or compression (for instance top-k or random-k) and show that this scheme converges at the same rate as vanilla SGD when equipped with error compensation (keeping track of accumulated errors in memory). That is, communication can be reduced by a factor of the dimension of the problem (sometimes even more) whilst still converging at the same rate. We present numerical experiments to illustrate the theoretical findings and the better scalability for distributed applications.

Integrity signals

Registry

DataCite · 10.48550/arxiv.1809.07599

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Sparsified SGD with error compensation converges at the same rate as vanilla SGD.

    “The analysis shows that this scheme converges at the same rate as vanilla SGD when equipped with error compensation (keeping track of accumulated errors in memory).”
  • Communication can be reduced by a factor of the dimension of the problem (sometimes even more) while still converging at the same rate.

    “In other words, communication can be reduced by a factor of the dimension of the problem (sometimes even more) while still converging at the same rate.”

Cites

Still being checked.

Cited by

Sorted by citations

Authors
Stich, S. U., Cordonnier, J.-B., & Jaggi, M.
Affiliations
École Polytechnique Fédérale de Lausanne (CH)
Venue
arXiv
Publisher
arXiv
Published
2018
Volume
31
Pages
4447-4458
ISSN
2331-8422 (ISSN-L)
OpenAlex
W2890924858
Cited by
508
References
0
Citations by year
2025: 27 · 2024: 98 · 2023: 97 · 2022: 59 · 2021: 123 · 2020: 75 · 2019: 28 · 2018: 1
Type
posted content
Language
en
Open access
Locations
  • arXiv (Cornell University) (submittedVersion)
  • Infoscience (Ecole Polytechnique Fédérale de Lausanne) (submittedVersion, cc-by-nc-nd)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Control Multi-Agent Systems
  • Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
Keywords
top-k sparsification, communication compression, error compensation, distributed optimization, convergence rate, communication efficiency, memory overhead, large-scale machine learning

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review