Near-Optimal Decentralized Stochastic Convex Optimization over Networks

arXiv:2606.04757v1 Announce Type: cross Abstract: We study decentralized stochastic smooth convex optimization, where M workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of N gradient samples while still preserving the centralized O(1/sqrt N) statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to smash{Mlesssim sqrt{rho},N^{3/4}} workers, where rho is the spectral gap of the gossip network, improving the best prior maximal scaling of smash{Mlesssim rhosqrt N}. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.

Source: arXiv cs.LG | 2026-06-04