Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation
zengfeng Huang, Ziyue Huang, Yilei WANG, Ke Yi
Abstract
We consider the problem of estimating the mean of a set of vectors, which are stored in a distributed system. This is a fundamental task with applications in distributed SGD and many other distributed problems, where communication is a main bottleneck for scaling up computations. We propose a new sparsity-aware algorithm, which improves previous results both theoretically and empirically. The communication cost of our algorithm is characterized by Hoyer's measure of sparseness. Moreover, we prove that the communication cost of our algorithm is information-theoretic optimal up to a constant factor in all sparseness regime. We have also conducted experimental studies, which demonstrate the advantages of our method and confirm our theoretical findings.
BibTeX
@inproceedings{NEURIPS2019_5b970a1d,
author = {Huang, zengfeng and Huang, Ziyue and WANG, Yilei and Yi, Ke},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/5b970a1d9be0fd100063fd6cd688b73e-Paper.pdf},
volume = {32},
year = {2019}
}