Unbiased Quantization of the $l_1$ Ball for Communication-Efficient Distributed Mean Estimation
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
Text
Babu et al. "Unbiased Quantization of the $l_1$ Ball for Communication-Efficient Distributed Mean Estimation." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Babu et al. "Unbiased Quantization of the $l_1$ Ball for Communication-Efficient Distributed Mean Estimation." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/babu2025aistats-unbiased/)BibTeX
@inproceedings{babu2025aistats-unbiased,
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},
year = {2025},
pages = {1270-1278},
volume = {258},
url = {https://mlanthology.org/aistats/2025/babu2025aistats-unbiased/}
}