Vos et al. (2023) — ARXIV-2310.01972
Key takeaways
Introduces Epidemic Learning (EL), a decentralized learning algorithm in which each node sends model updates to a random sample of s other nodes every round, achieving O(n^3/s^2) transient iterations — an s^2 improvement over the O(n^3) best-known bound for static and semi-dynamic topologies. EL is empirically 1.7x faster than static baselines on CIFAR-10 with 96 nodes.
- Theorem 1 — EL transient iteration bound. EL requires at most O(n^3 / s^2) transient iterations before entering the linear speedup regime (dominant term O(1/sqrt(nT))). This is an s^2-fold improvement over the O(n^3) bound for static topologies. Holds when: n nodes, s out-neighbors sampled per node per round, smooth non-convex loss, IID data, synchronous communication.
- Theorem 1b — EL-Local matches EL-Oracle. EL-Local (independent sampling without coordination) achieves the same O(n^3/s^2) transient iteration bound as EL-Oracle (s-regular graph per round), with an additive constant factor difference in the mixing coefficient. Holds when: Same assumptions as Theorem 1; in-degree variance across nodes is absorbed into the constant.
- Empirical speedup over static topology (C3). EL achieves 1.7x faster convergence and 2.2% higher final accuracy than 7-regular static topology on CIFAR-10 with 96 nodes, using the same total communication bandwidth (s = 7 for EL vs. 7-regular). Holds when: 96 nodes, CIFAR-10, ResNet-20, 5 seeds, 95% CI.
What the evidence does not cover
- Assumes all nodes can potentially communicate with all other nodes; may not hold in edge deployments with restricted connectivity.
- EL-Oracle requires a central coordinator each round to generate the s-regular topology, partially reintroducing centralization.
- Synchronous communication model; asynchronous or node-dropout settings are not analyzed.
- Convergence guarantees are for smooth non-convex losses only; no rates for convex or strongly convex cases are provided.
- Experiments are limited to 96 nodes; scalability to thousands of nodes is not empirically verified.
Standing in the anthology
Read — the reading is NOTE-095. Arrived in the imported batch, which brought in the decentralized branch, where there is no parameter server and the topology is the hyperparameter.