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

This article is concerned with minimizing the average of is 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.

Automated summary

This article focuses on minimizing the average of cost functions over a network, where agents can communicate and exchange information. The article studies the distributed stochastic gradient descent (DSGD) method when only noisy gradient information is available, and performs a nonasymptotic convergence analysis. The main contribution of the article is to characterize the transient time needed for DSGD to approach the asymptotic convergence rate, and construct a hard optimization problem to prove the sharpness of the obtained result. Numerical experiments demonstrate the tightness of the theoretical results.