A principled framework for the design and analysis of token algorithms

Hadrien Hendrikx

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.

1. Introduction

In decentralized machine learning, nodes collaborate to train a global model without relying on a central server. The predominant paradigm is gossip, where nodes periodically average their local models with neighbors. While effective, gossip can be communication-intensive and may inadvertently leak private data through repeated pairwise exchanges.

An alternative approach is the token algorithm, where a single model estimate (the "token") performs a random walk across the network. The node currently holding the token performs a local update before passing it to a neighbor. Despite their intuitive appeal and privacy advantages, token algorithms have historically lacked the advanced optimization techniques—such as variance reduction and Nesterov-style acceleration—that characterize modern centralized and gossip-based methods. This work introduces a unified framework to bridge this gap by mapping token walks onto a "conceptual graph."

2. The Conceptual Graph Framework

The central innovation of this work is the Conceptual Graph. By mapping the sequential movement of a token onto a high-dimensional virtual graph, we can treat token algorithms as a special case of randomized gossip.

2.1 Node Splitting and Dual Formulation

To achieve this mapping, each physical node is split into two virtual components: a computation node (holding the local data and function $f_i$) and a communication node (handling token interactions). The optimization problem is then moved into its dual form, where token movements correspond to simple coordinate descent steps.

Mapping physical nodes to a conceptual graph with computation nodes, communication nodes, and tokens.

This framework allows for the decoupling of computation and communication. Nodes can continue performing local gradient updates even when they do not hold the token, preventing the "idle worker" bottleneck typical of sequential methods. Furthermore, the framework scales naturally to $K$ tokens by adding more token nodes to the conceptual graph.

3. Algorithm Suite: From GD to Acceleration

Using the conceptual graph, we derive a suite of new algorithms that match the theoretical efficiency of centralized systems. The most basic is Token Gradient Descent (Token GD), which provides the foundation for more advanced variants.

Algorithm 1: Token Gradient Descent (Token GD).

Beyond basic GD, we introduce:

  • Token Variance Reduction (TVR): Incorporates stochastic gradient methods (like SAGA or SVRG) to avoid full gradient computations at every token visit.
  • Token Accelerated Variance Reduced (TAVR): Adds momentum-like acceleration to further speed up convergence, improving the dependency on the condition number from $\kappa$ to $\sqrt{\kappa}$.

For general, non-complete graphs, we employ a "communication skipping" strategy. The token performs multiple jumps to ensure adequate mixing before a model update, effectively simulating a well-connected network topology.

4. Experimental Evaluation

We evaluated the framework on a large-scale linear classification task using the RCV1 (Reuters Corpus Volume 1) dataset, consisting of over 800,000 newswire stories. The task involved logistic regression with $L_2$ regularization across 20 nodes.

4.1 Key Results

  • Matching Centralized Performance: The proposed algorithms achieve a communication complexity of $O(n\kappa \log(1/\epsilon))$, matching centralized servers communicating with $n$ nodes over $\kappa$ rounds.
  • Linear Convergence: Unlike previous sub-linear random-walk methods, our algorithms provide strong linear convergence guarantees.
  • Empirical Speedup: In empirical tests, TVR significantly outperformed standard methods like Walkman and remained competitive with optimized ring topologies while being more communication-efficient than all-to-all Gradient Descent.

5. Conclusion and Future Work

This framework provides a principled way to design token algorithms that match the theoretical efficiency of centralized systems while preserving decentralized privacy. While the "communication skipping" for general graphs is mathematically sound, it introduces some practical inefficiency through "wasted" jumps. Future work includes formalizing the privacy guarantees of this framework and exploring more efficient information exchange where the token updates at every node it passes during its walk.

Summary updated

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 \emph{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.
BibTeX
@inproceedings{hendrikx2023principled,
  author = {Hadrien Hendrikx},
  title = {{A principled framework for the design and analysis of token algorithms}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=O10SGvk56o},
}
Figure