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 (Acc-DNGD) method. When the objective function is convex and L-smooth, we show that it achieves a O(frac1t1.4-ε) convergence rate for all ε∈(0,1.4). We also show the convergence rate can be improved to O(frac1t2) if the objective function is a composition of a linear map and a strongly-convex and smooth function. When the objective function is μ-strongly convex and L-smooth, we show that it achieves a linear convergence rate of O([ 1 - C (fracμL)5/7 ]t), where fracLμ is the condition number of the objective, and C>0 is some constant that does not depend on fracLμ.