Abstract
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.
Introduction
In decentralized machine learning, nodes collaborate to train a global model without relying on a central server. While traditional methods often use "gossip" protocols—where nodes periodically average their models with neighbors—this paper focuses on "token algorithms." In these schemes, a single data structure (the token) "walks" the network, updating itself at each node it visits.
Token algorithms offer unique advantages in privacy and communication efficiency, yet they have historically been difficult to analyze and lacked the advanced features of modern optimization, such as variance reduction and acceleration. This work introduces a unified mathematical framework that maps token algorithms onto a novel "conceptual graph," allowing these methods to match the efficiency of centralized systems while remaining robust to network bottlenecks.
The Conceptual Graph Approach
The core innovation of this work is the construction of a virtual "conceptual graph" that simplifies the analysis of the roaming token. Instead of analyzing the physical network directly, the framework transforms the optimization problem by splitting nodes and introducing the token as a participant in the graph.
As illustrated in the figure above, the conceptual graph involves:
- Node Splitting: Each physical node is represented as two virtual nodes—one for computation (handling data) and one for communication.
- Token as a Node: The roaming token itself is treated as a node in this virtual graph.
- Duality: By applying Lagrangian duality to this conceptual graph, the token's random walk is transformed into a form of Bregman Coordinate Descent.
This mapping allows for the seamless integration of well-studied optimization techniques, including multiple tokens for increased throughput, Token Variance Reduction (TVR) to handle noisy data, and acceleration for faster convergence.
Dynamics and Parallelism
A key insight is that the token acts as a "roaming server," aggregating information like a central server in Federated Learning but without the single point of failure or bandwidth bottlenecks. By decoupling computation and communication, the framework allows nodes to perform local updates even when they do not hold a token, enabling true parallelism.
This structure provides natural resilience to "stragglers." Because the token moves via a Markov Chain, it does not need to wait for slow nodes; it simply visits them less frequently or moves on, whereas synchronous methods would be forced to wait for the slowest participant.
Key Results and Performance
The proposed algorithms were evaluated on standard machine learning benchmarks, including RCV1 (text categorization), Phishing (logistic regression), and YearPredictionMSD (ridge regression).
Key findings include:
- Theoretical Parity: Token algorithms can achieve $O(\kappa \log 1/\epsilon)$ convergence rates, matching the performance of centralized gradient descent.
- TVR Performance: Token Variance Reduction significantly outperformed standard token methods and the well-known "Walkman" algorithm, particularly as the required precision increased.
- Scalability: Using multiple tokens (e.g., 4 tokens vs. 1) provided a near-linear speedup in communication-heavy environments, confirming that the optimization burden can be shared effectively.
- Efficiency: The algorithms proved more communication-efficient than standard decentralized methods like EXTRA in dense network graphs.
Conclusion
This framework provides a principled way to design robust and efficient decentralized optimization algorithms. By mapping physical networks to conceptual graphs, the author bridges the gap between simple token walks and state-of-the-art optimization. Future work will focus on direct analysis of coordinate descent on Markov Chains for general graphs and formalizing the inherent privacy guarantees of the token-based approach.
Summary updated