[edit]
Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:897-906, 2019.
Abstract
In this paper, we study the problem of minimizing a sum of smooth and strongly convex functions split over the nodes of a network in a decentralized fashion. We propose the algorithm ESDACD, a decentralized accelerated algorithm that only requires local synchrony. Its rate depends on the condition number κ of the local functions as well as the network topology and delays. Under mild assumptions on the topology of the graph, ESDACD takes a time O((τmax to reach a precision \epsilon where \gamma is the spectral gap of the graph, \tau_{\max} the maximum communication delay and \Delta_{\max} the maximum computation time. Therefore, it matches the rate of SSDA, which is optimal when \tau_{\max} = \Omega\left(\Delta_{\max}\right). Applying ESDACD to quadratic local functions leads to an accelerated randomized gossip algorithm of rate O( \sqrt{\theta_{\rm gossip}/n}) where \theta_{\rm gossip} is the rate of the standard randomized gossip. To the best of our knowledge, it is the first asynchronous algorithm with a provably improved rate of convergence of the second moment of the error. We illustrate these results with experiments in idealized settings.