Stochastic Distributed Learning with Gradient Quantization and Variance Reduction

MaRDI QIDQ6317002zbMATH OpenFDO

Authors Samuel Horváth, Dmitry P. Kovalev, Konstantin Mishchenko, S. U. Stich, Peter Richtárik

Publication date 10 April 2019

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 $omegageq1$ 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 $mathcalO((kappa+kappafracomegan+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 $mathcalO((kappa+kappafracomegan+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.

This page was built for publication: Stochastic Distributed Learning with Gradient Quantization and Variance Reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6317002)