Pointwise Bounds for Distribution Estimation under Communication Constraints
Year: 2022

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 pointwise bounds that depend on the target distribution p. In particular, we show that the `2 error decays with O ⇣ max ⇣kpk1/2 n2b , 1 n ⌘⌘ when n is sufficiently large, hence it is governed by the 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. This two-round scheme extends to `q loss with q 1, and hence gives pointwise upper bounds on `q error. We also develop a new local minimax lower bound with (almost) matching `2 error, showing that any interactive scheme must admit a ⌦ ⇣kpk(1+ )/2 n2b ⌘ `2 error for any > 0. Our upper and lower bounds together indicate that the H1/2(p) , log(kpk1/2) bits of communication is both sufficient and necessary to achieve the optimal (centralized) performance, where H1/2(p) is the Rényi entropy of order 2. Therefore, under the `2 loss, the correct measure of the local communication complexity at p is its Rényi entropy.

text: ⇣ max ⇣kpk1/2 n2b , 1 n ⌘⌘ when n is sufficiently large, hence it is governed by the 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. This two-round scheme extends to `q loss with q 1, and hence gives pointwise upper bounds on `q error. We also develop a new local minimax lower bound with (almost) matching `2 error, showing that any interactive scheme must admit a ⌦ ⇣kpk(1+ )/2 n2b ⌘ `2 error for any > 0.
Our upper and lower bounds together indicate that the H1/2(p) , log(kpk1/2) bits of communication is both sufficient and necessary to achieve the optimal (centralized) performance, where H1/2(p) is the Rényi entropy of order 2. Therefore, under the `2 loss, the correct measure of the local communication complexity at p is its Rényi entropy.

heading: 1 Introduction
text: Learning a distribution from its samples has been a fundamental task in unsupervised learning dating back to the late nineteenth century [1]. This task, especially under distributed settings, has gained growing popularity in the recent years as data is 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 a bottleneck hampering the training of highaccuracy machine learning models [2]. This is even more so for federated learning and analytics type settings [3] which rely on wireless mobile links for communication.
To resolve this issue, several communication-efficient distribution learning schemes have been recently proposed and studied in the literature (see Section 1.2 for a thorough discussion). On the positive side, the state-of-the-art schemes are known to be worst-case (minimax) optimal as they have been shown to achieve the information-theoretic lower bounds on the global minimax error [4–8]. On the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
negative side, however, the `2 estimation error achieved by these schemes scales as O( dn2b ) under a b-bit communication constraint on each sample, where d 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 [8, 9].
A recent work [10] has moved a step forward from the “global minimax regime” by restricting the target distribution p to be s-sparse and showing that the `2 error can be reduced to O( s log dn2b ) in this case, i.e. the error depends on the sparsity s rather than the ambient dimension d. However, their scheme heavily relies on the s-sparse assumption and requires knowing s 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.
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 a measure of local complexity that captures the hardness of estimating 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, a 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 a specific p under communication constraints. In particular, under the `2 loss, we show that the local complexity of estimating p is captured by its half-norm1 kpk 1
2 : we propose a two-round interactive scheme
that uniformly achieves the O ⇣ max ⇣kpk1/2 n2b , 1 n ⌘⌘ error under `2 loss2 which requires no prior 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 ⇣kpk1+ /2 n2b , 1 n ⌘⌘ for any > 0 when n is sufficiently large.
These upper and the lower bounds together indicate that kpk1/2 plays a fundamental role in distributed estimation and that the dlog(kpk1/2)e 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.e. H1/2(p) , log(kpk1/2), showing that under the `2 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( dn2b ), we see that when we move toward the local regime, the linear dependency on d in the convergence rate is replaced by kpk1/2. This dimension independent convergence is also empirically verified by our experiments (see Section 3 for more details). Note that kpk1/2 < d, so our proposed scheme is also globally minimax optimal. Moreover, since kpk1/2 < kpk0, our scheme achieves the O( s n2b ) convergence rate under the s-sparse model [10], which improves the O( s log(d/s)n2b ) upper bound in [10] by further shaving off the additional log(d/s) 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 to 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.
Our techniques Our proposed two-round interactive scheme is based on a local refinement approach, where in the first round, a standard (global) minimax optimal estimation scheme is applied 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 localizationrefinement 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 introduced in [11]. However, in order to obtain a local bound around p, we develop a new approach that
1Here we generalize the notion of q-norm kpkq , ⇣Pd i=1 p q i ⌘1/q to q 2 [0, 1]. 2Our scheme also guarantees pointwise upper bounds on `1 or general `q errors. See Theorem 2.2.
first finds the best parametric sub-model containing p, and then upper bounds its Fisher information in a 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 be of independent interest, e.g. to derive pointwise lower bounds for other estimation models under general information constraints.

