Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing

Abstract

Communication is a central bottleneck in distributed optimization, but its effect is often summarized by the spectral gap of a chosen mixing matrix. Since this gap depends on link weights as well as topology, it can obscure the intrinsic effect of the network. We clarify this distinction by relating graph diameter to the inverse spectral gap. We establish a universal one-sided bound that is tight up to constant factors, while constructions across several graph families show that no topology-only converse or universal two-sided scaling law exists. This motivates a class-based view of network optimality: diameter-dependent guarantees can be assessed uniformly over graph classes, whereas spectral-gap optimality requires both the graph--matrix pair class and the admissible algorithm class to be specified. Based on the resulting diameter-based minimax benchmark, we introduce Tree-Routed Gradient Tracking (Tree-RGT), a distributed method for stochastic nonconvex optimization. The method pipelines model dissemination and gradient aggregation over a rooted shortest-path spanning tree. Each iteration uses one round of one-hop communication and one stochastic-gradient evaluation per agent, without inner consensus or multi-gossip. Under smoothness and unbiased bounded-variance oracles, Tree-RGT achieves uniformly optimal network dependence over connected graphs of prescribed size and diameter. It recovers centralized stochastic scaling after 𝒪(nD_𝒢²) transient iterations, where n is the number of agents and D_𝒢 is the graph diameter. This network-dependent transient-iteration bound improves upon or matches those reported for representative distributed methods. Thus, topology-aware routing attains diameter-optimal guarantees without relying on a prescribed mixing matrix.

Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
Yury A. Sokolov, Maxim K. Mashtaler, Alexander V. Gasnikov +3
arXiv18 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Distributed Stochastic Extremum Seeking for Optimal Resource Allocation over Networks with Time Delays
Pei-Pei Zhang, Bao-Ting Zhang, Na Li
Axioms29 Oct 2026Peer-reviewedCC BY 4.0General mathematicsCrossref
Noise-Robust Distributed Optimization Over Directed Graphs With Row Stochastic Matrices
Yifan Wang, Mufeng Wang, Xianghui Cao
arXiv1 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
Qihao Zhou
arXiv25 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits
Grigory Begunov, Alexander Tyurin
arXiv19 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{you2026optimal,
  title = {{Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing}},
  author = {Runze You and Shi Pu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.18101},
  eprint = {2609.18101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.18101},
  note = {CC BY-NC-SA 4.0},
}

RIS

TY  - UNPB
TI  - Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing
AU  - Runze You
AU  - Shi Pu
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.18101
UR  - https://arxiv.org/abs/2609.18101
AB  - Communication is a central bottleneck in distributed optimization, but its effect is often summarized by the spectral gap of a chosen mixing matrix. Since this gap depends on link weights as well as topology, it can obscure the intrinsic effect of the network. We clarify this distinction by relating graph diameter to the inverse spectral gap. We establish a universal one-sided bound that is tight up to constant factors, while constructions across several graph families show that no topology-only converse or universal two-sided scaling law exists. This motivates a class-based view of network optimality: diameter-dependent guarantees can be assessed uniformly over graph classes, whereas spectral-gap optimality requires both the graph--matrix pair class and the admissible algorithm class to be specified. Based on the resulting diameter-based minimax benchmark, we introduce Tree-Routed Gradient Tracking (Tree-RGT), a distributed method for stochastic nonconvex optimization. The method pipelines model dissemination and gradient aggregation over a rooted shortest-path spanning tree. Each iteration uses one round of one-hop communication and one stochastic-gradient evaluation per agent, without inner consensus or multi-gossip. Under smoothness and unbiased bounded-variance oracles, Tree-RGT achieves uniformly optimal network dependence over connected graphs of prescribed size and diameter. It recovers centralized stochastic scaling after 𝒪(nD_𝒢^2) transient iterations, where n is the number of agents and D_𝒢 is the graph diameter. This network-dependent transient-iteration bound improves upon or matches those reported for representative distributed methods. Thus, topology-aware routing attains diameter-optimal guarantees without relying on a prescribed mixing matrix.
ER  -

Abstract

Related

Cite