Research map / Optimization / Distributed and compressed
Scalable Decentralized Learning with Teleportation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Teleportation, a decentralized SGD variant that activates a random subset of k nodes each round, passing parameters to the next active nodes and gossip-averaging only over a small k-node topology, plus a parallel search over k that needs about 2T iterations.
Problem
Decentralized SGD's convergence rate degrades as the number of nodes grows because the spectral gap of the topology shrinks, even when any two nodes can communicate.
Approach
Activate only k nodes per iteration, have them copy parameters from previous active nodes (token-based teleportation), and run gossip averaging on a small k-node topology so consensus is fast; choose k by a log-spaced parallel search instead of full grid search.
Key results
- On a synthetic 100-node problem, Teleportation converged up to three orders of magnitude faster than Decentralized SGD with a ring, and up to 10x faster with the Base-2 Graph.
- On CIFAR-10 / Fashion-MNIST with Dirichlet alpha=0.1 (heterogeneous), Teleportation outperformed Decentralized SGD and trained more stably; with alpha=10 all methods were competitive.
- The proposed parallel search needs 2T total iterations versus nT for grid search over k, with the same theoretical rate as the optimal k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Teleportation instead of Decentralized SGD with a ring | Decentralized learning · Synthetic experiment, ring topology | iterations to target accuracy: up to three orders of magnitude faster | Helped |
| Use Teleportation instead of Decentralized SGD with Base-2 Graph | Decentralized learning · Synthetic experiment, Base-2 Graph | iterations to target accuracy: up to $10$ times faster | Helped |
| Use Teleportation instead of Decentralized SGD | LeNet on Fashion MNIST · Fashion MNIST, heterogeneous data ($\alpha=0.1$) | test accuracy | Helped |
| Use Teleportation instead of Decentralized SGD | VGG on CIFAR-10 · CIFAR-10, heterogeneous data ($\alpha=0.1$) | test accuracy | Helped |
| Use Teleportation instead of Decentralized SGD | LeNet on Fashion MNIST · Fashion MNIST, homogeneous data ($\alpha=10.0$) | test accuracy | No clear effect |
| Use Teleportation instead of Decentralized SGD with a ring | LeNet on Fashion MNIST · Heterogeneous network ($\tau=5$), heterogeneous data ($\alpha=0.1$) | time to reach high accuracy | Helped |
| Use Teleportation instead of Decentralized SGD with a ring | LeNet on Fashion MNIST · Heterogeneous network ($\tau=5$), homogeneous data ($\alpha=10.0$) | time to reach high accuracy | Hurt |
| Use Teleportation instead of Decentralized SGD with a ring | LeNet on Fashion MNIST · Heterogeneous network ($\tau=5$), wallclock training time | training time | Hurt |
| Activate a tuned subset of nodes and gossip-average on their smaller topology | Decentralized SGD · Synthetic experiment, ring topology | iterations to target accuracy: up to three orders of magnitude faster | Helped |
| Activate a tuned subset of nodes and gossip-average on their smaller topology | Decentralized SGD · Synthetic experiment, Base-2 Graph | iterations to target accuracy: up to $10$ times faster | Helped |
Surprising findings
- With homogeneous data (alpha=10), Decentralized SGD with a ring reached high accuracy faster than Teleportation in heterogeneous-network experiments.
Limitations
- Not applicable when some pairs of nodes cannot communicate (e.g., wireless sensor networks).
- Randomly sampled active nodes may communicate between distant nodes in heterogeneous networks, increasing wall-clock cost.
- Theory relies on the assumption that the step size and k are tuned, and the search is only theoretically guaranteed under stated assumptions.
Experimental setup
Datasets: Fashion-MNIST CIFAR-10
Benchmarks: Fashion-MNIST CIFAR-10 synthetic quadratic problem
Metrics: iterations to target accuracy test accuracy gradient norm
Baselines: Decentralized SGD with ring Decentralized SGD with Base-2 Graph client sampling
Builds on: Decentralized SGD Base-2 Graph Dirichlet data partitioning
Closest papers by meaning
- Asynchronous Decentralized SGD with Quantized and Local Updates (NeurIPS 2021 · similarity 0.89)
- Improved Convergence Analysis of Topology Dependence in Decentralized SGD (ICML 2026 · similarity 0.88)
- Communication-Efficient Topologies for Decentralized Learning with $O(1)$ Consensus Rate (NeurIPS 2022 · similarity 0.88)
- Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence (NeurIPS 2023 · similarity 0.88)
- Enhancing Parallelism in Decentralized Stochastic Convex Optimization (ICML 2025 · similarity 0.86)
- Improving Convergence and Generalization Using Parameter Symmetries (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.