vqSGD: Vector Quantized Stochastic Gradient Descent

By V. Gandikota, Daniel Kane, Raj Kumar Maity, Arya Mazumdar. 2022

136 citations recorded by the source corpus.

In this work, we present a family of vector quantization schemes <italic>vqSGD</italic> (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: <inline-formula> <tex-math notation="LaTeX">$\Theta \left({\frac {d}{R^{2}}}\right)$ </tex-math></inline-formula> bits are necessary and sufficient (up to an additive <inline-formula> <tex-math notation="LaTeX">$O(\log d)$ </tex-math></inline-formula> term) to describe an unbiased estimator <inline-formula> <tex-math notation="LaTeX">$\hat{\boldsymbol {g}}(\boldsymbol {g})$ </tex-math></inline-formula> for any <inline-formula> <tex-math notation="LaTeX">$\boldsymbol {g}$ </tex-math></inline-formula> in the <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>-dimensional unit sphere, under the constraint that <inline-formula> <tex-math notation="LaTeX">$\| \hat{\boldsymbol {g}}(\boldsymbol {g})\|_{2}\le R$ </tex-math></inline-formula> almost surely, <inline-formula> <tex-math notation="LaTeX">$R > 1$ </tex-math></inline-formula>. In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>-dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require <inline-formula> <tex-math notation="LaTeX">$o(d)$ </tex-math></inline-formula> 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 <italic>vqSGD</italic> also offers automatic privacy guarantees.

Subfields: Artificial Intelligence, Computational Mechanics, Efficiency & Compression, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Efficiency & Compression

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “It is therefore worthwhile to evaluate these data-dependent compression schemes in the federated settings [171].”
Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, methodology): “Distributed mean estimation and its use in training learning models has been studied extensively in the literature (see [SYKM17, AGL + 17, GKMM19, MT20] and references therein).”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “However, if we further apply RandomSampling to b bits, by Theorem 6 in [8], the 2 estimation error grows as”
rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, background): “Such convergence guarantees have been proven in [6], [15], [26], [27] for various communication efficient training techniques.”
Limits on Gradient Compression for Stochastic Optimization (2020, background): “However, the quantizers in [14] are designed keeping in mind other objectives and they fall short of attaining the optimal precision guarantees of SimQ and SimQ+.”
High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning (2020, methodology): “1After submission of this work for publication, we noticed a parallel work on VQ for stochastic gradients as reported in [8], where a gradient is quantized using an unbiased random quantizer.”
Federated Learning in Edge Computing: A Systematic Survey (2022, background): “SGDs with reduced variance and quantized SGDs with reduced variance [171] are also essential.”
Lossless Compression of Efficient Private Local Randomizers (2021, background): “Thus reducing the communication cost of mean estimation has been studied in many works with (Agarwal et al., 2018; Girgis et al., 2020; Chen et al., 2020; Gandikota et al., 2019) or without privacy (Alistarh et al.”