Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition
Year: 2022

Abstract:
We obtain tight minimax rates for the problem of distributed estimation of discrete distributions under communication constraints, where n users observing m samples each can broadcast only  ̧ bits. Our main result is a tight characterization (up to logarithmic factors) of the error rate as a function of m,  ̧, the domain size, and the number of users under most regimes of interest. While previous work focused on the setting where each user only holds one sample, we show that as m grows the ̧1 error rate gets reduced by a factor of Ô m for small m. However, for large m we observe an interesting phase transition: the dependence of the error rate on the communication constraint  ̧ changes from 1/ Ô 2 ̧ to 1/ Ô ̧.

text: Ô m for small m. However, for large m
we observe an interesting phase transition: the dependence of the error rate on the communication constraint ¸ changes from 1/ Ô 2¸ to 1/ Ô ¸.

heading: 1 Introduction

heading: 1.1 Background and motivation
text: We consider the problem of density estimation in a distributed setting where each of n users locally holds a dataset of m independent observations from an unknown discrete probability distribution, and a central server seeks to leverage their data in order to estimate this underlying distribution. This abstract formulation encompasses an array of crucial building blocks in areas such as federated learning, IoT, or measurement from deployed sensors, and has (along with some of its variants) received significant attention in recent years.
Our focus in this work is to understand how a bandwidth constraint at each user affects this learning task. Namely, to characterize the fundamental tradeoffs between communication, local sample size, and estimation error rate. Previous work on distributed estimation has focused primarily on the single-sample case where each user has exactly one draw from an unknown underlying distribution p. We consider the more general, more practical, and technically more involved setting where each of the n users holds m Ø 1 samples from a k-ary distribution, and can transmit ¸ bits to a central server. Our goal is to understand the minimax rates of estimating p in ¸1 distance. Before detailing our results and discussing their relation with prior work, we provide the necessary background and notation.

heading: 1.2 Problem setting and notation
text: Let k be a positive integer. Let k = {p = (p1, . . . , pk) œ Rk : p Ø 0, ÎpÎ1 = 1} denote the set of all probability distributions over a discrete domain of size k, which we assume without loss of generality is [k] := {1, 2, . . . , k}. For p, q œ k, the total variation (TV) distance between
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
p and q is TV(p, q) := supS™[k](p(S) ≠ q(S)). Here for a set S ™ [k], p(S) := q
xœS px. Each of n users observes m i.i.d. samples from the same (unknown) distribution p œ k. We write Xi = (X(1)i , X (2) i , . . . , X (m) i ) for the samples of the ith user, and Xn = (X1, X2, . . . , Xn) œ [k]nm for the collection of all nm samples. We denote the empirical frequencies of samples at user i by Mi, where, for x œ [k], Mi(x) := 1m qm j=1 1{X (j) i = x}.
Each user can only send an ¸-bit message, capturing their bandwidth constraints. In particular, user i is allowed to send a message Yi œ {0, 1}¸ to the central server through a channel Wi œ W¸, that is, a Markov kernel Wi : {0, 1}¸ ◊ [k]m æ [0, 1], where
Wi(y | x) = Pr (Yi = y | Xi = x) , ’x œ [k]m, y œ {0, 1}¸ . Intuitively Wi can be viewed as a randomized function that maps an input Xi to some ¸-bit string Yi, which represents the messaging scheme used by the user. We consider two standard types of protocols, noninteractive and interactive. In noninteractive protocols, all the channels Wis are chosen in parallel, and the messages are sent independently of each other with no shared random seed available. In (sequentially) interactive protocols, the choice of Wi may depend on the previous messages Y i≠1 := (Y1, Y2, . . . , Yi≠1); that is, the message sent by the ith user can depend on the messages sent by the previous users, and on a common random seed U (independent of the observations) available to all users.12
Distribution estimation. Upon observing the messages Y n := (Y1, Y2, . . . , Yn), the server estimates the underlying distribution p with an estimator ‚p : ({0, 1}¸)n æ k, with goal to minimize the expected total variation (TV) distance between p and ‚p. In this work, we are interested in studying the minimax risk for distribution estimation under ¸-bit communication constraints, defined as
R(¸, k, n, m) := min W nœWn
¸
min p̂ max pœ k E[TV(‚p(Y n), p)] (1)
where the minimum is taken over all (possibly interactive) protocols.

