Title: Optimal Algorithms for Distributed Optimization,
Abstract: In this paper, we study the optimal convergence rate for distributed convex
optimization problems in networks. We model the communication restrictions
imposed by the network as a set of affine constraints and provide optimal
complexity bounds for four different setups, namely: the function $F(\xb)
\triangleq \sum_{i=1}^{m}f_i(\xb)$ is strongly convex and smooth, either
strongly convex or smooth or just convex. Our results show that Nesterov's
accelerated gradient descent on the dual problem can be executed in a
distributed manner and obtains the same optimal rates as in the centralized
version of the problem (up to constant or logarithmic factors) with an
additional cost related to the spectral gap of the interaction matrix. Finally,
we discuss some extensions to the proposed setup such as proximal friendly
functions, time-varying graphs, improvement of the condition numbers.