2019/04/10 by Samuel Horváth, Dmitry Kovalev, Horváth, Samuel +7 · 14 citations
Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1904.05115
We consider distributed optimization where the objective function is spread among different devices, each sending incremental model updates to a central server. To alleviate the communication bottleneck, recent work proposed various schemes to compress (e.g. quantize or sparsify) the gradients, thereby introducing additional variance ω≥ 1 that might slow down convergence. For strongly convex functions with condition number κ distributed among n machines, we (i) give a scheme that converges in O((κ+ κ\fracωn + ω) log (1/ε)) steps to a neighborhood of the optimal solution. For objective functions with a finite-sum structure, each worker having less than m components, we (ii) present novel variance reduced schemes that converge in O((κ+ κ\fracωn + ω+ m)log(1/ε)) steps to arbitrary accuracy ε> 0. These are the first methods that achieve linear convergence for arbitrary quantized updates. We also (iii) give analysis for the weakly convex and non-convex cases and (iv) verify in experiments that our novel variance reduced schemes are more efficient than the baselines.