A tight bound on the stepsize of the decentralized gradient descent

Abstract

In this paper, we consider the decentralized gradinet descent (DGD) given by \begin{equation*} x_i (t+1) = \sum_{j=1}^m w_{ij} x_j (t) - α(t) \nabla f_i (x_i (t)). \end{equation*} We find a sharp range of the stepsize $\alpha (t)>0$ such that the sequence $\{x_i(t)\}$ is uniformly bounded when the aggregate cost $f$ is assumed be strongly convex with smooth local costs which might be non-convex. Precisely, we find a tight bound ${\alpha }_0>0$ such that the states of the DGD algorithm is uniformly bounded for non-increasing sequence $\alpha (t)$ satisfying $\alpha (0)\le {\alpha }_0$. The theoretical results are also verified by numerical experiments.

15 pages