vqSGD: Vector Quantized Stochastic Gradient Descent
Preprint
Abstract
In this work, we present a family of vector quantization schemes \emph{vqSGD} (Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic reduction in the communication cost with convergence guarantees in first-order distributed optimization. In the process we derive the following fundamental information theoretic fact: $\Theta(\frac{d}{R^2})$ bits are necessary and sufficient to describe an unbiased estimator ${\hat{g}}({g})$ for any ${g}$ in the $d$-dimensional unit sphere, under the constraint that $\|{\hat{g}}({g})\|_2\le R$ almost surely. In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a $d$-dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require only $o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using the properties of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that \emph{vqSGD} also offers strong privacy guarantees.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Stochastic distributed learning with gradient quantization and double-variance reductionOptimization Methods and Software, 2022
- RATQ: A Universal Fixed-Length Quantizer for Stochastic OptimizationIEEE Transactions on Information Theory, 2021
- Calibrating Noise to Sensitivity in Private Data AnalysisJournal of Privacy and Confidentiality, 2017
- The Algorithmic Foundations of Differential Privacy2013
- Trading Accuracy for Sparsity in Optimization Problems with Sparsity ConstraintsSIAM Journal on Optimization, 2010
- Simple Approximations of the Error Function Q(x) for Communications ApplicationsIEEE Transactions on Communications, 1979