heading: 1.3 Prior results and our contribution
text: For the setting when m = 1, i.e., each user only observes one sample, the problem has been studied by various works in the literature [11, 1, 3], where it has been established that
R(¸, k, n, 1) = AÚ k
n ‚
Ú k2
n2¸
B . (2)
In this work, we consider a natural setting where each user has access to m > 1 i.i.d. samples. As a baseline, it is immediate to see that, absent any communication constraint (i.e., ¸ = Œ), the error rate would behave as in the centralized case,
R(Œ, k, n, m) = AÚ k
mn
B . (3)
This raises the natural question of how the minimax risk behaves between those two extremes, and of whether the exponential decrease of the risk as a function of the communication constraint ¸ is preserved. We point out that this setting is substantially more challenging to analyze, and requires significantly different techniques and new ideas than the m = 1 case. Indeed, as m grows, even the case ¸ = 1 is not entirely clear: given 1 π m π k samples and only one bit of information to send, should each user send that bit of information about one of their samples only? Or about the (quite imprecise) empirical distribution they can form with their own m samples? Now, what about the case m ∫ k, where each user now can compute by themselves an accurate estimate of the unknown p, but still lack the bandwith to send enough information about it to the server?
1Formally, this is captured by defining channels as Wi : Y ◊ [k]m ◊Yi≠1 ◊U æ [0, 1], where Y := {0, 1}¸. 2We note that some work further distinguish between private-coin noninteractive protocols, where each user randomizes their message independently as described above, and public-coin noninteractive protocols, where a common random seed is available to all users. In this work, we design private-coin noninteractive protocols for our upper bounds; as our lower bounds hold even for sequentially interactive protocols, this only makes our results stronger.
We are able to obtain tight bounds for most parameter regimes, and show that the minimax rates exhibit an interesting phase transition as m and ¸ vary (with respect to the domain size k). We state the results under cases where m < k/2¸ and m Ø k/2¸ in Theorem 1.1 and 1.2 respectively. Theorem 1.1. When m < k/2¸ and n/ log(n) > k2¸ log m, the minimax rate satisfies
R(¸, k, n, m) = AÚ k
mn ‚
Ú k2
mn2¸
B .
Moreover, this bound is achieved by a noninteractive communication protocol.
We observe that, keeping the same communication budget for each user, the minimax risk is reduced by a factor of Ô m compared to the one-sample case (2). In this regime, increasing the communication budget ¸ still reduces the estimation error exponentially, as it did in the one-sample case. Our second set of results shows that this is no longer the case as m increases: Theorem 1.2. When m Ø k/2¸ and n¸/ log(n) > min(m log(k/m + 1), k) log m, the minimax rate satisfies
R(¸, k, n, m) =
Y __]
__[
O
3Ò k mn ‚ Ò k log(k/m+1) n¸ 4 , when m < k,
O
3Ò k mn ‚ Ò k2 mn¸ 4 , when m Ø k.
Moreover, this bound is achieved by a noninteractive communication protocol.
Unlike the previous case m < k/2¸, the risk now decreases at a rate 1/ Ô ¸ instead of 1/ Ô
2¸, an exponential slowdown. As stated, however, Theorem 1.2 only provides an upper bound on the minimax rate, from which it would still be conceivable that the true rate behaves as 1/ Ô 2¸. We rule out this possibility, confirming the phase transition suggested by Theorem 1.2 as m grows: Theorem 1.3. When m Ø k/2¸ and n > (k/¸)2, the minimax rate satisfies
R(¸, k, n, m) =
Y __]
__[
3Ò
k mn ‚
Ò k
n¸ log k
4 , when m < k log k,
3Ò
k mn ‚
Ò k2
mn¸
4 , when m Ø k log k.
Note that the lower bound of Theorem 1.3 matches the upper bound from Theorem 1.2 up to either constant or logarithmic factors. Interestingly, our results imply that, keeping other parameters fixed, increasing m from k/2¸ to k can at best improve the rate by logarithmic factors in k. About the restriction on n. Our bounds for rates are tight up to logarithmic factors in k, for sufficiently large n. The constraint on the range of n in Theorems 1.1 to 1.3 may appear restrictive at first. However, note that since Theorem 1.1 focuses on the regime m < k/2¸, the bound becomes vacuous for n Æ k (as then k 2
mn2¸ Ø 1), and thus we can always assume n Ø k. Thus, the requirement n/ log n Ø k2¸ log m is only restrictive for ¸ π log log m+log log n. The assumption in Theorem 1.2 is more consequential; but it can be shown that n · ¸ must be at least linear in k under some conditions. Indeed, even if each user were given the distribution up to ¸1 error Á < 1, a standard packing argument would require n¸ Ø k log 1Á bits of communication. Finally, the requirement n > (k/¸)2 (instead of the natural n > k/¸ we just argued) in Theorem 1.3 is indeed not innocuous, and is an artifact of our proof method. For m = k log k, note that if we want to estimate the distribution up to TV error Á <  ¸/(k log k), the above lower bound implies n = ! k/(Á2¸ log k) " > (k/¸)2. Hence Theorem 1.3 demonstrates a phase transition in this case. When Á > 
¸/(k log k), the phase transition is less clear given Theorem 1.3 alone. However, observe that by the packing argument discussed above, we need at least n Ø k log 1Á /¸ users even when each user knows the exact distribution, and hence for any fixed m. This shows that the rate O(  k2/(mn2¸)) with exponential dependence on ¸ cannot always hold. We see removing these restrictions as an interesting future direction.
Our algorithm. To motivate our algorithm, we consider the simplest distribution estimation problem: under communication constraints “For nm coin tosses with each user observing m coin tosses and
sending 1 bit to the center, how do we best estimate the bias of the coin?” A key component of our general algorithm is an algorithm for this simplest of settings, which turns out to be surprisingly non-trivial.
One may easily come up with simple solutions. One idea is to let each user send 0 if there are more heads than tails and 1 otherwise. This algorithm works well when the coin is almost fair, e.g., Pr (head) œ (1/2 ≠ 1/Ôm, 1/2 + 1/Ôm), but it is ineffective if the coin is strongly biased. Another idea might be to only let each user indicate whether head appeared or not. This would lead to much better performance for strongly biased coins, e.g., Pr (head) < 1/m, but worse accuracy for fair coins. We elaborate further on this in Section 2.1.1.
In Section 2.1, we propose an algorithm which estimates the bias of the coin with accuracy O(  1/mn) with 1-bit of communication from each user under mild regularity conditions. Note that this is the best rate that can be achieve even when the server has access to all clean samples. Our proposed algorithm not only combines the best of the two naïve algorithms, but further tackles the regime where both solutions fail. It first forms local estimates of the bias of lower accuracy, and then boosts the accuracy by combining local estimates. For the first part, we use a scheme similar to the Gray coding based scheme proposed for Gaussian mean estimation in [8], but we need to modify it significantly as the tail probabilities of the underlying distribution can change with the unknown bias.
Using this algorithm as a primitive, we form a general algorithm in steps. The first step is to convert the bias estimation algorithm to that for estimating a t-ary distribution using 1-bit communication per user. We do so by partitioning the overall domain [k] into t ¥ k/2¸ parts of size at most 2¸: we then estimate the distribution induced on the parts, using the 1-bit algorithm above by setting t to equal the number of parts. (Users assigned to this task use their m samples, but only one bit of communication.) That being done, we estimate the k/2¸ conditional distributions given the sample lies in each of these parts. Since each part has size at most 2¸, the user can communicate one exact value in these parts using ¸ bits, which allows us to perform this task under our ¸-bit communication constraint, keeping only one of the m samples and transmitting its exact value within a given part. (Users assigned to this task use their ¸ bits of communication, but only one of their m samples.) Finally, combining the two types of estimates – of the induced distribution over parts, and of the conditional distribution within each part – allows us to form our overall estimate of the distribution.

heading: 1.4 Related Works
text: We first discuss the literature most relevant to our work. As previously mentioned, in the onesample case (m = 1) discrete distribution estimation under communication constraints has received significant attention over recent years: [11], and [2, 3] obtain the tight minimax rates stated in Eq. (2), for the noninteractive case. [12] and [1] extend the lower bounds to interactive protocols (resp., in the blackboard model and the sequential interactivity model considered here), showing that the minimax error rate does not improve with interactivity. [4] builds upon [1] and extend this lower bound framework to more general distribution families; our own lower bounds will draw upon the techniques in this paper.
Switching from total variation (i.e., ¸1) loss to the less stringent ¸2 loss, [6] develops a lower bound technique based on Fisher information, which allows us to pinpoint the minimax rates (again, in the m = 1 case) under ¸2 loss for various distribution families, including discrete distributions. Finally, [10] states tight minimax bounds for estimation for ¸1 loss under a different communication constraint, where each user can hold an unlimited number of samples but the constraint is on the total communication budget (as opposed to our setting, where each user has its own bandwidth constraint). We once again emphasize that all the techniques from the aforementioned papers are either limited to the m = 1 case or focusing on a different loss than ¸1, and do not extend to the more challenging m > 1 case (or would lead to vacuous bounds due to the loose connection between ¸2 and ¸1 losses). Other works on communication-constrained estimation. Beyond the case of discrete distribution estimation, there is a significant body of work on various parametric estimation tasks under communication constraints (including the case m Ø 1). [14] considers parameter estimation for the ¸2 loss under a total communication budget constraint. In the same setting, [7] focuses on Gaussian mean estimation (note that for Gaussian distributions, having a number of samples m > 1 per user is less of a technical challenge, as the sum of m samples remains Gaussian, with a different variance). [13] obtains results in the same communication model as ours (per-user communication constraint), but for high-dimensional product Bernoulli distributions. Finally, [8] studies parameter estimation for
high-dimensional Gaussian distributions under per-user communication constraints; some of their techniques, such as the use of a Gray code, are similar to ours; however, the product structure and stability by convolution of Gaussian distributions make the Gaussian setting fundamentally incomparable to the univariate discrete case.

heading: 2 Start with one bit: from multinomial to binomial
text: In this section, we consider the setting where each user can only send one bit. In particular, we present a one-bit algorithm which achieves the guarantee stated below; this algorithm will later be a key subroutine for the general case ¸ > 1. Theorem 2.1. When n > 100k log(m) log(n) and ¸ = 1, the minimax rate satisfies
R(1, k, n, m) = O AÚ k2
mn
B .
As described in the setting, each user observes m samples from a multinomial distribution p. Our algorithm then estimates p by learning each px separately. In more detail, the algorithm partitions users into k sets S1, S2, . . . , Sk, each with size nÕ := Ân/kÊ. For x œ [k], information from users in Sx will be used to estimate px. Note that for all j œ Sx, Mj(x), the number of times x appears in Xj , is a sample from Bin(m, px). The crux of the algorithm then relies on solving the following problem of estimating the bias of Binomial distributions with one-bit protocols.
Binomial estimation. Given nÕ i.i.d. samples ZnÕ = (Z1, Z2, . . . , ZnÕ) from Bin(m, p), the goal is to design one-bit messaging schemes Wi : [m] æ {0, 1} and p̂, which minimizes
E 51 p̂(Y nÕ) ≠ p 226 ,
where ’i œ [nÕ], Yi = Wi(Zi). Without communication constraints, it is folklore that the simple averaging estimator can achieve the optimal estimation error of O(p(1 ≠ p)/mnÕ). In this section, we show that there exists a one-bit protocol which achieves this rate with an extra error exponentially small in nÕ, stated below. Lemma 2.2. Given nÕ users each observing an i.i.d. sample from Bin(m, p), where nÕ > c log(m) for some absolute constant c > 0, there exists a one-bit protocol which outputs an estimate p̂ satisfying
E Ë (p̂ ≠ p)2 È = O
3 p(1 ≠ p)
mnÕ + 1 m e
≠ nÕ240 log(m) 4
.
We give a high-level overview of the binomial estimation protocol in Section 2.1. The proof of the lemma is rather technical and we defer it to the supplemental. We next explain how the lemma can be used to establish Theorem 2.1. By applying the algorithm of Lemma 2.2 to each x œ [k] with the n Õ = Ân/kÊ users from group Sx, we have
E Ë Îp̂ ≠ pÎ22 È = ÿ
xœ[k] E
Ë (p̂x ≠ px)2 È = O
Aq xœ[k] px(1 ≠ px)
mnÕ + k m e
≠ nÕ240 log(m) B = O 3 k
mn
4 ,
where the last bound holds when n > 100k log(m) log(n). Applying Cauchy–Schwarz and Jensen’s inequalities, we get as desired,
E[TV(p̂, p)] Æ 12
Ú kE Ë Îp̂ ≠ pÎ22 È = O AÚ k2
mn
B .

heading: 2.1 Binomial estimation with one-bit protocol
text: In this section, we provide an overview of the protocol which achieves the guarantee stated in Lemma 2.2. We start by introducing a threshold-based algorithm to provide some motivation.

heading: 2.1.1 Motivation
text: We motivate our algorithm by discussing the two naïve algorithms in Section 1.3: why they work in certain regimes and fail in others. We consider the following family of algorithms,
Fix threshold t œ [0, m]: upon observing Zi, user i sends Yi = 1{Zi Ø t}.
Note that choosing t = Ám/2Ë and t = 1, respectively, gives the two naïve algorithms. Using the above algorithm, one can calculate the empirical estimate of Pm,t(p) := PrZ≥Bin(m,p)[ Z Ø t ],
P̂ = 1 nÕ
nÕÿ
i=1 Yi,
We then obtain an estimate using p̂ = P ≠1m,t(P̂ ). It can be shown that that E Ë |P̂ ≠ Pm,t(p)| È Æ  Pm,t(p)(1 ≠ Pm,t(p))/nÕ by standard argument of estimating Bernoulli random variables. If P̂ is sufficiently close to Pm,t(p), we can roughly bound the error for estimating p as
E[|p̂ ≠ p|] ¥ 1|P Õm,t(p)| E Ë |P̂ ≠ Pm,t(p)| È .
Hence for better accuracy, we want the derivative |P Õm,t(p)| to be large. However, this can only be guaranteed if p and t/m are not too far apart. In fact, to obtain the desired error of O(p(1 ≠ p)/mnÕ), we need roughly |p ≠ t/m| = O(  p(1 ≠ p)/m), the standard deviation of Bin(m, p).
Hence any fixed threshold-based scheme, including the two naïve algorithms, cannot achieve the optimal rate for all p. However, this provides an important intuition for our algorithm: if we can first estimate p up to constant standard deviation, then we can obtain a good estimate with one bit by sending a proper threshold. This motivates the two-stage algorithm in the next section.

heading: 2.1.2 Algorithm
text: As outlined in the foregoing informal discussion, the algorithm has two stages, a localization stage and a refinement stage. Similar structures have also been used in estimating the mean of Gaussian distributions under communication constraints [7, 8]. Note that although the protocol is presented in a two-stage manner, the two stages can be implemented by two disjoint subset of users, who can send the messages simultaneously. Hence the protocol is noninteractive. We first introduce Gray codes. Definition 2.3 (Gray code). An s-bit Gray code Gs : [0, 1] æ {≠1, +1}s is defined by a collection of Gray functions gi : [0, 1] æ {0, 1}, i œ [s], where
gi(x) = ; 0 % 2ix & mod 4 = 0, 3,
1 % 2ix & mod 4 = 1, 2.
And the encoding is given by Gs(x) = (g1(x), g2(x), . . . , gs(x)).
Gray code is a widely used code in wireless systems to guarantee robustness to bit errors. The code has the following nice property. Claim 2.4. Gs partitions [0, 1] into 2s intervals such that, for any two consecutive intervals, the encodings only differ at one bit.
The property guarantees that if a user can obtain p̂ such that |p ≠ p̂| < 2≠s, then Gs(p̂) and Gs(p) only differ in one bit. This is crucial in establishing the performance of the algorithm.
Next we introduce the protocol. We divide users into 4 groups S1, . . . , S4, each with N := n Õ
4 users. Let s = log(m) and M = Ns . Localization. This stage uses samples from S1 to locate p up to accuracy ( 
p(1 ≠ p)/m) with high probability. Since each user has a sample Z ≥ Bin(m, p), by standard concentration inequalities, |Z/m≠p| Æ  2p(1 ≠ p)/m with high probability. S1 is further partitioned into s subgroups (Sj1)jÆs of equal size. All users u œ Sj1 send the jth bit of the Gray code for Zu, i.e., Yu = gj(Zu/m).
The server then obtains majority votes for the jth bit bj := 1 Óq
uœSj1 Yu Ø M/2
Ô . By decoding
(b1, . . . , bs), we obtain a coarse estimate of p. By standard concentration analysis and the property of Gray code, it can be shown that with high probability, the estimate has the desired accuracy. Refinement. In this stage, we improve the accuracy of estimating p to ( 
p(1 ≠ p)/mnÕ) using samples from S2, S3, S4. If interactivity is allowed, users in this stage only need to send the threshold function at the crude estimate. To remove interactivity, users in each of the groups will send indicators of whether their sample lies in a certain subset, defined below. Albeit much more involved, these indicator functions are used in a very similar fashion as the threshold functions.
1. We define a partition of [0, 1]. Let CI be a constant and r := Â Ò
m 2CI Ê. Define the intervals
Ii := [li≠1, li] for 1 Æ i Æ r, where
li := min ; CI i 2
m , 1 2
< , 0 Æ i Æ r.
Furthermore let I2r+1≠i := [1 ≠ li, 1 ≠ li≠1]. User u œ S2 sends Yu = 1{Zu/m œ fiiI2i} 2. Let ji be the midpoint of Ii for 1 Æ i Æ 2r and j0 = 0, j2r+1 = 1. Define Ji := [ji≠1, ji].
User u œ S3 sends Yu = 1{Zu/m œ fiiJ2i}. 3. User u œ S4 sends Yu = 1{Zu Ø 1}.
To estimate p, we show that if p is successfully estimated up to accuracy ( 
p(1 ≠ p)/m) in the localization stage, then for any p within an interval around the estimate, at least one of the expectations of the above indicators has a large derivative with respect to p. Hence we show that the server can refine the estimate for p by inverting the corresponding empirical frequency within the interval. Details are provided in the supplementary.
The design of the indicator functions is a keycontribution that sets our algorithm apart from that of [7, 8]. Unlike in the Gaussian case, the variance of a binomial changes with its mean. Note that if p œ Ii, |Ii| = (max{  p(1 ≠ p)/m, 1/m}). Hence this partition reflects the behavior of the binomial variance as p varies.

heading: 3 Distribution estimation with ¸ bits: a phase transition
text: In this section, we consider the general setting where each user can send ¸ bits. We first note that since each user observes m samples from [k], each multiset of m samples can take at most NS = !m+k≠1 m " possible values. As it is enough for a protocol to only transmit information about the multiset, or equivalently, the empirical frequencies of the samples, log NS = (m log(k/m) + k log(m/k)) bits are enough for a user to transmit all their information. Hence here we focus on the case when ¸ = O(m log(k/m) + k log(m/k)). As mentioned in Section 1.3, we obtain different bounds for different regimes of parameters. When m < k/2¸, we show in Section 3.1 that the risk scales at rate 1/ Ô 2¸ (Theorem 1.1). When m Ø k/2¸,
however, our bounds scale as 1/ Ô
¸ (Theorem 1.2). In this regime, we consider two different cases: (i) m < k, ¸ > log(k/m); (ii) m Ø k, presented in Sections 3.2 and 3.3 separately.

heading: 3.1 Regime m Æ k/2¸: an exponential rate in ¸
text: In this subsection, we present an algorithm which achieves the upper bound part of Theorem 1.1. Without loss of generality, we assume each user can send ¸ + 1 bits as this will only change the resulting bound by a factor of Ô 2. Since 2¸ Æ k/m Æ k, we cannot represent a symbol in [k] losslessly using ¸ bits. Instead, we partition the domain into t = ' k/(2¸ ≠ 1) ( blocks B1, . . . , Bt, each of size at most 2¸ ≠ 1. Our protocol builds on the observation that, given a fixed block Bi, with ¸ bits each user can either represent a symbol in Bi that has appeared in their samples or indicate that none of symbols has appeared.
Before stating the protocol, we first define some related quantities. For p œ k, let pB be the distribution over the blocks induced by p, where for all j œ [t] pB(j) = q xœBj px. For block j œ [t], let p̄j(x) be the normalized distribution over elements in set Bj , i.e., for all x œ Bj , p̄j(x) = p(x)/pB(j) (if pB(j) = 0, we set p̄j(x) = 1/(2¸ ≠ 1),which is the uniform distribution
over Bj). The protocol learns p by estimating both the distribution over blocks and the normalized distributions within each block.
Estimating pB . Each user maps the observed samples to the set they belong to in B1, . . . , Bt. Then the users use the first bit to run the 1-bit protocol in Theorem 2.1 to learn pB . The server collects the messages and obtain an estimate ‚pB . Estimating normalized distributions. Users are partitioned into t sets S1, S2, . . . , St, each of size Ân/tÊ.3 For i œ Sj , user i uses the remaining ¸ bits to send the first sample it observes in Bj . If none of them is observed, the user sends ‹. Upon receiving the messages, the server uses the empirical estimator to estimate p̄j ,
‚pj(x) = q
iœSj 1{Yi = x}q iœSj 1{Yi ”= ‹} , x œ [2¸],
if q
iœSj 1{Yi ”= ‹} ”= 0. Otherwise, we set ‚pj(x) = 1/(2 ¸ ≠ 1) for all x œ Sj .
The final estimates are simply ‚p(x) = ‚pB(j) · ‚pj(x), ’j œ [t], x œ Bj .
Next we prove that the estimator achieves the upper bound guarantee in Theorem 1.1. We first relate the estimation errors for ‚p to those of ‚pB and ‚pj . Lemma 3.1. We have E[TV(‚p, p)] Æ E[TV(‚pB , pB)] + q jœ[t] pB(j)E[TV(‚pj , p̄j)].
Proof. We write
E[TV(‚p, p)] = 12E # ÿ
jœ[t]
ÿ
xœBj
|‚p(x) ≠ p(x)| $ = 12E # ÿ
jœ[t]
ÿ
xœBj
|‚pB(j)‚pj(x) ≠ pB(j)pj(x)| $
Æ 12E # ÿ
jœ[t]
ÿ
xœBj
(|‚pB(j)‚pj(x) ≠ pB(j)‚pj(x)| + |pB(j)‚pj(x) ≠ pB(j)pj(x)|) $
= 12E # ÿ
jœ[t]
ÿ
xœBj
‚pj(x)|‚pB(j) ≠ pB(j)| $ + 12E # ÿ
jœ[t] pB(j)
ÿ
xœBj
|‚pj(x) ≠ pj(x)| $
= E[TV(‚pB , pB)] + ÿ
jœ[t] pB(j)E[TV(‚pj , p̄j)].
Next we bound terms in Lemma 3.1 separately. Since pB is over a smaller domain of size' k/(2¸ ≠ 1) ( , by Theorem 2.1, we have when n > 100 k2¸ log m log n,
E[TV(‚pB , pB)] = O 3Ò k2
mn(2¸)2
4 . (4)
We then bound the error on estimating p̄j’s. Note that since each user in Sj either sends the first sample it observes in Bj or ‹ if none of the elements appears, we have the following facts:
1. For j œ [t], let Nj := q
iœSj 1{Yi ”= ‹}, the number of samples the server receives from Bj . Then Nj follows a binomial distribution Bin(Ân/tÊ , —j) where —j := 1 ≠ (1 ≠ pB(j))m = (min{mpB(j), 1}). 2. For j œ [t], conditioned on that the first sample in Bj is sent, the sample is distributed according to the normalized distribution p̄j .
Based on these observations, we obtain the following lemma. Lemma 3.2. If pB(j) > 0, then E[TV(‚pj , p̄j)] = O 1Ò
k n—j
2 .
Proof. When —j Æ 8kn , the bound is trivial since TV distance is always bounded by 1. When —j > 8k n , by a Chernoff bound, we have Pr 1 Nj < n—j 2t 2 Æ exp 1 ≠ n—j8t 2 . When Nj Ø n—j2t ,
E # TV(‚pj , p̄j) | Nj Ø n—j2t $ = O 3Ò 2¸≠1 Nj 4 = O 1Ò k n—j 2 .
3If t does not divide n, the protocol ignores the last n ≠ t Ân/tÊ users.
Combining both, we get
E[TV(‚pj , p̄j)] = O 1Ò
k n—j
+ exp 1 ≠ n—j2 ¸
8k
22 = O 1Ò k
n—j
2 ,
completing the proof of the lemma.
Next we bound the second term in Lemma 3.1 using Lemma 3.2, since —j = (min{mpB(j), 1}),
ÿ jœ[t] pB(j)E[TV(‚pj , p̄j)] = O
Q a ÿ
jœ[t] max
I pB(j) Ú k
n ,
Ú pB(j)k
nm
JR
b
= O A max IÚ k
n ,
Ú kt
nm
JB . (5)
= O AÚ k2
nm2¸
B , (6)
where (6) follows from t = ' k/(2¸ ≠ 1) ( > m. Together with (4), this completes the proof.
3.2 Regime m < k, ¸ > log(k/m): increasing m barely helps
When m Ø k/2¸, the first term in (5) dominates (up to constant factors) and the bound will not further decrease as t decreases (or ¸ increases when using the parameter in Section 3.1). Hence we fix t = 2m, where the two terms in (5) match. Similar to the protocol in Section 3.1, we divide the domain into t = 2m non-overlapping blocks B1, . . . , Bt, each with size Ák/(2m)Ë. Then we can define pB and p̄j , j œ [t] similarly as in Section 3.1 and estimate them separately. Estimating pB . Users follow the procedures as in Section 3.1 and the server obtains ‚pB using the 1-bit protocol from Theorem 2.1.
Estimating normalized distributions. Since each block is only of size Ák/(2m)Ë, given a block index, each user can send an element within the block with log Ák/(2m)Ë < ¸ bits. To take advantage of this, we assign each user tÕ = Â¸/ log Ák/(2m)ËÊ different blocks. More precisely, user i is assigned blocks Bj for j = (i ≠ 1)tÕ + 1, (i ≠ 1)tÕ + 2, . . . , itÕ mod t. For each Bj , the user sends the first sample they observe in Bj or sends ‹ if none of them appears. In total, n users send out ntÕ messages, which we index as (Zi)iœ[ntÕ]. Based on which of the t blocks the messages correspond to, we can divide them into t sets where Sj = {i œ [nÕt] | j = i mod t}. The server collects the messages from the users and uses the empirical estimator to estimate each normalized distribution within each block, where for j œ [2t], x œ [Ák/(2m)Ë],
‚pj(x) = q
iœSj 1{Zi = x}q iœSj 1{Zi ”= x} .
We show the above protocol achieves the upper bound in Theorem 1.2. The proof is in similar spirit as the proof in Section 3.1 with only two differences. First we fix t = 2m, hence the first term in (5) dominates. However, since for each block Bj , the server receives |Sj | Ø ntÕ/(2t) = ( n¸m log(k/m+1) ) users, the estimation error for the normalized distribution within the block can be improved by a factor of tÕ. We defer the details of the proof to the supplemental.

heading: 3.3 Regime m Ø k: learning each px separately
text: In this case, the protocol in Section 3.2 will not apply since the domain is of size k < 2m. We instead consider a protocol which estimates each px using samples from Bin(m, px) as we did in Section 2. Since now each user has ¸ bits, the users can send information about ¸ elements, which improves the rate by a 1/ Ô ¸ factor. We next describe the protocol formally.
We assume without loss of generality ¸ Æ k; otherwise, each user only uses k bits of its allowed ¸.4 To each x œ [k], we assign a set of users Sx as follows. User i is in set Sx if and only if
4This is enough since plugging in ¸ = k in Theorem 1.2 already achieves the optimal centralized rate.
÷iÕ œ [¸ ≠ 1], (i ≠ 1)¸ + iÕ = x mod k. It can be verified that each user is assigned to exactly ¸ sets and that |Sx| Ø n¸2k for all x. Once the sets are assigned, users in Sx run the one-bit protocol in Lemma 2.2 to estimate px. By Lemma 2.2, we have when n¸ > 100k log m log n, E Ë Îp̂ ≠ pÎ22 È = ÿ
xœ[k] E
Ë (p̂x ≠ px)2 È = O Aq xœ[k] px(1 ≠ px) m minx |Sx| + k m e ≠ minx |Sx|30 log(m) B = O 3 k 2 mn¸ 4 .
Hence, applying Cauchy–Schwarz and Jensen’s inequalities we get, as desired,
E[TV(p̂, p)] Æ 12
Ú kE Ë Îp̂ ≠ pÎ22 È = O AÚ k2
mn¸
B .

heading: 4 Lower bounds
text: In this section, we provide a sketch of the proof for the lower bound parts of Theorem 1.1 and Theorem 1.3. We first use the Poisson sampling trick to show that the problem is at least as hard as estimating the mean of a suitable product of Poisson distributions. Then we leverage the recently developed lower bound technique from [4] to prove minimax estimation lower bounds for that product of Poisson distributions. We provide the complete proof in the supplementary.
Product of Poisson distributions. Let ◊ œ Rk be a vector. A product of Poisson distributions p◊ is a product distribution over Nk whose ith marginal is a Poi(◊(i)) distribution: p◊ = ¢ki=1 Poi(◊(i)). We next introduce a family of product of Poisson distributions, which will be used as hard instances. For all z œ {≠1, +1}k, define ◊z as
◊z(i) = m(1 + 2Ázi)
k , i œ [k].
For z œ {≠1, +1}k, let pz = p◊z and P = {pz : z œ {≠1, +1}k}. Consider now the following generative process: (1) Pick Z uniformly from {≠1, +1}k. (2) Users observe samples Xn from p¢nZ . (3) Users follow a protocol and send messages Y n. The following lemma states that if there exists a discrete distribution learning protocol, there must exist a protocol which is able to extract enough information about Z from Y n. Lemma 4.1 (Assouad-type bound). If there exists a discrete distribution learning protocol with m samples per user which has expected TV error at most Á/10, there must exist a protocol whose messages Y n under the above defined process satisfy q iœ[k] I(Zi; Y n) = (k).
The proof combines standard lower bound techniques of Poisson sampling and Assouad’s Lemma, which we present in the supplementary. The challenging part of the argument then lies in bounding the sum of mutual informations in Lemma 4.1 for communication-constrained protocols, which we do in the next lemma: Lemma 4.2. Let Z ≠Xn ≠Y n be the Markov chain defined above. For any ¸-bit interactive protocol:
1. When m2¸ < k, we have q
iœ[k] I(Zi; Y n) Æ mn2 ¸Á2 k .
2. When m > k log k and n < (k/¸)2, we have q
iœ[k] I(Zi; Y n) Æ mn¸Á 2 k .
We provide the detailed proof of these two points in the supplementary, and only provide a sketch here. The bounds are proved using the ‰2-contraction bounds recently developed in [4]. The bounds relates the amount of information to a function „z,i Ã ( dpzüidpz ≠ 1), where z
üi denotes the vector obtained by flipping the ith coordinate of z. Obtaining the bound q iœ[k] I(Zi; Y n) = O(2¸), while quite
involved, then can be done using ideas from [4]. Getting the tight bound of q
iœ[k] I(Zi; Y n) = O(¸) when m > k log k, however, requires some additional ideas. Indeed, to get such a dependence on ¸, one would typically argue about and use the subgaussian tail of „z,i; unfortunately, the quantity „z,i provably does not exhibit such tails for the family of Poisson distributions. To circumvent this issue, we decompose „z,i into a subgaussian part and a remainder part, and bound each term separately (noting that the subgaussian part only dominates in the regime m ∫ k). Finally, we show how the lemmas can be used to derive the lower bound of Theorem 1.1. Assume there exists an ¸-bit protocol which estimates any discrete distribution up to expected TV error Á. By Lemma 4.2 (Item 1) and Lemma 4.1, we have mn2 ¸Á2 k Ø q iœ[k] I(Zi; Y n) = (k). Reorganizing, this implies Á = ( Ò k2
mn2¸ ), as stated in Theorem 1.1. Theorem 1.3 can be obtained similarly using Lemma 4.2 (Item 2) and Lemma 4.1.
Acknowledgments and Disclosure of Funding
Jayadev Acharya is supported by NSF-CCF- 1846300 (CAREER), NSF-CCF-1815893, and a Google Faculty Fellowship. Yuhan Liu is supported by AFRI Competitive Grant no. 2020-67021- 32855/project accession no. 1024262 from the USDA National Institute of Food and Agriculture, and NSF-CCF- 1846300 (CAREER). Ziteng Sun is supported by NSF-CCF- 1846300 (CAREER). Himanshu Tyagi is supported in part by a research grant from the Robert Bosch Center for Cyberphysical Systems (RBCCPS), Indian Institute of Science, Bangalore.

Review summaries:
The paper studies the problem of distributed learning of a discrete distribution.  Formally, there are $n$ participants each of whom receives $m$ samples from a discrete distribution $\mathcal{D}$  on $[k]$.  The participants, after seeing their own samples, each send at most $l$ bits of information to a centralized server.  The goal is for the centralized server to output a distribution $\mathcal{D'}$ that is close to $\mathcal{D}$ in TV distance.  The main results of the paper are matching upper and lower bounds in various regimes of $n,m,k, l$, generalizing previous works that had only studied the case of $m = 1$.  Furthermore, the upper bounds are obtained using non-interactive algorithms with no shared randomness while the lower bound holds even against sequential algorithms that use shared randomness.  The main takeaway is a supposed phase transition when $m \sim k/2^l$ where the "value" of additional bits goes from exponential when $m < k/ 2^l$ to polynomial when $m > k/2^l$.  

This paper is about distributed density estimation of an unknown probability distribution $p$, where the samples from that distribution are held by different users. In the model considered, there is a central server that collects messages from the users who hold the samples from $p$. Apart from the number of users $n$ and the domain size $k$, the problem is parametrized by the number of samples $m$ that each user holds and the maximum message size of $\ell$ bits. The goal is to minimize the total communication complexity (i.e the number of bits sent to the server). Interestingly, the authors show a phase transition of the error of the estimation with regard to $m$ happening at $m=k/2^\ell$. Specifically, it is shown that the error scales with $\frac{1}{\sqrt{\ 2^\ell}}$ for $m<k/2^\ell$ and with $\frac{1}{\sqrt{\ell}}$ otherwise. The existence of this phase transition is supported by both upper and lower bounds, although they are not shown for the entire parameter regime. However, both bounds are shown for sufficiently large $n$ and they are also tight up to logarithmic factors. The algorithm uses the estimation of a cointoss ($k=2$) bernoulli distribution as a primitive and recursively estimates the mass of certain parts of the domain in this way.   

This work considers distributed density estimation. The problem setting is as follows: n users each have a dataset of m independent observations from an unknown discrete probability distribution and a central server aims to estimate the unknown distribution. When each user is subject to a bandwidth constraint such that each user can only send \ell bits to the center, the authors seek to understand tradeoffs between communication, sample size, and estimation error in the problem. In particular, for an unknown $k$-ary distribution p, this works characterizes minimax rates of estimating p in L1 distance. 

The paper introduces new algorithms for low bandwidth distributed estimation problems which could be useful in different applications including distribution estimation via multiple sensor readings. The assumption that each node or user can have multiple samples makes this paper interesting and makes it different from the previous works. Another important assumption that makes the paper interesting is the low bandwidth restriction. The authors prove phase transition properties as the bandwidth increases.