Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives

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 $\kappa$ 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(({\tau }_{\max }+{\Delta }_{\max })\sqrt{\kappa /\gamma }\ln ({\epsilon }^{-1}))$ 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 }_{\mathrm{gossip}}/n})$ where ${\theta }_{\mathrm{gossip}}$ is the rate of the standard randomized gossip. To the best of our knowledge, it is the first asynchronous gossip algorithm with a provably improved rate of convergence of the second moment of the error. We illustrate these results with experiments in idealized settings.

References in corpus (1)

• Stochastic Dual Ascent for Solving Linear Systems

Cited by in corpus (12)

• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• Projected Gradient Method for Decentralized Optimization over Time-Varying Networks
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
• Asynchronous Decentralized Successive Convex Approximation
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Asynchrony and Acceleration in Gossip Algorithms
• Decentralized Learning with Lazy and Approximate Dual Gradients
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols
• Dynamic Average Diffusion with randomized Coordinate Updates