Accelerated decentralized optimization with local updates for smooth and strongly convex objectives - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

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

Résumé

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.
Fichier principal
Vignette du fichier
1810.02660.pdf (780.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01893568 , version 1 (11-10-2018)
hal-01893568 , version 2 (16-01-2020)

Identifiants

  • HAL Id : hal-01893568 , version 1

Citer

Hadrien Hendrikx, Francis Bach, Laurent Massoulié. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives. 2018. ⟨hal-01893568v1⟩
173 Consultations
99 Téléchargements

Partager

Gmail Facebook X LinkedIn More