Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange

arXiv:2610.14716v1 Announce Type: new Abstract: Random walk (RW)-based algorithms are widely used in decentralized learning due to their low communication overhead and scalability. While most existing methods rely on a single token, multiple tokens can explore the network in parallel and exchange information upon meeting. However, the fundamental benefits of such meeting-triggered interactions remain unclear. In this work, we investigate multi-token RW learning under two information exchange policies: \textsc{Average-Gradient} and \textsc{Average-Model}, which average stochastic gradients and updated models, respectively, when tokens meet. We establish iteration complexity lower bounds for non-convex, convex, and strongly convex objectives on complete graphs, which apply to both exchange policies. Compared with single-token RW learning, the scaling factor in these bounds is reduced by a factor of $m^2$ for non-convex and convex objectives, and by an exponentially in $m$ for strongly convex objectives, where $m$ denotes the number of tokens. Numerical experiments reveal distinct behaviors of the two policies under two performance criteria: mean-token loss (the average loss across all tokens) and best-token loss (the minimum loss across all tokens). \textsc{Average-Model} achieves lower mean-token loss and is relatively insensitive to the network-to-token ratio $N/m$, where $N$ is the number of nodes. In contrast, \textsc{Average-Gradient} achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as $N/m$ decreases.

Abstract:Random walk (RW)-based algorithms are widely used in decentralized learning due to their low communication overhead and scalability. While most existing methods rely on a single token, multiple tokens can explore the network in parallel and exchange information upon meeting. However, the fundamental benefits of such meeting-triggered interactions remain unclear. In this work, we investigate multi-token RW learning under two information exchange policies: \textsc{Average-Gradient} and \textsc{Average-Model}, which average stochastic gradients and updated models, respectively, when tokens meet. We establish iteration complexity lower bounds for non-convex, convex, and strongly convex objectives on complete graphs, which apply to both exchange policies. Compared with single-token RW learning, the scaling factor in these bounds is reduced by a factor of $m^2$ for non-convex and convex objectives, and by an exponentially in $m$ for strongly convex objectives, where $m$ denotes the number of tokens. Numerical experiments reveal distinct behaviors of the two policies under two performance criteria: mean-token loss (the average loss across all tokens) and best-token loss (the minimum loss across all tokens). \textsc{Average-Model} achieves lower mean-token loss and is relatively insensitive to the network-to-token ratio $N/m$, where $N$ is the number of nodes. In contrast, \textsc{Average-Gradient} achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as $N/m$ decreases.

Machine Learning (cs.LG)

arXiv:2610.14716 [cs.LG]

(or arXiv:2610.14716v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.14716 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange

Subiecte conexe