Refinement Methods for Distributed Distribution Estimation under $\ell^p$-Losses
Authors: Deheng Yuan
Tao Guo
Zhongyi Huang
Venue: NeurIPS 2025 spotlight ()
Keywords: Distributed estimation
distribution learning
communication constraints
distributed algorithms
optimal rate of convergence.
Primary area: theory

Abstract: Consider the communication-constrained estimation of discrete distributions under $\ell^p$ losses, where each distributed terminal holds multiple independent samples and uses limited number of bits to describe the samples. We obtain the minimax optimal rates of the problem for most parameter regimes. As a result, an elbow effect of the optimal rates at $p=2$ is clearly identified. In order to achieve the optimal rates for different parameter regimes, we introduce refinement methods and develop additional customized techniques in the estimation protocols. The general idea of the refinement methods is to first generate rough estimate by partial information and then establish  refined estimate in subsequent steps guided by the rough estimate. Then customized techniques such as successive refinement, sample compression, thresholding and random hashing are leveraged to achieve the optimal rates in different parameter regimes. The optimality of the estimation protocols is shown by deriving compatible minimax lower bounds.

Refinement Methods for Distributed Distribution Estimation under (r-Losses
Deheng Yuan', Tao Guo Zhongyi Huang' Department of Mathematical Sciences, Tsinghua University School of Cyber Science and Engineering, Southeast University
State Key Laboratory of Integrated Services Networks, Xidian University ydh220mails. tsinghua, edu, en, taoguo@seu. edu. cn, zhongylh@tsinghuu.. edu. on
Abstract
Consider the communication-consee constrained estimation of discrete distributions under @ losses, where each distributed terminal holds multiple independent samples and uses limited number of bits to describe the samples. We obtain the minimax optimal rates of the problem for most parameter regimes. As result, elbow effect of the optimal rates at p = clearly identified, In order to achieve the optimal rates for different parameter regimes, and develop additional customized techniques in the estimation protocols. The general idea of the refinement methods is to first generate rough estimate by partial information and then establish refined estimate in subsequent steps guided by the rough estimate. Then customized techniques such successive refinement, sample compression, thresholding and random hashing are leveraged to achieve the optimal rates in different parameter regimes. The optimality of the estimation protocols is shown by deriving compatible minimax lower bounds.
introduce refinement methods
Introduction
Motivated by applications in areas such as federated learning (13). distributed statistical estimation problems have recently received wide attention. In this setting, multiple distributed agents cooperate to train model, while each of them can only access to a subset of training data. These agents can exchange messages but their communication budgets are constrained. The performance of the system often limited by the communication constraints.
One fundamental learning task is to estimate the underlying discrete distribution of the data. Under communication constraints, the minimax optimal rates for the estimation error were studied in I Another important constraint is the differential privacy, and the corresponding problem was similarly considered in 6 13). these works, only one sample was accessed by each distributed terminal and the most common E and losses were used to measure the estimation error. However, this is an oversimplification of the practical case, where general ( losses may be necessary and each terminal can access to n > samples.
On the one hand, some works [54 further explored the distribution estimation problem with 1 samples at each terminal, under the e loss. On the other hand, later works [16 17) considered the problem under general ( losses, with a limited scope regime p > 2 only suboptimal lower bounds were derived. In the more practical case where each terminal can obtain n samples, the optimal rates under f losses are also unclear. The problem with n > samples is much more difficult than that for n 1, since its inherent structure is not
1. Even in this limited case, for the
The first two authors contributed equally to this work. Corresponding authors: Tao Guo, Zhongyi Huang.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

revealed in the n = 1 case, Even though (14) presented an optimal protocol for n >> 1 and the E' loss, it still does not apply to ! losses since its optimality depends heavily on several special properties of the el loss.
In this work, we consider the distributed estimation of discrete distributions under communication constraints. The range of the problem is expanded in two directions, letting each terminal hold n > 1 samples and imposing general ( losses simultaneously. We design interactive protocols achieve optimal rates in this technically more challenging setting. The difficulty lies in the communication budget allocation strategy, namely how to assign multiple terminals and their communication budgets to the tasks of estimating different distribution entries. The naive uniform allocation strategy that treats all the entries equally fails to achieve the optimal convergence rate under the general ( loss for p > 1. To achieve the optimal rate, communication budgets should be invested based on the distribution to be estimated. As a result, existing protocols cannot handle the general problem under the @ loss. Instead, we develop refinement methods in the estimation protocol, which first establishes rough estimate based on partial information obtained by portion of budgets, and then uses it to allocate the remaining budgets for refining the estimate. The refined estimate can achieve the optimal error rate, since the remaining budgets are allocated most effectively.
We introduce additional auxiliary estimation techniques to customize the refinement methods for different parameter regimes. The induced estimation protocols shows upper bounds for the optimal rates. We also derive compatible lower bounds for most parameter regimes. Hence the optimality of the protocols is shown and the optimal rates are obtained in these regimes.
1. We exploit the classic devide-and-oonquee technique and design a successive refinement estimation protocol equipped with adaptive budget allocation strategy. The distribution is divided into blocks. The estimation task is achieved by first estimating the block distribution and then conditional distribution over each block. The block distribution has a lower dimension, and the divide-and-conquer procedure is not stopped until it is more efficient estimate each entry directly. This induces successive refinement protocol where the rough estimate for the block distribution is refined by further estimating the conditional distributions over blocks. More importantly, in the refinement step we introduce adaptive budget allocation strategy. Specifically, terminals are assigned to estimating different conditional distributions based on the block distribution estimated by the former phase, which achieves faster convergence rate for > 1 than the uniform allocation strategy by previous works [14). Hence the successive refinement protocol achieves the optimal rates up to logarithmic factors for most parameter regimes with 1 S S 2. Moreover, by using multiple successive refinement steps rather than only one step. our protocol for p 1 achieves the optimal rates for larger range of regimes than that in [14]
2. For p > 2, we develop auxiliary sample compression techniques, so that refinement methods can be adopted in the estimation protocol. Different from 1 S p S 2, the protocol in this regime obtains rough estimate of the distribution itself (rather than an estimate of the block distribution) first by uniform allocation of budgets. It then refines the estimate by allocating the remaining budgets according the rough estimate. In the refinement stage of the protocol, we further develop sample compression techniques, which compress the description for samples and reduce the communication budget, allowing more samples be transmitted. The resulting protocols can achieve the optimal rates for relatively large n.
3. In the very special regime where the total communication budget is extremely tight, we incorporate a thresholding technique into the estimation protocol to achieve the optimal rate. The key observation is that under the extremely tight communication budget, if an entry of the distribution is too small then approximating it simply by 0 induces a lower variance than trying to estimate them. For p > 2, the thresholding technique combined with the sample compression to yield the optimality protocol. To the best of our knowledge, the regime has not been discussed in any previous work.
4. For the special case n 1, we design an optimal non-interactive protocol by exploiting random hash functions, rather than the sample splitting trick or the simulate and infer protocol used in previous works
8 [8). To show the optimality, we further establish a compatible lower bound that is strictly better than that in [16 for p > 2. This proves the optimal rates under general S losses, especially that for p > 2 left open by previous works [16]

---

The expression of the optimal rates under S losses reveals an elbow effect at p 2. providing more insights into the distributed estimation problem. It is interesting to compare our results with the elhow effect discovered in the nonparamentric density estimation problem 199 20 It is not a coincidence since in both problems there are constraints for the estimated object (namely the normalization constraint for the distribution estimation problem and the Sobolev regularity constraint for the nonparametric density estimation problem), and the loss functions can vary with a parameter. The similarity sheds light on how the optimal rates are affected by the relation between the imposed loss function and the constraints on the estimated object.
The remaining part of this work is organized as follows. First, the problem is formulated in Section 2 Then we present our main results for S p I 2 and p 2 in Sections B and respectively In Section 5] the special case with n is discussed and the non non-interactive protocol is presented. Finally, the optimal rates are summarized in Section SectionGJand few further remarks are given Section 7 Detailed estimation protocols and complete proofs of both upper and lower bounds can be found in the technical appendix.
2 Problem Formulation
Denote a discrete random variable by a capital letter and its finite alphabet by the corresponding calligraphic letter, e.g., W W. We use the superscript n to denote n-sequence, e.g., W (W.) For a finite set W of size l = [W], let Aw be the set of all the probability measures over W.e. Aw A {p(-)= p(w) E [o, I], Vu E W, P(w) = 1}. Let Aw be the set of subprobability measures, i.c. Aw (p(-) p(w)= [0, 1], Vw W. W. p(W) - 1}.
Suppose that we want to estimate the dimensodmennion distribution pw E Aw with dimension k, and the samples are generated at random. To be precise, let Waj ~ Pw (w), = 1,2, m, j = 1, 2, ... nn be i.i.d. random variables distributed over W. The total sample size is mn.
Consider the distributed minimax parametric distribution estimation problem with communication constraints depicted in Fig. [ which is theoretical model of federated learning systems. There m encoders and one decoder, and common randomness is shared among them. The i-th encoder observes the samples W
(Wa))=1 and transmits an encoded message B, of length / to the decoder, i 1, ...; m. Upon receiving messages dTh (B:) the decoder needs establish reconstruction Pw E Aw of pw-
An (m, n, k protoool P is defined by series of random encoding functions Enc; W" {0, (i-11) + {0, 1)¹ vi 1, ..... m,
and a random decoding function
Dec: {0, mm Aw-
The i-th encoder is aware of the messages sent by the previous encoders (which can be achieved by interacting with other encoders and/or the decoder), and it generates a binary sequence B, = Enc,(W" B1: of length 1. The reconstruction of the distribution is pw Dec( B1, B2.... B..)
For 2 1, we use the l loss to measure the estimation error. We are interested in the minimal error of all the estimation protocols in the worst case, as the true distribution pw varies in the probability simplex Aw. To be specific, our goal is to characterize the order of the the following minimax convergence rate
inf R(m,n,K, n. k,, (m, n. &r. (, D-protocol PW
sup Billpw P1
Remark 1. The (m, n, k 1)-proooool P defined in this work is usually called the (sequentially) interactive protocol in the literature. The protocol is called non-interactive, for each i = 1,.... m, the i-th encoder is ignorant of all the messages B1:11 sent by previous encoders and the encoding function Enc, (W²) is a function of the samples only. In most cases we design interactive protocols since it is too hard to construct a non-interactive protocol. For some simple special cases, non- interactive protocol achieving the optimal rates can be constructed, which will be indicated.
We further define some necessary notations. For any positive functions a(m, n, ki 1,p) and B(m, n., k. I.p. we say 3 b if a S e. b for some positive constant e > 0 independent of pa- rameters (m, n, k. I). The notation > is defined similarly. Then we denote by a = b if both a 3 and 2 b hold. Denote by A b the minimum of two real numbers and b, and a V b the maximum.
3

---

B1
WT
Encoder 1
Bg
(B1, W
Encoder 2
Decoder
Pw
Bm
(B1m-1: Wm)
Encoder m
Figure 1: Distributed (sequentially) interactive distribution estimation
3
Optimal Rates for 1 S p <
First assume that 1 I S 2. We present the upper bound in the following theorem.
Theorem 1. Let S p S 2, then we have R(m, n, k k,l,)) 3
k--
(mml) 1 V
2 k. m( > 1000k log(mn) logn,
(la)
(mm)
11 & log ( + 1)
41-
k
V
< k ml1 An)
2000m log(mm) log
(1b)
(ml)
(mn) 8
2
k (mm22)
k
n <
ml1 A n) 4000m log(mm) log
(1c)
2
log & k (ml)p-1²
log k < 1 < n, ml < k.
(1d)
Proof. The case (Ta) is by Proposition T in Appendix cases Tb and (Tc) are by Proposition
in Appendix B and the case (Id) is by Proposition 5 in Appendix We sketch the proof here and details can be found in the appendix.
Successive refinement protocol with adaptive budget allocation For the first three cases (Ta.. (Ib) and (cc), the estimation protocol can be sketched as the following inductive procedure.
At each step, choose some lo and construct a division W = W, with [WA] S 2 1, 4o </ and f. = [ 1- First suppose that the distribution pg of blocks has been estimated to some accuracy by some Pg. Then each encoder can use its bitbit message to only describe its samples on predetermined block W,. Based on these messages, the decoder then estimates the conditional distribution p. Aw, on the s-th block, where (w) & p(w[W.). Based the message, the decoder constructs p. as an estimate of p.. Combining PB and p. for each block s, an estimate of pw (w) for W.. Note that pø E Ap::t]
can be immediately obtained by letting pw (w) = PB (s) p always has lower dimension than the dimension & for pw. Fewer encoders are needed for the smaller problem. Hence Pw can be refined from these layered block distributions successively.
For the base case 1 < n where the length i of the distribution Pw is sufficiently small, it is optimal to estimate Pw (w) directly for each analysis is only shown for the e loss in 14]. it can be adapted to prove the optimality of the above procedure for EP losses with 1 S p < 2. See Appendix for details.
W using the one-bit protocol in [14). Although the error
Then consider the successive refinement subroutine for estimating all the p.. 3 I,.... t given an estimate PB for pB. Through detailed error analysis (see Lemma and its discussions). to achieve the optimality, the budget for estimating each pa should be proportional to (B(s). Since the decoder have obtained the rough estimate ( it can allocate remaining budget by interactions with encoders. Such an allocation plan in contrast to the estimation problem under the TV loss discussed in Section 3.1 and [14]. where uniform budget allocation among all the P.. = 1,..., is optimal.
Given the successive refinement subroutine and the estimation protocol for the base case, it remains to consider the choice lo as well the budget allocation between these successive steps. They depend on the parameter regime. For the case lb where the length is relatively large, each message

---

can be divided to describe multiple samples. In order to directly exploit the protocol for the base c. In contrast, for the case in estimating the block distribution Ps, we choose t ~ n. and lo ~ log n case ([c) where is relatively small, we let lo I and then use multiple successive steps until the dimension of the distribution is reduced to n 2". The complete estimation protocol is constructed in respectively.
Appendices B.2.2 and B B.2.3
Refinement protocol with thresholding techniques For the final case (Id), the refinement protocol designed with the help of thresholding techniques. The idea is that under the extremely tight com- munication budget, roughly ~ ml samples can be transmitted by the protocol. Then approximating those Pw (w) ml simply by 0 is better than estimating them. In the refinement step, the remaining
budget can be used for generating another independent estimate for those pw (w) = ml whose number ~ ml is limited. Detailed protocol can be found in Appendix E.1
Lower bounds under the ! loss can be derived in the following lemma, which provides baseline. Lemma 1. For 1 S S 2, we have
V hi- (mn)
kt
n 2 l loogh k. m >
(mnd)
1
k1-8
V b--
h: 2
S n < l: log k. m >
(ml k) h
(mn)
1
R(m, n, ki 1.P. =
k
2 mn2 >> k2
n <
(mn22) $
12 (mn) ?
k ml 2
(ml))-1
Proof. Lower bounds for the first three cases under the l loss can be derived from existing re- sults in [14) under the E loss. For the last case, we use an algebraic technique to first note R(m, n, k, R(m, n, 2ml, L, p) and then bound the latter, which slightly strengthens the usual bound obtained by the data processing inequality. This induces compatible lower bound with the upper bound in [d).. The detailed proof can be found in Appendix G
Combining Theorem and lemma the optimal rates for the following cases can be roughly characterized by
k
k!-B
2 k. ml 2 k,
(mnl) 1
(mn)
k1- 2
Al-
k
< k; ml x k
(ml)
(mn)
R(m,n, n, k, x
k
k
n 2 mn2 - k22
(mm22)
カ1
ml = k.
(ml)p-I
(mn)²
Remark 2. We add a few explanations concerning the boundaries 2 The regularity condition
m > ($)2 in the lower bound is induced mainly by technical reasons and the boundary ml > is more essential. Similarly, the conditions m(l A k) > 1000k log(mn) log n and m(l A n) > 2000n log(mn) log n in the upper bound can be relaxed by finer analysis and the true boundaries seem to be around ml > k and ml >> n. respectively. Under these observations, in the third case the conditions m > 2 and n < k
z imply that m > k and hence ml > k > n is fullfilled.
3.1 Special Cases: Optimal Rates for p and p=
In this subsection, we specialize our results and characterize the optimal rates under the most commonly used total variation (TV) and squared losses, i.e. E and e losses. For the TV loss, the successive refinement protocol can be made non non-interactive. See Appendix C details.
5

---

Theorem 2. The following upper bound can be achieved by non non- inn-interaative protocol.
12
n z k, m(1 k) 1000k log log n.
mnl
mn
R(m, n. 1,,,1)
llog( ml
1)
k
S n < k, m A n) > 2000n log m log n,
mn'
2
1-2
n < 2 m A n) > 4000n log m log n.
mm2
For the TV loss, we have the following characterization of the optimal rates.
n 2 ki ml 2 k,
mnl
mi
k
k
S n < k ml ビ k
R(m,n, k, 1)
ml
mn
2
k2
A 1,
< 2
mn2
ml k.
Remark 3. In [14]. non-iteractive protocol for the same problem in Section 2 under the TV loss is also constructed. However, corresponding to the third case in Theorem 2 [14] a stronger restriction m > 100 ft log m log imposed (cf. Theorem 1.1 in [14] and note that the notations m and n are interchanged therein). The restriction is induced by using the first bit of each encoder to estimate the block probability pa with the protocol for the first case. The conditional probability in each block B is then estimated. Combining it with the estimate for pn. estimate for Pw is obtained. In fact, it is a one-step reduction. We note that the step that estimates and summarized
conditional probability can abstracted separate protocol, and it has inductive nature. Instead of using it only once, we iteratively use the protocol, which inspired by the classic divide-and-en -ndd--u technique. Thus successive refinement protocol relaxes the restriction in [4 and achieve upper bound for wider parametric range.
The squared loss is the most important loss, in both theoretical analysis and algorithm research. By directly specializing Theorem we have the following upper bounds under the squared loss.
Corollary 1. For the squared loss, we have
1
2 k m(1 K) > 1000k log(mn) log n,
men Tan
log(* 1)
k 2
S n < k, m(1 A n)
2000n log(mn) log n,
R(m, n, k,,, 1=pp=0 2) =
ml
mn
k
k
n < 2 m( (1 n) 4000n log(m)) log n,
mn2 log k. ml
log k 1 n, ml k.
Lemma 1 can be specialized to obtain the lower bounds as well. Then we have a more complete characterization of the order of R(m, n, k. 2).
k
V
n ki ml 2 k,
mnl
min
1
k
R(m,n, 1, 2)
S n
hi ml 1 k,
ml
mn
2
k
n < k 2
mn2! 1 12
mn2

---

4 Optimal Rates for p > 2
For p 2, we first present the upper bound in the following.
Theorem 3. Let p > 2, then we have R(m, n, k. k,I,p) 1
k
1
n nz k. m(l A 1000k (mg(mm) logn, n, (5a)
(mnl) &
(mn) &
log* k
k
S K. mil A An (2
1000n log(mn) log k.
(ml) 8
(mn) 4
1 log ki k
(5b)
k
mil n)
4000n log(mm) log n,
(5c)
mn2
(2))
log" lo V log 4p (mn) (ml))-1
log k < 1 < n, ml n.
(5d)
(mn)
Proof. The case (5a is by Proposition I in Appendix A the case (5b) is by Proposition in Ap- pendix D the case (5c) is by Proposition Appendix and the case (5d) is by Proposition
in Appendix We present sketch of the proof for these cases here.
Refinement protocol For the case (a). the first step of the protocol for p > is the same that for 1 S p & 2. That is, a rough estimate Pw is established by assigning the first half of all encoders uniformly estimating each entry pw (w) using the one-bit protocol in [14). But it is not enough, since for p > 2 the estimation error for the big entry pw (w) decays significantly slower than that for the small entry, which is different from the case 1 S p S 2. To overcome the difficulty, refinement method is necessary, where a portion of roughly (w(ww remaining budget is allocated to estimate pw (w). The spirit of the allocation strategy is similar to that designed for the pointwise estimation problem with n = 1. Details can be found in Appendix A
Refinement protocol with sample compression techniques For the case (b). sample compression techniques are further incorporated. The starting point is also the refinement method, but this case the length of the distribution is too long, namely k n. Hence the optimal estimation method for the encoder is not to summarize its samples and describe each pw (w), but to describe samples observes directly. This makes how to do the refinement step obscure.
Sample compression techniques are designed to customize the refinement methods in this regime. Note that the number of the elements w with pw pw(w) ž (denote the set containing those elements w by W\) is about n. Samples are first compressed by projecting them to W", which saves the communication budget for describing them. Hence those pw (w) ž n are refined by invoking the protocol for the case (5a). See Appendix D for details.
The remaining two eases The bound in (cc) is corollary of the successive refinement protocol in Appendix [B] For the case (5d), the bound is achieved by a refinement protocol exploiting both sample compression and thresholding techniques, and details can be found in Appendix E..2
Similar to Section 3 we present the lower bound as a baseline in the following lemma.
Lemma 2. For p 2, we have
k
k 2 (
n 2 l ki m
(mnl)²
(mn)² 2
k (2
nz/ logn
2
S klog k,
R(m,n,k,L.p) z
(md) 2n
loga
(mn)
k
k (2))
n <
mn2 k2
(mn21)²
1
1
ml k
(ml)r-1
(mn)
2
7

---

Proof. Most of the lower bounds can be derived from that under the E! loss in [4] using Hölder's s in the second case and
Inequality. Two of the bounds, namely (ml)),, i log log
[md]p in the last case require the additional algebraic technique the proof of L T The last exception, the centralized (man)
bound-
without communication constraints is little-known but easy to show. Moreover, we
think its proof uncovers the major differences of the estimation problem for p > 2 compared with that for s 2. Hence it is sketched as follows. Detailed proof for all the lower bounds can be found in Appendix G
The centralized bound without communication constraints For p > 2, the key observation is that distributions most difficult to estimate have only few large entries of constant order. It is in contrast to the case 1 S p I 2 where such distributions are close to uniform and each entry is roughly In light of this, the bound can be proved by simple way of reduction to binary hypothesis testing. It is elaborated in the proof of Lemma in Appendix G
Remark 4. We summarize technical contributions in the lower bounds in Lemmas 1 and 2 here. From a technical perspective, the overall proof of the lower bounds depend on four different ways of reduction to hypothesis testing problems. Most of lower bounds under the S loss are derived from that under the loss in 14]. Typically, the proof in [4] uses the reduction to hypothesis testing problem of roughly 2 hypotheses. However, the derived bounds are not tight, especially for the case p > In this work, one of the major finding that the optimal bounds are different for p S 2 and p >> 2. To show that, we introduce two major techniques, which rely on three ways of reduction to hypothesis testing. First, the centralized bound
for p > is proved by the reduction to a binary hypothesis testing. Second, the algebraic technique is exploited for the bounds
(mn) y
conuumiicttt-ootttinneed 5 2 and [m]]jr> T. In its spirit, the technique used in these two cases is equivalent
to two different ways of reduction hypothesis testing problems, with roughly 2n and 2 hypotheses respectively. The latter three ways of reduction used in this work improve bounds derived from the first way in [4], so that the overall lower bound is tight. These four reductions together complete the proof of lower bounds.
Combining Theorem and lemma 2 the optimal rates can be characterized in the following, except for the third case where our lower and upper bounds do not coincide. We conjecture that the lower is tight, which is partially verified for the case n = 1 in the next section.
bound A (
k
ki md 2 n
(mnl) &
(mn) E
k
< k, ml 2 n,
(md) (md)&n2-1 (mn)
(2 &
R(m, n, k,k,p,
(6)
k
k
(mm2l)
<
(2
m k2
(ml)p-1 V
ml 1 k, k ml n, k
(mn)
5 Optimal Rates for = 1,, > 2 and the Non-interactive Estimation Protocol
For and p 2, the lower bound can be derived by specializing Lemma 2 and the compatible upper bound is achieved by a non-interactive protocol, shown in the following thoerem.
Theorem 4. Let = 1, p. 2 2 and m(2 A A 2 R22 We can design a non-interactive protocol that achieves the optimal rate R(m, 1, k, x (m2*) m
Proof. The lower bound is implied by Lemma 2 The upper bound by Proposition G Appendix for which present the proof sketch here.
8

---

Non-interactive protocol with random hashing For each encoder, a hash function hG : W - [1 : 2 is randomly generated. Then the encoder can compress its sample W; to the message (W,))) using its I bits. Upon receiving all the messages, the decoder can directly obtain the estimate by constructing and rescaling the histogram. Further discussions can be found in the proof of Proposition 6 and Appendix F.T.
L
Remark 5, Note that the centralized bound without the communication constraints is neglected m. by previous works [16 17] (see Theorem 6 in [16] and Corollary 3.2 in (17). Hence the lower bounds in both works are clearly not tight (for p > 2). The work [17) further claimed that the lower bound -t- is optimal (see Lemma 3.3 therein), but the sketch given there is not sufficient to m
k V
(m2)
describe protocol that achieves the bound. In fact, given that the lower bound in [7 can be strictly improved, it is impossible to show its optimality. Moreover, constructing the protocol that achieves the optimal rates for 2 is not straightforward and needs additional ideas. We use random hashing technique to resolve the difficulty in this work, and there may be other solutions.
Remark 6. We give some intuitive explanations about why our random hashing protocol achieves the optimal rate in Theorem 4 while existing methods like the simulate-and-inffe protocol 778 [8] fail to do so. As discussed in Section and the proof sketch of Lemma 2 entries pw (w) are typically more difficult to estimate, and communication budgets should be invested more into estimating them. In this sense, the problem resembles a sparse distribution estimation. The simulate-and
for p 2 relatively larger
protocol uses too much communication budget to estimate the smaller entries, while fails to simulate enough samples for estimating the larger entries. In contrast, random hashing reduces estimation errors for the larger entries, despite increasing the error for the smaller entries. Therefore, it achieves an optimal communication budget allocation strategy, well the optimal rate.
6 Summary of the Optimal Rates
In Table T we summarize the characterizations of the optimal rate obtained in Equations 22 to and (6) and Theorem 4 where fundamentally different regimes lead to different rates. The essential bounds originally proved in this work highlighted in red, while those established in previous works 77 16 17) are shown in blue. All the other bounds are corollaries of them. The optimal rates (up to logarithmic factors) are obtained for most cases, except the case p > 2, n < (21)
and
mn2' 2 x2, where our lower and upper bounds do not coincide. Though a good news is that for its special case 1, the optimal rates can be obtained. We conjecture that the lower bound & is tight, which is partially verified in the case 1. We find several interesting phenomena of the optimal rates.
(mm2*)
1. There is an elbow effect in the parameter p between the regimes S p and p 2 2. The difference is clearly reflected in the centralized bound without any communication constraints, i.c. / = co. The bound is -- & for S p < 2, while for 2 2 it is (man) (man)
and independent of the dimension & of the distribution. The other sharp difference is that, for medium n, i.e. (vt S n < k, the optimal rate is independent of l: (up to logarithmic
factors) for p 2 2, which is not the case for 1 S p < 2.
2. Second, the minimum transmitted bits required for recovering the same rates in the central- 2
ized case without any communication constraints are interesting for p > 2. It is roughly & for < n, ml 2 1: and nz for k 2 n, ml 2 n, which is out of expectation.
shows a shrinkage compared to the required number of bits l and for the case 1 < p < 2. Similarly, for n = and m2 > 22, the required number of bits is roughly 2 log k instead of log k.
3. The last observation is that if the total communication budget is extremely tight (ml < k). then the optimal rate dependent only on the total budget and independent of the parameters k and n. This parameter regime has not been studied in previous work to our best knowledge.

---

Table I: Bounds of R(m, n, k, p) for Different Cases
Parameter Regimes
p=1
1 2
p 2
p
4' (man)
R (mn)
=000 00
R
R x
R
mn
(Lemma
n1 2 k
R
R
13v1 < k,
R
mml
&
(mnl)) 2
R
mal
(mnl) 2
ml 2 k
(Proposition
(2 S n < k.
13 n,
R
R
1 R
(ml)
ml
(md) 2n
ml 2 k (p 2) ml 2 2n(p> 2)
(Propositions 2 and
ml < 52 pr 2, k < n),
R=1
R
(mi
R x
1 ml
(ml)p-T
ml (p > k > n),
1> log k
(Proposition 5
(Proposition
n <
mm2 2 22
R
Vmn2
R
(mn21) &
& R
mn2
Proposition
R Z
min
&
(mn2))
n= 1, (2)) < k m2 2 2
R
R
A Vm2!!
R
(m2
R m2
(m29)
(Proposition
7 Discussions and Future Works
In this work, we focused on the minimax optimal rates of distribution estimation over the whole probability simplex, without imposing any additional assumptions on the structure of the distribution to be estimated. In contrast, many previous works studied the structured distribution estimation problems 177 such as the point-wise distribution estimation problem [T] [7] and the sparse distribution estimation problems [0]. These problems are also of both theoretical and practical importance. However, existing works limited their scope to n 1, leaving problems with n > 1 and (2 losses unexplored. We hope our methods can help with determining optimal rates for these problems.
Moreover, the methods in this work are not restricted to the discrete distribution estimation problem. The analysis statistical learning problems various other settings under S losses can also benefit from our methods. The methods deal with the difficulty induced by the normalization constraint of the distribution in the distribution estimation setting, which also shows potential direction for solving problems with similar implicit constraints. A more challenging problem is whether we can construct non-interactive protocols, instead of interactive protocols in this work, to achieve the minimax optimal rates with n > 1 samples per terminal and under & losses. Determining the arivacy-constrained optimal rates for
and E losses is also an interesting direction for future work.
Finally, our protocol for estimating a discrete distribution (especially for the squared loss) can be used as subroutine of the protocol achieving the optimal rates in the nonparametric density estimation and regression problems. See the works [20 21 for details.
Acknowledgments and Disclosure of Funding
This work was supported in part by the NSFC Projects No. 1o.1200 12025104 and 62301 144, in part by the SEU Startup Fund R0100282623003 and in part by the Zhishan Young Scholar Fund No. No.2242025RCB0022.
10

---

References
[1] B. McMahan. E. Moore, D. Ramage, Hampson, and B. y. Arcas, "Communication learning of deep networks from decentralized data," in International Conference on Artificial Intelligence and Statistics, vol. 54, Fort Lauderdale, FL, USA, Apr. 2017, pp. 1273-1282.
[2] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, "Federated learning: Challenges, methods, and future directions," IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 50-60, May 2020.
[3] P. Kairouz, et al., "Advances and open problems in federated learning," Foundations and Trends in Machine Learning, vol. 14, no. 1-2, pp. 1-210, Jun. 2021.
[4] I. Diakonikolas, E. Grigorescu, J. Li, A. Natarajan, K. Onak, and L. Schmidt, "Communication- efficient distributed learning of discrete distributions," in International Conference on Neural Information Processing Systems, vol. 30, Long Beach, CA, USA, 2017, pp. 6394-6404.
[5] J. Acharya, Z. Sun, and H. Zhang. "Hadamard response:
Estimating distributions privately, efficiently, and with little communication." in International Conference on Artificial Intelligence and Statistics, vol. 89, Naha, Japan, Apr. 2019, pp. 1120-1129.
[6] W.-N. Chen, P. Kairouz, and A. Özgür, "Breaking the cattuumiiaaioo-pivvayyyeee trilemma," " in International Conference on Neural Information Processing Systems, Red Hook, NY, USA, Dec. 2020, pp. 3312 33244.
[7] L. P. Barnes, Y. Han, and A. Özgür. "Lower bounds for learning distributions under communi- cation constraints via fisher information," Journal of Machine Learning Research, vol. 21, no. 236, pp. 1-30, Feb. 2020.
[8] Y. Han, A. Özgür, and T. Weissman, "Geometric lower bounds for distributed parameter estimation under communication constraints," IEEE Transactions on Information Theory, vol. 67, no. 12, pp. 8248-8263. Dec. 2021.
[9] J. Acharya, P. Kairouz, Y. Liu, and Z. Sun, "Estimating sparse discrete distributions under privaey and communication constraints," International Conference on Algorithmic Learning Theory, Mar. 2021, pp. 79-98.
[10] W.-N. Chen, P. Kairouz, and A. Özgür, "Breaking the dimension dependence in sparse distribu- tion estimation under communication constraints," in Conference on Learning Theory, vol. 134, Boulder, CO, US, Aug. 2021, pp. 1028-1059.
[11]
"Pointwise bounds for distribution estimation under communication constraints," in International Conference on Neural Information Processing Systems, vol. 34, Red Hook, NY. USA, Dec. 2021, pp. 24 593-24 603.
[12] P. Kairouz, K. Bonawitz, and D. Ramage, "Discrete distribution estimation under local privacy." in International Conference on Machine Learning, M. F. Balcan and K. Q. Weinberger, Eds., vol. 48, New York, NY, USA, Jun. 2016, pp. 2436-2444.
[13] M. Ye and A. Barg, "Optimal schemes for discrete distribution estimation under locally differ- ential privacy," IEEE Transactions on Information Theory, vol. 64, no. 8, pp. 5662-5676, Aug. 2018.
[14] J. Acharya, C. Canonne, Y. Liu, Z. Sun, and H. Tyagi, "Distributed estimation with multiple samples per user: Sharp rates and phase transition." in International Conference Neural Information Processing Systems, vol. 34, Dec. 2021, pp. 18 9892-88911.
[15] J. Acharya, Y. Liu, and Z. Sun, "Discrete distribution estimation under user-level local differ- ential privacy," in International Conference on Artificial Intelligence and Statistics, vol. 206, Palau de Congressos, Valencia, Spain, Apr. 2023, pp. 8561-8585
[16] J. Acharya, C. L. Canonne, Z. Sun, and H. Tyagi, "Unified lower bounds for interactive high- dimensional estimation under information constraints," in International Conference on Neural Information Processing Systems, vol. 36, New Orleans, LA, US Dec. 2023, pp. 51 133-51 165.
[17] W.-N. Chen and A. Özgür, "Lq lower bounds on distributed estimation via fisher information." in IEEE International Symposüum Information Theory, Athens, Greece, Jul. 2024. pp. 91-96.
[18] J. Acharya, C. L.. Canonne, and H. Tyagi, "Inference under information constraints II: Com- munication constraints and shared randomness," IEEE Transactions on Information Theory, vol. 66, no. 12, pp. 7856-7877, Dec. 2020.

---

[19] C. Butucea, A. Dubois, M. Kroll, and A. Saumard, "Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids." Bernoulli, vol. 26, no. 3, pp. 1727-1764, Aug. 2020.
[20] J. Acharya, C. L.. Canonne, A. V. Singh, and H. Tyagi, "Optimal rates for nonparametric density estimation under communication constraints," IEEE Transactions Information Theory, vol. 70, no. 3, pp. 1939-1961, Mar. 2024.
[21] D. Yuan, T. Guo, and Z. Huang, "Distributed nonparametric estimation: from sparse to dense samples per terminal," 2025. [Online]. Available: https:/aarkv.rr//bb/25500..77
[22] M. Skorski, "Handy formulas for binomial moments," 2020. [Online]. Available:
http:///epprraaarrrooga//////111
[23] H. P. Rosenthal, "On the subspaces of L (p >> spanned by sequences of independent random variables," Israel Journal of Mathematics, vol. 8, pp. 273-303, Sep. 1970.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper's 's scope clearly defined, and our contributions are accurately summarized in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Range of applicability of our results is accurately described in the introduction and theorems. Potential further directions not covered in this work are provided in the final discussion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: All the assumptions and proofs are presented in the main paper or the supple- mental material. In the where the complete proof appears in the supplemental material, a short sketch is provided in the main body to provide some intuition.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guuddeeeeedeuuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics https: http:::://///eiis...... httprrpp.....ppooooc/cccccceeea.
Answer: [Yes]
Justification: The research conducted in the paper conform with the NeurIPS Code Ethies in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper focuses on foundational theoretical results not tied to particular application. Although some further applications may have societal impacts, the paper too far from those impacts and should not be responsible for them.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper focuses foundational theoretical results not tied particular application. It does not release data or practical models.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
19

---

Appendix
This technical appendix is devoted to presenting the detailed proof of the main results, by designing optimal protocols to achieve the upper bounds for different parameter regimes in Appendices | to and deriving the compatible (up to logarithmic factors) lower bounds in Appendix G are organized as in Table and follows.
These sections
Appendix A presents the refinement protocol for cases summarized in Proposition
Ta and
5a in Theorems
1 and
Appendix presents the successive refinement protocol with adaptive budget allocation for cases (lb and (Ich Theorem and (5c) in Theorem summarized Proposition 2
Appendix C
presents the non -on-interective successive refinement protocol for the TV loss
Theorem summarized in Proposition
Appendix D
presents the refinement protocol with sample compression techniques for the and
case (5b) in Theorem
3
summarized in Proposition 4
Appendix E presents the refinement protocol with thresholding for cases
Id
5d
in Theorems and
summarized in Proposition
presents the non-interactive protocol based on random hashing for the case Theorem summarized in Proposition
Appendix F
Appendix
shows all the lower bounds in Lemmas and 2
A The Protocol for Cases la and 5a and Its Analysis
In this section, we design the estimation protocol with refinement methods that achieves the optimal rates for cases (Ta) and (a), summarized in the following proposition.
Proposition 1. Let p 2 2, k S mll >> 1000k log(mm) log and < kž. Then for the estimation
problem Section there exists an interactive refinement protocol TR(m, n, k,,, p) such that for
any Pw Aw, the protocol outputs an estimate pw satisfying E[llpw - -pw
(mrl) 2
Remark 7. With the help of Proposition I for 1 S < 2. let the protocol IR(m, n, k,,, p) be the same as that for p 2, i.e., IR(m, n, k 2). Then by the Hölder's inequality, we have
Sw pw Ip k Plllpw Pw 12))
Hence
R(m, k. L) < k' R( (m, n, 1,2) and the minimax upper bound for S < 2 is easily implied by that for 2.
Now we return to the proof of Proposition] I Each entry of the distribution can be estimated by invoking the one-bi, bit protocol in [14] for the estimation of binary distribution. We first show the error bound in the following lemma, which can be proved by adapting the proof of Theorem A.2 and A.3 therein.
Lemma 3. Suppose that there are m' users and each of them observe an i..dd. sample from the binary distribution B(n, 9) and m² > 1000log Then for p 2 2, there exists one-bit protocol which outputs an estimate i satisfying
( m'n
E 114 71
9 V
240 Tog
(m/n)r-1 p-
72
n
A.1 The Refinement Protocol
Rough estimation The first step is let the first encoders and the decoder jointly generate Each encoder can concurrently run / one-bit protocols < n and the goal of each protocol is to estimate Pw( (w(w) for some E W. At the same time, proper allocation plan can ensure that for each E W, there are m' encoders running the protocol for estimating Pw Pw(w) (w). The decoder then obtains the rough estimate ply-
a rough estimate ply- Let m' = L 2x
Lemma using its bits, where < =
20

---

Refinement of the estimate The second step is to let the next encoders and the decoder jointly
generate refined estimate p.. Let m(w) ( A m. Each encoder can concurrently run one-bit protocols in Lemmal using its bits, for estimating some pw pw(ww.. ) At the same time, proper allocation plan can ensure that for each W, there m(w) encoders] running the protocol for estimating Pw (w)) The decoder then constructs the refined estimate pwy following the protocol.
Remark (Necessity of the Refinement Methods). is easy to analyze the error of the rough estimate pwy By Lemma and the assumption ml 1000k log(mn) log n, for any w E W we have
(( (kpw (w) mnl
E [[pw(w) - (w))]] =
+
pw(w) +
(8)
mnl
mnl
However, simply taking the summation can only get the total error bound O (((mm)) {), which is not tight for p > 2. To obtain the tight bound, our protocol uses the rough estimate pWr for directing the budget allocation in the second step. Then the refined estimate in the second step can
achieve the desired upper bound. i.e. E|lpw Pw | = O (mml)
which completes the proof
of Proposition See Appendix A.2 for details.
A.2 Proof of Proposition T Error Analysis for the Protocol Appendix A.1
We first show the following preliminary emror bound concerning the rough estimate.
Lemma 4. If pw (w) 2 for some W, then IP
(w(W)
2 0 Pwy
(w))
Proof. By 8 and pw (w) 2 x we have
(ww) plr (w))) (wmPp)
=0
(mml
(9)
By the Markov inequality, obtain that
(wr(w)
(w)(w)) (w) 2 2 = ply (w) Pw (w)
1
$
<P 1ow (w) - pw (w)) 2
2 pw((w)
2
2 E pty (w) pw pw(w)) (w)
Pw (w)p
Then by g and the assumption that ml 1000k log(mn) log n, we complete the proof.
L
Now return to the proof of Proposition
Note that suffices to show that for each W,
k
p-1
PW (w))
E (w)) p (w)) = [=
Pw Pw (w))
(10)
(mnl)
mnl
(mn)
then taking the summation and using mid 2 k2 can complete the proof.
'One may worry that the estimate ply may not be normalized. But it does not affect the subsequent steps of using Pty for directing the budget allocation. This can be seen by the following analysis. By the proof of Theorem A.2
for constant C Pllló 2 CJ < Σn P((pw(w) pw (w)] 2 zir. which is sufficiently small if ml >> log n log(mn). In the case that ply is used as a ratio for budget allocation, we can simply divide it by the constant and then the emor analysis is still true. Hence, for simplicity we assume that Ply is normalized and do not point out this minor
14] and
(C (C- 1)
(w(
log n-nn-ee
obstacle in similar cases where piv is generated by the protocol in Lemma
21

---

By Lemma
we have
E [lww(w) Pwr (w)P
PW (w()) =0 =0(1) (n + 1))
57
k
p-1
pw (w) mrn
LE
+
pw (w) +
mind
mend
suffices to bound the first term. Define the event Fu = (w k, we have
2 2
Then by Lemma 4 and
(w)
(w (pw((()))) + 1))
E
pw(w)) (w)
$
PW (w))
=5
F
+
1
(m (w0) + +1²
mnl (w) + 1t)
kpw(w) mnl
1
<P
[P]]
mnl
1
$
-O
kpw $
=1 (2)
mml|
+
(w)22))
mnd
+0
mnl
4
=0
mnl
which completes the proof.
The Protocol for Cases (Tb), (Tc) and (5c) and Its Analysis
In this section, we design successive refinement protocol with adaptive budget allocation that achieves the optimal rates for cases (lb), (Ic) and (5c.. Similar to the discussion in Remark 7 it suffices to show the following proposition for p 2
there exists an interactive protocol SSR(m, n. k,1,p) such that for any Pw E Aw, the protocol oulputs an estimate pw satisfying,
Proposition Let p 2. Then for the problem Section 2
1. k < m(1 A k)) > log(mn) log then Billpw Pw [|]] = =0
(mn) &
if n S (2' 1) n, 12 2 and m(1 A n) > 2000nlog(mm) log n, then E[ Pw ||]]
log( +1) (mm)) 5
if -1) 1). n, 2 and mll A An) 4000n log(mn) ) log n, then Billpw Pw
2
Remark 9. Although the bound in Proposition 2 not always tight for > 2, it is indeed tight (up to logarithmic factors) for p = and can imply tight bound for 1 S p 2. The advantage of using the successive refinement protocol for < 2 is that the protocol can apply for a lager parameter regime. In comparison,
protocol Appendix D can be used for 1 S p and k >
requires that log Hence fails handle the case 2 for log( + 1) < log k and the case
in Proposition 2
We design the successive refinement protocol SSR(m, n, 1.) in Proposition 2 inductively, which turns out to successive refinement procedure. The protocol each case Proposition on that for the preceding case. The goal is to estimate distribution Pw E Aw. If the communication budget for each encoder too tight, then it difficult describe the entries of pw- Instead, we can perform divide-and-conee technique.
22

---

At each step, choose some to and construct division W = W with [W,] - 2 1. and = - Then each encoder is assigned several W, and ordered to describe the conditional distribution Ps E Δw, for the assigned We, where pa(w) _ p(w(W,). Based on the message. estimate of ps- Let the block distribution be pa, where pr(())
the decoder constructs Ps Ewew, p(w). As long as an estimate PB of the distribution ps can be obtained, we can obtain an estimate Pw (w(w) (w) = pn (ss (w) for w E W.
The above procedure can be repeated for the estimation of pn. Note that pn E [1: always has lower dimension than the dimension for pw,, the inductive procedure will finally terminate. Hence the estimate pa can be obtained, well pw-
The error of each one-step procedure is bounded by the following lemma, proved in Appendix B.3 Lemma 5. For p 2 2, we have
PW
PW 2
BllipB PB +
(lpp(s) llp. - Pp
(11)
Remark 10. For the TV distance (p 1), is easy to obtain that (ef. Lemma 3.1 in 14)
E Bl - Pw [[v]] < B| - pallrvl+ + Σ pn(s) - P=llTv].
(12)
Now consider the subroutine for estimating all the Pa. 1..... t given an estimate P3 for pg- By (II). it intuitive that the budgets for estimating each p. should be based on the multiplicative weight (s(s) (s))) of the estimation error pp. 1D:-pslle It turns out that the number of encoders for estimating ps can be proportional to Pn (s). Since the quantity (s) can be obtained by the decoder, the allocation of encoders can be based on it by interaction between the decoder and encoders. Such
an allocation plan in contrast the estimation problem under the TV loss discussed in Appendix C The difference is characterized by the error bound (12). where the weight is simply PB (s) and uniform budget allocation plan among all the p.. s ...,? is optimal.
The detailed subroutine is presented in the following subsection.
B.1 Successive Refinement Subroutines
Suppose that there are m' encoders and each of them observes i.i.d. samples W Fix lo S l and let ng = 1 A n. Then we design the successive refinement subroutine SSRSub(m' n, k. I, lo. p) as follows. It receives an estimate Pa of the block distribution ps of dimension f,, and outputs an estimate Pw of the original distribution pw-
Allocating frames to blocks Divide the l-bit message for each encoder into multiple lo-bit frames. Then each encoder holds at least no such frames and all encoders hold m' no frames in total. Each bit frame is sufficient to transmit sample, given that the sample is from fixed block of size
more than 2 - 1. Simply let
r(s) = ()(s).
(13)
Then r is a block distribution. And we allocate all m''n, m' framess held by m' encoders to encoding samples in diffeernnt W,, such that
(i) for each block s, N, = m' mn)))r()] frames are allocated:
(ii) for each encoder, there are most [s)](s)] frames allocated transmitting samples in W..
Encoding For each block s, each encoder divides all its n samples into [nor(s)] parts, and each part has [ samples (ignoring the remaining [<or[(s]] [ D). Each frame that is held by the encoder and allocated for transmitting samples in block is then mapped to one of these parts injectively. If in that part, there are samples falling into the block 8, then the encoder uses the corresponding frame to encode the first such sample. If not, the frame is encoded as 0.
23

---

Decoding and estimating For each block s, the decoder extracts frames in messages which are allocated to the block. For b = L,.., s. let Wg = 0 if the b-th such frame is 0 and let W be the sample encoded by the frame if is not O. The decoder computes N₂ =>m 1l wig Then computes
Ebm 1 W w N
(.(w)
(14)
N2 * and it computes pa(w) [w.] otherwise. Finally, for each s 1,.... and each Ws, it computes (w) = (s)))
The complete successive refinement subroutine SSRSub(m', n, k. I, 1, p) is summarized in Algo- rithm The estimation error induced by the subroutine is described the following lemma, proved in Appendix B.4
Lemma 6. For p 2 2, we have
(Iv n
(
(4r 2)
((pp(())pp((){)))) psl
- =0 -
(15)
2
B.2 Construction of the Complete Protocol SSR
By inductively using the subroutine, the complete protocol SSR(m, n, k, 1,p) for the three cases in Proposition 2 can be constructed as follows. Then the error bounds are derived accordingly
from Lemmas and in Appendix B.5 and B.6
B.2.1 The Protocol for Case 1
Invoke the first step the protocol IR(m, n, k, A k. Appendix A and then output the rough estimate pl. By the analysis in Remark & we have pw Pw [[]] O
mal
(mn)
B.2.2 The Protocol for Case 2
Let to [log( & + +)7 S and divide the W into
[--_]] E [S.n]
n2] blocks.
Let the first !I encoders and the decoder estimate the reduced distribution of dimension t S By the assumptions mll An) > 2000n log(mn) log n, they can invoke the protocol SSR( ( n, 1,1,)) in Appendix B.2.1
Then let the second m encoders and the decoder invoke the subroutine SSRSub( m. n, n,k lo. and 2
compute the estimate of the original distribution pw-
B.2.3 The Protocol for Case
It suffices to design the protocol for 2 8k and then compute the integer follows. Let k k. then iteratively compute hu+1
n2t since the upper bound is vacuous otherwise. Let ln = I
[ 2--1 for
I..., a. Let a be the minimal number satisfying Ka+11 S (2 - 1), then Ka+1 >
Let the first encoders invoke the protocol SSR(") Th n, k. I.) defined in Appendix B.2.2 to estimate the last reduced block distribution of dimension ka+1-
Divide the second Z encoders into a parts, such that the u-th part has m,,
encoders. By
2 logí m
the choice of a, have
Then we have 2 < 2
for 1 2
112 1)
Hence 2 g 2 1. For u = 1,..., the decoder iteratively invokes SSRSub n. kn, 1, lo, with encoders the w-th part successively. Then compute the estimate of the original distribution Pw.
24

---

Algorithm 1 Successive Refinement Subroutine SSRSub(m' n. k, l.
Input: Parameters (m', n, k; lo: p), an estimate p of the block distribution pa (at all encoder and decoder sides).
Output: An estimate Pw the original distribution pw-
Allocating frames to blocks:
1: 74 - _ A n.
2: Divide each (-bit message into no frames of length lo-
3: for : do
4: r(s) - Pg(s).
5: N₂ - [s]]
6: Allocate N₂ frames to Ws, s.t. at most [nor(s)] frames are at the same encoder side.
7: end for
Encoding at each encoder side:
8: for 1: do
9: Divide all samples into [nor(S)] parts, each with [nor(s)] samples.
10: Find frames allocated to W..
for
[s)] do
12:
if all such frames have been encoded then
13:
Break.
14:
else if 3W; E W, for some W; in the b-th part then The b-th frame +- the first such W.- else
15:
16:
17: The b-th frame +-
18: end if
19: end for
20: end for
Decoding and estimating at the decoder side:
21: for 1: do
22: Extract all N, frames allocated to W.
23: for b I,....N, N2 do
24:
if the b-th frame is 0 then
W +
26:
else
27:
W. +- the b-th frame.
28:
end if
end for
30:
N M w
31:
for W, do
32:
if N # 0 then
(www)= - ENe Lug-
33:
N
34:
else
35:
(ww) +- W.T
36:
end if
37:
pw (wr) Pr (w).
38:
end for
end for
40:
return pw.
B.3 Proof of Lemma 5
Note that
(pn(s)p,(w) (w)
<(pr(s)p<(w) (w))) (pe(s)ps(w) (w)))
25

---

(w=(2)²² + (p - 2p P. (2o)).
Then by the Hölder's incquality, we have
(sn(s)pa((e (w) - (n())fp(w))
<24 -1
(p=(w)² + ) - (pn(s)) + pn) (n(s) fall (pa(w) Da (1o))))
1
<2--1
2 (Pa(w) + (w)) (PB(s) - )B(s)) (pppsss)ppp(S) -
where the last inequality is since 2 and ps (W) [0. 1l. Take the summation, and then have
ppw pw $20-1 Σ (pa(s)-
DD(s))' pp(s) p=ll")
Then (11 is obtained by taking the expectation. We complete the proof.
B.4 Proof of Lemma 6
m (or(s) = m' m'nopn(s) S 4, since |p.. - Pol S 2, then
(n(
pB(S) lpp -P-ll s 2pp (s) 2p s 2
m/no
Otherwise, have m' ms)) m'nopB(s) > hence N, θ (m' (orm)or(s)) O (m (mm'nop(( (8)). Given pp. then We for 1,... N₂ i.i.d. random variables with
Is PPiW + 0/ppl
(1 pB(s)) Tmor(o)
(16)
= (s(()
^1 θ
(B(()
n1)
[nor(s)]
(nODB(s)
In this case, establish the bound shown in the following lemma.
Lemma 7. E[pp(s) ( (p)))) llp. Pellippa] < CE
(
((n(s) m'n
V m/nno m no
pa(a)
PB
for some
C>0 0.
Proof. By the Chernoff bound, we have
Noqs 2
Nog.
P
N
PB
- exp
(17)
8
And conditional on the event { + 0). the distribution of W is p.. Hence for each w W., is folklore that (cf. Theorem 4 in 22 or Rosenthal's inequality (23).
Bllp. (aww))lN pal =o
(( (Pa(w))
$
(w(w)
+
N
N
Take the summation, since p 2 2 and (w( E [0. 1] we have
lp. - P.l No Nog= DB =
E
N
Since Ipp. 22l12 < 2, we have
Noga
Blllp p=11=ppm 5 2exp
(-8
+ +
0
8
2
qr
N
26

---

Since no S n, we have [noPs(s)] I n and [e] 2 1. Hence there exists some C' >> 0, such that
(lpB(s)$pBle)
Ps Pelpppa)
pB(S) m m'noDBl (8)
3
<CB
PB
(B())
=CE
nopplts) A A1) 11) PB
m'no (pa(s)
PB(s)
=CE
PB
m'no
mnno
[ToDe(")]
nopn(s) V1
(s())
CE
PB
mnnno
m'no
completing the proof.
In both cases, we can take the expectation and obtain that
(px(s) m'n
(s())
4
ElpB(s) & (s()) lpp P*l S C'E
C'E
m'nno
mr'' na
for some C' >0. O. Finally, take the and note that p 2 2, then
(s) E (s()) 11 - Ps 1Pl
ps(s)
v (B(s) $
<
v
m'n
m'nno
m' 'no
1=1
V
m'no
(m''nno)
t 1V
(41 V 2)
n
m
which completes the proof.
B.5 Proof of Proposition| 2 Analysis of The Protocol for Case 2
By the case I
the estimation error for the reduced block distribution is bounded by
C3
mnl
(mn)
for some C3 0.
By Lemma 6 the estimation error for the conditional distribution induced by the invoking of the subroutine SSRSub(") m n, k, 1, lu, p) bounded by
(4 4) $
2 (2 +
21o ml
2
O₂
C2
=CA
(mn)
2
llog( & + 1) n ml
2 (mn)
SC₁
V
27

---

for some C2 > 0.
Then by Lemma the total error is bounded by
(
&
log( &
1)
24
2
C4 {
+
+C3
V
ml
(mn)
mil
(mn)²
(( [log
f + 1)
=0
ml
(mn)
B.6 Proof of Proposition] 2 Analysis of The Protocol for Case 3
By the analysis in Appendix B.2.2 the estimation error for the reduced block distribution induced by the invocation of SSR( 2 n. kot p) is bounded by
log
Rall
Cs m
C5:
ml
(mn)
for some C3 0.
We have ku+1 2 ka+1 > and 1o conditional distribution induced by the u-th invocation of the subroutine SSRSub n, ky lo. is bounded by
7 = 1 >
Then by Lemma the estimation error for the
Na+1
2
Cs
I Co
Cb
(18)
man
204z
m
(21-1)umm
for some Ce 0. Then by Lemma
and
4. the total error is bounded by
Cs C
2 2
20(x-1) 1)
+
2u(p-1) 1)
m E
(21-1)um
2(p-1)
k
Cs
k 2'm
<2
23pCo
n22 - 1)
m
#
k
2'm
C The Non-interactive Protocol for the TV Loss and Its Analysis
Consider the estimation problem under the TV loss, i.e. p= In this section, we show that uniform budget allocation plan is sufficient in this case, thanks to the error bound (12). The advantage of the uniform allocation plan obvious, since there no need for the decoder send any message
to the encoders. Hence non-interactive protocol is immediate induced, only by changing [3 to
r(s)
(19)
in the successive refinement subroutine SSRSub(m', n, k, 4, 1) in Appendix B.I
For simplicity, we slightly abuse the notations SSRSub(m's n, k, 1, 1) and SSR(m, n, k, 1) to still denote the resulting non-interactive protocols. The non-interactive successive refinement subroutine SSRSub(m' k. lo, 1) is presented in Algorithm 2 for completeness, where differences with Algorithm [ are underlined.
To show Theorem 2 it remains to show the error bound in the following proposition.
Proposition 3. For any Pw E Aw, the non-interactive protocol SSR(m, n, k. 1, 1) outputs an estimate Pw satisfying.
28

---

Algorithm 2 Non-Interactive Successive Refinement Subroutine SSRSub(m' n, k, k, (,
Input:
Parameters (m/' n, ki lo), an estimate p of the block distribution pa (only the decoder side).
Output: An estimate Pw the original distribution pw- Allocating frames to blocks:
1: 74 f _ A An.
2: Divide each (-bit message into no frames of length lo-
3: for 1: do
4: r(s) - 1/t.
5: N₂ + mm [s)]
6: Allocate N₂ frames Ws, s.t. most [ngr(s)] frames are the same encoder side.
7: end for
Proceed as that in Algorithm !
(v
1. ifk S n, ml1 k)
1000k log log n. then E[llpw pw [1]] O
R. mart
&
van
if n < k (2)
1)
n, 12 2 and mll A A) > 2000n log m log n, then [E[]l
pw 11]]
h logl +11 ml
0
V
if
> (2) 1) n, 2 and mll A n)
4000n log m logn, n, then Billpw - pwl
V
2 mn
C.1 Error Analysis of the Subroutine for p p=
First, the estimation error induced by the subroutine SSRSub(m' n, k, 1, 1) is described in the following lemma.
Lemma 8. We have
Σ E(pn(s)lpp - pollrv]=00. (V
1 n2
( 10
-
lv
(20)
Proof. If m'nor(s) m'ng < 4, since 1 -PsllTV- 2, then
(B(s)
PB pB(s) )
PB())lld. Pollrv < (pp(s) S </
< <41
/
m'no
m m'no
Otherwise, we have m m'ngr(s)) m 4, hence N₂ θ (m'nor(s)) O
(m'no
Then W for
u 1, N₂ are i.i.d. random variables with
gs e PIW # 0ppn] θ (pn(s) [oo
A1)= = (pp(s))
[t/ A1).
(21)
Then we can establish the following lemma.
Lemma 9. E(pp(s))lp. pall s CE
V
pn(e)k pa(e)k
pa(s)*k my no
for some C
m' mo mang
Proof. By the Chernoff bound, we have
Noq.
Noge
N
>
DB
S
exp
(22)
2
8
29

---

And conditional on the event {W * 0}. the distribution of W is By the Cauchy-Schward inequality and Ps ps(w) [0. 1].
E lp: Poll N'
No: 2
Nag.
S |
E
110-
-Pall
No
N
0
(v
W
2
2
Nog.
Since lip- psll2 s 2, we have
No4 8
W Naqs
(V
[.&l Noqs
Bllp: pal121pal 2 exp
+0
0
Since no S we have
S and
1. Hence there exists some C >
0, such that
Too/E
(
E
Elpb(s)]pp. p. PsllTv] S CE
m'noo 9s
PB())2k
=CE
m' mo PB (B(()] [mo/t]] A1
PB(8)k:
(s(
=CE
m'' no [no/cc]
m'no
(B(s) v (B(s) m'nt
(B())*k m/no
=CE
V
m'nno
completing the proof.
In both cases, we can take the expectation and obtain that
PB(s) ment
v pB(s)k
pB(s)2k vre' m''no
Elpa(s)ll -psl/vl & C'E
m''mo
for some C' > 0. Finally, take the and use the Sauchy-Schwarz inequality, then
E(pe(s)llp. p&l pal|Tvl
PB(s)K m'nt
Pε(s)K m'nno
pB(s)2k m no
50"
E
k
kt m'nmo
m'no
ke
t
(4
m'
which completes the proof of Proposition
3
C.2 Error Analysis of the Non-Interactive Protocol We complete the proof of Proposition B in this subsection.
30

---

C.2.1 Error Analysis for the Base Case
Since the protocol for is the same as that for 2, then by the Cauchy-Schwarz inequality and the analysis in Appendix we have
E pw - pwwllvl & V /KEllow - pw
k2
v
mnl
mn
C.2.2 Error Analysis for Case
By the analysis in Appendix C.2.1 the estimation error for the reduced block distribution is bounded by
f2 mnn
t mm
C3
for some C3 > 0.
By Lemma 8 the estimation for the conditional distribution induced by the invoking of the subroutine SSRSub( 2
m
n, k,,, lo, 1) is bounded by
2k
7
(V
21gk ml
2k
C4
Ci
=Cs
m 2
m
yn
4k log(
& + 1)
2k
SCs
V
ml
mn
for some C2 > 0.
Then by 112 the total error is bounded by
(V mad
4k log({
& + 1) ml.
k ma
Ca
+ C4
V
mr
log (
+ 1)
k mm
=0
ml
C.2.3 Error Analysis for Case
By the analysis in Appendix C.2.2, the estimation error for the reduced block distribution induced by the invocation of SSR( 7 n, hio 1, I, 1) is bounded by
kat1 log
kati
Ka+1 mn
ka+1 m
C3
V
S Cs
ml
for some C3 > 0.
We have Ku+1 2 Ka+1 and 4e 1 1. Then by Lemma conditional distribution induced by the w-th invocation of the subroutine SSRSub(m n, kig L, los 1) bounded by
the estimation error for the
kuti tn
2u k
2a+222
Co
S
Cop
(23)
m
m 20T2 n
(21-1)umn
for some Cs 0.
Then by
12 and 1 2 4, the total error is bounded by
C5
hit1
+ Co
2u+222
Os
8Co
22
=0
(V
12 2
m
(2--1)amm
m
22m
31

---

D The Protocol for the Case (5b) and Its Analysis
In this section, we design a refinement protocol with sample compression that achieves the optimal rates for the case (5b), summarized in the following proposition.
Proposition& 4. Letp 2 2, k n, ml 2 1000n log(mm) log k and [log k| < S n.. Then for the
problem in Section 2 there exists an interactive protocol such that for any pw E Aw, the protocol
log 2
outputs estimate Pw satisfying [B]] pww Pw Pwlppl 1|pl O
(ml) nn
Note that the communication budget 1 > [log k] is sufficient to encode more than sample. A naive idea is to let each terminal transmit their i.idd samples directly, so that the decoder can infer the distribution based the samples.
To achieve higher accuracy, a subset W containing w with relatively larger pw pw(w) is identified and those Pw (w: needs to be refined. A sample compression technique projects each sample to the subset W", which makes the encoding of the samples efficient. The protocol designed in Appendix A is then used to refine the distribution W" We present the details follows.
D.1 The Refinement Protocol with Sample Compression
Transmit multiple samples Let no [log I Each of the first encoders divides its l-bit message into no frames, and each frame has [log k] bits. Then encode each of its first no samples by one of these no frames. Send the message to the decoder.
Receiving the message, the decoder can access M1 - mnn i..d. random samples (W) W Then for each W, let
M=1
MM 1
Pw Pw(w)
M
and output the estimate ply
Refinement with sample compression
Based on the estimate pw: the decoder computes
2 n
W E W: ply (w)
where it is immediate that [W'] S n - since ply is normalized. All the remaining informed of W
2m 3
encoders are
Let the second m Ply (w) is obtained by the decoder.
3 encoders and the decoder repeat the protocol in the first step, so that an estimate
Finally, consider the last 3 encoders. For the i-th encoder among them, it computes W h(W))) for 1,.... n. where (Wey)== its observed samples and
w. W 00 w $ W
h(w)
Let W h(W) and Pw be its distribution of dimension no more than n. Then each encoder holds i.i.d. samples (W7, ) and W ~ Pw Let these encoders and the decoder invoke the protocol IR 2. [W" + 1,1,p) defined in Appendix A (which is possible since [W"] + 1 S n and ml 2 1000((W") + 1) log(mn) n). The decoder can obtain the estimate piy for Pwr.
Finally, for each W, the decoder computes
(w),, piv (w),
w E W',
& W
and outputs the estimate p
32

---

D.2 Proof of Proposition 4 Error Analysis for the Protocol in Appendix D.1
easy analyze the enror for the rough estimate Ply. For each w E W, is folklore that for 2 1 (cf. Theorem 4 in (22) or Rosenthal's 's inequality (23)).
(( (PW((w)
Pw Pw(w)
(w](w)) pw Pw)
mnn
p22
(mma))-1)
(24)
Remark 11 (Necessity of the refinement method). For 1 S S 2, taking the summation and using the Hölder's Inequality imply that
1:1 $ (mmg)
=0 )
1- log k. (md)
E Plw
Pw [p S O
The bound is tight up to logarithm factors for S p S 2. However, for p > 2 we can only get the which is not tight. In contrast, the refined estimate pw achieve
total error bound O log & k (ml)
or
better upper bound and we show E|ll pi Pw pwlpl O
log in the following.
(ml) (mi))
in
To complete the proof of Proposition it suffices to show that Elllpw Pw I| =
(mno) n 5-1
We obtain the following preliminary results, characterizing the estimation errors for the first and the second step. The proof is derived from (24) and similar to the proof of Lemma for pw (w) A.
I pw (w)
=o -((man (w))
pw (we)
(25)
2
By 10 the proof Proposition
[ we have
pw(w) + pw(w)
E [pw (w) - pir (w) E W'
(menl)² ?
+
mmn
(mn)²
(26)
Note that
E|] B - Pw
Σ
(Iww(w) - pw (w)Pp) +
Σ
E (ww) - -i
w:Pw(w)) (w)
wwww (w)
>
4
suffices to bound the above terms separately.
pw (w) I n then by the error bounds (24) (applied to p.y) and
26 we have
E [pw (w) Pi [w)
E TEew (wewrlpw(w) Pwr (w) []] + IE [Lwew (w) Pw
<P W W (ww) pir (w) w E [Ipww(()) pir (w)lp)
Plw W
pw(w) + pw (w))=
+ +0 ((
[P (w)
pw
por (w) (mng )-
<0
(mmll
ml
(mm)
mnn
P(w E WI]
(w)
=0
(min))²
(mmn) 2n=
Take the summation and note that [W'1 < n, then
Plw E W
Pw (w)
E (w (w) 50
Σ
(mnl) &
(mno) 2
wipw (w)
uaPp (w)
<
=0
(mnl)
(mno) 2
(mmo) n (27)
33

---

pw pw(ww)
1. n.
then Plw W - IP ppr (w) _ pw(w) By (applied to piy (25 and (26).
we have
E Ipw (w) - Pw (w)l)
E wew (w((w) Pw (w) + E [www (ww))) - -Pr (w))
E [low (w) pw (1)) w E w"] Plw & wi E. [Iww(w) piv (w)))
1
p-1
pw (w))
00
pw pw(w) (w:)
(mnl) &
ml
(mm) $
(w(ww)
pw(w)
+0
(mnoPw((y)) (w))
mno
(mma)r-1
1
P-1
Pw [w)(w)
=0
Pw(w) +
(mmng)
ml
(mn)
where the last step is since pw(w) (w)) > and mno 2
ml alog
1000n.
Take the summation and note
that kw :w:::pwuuu (w) > 3 n, we have
Σ
[[w((w) - Pw (w)P
(opw(w))
1 1181
Pw (w))
50
+
(w(w)
(28)
(mmnn)) 4
ml
(m1)²
wspw (w)>
(mn)) in
where the last step is since of Proposition
Toog RT S nF. Combining 27 and 288
we complete the proof
E The Protocol for Cases
ld and (5d) and Its Analysis
In this section, we design refinement protocol with thresholding that achieves the optimal rates for cases (Id) and (5d). It suffices to prove the following proposition in this section. Proposition 5. For the problem in Section each of the following cases, there exists an interactive protocol such that for any pw Aw, the protocol outputs estimate pw satisfying
1. 1f1 Sp flog SIS S and ml k, then Elllpw Pw [p] O
log (mljp=T
1f P
2, [log S
S and ml n, then Bllløw Pw (mn)
log"
2r ((m)) 20
(ml))=1
To overcome the difficulty induced by the extremely tight total communication budget, huge "preys" and little "flies" among all Pw (w) be estimated should be classified and dealt with differently. The thresholding level is naturally mit since roughly ~ ml samples can be transmitted by the first step of the protocol in Appendix D.1 For those little "flies" pw (w) < it is better to overlooking them than trying to estimate them. The remaining budgets should be used for refining huge "preys" Pw (w) ž 7 whose number ml is limited, by generating another independent estimate. For > 2. sample compression strategies and the protocol Appendix A are applied to refine the estimate similar to the refinement step of the protocol in Appendix [.I] With the help of thresholding, the resulting estimation protocol can catch the rough landscape of the distribution Pw and achieve the optimal error rate under the communication constraints.
present the protocols for two cases respectively in the following subsections and detailed error analysis can be found in Appendices B.3 and E.4
34

---

E.1 Thresholding Methods for Case 1
Rough estimation Let no = 1 R] S n. Let the first z encoders and the decoder invoke
first step (namely the "transmit multiple sample" step) the protocol presented in Appendix D.I so that the decoder can obtain estimate PW-
Thresholding technique
Based that, the decoder computes
W = fwE
= W W pW (w)
2
ml
where it is immediate that [W1] I ml since Ply is normalized.
Let the second m encoders and the decoder repeat the first step of the protocol in Appendix D.1 so that an estimate Piy (w) is obtained by the decoder.
Then for each w E W, the decoder computes
(w) = Pw (w), w E W,
10, w $ W,,
and outputs the estimate pw-
E.2 Combining Thresholding Methods and Refinement for Case 2
Rough estimation
Let k 2000 [mg[ Tog then k' ml and ml 1000k log(mn) log n.
Let the first 12 encoders and the decoder invoke the protocol presented the first step of Appendix D.I Then the decoder can obtain an estimate pw-
The mixed thresholding and refinement technique
Based on that, the decoder computes
2 k }
W w W (w))
where it is immediate that [W'| K' since p/ is normalized. All the remaining zh encoders informed of W.
Then consider the second mi encoders. For the i-th encoder among them, it computes W/J h(W;) 2
for j 1,... n, where (Wr,)y= are observed samples and
h(w) = w. W 0. W"
Let W" = l(W)) and pwr be its distribution of dimension no more than n.. Then each encoder holds i..d. samples (W7, )j= and W Pwr. Let these encoders and the decoder invoke the protocol IR(2 n, [W'| + 1,(,p) defined in Appendix A (which is possible since [ + S k' and ml 1000([W"I 1) log(mn) log n). The decoder obtain the estimate p for Pwr. Then for each w W. computes
w E W" [ph,
(w)
0,
w $ W"
and outputs the estimate y
E.3 Error Analysis for the Protocol in Appendix E.1
suffices to show that Elipp PW [|]] = O (mmg) 3 (ml)
35

---

We first give the following preliminary results, characterizing the estimation error for the first step. The proof is derived from (4). similar to the proof of Lemma but simpler.
pw (w)
P
Pw (w)
(29)
2
(mmoaww (w))
Note that E
Pw PP v
Σ
E [lpw (w) - pw (w))²)
+
Σ
E [lpw (w)) - Pi (w)
w:w (w) mL
wwww (w)) ml
suffices to bound the two terms separately. If pw S ml then by 24
(applied to piy.)
E [[pw (m0) (w)P) =I [1 weww (w)) pir (w)) + E
+ w pw
<PI E W'] EE [lew (w) p'r (w)
(w))))
(w((w)
=0 Plw E w7
pw pw))
mno
pw pw((w) (w) (mal)p-1
=0 Plw w7.
m2nol
Take the summation and note that [V S ml, then
Pw (w)
Σ
E [lw (w) pi (w)l 00
Σ
Plw wi]
m22no
+
(ml))-I
w:pp (w)
w:pw (w)
B[[W]]]
-((mm))) (mno)² (ml)) 3
(ml)p-I) =0
<0
(m2nol)²
(30)
(w)) > mi. then Plw & Wi S pir (w) S (w(
By 24 (applied to piy) and
29 we
have
E [lpp (w) pw (w) po] =E 1 weww law (w) - ph (w) Il + E PW -ir (w)l Plw & Wi) pw (w))
< ||ww (w)
Pw (w:) mino
+ pw((w) o
(
00
(mmopw(ww)
Pw (w)
mnn
Taking the summation and noting that [[ (w(ww) have
All S ml, by the Hölder's inequality we
E (w) (w)) 50
Σ
Pw (w)
0
((min)) 2 (ml) - -
1 (mno))
mnn
w.pw (w)>
w:pw(ww] (w)>
(31)
Combining
30 and (1). we complete the proof.
E.4
Error Analysis for the Protocol in Appendix E.2
It remains to show that Ellli Pw 13 =
(mil))
W-F-T
( PPpT
We first give the following preliminary results, characterizing the estimation enror for the first step. The proof is derived from 24). similar to the proof of Lemma 4 (where p in Lemma is replaced by 2p). For Pw( (w) >
pl (w) < Pw (w)
(ml)²-1
5o
(32)
2
(mmo))2 228 (pw(w))p
36

---

By 10 in the proof of Proposition | we have
E [ww(w) (w) w = o
((m)))
k' mind
p-1
pw (w)
(mnd))
+
Pw (w)
(33)
(mn)
Note that
E|| PW Pw
Σ
E [lew (w) - Pw (w)PP] +
Σ
E [Pw (w) pw((w) P.]
www (w)S &
weww (w)
>g
It suffices to bound the two terms separately. If pw(w)) S 27. then by
33 (applied to Piy.). we have
[lew (w) - (w))')
= [1 wew (oeew/pww(() (w) Pwr (w])P) + E www
S w E WIE [[ww(w) (w)) w wI + pw(w))
k' p-1
pw(w)
(w)
Plw W'] <0
puo(vo)
0
(mnl)
mnl
(mn)
k/p-1
Plw E W"]
pw (w:
=0
(mnl)
k/-1
Take the summation and note that [W < W,, then
Plw E W Pw (10)
Σ
E [Ip)(w)) p (w))
50
(mand)
kpp-
wsp w (w) &
wePW (w)S +
(34)
EE [[([
50
(mnl) &
po--1
Fop-1
If Ppw (w)) > $. then P(w W/ < P (w)) < (w
By 32p and
33
we have
E (ww)(w) - pi (w)P]
=E wwew (pw(w)))))))))) pir [p] + E [mmgw: (1)
[lpw (w) pi (w) w E w + Pfw & W Pw (w))
1
W p-1
(w(w) Pw (w) (mn) 1
(ml)=-1
50
+ +0
Pw((w)p)
(mnl)
mnl
(mn])-11
k' p-1 mml
(w( + Pw (w(w)) (w) (mn)
=0
(mmy) 1p-1
where the last step is since mno = ml TTg < ml < n. Take the summation and note that Hw: pw(ww)
W' ml, we have
E (1) (w))p wwpw (w)
Σ
(ml)p-1
k' P-1
Pw (w)) Pw (w) (mn) &
(35)
(mng) 2p-
mnl
wipw (w)>
(ml)²
(mmg) Tp-1
(mn)
Combining 34 and 335 complete the proof.
37

---

F The Protocol for n1 = p, 2 2 and Its Analysis
In this section, we design a non-interactive protocol based on random hashing, which achieves the optimal rate for 1. Similar to the discussion in Remark 7 it suffices show the following proposition for p 2 2.
Proposition 6. Let p 2 2, n = and m2' 2 h.2 Then there exists non-interactive protocol
such that for any pw Aw, the protocol oulputs an estimate pw satisfying Bllpww Pw [1]]]
o
(m2))
m
F.1 Motivation of the Protocol
The most natural idea is to first invoke the simulation protocol in 18 to output M = O m2' from the distribution pw at the decoder side; then estimate pw using M samples by traditional central estimation method. It can achieve the optimal minimax rate k for 2, and hence the m2
(((e samples
for 1 p S However, for 2, using M i.i.d. samples estimate the optimal rate (m²))
underlying distribution under the ( loss only achieve rate of _ M
( which leaves
&: by Lemma The above naive protocol not optimal and (m22)* 4 show that the lower bound & is optimal.
gap with the lower bound
(m22)
The subtle difference that the minimax optimal rate without the communication constraint is
for p 2 (cf. Lemma 11 in contrast with the optimal rate k'- for $ S 2. The difference was M ignored by the proof of upper bound in some previous work [17], hence the optimal rate claimed therein is not true. Constructing the order-optimal protocol really deserves special care, which the main goal in the remaining part of this section.
The aforementioned difficulty in estimation under ( losses can be overcome, by using a random hash function to compress the sample first, and then constructing and rescaling the histogram to
obtain the estimate. No simulation step as in (18) needed. Moreover, it worth mentioning that
the resulting protocol is non-interactive. The idea is similar to the second estimation stage in (10) for estimating sparse distribution under communication constraints. Details of the protocol are presented in Appendix F.2 and the error analysis can be found in Appendix F3
The Non-interactive Protocol Based on Random Hashing for F.2
Note that it suffices to design the protocol for 2 < kr.
Encoding Let the i-th encoder generate a random hash function h4 W + by shared randomness (i.e. (e(w)))ew are independent and ((,,(w) = b] = 2 for each w E W and E {0, 1)'), so that the decoder can also generate ht. Observing its sample W,, the i-th encoder computes B; = h; (W,) and sends it to the decoder.
Decoding Upon receiving B,, the decoder then computes
2
E
1 (.
1
Pw (w(w)
(36)
2! 1
m
2
for each w E W and outputs pw-
F33 Proof of Proposition 6 Error Analysis for the Protocol in Appendix F2
We can analyze the error of the estimate pw as follows. Note that for each w E W and
1, 1,... m,
1 P(h,(w) B,] Pw (w(w) 2 (1 Pw (w(w)).
38

---

It is folklore that (cf. Theorem 4 in
[2] or Rosenthal's 's inequality 23
m -i=1
[ Flbi(w) 1il]
m
Plhz(w)= B1}
P(hi B1l
m
mp-1
(w(w)
V 2
(w V T
m
mp-1
Then by (36), we have
((
Pw (w)
[w) Pw (w)l]
22
mP-1
well. Note that m2 2 222 and 2 < 1 < implies that 2 2'. By taking the summation
all w E W, we complete the proof of Proposition 6
G Proof of Lower Bounds
In order prove Lemmas and lemmas.
we first reorganize the lower bounds into the following three
Lemma 10. For S S 2, we have
h 2 l log k m >
k I k, I
(mnl)
n, k,,,))
h1-8
< k K, >
ki
n log k.
loglog
1
mn2 > 122
(mm21)
For p 2 2, we have
k (mnl)
x)² (7)
n 2 log k, m
I kē
1
(m/ 1
(n/logm
n// log n
n log n
n < & log k, m
11
(ml) fin -1 -lloooog' (mn21)
mn2 > k22
11 For 2, then R(m, k. 2 (mn)
Lemma 11. For R(m, k. k, 2
(mn)
Lemma 12. 2ml < k, then R(m, n, k, [mip-TT
We show Lemmas 11 and 12 in Appendices G. and G.2 respectively. Then Lemma 10 is proved by exploiting the results for p
and details can be found in Appendix G.3
G.1 Proof of Lemmal
The results for < S are well-known 16 the -nformation-thhoretie methods.
hence we only give the proof for p 2 We use
39

---

G.1.1 Choose prior distribution and lower bound the minimax risk by the Bayes risk
We can assume that W = [1: k] without loss of generality. Let
1+E 1 1-E
Pw
0, 0,..... 2 2
0
(37)
1-c
1
Pw
0, .0,..... 0
2 2
Let Z ~ Bern( and define the prior distribution to be ply. Let P be an (m, (,,,n, -pootoool defined Section 2 then we have
sup PwEAw
Fll Pw
2 [E] [Rillw pw Ipl + Blllow pw
G.1.2
Convert the estimation problem into testing problem
Let
7 arg min [pir pW 1pp- =E(0,1}
Then we have
Ilw pwllp S11pW
Pw lpp + lpw -Pivll
2
<2 <2| p 1lp.
Hence we have
Blllew
pwv [
1
2 p
2F
(38)
1
ePIZ 21. 2
Since Wmm Bm a Markov chain, then by the Fano's 's inequality, we have
(Z; 2 (P12
(39)
where h(pp -p lpgog2 p (1 - p) log, (1 p) is the binary entropy function. If we can show that for suitably chosen e,
(m: 2'
(40)
then by 38 and 39
we have
Piž + 2 10'
thus
Blllph
Then we have 1, E..
40

---

G.1.3 Choose suitable parameter
By the Markov chain Z. Wm 8 and the data processing inequality, we have
T(Z; BT)) - T( Wmm)
Dymn
2 (piv (w (mm) + pwv((u (w
+ Dwm (pi((ummm)l (ww + per (w (w=m)))
(Dymn (ww(wm (w)n)) + Dyomn (pfv (er(wmm) (w" Mep (m)
mn
Dw (piv (w))lll
2
mnc
2c
log
1
2
1 -
mnE 2
1-ce
where the first inequality is due to the convexity of KL divergence and the second is by the fact that log(1 + x) S x. for x > By letting e (100mn) - & we obtain that R(m, n, n,l, r) ž (mn)
G.2 Proof Lemma
The case for ml < l is not hard, but it has not been fully explored in previous literature. First note that by the Hölder's s inequality, we have
liww PWlITV k'- blpww pwllp-
Hence have
R(m, n, k,,,p) 2 k2-PR(m, n, 1)P,
(41)
and the minimax lower bound for p 2 1 is easily implied by that for p 1. We have the following folklore lemma for p which can be proved by the Fano's method and the data processing inequality.
Lemma 13. 2ml < k. then we have R(m, k,1,1) 2 1.
Combining Lemma
13 and for any 2 2ml we have
1
R(m,n, n, k,p,,, 2 KP-1
Hence we further have
R(m, n. k,I,p) 2 R(m, n, 2md,1.p) 2 (ml)--I
G.3 Proof Lemma 10
For L, we have the following lemma in [4]
Lemma 14 [4]. Theorem 1.1 & 1.3). 1) For 2 k log k and m > (4) R(m, n, (om,n,k 2
mnd A
2) For S klook k and m (4)² R(m, n, k,,,1,
mi log
3) We always have R(m, n, k. 1,1,1)
mmn A 1.
With the help of (41). the following three bounds is derived from three cases in Lemmal 14 respectively.
41

---

Proof of the first bound For m 2 k log k and m >> (4)² and S k, we can obtain that m > { and
mnd 2 k2. Then by 1) in Lemma 14 and (41
k
R(m, n, k,k,p) = (mnl)
Proof of the second bound If ($) and I k. then ml mllogk 2 k. Then by 2) in Lemma 14 and 41 we have
k1-
R(m,n,k,l. = (ml k)$
Now let p 2 Since n I k log k we have & 2 logn We further have
1
R(m, k,k, 2 R(m, mn/lognl,4, t
(ml) in 3
log n
[n/ nogm] ) and < [m/ n]..
as long as >
Proof of the third bound If mm2 2 k2, then by 1) in Lemma 14 and
41
we have
k
k,m,nkk,,.p) 2 (mn22)
42


Reviews:
[{"review_id": "vStUWrI5vN", "reviewer": "Reviewer_XUHt", "summary": "The paper studies minimax rates for the problem of (discrete) distribution learning in the distributed setting where:\n- there are $m$ terminals;\n- each terminal has $n$ i.i.d. samples and uses at most $l$ bits to describe its samples;\n- the error in estimation is quantified using the $\\ell^p$ loss for $p \\geq 1$.\n\nA previous paper [13] studied a similar problem which was limited to the case $p = 1$ (i.e. total variation loss). As there, the schema of the protocols here is to get a rough estimate, followed by a refinement procedure. To make this schema work for general $p$ requires additional ideas, which is the main contribution of this paper.\n\nThe upper bounds on the minimax rates are given by Theorem 1 (for $1 \\leq p \\leq 2$) and Theorem 3 (for $p > 2$); the corresponding lower bounds are given by Lemma 1 and Lemma 2, respectively. \n\nTheorem 2 and Theorem 4 are devoted to special cases where the estimation protocol can be made non-interactive:\n- Theorem 2 gives a non-interactive protocol for the special case when $p = 1$. This is exactly the case considered in the previous work [13]. Here, the authors show that their protocol extends the range of parameters to which the guarantees apply.\n- Theorem 4 gives a non-interactive protocol for the case where $n = 1$ (i.e. each terminal has $1$ sample) and $p \\geq 2$. This protocol uses random hashing (and thus requires shared randomness). Further, the authors point out that the lower bounds for $p > 2$ from [16] that were claimed to be optimal are not so since the random hashing protocol achieves a performance that is strictly better.", "questions": "In Section 5, where a random hashing based non-interactive protocol is proposed in the case where every terminal has $1$ sample, the authors point out that the simulate and infer protocol (which requires no shared randomness) results in a suboptimal rate. \n- Could the authors give a intuitive explanation of why random hashing leads to optimal rates?\n- Do the authors believe that shared randomness is necessary to obtain this rate? In other words, do they think it is possible to get a lower bound for private-randomness protocols that shows a strictly worse rate than the one obtainable by shared randomness?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The overall story and the flow of the paper is clear. \n\nAs already mentioned in the summary, the main contribution of the paper is to show how to make the general idea of estimate-then-refine work for distributed distribution learning with general $\\ell^p$ loss. This comes at the cost of introducing interaction among the terminals: e.g., for adaptive budget allocation; for deciding the projection set for sample compression. Even so, I believe the results in the paper demonstrate that the gap in the literature of distributed estimation with $\\ell^p$ losses requires something more than just generalising the analysis of existing protocols.\n\nPresentation wise, I would have liked a more pseudo-code style description of the protocol in terms of basic primitives. I don't think it is possible to do that in the main body of the paper because of the page limit. But perhaps this can be done in the appendix?", "was_revised": true, "final_justification": "I missed the final justification box, so writing it now. I am happy with author's responses to me and the other reviewers. The main concern raised by most was about the explanations and the presentation which the authors have promised to rectify. I stand by my  original score of 5.", "rebuttal": "Thanks for your comprehensive review and positive assessment. We are going to improve our paper according to your suggestions in the following aspects.\n\n-   **I would have liked a more pseudo-code style description of the protocol in terms of basic primitives.**\n\nThanks for your suggestion. We are going to add more pseudo-code description in the technical appendix, in order to make the presentation of the estimation protocol more clear.\n\n-   **Could the authors give an intuitive explanation of why random hashing leads to optimal rates?**\n\nWe will add a remark to give the explanation. In the following, we try to present a rough answer to this question.\n\nIn our understanding, it is because random hashing implicitly adopts an optimal communication budget allocation strategy. Hence it can extract information that is most useful for estimating the underlying distribution, and ensure that the estimation errors for different entries are balanced to obtain the optimality under the $\\ell^p$ loss, either for $p \\leq 2$ or for $p>2$.\n\nAs we have discussed in Section 5 of our paper, the estimation error for each $p_W(w)$ is $(\\frac{p_W(w)}{M})^{\\frac{p}{2}}$ if $M$ raw samples are available at the decoder side. That is, relatively larger entries $p_W(w)$ are typically more difficult to estimate. Hence communication budgets should be invested more into estimating these entries, especially under $\\ell^p$ losses with $p>2$. In this case, the simulate-and-infer protocol uses too much communication budget to estimate the smaller entries, while fails to simulate enough samples for estimating the larger entries. Compared with the simulate-and-infer protocol, random hashing reduces estimation errors for the larger entries, despite increasing the error for the smaller entries. It turns out that random hashing obtains the optimal budget allocation, and hence achieves the optimal rate.\n\nTo make it more clear, for example let $p>2$, $p_W(w_1), p_W(w_2) \\asymp \\frac{1}{2}$ and other $p_W(w) = 0$. To have a basic understanding, we focus on the estimation error of $p_W(w_1)$ and $p_W(w_2)$. Note that $w_1, w_2$ are unknown. The simulate-and-infer protocol simulates only $\\frac{m2^l}{k}$ samples, hence the estimation error is $\\sim (\\frac{k}{m2^l})^{\\frac{p}{2}}$. In contrast, random hashing can generate $m$ compressed samples, and reduces the estimation error for $p_W(w_1), p_W(w_2)$ to $\\frac{1}{m^{\\frac{p}{2}}}$. Random hashing implicitly uses more communication budgets in estimating $p_W(w_1), p_W(w_2)$, achieving an equivalent sample size of $m$ that is larger than $\\frac{m2^l}{k}$. This roughly explains why random hashing obtains the optimal rates, while simulate-and-infer protocol fails to do so.\n\n-   **Do the authors believe that shared randomness is necessary to obtain this rate?**\n\nIt is a very interesting question that merits further investigation. We will try to answer it in the revised paper, and later works."}, {"review_id": "yFDJg4wLI8", "reviewer": "Reviewer_ec8n", "summary": "The paper considers discrete distribution estimation under l^p losses where each user holds multiple independent samples and provides order-wise characterization of the minimax convergence rate. Previous results have been limited to p=1,2 and often single sample per user. The paper characterizes the order-optimal convergence rate for a wide range of parameters that has remained open in the literature.", "questions": "Please see weaknesses for suggestions on how to improve the paper.\n\nQuestion: Since the scheme for p>2 builds on the pointwise estimation scheme in [10], I wonder if the results in this paper can be further developed to achieve point-wise optimal estimation at least for p>2 but ideally in all regimes.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper addresses the distributed discrete distribution estimation problem across a wide range of parameter settings by developing and refining achievability schemes tailored to each subregime. The problem is practically motivated, and the schemes presented are non-trivial and sufficiently novel, despite building on prior work—for instance, [13] in the regime 1<p<2 and [10] for p>2. The paper aims to handle the general case where the rate depends on five parameters, which introduces significant complexity. I appreciated the attempts to distill high-level insights in the introduction and Section 6. For example, the intuition that block-based refinement schemes are needed when 1<p<2, while individual-entry refinements are needed for  p>2 is compelling. This aligns with the observation that estimation errors for larger probabilities become more significant as p increases. Further efforts to distill high-level insights would strengthen the paper.\n\nWeaknesses:\n\nSince the paper tackles the problem in full generality, the communication rate ends up depending on five parameters. As a result, it’s easy for the reader to get lost in the multitude of scaling laws across various parameter regimes. This makes the paper feel somewhat dry at times, especially when the presentation leans heavily on technical detail without sufficient guiding intuition or narrative. It would be helpful to provide more intuition about why the five regimes arise in the theorems, what each one represents, how the optimal strategies differ across them, and whether these distinctions are fundamental or largely technical. In particular, some high-level takeaways on how optimal schemes vary with respect to parameters such as p<2 vs. p>2, small n vs. large  n, or tight vs. loose communication constraints would add clarity and insight.\n\nAdditionally, the writing could benefit from further revision. Some sentences are awkwardly phrased, for instance: \"The same as Theorem 2, the non-iteractive protocol in [13] is constructed for the estimation problem under the TV loss.\" A thorough proofreading is needed to enhance the clarity  of the presentation.", "was_revised": true, "final_justification": "I am satisfied with authors' response. I think the contributions of the paper and the generality of the results warrant acceptance. I am updating my score accordingly.", "rebuttal": "Thanks for your careful reading and detailed suggestions. Here are our point-to-point responses to your concerns.\n\n## Responses to the weaknesses:\n\n-   **It would be helpful to provide more intuition about why the five regimes arise in the theorems, what each one represents, how the optimal strategies differ across them, and whether these distinctions are fundamental or largely technical. ...**\n\nThanks for your suggestion. As you say, since our paper tackles the problem in full generality, it is difficult to explain distinctions of all the regimes and their corresponding optimal protocols. We believe all the regimes discussed in the theorems are fundamental, as shown by Equations (2), (6) and Table 1. We gave some explanations in the proof sketch of Theorems 1 and 3. In light of your suggestions, we will further clarify the intuition of different protocols by revising our paper in the following. \n\n1.  Adding a few remarks immediately after the proof sketch of Theorems 1 and 3, in order to give more high-level takeaways on how and why optimal schemes vary with respect to parameters.\n\n2.  Adding and expanding detailed comparisons between protocols in different parameter regimes, especially in the corresponding sections in the technical appendix.\n\n-   **Additionally, the writing could benefit from further revision.**\n\nWe are thankful for your advice and will thoroughly revise our paper.\n\n## Responses to the question:\n\n-   **Since the scheme for** $p>2$ **builds on the pointwise estimation scheme in [10], I wonder if the results in this paper can be further developed to achieve point-wise optimal estimation at least for p\\>2 but ideally in all regimes.**\n\nThanks for your question, which indicates a good direction for further works. A brief discussion of the pointwise estimation problem (as well as the related work [10]) will be added in Section 7 as a potential new direction.\n\nWe personally believe it is very likely to further design the point-wise optimal (up to logarithmic factors) estimation protocol for $n>1$ (at least for some parameter regimes), similar to that discussed in [10] for $n = 1$ and $1 \\leq p \\leq 2$. Techniques in [10] are useful for further extending the estimation methods in this work to achieve the point-wise optimality. Specifically, the protocol in Section 4 for $p>2$ is relatively easier to extend, while that in Section 3 for $1 \\leq p \\leq 2$ is more difficult. The idiom says, \"the devil is in the details\". We think that at least very careful theoretical analysis, and possibly some new techniques are still needed to fully answer this question."}, {"review_id": "x4VOLAh7nv", "reviewer": "Reviewer_qrGV", "summary": "The authors consider the problem of interactive communication constrained discrete distribution estimation under \\ell^p loss, and they obtain minimax rates for most parameter regimes (some of these regimes were not considered in previous works). In this setup there are m  distributed encoders, each observing n i.i.d. samples from the distribution and the message generated by the previous encoder, and each transmits an L-bit message to the central decoder (observed by all subsequent encoders as well). The authors upper bound approach is to start with a rough estimate which is then being successively refined and compressed, where the refinement method depends on the specific parameter regime. The lower bounds uses a standard reduction argument to a testing problem.", "questions": "The lower bound uses a reduction to a binary hypothesis testing, which is a very crude reduction when dealing with distribution estimation. Yet, surprisingly, this allows you to attain a tight lower bound, up to logarithmic factors. Can you elaborate on why this is happening?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: The paper addresses an intersting and timely distributed interactive distribution estimation, and it contributes to the literature by formulating minimax rates for a large regimes of parameters and identifying interesting trade-offs and elbow effects.\nWeaknesses: \nPersonally, I find the paper difficult to evaluate due to some of the condensed explanations compounded with some typos, which are mainly prevalent in the appendix section. For example, in A.1, it is not stated how the refined estimate \\hat{p}_W^2 is generated. In the subsequent algorithm of B.1, it is not stated how r(s)=\\hat{p}_B(s) is estimated. There are some typos, such as the upper bound of remark 5 should be \\ell_2 norm instead of \\ell_p, and the bottom of p.37 should be P(\\hat{Z}\\neq Z)\\geq 1/10. Also, in eq. (14) the indicator function should be equal to w rather that t. \nAnother concern I have is the significance of some of the results. While the trade-offs presented in the paper are novel, the proof techniques are relatively straightforward. The upper bounds are based on refining a crude estimate, where the refinement is tailored to the particular parameter range considered, and the lower bound is achieved via reduction to binary testing. I would like to see the authors elaborate on their lower bounds as it is surprising these crude reductions are tight.", "was_revised": true, "final_justification": "The authors have agreed to address my comments in the revision, and as I don't currently find any problem with their main results, I am increasing my final score.", "rebuttal": "Thanks for your careful reading and detailed comments. Here we give the point-to-point responses, in order to address your concerns.\n\n## Responses to the weaknesses and Questions:\n\n-   **Another concern I have is the significance of some of the results. While the trade-offs presented in the paper are novel, the proof techniques are relatively straightforward. The upper bounds are based on refining a crude estimate, where the refinement is tailored to the particular parameter range considered, and the lower bound is achieved via reduction to binary testing.**\n\nWe want to emphasize more about the technical contributions of our work here. Most of the technical difficulties lie in the proof of the upper bound, which is summarized here. We also derive compatible lower bounds for most parameter regimes. Technical contributions in the proof of lower bounds are given in the response to the next comment.\n\nFirst, introduction of refinement methods to the problem here constitutes a substantial improvement. The previous protocol for the $\\ell^1$ loss does not apply to $\\ell^p$ losses, since its optimality depends heavily on several special properties of the $\\ell^1$ loss. Even for the $\\ell^2$ loss, how to design an optimal protocol remains unclear. We find that the difficulty lies in the communication budget allocation strategy, where communication budgets should be invested based on the distribution to be estimated. In order to overcome the difficulty, we introduce refinement method in designing the protocols to achieve the optimal rates. Understanding the methods is relatively easy, but coming up with it is not trivial.\n\nSecond, how to make this method work for different parameter regimes requires additional ideas. Many other techniques such as successive refinement, sample compression, thresholding and random hashing are also exploited to solve the problem here, neither of which are straightforward. Showing the optimality of the induced protocol also requires solid error analysis. \n\nFinally, the estimation techniques proposed in this paper have a wide potential use in many other problems, such as the problem with privacy constraints, the pointwise estimation problem and other estimation setting with similar structural assumptions on the objects to be estimated.\n\n-   **I would like to see the authors elaborate on their lower bounds as it is surprising these crude reductions are tight. The lower bound uses a reduction to a binary hypothesis testing, which is a very crude reduction when dealing with distribution estimation. Yet, surprisingly, this allows you to attain a tight lower bound, up to logarithmic factors. Can you elaborate on why this is happening?**\n\nThanks for your comment. We want to clarify here that the crude reduction to a binary hypothesis testing is one of the key ideas, but it does not yield the optimal rates on its own. In Section G, the overall proof of lower bounds is decomposed into Lemmas 10-12, among which two major techniques are exploited.\n\nFirst, in the proof of Lemmas 10 and 12, lower bounds under the $\\ell^p$ loss are derived from that under the $\\ell^1$ loss. Most of lower bounds under the $\\ell^1$ loss are the contributions of the previous work [13]. Typically, the proof in [13] uses a reduction to a hypothesis testing problem of roughly $2^{\\frac{k}{2}}$ hypotheses. A large portion of difficulty in the lower bound proof has been overcome by [13]. Based on these bounds under the $\\ell^1$ loss, we derive most of the bounds under the $\\ell^p$ loss using Holder Inequality. Moreover, for some regimes such as that in Lemma 12, additional algebraic tricks are exploited to strengthen the bounds, so that tight bounds are obtained.\n\nHowever, the derived bounds are still not tight for the case $p>2$, where the second technique is introduced to resolve the difficulty. In this work, one of the major finding is that the optimal bounds are different for $p \\leq 2$ and $p>2$. For $p>2$, the centralized bound without the communication constraints in Lemma 11 is little-known but easy to show. It can be achieved by the crude reduction to a binary hypothesis testing. From a high-level perspective, this reduction to a binary hypothesis testing, combined with the reduction to multiple hypotheses testing in the proof in [13], completes the proof of lower bounds. This is why we present the proof of Lemma 11 separately and emphasize its main technique. These efforts improve the bounds derived by the first technique, so that the overall lower bound is tight.\n\nTo further address your concern, we will expand the proof sketch of Lemma 1 and 2 by adding more detailed explanations.\n \n-   **Personally, I find the paper difficult to evaluate due to some of the condensed explanations compounded with some typos, which are mainly prevalent in the appendix section.**\n\nThanks for your careful reading. Since our paper tackles the problem mathematically, we have to present these technically difficult proofs in the appendix. We will revise our paper in light of your suggestions to improve readability of the appendix. Specifically, we appreciate you indicating the typos to us and will correct them in the revised paper. However, for the first two points, besides adding more details in our paper, here we want to clarify that they do not affect the correctness of the main proofs. Our detailed responses to these points and typos are as follows.\n\n-   **In A.1, it is not stated how the refined estimate** $\\hat{p}_W^2$ **is generated.**\n\nAs stated in the second paragraph of Section A.1, we let $m(w)$ encoders invoke the one-bit protocol in Lemma 3 and each of them sends one bit for estimating $p_W(w)$. Upon receiving these bits, the decoder can output an estimate $\\hat{p}_W^2(w)$ of $p_W(w)$ following the protocol. In Lemma 3, we introduced the one-bit protocol in [13] for the distributed estimation of the mean of a binary distribution. Following the protocol, each encoder sends one bit to the decoder, and then the decoder can output an estimate of the mean of the binary distribution. Here we apply the protocol to the estimation of each $p_W(w)$. The detailed procedure for generating $\\hat{p}_W^2$ has been defined in [13]. In this work, we do not dive into details of the one-bit protocol in [13], but only exploit the error bound.\n\nWe will revise the paper to emphasize that the decoder generates $\\hat{p}_W^2$ following the one-bit protocol.\n\n-   **In the subsequent algorithm of B.1, it is not stated how** $r(s)=\\hat{p}_B(s)$ **is estimated.**\n\nLet us clarify the basic assumption of the successive refinement subroutine in Section B.1 here. We just assume that $\\hat{p}_B$ has been known and is an input of the subroutine. We explained in the last sentence of the first paragraph in Section B.1: \"It receives an estimate $\\hat{p}_B$ of the block distribution $p_B$ of dimension $t$, and outputs an estimate $\\hat{p}_W$ of the original distribution $p_W$.\" In other words, the subroutine is one step in the inductive procedure. $\\hat{p}_B(s)$ has been generated by the previous step or the base step, and the goal of the subroutine is to generate $\\hat{p}_W$ based on $\\hat{p}_B$ at the decoder side through communicating with encoders. How to construct the complete protocol by inductively using the subroutine is presented in Section B.2.\n\nWe are going to add a pseudo-code description of the subroutine in Section B.1 to emphasize the input of the subroutine.\n\n-   **There are some typos, such as ...**\n\nThanks again for your careful reading. We will correct these typos in the revised paper. Moreover, we are going to do a thorough proofreading to ensure that other typos are corrected and the presentation is improved."}, {"review_id": "FHTaSAQUcw", "reviewer": "Reviewer_sk54", "summary": "The paper derives minimax optimal rates for communication-limited \\ell_p estimation of discrete distributions, identifying an elbow effect at p=2 and developing adaptive protocols combining refinement methods with specialized techniques to achieve these rates.", "questions": "Expand the motivation and implications in the introduction, add more intuitive explanations of key concepts, and include illustrative examples where possible. This will help researchers outside this specialized area better appreciate the significance of the contributions.\n\nDemonstrate the practical applicability of the theoretical findings through numerical experiments or case studies.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is technically solid. Conclusive results are obtained for most scenarios, greatly extending and strengthening the relevant results in the literature. \n\nThe current presentation is quite terse, which may limit accessibility for readers outside this specialized field. Enhancing the exposition with additional explanatory passages would improve the paper's broader appeal.\n\nWhile the theoretical contributions are substantial, incorporating empirical validation would further strengthen the work by demonstrating practical applications of the theoretical findings.", "was_revised": true, "final_justification": "Based on the original manuscript and the authors' responses, I have no major concerns regarding this paper.", "rebuttal": "Thanks for your careful reading and constructive suggestions. We are going to revise our paper according to your suggestions in the following aspects.\n\n-   **... Enhancing the exposition with additional explanatory passages would improve the paper's broader appeal. Expand the motivation and implications in the introduction, add more intuitive explanations of key concepts, and include illustrative examples where possible. This will help researchers outside this specialized area better appreciate the significance of the contributions.**\n\nThanks for your suggestion. In the revised version, we will add more explanatory passages throughout the whole paper. Especially, we will expand the motivation and implications in Section 1, add more explanations about the key concepts in Sections 1 and 2, and validate our general results in several special cases to provide some intuition in Section 3 and 4.\n\n-   **While the theoretical contributions are substantial, incorporating empirical validation would further strengthen the work by demonstrating practical applications of the theoretical findings.**\n\nWe will try to add some empirical validation in the revised paper and later works."}]

Author rebuttal:

Meta-review: This paper studies the problem of distributed distribution estimation under communication constraints. While this is a classical problem which has been studied extensively in recent years, this paper provides a complete picture to the general setting of 

1. each node holds multiple observations; 
2. a strong interactive communication protocol; and
3. a general \ell^p loss with p\ge 1. 

This paper gives a complete characterization of different regimes, with matching upper and lower bounds in each regime. In particular, several different algorithmic ideas are applied in different regimes. The reviewers unanimously appreciate the merits of this paper, and I'm happily recommending acceptance. Meanwhile, the presentation of this paper can be greatly improved if some pictures of regime classifications can be drawn, and intuitions can be provided for the results in each regime.
Decision: Accept (spotlight)