Thu, 10-Mar-2022 / 4:00pm / Zoom: https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ
Distributed mean estimation is a commonly used subroutine in many distributed learning and optimization algorithms. In several distributed scenarios, communication cost is a bottleneck and quantization techniques have been proposed to improve communication efficiency. However, existing techniques often suffer a quantization error scaling with the range of data points. We propose a new non-interactive correlated quantization protocol whose error guarantee depends on the deviation of data points instead of their absolute range. Furthermore, our algorithm and analysis does not make any distribution assumptions or require any prior knowledge on the concentration property of the data. We prove the optimality of our protocol under mild assumptions and also show that applying it as a subroutine in distributed optimization leads to better convergence rates.
Based on joint work with Jae Ro, Ziteng Sun, and Felix Yu.
Ananda Theertha Suresh is a research scientist at Google Research, New York. He received his PhD from University of California San Diego, where he was advised by Prof. Alon Orlitsky. His research focuses on theoretical and algorithmic aspects of machine learning, information theory, differential privacy, and statistics. He is a recipient of the 2017 Paul Baran Maroni Young Scholar award and a co-recipient of best paper awards at NeurIPS 2015, ALT 2020, CCS 2021, and a best paper honorable mention award at ICML 2017.
Packard Building
Electrical Engineering Department
350 Jane Stanford Way
Stanford, CA 94305-9515
Thursdays, 4pm, Packard 202
