Simple iteration-optimal distributed optimization

We propose a consensus-based distributed optimization algorithm for minimizing separable convex objectives. Each node only knows one component of the objective function, and so the nodes must coordinate in order to find a global minimizer. The proposed algorithm has an error rate which is no more than O(1/√T) after T iterations, matching the best possible rate. To achieve this, the algorithm requires multiple rounds of consensus per iteration, where the number of consensus rounds depends on the structure of the underlying communication topology through the spectral gap. Consequently, the amount of computation required by the proposed approach is less that of distributed optimization methods in the literature, while the total amount of communication is not increased.