{"id":"arxiv/2606.04757","url":"https://arxiv.org/abs/2606.04757","tags":["math.OC","cs.LG"],"score":0,"title":"Near-Optimal Decentralized Stochastic Convex Optimization over Networks","domain":"math.OC","source":"arxiv","authors":["Nitai Kluger","Amit Attia","Tomer Koren"],"reviews":0,"subject":"math.OC","summary":"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{M\\lesssim \\sqrtρ\\,N^{3/4}}$ workers, where $ρ$ is the spectral gap of the gossip…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-03","reactions":{}}