We consider the task of decentralized minimization of the sum of smooth strongly convex functions stored across the nodes of a network. For this problem, lower bounds on the number of gradient computations and the number of communication rounds required to achieve $\varepsilon$ accuracy have recently been proven. We propose two new algorithms for this decentralized optimization problem and equip them with complexity guarantees. We show that our first method is optimal both in terms of the number of communication rounds and in terms of the number of gradient computations. Unlike existing optimal algorithms, our algorithm does not rely on the expensive evaluation of dual gradients. Our second algorithm is optimal in terms of the number of communication rounds, without a logarithmic factor. Our approach relies on viewing the two proposed algorithms as accelerated variants of the Forward Backward algorithm to solve monotone inclusions associated with the decentralized optimization problem. We also verify the efficacy of our methods against state-of-the-art algorithms through numerical experiments.

Summary and Contributions: The paper considers smooth and strongly-convex decentralized optimization problems. The authors propose a novel primal gossip-based optimization algorithm (OPAPC) which is provably optimal w.r.t. Existing optimal algorithms for this setting rely on access to dual gradient which, in absence of any structure, can be very expensive. The suggested method uses primal (1st order) access exclusively---forming the main contribution of the paper. The main algorithmic idea is to use a generalized forward backward-like algorithm with the corresponding positive-definite operator being chosen according to the gossip matrix (so as to comply with the underlying decentralized structure).

We consider the task of decentralized minimization of the sum of smooth strongly convex functions stored across the nodes of a network. For this problem, lower bounds on the number of gradient computations and the number of communication rounds required to achieve \varepsilon accuracy have recently been proven. We propose two new algorithms for this decentralized optimization problem and equip them with complexity guarantees. We show that our first method is optimal both in terms of the number of communication rounds and in terms of the number of gradient computations. Unlike existing optimal algorithms, our algorithm does not rely on the expensive evaluation of dual gradients.