vqSGD: Vector Quantized Stochastic Gradient Descent
- 23 March 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (7) , 4573-4587
Abstract
In this work, we present a family of vector quantization schemes 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 \left({\frac {d}{R^{2}}}\right)$ bits are necessary and sufficient (up to an additive $O(\log d)$ term) to describe an unbiased estimator $\hat{\boldsymbol {g}}(\boldsymbol {g})$ for any $\boldsymbol {g}$ in the $d$ -dimensional unit sphere, under the constraint that $\| \hat{\boldsymbol {g}}(\boldsymbol {g})\|_{2}\le R$ almost surely, $R > 1$ . 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 $o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using well-known families of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that vqSGD also offers automatic privacy guarantees.
Keywords
All Related Versions
Funding Information
- NSF (CCF 2127929, CCF 1934846, CCF 1909046)
This publication has 22 references indexed in Scilit:
- High-Dimensional Statistics2019
- Calibrating Noise to Sensitivity in Private Data AnalysisJournal of Privacy and Confidentiality, 2017
- Deep Learning with Differential Privacy2016
- Convex Optimization: Algorithms and ComplexityFoundations and Trends in Machine Learning, 2015
- RAPPOR2014
- Understanding Machine Learning2014
- LIBSVMACM Transactions on Intelligent Systems and Technology, 2011
- Boosting and Differential Privacy2010
- 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