Unbiased Quantization of the $L_1$ Ball for Communication-Efficient Distributed Mean Estimation

Nithish Suresh Babu, Ritesh Kumar, Shashank Vatedka
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:1270-1278, 2025.

Abstract

We study the problem of unbiased minimum mean squared error quantization of the $L_1$ ball, with applications to distributed mean estimation and federated learning. Inspired by quantization of probability distributions using types, we design a novel computationally efficient unbiased quantization scheme for vectors that lie within the $L_1$ ball. We also derive upper bounds on the worst-case mean squared error achieved by our scheme and show that this is order optimal. We then use this to design polynomial (in the dimension of the input vectors)-time schemes for communication-efficient distributed mean estimation and distributed/federated learning, and demonstrate its effectiveness using simulations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-babu25a, title = {Unbiased Quantization of the $L_1$ Ball for Communication-Efficient Distributed Mean Estimation}, author = {Babu, Nithish Suresh and Kumar, Ritesh and Vatedka, Shashank}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {1270--1278}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/babu25a/babu25a.pdf}, url = {https://proceedings.mlr.press/v258/babu25a.html}, abstract = {We study the problem of unbiased minimum mean squared error quantization of the $L_1$ ball, with applications to distributed mean estimation and federated learning. Inspired by quantization of probability distributions using types, we design a novel computationally efficient unbiased quantization scheme for vectors that lie within the $L_1$ ball. We also derive upper bounds on the worst-case mean squared error achieved by our scheme and show that this is order optimal. We then use this to design polynomial (in the dimension of the input vectors)-time schemes for communication-efficient distributed mean estimation and distributed/federated learning, and demonstrate its effectiveness using simulations.} }
Endnote
%0 Conference Paper %T Unbiased Quantization of the $L_1$ Ball for Communication-Efficient Distributed Mean Estimation %A Nithish Suresh Babu %A Ritesh Kumar %A Shashank Vatedka %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-babu25a %I PMLR %P 1270--1278 %U https://proceedings.mlr.press/v258/babu25a.html %V 258 %X We study the problem of unbiased minimum mean squared error quantization of the $L_1$ ball, with applications to distributed mean estimation and federated learning. Inspired by quantization of probability distributions using types, we design a novel computationally efficient unbiased quantization scheme for vectors that lie within the $L_1$ ball. We also derive upper bounds on the worst-case mean squared error achieved by our scheme and show that this is order optimal. We then use this to design polynomial (in the dimension of the input vectors)-time schemes for communication-efficient distributed mean estimation and distributed/federated learning, and demonstrate its effectiveness using simulations.
APA
Babu, N.S., Kumar, R. & Vatedka, S.. (2025). Unbiased Quantization of the $L_1$ Ball for Communication-Efficient Distributed Mean Estimation. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:1270-1278 Available from https://proceedings.mlr.press/v258/babu25a.html.

Related Material