Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing

Runze You, Shi Pu

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…