  We study the problem of distributed mean estimation and optimization under
communication constraints. We propose a correlated quantization protocol whose
leading term in the error guarantee depends on the mean deviation of data
points rather than only 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 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.
