{"ID":3050087,"CreatedAt":"2026-06-04T02:13:16.786527022Z","UpdatedAt":"2026-06-06T11:27:32.998563389Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.04757","arxiv_id":"2606.04757","title":"Near-Optimal Decentralized Stochastic Convex Optimization over Networks","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{M\\lesssim \\sqrtρ\\,N^{3/4}}$ workers, where $ρ$ is the spectral gap of the gossip network, improving the best prior maximal scaling of $\\smash{M\\lesssim ρ\\sqrt 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.","short_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 budg...","url_abs":"https://arxiv.org/abs/2606.04757","url_pdf":"https://arxiv.org/pdf/2606.04757v1","authors":"[\"Nitai Kluger\",\"Amit Attia\",\"Tomer Koren\"]","published":"2026-06-03T11:42:01Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\"]","methods":"[]","has_code":false}