Local SGD Converges Fast and Communicates Little

By Sebastian U. Stich. 2018

1,280 citations recorded by the source corpus.

Mini-batch stochastic gradient descent (SGD) is state of the art in large scale distributed training. The scheme can reach a linear speedup with respect to the number of workers, but this is rarely seen in practice as the scheme often suffers from large network delays and bandwidth limits. To overcome this communication bottleneck recent works propose to reduce the communication frequency. An algorithm of this type is local SGD that runs SGD independently in parallel on different workers and averages the sequences only once in a while. This scheme shows promising results in practice, but eluded thorough theoretical analysis. We prove concise convergence rates for local SGD on convex problems and show that it converges at the same rate as mini-batch SGD in terms of number of evaluated gradients, that is, the scheme achieves linear speedup in the number of workers and mini-batch size. The number of communication rounds can be reduced up to a factor of T^{1/2}---where T denotes the number of total steps---compared to mini-batch SGD. This also holds for asynchronous implementations. Local SGD can also be used for large scale training of deep learning models. The results shown here aim serving as a guideline to further explore the theoretical and practical aspects of local SGD in these applications.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Optimization & Training, Federated & Distributed Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Peter Richtárik
  2. Martin Jaggi
  3. Sebastian U. Stich
  4. Jakub Konecný
  5. Qiang Yang
  6. Jianyu Wang
  7. Virginia Smith
  8. Aryan Mokhtari

In Electrical and Electronic Engineering

  1. H. Vincent Poor
  2. Jianyu Wang
  3. Martin Jaggi
  4. Gauri Joshi
  5. Sebastian U. Stich
  6. Medhi Bennis
  7. Mingzhe Chen
  8. Sai Praneeth Karimireddy

In Optimization & Training

  1. Peter Richtárik
  2. Sebastian U. Stich
  3. Martin Jaggi
  4. Jakub Konecný
  5. Jianyu Wang
  6. Nicolas Loizou
  7. Gauri Joshi
  8. Aryan Mokhtari

In Federated & Distributed Learning

  1. Peter Richtárik
  2. Jianyu Wang
  3. Gauri Joshi
  4. Mehrdad Mahdavi
  5. Jakub Konecný
  6. Aryan Mokhtari
  7. Virginia Smith
  8. Zachary B. Charles

Citations in the corpus