Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper addresses learning densities in Bezov space under communication constraints, primarily in a non-interactive setting. In fact, Theorems 1.1 and 1.3 together suggest that interaction may not help much in achieving a better performance. The proposed algorithms leverage wavelet-induced sparsity, vector quantization, and distributed (sample) simulation, but not the standard Fourier basis.  
main_review: Strengths

- The paper reads well, though I feel that the presentation of the appendices looks better than that of the submission. But the organization of the appendices is similar to journal papers. 
- The theoretical results seem to be a reasonable contribution to the topic. The upper and lower bounds almost match. The idea of leveraging wavelets' sparsity is also natural. Combining several techniques and showing the resulting algorithm works well seems nontrivial. 
- The fact that the lower bound also applies to the interactive setting is a plus to the paper's merits. 

Weaknesses

- It might be reasonable to provide a guide for the appendices. There are no explicit statements (in the main paper) about which section proves which result. For example, I wonder whether Theorem 3.3 on the simulation protocol of [3] is a new result or not. 
- Lines 114 - 119 state that the analysis in the paper draws upon ideas from [7] but differs from the latter, as [7] does not use techniques like distributed simulation. It seems reasonable to mention here that distributed simulation is also not a new idea and appears in [3].
- Line 133 mentioned that the lower bounds rely on the framework in [2]. I wonder if the authors can illustrate, on a high level, how different the extensions are from the original. 
- I am pretty interested in seeing how the proposed algorithms perform in practice. I suggest the authors conduct some experiments on synthetic or natural datasets.

Minor

- Line 289 is apparently under full. I suggest the authors adjust the equations accordingly. 



 
limitations_and_societal_impact: The results are mainly theoretical. I think the limitations are clear from the assumptions. I do not foresee any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies a quantization approach for nonparametric density estimation in the Besov space with communication constraints.
main_review: The proposed algorithm is the following: take the empirical coefficients and 1) if the number of coefficients (at the minimax wavelet cutoff level) is < communication constraint, suffering no quantization loss, and 2) if the number of coefficients is > communication constraint, use a simulate-and-infer approach to quantize the number of coefficients down to communication constraint.

I think the approach is reasonable and the theoretical analysis shows that the statistical rates are minimax optimal. I recommend acceptance.

I only have one comment: wavelet based approaches, similar to other methods that project to a family of basis functions, are convenient for theoretical analysis but usually not very practical because in practical the data are usually multi-variate and it is somewhat cumbersome to construct multivariate basis functions. Is it possible to design a communication efficient algorithm for some more practical methods, such as kernel smoothing or local polynomial regression?
limitations_and_societal_impact: See my main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This problem of estimating a density, assumed to lie in a Besov class, under communication constraints in which each sample must be encoded using a fixed number $\ell$ of bits before computing the density estimate. Both the non-adaptive and adaptive cases are considered, with matching upper and lower bounds (up to polylogarithmic factors) obtained in both cases. The matching bounds also indicate that the rate is the same for interactive and non-interactive protocols. The proposed methods utilizes 3 main ingredients:
1. The fact that at most a constant number of wavelets at resolution J are non-zero on any interval of width $2^{-J}$.
2. A particular randomized scheme that quantizes the values of the non-zero wavelets at a sample point without introducing bias.
3. The DISTRSIM protocol proposed by [3], which maps a quantized sample to a smaller IID sample of higher resolution.
main_review: Overall, this paper was quite well-written, and both the problem and its solution are well-motivated and interesting. My main criticism is that no experiments are performed. It would be interesting, for example, to know how large $n$ needs to be for the proposed method to outperform the "natural approach" (Lines 83-85). However, I think the paper makes a sufficiently strong theoretical contribution to be accepted even without experimental results.

Comments:
1) It's surprising to me that one can even estimate the density consistently as $n \to \infty$ if $\ell$ is fixed (using a non-interactive protocol). Fixing the number $\ell$ of bits from each sample, it seems like there would be some resolution $J$ below which it would not be possible to encode all of the possible bins into which the samples might fall. Certainly, I think the "natural approach" (Lines 83-85) would fail to converge for this reason. The trick to overcoming this seems to lie in the DISTRSIM protocol, since that produces arbitrarily many bits of each sample so long as $n$ is sufficiently large. It would be nice if the authors could discuss this further.

