Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition
Authors: Jayadev Acharya
Clement Louis Canonne
Yuhan Liu
Ziteng Sun
Himanshu Tyagi
Venue: NeurIPS 2021 Poster (2021)
Keywords: density estimation
distributed algorithms
communication constraints
probability distributions
statistical rates

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 $\ell$  bits. Our main result is a tight characterization (up to logarithmic factors) of the error rate as a function of $m$, $\ell$, 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 $\ell_1$ error rate gets reduced by a factor of $\sqrt{m}$ for small $m$. However, for large $m$ we observe an interesting phase transition: the dependence of the error rate on the communication constraint $\ell$ changes from $1/\sqrt{2^{\ell}}$ to $1/\sqrt{\ell}$.

Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition
Jayadev Acharya Cornell University acharya@cornell.co edu
Clément L. Canonne University of Sydney
Yuhan Liu
Cornell University
clement. canonne@sydney edu.au au
y129760cornel1. edu
Ziteng Sun Cornell University z83350corne1l edu
Himanshu Tyagi
Indian Institute of Science ht ttyagi@iisc... ac
Abstract
We obtain tight minimax rates for the problem of distributed estimation of discrete distributions under communication constraints, where n users observing samples each can broadcast only bits. Our main result is a tight characterization (up logarithmic factors) of the error rate as function of m, f, 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 & error rate gets reduced by a factor /m for small m. However, for large m we observe interesting phase transition: the dependence of the error rate the communication constraint changes from 1/v2 1/VE.
Introduction
Background and motivation
We consider the problem of density estimation in distributed setting where each of 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 crucial building blocks in areas such as federated learning, IoT, 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 construint 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 2 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 & distance. Before detailing our results and discussing their relation with prior work, we provide the necessary background and notation.
1.2 Problem setting and notation
Let be positive integer. Let A& (p (PI...., R set of all probability distributions over discrete domain of size k, which we assume without loss of generality [k] := k). For p, q Ag. the total variation (TV) distance between
2, 2
1} denote the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and is qp. = sc (P(S) (()).. Here for set S S [k] p(S) == Exes Pz. Each of n users observes mn i.i.d. samples from the same (unknown) distribution p E As. We write X; (x:-) x::
) for the samples the ith user, and X = (X1, X2, ....... Xn) E mm for the collection of all nm samples. We denote the empirical frequencies of samples at user by M,.
where, for E [k), Mx)x) == m Ej=1 1(x; x).
Each user can only send ě-bit message, capturing their bandwidth constraints, In particular, user i allowed to send a message Y; E {0, 1 to the central server through channel W; E We, that is, Markov kernel Wi: : {0, 1)dh [k] m + [0, 1], where
Wiy z) = Pr (Y; = xx),
VX E [k] . E {0, 1
Intuitively W; can be viewed as a randomized function that maps an input X; to some (-bit string Y, 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 available. In (sequentially) interactive protocols, the choice of W; may depend on the previous messages Y : (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
sent independently of each other with no shared random seed
Distribution estimation. Upon observing the messages Y == (Vi, Y2...., .,....,,,,,. the server estimates the underlying distribution p with an estimator p: (40, 1) + As. with goal 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 f-bit communication constraints, defined as
R(C, n, m) := min min max E(TV p)]
WnEWN P pεát
where the minimum is taken over all (possibly interactive) protocols.
1.3 Prior results and our contribution
For the setting when m = ie.. each user only observes one sample, the problem has been studied by various works in the literature [11, 1, 1J3 where it has been established that
R(e, k, n, 1) = (V=
k2
n2
In this work, we consider a natural setting where each user has access to m > 1 i.idd samples. As a baseline, it is immediate to see that, absent any communication constraint (i.e., f = oo), the error rate would behave as in the centralized case,
R(oo, n, m) = VIE7
(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 substantially more challenging analyze, and requires significantly different techniques and new ideas than the m = 1 case. Indeed, as m grows, even the < 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?
case 1 is not entirely clear: given
Formally, this is captured by defining channels as W.: y x [A] x x x/4 - [0, 1]. where y' = (0. 1) We 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 common random seed 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/22 and m 2 k/2f in Theorem 1.1 and 1.2 respectively.
Theorem 1.1. When < k/2² and n/ log(n) z log m, the minimax rate satisfies
R(C, n,) = -0
=6(1
(V
k me
k2
mnn2
Moreover, this bound is achieved by noninteractive communication protocol.
We observe that, keeping the same communication budget for each user, the minimax risk 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 did the one-sample case. Our second set of results shows that this is no longer the case as increases:
Theorem 1.2. When m 2 k/22 and n log(n) > min(m log(k/m + 1), k)) log m, the minimax rate satisfies
E
log(k (log(//m+1)
when m. < ki
R(C,k,n,m)
JE
V
A2 WETT
when m 2 k.
Moreover, this bound achieved by a noninteractive communication protocol.
Unlike the previous case m < k/22, the risk now decreases at a rate 1/ //V instead of 1/v2', 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/v22. We rule out this possibility, confirming the phase transition suggested by Theorem 1.2 m grows:
Theorem 1.3. When m. 2 k/2f and n > (k/E)², the minimax rate satisfies
Ω
V
when m < klog k.
nf log Ro
R(C, n.
Ω
A2 manE
when m 2 llogg 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 & can at best improve the rate by logarithmic factors in k.
About the restriction 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
the regime < ke/2 the bound becomes vacuous for n & & (as then mn2 2 1), and thus we can always assume n 2 k. Thus, the requirement n/ logn n 2 *x log m only restrictive for l & log log m + log log n. The assumption Theorem 1.2 more consequential; but it can be shown that n & must be at least linear in & under some conditions. Indeed, even if each user were given the distribution up to l error E < 1, a standard packing argument would require ne > & log bits of communication. Finally, the requirement (instead of the natural n > k:/E we just argued) in Theorem 1.3 is indeed not innocuous, and is an artifact of our proof method. For m & log k note that if we want estimate the distribution up to TV error < (e/(k: log k). the above lower bound implies
(k/e)²
k)) (k/
Hence Theorem 1.3 demonstrates a phase transition this case. When E > ve/(A (I 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 2 A log ! users even when each user knows the exact distribution, and hence for any fixed m. This shows that the rate Olv k22 ha//////maan (mm2f)) 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 coin tosses and
3

---

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 be surprisingly non-trivial.
One may easily come up with simple solutions. One idea is let each user send 0 if there more heads than tails and I otherwise. This algorithm works well when the coin is almost fair, e.g., Pr (head) E (1/2-1/4
1/2 4 1//mm, 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/mm) 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 naive 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 scheme similar 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 t-ary distribution using 1-bit communication per user. We do so by partitioning the overall domain [k] into = k/22 parts of size at most 2 then estimate the distribution induced 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/22 conditional distributions given the sample lies in each of these parts. Since each part has size at most 2', the user can communicate value in these parts using l bits, which allows us to perform this task under our b-bit communication constraint, keeping only one of the m samples and transmitting its exact value within 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.
exact
1.4
Related Works
We first discuss the literature most relevant to our work. As previously mentioned, in the one- sample 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 bg loss, [6] develops a lower bound technique based on Fisher information, which allows us to pinpoint the minimax rates (again, in the m = case) under b loss for various distribution families, including discrete distributions. Finally, [10] states tight minimax bounds for estimation for & loss under 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 = case or focusing on a different loss than f,, and do not extend to the more challenging m > 1 case (or would lead to vacuous bounds due to the loose connection between la and l losses).
estimation. Beyond the case of discrete distribution estimation, there is significant body of work on various parametric estimation tasks under commu- nication constraints (including the case m 2 1). [14] considers parameter estimation for the & loss under 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 technical challenge, as the sum of m samples remains Gaussian, with different variance). [13] obtains results in the same communication model as ours (per-user communication constraint), but for nigh-dimensiooal product Bernoulli distributions. Finally, [8] studies parameter estimation for
Other works on communication-cons/ee

---

high-diienniionl Gaussian distributions under per-user communication constraints; some of their techniques, such as the use of a Gray code, are similar ours: however, the product structure and stability by convolution of Gaussian distributions make the Gaussian setting fundamentally incomparable to the univariate discrete case.
2 Start with one bit: from multinomial to binomial
In this section, we consider the setting where each user can only send one bit. In particular, we present one-bit algorithm which achieves the guarantee stated below; this algorithm will later be key subroutine for the general case l 1.
Theorem 2.1. When n > 100k log(m) log(n) and 1, the minimax rate satisfies
R(1, n1 m) = o
k
mn
As described in the setting, each user observes samples from multinomial distribution p. Our algorithm then estimates p by learning each Р,, separately. In more detail, the algorithm partitions users into k sets S2,....... ... Sk. each with size n' := [n/k]. For E [k:]. information from users in S₂ will used to estimate Pa. Note that all j E Sz, (x),,, the number of times a appears in X5, is a sample from (in Pa). The crux of the algorithm then relies solving the following problem of estimating the bias of Binomial distributions with one-bit protocols.
Binomial estimation. Given n' i.i.d. samples 7' (71, Zz,..., Ze') from Bin(m, p), the goal to design one-bit messaging schemes Wi: [m] + {0, 1} and Ó. which minimizes
(D -p)
I
where vi e [n'],Y; = (Z.).
Without communication constraints, it is folklore that the simple averaging estimator can achieve the optimal estimation error of Opp(1 p)/ mn'). In this section, show that there exists one-bit protocol which achieves this rate with an extra error exponentially small n', stated below.
Lemma 2.2. Given n' users each observing an i.i.d. sample from Bin(m,p) p), where > clog(m) for some absolute constant 0, there exists one-bit protocol which outputs estimate satisfying
E ( p)'] = -0(1i)
((((1 p)
C
mnn!
m
We give high-level overview of the binomial estimation protocol 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 E [kc] with the n' [n/k] users from group Sz, have
(
E EuE(N) Pa - P&)
[p pll
ΣE((p p.o p
-0
e
240 low(m)
=
mn!
m
mn
ZE|R]
where the last bound holds when n > 100k log(m) log(n). Applying Cauchy-Schwand and Jensen's inequalities, we desired,
k2 -0(v mn
(p.
S 2\
21l
=0
2.1 Binomial estimation with one-bit protocol
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.
5

---

2.1.1 Motivation
We motivate our algorithm by discussing the two naive algorithms in Section 1.3: why they work in certain regimes and fail others. We consider the following family of algorithms,
Fix threshold t [0, ml: upon observing Zz user sends Y; 1 1 2).
Note that choosing t = [m/ [ and t = 1, respectively, gives the two naïve algorithms. Using the above algorithm, one can calculate the empirical estimate of P (m,r(p) Prz=Bin(m.p)) 2 t].
11'
We then obtain an estimate using f = Pitt(PP (P).
It can be shown that that E - Pm,l()) s
v (m. by standard argument of estimating Bernoulli random variables. If P is sufficienlly close to P,,,(D), we can roughly bound the error for estimating p as
B
pl R3
B P Pw,:(w)l.. (P))
B
P
Hence for better accuracy, want the derivative (P)) to be large. However, this can only be guaranteed if and t/m are not too far apart. In fact, to obtain the desired error of O(p(1 pp)/mm)), we need roughly Ip- - l/ml = O(v[( p)/m). the standard deviation of Bin(m..).
Hence any fixed threshold-based scheme, including the two naive 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 good estimate with one bit by sending a proper threshold. This motivates the two-stage algorithm in the next section.
2.1.2 Algorithm
As outlined the foregoing informal discussion, the algorithm has two stages, a localization stage and 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 two-stage manner, the two stages can be implemented by two disjoint subset of users, who send the messages simultaneously. Hence the protocol noninteractive. We first introduce Gray codes.
Definition 2.3 (Gray code). An s-bit Gray code G.: [o, 1] - {11 is defined by a collection of Gray functions g:: [0, 1] + {0, 1}, E [s], where
0
2'x mod 4 0,3,
gi (x(x) =
1
2'x mod 4 = 1,2.
And the encoding is given by Gz) (g) (x), (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. G. partitions [0, 1] into 2 intervals such that, for any two consecutive intervals, the encodings only differ one bit.
The property guarantees that if user obtain such that Ip P) < 2 then Gp( and Gp(p) only differ in one bit. This is crucial in establishing the performance the algorithm.
Next we introduce the protocol. We divide users into groups Si...., each with N = I users. Let = log(m) and M N.
This stage uses samples from S to locate p up to accuracy O @(vp(1 p(1 m)/m) with high probability. Since each user has sample Z Bin(m, p). by standard concentration inequalities, IZ/m-pl S /2p(11 p)/m m with high probability. S1 is further partitioned into s subgroups (5 Siss of equal size. All users e Si send the jth bit of the Gray code for Z., i.e., Y. (z (Z./m). mm).
Localization.

---

The server then obtains majority votes for the jth bit byt := = Yu M/2}. By decoding (b1.--.; bs), obtain 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. this stage, we improve the accuracy of estimating to (vvp(1 - p)/mmr)) 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 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 C2 be a constant and :
m
Define the intervals
T = [4-1, for $ i r, where
Ct 1 m
1 = min
Osisr.
Furthermore let 12++1-1 := [] 4, 4-1]. User u E S2 sends Y, = 1/Zu/m E U,122
2. Let ja be the midpoint of I, for 1 S 2r and jo 0, 02 1. Define Jj == J.] User u E S3 sends Yu = 1 E U,J2i
3. User S4 sends Y. 1 1}.
To estimate p. we show that if p is successfully estimated up to accuracy O ((vp(1-p)) 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 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 keycontribution that sets algorithm apart from that of [7, 8]. Unlike in the Gaussian case, the variance of binomial changes with its mean. Note that if E 4, [ (maxx / /p111 - p)/m, 1/m]). Hence this partition reflects the behavior of the binomial variance p varies.
Distribution estimation with l bits: a phase transition
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- ( (
possible values. As it is enough for a protocol only transmit information about the multiset, or equivalently, the empirical frequencies of the samples, log Ns = (m log /mm) + k log(m/k) bits are enough for a user to transmit all their information. Hence here we focus on the case when = Om log(k/m) + k log(m/k)).
As mentioned in Section 1.3, 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/v22 (Theorem 1.1). When m 2 k/2 however, our bounds scale as 1/ 1/vl (Theorem 1.2). In this regime, we consider two different cases: (i) m < k, > log(k/m) /m); (ii) m 2 k. presented in Sections 3.2 and 3.3 separately.
3.1 Regime m < k/2": an exponential rate in &
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 e bits. Instead, we partition the domain into t = [k/(2* - 1)] blocks B1....,A B,, each of size at most 2 1. Our protocol builds on the observation that, given a fixed block B, with l bits each user can either represent a symbol B, that has appeared in their samples or indicate that none of symbols has appeared.
Before stating the protocol, first define some related quantities. For p E As. let pø be the distribution over the blocks induced by p. where for all E [t] Po(j) = ExEB, P For block
j E [t]. let (ar)) be the normalized distribution over elements in set Bj, i.e., for all x Bj. p p(x)/(((())))) (if paj)) 0, we set (z(x) 1/(2 1).which is the uniform distribution
7

---

over Bj). The protocol learns by estimating both the distribution over blocks and the normalized distributions within each block.
Estimating Pa. Each user maps the observed samples to the set they belong to in Bi..... B, Then the users the first bit to the 1-bit protocol in Theorem 2.1 learn pg- The server collects the messages and obtain an estimate Pg.
Estimating normalized distributions. Users are partitioned into é sets S S S., each of size [n/t]." For i E Sj. user i uses the remaining bits to send the first sample it observes in By. none of them is observed, the user sends T.
Upon receiving the messages, the server uses the empirical estimator to estimate Рj+
Eies, 1(Y = 2} (イ(2) = Eies, 1(Y, # =}
x E (2%.
Eies, 1(Y, + 1} + 0. Otherwise, we set (5(x) = 1/(22 - 1) for all a E Sj.
The final estimates are simply
((x) PB() (z),
Vj [t), Bj.
Next we prove that the estimator achieves the upper bound guarantee in Theorem 1.1. We first relate the estimation emrors for P to those of Pa and Pj.
Lemma 3.1. We have E(TV p)] & (P PB)] - Pe
Proof. We write
(TTV(P
1 Σ
Σ
[p(x) p(x) 5 X Σ
jeld zEB;
JE(1] BE
$
E
Σ
(# - -pB()) + (p)()),
(z))
jElA BEB,
E
Σ
Σ
()(1))p(()) (apn((i)nn((]]]) + E Σ
pn(iI
(n(i)
Σ
[1(() p5 (+)
2
JE(1]
ZEB,
SC((]
zEB,
ETV (8 PB)
Σ PB())
jEL
Next we bound terms in Lemma 3.1 separately. Since Pa over a smaller domain of size [k/(2' 1)], by Theorem 2.1, we have when 100 h 2 log m logn, n,
E TV PB)] =0
(V
We then bound the error on estimating py 's. Note that since each user in Sy either sends the first sample it observes in Bj or 1 if none of the elements appears, we have the following facts:
1. For j E [t]. let N, == Eies, 1( 1}. the number of samples the server receives
from Bj. Then N; follows binomial distribution Bin([n/4J,.. where B, = 1 (1 Pn Pn(j))" = (mnin(mppp()) 1)).
2. For j [t]. conditioned on that the first sample in Bj is sent, the sample is distributed according to the normalized distribution Pj-
Based on these observations, we obtain the following lemma. Lemma 3.2. If pf( 0, then E[TV P,)1 = o mB
Proof. When By < the bound is trivial since TV distance is always bounded by 1. 8
When
8k n by Chernoff bound, we have Pr N2 n=: 2
< exp
n8, 8t
When N₂ n8; 2
E EVV P/) N, 2 n8 =
2--1 O
n.,
II t does not divide the protocol ignores the last [nt/t] users.

---

Combining both, we get
EJTV(P,,P;)) = (
exp n,,,2 ))
0
A
m.
n..yy
completing the proof of the lemma.
Next we bound the second term in Lemma 3.1 using Lemma 3.2, since 3, --min (t), 1)).
Σ P=(i)E(TV(,, =0
Σ
max
PB
PB
k
Pn Pn)i:::
})
n
nm
jE|t]
k
kl
0
max
(5)
Ti
mu
h2
0
(6)
nm22
where (6) follows from t = [k/(2' - 1)] > m. Together with (4), this completes the proof.
3.2 Regime m < k, 8 (lg(kk/m) increasing m barely helps
When k/2f, the first term in (5) dominates (up to constant factors) and the bound will not further decrease as / decreases (or E increases when using the parameter in Section 3.1). Hence we fix 2m, where the two terms in (5) match. Similar to the protocol Section 3.1, we divide the domain into t = 2m non-overlapping blocks Bı...., Bt, each with size [// [2/] Then we can define рø and Jj. J E [t] similarly as Section 3.1 and estimate them separately.
Estimating pa. Users follow the procedures as Section 3.1 and the server obtains Pa using the 1-bit protocol from Theorem 2.1.
Estimating normalized distributions. index, each user can send element within the block with log [k/(mm]] < l bits. To take advantage of this, we assign each user t' = Le/ log [k/ (2m)]] different blocks. More precisely, user is assigned blocks B, for j (i 1)t'' the first sample they observe in B, or sends if none of them appears.
Since each block is only of size [k/(2m)], given block
1)t' + 2, ..... it' mod For each Bj, the user sends
In total, n users send out ntt' messages, which we index as (Zi)iejne)) Based on which of the t blocks the messages correspond to, we can divide them into & sets where Sj- = (i E [n't] j = mod f). 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/ [[m]/2mm]]
Eies, 1 2) P)(x) Eies, 1[ + x}
We show the above protocol achieves the upper bound in Theorem 1.2. The proof is in similar spirit
the proof in Section 3.1 with only two differences. First we fix = 2m, hence the first term in (5) dominates. However, since for each block Bj, the server receives [Sy| 2 nt' n2t) O m (11)
nf
users, the estimation error for the normalized distribution within the block can be improved by factor of t'. We defer the details of the proof to the supplemental.
3.3 Regime m 2 k: learning each Pa separately
In this case, the protocol in Section 3.2 will not apply since the domain is of size i < 2m. We instead consider protocol which estimates each Pa using samples from Bin(m, px) did in Section 2. Since now each user has l bits, the users can send information about & elements, which improves the rate by 1/vê factor. We next describe the protocol formally.
We assume without loss of generality e < k; otherwise, each user only uses & bits of its allowed e.4 To each x E [k]. we assign a set of users S, as follows. User is set S, and only
'This enough since plugging in é & in Theorem 1.2 already achieves the optimal centralized rate.

---

Bi' E [e - 1). (i 1) + = mod k. It can be verified that each user is assigned to exactly & xt for all z. Once the sets are assigned, users in Sp run the one-bit protocol in Lemma 2.2 to estimate Pz. By Lemma 2.2, we have when né 100% log m log n,
sets and that [S 2 21
E I - pll]
Σ zE[R]
DELO Pa) =0 pa)
EneM ( P&) k m mmiin Sal
wine 1Sx 30To
= 0
k
mnl
Hence, applying Cauchy- Sechharz-crarrzaaa and Jensen's inequalities we get, as desired,
1 2V
k2
([TV
kE p p1
O
mn!
4 Lower bounds
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 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 0 e & be a vector. product of Poisson distributions pe is a product distribution over N whose ith marginal is a Poi(O(t)) distribution: Pe = @ Poi (())). We next introduce a family of product of Poisson distributions, which will be used as hard instances. For all E {-1,+11 define 0₂ as
m + 2E2.)
(i)
E [A].
k
For z E +11, let Ps = pe_ and P {p. : (-1, Consider now the following generative process: (1) Pick Z uniformly from (-1, +1, (2) Users observe samples X" from pz 60m (3) Users follow a protocol II and send messages Y". The following lemma states that if there exists discrete distribution learning protocol, there must exist a protocol which is able extract enough information about Z from Y
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 e/10, there must exist a protocol II whose messages Y under the above defined process satisfy Σie kk] I[Z;; Y") (2(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 1 for coapuunicaatiocconsrriiinn protocols, which we do in the next lemma:
Lemma 4.2. Let Z - -\" be the Markov chain defined above. For any t-bit interactive protocol:
1. When m2 < ki we have Σie(k] I(Z; < m
2. When m > k log k and < (k/E)², we have Σie(n) ((Z;Y") < mnde?
We provide the detailed proof of these two points in the supplementary. and only provide sketch here. The bounds are proved using the >=-contraction bounds recently developed in [4]. The bounds relates the amount of information to a function Φz.i x ddp
<p..s gi 1). where 2 Si denotes the vector obtained
by flipping the ith coordinate of z. Obtaining the bound ΣiEW 1(2;; Y") O(2'), while quite
involved, then can be done using ideas from [4]. Getting the tight bound of E.EM) ((; ) = O()) when m > & log k however, requires some additional ideas. Indeed, to get such a dependence on f. one would typically argue about and use the subgaussian tail of da.zi unfortunately, the quantity d provably does not exhibit such tails for the family of Poisson distributions. To circumvent this issue, we decompose Φ2,i into 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 I.I. Assume there exists an f-bit protocol which estimates any discrete distribution up to expected TV error e. By
Lemma 4.2 (Item 1) and Lemma 4.1, we have mn2fc2 > Eve(k) T(Z;; Y") = 2(k))
Aa Reorganizing, this implies = = 2 mn24 ) as stated in Theorem 1.1. Theorem 1.3 can be obtained similarly using Lemma 4.2 (Item 2) and Lemma 4.1.
10

---

Acknowledgments and Disclosure of Funding
Jayadev Acharya is supported by NSF-CCF- 1846300 (CAREER), NSF-CCF-1815889 and 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-CCT- 1846300 (CAREER). Himan- shu Tyagi is supported in part by research grant from the Robert Bosch Center for Cyberphysical Systems (RBCCPS), Indian Institute of Science, Bangalore.
References
[1] Jayadev Acharya, Clément I. Canonne, Yuhan Liu, Ziteng Sun, and Himanshu Tyagi. Interactive inference under information constraints. In 202/ IEEE International Symposium on Information Theory (ISIT), pages 326-331. IEEE, 2021. To appear at IEEE Transaction on Information Theory. Full version available at 10s/2007.10976 1.3, 1.4
[2] Jayadev Acharya, Clément I.. Canonne, and Himanshu Tyagi. Inference under information con- straints I: Lower bounds from chi-square contraction. IEEE Trans. Inform. Theory, 66 (6(12):7835- 7855, 2020. Available at abs/1812.1
1.4
[3] Jayadev Acharya, Clément I.. Canonne, and Himanshu Tyagi. Inference under information constraints II: Communication constraints and shared randomness. IEEE Trans. Inform. Theory, 66(12):785-7777, 2020. Available at abs/ 190.0800... 1.3, 1.4
[4] Jayadev Acharya, Clément L.. Canonne, Ziteng Sun, and Himanshu Tyagi. Unified lower bounds for interactive high-dimensional estimation under information constraints, 2021. Available at abs/2010.06562v4. 1.4, 4, 4, C.I, C.2, C.1, C.2, C.4
[5] José A Adell and Pedro Jodrá. Exact kolmogorov and total variation distances between some familiar discrete distributions. Journal of Inequalities and Applications, 2006(1):64307, 2006. A.2.2
[6] Leighton P. Barnes, Yanjun Han, and Ayfer Özgür. Fisher information for distributed estimation under a blackboard communication protocol. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 2704 2708. IEEE, 2019. 1.4
[7] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff. Com- munication lower bounds for statistical estimation problems via distributed data processing inequality. In Symposium on Theory of Computing Conference, STOC' 16, pages 1011-1020. ACM, 2016. 1.4, 2.1.
[8] T. Tony Cai and Hongji Wei. Distributed gaussian mean estimation under communication constraints: Optimal rates and communication-effe effiicient algorithms. CoRR, abs/2200100887, 2020. 1.3, 1.4, 2.1,2, 2.1.2, A
[9] Clément L. Canonne. tttps://githul cww/ componncnnnee////mmmmmmmmaeee/ee poissonconncenraationn pdf. C.4
A short note on Poisson tail bounds, 2017.
URL: master/
[10] Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, and Ludwig Schmidt. Communication-eficiee distributed learning of discrete distributions. In Advances in Neural Information Processing Systems 30, pages 6394-6404, 2017. 1.4
[11] Yanjun Han, Pritam Mukherjee, Ayfer Özgüür, and Tsachy Weissman. Distributed statistical estimation of high-dimensional and non-parametric distributions. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT' 18), pages 506-510, 2018. 1.3, 1.4
[12] Yanjun Han, Ayfer Özgür, and Tsachy Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. In Proceedings of the 31st Conference on Learning Theory, COLT 2018, volume of Proceedings of Machine Learning Research, pages 3163-3188. PMLR, 2018. 1.4
11

---

[13] Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. Advances Neural Information Processing Systems 27, pages 163-171.
2014. 1.4
[14] Yuchen Zhang, John Duchi, Michael I. Jordan, and Martin J. Wainwright. Information-theorele lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems 26, pages 22362336, 2013. 1.4
12


Reviews:
[{"review_id": "WrJh_e-NuI", "reviewer": "Reviewer_RBWm", "summary": "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.\n\nThe 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$.  ", "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": "The proposed problem is a nice and natural generalization of the $m = 1$ case that had been studied previously.  Overall, the presentation is reasonable.  \n\nI do have a few questions about the main results.  Theorem 1.1 solves the case when $m < k/2^l$.  However, I have some concerns about the significance of Theorems 1.2 and 1.3 (especially Theorem 1.3) and whether they actually imply the phase transition that is claimed.  \n\n1. In both statements (Theorem 1.2 and Theorem 1.3) should the $\\sqrt{\\frac{k^2}{mn}}$ be $\\sqrt{\\frac{k}{mn}}$ instead?  A lower bound of  $\\sqrt{\\frac{k^2}{mn}}$ seems to be false in the regime where $n = 1$ and one player may just communicate the entire distribution to the central server.  Does the upper bound proof also only need  $\\sqrt{\\frac{k}{mn}}$ and not $\\sqrt{\\frac{k^2}{mn}}$  (based on skimming the supplement this seems to be the case but I did not verify all of the details carefully)?\n\n2. My main concern is the following:  if I want to estimate the distribution to some constant accuracy  (say $0.1$) then the lower bound in Theorem 1.3 only kicks in when $l \\geq k$.  This is because by assumption $n> \\frac{k^2}{l^2} \\rightarrow nl > \\frac{k^2}{l}$ so plugging this into the expression for the lower bound gives something less than $1/(\\log k)$ unless $l \\geq k$.  However, $l \\geq k$ is well outside the range of the claimed phase transition at $m \\sim k/2^l$  (which only makes sense for $l \\leq \\log k$).  Thus, it does not seem that we can apply Theorem 1.3 to prove that there is indeed a phase transition.\n\nAfter Author Response: Thanks for clarifications, after reading the response I do believe that the contributions are significant enough and I have raised my score accordingly.  Still, I think the authors need to be more clear and explicit about what regimes their results do and do not cover.  In particular the paper is a bit misleading in that it seems to claim a \"full understanding\" while the results only cover some of the important regimes.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "T4A29uUzq1_", "reviewer": "Reviewer_VJXc", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the problem studied studied in the paper, namely that of distributed density estimation, is interesting and timely. I believe the work provides significant generalizations beyond what exists currently in the literature (existing literature usually uses either users having m=1 sample or one able to send \\ell=1 bit of info), and this requires some novel proof ideas. For what it's worth, I also think the work is nice because it pulls high level ideas from many different disciplines like information theory, statistics, and applied probability. I list a few comments below followed by some typos I found.\n\nSome comments on the work: \n\nOne comment is that at some points in the paper, I thought the writing wasn't very accessible to non-experts. Essentially, if you don't already understand the problem set-up and some standard coding schemes for such problems, you will likely have difficulty understanding the first section of the paper. For example, in introducing the problem setting, it is not clear what you mean by the channel. Is your setting that a central server receives a noisy version of each user's message y_i? This is one standard usage of 'channel' in communication and statistics, but apparently not what is meant here. In particular, you don't tell use what is meant by x in your problem setting in the definition of the channel between lines 36-37. It may be useful to say here something like the channel represents the decision making process of the user: it states the probability distribution relating each possible user dataset to each possible user message. As another example, you aim to motivate your algorithm with a simple estimation problem related to coin tosses, but then when explaining how to solve this estimation problem you end up just saying it's technical and \"we use a scheme similar to the Gray coding based scheme proposed for Gaussian mean estimation in [7], but with modification.\" So unless the reader is familiar with the Gray coding scheme, this doesn't do much in the way of motivation. A way to actually motivate the suggested scheme might be to discuss why a naive solution of having each user send 0 if they see more heads than tails and 1 otherwise is ineffective if the coin is strongly biased. This would at least give the reader a feel for what the technical challenges are and some intuition for the two-pronged approach suggested in what follows.\n\nSome typos/comments:\n-- You use the notation \\textbf{p} in line 23, but it isn't defined until later.\n-- What is $\\mathcal{W}$ in line 35?\n-- Should the O() rate between lines 168-169 use sum_x p_x(1-p_x) in the first term in line with the result between lines 164-165?\n-- On line 179 \"... is defined by a a collection...\"\n-- It may be worth mentioning that your proof of Lemma 3.1 uses a different (but equivalent) definition of total variation than is given in the problem setting and notation section. I think the second inequality in the proof is actually an equality.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "9CXdPElQwFq", "reviewer": "Reviewer_EXUY", "summary": "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.\n\n\n", "questions": "", "limitations": "", "rating": 7, "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 makes some progress on the very fundamental problem density estimation of a probability distribution in the distributed setting. The main contribution is the extension to the case where each user holds multiple samples (denoted by $m$) from the distribution, rather than just one sample as in prior works. This also revealed an interesting phase transition of the error of the estimation around $m=k/2^\\ell$, where $\\ell$ is the message bound. The authors also provide lower bounds showing that the phase transition is inherent. On the negative side, some of the bounds need artificial conditions to work and although tightness up to log factors is shown for sufficiently large $n$, there are still parameter regimes where the bounds do not apply. \n\n\nMinor Comments:\nLine 4: It might be useful to introduce the notation k, for the domain size here along with the other parameters. \nLines 32 and 36: It might be confusing that the same variable (x) is used both as an integer and as a vector. \nLine 35: $\\mathcal{W}$->$\\mathcal{W}_\\ell$, as it is used later in equation (1)\nLine 88: can “be” shown\nLine 112: $\\ell$ “bits” of communication\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors as well as myself do not see any potential negative societal impact from this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "5p4LcqbpnPf", "reviewer": "Reviewer_RoPp", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 big O notation is not carefully used throughout the paper. In some occasions the authors need to clarify about the parameter that goes to infinity in the Big O. \n\nThere is no comparison with already existing bounds. It is recommended that the authors include the existing crude bounds and then compare it with their proposed bounds to show the amount of improvement in the computed bounds.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper seems to be among the first works in this area. So it studies a relatively easy case and proposes algorithms for this case. It is therefore limited to such cases. Future works could improve upon the results in this paper.", "review_text": "", "extra_scores": {"ethical_concerns": "No concern", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall the reviewers liked the matching upper and lower bounds in a wide range of regimes for a quite natural distributed problem, generalizing in a significant way previous work that only held for one sample per machine. The reviewers also found the phase transition to be interesting, as well as the techniques drawn from different areas. There were some specific presentation comments that we encourage the authors to take into account. 
Decision: Accept (Poster)