Google Research

Breaking the Communication-Privacy-Accuracy Trilemma

Neural Information Processing Systems (NeurIPS) 2020, Neural Information Processing Systems (NeurIPS) 2020


Two major challenges in distributed estimation and learning are 1) preserving the privacy of the local samples; and 2) communicating them efficiently to a central server, while achieving high accuracy for the end-to-end task. While there has been significant interest in addressing each of these challenges separately in the recent literature, encoding mechanisms that simultaneously address both challenges are largely missing. In this paper, we develop novel encoding mechanisms that simultaneously achieve optimal privacy and communication efficiency in a large class of settings. In particular, we consider the problems of frequency estimation and mean estimation under $\varepsilon$-local differential privacy and $b$-bit communication constraints. For frequency estimation, we present a mechanism that leverages the recursive structure of Walsh-Hadamard matrices and achieves order-optimal $\ell_1$ and $\ell_2$ estimation error for \emph{all} privacy levels $\varepsilon = O\lp\log d \rp$ and communication budgets $b$, where $d$ is the support size. As a by-product, we also construct a distribution estimation mechanism that is rate-optimal for all privacy regimes and communication constraints, extending prior work that has been limited to $b=1$ and $\varepsilon=O(1)$. For $d$-dimensional mean estimation, we propose a scheme based on random rotation and sampling, with order-optimal (up to a logarithmic factor) $\ell_2$ estimation error under both constraints. Our results demonstrate that intelligent encoding under joint privacy and communication constraints can yield a performance that matches the optimal accuracy achievable under either constraint alone.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work