Home / Curated / Algorithms / RelaySum Spanning-Tree Information Propagation for Decentralized Learning

RelaySum Spanning-Tree Information Propagation for Decentralized Learning

Algorithms AIMech:RelaySumSpanningTreeInformationPropagationForDecentralizedLearning DRAFT

Aliases: RelaySum, RelaySGD, RelaySum Spanning-Tree Decentralized Optimization

A decentralized information propagation and model-optimization mechanism (RelaySum / RelaySGD) that routes local model updates across spanning trees of a peer-to-peer communication network without hop-wise weight decay by having each worker i send to each tree neighbor j in N_i the sum m_{i->j}^(t) = x_i^(t+1/2) + sum_{k in N_i \ {j}} m_{k->i}^(t-1) along with scalar parcel counters c_{i->j}^(t), delivering to every worker an exact uniform average (1/n) sum_{j=1}^n x_j^(t - tau_{ij} + 1/2) of delayed local models within a finite number of steps equal to the tree diameter tau_max while using the same per-step communication volume as standard gossip averaging.

Identity Notes & Concept Scope Introduced by Thijs Vogels, Lie He, Anastasia Koloskova, Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi (NeurIPS 2021, pp. 28004-28015; arXiv:2110.04175). Distinct from standard gossip averaging / DP-SGD (Lian et al., NeurIPS 2017) and Stochastic Gradient Push (Assran et al., ICML 2019), which decay message weights by mixing-matrix entries < 1 at every hop and suffer from data heterogeneity drift; and distinct from gradient-tracking / exact-diffusion algorithms (D^2, NEXT, SONATA, Push-Pull), which subtract previous gradients or maintain gradient trackers rather than relaying unattenuated model sums over spanning trees.

Claims & Grounded Evidence

4 Claims

Mechanism #relaysum-tree-message-merging-and-counter-normalization-mechanism

On any tree network G = (V, E), each node i in V computes its local half-step model x_i^(t+1/2) = x_i^(t) - gamma * grad f_i(x_i^(t)) and transmits to each neighbor j in N_i the merged relay sum m_{i->j}^(t) = x_i^(t+1/2) + sum_{k in N_i \ {j}} m_{k->i}^(t-1) together with the counter c_{i->j}^(t) = 1 + sum_{k in N_i \ {j}} c_{k->i}^(t-1), updating x_i^(t+1) = (x_i^(t+1/2) + sum_{j in N_i} m_{j->i}^(t)) / (1 + sum_{j in N_i} c_{j->i}^(t)) so that for all t >= tau_max every worker receives an exact 1/n uniform average of all n workers' models delayed by shortest-path hop distance tau_{ij}.

supports Source: RelaySum for Decentralized Deep Learning on Heterogeneous Data · Locator: Section 3 Method & Algorithm 1 RelaySGD, pp. 4-5

Scope #relaysum-data-heterogeneity-independence-convergence-scope

Under L-smoothness and bounded stochastic gradient variance sigma_bar^2, RelaySGD converges on convex and non-convex objectives at rate O(sigma_bar^2 / (n * epsilon^2) + C * sigma_bar / epsilon^(3/2) + C / epsilon) completely independent of the inter-worker data heterogeneity bound zeta^2 = max_i ||grad f_i(x) - grad f(x)||^2.

supports Source: RelaySum for Decentralized Deep Learning on Heterogeneous Data · Locator: Section 4 Theoretical Analysis, Lemma 1 & Theorem I, pp. 5-6

Limitation #relaysum-spanning-tree-restriction-and-neighbor-memory-limitation

RelaySum requires an acyclic spanning tree (or double binary trees) so that messages do not loop indefinitely, requires auxiliary memory O(|N_i| * d) proportional to the number of tree neighbors to store incoming directional buffers m_{k->i}^(t-1), and attenuates effective step-size energy by a topology-dependent factor alpha <= 1/n.

supports Source: RelaySum for Decentralized Deep Learning on Heterogeneous Data · Locator: Section 3 Method, Section 5.2, & Appendix D.1, pp. 4, 7, 33-34

Application #relaysum-heterogeneous-decentralized-deep-learning-application

Applied to decentralized deep learning on heterogeneous non-IID image classification (CIFAR-10 VGG-11, ImageNet ResNet-20-EvoNorm) and NLP fine-tuning (DistilBERT on AG News) over spanning trees and double binary trees.

supports Source: RelaySum for Decentralized Deep Learning on Heterogeneous Data · Locator: Section 5.3 Effect of data heterogeneity in decentralized deep learning, Tables 1-5, pp. 7-10

⚠️ Curated Limitations & Negative Results

Cannot utilize cycle edges directly on general graphs without first extracting one or more spanning trees.
Requires storing one model-sized message buffer per incident tree edge at each worker node.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	AIO:FederatedLearning represents centralized server-coordinated distributed learning, whereas RelaySum/RelaySGD is a serverless spanning-tree information-propagation and optimization protocol for decentralized networks.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r549-primary-pdf`	RelaySum for Decentralized Deep Learning on Heterogeneous Data Thijs Vogels, Lie He, Anastasia Koloskova, Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, Martin Jaggi	primary paper full_text	ID: https://dblp.org/rec/conf/nips/VogelsHKKLSJ21 sha256:fab0dba33b56…
`r549-arxiv-abs`	RelaySum for Decentralized Deep Learning on Heterogeneous Data (arXiv abstract) Thijs Vogels, Lie He, Anastasia Koloskova, Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, Martin Jaggi	primary paper abstract_only	ID: https://arxiv.org/abs/2110.04175 sha256:ee3a1cfd3860…
`r549-metadata-cr`	RelaySum for Decentralized Deep Learning on Heterogeneous Data (Crossref metadata) Thijs Vogels, Lie He, Anastasia Koloskova, Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, Martin Jaggi	primary paper abstract_only	ID: https://dblp.org/rec/conf/nips/VogelsHKKLSJ21 sha256:d78b01d8d47a…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:32:00Z

Updated: 2026-10-19T10:32:00Z

Source File: data/curated/RelaySumSpanningTreeInformationPropagationForDecentralizedLearning.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories