Skip to yearly menu bar Skip to main content


Correlated Quantization for Distributed Mean Estimation and Optimization

Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu

Hall E #1111

Keywords: [ T: Everything Else ]


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.

Chat is not available.