2022/05/30 by Hadrien Hendrikx, Hendrikx, Hadrien · 2 citations
Computer Science · #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2205.15015
openalex publication_date 2022/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We consider a decentralized optimization problem, in which n nodes collaborate to optimize a global objective function using local communications only. While many decentralized algorithms focus on gossip communications (pairwise averaging), we consider a different scheme, in which a ``token'' that contains the current estimate of the model performs a random walk over the network, and updates its model using the local model of the node it is at. Indeed, token algorithms generally benefit from improved communication efficiency and privacy guarantees. We frame the token algorithm as a randomized gossip algorithm on a conceptual graph, which allows us to prove a series of convergence results for variance-reduced and accelerated token algorithms for the complete graph. We also extend these results to the case of multiple tokens by extending the conceptual graph, and to general graphs by tweaking the communication procedure. The reduction from token to well-studied gossip algorithms leads to tight rates for many token algorithms, and we illustrate their performance empirically.