The Communication Complexity of Distributed Estimation

We research an extension of the usual two-party communication mannequin by which Alice and Bob maintain likelihood distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their purpose is to estimate

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

to inside additive error $varepsilon$ for a bounded perform $f$, identified to each events. We seek advice from this because the distributed estimation downside. Particular circumstances of this downside come up in quite a lot of areas together with sketching, databases and studying. Our purpose is to grasp how the required communication scales with the communication complexity of $f$ and the error parameter $varepsilon$.

The random sampling method — estimating the imply by averaging over $O(1/varepsilon^2)$

• † College of California, Los Angeles
• ‡ College of California, Berkeley
• § Institute for Superior Research (IAS)