Wyner-Ziv Estimators: Efficient Distributed Mean Estimation with Side-Information

Prathamesh Mayekar, Ananda Theertha Suresh, Himanshu Tyagi
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:3502-3510, 2021.

Abstract

Communication efficient distributed mean estimation is an important primitive that arises in many distributed learning and optimization scenarios such as federated learning. Without any probabilistic assumptions on the underlying data, we study the problem of distributed mean estimation where the server has access to side information. We propose \emph{Wyner-Ziv estimators}, which are efficient and near-optimal when an upper bound for the distance between the side information and the data is known. In a different direction, when there is no knowledge assumed about the distance between side information and the data, we present an alternative Wyner-Ziv estimator that uses correlated sampling. This latter setting offers universal recovery guarantees, and perhaps will be of interest in practice when the number of users is large, where keeping track of the distances between the data and the side information may not be possible.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-mayekar21a, title = { Wyner-Ziv Estimators: Efficient Distributed Mean Estimation with Side-Information }, author = {Mayekar, Prathamesh and Theertha Suresh, Ananda and Tyagi, Himanshu}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {3502--3510}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/mayekar21a/mayekar21a.pdf}, url = {https://proceedings.mlr.press/v130/mayekar21a.html}, abstract = { Communication efficient distributed mean estimation is an important primitive that arises in many distributed learning and optimization scenarios such as federated learning. Without any probabilistic assumptions on the underlying data, we study the problem of distributed mean estimation where the server has access to side information. We propose \emph{Wyner-Ziv estimators}, which are efficient and near-optimal when an upper bound for the distance between the side information and the data is known. In a different direction, when there is no knowledge assumed about the distance between side information and the data, we present an alternative Wyner-Ziv estimator that uses correlated sampling. This latter setting offers universal recovery guarantees, and perhaps will be of interest in practice when the number of users is large, where keeping track of the distances between the data and the side information may not be possible. } }
Endnote
%0 Conference Paper %T Wyner-Ziv Estimators: Efficient Distributed Mean Estimation with Side-Information %A Prathamesh Mayekar %A Ananda Theertha Suresh %A Himanshu Tyagi %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-mayekar21a %I PMLR %P 3502--3510 %U https://proceedings.mlr.press/v130/mayekar21a.html %V 130 %X Communication efficient distributed mean estimation is an important primitive that arises in many distributed learning and optimization scenarios such as federated learning. Without any probabilistic assumptions on the underlying data, we study the problem of distributed mean estimation where the server has access to side information. We propose \emph{Wyner-Ziv estimators}, which are efficient and near-optimal when an upper bound for the distance between the side information and the data is known. In a different direction, when there is no knowledge assumed about the distance between side information and the data, we present an alternative Wyner-Ziv estimator that uses correlated sampling. This latter setting offers universal recovery guarantees, and perhaps will be of interest in practice when the number of users is large, where keeping track of the distances between the data and the side information may not be possible.
APA
Mayekar, P., Theertha Suresh, A. & Tyagi, H.. (2021). Wyner-Ziv Estimators: Efficient Distributed Mean Estimation with Side-Information . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:3502-3510 Available from https://proceedings.mlr.press/v130/mayekar21a.html.

Related Material