Abstract
We consider decentralized machine learning over a network where the training data is distributed across $n$ agents, each of which can compute stochastic model updates on their local data. The agent's common goal is to find a model that minimizes the average of all local loss functions. While gradient tracking (GT) algorithms can overcome a key challenge, namely accounting for differences between workers' local data distributions, the known convergence rates for GT algorithms are not optimal with respect to their dependence on the mixing parameter $p$ (related to the spectral gap of the connectivity matrix). We provide a tighter analysis of the GT method in the stochastic strongly convex, convex and non-convex settings. We improve the dependency on $p$ from $\mathcal{O}(p^{-2})$ to $\mathcal{O}(p^{-1}c^{-1})$ in the noiseless case and from $\mathcal{O}(p^{-3/2})$ to $\mathcal{O}(p^{-1/2}c^{-1})$ in the general stochastic case, where $c \geq p$ is related to the negative eigenvalues of the connectivity matrix (and is a constant in most practical applications). This improvement was possible due to a new proof technique which could be of independent interest.
Introduction
In decentralized machine learning, data is distributed across numerous agents—such as mobile devices or edge sensors—connected in a network without a central coordinator. A primary challenge in this environment is data heterogeneity. When local datasets differ significantly (e.g., one node has only images of cats while another has only dogs), standard decentralized algorithms like Decentralized Stochastic Gradient Descent (D-SGD) often fail to converge to the global optimum.
Gradient Tracking (GT) was developed to mitigate this by requiring each node to "track" the average gradient across the entire network. While GT has shown empirical success, theoretical analysis has historically been pessimistic, suggesting that poor network connectivity (low spectral gap $p$) would lead to extremely slow convergence. This work closes the gap between theory and practice by providing a significantly tighter analysis of GT's efficiency.
Methodology: The Windowed Contraction
The core contribution of this research is a novel proof technique that reevaluates how the algorithm's error decreases over time. Traditional proofs analyze the algorithm step-by-step. However, the mathematical operator governing GT is not necessarily a "contraction" (a reduction in error) in a single iteration.
By introducing the Contraction Lemma, the authors demonstrate that if one observes a window of steps (specifically $\tau$ steps), the cumulative effect is a guaranteed contraction. This shift in perspective allows for much tighter mathematical bounds. Additionally, the authors introduce a new graph parameter, $c$, which relates to the negative eigenvalues of the network's connectivity matrix. This parameter provides a more granular description of how specific network topologies—like rings or 2D-tori—impact learning speed.
Tighter Convergence Bounds
The new analysis reveals that GT is far less sensitive to network connectivity than previously thought. In the strongly convex setting, the dependency on the mixing parameter $p$ is improved from $\mathcal{O}(p^{-2})$ to $\mathcal{O}(p^{-1}c^{-1})$.
Crucially, this analysis confirms that GT's performance is independent of data heterogeneity. Whether node datasets are identical or completely disparate, the convergence rate remains stable. Furthermore, the analysis shows that while connectivity affects the initial "transient phase," the dominant error term eventually matches that of centralized all-reduce mini-batch SGD, proving that decentralized training can be as efficient as centralized methods given enough time.
Non-Convex Optimization and Optimality
The research extends these findings to non-convex settings, which are critical for modern deep learning. The authors are the first to show that GT achieves the optimal convergence rate for stochastic gradients in non-convex problems, matching the best possible centralized methods.
Conclusion and Future Work
This work provides a theoretical foundation that aligns with the observed efficiency of Gradient Tracking in practice. By proving a linear rather than quadratic dependence on the network spectral gap, the authors demonstrate that GT is a robust choice for large, sparse networks.
Future research directions include extending this analysis to directed graphs (where communication may not be symmetric) and applying the "windowed contraction" technique to time-varying network topologies, where the connections between agents change dynamically during training.
Summary updated