2) The current writing of the paper implicitly requires the reader to reference the supplement to understand several points.
I realize the paper is at the page limit, but It might be nice if some of these could be elaborated on in the main paper:
    1) Perhaps the definition of a Besov space should be given in the main paper rather than in the supplement, since a reader cannot really understand the paper without this. At very least, it should be noted in the main paper that the definition is given in the supplement.
    2) A brief description of how the DISTRSIM protocol works would be nice.
    3) In Section 4, a prior $\pi$ is mentioned but isn't described. In the supplement it looks like two different priors are used -- one uniform and one highly non-uniform. It would be nice if the authors could discuss the need for these two different priors, especially the non-uniform prior which isn't needed in the unconstrained setting.


-------AFTER READING AUTHOR REBUTTAL-------
I appreciate the points raised by other reviewers regarding the novelty and significance of the results, which rely heavily on prior work that is not very clearly explained (see my questions above). Since the authors did not answer my questions at all in the rebuttal, I have lowered my score from 8 to 7.
limitations_and_societal_impact: The assumptions underlying the paper's results are fairly clearly stated. The results are fairly comprehensive for the problem being studied, although additional discussion of room for future work would be nice. I don't foresee any potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposed a method for distributed density estimation with the unknown density from a Besov space. The estimation is based on local observations of independent samples drawn from a common distribution. The agents with local observations are connected via bit-constrained channels to a central unit ("referee"). The proposed method is based on a novel quantization strategy that exploits the properties of a wavelet expansion of the unknown density. The method is implemented as two algorithms, one which requires knowledge of Besov space parameter and another one which does not require precise Besov parameters. 

main_review: There should be more motivation for why it is useful to consider the extension from Hoelder to Besov spaces. Which application domains (e.g. wireless sensor networks) involve densities which belong to Besov but not to Hoelder spaces? I also suggest adding numerical experiments to showcase the usefulness of your methods compared to state-of-the art. 

I would like to have more discussion about the restrictiveness of the assumption of wavelet-induced sparsity as formulated in Claim 3.1. Also, i suggest renaming Claim 3.1 either as Assumption or as Corollary depending if this follows from other assumptions on the wavelet expansion or is an explicit assumption that you require to be fulfilled for your method. 

The considered communication setting seems quite simple. The paper mentioned federated learning as an application domain for density estimation. It would be interesting to discuss how the proposed methods could be extended to fully decentralized settings where each agent is participating equally in the estimation. Such a setting has been considered for parametric estimation recently in 

A. Jung, "Networked Exponential Families for Big Data Over Networks," in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.


The clarity/precision of the presentation could be improved: 

- a quick reminder about the defs for Hoelder and Besov spaces would be helpful for those who don't work with them on a daily basis. 

- The role of the last paragraph in Section 1.2. is not very clear. 

- in which sense is (4) to be understood ? pointwise (for each x) or w.r.t. some norm?

- ".. is an unbiased estimate of \alpha_{j,k} .." how is \alpha_{j,k} defined for j different from 0 ? 

- "...s lies in a certain range." what is this range?

- "Our proposed estimators draws upon these classical estimators.."  how exactly does it draw upon them ? 

- "As in the unconstrained setting ..."  i assume you mean for \ell -> infty ?

- include an outline paragraph in Section 1 where you give a plan of the paper and also make explicit how the different parts tie in together. E.g., What is the relation between Algorithm 1,2,3,4,5 ? 

- be more precise about inputs to Algorithms. E.g., Algorithm 2 uses a parameter "H", "\ell" and "\phi_{H,k}(.)" which seem to be input parameter. Or do you consider only one single choice for those throughout the entire paper. 

- ".. we form an approximately sufficient statistic ... can be represented using finite number of bits .." pls refer to the precise formula for this approximately sufficient statistic 

- the relevance of Theorem 3.3. is not very clear. I also suggest to write down DISTRSIM algorithm explicitly as it is a main building block of your methods. 


limitations_and_societal_impact: yes
review_title: null

Meta-review: The paper studies estimation of densities in Besov spaces in a distributed interactive setting with communication constraints.
The obtained estimator is nearly minimax optimal. This is a nice contribution to the literature on distributed adaptive density estimation.
I would encourage the authors to revise the paper to include the reviewers' comments into the final version of the manuscript.
Decision: Accept (Poster)