Convergence rate analysis of distributed gradient methods for smooth optimization

We derive the convergence rate of a distributed gradient algorithm for smooth optimization in networked systems. We assume that each agent in the network has a convex cost function f_i(x), known only to agent i, and the goal is to minimize the sum Σ^N_i=1 fi(x) of all agents´ costs; such problem formulation arises in various networked applications, like, e.g., distributed inference or source localization in sensor networks. With the distributed gradient algorithm under study, each agent, at each iteration k, performs a weighted average of its own and its neighbors´ solution estimates, and performs a step in the direction of the negative of its local function´s gradient. We establish a novel result that the distributed gradient algorithm has the convergence rate O(1/k^2/3), in terms of the cost function optimality gap, under the assumption of convex f_i´s with Lipschitz continuous and bounded gradients.