High-Probability Convergence Guarantees of Decentralized SGD

Convergence in high-probability (HP) has attracted increasing interest, due to implying exponentially decaying tail bounds and strong guarantees for individual runs of an algorithm. While many works study HP guarantees in centralized settings, much less is understood in the decentralized setup, where existing works require strong assumptions, like uniformly bounded gradients, or asymptotically vanishing noise. This results in a significant gap between the assumptions used to establish convergence in the HP and the mean-squared error (MSE) sense, and is also contrary to centralized settings, where it is known that $\mathtt{SGD}$ converges in HP under the same conditions on the cost function as needed for MSE convergence. Motivated by these observations, we study the HP convergence of Decentralized $\mathtt{SGD}$ ($\mathtt{DSGD}$) in the presence of light-tailed noise, providing several strong results. First, we show that $\mathtt{DSGD}$ converges in HP under the same conditions on the cost as in the MSE sense, removing the restrictive assumptions used in prior works. Second, our sharp analysis yields order-optimal rates for both non-convex and strongly convex costs. Third, we establish a linear speed-up in the number of users, leading to matching or strictly better transient times than those obtained from MSE results, further underlining the tightness of our analysis. To the best of our knowledge, this is the first work that shows $\mathtt{DSGD}$ achieves a linear speed-up in the HP sense. Our relaxed assumptions and sharp rates stem from several technical results of independent interest, including a result on the variance-reduction effect of decentralized methods in the HP sense, as well as a novel bound on the moment-generating function of strongly convex costs, of interest even in centralized settings. Numerical experiments validate our theory.

Machine learning algorithms are often judged by how well they perform on average, but in many applications it is also important to know that a single run is very likely to succeed. This kind of “high-probability” guarantee gives stronger confidence that an algorithm will not fail due to random noise. For decentralized learning, where many users or devices cooperate without sending all data to one central machine, such guarantees are still poorly understood. Existing results often rely on unrealistic assumptions, such as gradients being uniformly bounded or noise disappearing over time. We study Decentralized Stochastic Gradient Descent, a widely used method for training models across a network of users, and prove that it converges with high probability under much weaker and more standard conditions. In particular, we show that the same assumptions used for traditional average-case guarantees are enough to obtain strong guarantees for individual runs. Our analysis also proves optimal convergence rates and shows that adding more users can speed up the learning linearly. This helps close an important gap in the theory of decentralized optimization and supports the practical reliability of decentralized learning methods.