The Communication Complexity of Distributed Estimation

We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate

$\mathbb{E}_{x \sim p, y \sim q}[f(x, y)]$

to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$.

The random sampling approach — estimating the mean by averaging over $O(1/\varepsilon^2)$

• † University of California, Los Angeles
• ‡ University of California, Berkeley
• § Institute for Advanced Study (IAS)