Metraipolis › archive › dc_dfce86cbeef0

Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing — arXiv:2609.18101

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.18101
License (as archived): CC0-1.0
Archived: 2026-10-15T15:40:18.577Z
SHA-256 of the archived text: 8a4040c04c8d0b773e46d21428ca5ada6529f5718798cdb4b3a37db982abd119
Stable URL of this page: https://metraipolis.com/documento/dc_dfce86cbeef0

How to cite

Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing — arXiv:2609.18101 — arXiv (en), https://arxiv.org/abs/2609.18101 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dfce86cbeef0 (Metraipolis archive dc_dfce86cbeef0, sha256 8a4040c04c8d0b773e46d21428ca5ada6529f5718798cdb4b3a37db982abd119)

BibTeX

@misc{dcdfce86cbeef0,
  title = {Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing — arXiv:2609.18101},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18101},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dfce86cbeef0; sha256 8a4040c04c8d0b773e46d21428ca5ada6529f5718798cdb4b3a37db982abd119},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18101. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathcal{O}(nD_{\mathcal{G}}^2)$ transient iterations, where $n$ is the number of agents and $D_{\mathcal{G}}$ 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.18101 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T15:08:22.579Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).