Timezone: »

 
Poster
Communication-Efficient Distributed Learning of Discrete Distributions
Ilias Diakonikolas · Elena Grigorescu · Jerry Li · Abhiram Natarajan · Krzysztof Onak · Ludwig Schmidt

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #61
in Posters Tue »

We initiate a systematic investigation of distribution learning (density estimation) when the data is distributed across multiple servers. The servers must communicate with a referee and the goal is to estimate the underlying distribution with as few bits of communication as possible. We focus on non-parametric density estimation of discrete distributions with respect to the l1 and l2 norms. We provide the first non-trivial upper and lower bounds on the communication complexity of this basic estimation task in various settings of interest. Specifically, our results include the following: 1. When the unknown discrete distribution is unstructured and each server has only one sample, we show that any blackboard protocol (i.e., any protocol in which servers interact arbitrarily using public messages) that learns the distribution must essentially communicate the entire sample. 2. For the case of structured distributions, such as k-histograms and monotone distributions, we design distributed learning algorithms that achieve significantly better communication guarantees than the naive ones, and obtain tight upper and lower bounds in several regimes. Our distributed learning algorithms run in near-linear time and are robust to model misspecification. Our results provide insights on the interplay between structure and communication efficiency for a range of fundamental distribution estimation tasks.

Keywords: Information Theory · Learning Theory · Density Estimation · Frequentist Statistics · Computational Complexity
[ Paper] 

Author Information

Ilias Diakonikolas (USC)
Elena Grigorescu (Purdue University)
Jerry Li (Berkeley)
Abhiram Natarajan (Purdue University)
Krzysztof Onak (IBM T.J. Watson Research Center)
Ludwig Schmidt (MIT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors