Communication-Efficient Distributed Learning of Discrete Probability Distributions
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 1 and 2 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.
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.
1 Introduction
Summary; The paper studies the classical problem of estimating the probability mass function (pmf) of a discrete random variable given iid samples, but distributed among different nodes. The key quantity of interest is how much communication must be expended by each node (in a broadcast, but perhaps interactive, setting) to a central observer which then outputs the estimate of the underlying pmf. The main results of the paper areclearly stated and are  easy to follow.  The results mostly point out that in the worst case (i.e., no assumptions on the underlying pmf) there is nothing better for each node to do than to communicate its sample to the central observer. 
The paper addresses a central topic of a long line of recent works on distributed parameter estimation. The distinguishing feature here is to have as few parametric assumptions on the underlying distribution as possible. 
1. In the case when no assumption at all is made on the underlying distribution (other than the alphabet size), the main result is to show that essentially nothing better can be achieved than when all nodes communicate their raw samples (noninteractively) to the central observer. The upper bound is hence trivial and doesnt take much to analyze. The key innovation is in the lower bound where the authors consider a specific near-uniform distribution (where neighboring letters have probabilities that are parametrically (\delta_i in the notation of the paper) close to each other). Then the authors show that any (interactive) protocol allows the central observer to learn these \delta_i parameters and which itself is tantamount to learning the sample itself. The key calculation is to bound the mutual information between the transcripts and the \delta_i parameters which is then fed into a standard hypothesis testing framework (Fano's inequality). Although this machinery is standard, I found the setup of the hypothesis test creative and interesting and novel. Overall, this part of the paper is of fundamental interest (no assumptions at all on the underlying hypothesis) and nicely carried out. 
2. I am less sure about the two `structured' settings considered in this paper: k-histograms and monotone pmfs. I can imagine monotone pmfs coming up in some application domain, but far less sure about why k-histograms makes sense.  The main challenging aspect of this setting is that only k intervals are allowed, but their position is arbitrary. I understand the formulation makes for pretty math (and fits in nicely with a bunch of existing literature), but cannot  see any canonical/practical setting where allowing this flexibility makes sense. I would appreciate it if the authors can elaborate on this point in the rebuttal stage. 
3. In the context of the last sentence of the previous comment, I would also like to see some discussion by authors on any practical implications of this work. For instance the authors mention that the problem is very well motivated and cite some works from the literature [44, 40, 30, 54, 47]. Of these, I would guess that [47] is the only recent practical work (the others are either more than a decade old or also correspond to an already stylized setting) -- on this topic, can the authors please fix the reference [40] so that it includes its title? I would like to see concrete settings where the structured settings are motivated properly and the authors actually try out their algorithms (along with competing baselines) in that setting. In the context of this paper, I would like to see a (brief) discussion of how the settings might be related to the distributed computing revolution underlying modern data centers. Most NIPS papers  have a section where they discuss their  algorithms in the context of some concrete practical setting and report empirical results. 
3. The schemes proposed in the two structured settings are more sophisticated than the baseline one (where the nodes simply communicate their samples directly), but are directly motivated from their centralized counterparts. In particular, the k-histogram setting uses ideas from [3] and approximation in the \A_k norm and the monotone setting from the classical work of Birge. Overall, the proofs are correct and represent a reasonable innovation over a long line of work on this topic. 
Summary: I recommend this submission as far better suited to COLT or even SODA.