vqSGD: Vector Quantized Stochastic Gradient Descent
Open accessThe DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
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: $Θ(\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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
Xiao, H., Rasul, K., & Vollgraf, R. (2017) · arXiv · doi:10.48550/arxiv.1708.07747 · Cited by 6,108
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000042 · Cited by 5,557
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
Warner, S. L. (1965) · Journal of the American Statistical Association · doi:10.2307/2283137 · Cited by 3,263
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115
Privacy-preserving deep learning
Shokri, R., & Shmatikov, V. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813687 · Cited by 2,356 · cited 1×
“While di ↵ erential privacy for gradient based algorithms [1, 30] were considered earlier in literature, cpSGD [4] is the only work that considered achieving di ↵ eren-tial privacy for gradient based algorithms and simultaneously minimizing the gradient communication cost.”
MethodRAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
Erlingsson, Ú., Pihur, V., & Korolova, A. (2014) · Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2660267.2660348 · Cited by 1,838
Boosting and Differential Privacy
Dwork, C., Rothblum, G. N., & Vadhan, S. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.12 · Cited by 784
signSGD: Compressed Optimisation for Non-Convex Problems
Bernstein, J., Wang, Y.-X., Azizzadenesheli, K., & Anandkumar, A. (2018) · arXiv · doi:10.48550/arxiv.1802.04434 · Cited by 541
Stich, S. U., Cordonnier, J.-B., & Jaggi, M. (2018) · arXiv · doi:10.48550/arxiv.1809.07599 · Cited by 508
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
A survey of federated learning for edge computing: Research problems and solutions
Xia, Q., Ye, W., Tao, Z., Wu, J., & Li, Q. (2021) · High-Confidence Computing · doi:10.1016/j.hcc.2021.100008 · Cited by 279
Privacy for Free: Wireless Federated Learning via Uncoded Transmission With Adaptive Power Control
Liu, D., & Simeone, O. (2021) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2020.3036948 · Cited by 234
Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning
Jhunjhunwala, D., Gadhikar, A., Joshi, G., & Eldar, Y. C. (2021) · ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp39728.2021.9413697 · Cited by 126
High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning
Du, Y., Yang, S., & Huang, K. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2983166 · Cited by 116
Metadata
- Authors
- Gandikota, V., Kane, D., Maity, R. K., & Mazumdar, A.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2022-07
- Volume
- 68
- Issue
- 7
- Pages
- 4573-4587
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2989787172
- Cited by
- 62
- References
- 15
- FWCI
- 2.67
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: vqSGD: Vector Quantized Stochastic Gradient Descent. https://app.cochat.ai/papers/10.1109/tit.2022.3161620
- The paper
- Gandikota, V., Kane, D., Maity, R. K., & Mazumdar, A. (2022). vqSGD: Vector Quantized Stochastic Gradient Descent. IEEE Transactions on Information Theory. https://doi.org/10.1109/tit.2022.3161620
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.