Pointwise Bounds for Distribution Estimation under Communication Constraints
Authors: Wei-Ning Chen
Peter Kairouz
Ayfer Ozgur
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributed estimation
communication complexity
instance-optimal

Abstract: We consider the problem of estimating a $d$-dimensional discrete distribution from its samples observed under a $b$-bit communication constraint. In contrast to most previous results that largely focus on the global minimax error, we study the local behavior of the estimation error and provide \emph{pointwise} bounds that depend on the target distribution $p$. In particular, we show that the $\ell_2$ error decays with $O\left(\frac{\lVert p\rVert_{1/2}}{n2^b}\vee \frac{1}{n}\right)$ when $n$ is sufficiently large, hence it is governed by the \emph{half-norm} of $p$ instead of the ambient dimension $d$. For the achievability result, we propose a two-round sequentially interactive estimation scheme that achieves this error rate uniformly over all $p$. Our scheme is based on a novel local refinement idea, where we first use a standard global minimax scheme to localize $p$ and then use the remaining samples to locally refine our estimate.
We also develop a new local minimax lower bound with (almost) matching $\ell_2$ error, showing that any interactive scheme must admit a $\Omega\left( \frac{\lVert p \rVert_{{(1+\delta)}/{2}}}{n2^b}\right)$ $\ell_2$ error for any $\delta > 0$ when $n$ is sufficiently large. The lower bound is derived by first finding the best parametric sub-model containing $p$, and then upper bounding the quantized Fisher information under this model. 

Our upper and lower bounds together indicate that the $\mathsf{H}_{1/2}(p) = \log(\lVert p \rVert_{{1}/{2}})$ bits of communication is both sufficient and necessary to achieve the optimal (centralized) performance, where $\mathsf{H}_{{1}/{2}}(p)$ is the R\'enyi entropy of order $2$. Therefore, under the $\ell_2$ loss, the correct measure of the local communication complexity at $p$ is its R\'enyi entropy.

