Breaking the Communication-Privacy-Accuracy Trilemma

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.

• Machine Intelligence