Accelerated decentralized optimization with local updates for smooth and strongly convex objectives

Hadrien Hendrikx 1, 2, 3, 4 Francis Bach 3, 4 Laurent Massoulié 2, 1, 4
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
3 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
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 topol-ogy and delays. Under mild assumptions on the topology of the graph, ESDACD takes a time O((τmax + ∆max) κ/γ ln(−1)) to reach a precision where γ is the spectral gap of the graph, τmax the maximum communication delay and ∆max the maximum computation time. Therefore, it matches the rate of SSDA (Scaman et al., 2017), which is optimal when τmax = Ω (∆max). Applying ESDACD to quadratic local functions leads to an accelerated randomized gossip algorithm of rate O(θ gossip /n) where θ gossip is the rate of the standard randomized gossip (Boyd et al., 2006). 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.
Complete list of metadatas

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/hal-01893568
Contributor : Hadrien Hendrikx <>
Submitted on : Thursday, October 11, 2018 - 3:18:18 PM
Last modification on : Friday, April 19, 2019 - 4:55:26 PM
Long-term archiving on : Saturday, January 12, 2019 - 2:59:15 PM

File

1810.02660.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01893568, version 1

Collections

Citation

Hadrien Hendrikx, Francis Bach, Laurent Massoulié. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives. 2018. ⟨hal-01893568⟩

Share

Metrics

Record views

120

Files downloads

49