Research map / Optimization / Distributed and compressed
B-ary Tree Push-Pull Method is Provably Efficient for Distributed Learning on Heterogeneous Data
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 B-ary Tree Push-Pull (BTPP), a decentralized stochastic gradient method using two B-ary spanning trees for parameter pulling and gradient-tracker pushing, achieving ~O(n) transient iterations for nonconvex and ~O(1) for strongly convex objectives with Θ(1) per-iteration communication.
Problem
Decentralized stochastic optimization over heterogeneous data with peer-to-peer communication; existing methods with constant per-iteration communication suffer large transient iteration counts (about O(n^3) for nonconvex objectives).
Approach
Replace gossip averaging with two B-ary spanning trees (a pull tree for parameters and its reverse push tree for gradient trackers), so mixing matrices contain only 0/1 entries and each agent talks to at most B+1 neighbors, with diameter ~log_B(n) driving faster information spread.
Key results
- BTPP achieves ~O(n) transient iterations under smooth nonconvex objectives versus O(n^3) for prior Θ(1)-degree methods (Table 1).
- BTPP achieves ~O(1) transient iterations under smooth strongly convex objectives, improving on prior ~O(n) (Table 2).
- On logistic regression with nonconvex regularization (n=100), BTPP with B=2 converges faster than other Θ(1)-degree methods and approaches centralized DSGD; larger B moves it closer to centralized SGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BTPP instead of RelaySGD | Distributed stochastic optimization · Smooth nonconvex objectives | transient iterations: O(n3) -> ˜O(n) | Helped |
| use BTPP instead of DSGD-CECA | Distributed stochastic optimization · Smooth nonconvex objectives | transient iterations: ˜O(n3) -> ˜O(n) | Helped |
| use BTPP instead of RelaySGD | Distributed stochastic optimization · Smooth strongly convex objectives | transient iterations: ˜O(n) -> ˜O(1) | Helped |
| use BTPP instead of OD(OU)-EquiDyn | Distributed stochastic optimization · Smooth strongly convex objectives | transient iterations: ˜O(n) -> ˜O(1) | Helped |
| increase the BTPP branch size B (ablation) | BTPP · Logistic regression with nonconvex regularization | gradient norm | Helped |
Limitations
- Experiments are small-scale (logistic regression and a small CNN on MNIST) and use a modified stepsize for BTPP.
- Slower convergence during the initial O(d) iterations under the chosen stepsize configuration.
- Theoretical transient-time comparisons depend on polylogarithmic factors and constants.
Experimental setup
Datasets: MNIST synthetic logistic regression data
Benchmarks: MNIST
Metrics: gradient norm training loss test accuracy
Baselines: D2 DSGD Hypercube Static Exponential graph One-peer Exponential graph RelaySGD OD(OU)-EquiDyn Base-(k+1) DSGD-FullyConnected DSGT
Builds on: Push-Pull method gradient tracking DSGD RelaySGD one-peer exponential graph
Closest papers by meaning
- Communication-Efficient Topologies for Decentralized Learning with $O(1)$ Consensus Rate (NeurIPS 2022 · similarity 0.86)
- Distributed Event-Based Learning via ADMM (ICML 2025 · similarity 0.85)
- Quantized Decentralized Stochastic Learning over Directed Graphs (ICML 2020 · similarity 0.85)
- A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning (ICML 2018 · similarity 0.85)
- Beyond Flat Gossip: Tiered Gossip Learning for Scalable Collaborative AI (NeurIPS 2026 · similarity 0.85)
- Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers (NeurIPS 2025 · similarity 0.84)
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.