Timezone: »

 
Poster
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
in Algorithms -- Large Scale Learning »

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.

Keywords: Information Theory · Communication- or Memory-Bounded Learning · Applications · Algorithms -> Large Scale Learning; Theory -> Computational Complexity; Theory
[ Paper]  [ Poster] 

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")

More from the Same Authors