We examine an extension of the usual two-party communication mannequin during which Alice and Bob maintain chance distributions and over domains and , respectively. Their objective is to estimate
to inside additive error for a bounded operate , recognized to each events. We confer with this because the distributed estimation drawback. Particular circumstances of this drawback come up in a wide range of areas together with sketching, databases and studying. Our objective is to grasp how the required communication scales with the communication complexity of and the error parameter .
The random sampling strategy — estimating the imply by averaging over random samples — requires whole communication, the place is the randomized communication complexity of . We design a brand new debiasing protocol which improves the dependence on to be linear as an alternative of quadratic. Moreover we present higher higher bounds for a number of particular lessons of capabilities, together with the Equality and Better-than capabilities. We introduce decrease sure methods based mostly on spectral strategies and discrepancy, and present the optimality of lots of our protocols: the debiasing protocol is tight for common capabilities, and that our protocols for the equality and greater-than capabilities are additionally optimum. Moreover, we present that amongst full-rank Boolean capabilities, Equality is basically the best.
- † College of California, Los Angeles
- ‡ College of California, Berkeley
- § Institute for Superior Research (IAS)
