Timezone: »

Correlated Quantization for Distributed Mean Estimation and Optimization
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu

Tue Jul 19 11:35 AM -- 11:40 AM (PDT) @ Room 310

We study the problem of distributed mean estimation and optimization under communication constraints. We propose a correlated quantization protocol whose error guarantee depends on the deviation of data points instead of their absolute range. The design doesn't need any prior knowledge on the concentration property of the dataset, which is required to get such dependence in previous works. We show that applying the proposed protocol as a sub-routine in distributed optimization algorithms leads to better convergence rates. We also prove the optimality of our protocol under mild assumptions. Experimental results show that our proposed algorithm outperforms existing mean estimation protocols on a diverse set of tasks.

Author Information

Ananda Suresh (Google Research)
Ziteng Sun (Google Research)
Jae Ro (Google)
Felix Xinnan Yu (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors