Near-Optimal Decentralized Stochastic Convex Optimization over Networks
For the field of decentralized optimization, this work provides a near-optimal algorithm that significantly improves the maximum number of workers that can be used under a fixed gradient sample budget.
This paper studies decentralized stochastic convex optimization and introduces an accelerated method that preserves the centralized O(1/√N) statistical rate for up to M ≲ √ρ N^{3/4} workers, improving the prior best scaling of M ≲ ρ√N. A matching lower bound shows the method is optimal up to logarithmic factors.
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.