A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent

By Shi Pu, Alexander Olshevsky, Ioannis Ch. Paschalidis. 2019

78 citations recorded by the source corpus.

This article is concerned with minimizing the average of $n$ cost functions over a network, in which agents may communicate and exchange information with each other. We consider the setting where only noisy gradient information is available. To solve the problem, we study the distributed stochastic gradient descent (DSGD) method and perform a nonasymptotic convergence analysis. For strongly convex and smooth objective functions, in expectation, DSGD asymptotically achieves the optimal network-independent convergence rate compared to centralized stochastic gradient descent. Our main contribution is to characterize the transient time needed for DSGD to approach the asymptotic convergence rate. Moreover, we construct a “hard” optimization problem that proves the sharpness of the obtained result. Numerical experiments demonstrate the tightness of the theoretical results.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

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. Shi Pu
  2. Angelia Nedić
  3. Alexander Olshevsky
  4. Wei Shi
  5. Michael G. Rabbat
  6. Ali H. Sayed
  7. Qing Ling
  8. Wotao Yin

In Computational Mechanics

  1. Shi Pu
  2. Angelia Nedić
  3. Alexander Olshevsky
  4. Wei Shi
  5. Qing Ling
  6. Wotao Yin
  7. Mingyi Hong
  8. Ali H. Sayed

In Computer Networks and Communications

  1. Shi Pu
  2. Angelia Nedić
  3. Alexander Olshevsky
  4. Ali H. Sayed
  5. Wei Shi
  6. Michael G. Rabbat
  7. Qing Ling
  8. Wotao Yin

Citations in the corpus