Timezone: »
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")
More from the Same Authors
-
2022 Poster: Lipschitz Bandits with Batched Feedback »
Yasong Feng · zengfeng Huang · Tianyu Wang -
2023 Poster: Adversarially Robust Distributed Count Tracking via Partial Differential Privacy »
Zhongzheng Xiong · Xiaoyi Zhu · zengfeng Huang -
2023 Poster: Rethinking Semi-Supervised Imbalanced Node Classification from Bias-Variance Decomposition »
Divin Yan · Gengchen Wei · Chen Yang · Shengzhong Zhang · zengfeng Huang -
2022 Spotlight: Lipschitz Bandits with Batched Feedback »
Yasong Feng · zengfeng Huang · Tianyu Wang -
2022 Spotlight: Lightning Talks 2A-1 »
Caio Kalil Lauand · Ryan Strauss · Yasong Feng · lingyu gu · Alireza Fathollah Pour · Oren Mangoubi · Jianhao Ma · Binghui Li · Hassan Ashtiani · Yongqi Du · Salar Fattahi · Sean Meyn · Jikai Jin · Nisheeth Vishnoi · zengfeng Huang · Junier B Oliva · yuan zhang · Han Zhong · Tianyu Wang · John Hopcroft · Di Xie · Shiliang Pu · Liwei Wang · Robert Qiu · Zhenyu Liao -
2022 Poster: SeqPATE: Differentially Private Text Generation via Knowledge Distillation »
Zhiliang Tian · Yingxiu Zhao · Ziyue Huang · Yu-Xiang Wang · Nevin L. Zhang · He He -
2022 Poster: Transformers from an Optimization Perspective »
Yongyi Yang · zengfeng Huang · David P Wipf -
2022 Poster: Differentially Private Covariance Revisited »
Wei Dong · Yuting Liang · Ke Yi -
2021 Poster: Understanding Bandits with Graph Feedback »
Houshuang Chen · zengfeng Huang · Shuai Li · Chihao Zhang -
2021 Poster: BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation »
Mingguo He · Zhewei Wei · zengfeng Huang · Hongteng Xu -
2021 Poster: Instance-optimal Mean Estimation Under Differential Privacy »
Ziyue Huang · Yuting Liang · Ke Yi