IEEE Transactions on Information Theory · 2022 · 35 citations · 29 references
ComputingCommunicationComputer ScienceAlgorithmsInformation TheoryOptimizationCommunication ComplexityConvex OptimizationDistributed ComputingRandomized ComputationStochastic OptimizationCommunication Cost AnalysisConvergenceGradient DescentQuantizationRandomization SchemeRandomized OptimizationStochastic Gradient DescentVector Quantization
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: $Θ(\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.
29
Chih-Chung Chang, Chih‐Jen Lin · ACM Transactions on Intelligent Systems and Technology · 2011 · 41.3K citations
Deep Learning with Differential Privacy
Martı́n Abadi, Andy Chu, Ian Goodfellow et al. · 2016 · 5.9K citations · Full text
Federated Learning: Strategies for Improving Communication Efficiency
Jakub Konečný, H. Brendan McMahan, Felix X. Yu et al. · arXiv (Cornell University) · 2016 · 3K citations · Full text