2022/02/08 by Anastasia Koloskova, Tao Lin, Sebastian U. Stich · 2 citations
Computer Science · Mathematics · #cs.DC #cs.LG #math.OC #msc:68W10 #msc:68W15 #msc:68W40 #msc:90C06 #msc:90C35 #acm:68W10 #acm:68W15 #acm:68W40 #acm:90C06 #acm:90C35
published as 35th Conference on Neural Information Processing Systems (NeurIPS 2021) · published at NeurIPS 2021
arxiv created 2022/02/08 · arxiv updated 2022/02/09
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 O(p-2) to O(p-1c-1) in the noiseless case and from O(p-3/2) to O(p-1/2c-1) in the general stochastic case, where c ≥ 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.