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.
