{"id":"arxiv/2609.18101","url":"https://arxiv.org/abs/2609.18101","tags":["math.OC"],"score":0,"title":"Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing","domain":"math.OC","source":"arxiv","authors":["Runze You","Shi Pu"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}