Pointwise Bounds for Distribution Estimation under Communication Constraints
Wei-Ning Chen
Peter Kairouz Google Research
Department of Electrical Engineering
Stanford University machen@stan.free edu
tairouz@google.com
Ayfer Özgür
Department Electrical Engineering Stanford University aozgur@stanforde edu
Abstract
We consider the problem of estimating d-dimensional discrete distribution from its samples observed under b-bit communication constraint, In contrast most previous results that largely focus on the global minimax error, we study the local behavior of the estimation error and provide poinnwise bounds that depend on the target distribution p. In particular, we show that the l error decays with [1plly/2
governed by the half-norm of instead of the ambient dimension d. For the achievability result, we propose a two-round sequentially interactive estimation scheme that achieves this error rate uniformly over all p. This two-round scheme extends & loss with 2 1, and hence gives pointwise upper bounds on b, error. We also develop a local minimax lower bound with (almost) matching error, showing that any [1 n2*
(mnx
n2" :)) when n sufficiently large, hence
interactive scheme must admit ?
lg error for any 8 0.
Our upper and lower bounds together indicate that the 21)2(p) A log( (PPl1/2) bits of communication is both sufficient and necessary achieve the optimal (cen- tralized) performance, where H1)2(p) (p) is the Rényi entropy of order 2. Therefore, under the & loss, the correct measure of the local communication complexity at p is its Rényi entropy.
Introduction
Learning distribution from its samples has been fundamental task in unsupervised learning dating back to the late nineteenth century (T]. This task, especially under distributed settings, has gained growing popularity in the recent years data increasingly generated "at the edge" by countless sensors, smartphones, and other devices. When data is distributed across multiple devices, communication cost and bandwidth often become bottleneck hampering the training high- accuracy machine learning models (2) This is even more so for federated learning and analytics type settings which rely on wireless mobile links for communication.
To resolve this issue, several communication--ffiiiee distribution learning schemes have been recently proposed and studied in the literature (see Section 1.2] for thorough discussion). On the positive side, the state-of-ther the-tthhrrtt schemes are known to be worst-case (minimax) optimal as they have been shown achieve the information--thorred lower bounds on the global minimax error 4 On the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

negative side, however, the lz estimation enror achieved by these schemes scales as Ol w25 under a b-bit communication constraint on each sample, where is the alphabet size of the unknown discrete distribution p. This suggests that without additional assumptions on p the error scales linearly in d, i.e. the introduction of communication constraints introduces a penalty d on the estimation accuracy. This is true even if we allow for interaction between clients [
recent work [0]] has moved step forward from the "global minimax regime" by restricting the target distribution p to be s-sparse and showing that the & error can be reduced to O [ in this case, i.c. the eттоr depends on the sparsity rather than the ambient dimension d. However, their scheme heavily relies on the s-sparse assumption and requires knowing beforehand. Therefore. when s is unknown and we need to work with a (potentially loose) upper bound on s. the estimation error increases accordingly. In addition, little is known when the target distribution deviates slightly from being exactly s-sparse.
n2
In this paper, we argue that all these results can be overly pessimistic, as worst-case notions of complexity and schemes designed to optimize these worst-case notions can be too conservative. Instead, we seek measure of local complexity that captures the hardness of estimatinn a specific instance p. Ideally, we want a scheme that adapts to the hardness of the problem instead of being tuned to the worst-case scenario; that is, scheme achieving smaller error when p is "simpler."
Our contributions Motivated by these observations, in this work we consider the local minimax complexity of distribution estimation and quantify the hardness of estimating specifie p under communication constraints. In particular, under the lz loss, we show that the local complexity of estimating p is captured by its half-norm ||lll. we propose two-round interactive scheme
[Ipl [1pl..2 1 eπtor under Eg loss which requires no prior n2 n
that uniformly achieves the O [max
information on p. On the impossibility side, we also show that for any (arbitrarily) interactive scheme, the local minimax error (which is formally defined in Theorem 2.4) must be at least Ω [max [|Pll146/2 n2"
H)) for any 8 >> O when n is sufficiently large.
These upper and the lower bounds together indicate that l|pll//2 plays a fundamental role in distributed estimation and that the (10((1)111/2) bits of communication is both sufficient and necessary to achieve the optimal (centralized) performance when n is large enough. Indeed, this quantity is exactly the Rényi entropy of order 2, i.c. H (p) _ log(1ppl11/2) 1/22) showing that under the Eg loss, the correct measure of the local communication complexity at p is the Rényi entropy of p.
Compared to the global minimax results where the error scales as O ((15)) ) we see that when we move toward the local regime, the linear dependency d in the convergence rate is replaced by 1PPl1/22 This dimension independent convergence is also empirically verified by our experiments (see Section for more details). Note that l|pll1/2 < d, so our proposed scheme is also globally minimax optimal. Moreover, since ||pll//2 < llpll- our scheme achieves the O n25 convergence rate under
the s-sparse model (10), which improves the O s log(d/s) upper bound in 110 by further shaving off the additional log (og(d/)) term (though admittedly, their scheme is designed under the more stringent non-interactive setting). As another immediate corollary, our pointwise upper bounds indicate that 1 bit suffices attain the performance of the centralized model when the target distribution is highly skewed, such as the (truncated) Geometric distributions and Zipf distributions with degree greater than two.
n2"
Our techniques Our proposed two-round interactive scheme based on a local refinement approach, where in the first round, standard (global) minimax optimal estimation scheme is applicd to localize p. In the second round, we use additional ((n) samples (clients), together with the information obtained from the previous round, to locally refine the estimate. The localization- refinement procedure enables us to tune the encoders (in the second round) to the target distribution p and hence attain the optimal pointwise convergence rate uniformly.
On the other hand, our lower bound is based on the quantized Fisher information framework intro- duced in D]] However, in order to obtain local bound around p, we develop new approach that
Herr we generalize the notion of q-norm lipll, A (E
p!)
1/4
to E 1].
Our scheme also guarantees pointwise upper bounds on Eı general l, errors. See Theorem 2.2
2

---

first finds the best parametric sub-model containing and then upper bounds its Fisher information in neighborhood around p. To the best of our knowledge, this is the first impossibility result that allows to capture the local complexity of high dimensional estimation under information constraints and can of independent interest, e.g. to derive pointwise lower bounds for other estimation models under general information constraints.
1.1 Notation and Setup
The general distributed statistical task we consider in this paper can be formulated as follows. Each one of the n clients has local data X; ~ p. where p E Pa and Pa - collection of all d-dimensional discrete distributions. The i-th client then sends message Y; E y to the server, who upon receiving Y aims to estimate the unknown distribution p.
{p e R4 Σ, = 1 is the
At client the message Y, is generated via sequentially interactive protocol; that is, samples are communicated sequentially by broadcasting the communication to all nodes in the system including the server. Therefore, the encoding function W, of the i-th client can depend on all previous messages Y1,... 1 Formally, it can be written as a randomized mapping (possibly using shared randomness across participating clients and the server) of the form W Y and the b-bit communication
constraint restricts | < 2b, As special case, when W; depends only X; and is independent of the other messages yi-1 for all i (i.e. W, Y = W,(+lX,)), we say the corresponding call the tuple (W' (({")) an estimation scheme, where
protocol is non-inted non-interactive. Finally, á (Y") is an estimator of We use Ilseq and Ilind to denote the collections of all sequentially interactive and non-interactive schemes respectively.
Our goal here to design a scheme (W", (Y")) to minimize the l (or E1) estimation error: r (f2, (W", p)) è Ellpp - 5 (Y")) for all p E Pa. as well as characterizing the best error achievable by any scheme in Ie We note that while our impossibility bounds hold for any scheme in Il the particular scheme we propose uses only one round of interaction.Fe & error, we replace 11-112 in the above expectations with II-II, In this work, we mainly focus on the regime 1 < d < aiming to characterize the statistical convergence rates when n is sufficiently large.
1.2 Related works
Estimating discrete distributions is a fundamental task in statistical inference and has a rich literature [5) Under communication constraints, the optimal convergence rate for discrete distribution estimation was established in [6) for the non-interactive setting, and (8 9 for the general (blackboard) interactive model. The recent work (T0) considers the same task under the sparse assumption for the distribution under communication or privacy constraints. However, all these works study the global minimax error and focus on minimizing the worst-case estimation error. Hence the resultant schemes are tuned to minimize the error in the worst-case which may be too pessimistic for most real-world applications.
slightly different but closely related problem is distributed estimation of distributions heavy hitter detection under local differential privacy (LDP) constraints (4) Although originally designed for preserving user privacy, some of these schemes can be made communication efficient.
and
For instance, the scheme in 220 suggests that one can use 1 bit communication to achieve ((d / &
error (which is global minimax optimal); the non-interactive tree-based schemes proposed in [2 23 can be cast into a 1 1-bit frequency oracle, but since the scheme is optimized with respect to to error,
directly applying their frequency oracle leads to sub-optimal convergence O
[sloog (llggd+ in lz.
n
In the line of distributed estimation under LDP constraint, the recent work 25 studies local minimax lower bounds and shows that the local modulus of continuity with respect to the variation distance governs the rate of convergence under LDP. However, the notion of the local minimax error in (25) is based on the two-point method, so their characterized lower bounds may not be uniformly attainable in general high-dimensiooal settings.
Organization The rest of the paper is organized as follows. In Section 2 results, including pointwise upper bounds and an (almost) matching local minimax lower bound. We provide examples and experiments in Section 3 to demonstrate how our pointwise bounds improve
we present our main
3

---

upon previous global minimax results. In Section we introduce our two-round interactive scheme that achieves the pointwise bound. The analysis of this scheme, as well as the proof of the upper bounds, is given in Section 5 Finally, in Section 6 we provide the proof of the local minimax lower bound.
2
Main results
Our first contribution is the design of a two-round interactive scheme (see Section for details) for the problem described in the earlier section. The analysis of the convergence rate of this scheme leads to the following pointwise upper bound on the &2 error:
Theorem 2.1 (Local &g upper bound) For any b S [log2 d], there exist a sequentially interactive scheme (W",)) Tes. such that for all p E Pa.
1
d llo(ndd)
1ll| + (n())
(l2,p, .D) S C1 C2
C3
n26
(n22)²
n2
where C1, Cz. C3 > 0 are some universal constants (which are explicitly specified Section 5 This d logd
implies that as long
Ω
1plliy2) (l2. (W", p)) = max
)
n2*
In addition to the l enror, by slightly tweaking the parameters in our proposed scheme, we can obtain the following pointwise upper bound on the & (i.e. the total variation) error:
Theorem 2.2 (Local l upper bound) For any S [log2 dj, there exists a sequentially interactive
scheme (Wr.p) E Ilseq such that for all E Pa
r r(1,,, (Wm,p)) s CiV
[pll + +cy
lpll
dAlog log (nd)
[|lll3 + (1)
+ Cay
n26
(n22)²
n25
where C1, C22 C3 > are some universal constants.
Hence as long as n Ω
a log
ppllyza 42"
IPll./2
r (L,,,, (W", ,))
O max
Theorem 2.1 implies that the convergence rate of the lg error is dictated by the half-norm of the target distribution while Theorem T immpliss that the & error is dictated by the one-third norm of the distribution. In general, we can optimize the encoding function with respect to any lg loss for q E [1, 2] and the quantity that determines the convergence rate becomes the 9+2 -n-oorm (see Remark CT for details). We also remark that the large second-orde terms in Theorem and
Theorem 2.2 are generally inevitable. See Appendix A. for a discussion. The proofs of Theorem
and Theorem 2.2 are given in Section and Appendix respectively.
Next, complement achievability results with the following minimax lower bounds.
Theorem 2.3 (Global minimax lower bound) For any (possibly interactive) scheme, it holds that
inf (W' ETT 1
sup
Ex-p [Io(W> - =112 -p11?] S2
h
1:26
Note that the lower bound in Theorem 2.3 can be uniformly attained by our scheme even if no information the target set of distributions, i.e. the parameter h is available, indicating that our proposed scheme global minimax optimal. The proof can found Section D

---

Theorem 2.4 (Local minimax lower bound) Letp E Pa {pe Pa
< < 3. Then for any
ò >>0,
0,
Pll d2
as long as n2 = S d logd it holds that
Tplla//2
c1 IIeely log d
inf (W" Wellle p:lll//pll.g vn
sup
By [lo(W"(X*)) - -p'll
2 max
n22
cs عللا
+ C2
for some cB,
C1, CB,C1,0 O.
B Remark 2.1 Note that in Theorem 2.4 the &o neighborhood pp' -1pp' - pll S v
is {1' IIp'' pll2 S v / (2 (since
strictly smaller than the following l neighborhood:
B Ja) C Ba,s, (1)). Therefore, in Theorem 2.4 we present slightly stronger statement.
Theorem 2.4 indicates that our proposed scheme is (almost) optimal when n is sufficiently large and that |||| 1/2 is the fundamental limit for the estimation error. This conclusion implies that under & loss, the right measure of the hardness of an instance p is its half-norm, or equivalently its Rényi entropy of order 1/2. The proof of Theorem 2.4 is given in Section
Corollary 2.1 When is sufficiently large, [log(Ile])/22] bits of communication is both sufficient and necessary achieve the convergence of the centralized setting under &z loss. Similarly, [log(I]Phh/)5) bits are sufficient for & loss.
In addition, observe that the quantities log(Ilplla/2) and log ((Pll1/) are the Rényi entropies of order 1/2 and 1/3, denoted as (p) and H1 (p))) respectively. In other words, the communication required to achieve the optimal (i.c. the centralized) rate determined by the Rényi entropy of the underlying distribution p.
Finally, we remark that when the goal achieve the centralized rate with minimal communication (instead of achieving the best convergence rate for a fixed communication budget as we have assumed so far), the performance promised the above corollary can be achieved without knowing H2 (p) beforehand. See Appendix A.2 for discussion.
Examples and experiments
Next, we demonstrate by several examples and experiments that results recover earlier global minimax results and can significantly improve them when the target distribution is highly skewed.
Corollary 3.1 (s-sparse distributions) Let Pa. A {De [0, 1 Σp. lllll S s). Then as long as n large enough, there exists interactive schemes (W", , and (W", .P) such that r (42,P, (W", p)) 0 n2 and (C1,P%, (W*.)) = 0 n
The above result shows that our scheme minimax optimal over Pa,.- This recovers and improves (by a factor of log d/s) s) the results from 110 on the & and l convergence rates for s-sparse distributions m
Corollary 3.2 (Truncated geometric distributions) Let p A Geog,a be the trancated geometric
distribution. That is, for all [0,1] and E [d]. Geo 2 Ω (d log d/2²).
1-3 31- Then if n
1 (1++)) v3" = O max n11 n2 (1 (B) )
2 2 ))
(W" P)) :))= 0
Indeed, the lower bound holds for blackboard interactive schemes 26 more general class interactive schemes than Tlzg. See [8] for discussion blackboard schemes.
We remark. however, that their scheme is non-in interrtteee and has smaller minimum sample size requirement.
5

---

This result shows that if / is constant for the truncated geometric distribution, 1 bit suffices to achieve the centralized convergence rate ( in this case. Note that this significant improvement over previous minimax bounds on the the & error which are O n22 [4). This suggests that the Σ k
corresponding minimax optimal scheme suboptimal by a factor of d when the target distribution is
truncated geometric. Our results suggest that the &g error should not depend on d at all, and Figure provides empirical evidence justify this observation.
Corollary 3.3 (Truncated Zipf distributions with > 2) Let P
-
Zipf x be a truncated Zipf
distribution with X 2. That is, for [d]. x
"/)()) Then the local
complexity of is characterized by 1/pll//2 = θ -(4+
12--1/211
2)
(
= @(1). So in this case,
r (f2,P, (W", :)) = O ( as long as n = (d log d/2%).
We leave the complete characterization for all Geog,a and Zipf are not sparse distributions, [10] cannot be applied here. Therefore, the best previously known scheme for these two cases is the global minimax optimal scheme achieving an error. Again, our results suggest that this is suboptimal by factor of d. O (22))
to Section in appendix. Note that since both
In Figure L we empirically compare our scheme with (which is globally minimax optimal). In the left figure, we see that the error of our scheme is an order of magnitude smaller than the minimax scheme and remains almost the same under different values of We illustrate that more clearly in the right figure, where we fix n and increase d. It can be observed that the error of our scheme remains bounded when d increases, while the eπrоr of the minimax scheme scales linearly in This phenomenon is justified by Corollary 3.2
Truncated Geometric (2 bits)
Truncated Geometric (2 bits, = 10²)
XLD-
-uisinuss, d-102
-mizimat, d=200
7
minbaa
mnininas, d-300
Iocalize and refine, d= 150
loralize-ond-
Jocullee acllat,
f. ceror
Eu orror
0
211
500
801
100
120
number modes
-12
alphabet size
Figure Comparisons between our scheme (labeled as minimax optimal scheme (labeled as 'minimax') The underlying distribution is set to be truncated geometric distribution with /3 0.8.
and the globally
4 The localization-refieeeent scheme
In this section, we introduce our two-round localization-rffiemeee scheme and show how it locally refines global minimax estimator ý to obtain a pointwise upper bound.
The first round of our two-round estimation scheme (the localization phase) is built upon the global minimax optimal scheme [4). in which symbols are partitioned into [d/(2' 1)] subsets each of size (2h 1), and each of the first n/2 clients is assigned one of these subsets (each subset is assigned to (n/2)/(d/(2² - 1)) clients). The client reports its observation only if it is in its assigned subset by using b bits. This first round allows us to obtain a coarse estimate with error E[Ipp - 21 x Σ, P//n2b = O(d/n2)). Then in the second round (the refinement phase), we locally refine the estimate by adaptively assigning more "resources" (i.e. samples), according to á obtained from the first round, to the more difficult symbols (i.c. j E [d] with larger error

---

Algorithm 1: uniform grouping 4 (at client i)
Algorithm 2: localize-and-refie (at client i)
Input: X, [d].6
Input: X; [d]. b N4
Compute M = d/ (2 1);
(G)..., Gd) < gen_group (p. d). Y, <- 0
m mood M. Y t
Compute J. a { [d]i 9y):
X; E [m 1) 1) + m2(=mm -1]] then
1)]
X; E Ji then
Y, + X, mod (2 1)
Y, +- the ranking of X, in T
end return Y;
end return
[Ø0 - p))) In particular, under the & loss, the number of samples assigned to symbol j will be roughly in proportional to vPj. It turns out that the local refinement step can effectively mitigate the estimation error, enabling us to move from a worst-case bound to a pointwise bound.
Round (localization): In the first round, the first n/2 clients collaboratively produce coarse estimate p = (f1, .h......Jp]] for the target distribution via the grouping scheme described above (this is the minimax optimal scheme proposed in 4 see Algorithm for details). Note that in general, this scheme can be replaced by any non-ine interrtreeteve minimax optimal scheme.
Round (local refinement): Upon obtaining P from the first round, the server then computes (p): Pa + Pa. where the exact definition of π depends on the loss function. x will be used in the
design of the rest n/2 clients' encoders. In particular, for Eg loss, we set My (p) - /Pj
Etele vpL for E
loss, we Ty (p)
For notational convenience, denote (ÿ) as मे. (#1, .. #d)-
ΣKEja PP
To design the encoding functions of the remaining n/2 clients, we group them into d (possibly overlapping) sets .I....,. Gu with
min 1, 11, - 11)()) 1 4d ))
9 ny A n1
2
for all j [d].
We require the grouping { satisfy the following properties: 1) each {Gy} consists of ny distinct clients, and 2) each client i is contained in most (2 1) groups. Notice that these requirements can always be attained (see, for instance, Algorithm 3 in Section B). We further write J, to be the set of indices of the groups that client i belongs to (i.e. J, A (j E ddli E G,)), so the second property implies [T] <
for all i.
As in the first round, client i will report its observation if it belongs to the subset J. Since [ < 2 1, client i's report can be encoded in b bits. Note that with this grouping strategy each symbol reported by clients in Gj. hence the server estimate Pj by computing P, (Y Eieg, ((x-i)) Note that the size of 9j is dictated by the estimate for py obtained in the first round. See Algorithm for the details of the second round.
By
Remark 4.1 In the above two-round scheme, see that the local refinement step is crucial for moving from the worst-case performunce guarantee to a pointwise one. Therefore we conjecture that the local lower bound in Theorem cannot be achieved by any non-interace internttraativ scheme.
5 Analysis of the & error (proof of Theorem 2.1
In this section, we analyze the estimation errors of the above two-round localization-refinen scheme and prove Theorem 2.1 Before entering the main proof, we give the following lemma that controls the estimation error of between and π.
Lemma 5.1 Let (W", ,P) be the grouping scheme given in Algorithm Then with probability at
least 1 12. it holds that /p; vP,l VEn and v/, Vpp, Ven, where 3d log(nd)
7

---

Now consider the scheme described in Section 1 After the first round, we obtain a coarse estimate I (p.....Pp))
pj). Set E _ Neeja {vP, [vpj V vPj V Then by Lemma 5.1 and
taking the union bound over j E [d]. we have P [ 2
In order to distinguish the estimate obtained from the first round the final estimator, we use P/ to denote the final estimator.
Now observe that the &g estimation error can be decomposed into
E lp 2 P( E [|p e| + +P(E)
[1
(a) 2 S +
|1p m11((e]
where (a) holds since 1p 2 s 2 almost surely. Hence it remains to bound E ||p - 213 E] Next, as described in Section we partition the second r2/2 clients into d overlapping groups GI.... Ga according to ② The reason choose n, in this way is ensure that 1) for symbols with larger p (which implies larger estimation error), we allocate them more samples; 2) every symbol assigned with at least (n//d) samples.
Clients in G, then collaboratively estimate Py- In particular, client reports her observation
X, E J, _ Úili Gj), and the server computes P3 (Y" Eiev, 1(x,ss) Binom(ng, P5).
",
n,
[|pp - ق|ا |l completing the proof of Theorem 2.1
Finally, the following lemma controls E
Lemma 5.2 Let p be defined as above. Then E [|p p12|
6 m2n
(Eseta vp;)
+
10d
+
n2
For the & error, we set TT (p) analysis, we obtain Theorem 2.2 The detailed proof is left to Section C in appendix.
PP Following the similar but slightly more sophisticated
6 The local minimax lower bound (proof of Theorem 2.4
Our proof is based on the framework introduced in [8]. where global upper bound on the quantized Fisher information given and used derive the minimax lower bound on the &2 error. We extend their results to the local regime and develop local upper bound on the quantized Fisher information around a neighborhood of p.
To obtain a local upper bound, we construct an h-dimmensional parametric sub-model O that contains p and is a subset of Pa. where h E [d] tuning parameter and will be determined later. By considering the sub-model O we can control its Fisher information around p with a function of and p. Optimizing over h E [d] yield an upper bound that depends on llpll.- Finally, the local upper bound on the quantized Fisher information can then be transformed to the local minimax lower bound on the la error via van Tree's inequality [27]-
Before entering the main proof, we first introduce some notation that will be used through this section. Let (P(1), P(2). .... P(a)) be the sorted sequence of p (P1, Pe........Pal Pa) in the non-increasing order; that is, P(3) 2 P(j for all i > Denote [d]
[d]] as the corresponding sorting function i.e.
P()) Pm(1) for all i E [d].
Constructing the sub-model e We construct O by "freezing" the (d id-16 fi) smallest coordinates of p and only letting the largest (h- 1) coordinates to be free parameters. Mathematically, let
² {02, Bz ..., 0n) n (01, 62, ..., P(
Pa),
(3)
where 0, Σ 2 0; Dd 2 Pt is fixed when (02, ..., 0n) are determined. For instance, p =
- (1 1
(so = 5) and 3, then the corresponding sub-model
T6 3:
2
I6
(0 0s)) (16 0s, 0z, 16" ./88 E EPa)
'iit slight abuse of notation, overload that (pI, ...,...,)) pa)) & (po(t)....Patt))

---

Bounding the quantized Fisher information Next, under this model, we control the quantized Fisher information the following lemma.
Lemma 6.1 Let W be any b-bit quantization scheme and Iw (0) be the Fisher information of Y at where Y ~ X (-IX) and X ~ Po- Let 0 < B < Piu and E P & {pe Pal < Pi < f.. Define
3
the neighborhood (p) - 0(p) I- B)th (note that under this definition, NB. (p) must be contained in ).)) Then
3
4O' (BA())); Tr Tr(Tw(0)) s 22 6h
2p(n))
Bounding the &g error
Applying
Theorem 3] on (P), we obtain
h
h 12p00
p'p())
sup ('EN
E
0'
2 n2
6h + 2p(n)
10m2 +
10kp
20m2
(4)
B
where the second inequality is due to hM()) I 1, and the third inequality holds if we pick Σ
hP()
n2"
Notice that in order to satisfy the condition (B) S eb. B must be at most P(A) implicit sample size requirement: must be at least 3h
3 so we have an
2"p(k)
Optimizing over Finally, we maximize h (PP()) over E [d] to obtain the best lower bound. The following simple but crucial lemma relates p())) to l!lll
Lemma 6.2 For any p E Pa and 8 > O, it holds that
|pll
max 12 p(a) 2 max (Cssle (Collpll2e Cllplll /log he(d
for Cs A
and universal constant small enough.
I+8
Picking ht* = argmax;eed h² hPp( and by Lemma 6.2 and
we obtain that for all
sup 0' D'E. a- (p)
E 110
0r
2 max C/s
|pel
1-
C
Illlly
n2
n22 log
as long as p E P/ and B,,
1s P(a n2
(a)
where (a) holds due to the second result of
n2 PP
Lemma 6.2 and h² S d. addition, the sample size constraint that n must larger than P'P(A) be satisfied if
can
logd 2
since A
(h*)
d log where the first inequality is due Tirll
P(n*) Clppll
to Lemma 6.2 and the second is due to h < d. The proof is complete by observing that
inf sup
E
10
p [12]
2 inf sup
E
0
0¹
27
(W" p
pll SB
(W o'e a.
7 Conclusion and open problems
We have investigated distribution estimation under b-bit communication constraints and characterized the local complexity of target distribution p. We show that under lg loss, the half-norm of dictates the convergence rate of the estimation error. In addition, to achieve the optimal (centralized) convergence rate, ((H))2(p)) bits of communication is both necessary and sufficient.
Many interesting questions remain to addressed, including investigating the same lower bound can be achieved by non-interactive schemes, deriving the local complexity under general informa- tion constraints (such as e-local differential privacy constraint), and extending this results to the distribution-free setting (i.e. the frequency estimation problem).

---

Acknowledgments
This work was supported in part by a Google Faculty Research Award, a National Semiconductor Corporation Stanford Graduate Fellowship, and the National Science Foundation under grants CCF- 1704624 and NeTS-1817205.
References
[1] K. Pearson, "Contributions to the mathematical theory of evolution," Philosophical Transactions of the Royal Society of London. A, vol. 185, pp. 71-110, 1894.
[2] A. Garg, T. Ma, and H. Nguyen, "On communication cost of distributed statistical estimation and dimensionality," in Advances in Neural Information Processing Systems, pp. 2726-2734, 2014.
[3] Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, al., "Advances and open problems in federated learning," arXiv preprint arXiv:
2019.
[4] Y. Han, P. Mukherjee, A. Ozgur, and T. Weissman, "Distributed statistical estimation of high- dimensional and nonparametric distributions." in 2018 IEEE International Symposium on Information Theory (ISIT), pp. 506-510, IEEE, 2018.
[5] J. Acharya, C. L. Canonne, and H. Tyagi, "Inference under information constraints: Lower bounds from chi-square contraction," " in Conference on Learning Theory, pp. 3-17, PMLR, 2019.
[6] J. Acharya, C. L. Canonne, and H. Tyagi, "Inference under information constraints ii: Commu- nication constraints and shared randomness," arXiv preprint arXiv: 093000 2019.
[7] Y. Han, A. Özgür, and T. Weissman, "Geometric lower bounds for distributed parameter estimation under communication constraints," Conference On Learning Theory, pp. 3163- 3188, PMLR, 2018.
[8] I.. P. Barnes, Y. Han, and A. Ozgur, "Lower bounds for learning distributions under communica- tion constraints via fisher information." " 2019.
[9] Acharya, C. L. Canonne, and H. Tyagi, "General lower bounds for interactive high- dimensional estimation under information constraints," arXiv preprint arXiv:2010.06562, 2020.
[10] Acharya, Kairouz, Y. Liu, and Sun, "Estimating sparse discrete distributions under local privacy and communication constraints," in Algorithmic Learning Theory, PMLR, 2021.
[11] L. P. Barnes, W.-N. Chen, and A. Ozgur, "Fisher information under local differential privacy." arXiv preprint urXiv:2005. 10783, 2020.
[12] R. E. Barlow, "Statistical inference under order restrictions; the theory and application of isotonic regression," tech. rep., 1972.
[13] L.. Devroye and I.. Gábor, Nomparametric Density Estimation: The Ll View. Wiley Interscience Series in Discrete Mathematics, Wiley, 1985.
[14] L. Devroye and G. Lugosi, Combinatorial Methods in Density Estimation. Springer Series in Statistics, Springer New York, 2012.
[15] B. W. Silverman, Density Estimation for Statistics and Data Analysis. London: Chapman & Hall, 1986.
[16] W.-N. Chen, P. Kairouz, and A. Ozgur, "Breaking the ciamuunication-priaayy-eee trilemma," Advances in Neural Information Processing Systems, vol. 33, 2020.
[17] M. Ye and A. Barg, "Optimal schemes for discrete distribution estimation under local differential privacy." in 2017 IEEE International Symposium on Information Theory (ISIT), pp. 759-763,
June 2017.
[18] T. Wang. J. Blocki, N. Li, and S. Jha, "Locally differentially private protocols for frequency estimation," 26th (USENIX) Security Symposium ({USENIX Security 17), pp. 729-745, 2017.
10

---

[19] J. Acharya, Z. Sun, and H. Zhang. "Hadamard response: Estimating distributions privately, efficiently, and with little communication, The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1 1120-1122 2019.
[20] Acharya and Z. Sun, "Communication complexity in locally private distribution estimation and heavy hitters," in International Conference Machine Learning, pp. 51-60, 2019.
[21] R. Bassily and A. Smith, "Local, private, efficient protocols for succinct histograms," in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, (New York, NY, USA), p. 127-135, Association for Computing Machinery, 2015.
[22] R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta, "Practical locally private heavy hitters," in Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, (Red Hook, NY, USA), p. 2285- 2293, Curran Associates Inc., 2017.
[23] M. Bun, J. Nelson, and U. Stemmer, "Heavy hitters and the structure of local privacy," ACM Transactions on Algorithms (TALG), vol. 15, no. pp. 1-40. 2019.
[24] W. Zhu, P. Kairouz, B. McMahan, H. Sun, and W. Li, "Federated heavy hitters discovery
with differential privacy," in International Conference on Artificial Intelligence and Statistics,
pp. 3837-3847, PMLR, 2020.
[25] J. C. Duchi and F. Ruan, "The right complexity measure in locally private estimation: It is not the fisher information," arXiv preprint arXiv: 05756, 2018.
[26] E. Kushilevitz, "Communication complexity," in Advances in Computers, vol. 44, pp. 331-360. Elsevier, 1997.
[27] R. D. Gill, B. Y. Levit, et al., "Applications of the van trees inequality: bayesian cramér-rao bound," Bernoulli, vol. 1, no. 1-2, pp. 59-79, 1995.
[28] W.-N. Chen, P. Kairouz, and A. Özgür, "Breaking the dimension dependence in sparse distribu- tion estimation under communication constraints," arXiv preprint arXiv:2106.08597 2021.


Reviews:
[{"review_id": "v_4E9tWQhC", "reviewer": "Reviewer_qr7y", "summary": "This paper considers the estimation of a discrete distribution P on an alphabet of size d under communication constraints. Each local client holds a single observation from P and transmits no more than b bits to the central server. A two-round interactive scheme is proposed and achieves nearly optimal estimation error. The estimation error depends on the Rényi entropy of P instead of the global parameter d. The minimax lower bound is also derived in this paper. ", "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": "Overall the problem considered is of broad interest and the results in this paper are solid. The fundamental limit on the communication resources in terms of the Rényi entropy is one significant contribution of the current paper. The main concern is on the additional terms of Theorems 2.1 and 2.2 (hidden from the abstract when n is sufficiently large). The quantitative implication is n=poly(d), which appears unrealistic and should be properly justified. With so many clients, the total communication costs are still high. This issue also concerns Theorem 2.4 where the local region scales with n. More issues in Theorem 2.4: the set $\\mathcal{P}_d'$ is introduced without context; the term $\\delta>0$ is not really arbitrary as $c_\\delta$ vanishes with $\\delta$, so it should be optimized if possible. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the paper. The potential negative societal impacts are not available as the paper is mostly on the theoretical aspects. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cQlX1omq3bh", "reviewer": "Reviewer_JieB", "summary": "The paper studies estimating an unknown discrete distribution over $d$ symbols from its samples observed under $b$-bit communication constraint. The main result states that for a sufficiently large sample size $n$, the optimal $\\ell_2$ error is essentially \n$\\Theta \\left(\n\\frac{\\lVert p \\rVert_{1/2}}{n2^b}\n\\lor\n\\frac1n\n\\right)$.\nThe paper also obtains an upper bound on the $\\ell_1$ learning rate without a matching lower bound. \nThe optimal interactive scheme first finds a coarse estimate of the underlying distribution with an existing minimax approach, \nthen refines the result using this estimate and an independent sample. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Pros:\n1. The paper is well-written and provides appropriate examples and plots. \n2. I appreciate the authors' efforts to develop the proposed learning scheme that achieves near-optimal performance for every distribution. The idea is also natural enough to lead to a simple algorithm.\n3. The results also imply a logarithmic improvement over an existing scheme on $s$-sparse distributions, though under a different setting. \n\nCons:\n1. It seems that the results, including Theorems 2.1, 2.2., and 2.4, hold only for large sample sizes $n$, e.g., $n\\gtrsim d^3$. I wonder if this is the case for practical applications. As per my understanding, these types of distribution learning applications often involve large alphabets. \n2. The minimax lower bound in Theorem 2.4 considers the supremum over distributions $p'$ satisfying $\\lVert p' - p\\rVert_\\infty \\le \\sqrt{\\frac{\\lVert p\\rVert_{1/2}}{n d 2^{b}}}$. I wonder if the $\\ell_{1/2}$-norm values remain close to that of $p$ or not, which is critical to the merits of the lower bound. \n3. The optimality of the results on the $\\ell_1$ norm is unclear. From my perspective, $\\ell_1$ distance is probably a better measure for distribution learning as it directly relates to classification errors in hypothesis selection. \n4. In line 191, the paper claims that the scheme is minimax optimal over $\\mathcal P_{d, s}$. I can see the upper bound, but not a (nearly matching lower bound for $s$-sparse distributions. Note that the prior work [10] considers the problem under the non-interactive setting, which is more restrictive. \n5. Line 193 states that \"since $\\beta$ is constant,\" I wonder why this is the case and note that Corollary 3.2 assumes only $\\beta\\in(0, 1/3)$. Also, Line 204 claims that the results in [10] do not apply to geometric and Zipf distributions. My thought is that these distributions have small \"effective support sizes,\" learnable with a standard minimax algorithm. \n\nAdditional suggestion:\n1. It might be better if the authors can shorten the abstract as it has 20 lines of text.\n2. It seems reasonable to consider experiments in more practical settings, such as those mentioned in the Introduction. \n\n \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations of their work and marked N/A for the potential negative societal impact of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_5jrbPOLnK9", "reviewer": "Reviewer_d6xD", "summary": "The paper studies distributed estimation of a discrete, $d$-dimensional law $p$ under communication constraints (wherein each client may only send $b$ bits) in a sequential model (wherein clients are ordered, and are aware of messages sent by earlier clients when preparing their message). \n\nThe authors describe what is essentially a two-stage scheme that first obtains a crude estimate of the law using a minimax scheme. This estimate yields a sense of which elements of the law are large, and subsequent communications are designed that provide more samples for such elements, the precise weighting of which depends on the error metric being controlled. As a result, if the number of clients is large enough ($n \\gg d^3\\log d$ for squared-$\\ell_2$ error), the resulting estimate for the squared-$\\ell_2$ criterion has error decaying as $\\max( \\\\| p\\\\|_{1/2}2^{-b} , 1)/n$. Both stages of the scheme use the grouping idea of Han et al [4].\n\nThe above scheme is complemented by a lower bound for the $\\ell_2$ criterion, which shows that under the same large $n$ condition, a matching lower bound but with a $(1+\\delta)/2$ norm instead of the $1/2$ norm, lending a measure of tightness to the achievability analysis. This is derived via a Fisher information technique due to Barnes et al, and a nice construction of a parametric family of discrete laws in which the lowest $d-h$ masses are fixed. Under some auxiliary conditions, the resulting bound depends linearly on $h^2 p_{(h)},$ where $p_{(h)}$ is the $h$th biggest entry of $p$, and this quantity is characterised in terms of the $1/2$ and $(1+\\delta)/2$ norms.\n\nTogether, these results almost characterise the bit-rate needed by each client to ensure optimal estimation, specifically the $1/2$-Renyi entropy of $p.$ This immediately leads to improved rates for spase, and for highly skewed laws.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "Post Rebuttal: thanks for the clarifications. I think my view basically remains the same.\n\n----\n\n\nI think the paper discusses a relevant problem, and the proposed scheme and lower bound are quite elegant. Pointwise results are always particularly interesting, and the bound of this paper are novel, and offer a broad insight into distributed estimation. It's particularly nice that these offer direct improvements for cases such as sparsity.\n\nPerhaps the biggest weakness of the analysis is the large error terms, which require a large number of clients to be effective. Equivalently, the results of the paper do not offer improvements on sample complexity of the tasks for a given bitrate. On the whole this is not a deal breaker - I think there may well be regimes where one does have access to a large number of clients, none of which can communicate much (although whether such a situation would admit the sequential model is a little questionable). I think that the paper should discuss this aspect explicitly [*], and contextualise the analysis by describing application domains where such an assumption is reasonable (and ideally also where it is not). In addition, a discussion of whether the authors believe that these terms are an artifact of the analysis or more fundamental would also be useful to the community. \n\n[*] while the authors are conscientious about stating the bounds completely and acknowleding the requirements on $n$, I think this is not enough.\n\n---\n\nClarity: The paper is mostly well written, and the approach is well explained. The related work described is, to my knowledge, adequate, and the results are properly contextualised with respect to these (barring a frank discussion of the size of $n$, as I discussed above). I think the paper can benefit from explaining where the particular form of the $n_j$ comes from. This seems not hard to motivate, at least for the $\\ell_2$ squared error - using the explanation on line 267, the net error behaves as $\\sum p_j/n_j$, and since no client can account for more than $2^b-1$ symbols, there's a sum constraint on the $n_j$, and minimising under it leads to the choice of $n_j \\propto \\sqrt{p_j}$.\n\n----\n\nA few minor points that need correction:\n\n- Equation (2) is missing a factor of $2$ somewhere (there are only $n/2$ clients).\n\n- The event $\\mathcal{E}$ on 257 should be an intersection of each of the $\\sqrt{\\hat{p_j}}$ being close, not a union. Similarly for $\\mathcal{E}_1$ in the appendix. \n\n- Equation (6) is not quite right - the Binomial tails flatten at the extremes, due to which if $n' p$ is small, then concentration at $\\sqrt{\\varepsilon_n p}$ as claimed is not right, and instead we have something like (Bernstein's inequality) $\\hat{p} \\in p \\pm \\max(\\epsilon_n, \\sqrt{\\varepsilon_n p})$. The argument can be fixed by separately considering the case $p < \\varepsilon_n \\implies \\hat{p} < 2\\varepsilon_n $ which directly gives $|\\sqrt{p} - \\sqrt{\\hat{p}}| \\le 3\\sqrt{\\varepsilon_n}.$ Also, for completeness' sake, the usual statement of Hoeffding's inequality is not sensitive to the variance, and something like Bernstein's or Bennet's is needed.\n\n- The proof for $C_\\delta = \\delta^{2/(1+\\delta)} $ in Lemma 6.2 does not quite follow (in fact $\\sum_{h \\in \\mathbb{N}} 1/h^{1 + \\delta} > 1/\\delta  $). This is not a big deal, since the bound $\\sum_{h \\in \\mathbb{N}} 1/h^{1 + \\delta} \\le 1 + 1/\\delta  $ is true, and this in turn gives $C_\\delta = (\\delta/(1+\\delta) )^{2 / (1 + \\delta)},$ which has the same qualitative behaviour for the relevant small $\\delta$.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations with respect to $n$ should be discussed more deeply, as described above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "XbVM9oLpGZr", "reviewer": "Reviewer_PqZC", "summary": "This paper considers \"instance-optimality\" of discrete distribution estimation under communication constraints for interactive schemes where each client receives a single sample from the distribution p. The focus is on the small alphabet regime (d<<n). Upper bounds for $l_2$ error feature the half norm and for $l_1$ error feature the one-third norm. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 paper considers a problem of significant interest. This is the first work to consider instance-optimality in communication constrained settings. The writing is clear for most of the part, except the lower bound. It appears as if the authors copy-pasted parts of the lower bound proof in haste since there are symbols such as $S'_{\\theta}(X)$ that have not been defined in the main text and there are references to equation numbers (7) and Lemma E.1 that can be found in the appendix. \nCouple of concerns:\n1) In the local refinement round, the knowledge of the groups is available at the server after the localization round. It's then not clear how this is available to clients since the knowledge of $\\mathcal{J}_i$ is necessary to send the ranking of the symbol it receives. \n\n2) Line 263 states that symbols with larger $p_j$ have a larger estimation error. It's not clear why this should be the case when one would expect that a higher probability symbol might be seen often and therefore be estimated more accurately. \n\nOverall, I would have preferred more discussion about the intuition behind the local refinement scheme (for e.g. some explanation for why it works well). It is also worth pointing out in the related works section that most works that analyze the minimax settings focus on the large alphabet regime. \n\nSome typos: \n1) Pg 7, line 257, is the union an intersection? \n2) Pg 8, line 263 - comma instead of period\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am satisfied with the limitations that have been addressed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the reviews and discussion, I am inclined to recommend the acceptance of this paper.  The reviewers generally appreciate the importance of the problem, and the contributions made, particularly studying instance-optimality in a communication-constrained setting.  However, the reviewers do maintain some concerns, some of which are quoted as follows:
- "I still think $n\ge d^3$ is restrictive (also much worse than $d^2$ you mentioned). Even in applications where the number of samples is larger than the domain size, $d^3$ easily blows up. As other quantitative results are available, it is important to include proper discussions such as why you believe the transition happens at $d^3$."
- "I don't agree with "the scaling of our lower can be made arbitrarly close to the upper bound" due to the extra vanishing $c_\delta$. I do appreciate the lower bound $\Vert p\Vert_{1/2} /\log d $ though."
- "Perhaps the biggest weakness of the analysis is the large error terms, which require a large number of clients to be effective. Equivalently, the results of the paper do not offer improvements on sample complexity of the tasks for a given bitrate."
- "the authors claimed that their min-max Lower Bound is stronger because they maximize over a larger domain, not making intuitive sense. For another example, the authors commented that the $\ell_2$ error is equally important as the $\ell_1$ error for assessing discrete distribution learners. I don't think this is the case in the literature, and the $\ell_2$-type results are often much easier to derive. In particular, the authors also admitted that the $\ell_1$ problem remains "open." "

I believe that these are valid concerns, but at the same time, none of them were viewed as strong reasons for rejection, and one reviewer was willing to champion the paper more strongly, hence my recommendation.

In the final version of the paper, I ask that the authors carefully take the above comments *and* all of the reviews into careful consideration.
Decision: Accept (Poster)