An Improved Analysis of Gradient Tracking for Decentralized Machine\n Learning

Abstract

We consider decentralized machine learning over a network where the training\ndata is distributed across $n$ agents, each of which can compute stochastic\nmodel updates on their local data. The agent's common goal is to find a model\nthat minimizes the average of all local loss functions. While gradient tracking\n(GT) algorithms can overcome a key challenge, namely accounting for differences\nbetween workers' local data distributions, the known convergence rates for GT\nalgorithms are not optimal with respect to their dependence on the mixing\nparameter $p$ (related to the spectral gap of the connectivity matrix).\n We provide a tighter analysis of the GT method in the stochastic strongly\nconvex, convex and non-convex settings. We improve the dependency on $p$ from\n$\\mathcal{O}(p^{-2})$ to $\\mathcal{O}(p^{-1}c^{-1})$ in the noiseless case and\nfrom $\\mathcal{O}(p^{-3/2})$ to $\\mathcal{O}(p^{-1/2}c^{-1})$ in the general\nstochastic case, where $c \\geq p$ is related to the negative eigenvalues of the\nconnectivity matrix (and is a constant in most practical applications). This\nimprovement was possible due to a new proof technique which could be of\nindependent interest.\n