2018/10/05 by Hadrien Hendrikx, Francis Bach, Hendrikx, Hadrien +3 · 2 citations
Computer Science · Materials Science · #Cooperative Communication and Network Coding #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Nanocluster Synthesis and Applications #Neural Networks Stability and Synchronization #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1810.02660
openalex publication_date 2018/10/05 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28
In this paper, we study the problem of minimizing a sum of smooth and\nstrongly convex functions split over the nodes of a network in a decentralized\nfashion. We propose the algorithm ESDACD, a decentralized accelerated\nalgorithm that only requires local synchrony. Its rate depends on the condition\nnumber \κ of the local functions as well as the network topology and\ndelays. Under mild assumptions on the topology of the graph, ESDACD takes a\ntime O((\τ\max +\n\Δ\max)\√\κ/\γ\ln(\ε-1)) to reach a precision\n\ε where \γ is the spectral gap of the graph, \τ\max the\nmaximum communication delay and \Δ\max the maximum computation time.\nTherefore, it matches the rate of SSDA, which is optimal when \τ\max =\n\Ω\(\Δ\max\). Applying ESDACD to quadratic local\nfunctions leads to an accelerated randomized gossip algorithm of rate O(\n\√\θ rm gossip/n) where \θ rm gossip is the rate of the\nstandard randomized gossip. To the best of our knowledge, it is the first\nasynchronous gossip algorithm with a provably improved rate of convergence of\nthe second moment of the error. We illustrate these results with experiments in\nidealized settings.\n