Stochastic Distributed Learning with Gradient Quantization and Variance Reduction

Abstract

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 $\omega \ge 1$ that might slow down convergence. For strongly convex functions with condition number $\kappa$ distributed among $n$ machines, we (i) give a scheme that converges in $\mathcal{O}((\kappa +\kappa \frac{\omega }{n}+\omega )$ $\log (1/\epsilon ))$ 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 $\mathcal{O}((\kappa +\kappa \frac{\omega }{n}+\omega +m)\log (1/\epsilon ))$ steps to arbitrary accuracy $\epsilon >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.

10 pages, 24 pages of Appendix

References in corpus (8)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• AIDE: Fast and Communication Efficient Distributed Optimization
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• ImageNet Training in Minutes
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses

Cited by in corpus (1)

• MISO is Making a Comeback With Better Proofs and Rates