Accelerated Distributed Nesterov Gradient Descent

This paper considers the distributed optimization problem over a network, where the objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. We develop an accelerated distributed Nesterov gradient descent method. When the objective function is convex and <inline-formula><tex-math notation="LaTeX">$L$</tex-math></inline-formula>-smooth, we show that it achieves a <inline-formula><tex-math notation="LaTeX">$O(\frac{1}{t^{1.4-\epsilon }})$</tex-math></inline-formula> convergence rate for all <inline-formula><tex-math notation="LaTeX">$\epsilon \in (0,1.4)$</tex-math></inline-formula>. We also show the convergence rate can be improved to <inline-formula><tex-math notation="LaTeX">$O(\frac{1}{t^2})$</tex-math></inline-formula> if the objective function is a composition of a linear map and a strongly convex and smooth function. When the objective function is <inline-formula><tex-math notation="LaTeX">$\mu$</tex-math></inline-formula>-strongly convex and <inline-formula><tex-math notation="LaTeX">$L$</tex-math></inline-formula>-smooth, we show that it achieves a linear convergence rate of <inline-formula><tex-math notation="LaTeX">$O([ 1 - C (\frac{\mu }{L})^{5/7} ]^t)$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$\frac{L}{\mu }$</tex-math></inline-formula> is the condition number of the objective, and <inline-formula><tex-math notation="LaTeX">$C>0$</tex-math></inline-formula> is some constant that does not depend on <inline-formula><tex-math notation="LaTeX">$\frac{L}{\mu }$</tex-math></inline-formula>.