heading: 1.1 Notation and Setup
text: The general distributed statistical task we consider in this paper can be formulated as follows. Each one of the n clients has local data Xi ⇠ p, where p 2 Pd and Pd , n p 2 Rd+ P j pj = 1 o
is the collection of all d-dimensional discrete distributions. The i-th client then sends a message Yi 2 Y to the server, who upon receiving Y n aims to estimate the unknown distribution p.
At client i, the message Yi is generated via a 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 Wi of the i-th client can depend on all previous messages Y1, ..., Yi 1. Formally, it can be written as a randomized mapping (possibly using shared randomness across participating clients and the server) of the form Wi(·|Xi, Y i 1), and the b-bit communication constraint restricts |Y|  2b. As a special case, when Wi depends only on Xi and is independent of the other messages Y i 1 for all i (i.e. Wi(·|Xi, Y i 1) = Wi(·|Xi)), we say the corresponding protocol is non-interactive. Finally, we call the tuple (Wn, p̂(Y n)) an estimation scheme, where p̂ (Y n) is an estimator of p. We use ⇧seq and ⇧ind to denote the collections of all sequentially interactive and non-interactive schemes respectively.
Our goal here is to design a scheme (Wn, p̂ (Y n)) to minimize the `2 (or `1) estimation error: r (`2, p, (Wn, p̂)) , E[kp p̂ (Y n)k22], for all p 2 Pd, as well as characterizing the best error achievable by any scheme in ⇧seq. We note that while our impossibility bounds hold for any scheme in ⇧seq, the particular scheme we propose uses only one round of interaction.For `1 error, we replace k·k22 in the above expectations with k·k1. In this work, we mainly focus on the regime 1 ⌧ d ⌧ n, aiming to characterize the statistical convergence rates when n is sufficiently large.

heading: 1.2 Related works
text: Estimating discrete distributions is a fundamental task in statistical inference and has a rich literature [12–15]. Under communication constraints, the optimal convergence rate for discrete distribution estimation was established in [4–8, 16] for the non-interactive setting, and [8, 9] for the general (blackboard) interactive model. The recent work [10] considers the same task under the s 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.
A slightly different but closely related problem is distributed estimation of distributions [16–20] and heavy hitter detection under local differential privacy (LDP) constraints [21–24]. Although originally designed for preserving user privacy, some of these schemes can be made communication efficient. For instance, the scheme in [20] suggests that one can use 1 bit communication to achieve O(d/n) `2 error (which is global minimax optimal); the non-interactive tree-based schemes proposed in [22, 23] can be cast into a 1-bit frequency oracle, but since the scheme is optimized with respect to `1 error, directly applying their frequency oracle leads to a sub-optimal convergence O ⇣ s(log d+logn)
n
⌘ in `2.
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-dimensional settings.
Organization The rest of the paper is organized as follows. In Section 2, we present our main 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
upon previous global minimax results. In Section 4, 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.

heading: 2 Main results
text: Our first contribution is the design of a two-round interactive scheme (see Section 4 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 `2 upper bound) For any b  blog2 dc, there exist a sequentially interactive scheme (Wn, p̌) 2 ⇧seq, such that for all p 2 Pd,
r (`2, p, (W n , p̌))  C1
1 n + C2
kpk 1 2
n2b + C3
d 3 log(nd)
(n2b)2 ⇣
kpk 1 2 + on(1)
n2b , (1)
where C1, C2, C3 > 0 are some universal constants (which are explicitly specified in Section 5). This implies that as long as n = ⌦ ⇣ d3 log d 2bkpk1/2 ⌘ , r (`2, p, (Wn, p̌)) = O ⇣ max ⇣kpk1/2 n2b , 1 n ⌘⌘ .
In addition to the `2 error, by slightly tweaking the parameters in our proposed scheme, we can obtain the following pointwise upper bound on the `1 (i.e. the total variation) error:
Theorem 2.2 (Local `1 upper bound) For any b  blog2 dc, there exists a sequentially interactive scheme ⇣ W̃ n , p̌ ⌘ 2 ⇧seq, such that for all p 2 Pd,
r ⇣ `1, p, ⇣ W̃ n , p̌ ⌘⌘  C1
s kpk 1
2
n + C2
s kpk 1
3
n2b + C3
s d4 log (nd)
(n2b)2 ⇣
s kpk 1
3 + on(1)
n2b ,
where C1, C2, C3 > 0 are some universal constants. Hence as long as n = ⌦ ⇣
d4 log d 2bkpk1/3
⌘ ,
r (`1, p, (Wn, p̌)) = O ✓ max ✓q kpk1/3 n2b , q kpk1/2 n ◆◆ .
Theorem 2.1 implies that the convergence rate of the `2 error is dictated by the half-norm of the target distribution p while Theorem 2.2 implies that the `1 error is dictated by the one-third norm of the distribution. In general, we can optimize the encoding function with respect to any `q loss for q 2 [1, 2] and the quantity that determines the convergence rate becomes the qq+2 -norm (see Remark C.1 for details). We also remark that the large second-order terms in Theorem 2.1 and Theorem 2.2 are generally inevitable. See Appendix A.1 for a discussion. The proofs of Theorem 2.1 and Theorem 2.2 are given in Section 5 and Appendix C respectively.
Next, we complement our achievability results with the following minimax lower bounds.
Theorem 2.3 (Global minimax lower bound) For any (possibly interactive) scheme, it holds that
inf (Wn,p̂)2⇧seq sup p:kpk1/2h
EX⇠p h kp̂(Wn(Xn)) pk22 i = ⌦
✓ h
n2b
◆ .
Note that the lower bound in Theorem 2.3 can be uniformly attained by our scheme even if no information on the target set of distributions, i.e. the parameter h is available, indicating that our proposed scheme is global minimax optimal. The proof can be found in Section D.
Theorem 2.4 (Local minimax lower bound) Let p 2 P 0d , p 2 Pd 1 2 < p1 < 2 3 . Then for any
> 0, B q
kpk1/2 d2b , as long as n = ⌦ ⇣ d3 log d kpk1/2 ⌘ , it holds that3
inf (Wn,p̂)2⇧seq sup p0:kp0 pk1 Bp n
Ep0 h kp̂ (Wn(Xn)) p0k22 i 1
n2b max
c kpk 1+
2 ,
c1 kpk 1 2
log d
! + c2
n ,
for some c , c1, c2 > 0.
Remark 2.1 Note that in Theorem 2.4, the `1 neighborhood n p 0 : kp0 pk1  Bp n o is strictly smaller than the following `2 neighborhood: n p 0 : kp0 pk2  q kpk1/2/(2bn) o (since
Bd,`1( 1pd ) ⇢ Bd,`2(1)). Therefore, in Theorem 2.4 we present a slightly stronger statement.
Theorem 2.4 indicates that our proposed scheme is (almost) optimal when n is sufficiently large and that kpk1/2 is the fundamental limit for the estimation error. This conclusion implies that under `2 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 6.
Corollary 2.1 When n is sufficiently large, dlog(kpk1/2)e bits of communication is both sufficient and necessary to achieve the convergence rate of the centralized setting under `2 loss. Similarly, dlog(kpk1/3)e bits are sufficient for `1 loss.
In addition, observe that the quantities log(kpk1/2) and 1 2 log ((pk1/3) are the Rényi entropies of order 1/2 and 1/3, denoted as H1/2(p) and H1/3(p), respectively. In other words, the communication required to achieve the optimal (i.e. the centralized) rate is determined by the Rényi entropy of the underlying distribution p.
Finally, we remark that when the goal is to 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 in the above corollary can be achieved without knowing H1/2(p) beforehand. See Appendix A.2 for a discussion.

heading: 3 Examples and experiments
text: Next, we demonstrate by several examples and experiments that our results can recover earlier global minimax results and can significantly improve them when the target distribution is highly skewed.
Corollary 3.1 (s-sparse distributions) Let Ps,d , p 2 [0, 1]d P pi = 1, kpk0  s
. Then as long as n large enough, there exists interactive schemes (Wn, p̌) and (W̃n, p̌) such that r (`2, p, (Wn, p̌)) = O( s n2b ) and r ⇣ `1, p, ⇣ W̃ n , p̌ ⌘⌘ = O( p s n2b ).
The above result shows that our scheme is minimax optimal over Pd,s. This recovers and improves (by a factor of log d/s) the results from [10] on the `1 and `2 convergence rates for s-sparse distributions4.
Corollary 3.2 (Truncated geometric distributions) Let p , Geo ,d be the truncated geometric distribution. That is, for all 2 (0, 1] and k 2 [d], Geo ,d(k) , 1 (1 d) k. Then if n = ⌦ d 3 log d/2b ,
r (`2, p, (W n , p̂)) = O
1 n2b (1 +
p )(1 p d )
(1 p )(1 + p d )
! = O ✓ max ✓ 1
n(1 p )2b
, 1
n
◆◆ .
3Indeed, the lower bound holds for blackboard interactive schemes [26], a more general class of interactive schemes than ⇧seq. See [8] for a discussion of blackboard schemes.
4We remark, however, that their scheme is non-interactive and has smaller minimum sample size requirement.
This result shows that if is constant for the truncated geometric distribution, 1 bit suffices to achieve the centralized convergence rate O
1 n in this case. Note that this is a significant improvement
over previous minimax bounds on the the `2 error which are O( dn2b ) [4]. This suggests that the corresponding minimax optimal scheme is suboptimal by a factor of d when the target distribution is truncated geometric. Our results suggest that the `2 error should not depend on d at all, and Figure 1 provides empirical evidence to justify this observation.
Corollary 3.3 (Truncated Zipf distributions with > 2) Let p , Zipf ,d be a truncated Zipf distribution with 2. That is, for k 2 [d], Zipf ,d(k) , k Pd
k0=1(k 0)
. Then the local
complexity of p is characterized by kpk1/2 = ⇥ ✓⇣ 1 d /2+1 1 d +1 ⌘2◆ = ⇥(1). So in this case,
r (`2, p, (Wn, p̂)) = O 1 n , as long as n = ⌦ d 3 log d/2b .
We leave the complete characterization for all > 0 to Section E in appendix. Note that since both Geo ,d and Zipf ,d 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 O
d n2b `2 error. Again, our results suggest that this is suboptimal by a factor of d.
In Figure 1, we empirically compare our scheme with [4] (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 d. 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 error of the minimax scheme scales linearly in d. This phenomenon is justified by Corollary 3.2.

heading: 4 The localization-refinement scheme
text: In this section, we introduce our two-round localization-refinement scheme and show how it locally refines a global minimax estimator p̂ 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 bd/(2b 1)c subsets each of size (2b 1), and each of the first n/2 clients is assigned one of these subsets (each subset is assigned to (n/2)/(d/(2b 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 p̂ with error E[kp p̂k22] ⇣ P j pj/n2
b = O(d/n2b). Then in the second round (the refinement phase), we locally refine the estimate by adaptively assigning more “resources” (i.e. samples), according to p̂ obtained from the first round, to the more difficult symbols (i.e. j 2 [d] with larger error
Algorithm 1: uniform grouping [4] (at client i) Input: Xi 2 [d], b 2 N Compute M = d/ 2b 1 ;
m imodM , Yi 0; if Xi 2 ⇥ (m 1)(2b 1) + 1 : m(2b 1) ⇤ then
Yi Xi mod (2b 1) end
return Yi
Algorithm 2: localize-and-refine (at client i) Input: Xi 2 [d], b 2 N, p̂ (G1, ...,Gd) gen_group (p̂, d), Yi 0 ; Compute Ji , {j 2 [d]|i 2 Gj} ; if Xi 2 Ji then
Yi the ranking of Xi in Ji end
return Yi
E ⇥ (p̂j pj)2 ⇤ ). In particular, under the `2 loss, the number of samples assigned to symbol j will be roughly in proportional to ppj . 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 1 (localization): In the first round, the first n/2 clients collaboratively produce a coarse estimate p̂ = (p̂1, ..., p̂j) for the target distribution p via the grouping scheme described above (this is the minimax optimal scheme proposed in [4], see Algorithm 1 for details). Note that in general, this scheme can be replaced by any non-interactive minimax optimal scheme.
Round 2 (local refinement): Upon obtaining p̂ from the first round, the server then computes ⇡(p̂) : Pd ! Pd, where the exact definition of ⇡ depends on the loss function. ⇡ will be used in the design of the rest n/2 clients’ encoders. In particular, for `2 loss, we set ⇡j(p) , p pjP
k2[d] p pk ; for `1
loss, we set ⇡j(p) , 3 p pjP
k2[d] 3 p pk . For notational convenience, we denote ⇡ (p̂) as ⇡̂ = (⇡̂1, ..., ⇡̂d).
To design the encoding functions of the remaining n/2 clients, we group them into d (possibly overlapping) sets G1, ...,Gd with
|Gj | = nj , n
2
✓ min ✓ 1, (2b 1) ✓ ⇡̂j
4 +
1
4d
◆◆◆ , (2)
for all j 2 [d]. We require the grouping {Gj} to satisfy the following properties: 1) each {Gj} consists of nj distinct clients, and 2) each client i is contained in at most (2b 1) groups. Notice that these requirements can always be attained (see, for instance, Algorithm 3 in Section B). We further write Ji to be the set of indices of the groups that client i belongs to (i.e. Ji , {j 2 [d]|i 2 Gj}), so the second property implies |Ji|  2b 1 for all i. As in the first round, client i will report its observation if it belongs to the subset Ji. Since |Ji|  2b 1, client i’s report can be encoded in b bits. Note that with this grouping strategy each symbol j is reported by clients in Gj , hence the server can estimate pj by computing p̌j(Y n) , P i2Gj {Xi=j}
nj .
Note that the size of Gj is dictated by the estimate for pj obtained in the first round. See Algorithm 2 for the details of the second round.
Remark 4.1 In the above two-round scheme, we see that the local refinement step is crucial for moving from the worst-case performance guarantee to a pointwise one. Therefore we conjecture that the local lower bound in Theorem 2.4 cannot be achieved by any non-interactive scheme.

heading: 5 Analysis of the `2 error (proof of Theorem 2.1)
text: In this section, we analyze the estimation errors of the above two-round localization-refinement scheme and prove Theorem 2.1. Before entering the main proof, we give the following lemma that controls the estimation error of between p̂ and ⇡.
Lemma 5.1 Let (Wn, p̂) be the grouping scheme given in Algorithm 1. Then with probability at least 1 1nd , it holds that ppj p p̂j  p"n and 3ppj 3 p p̂j  3p"n, where "n , 3d log(nd)n2b .
Now consider the scheme described in Section 4. After the first round, we obtain a coarse estimate p̂ = (p̂1, ..., p̂j). Set E , T j2[d] p p̂j 2 ⇥p pj p "n, p pj + p "n ⇤ . Then by Lemma 5.1 and taking the union bound over j 2 [d], we have P {E} 1 1n . In order to distinguish the estimate obtained from the first round to the final estimator, we use p̌j to denote the final estimator.
Now observe that the `2 estimation error can be decomposed into
E h kp p̌k22 i = P {Ec}E h kp p̌k22 Ec i + P {E}E h kp p̌k22 E i (a)  2
n + E
h kp p̌k22 E i
where (a) holds since kp p̌k22  2 almost surely. Hence it remains to bound E h kp p̌k22 E i . Next,
as described in Section 4, we partition the second n/2 clients into d overlapping groups G1, ...,Gd according to (2). The reason we choose nj in this way is to ensure that 1) for symbols with larger pj (which implies larger estimation error), we allocate them more samples; 2) every symbol is assigned with at least ⇥(n/d) samples.
Clients in Gj then collaboratively estimate pj . In particular, client i reports her observation if Xi 2 Ji , {j|i 2 Gj}, and the server computes p̌j(Y n|p̂) , P i2Gj {Xi=j}
nj ⇠ 1nj Binom(nj , pj).
Finally, the following lemma controls E h kp p̌k22 E i , completing the proof of Theorem 2.1.
Lemma 5.2 Let p̌ be defined as above. Then E h kp p̌k22 E i  6n2b ⇣P j2[d] p pj ⌘2 + 10d 2"n n2b + 1 n .
For the `1 error, we set ⇡j(p) , 3 p p jP
k 3 p pk . Following the similar but slightly more sophisticated analysis, we obtain Theorem 2.2. The detailed proof is left to Section C in appendix.

heading: 6 The local minimax lower bound (proof of Theorem 2.4)
text: Our proof is based on the framework introduced in [8], where a global upper bound on the quantized Fisher information is given and used to derive the minimax lower bound on the `2 error. We extend their results to the local regime and develop a local upper bound on the quantized Fisher information around a neighborhood of p.
To obtain a local upper bound, we construct an h-dimensional parametric sub-model ⇥hp that contains p and is a subset of Pd, where h 2 [d] is a tuning parameter and will be determined later. By considering the sub-model ⇥hp , we can control its Fisher information around p with a function of h and p. Optimizing over h 2 [d] yield an upper bound that depends on kpk 1
2 . Finally, the local upper
bound on the quantized Fisher information can then be transformed to the local minimax lower bound on the `2 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(d)) be the sorted sequence of p = (p1, p2, ..., pd) in the non-increasing order; that is, p(i) p(j) for all i > j. Denote ⇡ : [d] ! [d] as the corresponding sorting function5, i.e. p(i) = p⇡(i) for all i 2 [d].
Constructing the sub-model ⇥hp We construct ⇥hp by “freezing” the (d h) smallest coordinates of p and only letting the largest (h 1) coordinates to be free parameters. Mathematically, let
⇥hp , (✓2, ✓3, ..., ✓h) ⇡ 1 ✓1, ✓2, ..., ✓h, p(h+1), p(h+2), ..., p(d) 2 Pd , (3)
where ✓1 = 1 Ph i=2 ✓i Pd
i=h+1 pi is fixed when (✓2, ..., ✓h) are determined. For instance, if p =
1 16 , 1 8 , 1 2 , 1 16 , 1 4 (so d = 5) and h = 3, then the corresponding sub-model is
⇥hp , ⇢ (✓2, ✓3) ✓ 1
16 , ✓3, ✓1,
1
16 , ✓2
◆ 2 Pd .
5With a slight abuse of notation, we overload ⇡ so that ⇡ ((p1, ..., pd)) , (p⇡(1), ..., p⇡(d))
Bounding the quantized Fisher information Next, under this model, we control the quantized Fisher information in the following lemma.
Lemma 6.1 Let W be any b-bit quantization scheme and IW (✓) be the Fisher information of Y at ✓ where Y ⇠ W (·|X) and X ⇠ p✓. Let 0 < B  p(h) 3 and p 2 P 0 d , p 2 Pd 1 2 < p1 < 5 6 . Define the neighborhood NB,h(p) , ✓(p) + [ B,B]h (note that under this definition, NB,h(p) must be contained in ⇥hp ). Then
8✓0 2 NB,h(p), Tr (IW (✓0))  2b ✓ 6h+ 3
2p(h)
◆ .
Bounding the `2 error Applying [8, Theorem 3] on NB,h(p), we obtain
sup ✓02NB,h(p)
E  ✓̂ ✓0 2
2
h
2
n2b ⇣ 6h+ 32p(h) ⌘ + h⇡ 2 B2
h 2 p(h)
10n2b + 10hp(h)
B2
h 2 p(h) 20n2b , (4)
where the second inequality is due to hp(h)  1, and the third inequality holds if we pick B q hp(h) n2b . Notice that in order to satisfy the condition NB,h(p) ✓ ⇥hp , B must be at most p(h) 3 , so we have an implicit sample size requirement: n must be at least 3h2bp(h) .
Optimizing over h Finally, we maximize h2p(h) over h 2 [d] to obtain the best lower bound. The following simple but crucial lemma relates h2p(h) to kpk 1
2 .
Lemma 6.2 For any p 2 Pd and > 0, it holds that
kpk 1 2 max h2[d] h 2 p(h) max
⇣ C kpk 1+
2 , Ckpk 1 2 /log d
⌘ ,
for C , ⇣
1+
⌘ 2 1+
and a universal constant C small enough.
Picking h⇤ = argmaxh2[d] h2p(h) and by Lemma 6.2 and (4), we obtain that for all ✓̂
sup ✓02NBn,h⇤ (p)
E  ✓̂ ✓0 2
2
max C
0 kpk 1+ 2
n2b , C
0 kpk 1 2
n2b log d
! ,
as long as p 2 P 0d and Bn = q h⇤p(h⇤) n2b (a)  r d n2bkpk 1
2
, where (a) holds due to the second result of
Lemma 6.2 and h⇤  d. In addition, the sample size constraint that n must be larger than 3h ⇤
2bp(h⇤) can
be satisfied if n = ⌦ ✓
d3 log d 2bkpk 1
2
◆ since h ⇤
p(h⇤)  (h ⇤)3 log d Ckpk 1
2
 d 3 log d
Ckpk 1 2
, where the first inequality is due
to Lemma 6.2 and the second one is due to h⇤  d. The proof is complete by observing that
inf (Wn,p̂) sup p0:kp0 pk1Bn
E h kp̂ p0k22 i inf
(Wn,✓̂) sup ✓02NBn,h⇤ (p) E  ✓̂ ✓0 2 2 .

heading: 7 Conclusion and open problems
text: We have investigated distribution estimation under b-bit communication constraints and characterized the local complexity of a target distribution p. We show that under `2 loss, the half-norm of p dictates the convergence rate of the estimation error. In addition, to achieve the optimal (centralized) convergence rate, ⇥(H1/2(p)) bits of communication is both necessary and sufficient.
Many interesting questions remain to be addressed, including investigating if the same lower bound can be achieved by non-interactive schemes, deriving the local complexity under general information constraints (such as "-local differential privacy constraint), and extending this results to the distribution-free setting (i.e. the frequency estimation problem).

heading: Acknowledgments
text: 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 CCF1704624 and NeTS-1817205.

Review summaries:
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).   The 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].  The 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.  Together, 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. 

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  $\Theta \left( \frac{\lVert p \rVert_{1/2}}{n2^b} \lor \frac1n \right)$. The paper also obtains an upper bound on the $\ell_1$ learning rate without a matching lower bound.  The optimal interactive scheme first finds a coarse estimate of the underlying distribution with an existing minimax approach,  then refines the result using this estimate and an independent sample. 

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.