Timezone: »

Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation
zengfeng Huang · Ziyue Huang · Yilei WANG · Ke Yi

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #31

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.

Author Information

zengfeng Huang (Fudan University)
Ziyue Huang (HKUST)
Yilei WANG (The Hong Kong University of Science and Technology)
Ke Yi (" Hong Kong University of Science and Technology, Hong Kong")