Optimal Rates for Nonparametric Density Estimation under Communication Constraints
Authors: Jayadev Acharya
Clement Louis Canonne
Aditya Vikram Singh
Himanshu Tyagi
Venue: NeurIPS 2021 Poster (2021)
Keywords: density estimation
communication constraints
nonparametric inference
distributed algorithms

Abstract: We consider density estimation for Besov spaces when the estimator is restricted to use only a limited number of bits about each sample. We provide a noninteractive adaptive estimator which exploits the sparsity of wavelet bases, along with a simulate-and-infer technique from parametric estimation under communication constraints. We show that our estimator is nearly rate-optimal by deriving minmax lower bounds that hold even when interactive protocols are allowed. Interestingly, while our wavelet-based estimator is almost rate-optimal for Sobolev spaces as well, it is unclear whether the standard Fourier basis, which arise naturally for those spaces, can be used to achieve the same performance.

Optimal Rates for Nonparametric Density Estimation under Communication Constraints
Jayadev Acharya
Clément L. Canonne
Aditya Vikram Singh
Corelll University
University of Sydney
Indian Institute of Science
Ithaca, USA
Sydney, Australia
Bangalore, India
acharya@cornell.cm edu
c.eeentt.anomme@eyddng Gannone@@synneyeeduie edu.au au
clement.
adityavs@iisc iscc..iiss..... .cc.scc........ in
Himanshu Tyagi
Indian Institute of Science
Bangalore, India
atyagi@iisc..ac.it
Abstract
We consider density estimation for Besov spaces when the estimator is restricted use only limited number of bits about each sample. We provide a noninteractive adaptive estimator which exploits the sparsity of wavelet bases, along with simulate-and-infer technique from parametric estimation under communication constraints. We show that our estimator is nearly rate-optimal by deriving minmax lower bounds that hold even when interactive protocols are allowed. Interestingly, while our wavelet-based estimator almost rate-optimal for Sobolev spaces well, it is unclear whether the standard Fourier basis, which arise naturally for those spaces, can be used achieve the same performance.
Introduction
Estimating distributions from samples is fundamental statistical task. Modern applications. such as those arising in federated learning or the Internet of Things (IoT), often limit access the true data samples. One common limitation in large scale distributed systems is communication constraints, which require that each data sample must be compressed small number of bits.
Most prior work on communication-constre such as Gaussian mean estimation and discrete distribution estimation. In this work, study nonparametric density estimation under communication constraints where independent samples from unknown distribution (whose density lies in function class) are distributed across players (one sample per player), and each player can only send bits about its sample to a central referee; the referee outputs an estimate of based on these b-bit messages. This problem has been considered before by [5] for densities in Hölder class HJ, ([0, 1J) (functions supported on [0. 1] relatively simple class for which the normalized histogram with uniform bins is known to be optimal in the centralized setting. This suggests natural method for distributed setting quantize each data sample into uniform bins and use the optimal estimator for distributed discrete distribution estimation. Indeed, [5] shows that this is optimal for distributed estimation of densities from the Hölder class under communication constraints. However, this simple estimator does not seem extend to the richer Sobolev class and most general Besov classes. particular, the following question is largely open:
estimation has focused on parametric problems
satisfying [z) f()) S L/r y/ for every x, y [0, 1).. which
How quantize samples to estimate densities from Besov classes under communication constraints?
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We resolve this question both when the density belongs to Besov class with known parameters (nonadaptive setting), and when the density belongs to a Besov class where only upper and lower bounds on parameters are known (adaptive setting). Specifically, our proposed estimators exploit the sparsity of wavelet basis for the Besov class, and use vector quantization followed by the distributed simulation technique introduced in [3] for distributed parametric estimation. We also establish lower bounds that prove the optimality of our estimators (up to logarithmic terms in the adaptive setting).
1.1 Problem setup
X1 Xi....,Xy, Xn are independent samples from an unknown distribution with density f supported on X' := [0, 1] and belonging to the Besov space B(p, s) (see Section 2 for details). There are n distributed users (players), with player-i having access sample X,. Each player can only transmit & bits about its sample to a central server (referee) whose goal, upon observing b-bit messages from n players, to estimate f. We consider an interactive setting, where the current player observes the messages from previous players and can use them to design its message. That is, in round i, player-i chooses a communication-constii constrained channel (randomized mapping) W,: X - {0, 13 as function of prior messages .i,...: Y and randomness U available to all players; it then passes X; through W; to generate Y, {0, 13². The referee observes the messages Vi...., Y, and outputs an estimate f of f. We term such an an (n, E)-esimaate; let En,e denote the set of all (n, -)-esimmates. Our goal is to design estimators that achieve the minmax expected L, loss defined, for 2 1, by
(n,
inf sup fEE.. fEB(p.q..)
Ey [II 1
For upper bounds on C (n, l, g. 8), we consider algorithms that use the more restricted nonin- teractive protocols, where the channel W, of player-i is not allowed to depend on the messages Yi...., Y or on the common randomness U, but may depend on the private randomness U; available at player-i, where U,, Un are independent of each other and jointly of U. Noninteractive protocols are easier to implement and result in much simpler engineering for the distributed system.
1.2 Our results and techniques
Our first result is information-theorrtic lower bound on CT Theorem 1.1. For any p. 9, s,r, there exist constants C C(p.q, 0, a(p.q,s,r) such that
re mn /47 (n2²)
}.
r S (s + 1)p,
ria 1/mt1/r)
(. C.
max(n 2efI, (n2²)
20 1/D12
(log n2") }0
r E ((s + 1)p, (2s + 1)p)
L/y1 1/r2
1/24s/m) 1/5112
max {
2(-- 1/p)+1
(n22
(logn2²) "
2 (2s 1)p.
Tog
We emphasize that this lower bound even applies interactive protocols defined in Section 1.1. When the parameters p. q, s of the Besov space are known, we design a noninteractive estimator that achieves the optimal rate when S p.
Theorem 1.2. For any 2 1 and p. q. s with p. there exists constant C s,p,,,,sr) and an (n, -)eetimate i formed using a noninteractive protocol such that
E, [111--111 -1].]] 5C mmx(fn" 2041, (n2²) 2012
sup SEB(p.g.a)
We finally design adaptive, noninteractive estimator that only requires bounds on and further knowledge of and q. Moreover, this estimator achieves (up to logarithmic factors) the optimal rate for all parameter values.
Theorem 1.3. For any N E N. 2 1, and p, 4 with 1/p < < N, there exist constants C ((p.9,8,r), alp, (,,0,,88,)) 8) and an (n, E)-stimmmete î formed using a noninteractive protocol
Since lower bounds rely general results in [2], borrow the notation from that paper.

---

such that
max 2011, (n2²)
2042
r S (s + 1)p,
sup SEB(p.q.5) 15 [[[ /11.] C' C'log" n. max -F21 (n2²)
-le-1/pt1/m
1/)+
r E ((s + 1)p, (2s + 1)p),
-la-i/po1/m)
1/l11/)
max 2(a-1/p) (n22)
12-0
r 2 (2s 1)p.
where the protocol only requires knowledge of N (an upper bound 8). In summary, for all r 2 1, the minmax C, loss of estimating B(p, q, s) (up to logarithmic factors) is
maxfn n Z (n2²)
r S (s + 1)p, E ((s + 1)p, (2s + 1)p), (2)
ric- /c/ 2(1-1/p)+2
max (n" I (n22)
max
ris- 1/pt2/r)
2to 17p)
(n22)
2(0-1/2142
(2s 1)p.
It it worth noting that the first term of the maximum in all cases is the standard, unconstrained nonparametric rate (cf. [10], or the discussion below), while the second term reflects the convergence slowdown due to the communication constraints. The effect of communication constraints disappears when l is sufficiently large. In particular, we get back the centralized rates when & satisfies
2s+1 log n,
ifr S (s 1)p, log n. if ((s 1)p, (2s 1)p),
22
2a(1-1/f (2s IJlo 1//+1/r)
2s+1
logn, n,
if > (2s + 1)p.
2/3-1/
For the standard case of L2 loss, with, say p 2 2, the minmax rate becomes the more interpretable quantity
C5 x max(n zitr (n2²)
where we see that the b-bit communication constraint reduces the exponent of the convergence rate from 24 Z+4I to 28+2. Note that the difference becomes less perceptible as grows, or 8 tends to co.
Finally, from (2) we observe qualitative changes at r = (s + 1)p and r = (2s + 1)p, where the rate exponent changes slope. This phenomenon, whose analogue is observed in the unconstrained setting [10] as well as under local privacy constraints [7], is sometimes referred to as an elbow effect.
Quantize, simulate and infer. A conceptually simple technique for distributed estimation under communication constraints ("simulate-and-infer was proposed [3], which uses communication to simulate samples from the unknown distribution, and provides optimal rate estimator for discrete distribution estimation under communication constraints. A natural approach for nonparametric estimation would be to quantize the samples to the available number of bits (e) and use this quantized sample to estimate the distribution. However, is unclear if this approach gives optimal rates. Instead, in our approach, form an approximately sufficient statistic (based on wavelets) that can be represented using finite bits and does not result in rote- The number of bits could still be more than l, and therefore, we use simulate-and and-ifer to generate samples from the statistic. Thus, loss of information due to communication constraints only happens in the last step, when use multiple samples to simulate sample from the sufficient statistic; the quantization part is just for efficient finite representation.
quantize without inducing any "loss of information." " Specifically, we
Sobolev spaces and Fourier bases. A first approach that we tried for Sobolev spaces was to use the Fourier basis, a natural choice for a Sobolev space. However, all our attempts led to a suboptimal performance either in the dependence on é (we were not able to get the exponential 2- dependence) or the exponent of n (i.e., when we tried to get 2 dependence, this resulted in a suboptimal exponent of n). Somewhat surprisingly, the more general wavelet-based approach described above gives us tight bounds for Sobolev space as well, since Sobolev space S(3) = B(,, .9.. Thus, it seems that it for Sobolev spaces to get appropriately "small"
is necessary to use the wavelet representation statistic - sparsity of wavelets is very useful for inference under communication constraints.
Organization. After discussing prior works (Section 1.3) and preliminaries (Section 2), we describe our estimation algorithms in Section 3. In Section 3.1, we present the nonadaptive single-level estimator (comprising Algorithm 2 and Algorithm 3), which achieves guarantees of Theorem 1.2
3

---

(proof in Appendix B). In Section 3.2, we present the adaptive multi-level estimator (comprising Algorithm and Algorithm 5), which achieves guarantees of Theorem 1.3 (proof in Appendix C). Finally, in Section 4, we briefly discuss our approach to proving lower bounds of Theorem 1.1, with details deferred to Appendix D. Appendices can be found the Supplementary.
1.3
Prior work
The seminal work of Donoho, Johnstone, Kerkyacharian, and Picard [10] proposed wavelet estimators for Besov class in the centralized setting, and showed that these estimators achieve near-optimal rates of convergence (up to logarithmic factors),
n
r < (2s + 1)p,
(n, (o,2,
(3)
n2
r 2 (2s + 1)p.
Their results highlight the fact that linear estimators are inherently suboptimal for estimation with respect to L, losses, when r is large; that is, some nonlinearity in the estimator is required to achieve optimal rates for p. In particular, they show that nonlinearity in the form of thresholding achieves optimal rates for r > p (see Section 2 below for details). Further, they use thresholding to design adaptive estimators that achieve near-optimal rates. These minmax rates exhibit the aforementioned elbow effect, where the eπror exponent is only piecewise linear, and changes slope at = (2s + 1)p. We refer the reader to [10] for further discussion of these phenomena.
Butucea, Dubois, Kroll, and Saumard [7] recently extended these ideas to obtain near-rate optimal estimators for Besov spaces under local differential privacy constraints. Their adaptive estimator, as well as the information-theoreiic lower bounds they establish, show that similar phenomena occur in the context of locally private nonparametric estimation. Our work, specifically the analysis of our adaptive estimator, draws upon some of the ideas of [7], with some crucial differences. In particular, the key ideas underlying our estimators- the wavelet-induced sparsity (Claim 3.1), the use of distributed simulation, and vector quantization are neither present in nor applicable to the setting of [7] (where the introduction of random noise to ensure differential privacy effectively removes wavelet sparsity). Furthermore, our lower bounds even apply to interactive protocols, unlike the lower bounds from [7] which are restricted to the noninteractive setting.
In summary, our paper is the first to derive the counterpart of the nonparametric estimation results of [10, 7] under communication constraints, and shows that the analogue of the phenomena observed in [10] holds in the communication-consseee
setting.
Other work on distributed estimation. We briefly discuss the related literature on distributed coamuunication-conttaainni estimation problems. [18. 15, 16, 8] have studied the problem of distributed nonparametric function estimation (regression) under a Gaussian white noise model in noninteractive setting with n players, where each player observes an independent copy of the stochastic process dY = (t) + (L/VN)dW (t). st 1. Here W(t) is the standard Wiener process, and f is the function to be estimated. [18] derive minimax rates for ff in Sobolev space under Cg loss, where each player can send most f bits. [15] derive minimax rates for f in the Besov space B(2, oo. s) ("Sobolev type") under C2 loss, and f in B(oo, 00, s) ("Hölder type") under L loss, where each player can send at most é (assumed to be at least log N) bits on average. Further, the paper proposes near-optimal adaptive estimators (based on Lepski's 's method) that adapt to the smoothness parameter s. provided that E [Smin. $max). where Smin depends on n, l and Smax can be arbitrary. [16] further study the problem of adaptivity for B(2, co, 5) under Le loss and B(xo, oo, 8) under Lox loss, and answer the question of whether is possible to design adaptive estimators (adapting to the smoothness parameter s) that attain centralized minimax rates while also having the expected communication budget nearly the same as that of a minimax optimal distributed estimator that knows The paper shows that this is possible for (22,, oo, s) under L2 loss provided that is below certain threshold, and is impossible for B(oo, oo, s) under Loo loss. [8] derive minimax rates for f in Besov spaces B(p, g, s) (for p > 2) under Lg loss, where each player can send at most É bits on average. In addition, they study the problem of adaptivity and characterize the minimax communication budget of adaptive estimators (adapting to parameters p 2 2, > 1, > 0) that achieve centralized rates. The adaptive estimator proposed in this paper is based on thresholding, where the thresholding is done locally by each player.
Interestingly, when the communication budget l insufficient to achieve centralized rates, the minimax rates in these distributed nonparametric function estimation problems decay polynomially in

---

i, which is in contrast to the minimax rates we obtain for distributed nonparametric density estimation problem, where the decay exponential in
For higher dimensions, [13] consider two-party estimation of Hölder smooth density functions in d dimensions, where the two parties each observe subset of coordinates and must communicate to estimate the density. They show that interactivity strictly helps over one-way communication.
We now discuss related works distributed parametric estimation problems. [5] establish lower bounds on parametric density estimation, and on some restricted nonparametric families (Hölder classes) by bounding the Fisher information. [3] obtain upper and lower bounds for discrete distribu- tion estimation; our algorithms leverage the concept of distributed simulation ("simulate-ande "iimulat--nndinnfer") introduced in that context. [12] derive lower bounds for various parametric estimation tasks, including discrete distributions and continuous (parametric) families such as high-dimensional Gaussians (including the sparse case). [2], building [1] (which focused learning and testing discrete distri- butions), developed a general technique to prove estimation lower bounds for parametric families; our lower bounds rely on their framework, by suitably extending handle the nonparametric case.
We note that there are other approaches for establishing lower bounds under communication con- straints such as the early works [17]. [14]; [11, 6]. where bounds for specific inference problems under communication constraints were obtained; and [4], where Cramér-Rao bounds for this setting were developed. We found the general approach of [2] best fits our specific application, where we needed to handle interactive communication as well as nonuniform prior on the parameter in the lower bound construction.
2 Preliminaries
Given two integers m S n, we write [m, n] for the set {m, m m........ n) and [n] for [1.n] For two sequences or functions (an).. (bn)n: we write S bn if there exists a constant C > 0 (independent of n) such that an I Cb, for all n, and an bn if both an S bn and an 2 bn- For a function g. supp(g) denotes the support of
Let B(p, q; s) be the Besov space with parameters p. q, where < p.q S Do and 0. We will write Ø, wh E (TR). respectively, for the father and mother wavelets generating the basis of the Besov space, and Ilfll for the Besov norm of (pp, q, s). We refer the reader Appendix A in Supplementary for details on wavelets, Besov spaces and Besov norm.
Assumptions on the density and wavelets. We make the following assumptions on the density f:
1. f is compactly supported: without loss of generality, supp(f) S [0, 1].
2. Besov norm of f is bounded: without loss of generality, II S 1.
Our algorithm works with any father and mother wavelets and v satisfying the following conditions:
1. & and s are N-regular, where N > s, and
2. supp(o), S A A] for some integer A > 0 (which may depend on N).
As concrete example, Daubechies' family of wavelets [9] satisfies these assumptions.
Density estimation in centralized setting, In the centralized setting, XI...., X, from an unknown density f B(p, s) are accessible to the estimator. Let the wavelet expansion of f be (see Appendix A.1 for details)
Σ 00, + >E B3,
(4)
REZ
120KER KEZ
where (z)(2)) = 20/2 k), (z) 2/ixxb(2xx k). The wavelet basis satisfies the HH H-1
property that, for any L, H E Z with H L, we have Σxez 0L, + Eø=t Σvez B
ELez &HH (Fact A.1 in Supplementary). Note that for a given j, k. ā := E H5
an unbiased estimate of o.j.k Thus, for some H E Z+, estimate of is
fum
âH EáHNoH KEZ
Σ (H.)
(5)
n
5

---

where H is chosen depending on n and parameters p. to minimize the (worst-case) C, loss. This simple estimator (with appropriate choice of H) is rate-optimal when 1 1 r S p, but is sub-optimal when >> [10]. Moreover, setting H requires knowing the Besov parameters p, Q. which renders this estimator nonadaptive. The main contribution of [10] was to demonstrate that thresholding leads to estimators that are (i) near-optimal for every 2 1; (ii) adaptive, in the sense that the estimator does not use the values parameters p, g, as long as 1/p < < N for some N E N. For a given L, H. E Z4, L < H, thresholded estimator outputs the estimate
fthresh COLLOLA jEL
ΣΣ
B
By =B, (18,41241
(6)
where &L, == + (X,), 3, = , 4g and ty is a fixed threshold proportional to jjnn: here, L, H depend on n, but not parameters p, Our proposed estimators draws upon these classical estimators.
Estimation Algorithms
We propose algorithms for density estimation under communication constraints that achieve optimal/near-opimaal performance in terms of n (number of players) and & (number of bits each player can send). Designing density estimator in the communicatioon-constrnnnnd setting consists of: (i) specifying the sample-dependent ê-bit message that a player sends to the referee; (ii) specifying the density estimate that the referee outputs based the ê-bit messages from the players. As in the unconstrained setting, we estimate f by estimating its wavelet coefficients.
Our estimators consist of three ingredients: wavelet-induced sparsity, vector quantization, and distributed simulation.
(i) Wavelet-induced sparsity. Let the wavelet expansion of the density function f be given by (4). For given J E Z.,, partition the interval [0, 1] into 2 uniform bins as
2'
where E = 122- (t + [1 1-,2-111
if 10, -2], if 2 11
2]].
[0,
U
t=0
For a bin E / E [0,2 11. let
A! = E Z: F n supp(Ø..s) is non-empty
(8)
B = k z: E(") supp( ) non-empty
(9)
That is, for x E E we have (z) = 0 for & A and (. 0 for k Bl") By "wavelet-induced sparsity," we mean the following:
Claim 3.1. Let [0, 1] U E as in (7). Then, for each t [ 1]].
_A < 2(A 2), 2),
|B(01 S 2(A + 2).
where A is the assumed bound for points in the support of & and ab.
The claim follows from the observation that ΦJ,6 (resp., 1/J,x) is obtained by translating Φ
(resp., 11,0) in steps of size 2 and that supp(0J.k) C [-A2-3, A, (resp., supp(()).) S 1-A2-2,A2-9
(ii) Vector quantization. Consider the problem of designing a randomized algorithm that takes as input arbitrary x E _d satisfying | B, and outputs a random vector Q(z) Rd chosen from an alphabet of finite cardinality, such that [[](z)) = x. Our vector quantization algorithm (Algorithm 1) achieves this, and is based on the following idea: Let P be convex polytope with vertices { {11, ......} such that {a E Rd || < B} P. Given æ (with || I B). express x
as convex combination of vertices of P (say, x Σ, 0,0;) and output random vertex V, where V U, with probability 0,. Clearly, E[V]

---

Specifically, Algorithm uses the polytope P = Py formed by the vertex set V (=dd)e),,..... (Bd)))) where e, is the i-th standard basis vector (i.e., P is the & ball of radius Bd). Note that |V] 2d and that {ar E 12 || S B} Pv. This leads to the following claim.
Claim 3.2. Given x E Rd with || I B as input, Algorithm outputs a random variable (xx E V that is an unbiased estimate of with [V] 2d.
Remark. A more direct approach to quantization would to do it coordinate- í.e., quantize (independently) each coordinate to [-B, B} with appropriate probability to make it unbiased. This can equivalently be seen as quantizing the vector using the loo ball (of radius B) as the polytope. Here, the alphabet size becomes 2d instead of 2d in Algorithm I; but, on the plus side, the coordinate- wise variance of the quantized vector becomes RS Bd, instead of z (Bd)² in Algorithm I. In our estimators, will be quantizing vectors of constant length (d), so these dependencies on d do not affect the rate (up to constants).
Algorithm 1 Vector quantization
Let V = (=dd))) (Bddea)). Label the vectors in V as U1,..., U2d-
Input: Rd with ||=|| S B.
2d i= 1: Write x as convex combination of vectors in V: x = Σi 0,0,
2:
Choose I E {1....,2d) 2d) randomly where I= with probability 0, and return Q(x) Uz-
(iii) Distributed simulation. The problem of distributed simulation is the following: There are players, each having an i.i.d, sample from an unknown d-ary distribution p. Each player can only send & bits to central referee, where & < log d. Can the referee simulate i.i.d. samples from p using f-bit messages from the players? [3] proposed a noninteractive communication protocol, using which the referee can simulate one sample from p using é-bit messages from (dd/2) players. Moreover, the protocol is deterministic the players, and only requires private randomness at the referee.
Theorem 3.3 ([3)). For any 1, the simulation protocol of [3], denoted DISTRSIMg, lets the referee simulate Mn22 /d) i..dd. samples from an unknown d-ary probability distribution p using (-bit messages from players, where each player holds an independent sample from p.
Combining ideas. We now discuss how the three ideas come together. To mimic the classical estimator (5), player with sample X would ideally like to communicate (éH,((X)) (x)) but cannot do so due to communication constraints. Wavelct-inducee sparsity (Claim 3.1) ensures that communicating the bin (out of 2 possible bins) in which X lies is tantamount identifying the set of at most d == 2(A + 2) indices k for which ÓH (XX) is possibly non-zero. Moreover, the player can quantize (unbiasedly) the vector containing values of (H,,(X) whose output is one of 2d possibilities (Claim 3.2). Thus, overall, using an alphabet of size at most 2 (2d) = O(2"). ), a player can communicate an unbiased estimate of {Ør, (X)) It can be shown that a density estimate based on these unbiased estimates from n players still achieves centralized minmax rates (up to constants). However, 2 4(A + 2)2" the players cannot send these estimates directly to the referee. In this case, the players and the referee use the distributed simulation protocol DISTRSIMe (Theorem 3.3). which, effectively, enables the referee to simulate On2 /2") i.i.d. realizations of unbiased estimates of (x).(X)))e The referee can now output a density estimate based on these simulated estimates. The degradation in minmax rates under communication constraints is due to the fact that the referee has only O(n2 /2 realizations of unbiased estimates of (0 (X)) instead of n.
these indices using Algorithm 1,
We now give details of the idea outlined above. The resulting estimator (single-level estimator) is a communication-oonstaaiii
version of the classical estimator given in (5). We then describe an adaptive estimator (multi-level estimator). which is cwwpumiicctiooncontttinttt version of the classical adaptive estimator (6).
3.1 Single-level estimator
The n players and the referee agree beforehand on the following: wavelet functions Φ, t/; H E Z4; partition [0, = Up" E(!!) as in (7); collections of indices ( t [0. 2 - 1] as in (8). For every t, the indices in A (H) are arranged in ascending order.
7

---

Player's side. Each player carries out two broad steps: (1) quantization; (ii) simulation.
Algorithm 2 Single-level estimator (Players)
Input: Player-i has input X,, E [n]].
1: for .. do
2: Player-i computes Z, := (B, Q(V)), where: (i) B, is the bin in which X, lies; (ii) Q(V,) is an unbiased quantization of the vector Vi := h )ee))
> Quantization Player-i computes b-bit message Y; corresponding Zi as per DISTRSIM; (Theorem 3.3), Simulation
3:
and sends it to the referee.
The scaling by 2- /r/ 2- in the definition of V; (line 2 in Algorithm 2) ensures that ||V:]| S | which is a constant. This enables the of Algorithm to compute quantization of V. Overall, computing Zi = (B;, Q(V:)) involves two quantizations: В, can be seen as a quantized version of X, E [0, 1}: Q(V) is a quantized version (0H ( hx)),= Moreover, for each i E [n]] Zí E 2(H), where ( = [0. 2 1] Be Bea) (with d s 2(A + 2). by Claim 3.1), so that (2 < (4A+((2)) + 2 = O.
Thus, Z1..... Zn are i..d. samples (since X1..... X, are i..dd) from [Z(H) -ary distribution (call it Pz(m) distributed across n players, where (z(1) = O(2"). Since a player can send only & bits, player-i cannot send Z, directly if 2 < |z("] this case, player-i computes an f-bit message Y; according to the distributed simulation protocol DISTRSIM,, and sends Y; to the referee.
Referee's side. The referee, using the simulated i.idd samples from Pz computes the density estimate similar to the classical estimate (5). This is possible because the m = O(n2'/221 simulated samples are, essentially, i..dd realizations of unbiased quantization of {(),
Algorithm 3 Single-level estimator (Referee)
Input: YI...., Yn (é-bit messages from n players).
1: From Y,...., Yn, referee obtains m 0(n29/12(81) = O(n29/2H) i..d. samples
Zi...., Z' uzon as per DISTRSIMe, where = (Bi, Q1) E z
2: for I......,,m do
3: Referee computes
21 Q((k) if E A otherwise,
70 =
(10)
0
where (k(k) is the entry in Q¹ corresponding index k E A negate the scaling by 2-H/2 used in definition of V, on the players' side. Referee outputs density estimate
Scaling by 2/2 is to
4:
Σ
HHAOHH where āH.k KEZ
20 H.k.
k EZ
(II)
1=1
Result. For H such that 2 x min((n22)) ( n the single-level estimator recovers the guarantees in Theorem 1.2 (see Appendix in Supplementary). The estimator is nonadaptive because setting // requires knowing Besov parameter s. Further, note that the estimator is indeed noninteractive, as player-i's message Y, does not depend on messages YI....,Yy-1
3.2
Multi-level estimator: An adaptive density estimator
The key observation in designing our multi-level estimator is that different coefficients need to be recovered with different accuracy. We enable this by dividing players into groups for estimating different coefficients, and using a different level quantization for each group. This is in contrast to simply mimicking the classical adaptive estimator (6), which would suggest that player with sam- ple X should quantize and communicate information about (ΦL. ( (x)) Je
Instead, we do the following: Divide players into H L + groups of equal size (so, each

---

group has n' = H-L+I players). Label the groups L, - 1...., H. Players in group- only focus on { (x), Players in group-J, J [L 1, H, only focus on (V),(()) Moreover, players in group-J, J [L, H| quantize their sample X using 2 uniform bins. As before, by Claim 3.1, this is tantamount to identifying at most a constant number indices for which the wavelet function evaluates to non-zero value (since players in group-J only consider I...a or V),.)) The player then quantizes the vector containing these values using Algorithm 1, before using distributed simulation.
n.
The n players and the referee agree beforehand on the following: wavelet functions o, yे; L, H Z+: division of players into I/ L + 1 groups. Further, for each J E [L, HI the n' players in group-J and the referee agree on the following: partition [0, 1] = U E as in (7); collection of indices A B E [[o 2 - I]. as (8), (9). For every J, 1, the indices in A!") ,B(") are arranged in ascending order.
Player's side. Label players in group-J (I,J),.... ....),..... (n' JJ). We denote by X the sample with player-(i, Essentially, players in group-J run quantization and simulation steps as in the single- algorithm (Algorithm 2), with H replaced by
Algorithm 4 Multi-level estimator (Players)
Input: Player- J) has input X i E [n']. E [L, H]] (where n' = H-L+1 1: for J = L, L + 1,...,H do 1,...,,,'' do 3: Player-(i, computes Zz = Q(V..))) where: (i) B is the bin (out of 2 bins) in which X,, lies; (ii) Q(Vi,)) is unbiased quantization of the vector V1,,, where
n
2: for i
{2- Vunk (X.,)) kEB
if E [T. +1 H].
B,
Vi, 12-1./2 2L. (X., ke
+ @ 1/2 (XLL)
if J = L.
( denotes concatenation of two vectors.) (i, computes ξ-bit message Y,, corresponding to Z as per DISTRSIM, and Simulation
Quantization
4:
sends it the referee.
Referee's side. For players in group-J, Z,,J (0), where |z(r 0 Thus, after distributed simulation, referee obtains my On''2 /22) Onn2 /(H of group-J. Note that, higher the J, fewer the simulated samples; this dependence on of the number of samples available with the referee is of the major differences between the classical and the distributed setting. Finally, using the simulated samples from players of every group, referee computes a density estimate similar the adaptive classical estimator (6), with threshold value t / J m.. for a constant K.
1)2") samples from players
Result. For L, H satisfying 2 x min (n22) 2(+1)+ n2 + and 2 min{ log(n2 log the multi-level estimator yields the guarantees in Theorem 1.3 (see Appendix C in Supplementary) as long as E (1/p. N + 1) (recall that N is the regularity of the wavelet basis). Since L, H do not depend on specific Besov parameters, the estimator is adaptive. Moreover, it is noninteractive.
V2
Lower Bounds
We conclude with a description of our information-theoreei lower bounds (Theorem 1.1) for the minimax loss (n, p.p. s), which applies to the broader class of interactive protocols (recall that our matching upper bounds are obtained by noninteractive ones): the details can be found in Appendix in Supplementary. To derive lower bounds, we consider a family of probability
distributions P parameterized by (-1,1)d for some E Z4; that is, P = {p= : 2 E 1)), where P. has density fz. Moreover, we specify prior π Z = (Zi,..., ......Z)) E (-1,1) defined as Z, Rademacher(r) independently for each E [d], for some 7 E (0, 1/2). We then consider the following scenario;

---

Algorithm 5 Multi-level algorithm (Referee)
Input: (Xi,J ". (é-bit messages from n players).
1: for J = I,, I. 1,+1.-.. 1..., H do
2: From ,,...... K. referee obtains m. OOn2 L + 1)2")
iid. samples
J fi....... ..... Z m
Pzus per DISTRSIM,, where Z = (B E z
3:
for: i = 1, ,...., m do
4:
if L then
if E A 22/2 oi
5:
Referee computes
(300 [
700 as
LL, =
Bl,,.
KEZ
0
otherwise.
22 (k,
if E B( otherwise.
6:
Referee computes
J.K
as V ==
B
kez
0
7:
Referee outputs density estimate
H
f=
Σ ar. +
Σ Σ BINdIM
(12)
J=L
where āL,k = 1. Em
200) L,
BJ =
m. (13) J,k+
Bi = Br (10
my
For Z ~ ग., let X1..... ,.....,,,,, X2 be i..dd samples from pz distributed across n players. Let YI...., Yn be l-bit messages sent by the players (possibly interactively) to the referee. Denote by p (resp. p the joint distribution of Y1, .i,..., Yn, given Z; = 1 (resp. Z,- -1). That is,
1 Σ
P+
(2))
P
Σ T<))p
(13)
1
=:2==1
2:2,=-1
where p."" is the joint distribution of Yi..... Yn, given Z =
In this scenario, we analyze the "average discrepancy" 4 - dry (p -p-"".p -p"" where dry (p. q) denotes the total variation distance between p and q. On the one hand, a result from [2] gives us an upper bound on this average discrepancy a function of n and & which holds for any interactive protocol generating Yı..... Yn (Theorem D.3 in Supplementary). On the other hand, we derive lower bound on average discrepancy (as function of the error rate 2) follows: Consider a communication-comee conttrrinn density estimation algorithm (possibly interactive) which
outputs f satisfying suBpe.()...s) E, [lf fllz < e". We show that one can use the messages Yi...., Yn generated by this algorithm to solve, for each problem of deciding whether Z; 1 or 7: -1 This, in turn, implies a lower bound on +E (p'" ym PP")) Putting together the upper and lower bounds average discrepancy gives us a lower bound on E.
[d]. the binary hypothesis testing
The parameterized family of distributions P consider is constructed follows: Let fo be function supported on [o, 1]. Let II...., Ia S [0, 1] be mutually disjoint intervals of equal length. Let d) be a "bump" function supported interval L,, where v/, 's are all translations of the same bump function. Then, for 2 = (Z),..., 2d) 11,, we define P> be a probability distribution with density fz, defined as the "baseline" fo perturbed by adding (a rescaling of) the bump vi according to the value of 2,. In more detail, to get the desired lower bounds, we distinguish two cases depending on whether r < (s 1) 1)p, and construct two families of distributions: Pi (when r < (s 1)))) and Ps (when r 2 (s + 1)p). For P1, we use a uniform prior on Z (Zi...., Za), i.e., Z has independent Rademacher (1 (2) coordinates, and set f= = fo + Ed= 2eth for some suitably small parameter y 0. That is, the baseline density fo has disjoint bumps, which are either 1h -1/y depending on the value of z; (See Appendix D.3 for details.) For Pg, we use a non-uniform ("sparse") prior on 2, where 7 has independent Rademacher(1/66 /d) coordinates, and set fz fo + - + 2i);/;
(so that bump th only appears if Z, 1). (See Appendix D.4 for details.) Applying to these constructions the method described above allows us to derive the lower bounds of Theorem 1.1.
10

---

Acknowledgments and Disclosure of Funding
Aditya Vikram Singh supported by Prime Minister's Research Fellowship. Jayadev Acharya is supported by NSF-CCF- 1846300 (CAREER), NSF-CCF-1811899,, and Google Faculty Fellowship.
References
[1] Jayadev Acharya, Clément L Canonne, Yuhan Liu, Ziteng Sun, and Himanshu Tyagi. Interactive inference under information constraints. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 326-331. IEEE, 2021.
[2] Jayadev Acharya, Clément L. Canonne, Ziteng Sun, and Himanshu Tyagi. Unified lower bounds for interactive high-dimensional estimation under information constraints. arXiv preprint arXiv:2010.06562 00..00000.66...... 2021.
[3] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi. Inference under information constraints II: Communication constraints and shared randomness. IEEE Transactions Information Theory, 66(12):885-7877, 2020.
[4] Leighton Barnes, Yanjun Han, and Ayfer Özgür. Fisher information for distributed estimation under a blackboard communication protocol. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 2704-2708. IEEE, 2019.
[5] Leighton Pate Barnes, Yanjun Han, and Ayfer Özgür. Lower bounds for learning distributions under communication constraints via Fisher information. Journal of Machine Learning Research, 21(236):1334 2020.
[6] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff. Com- munication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the Forty-Fighth Annual ACM Symposium on Theory of Computing, pages 1011-1020. ACM, 2016.
[7] Cristina Butucea, Amandine Dubois, Martin Kroll, and Adrien Saumard. Local differential privacy: elbow effect in optimal density estimation and adaptation over Besov ellipsoids. Bernoulli, 1673):177711764, 2020.
[8] T Tony Cai and Hongji Wei. Distributed nonparametric function estimation: Optimal rate of convergence and cost of adaptation. arXiv preprint arXiv:2107.00179. 2021.
[9] Ingrid Daubechies. Ten lectures on wavelets. SIAM, 1992.
[10] David Donoho, lain M. Johnstone, Gérard Kerkyacharian, and Dominique Picard. Density estimation by wavelet thresholding. Ann. Statist., 24(2):508-539, 1996.
[11] Ankit Garg, Tengyu Ma, and Huy L. Nguyen. On communication cost of distributed statis- tical estimation and dimensionality. In Advances in Neural Information Processing Systems, volume 27, pages 2726-2734, 2014.
[12] Yanjun Han, Ayfer Özgürr and Tsachy Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. In Conference Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 3163-3188. PMLR, 2018.
[13] Jingbo Liu. A few interactions improve distributed nonparametric estimation, optimally, arXiv preprint 2XXv:2107.002111 2021.
[14] Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems, volume 27, pages 163-171,, 2014.
[15] Botond Szabo and Harry van Zanten. Adaptive distributed methods under communication constraints. The Annals of Statistics, 48(4):2347-2380, 2020.
[16] Botond Szabo and Harry van Zanten. Distributed function estimation: Adaptation using minimal communication. arXiv preprint arXiv:2003.12838, 2020.

---

[17] Yuchen Zhang, John C Duchi, Michael I. Jordan, and Martin J. Wainwright. Information- theoretic lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems, volume 26, pages 2328-2336, 2013.
[18] Yuancheng Zhu and John Lafferty. Distributed nonparametric regression under communication constraints. In International Conference on Machine Learning, pages 6009-6017. PMLR, 2018.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We did our best to put our results context, and accu- rately describe our contributions and results (including assumptions and upplicability of our results.
(b) Did you describe the limitations of your work? [Yes] Our theorem statements and the introduction describe the assumptions, and range of applicability, of our results.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our results are concerned with the theoretical foundations of nonparametric density estimation; while some applications may down the line have negative (or positive) societal impacts, they are too far remote from our work for us to be able to assess them.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "qD4S-ixo67r", "reviewer": "Reviewer_SLwN", "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:\n1. The fact that at most a constant number of wavelets at resolution J are non-zero on any interval of width $2^{-J}$.\n2. A particular randomized scheme that quantizes the values of the non-zero wavelets at a sample point without introducing bias.\n3. The DISTRSIM protocol proposed by [3], which maps a quantized sample to a smaller IID sample of higher resolution.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nComments:\n1) 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.\n\n2) The current writing of the paper implicitly requires the reader to reference the supplement to understand several points.\nI 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:\n    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.\n    2) A brief description of how the DISTRSIM protocol works would be nice.\n    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.\n\n\n-------AFTER READING AUTHOR REBUTTAL-------\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "gfLzMnHSxZ", "reviewer": "Reviewer_KsRx", "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n- 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. \n- 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. \n- The fact that the lower bound also applies to the interactive setting is a plus to the paper's merits. \n\nWeaknesses\n\n- 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. \n- 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].\n- 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. \n- 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.\n\nMinor\n\n- Line 289 is apparently under full. I suggest the authors adjust the equations accordingly. \n\n\n\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Hy4lvqnq76R", "reviewer": "Reviewer_4wEN", "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nI 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. \n\nThe 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 \n\nA. Jung, \"Networked Exponential Families for Big Data Over Networks,\" in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.\n\n\nThe clarity/precision of the presentation could be improved: \n\n- 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. \n\n- The role of the last paragraph in Section 1.2. is not very clear. \n\n- in which sense is (4) to be understood ? pointwise (for each x) or w.r.t. some norm?\n\n- \".. is an unbiased estimate of \\alpha_{j,k} ..\" how is \\alpha_{j,k} defined for j different from 0 ? \n\n- \"...s lies in a certain range.\" what is this range?\n\n- \"Our proposed estimators draws upon these classical estimators..\"  how exactly does it draw upon them ? \n\n- \"As in the unconstrained setting ...\"  i assume you mean for \\ell -> infty ?\n\n- 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 ? \n\n- 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. \n\n- \".. 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 \n\n- 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. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "B36wD42QS6g", "reviewer": "Reviewer_83Tb", "summary": "The paper studies a quantization approach for nonparametric density estimation in the Besov space with communication constraints.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI think the approach is reasonable and the theoretical analysis shows that the statistical rates are minimax optimal. I recommend acceptance.\n\nI 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See my main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "0.5"}, "extra_text": {}}]

Author rebuttal:

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)