A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip
Peyman Gholami, Hulya Seferoglu · 2025
Read A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip by Peyman Gholami, Hulya Seferoglu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-09792.txt.
Introduction
Peyman Gholami and Hulya Seferoglu compared in 2025 two styles of decentralized learning: gossip and multi-stream random walks. Both let networked machines train together without a central server, yet head-to-head theory was thin. The authors designed an asynchronous multi-walk method and proved how fast it settles. They gave the same full treatment to asynchronous gossip, filling a gap in the literature.
Walks won on iteration counts in stretched networks such as cycles, while gossip's edge depended on walk numbers and data spread in tight networks. In wall-clock terms, walks sped up with more streams and gossip with more nodes. Walks also used less communication, except in small networks with extreme data skew. The study maps which method suits which network shape. Code is shared for others to check the claims.
Catalog record
| CREATOR | Peyman Gholami, Hulya Seferoglu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-09792
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip Peyman Gholami, Hulya Seferoglu Abstract . Although gossip and random walk-based learning algorithms are widely known for decentralized learning, there has been limited theoretical and experimental analysis to understand their relative performance for different graph topologies and data heterogeneity. We first design and analyze an asynchronous random walk-based learning algorithm with multiple streams (walks), which we name “Multi-Walk”. We provide a convergence analysis for Multi-Walk w.r.t number of iterations (computation), wall-clock time, and communication cost. We also present a convergence analysis for “Asynchronous Gossip”, addressing the notable gap in the existing literature by explicitly accounting for its computational and communication overhead. Our results show that Multi-Walk has better convergence in terms of iterations as compared to Asynchronous Gossip in graphs with large diameters (e.g., cycles), while its relative performance, as compared to Asynchronous Gossip, depends on the number of walks and the data heterogeneity in graphs with small diameters (e.g., complete graphs). In wall-clock time analysis, we observe a linear speed-up with the number of walks and nodes in Multi-Walk and Asynchronous Gossip, respectively. Finally, we show that Multi-Walk outperforms Asynchronous Gossip in communication overhead, except in small-diameter topologies with extreme data heterogeneity. These results highlight the effectiveness of each algorithm across varying graph topologies and levels of data heterogeneity. Our codes are available for reproducibility. 1. Introduction Decentralized learning has gained significant attention as a robust alternative to traditional federated learning approaches, addressing critical limitations such as communication bottlenecks and single points of failure ( Tsitsiklis, 1984 ; Nedić and Ozdaglar, 2009 ; McMahan et al., 2023 ) . Among decentralized methods, two prominent approaches have emerged: gossip and random walk-based algorithms. While both paradigms have been extensively studied ( Boyd et al., 2006 ; Lian et al., 2017 ; Koloskova et al., 2019 ; Bertsekas, 1997 ; Ayache and Rouayheb, 2020 ; Sun et al., 2018 ; Needell et al., 2015 ) , a gap remains in understanding their relative performance and trade-offs across different graph topologies and data heterogeneity. Specifically, a comprehensive analysis comparing their convergence rates, communication cost, and computational overhead is still lacking, which constitutes the primary focus of this work. Gossip algorithms advocate that nodes in a graph iteratively update their models with Stochastic Gradient Descent (SGD) ( Robbins, 1951 ; Bottou et al., 2018 ) and exchange the updated models with their neighbors, leading to global consensus over time. Gossip can employ synchronous communication ( Lian et al., 2017 ; Koloskova et al., 2020 ) , where nodes must wait for all nodes to update their model in each round. However, in the presence of straggler nodes or nodes with varying computation speeds ( Kairouz et al., 2021 ) , synchronous gossip results in significant idle times for fast nodes and creates bottlenecks ( Chen et al., 2017 ) . Asynchronous gossip algorithms ( Baudet, 1978 ; Tsitsiklis et al., 1984 ; Recht et al., 2011 ) have been developed to leverage resources more effectively, allowing nodes to compute gradients using a stale model and communicate in a asynchronous manner, thereby eliminating the need to wait for all nodes ( Lian et al., 2018 ; Nabli et al., 2023 ; Nadiradze et al., 2022 ; Bornstein et al., 2022 ; Even et al., 2024 ) . In both synchronous and asynchronous cases, gossip incurs high communication costs due to frequent message exchange among nodes. The random walk-based learning algorithms suggest that one node at a time updates a model with its local data. The node then randomly selects a neighbor and sends the updated model to it. This neighbor becomes the next activated node and updates the model using its own local data. This process repeats until convergence. Random walk-based algorithms ( Ayache and Rouayheb, 2020 ; Sun et al., 2018 ; Needell et al., 2015 ) are typically single stream, i.e., only one node updates the model at any given time, which leads to slow convergence. While utilizing multiple streams can improve convergence, the coordination and interaction among these streams remain largely unexplored in the context of random walk-based learning—a gap this paper aims to address. To investigate the relative performance of gossip-based and random walk-based learning under varying graph topologies and data heterogeneity, we first design and analyze a multi-stream random walk algorithm, which we call asynchronous “Multi-Walk”. We then conduct a comprehensive comparison of Multi-Walk and Asynchronous Gossip in terms of iteration count (computation), wall-clock time, and communication cost. Our main contributions are as follows: Design of Multi-Walk algorithm. We design, for the first time in the literature, a random walk-based learning algorithm with multiple asynchronous streams, Multi-Walk. The core idea behind Multi-Walk is to improve the convergence rate of random walk-based methods by initiating multiple random walks (streams) simultaneously across the graph. This strategy increases the number of concurrent computations, enabling the algorithm to improve its convergence rate. Multi-Walk allows for a trade-off between convergence speed and resource utilization by adjusting the number of walks. There is no need for special coordination among the walks, as each walk operates independently on the graph. Furthermore, we demonstrate that Multi-Walk achieves a linear speedup with the number of walks. To the best of our knowledge, Multi-Walk is the first asynchronous random walk-based learning algorithm to leverage multiple parallel streams. Comprehensive analysis of Multi-Walk and Asynchronous Gossip. We provide an in-depth examination of both Multi-Walk and Asynchronous Gossip algorithms. Specifically, we analyze their convergence properties w.r.t. iterations (computation), wall-clock time, and communication overhead. This detailed comparison addresses a significant gap in the literature, offering insights into the performance trade-offs of these methods. We analyze both algorithms under the assumption of non-convex, smooth, and heterogeneous loss functions, without any upper bounds on computation or communication delays. Theoretical insights. Our analysis demonstrates that Multi-Walk exhibits superior performance on graphs with larger diameters, while Asynchronous Gossip is likely a better choice for small-diameter graphs in terms of iteration complexity. Specifically, Multi-Walk outperforms Asynchronous Gossip in both iteration complexity and communication overhead on graph topologies such as cycles. We showed that in iid setting, on graphs where p=\mathcal{O}\left(\frac{1}{V}\right), with V representing the number of nodes in the network graph, Multi-Walk shows superior performance compared to Asynchronous Gossip. Here, p refers to the spectral gap of \mathbf{P}^{\top}\mathbf{P} , where \mathbf{P} is the mixing matrix of Asynchronous Gossip. Intuitively, p^{-1/2} correlates with the graph’s diameter. When evaluating convergence in terms of clock time, Asynchronous Gossip benefits from a linear speed-up with the number of nodes. Multi-Walk outperforms Asynchronous Gossip when considering convergence in terms of communication overhead except in small-diameter graphs with extreme data heterogeneity (non-iid). This highlights the effectiveness of each algorithm in different scenarios. Empirical validation. We conduct experiments to validate our theoretical findings. The results confirm that Multi-Walk converges faster w.r.t. iterations for graphs with larger diameters, such as cycles. However, this advantage does not hold for topologies with smaller diameters, such as complete graphs. We also examine the impact of non-iid data in an Erdős–Rényi topology, observing behavior consistent with our theoretical analysis. To highlight the benefits of Multi-Walk over Asynchronous Gossip in communication-constrained settings, we conducted experiments measuring convergence rates