Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Authors: Deheng Yuan
Tao Guo
Zhongyi Huang
Venue: ICML 2025 poster (2025)
Keywords: Distributed statistical estimation
nonparametric estimation
communication constraints
distributed algorithms
optimal rate of convergence.
Primary area: theory->learning_theory

Abstract: Consider the communication-constrained problem of nonparametric function estimation, in which each distributed terminal holds multiple i.i.d. samples. Under certain regularity assumptions, we characterize the minimax optimal rates for all regimes,  and identify phase transitions of the optimal rates as the samples per terminal vary from sparse to dense. This fully solves the problem left open by previous works, whose scopes are limited to regimes with either dense samples or a single sample per terminal. To achieve the optimal rates, we design a layered estimation protocol by exploiting protocols for the parametric density estimation problem. We show the optimality of the protocol using information-theoretic methods and strong data processing inequalities, and incorporating the classic balls and bins model. The optimal rates are immediate for various special cases such as density estimation, Gaussian, binary, Poisson and heteroskedastic regression models.

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Deheng Yuan
Tao Guo
Zhongyi Huang'
Abstract
the classic centralized settings where all the samples accessed directly.
Consider the conmunication-constaaiinn prob- lem of nonparametric function estimation, in which each distributed terminal holds multiple i..dd samples. Under certain regularity assump- tions, we characterize the minimax optimal rates for all regimes, and identify phase transitions of the optimal rates as the samples per terminal vary from sparse to dense. This fully solves the prob- lem left open by previous works, whose scopes are limited to regimes with either dense sam- ples or single sample per terminal. To achieve the optimal rates, we design a layered estima- tion protocol by exploiting protocols for the para- metric density estimation problem. We show the optimality of the protocol using information- theoretic methods and strong data processing in- equalities, and incorporating the classic balls and bins model. The optimal rates are immediate for various special cases such as density estimation, Gaussian, binary, Poisson and heteroskedastic re- gression models.
In this work, we investigate the nonparametric function es- timation problem. where each of the m terminals observes n i.d.. samples and has communication budget of bits. We consider all parameter regimes from sparse dense samples per terminal, i.e., there is no restriction on the rel- ative value of compared to m. Inspired by (Zaman & Sz- abó, 2022), unified nonparametric estimation model de- scribing many ways of sample generation is adopted in this work, so that many specific settings are subsumed.
1.1. Our Contributions
The main contribution of this work is that we obtain the minimax optimal rates (up to logarithmic factors) for the aforementioned estimation problem, under a few regular- ity assumptions. The assumptions are satisfied in sev- eral key estimation settings, including density estimation, Gaussian, binary, Poisson and heteroskedastic regression models. Hence, the optimal rates for these models follow directly as corollaries of the main results.
Previous works focused on either the case m < n2, 7 < 2r (r is the Sobolev regularity parameter) with dense sam- ples (Szabó van Zanten, 2020; Zaman & Szabó, 2022) the specific density estimation problem with extremely sparse
1. Introduction
Distributed nonparametric estimation problems have at- tracted wide attention, and related theoretical studies can shed light on the understanding of modern applications such federated learning (McMahan et al., 2017; Li et al., 2020; P. Kairouz, al., 2021). In this setting, multiple distributed terminals cooperate to estimate nonparamet- ric function, while each of them can only observe part of samples and use limited number of bits to describe the ob- servation. The limitation of communication resources of- ten leads to an increase in estimation error compared with
sample (Barnes et al., 2020; Acharya al., 2024). We fully solve the problem by characterizing the optimal rates for all regimes from sparse to dense samples per terminal classified by the relative size of n and m. As result, We see that the dependence of the optimal rates on the communication budget can be qualitatively different for sparse and dense settings, where phase transitions are clearly characterized.
To establish our results, we need to prove both the up- per and lower bounds for the minimax rate. For the up- per bound, we design a two-layer estimation protocol. The outer layer transforms the original problem into paramet- rie density estimation problem, and the inner layer solves by exploiting the protocol developed in (Yuan al., 2024). The design of the outer layer employs wavelet-based timator with sparsity properties, incorporating appropriate
'Dppartment of Mathematical Sciences, Tsinghua Univer- sity, Beijing, China. "School of Cyber Science and Engi- neering, Southeast University, Nanjing, China.. Correspon- dence Tao Guo <taoguo scu.edu.en2, Zhongyi Huang <zhongyih@tsinge teaiih@@tiingu..du.com
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
truncation and quantization. Moreover, parameters link- ing two layers are tuned carefully to achieve optimality. For the lower bound, we take advantage of information- theoretic methods (Barnes et al., 2020; Acharya et al., 2022; 2023). We prove and apply a generalized tensoriza- tion of the strong data processing inequality, in which the key step is to bound the strong data processing constant. To establish this bound, we interpret the likelihood ratio by drawing connections to the classic balls and bins model.
B
Xi
Encoder
B2
(Bi, X2)
Encoder 2
Decoder
Bm
B BBim-1, X
Encoder m
Figure Distributed interactive nonparametric estimation
1.2. Comparisons with Related Works
As a theoretical framework for federated learning, dis- tributed nonparametric estimation problems under commu- nication constraints received wide attention (Zhu & Laf- ferty, 2018: 8; Barnes et al., 2020; Szabó & van Zanten, 2020; 2022: Cai & Wei, 2022: Zaman & Szabó, 2022; Acharya et al., 2024), as well as related problems under differen- tial privacy constraints (Butucea et al., 2020; Kroll, 2021; Sart, 2023: Lalanne et al., 2023; Cai et al., 2024). For the problems under communication constraints, optimal rates for certain special cases are obtained such the nonpara- metric density estimation (Barnes et al., 2020; Acharya et al., 2024). nonparametric Gaussian regression (Szabó & van Zanten, 2020), Gaussian sequence model with white noise (Zhu & Lafferty, 2018; Szabó & van Zanten, 2022; Cai & Wei, 2022) and two-party joint distribution estima- tion (Liu, 2022; 2023). In (Zaman & Szabó, 2022), gen- eral framework was developed and optimal rates were de- rived for several special cases under specific assumptions.
and more difficult than the Gaussian sequence model stud- ied by (Zhu & Lafferty, 2018; Szabó & van Zanten, 2022; Cai & Wei, 2022), and merits separate investigation. The difference is reflected in the optimal rates, which depend exponentially in / for some regimes of our problem, but al- ways polynomially for the Gaussian sequence model.
Moreover, it is interesting to see the similarities in the phase transitions of the optimal rates between the nonpara- metric estimation problem considered in this work and the parametric distribution estimation problem (Acharya et al., 2020; 2021; Yuan et al., 2024). The inherent connections are partially revealed in this work.
1.3. Problem Formulation
We denote a discrete random variable by a capital letter and use the superseript n to denote an n-sequence, c.g., X" (X.)%_ For any positive functions a(m, n, n)) and b(m, rr,, we say a bifa S e- for some constant 0 independent of parameters (m, n, 1). The notation ž is defined similarly. Then we denote by x both a 3 b and a ł b hold.
In the setting where each terminal has i.i.d. samples, pre- vious works focused on either the regime m < n",, < 2r (r is the Sobolev regularity parameter) with dense sam- ples (Szabó & van Zanten, 2020; Zaman & Szabó, 2022) or the density estimation problem with extremely sparse = 1 sample (Barnes et al., 2020; Acharya et al., 2024). However, the problem for other choices of n is more dif- ficult, since the methods in (Barnes et al., 2020; Acharya et al., 2024; Szabó & van Zanten, 2020; Zaman & Szabó, 2022) cannot be applied without substantial development.
Let be an unknown distribution (assume p is the pmf or pdf) parameterized by a function f belonging to a subset J of the standard Sobolev ball H ((0 1], L). r > 2. L > 0. See Section 3 for brief introduction of Sobolev spaces and wavelets. Assume that samples are generated at ran- dom according to py. To be precise, let Xij pf(x), 1, 2. m. j = 1, 2, ... n be i.i.d. random variables dis- tributed over X. Denote the total sample size by N == mn.
In the current work we set no restrictions on the rela- tive size of and m and obtain the optimal rates for all regimes, which fully solves the problem. To handle this general case, our framework imposes assumptions which are strengthened slightly from that in (Zaman & Szabó, 2022). All the special cases therein are still subsumed in our setting. Moreover, different from (Zaman & Szabó, 2022), our assumptions are imposed on single random vari- ables, making them easier to verify.
Consider the distributed nonparametric minimax estima- tion problem with communication constraints depicted in Figure 1. Assume there m encoders. For i 1,..., m, the i-th encoder observes the source message X (X,;)²= and the first i-1 coded messages (Bx) 1- Then the coded binary message B, of length / is transmitted to the decoder and the remaining m - í encoders. Upon re- ceiving messages Tm (B.) the decoder needs to es- tablish a reconstruction f E H² 1], L) of f. We assume that l 2 4 in this work, which is reasonable for most cases.
Specialized to regression problems like the nonparametric Gaussian regression, our problem leads to setting with random design where the explanatory variable is randomly generated. The resulting problem is substantially different
An (m, n, sequentially interactive protocol P is defined
2

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
by a series of random encoding functions
Proof of Theorem 2.1. We collect different cases in (2) based on the exact formula of Ness- Logarithmic factors in some boundaries that do not affect the conclusion in Theo- rem 2.1 are omitted. The proof of both lower and the upper bounds needs to handle all the following cases respectively.
Enc;: : X" x (0,11) + Vi I,.;, and random decoding function
Dec: : f0, mm + H" (7, L).
Then we have B; Enc, (X", B1 and the reconstruc- tion of the function is fo = Dec(Bi B2, .... Bm).
2rt1 1. Ness = (2'mm) 2 for m 2 2r and 1 S S 2r+1 log - In this case n S Ness I m.
Define the minimax convergence rate
2. Ness = Im for m > n² and 2r41 log narr V nd
R(m, n, n,,r) (m, n. pprotooool P JEF
inf sup Billfp fll)). (1)
S In this case Ness 2 n V m.
The parameter L is omitted in (1), since assume that L is constant and are only interested in the order of the convergence rate R in this work.
3. Ness = (mm) for n > m 2 and S 1 z n n In this case Ness S n.
4. Ness (Imn) 2-12 for < n nr and प V S m
2. Main Results
1 == A (mn) 20111 In this case n I Ness < <n 2r+
For the case oc, i.e. there are no communication con- straints, it is well known that (ef. Section 6.3.3 in (Giné & Nickl, 2015) and Section 15.3 in (Wainwright, 2019))
5. Ness mn for 1 2 n A (mn)a
R(m, n, 00, r) x -
We formulate the assumptions and give the detailed proof for upper and lower bounds in Sections 4 and 5 respec- tively. Combining the results of Theorems 4.2 and 5.3 di- rectly implies Theorem 2.1.
for specific settings like density estimation and Gaussian regression. Recall that N mn is the total sample size.
To see the effect of communication constraints, first define the effective sample size Ness as
2.1. Phase Transitions from Spase to Dense Samples per Terminal
{ (22 mm) 2 Alm) v (1m))r+) (lmm)) == } A mn.
Within a logarithmic gap, the optimal rate R(m, n, I, r) is fully characterized by Ness. which can be written in the following equivalent form.
(2)
It is easy to see that for = do. we have Ness mn. Further denote by Poly N) polynomial of log N. In the following, we show that the optimal rate for the prob- lem in Section 1.3 with total sample size mn is roughly the same as that for the problem without communication constraints with total sample size Ness. which is the main theorem of this work.
(2'mm) (Imn)
2r11 A Am A mn,
if 2 2r+1
2r+1
V Im
A mn,
if < m < n 2r+1
and n S m 2r+1
Ness
Theorem 2.1. Under Assumptions 4.1, 5.1 and 5.2, we have R(m,n,
(mmn) 2-12 A mn, if m S 2r and n I m 2r+1 (1m) ^ (Imn) 2 A mn,
= (Ness) * Tiol/Pooyyog N) and R(m, n. I,,, 2 (Ness)- (afi)) Poly(logg
if S 2r and n > m 2r+1
Theorem 2.1 shows that the minimax optimal rate R(m, n, 1,r) is approximately (Nee.)) 2:+ under a few necessary assumptions 4.1, 5.1 and 5.2 on the sample dis- tribution py. Details of assumptions are omitted here and will be formulated in Sections and 5. Assumption 4.1 is for the upper bound, which requires the existence of good estimators for f based each sample X ~ py- The re- maining assumptions 5.1 and 5.2 are for the lower bound, which reveals the difficulty of estimating f based on sam- ples generated from py. These assumptions are reasonable, and can be verified for many common examples such as those presented in Section 2.3.
First, we see that the dependence of R(m, n, n,,,) on the communication budget is different for sparse and dense regimes. For the sparsest regime, i.e. m > nr#+1 R(m, I, first decays exponentially as 1 increases, and then the rate slows to a polynomial order. For other regimes, R(m, n, l) always depends polynomially on l.
Second, in order for the distributed system to achieve roughly the same performance as the centralized one, the minimum communication budget should be for m > n and (mm) मंं for m S n 2r.
3

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
2.2. Compartsons with Related Previous Works
son and heteroskedastic regression models. By directly ver- ifying Assumption 4.1, 5.1 and 5.2 and specializing Theo- rem 2.1, the minimax optimal rates for all these settings are obtained in a unified manner.
Remark 2.2. The work (Zaman & Szabó, 2022; Szabó & van Zanten, 2020) only considered the case I n² for y x 2r with an extra assumption Ness > n. It is special case of the last two cases in (3) by imposing that Ness > n. In this case, Nesss = (Imn) 2 A mn and Theorem 2.1 re- covers the main results Theorems 1-2 of (Zaman & Szabó, 2022) under similar assumptions. Furthermore, our results extend those in (Zaman & Szabó, 2022) in two directions. First, we give the optimal rates for regimes m < n²²,, re- vealing more complicated but interesting structures of the problem. Second, we do not require Ness > n. Although restricting the scope to Ness > n suffices in certain situa- tions, is generally impractical in most others. Moreover, investigating the problem without the restriction can give more insights from theoretical view.
2.3.1. NONPARAMETRIC DENSITY ESTIMATION
Example 2.6 (Density Estimation). Each of m distributed terminals observes n i.i.d. random samples X7", and each sample Xij is generated from density function f H' (0, 1]. L). We want to estimate f at the decoder side. The problem is special case of the framework in Sec- tion 1.3 by letting
ps(#) = f(x), E [0.
(4)
The optimal rate for the above density estimation problem is shown as follows and proved in Appendix D.1.
Remark 2.3. The work (Acharya et al., 2024) considered the density estimation problem with extremely sparse sam- ples (i.e. Y = 1), the L norm and the Besov space B(p, q, r). By letting = q = s = 2. the Besov space re- duces to the Sobolev space H' ((o, 1), L) and the L norm becomes the L norm. In this way, their problem reduces 1, in which their conclusion coincides with the first case in (3), that is Ness (2'm)² / Am. It an interesting direction gen- eralize our results the Besov space and I.* norm, though it is not the main goal of this work due space limitation. Remark 2.4. We find the exponential dependence of R(m,n, n, (,) in I for m 2 n= and < I S 2-4I log प It is different from the Gaussian sequence model considered in (Zhu & Lafferty, 2018; Szabó & van Zanten, 2022; Cai & Wei, 2022) where R(m, r) de- pends on only polynomially, although there are phase transitions in the polynomial order. This difference in min- imax optimal rates is because the ways of generating sam- ples are different, between the Gaussian sequence model in (Zhu & Lafferty, 2018; Szabó & van Zanten, 2022: Cai & Wei, 2022) and the random design problem in Section 1.3. For the former, the noisy versions of all the Fourier coef- ficients are known, instead of the random samples them- selves for the latter.
Corollary 2.7. For the nonparametric density estimation
problem, have R(m, n,l,r) 3 Neas उ Poly(log N) and R(m, n. r)) E (Ness) 25-1 /Polyylooy))))
2.3.2. NONPARAMETRIC REGRESSION PROBLEMS
to the special case of Example 2.6 with
Consider nonparametric regression problems in the dis- tributed setting. Each of m distributed terminals observes i.i.d. pairs of random variables (Tij, Yoy);= and each pair (Tej, Yij) is sampled under random design, where we assume that the explanatory variable Tı₃ ~ [ni 1)) and the response Yú follows some distribution parameter- ized by f(TT)). We want to estimate f at the central de- coder. Next we specify the conditional distribution YúglTT, and consider the resulting regression problems.
m
Example 2.8 (Nonparametric Gaussian Regression). Let Yi Tij (((f(T.)) 1), and then the model is special case of that in Section 1.3 by letting
ROO
Pr(t, 8) = 22m
e
I = (t.8) E [0,1 R. (5)
Example 2.9 (Nonparametric Binary Regression (Classifi-
cation)). Let (t) E [0, 1] for any t E [0, 1] and Y., [Ta
(fr,(f(T,))), Then the model is special case of that in Section 1.3 by letting
Remark 2.5. In (Acharya et al., 2021) and (Yuan et al., 2024), the parametric distribution estimation problem was considered. The optimal rates were shown to be expo- nential in for some regimes, while polynomial for other regimes, which is similar to the phenomena revealed in this work. Deeper connections of these two problems are found and discussed in Remark 4.5.
(f = f()) y=1 + (1 -()) y= x x= (1, y) E (0, 10,
(6)
Example 2.10 (Nonparametric Poisson Regression). Let f(t) > 0 for any E [0, 1] and YiylTaj ~ (f Then the model a special case of that in Section 1.3 by letting
2.3. Examples
In this subsection, consider several important estimation settings such as density estimation, Gaussian, binary, Pois-
pf v) = -1(0 (f(t))
, (t, (l.1)) (7)
y!
4

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Example 2.11 (Nonparametric Heteroskedastic Regres- sion), Let f(t) > 0 for any è [] and Y.yTT NO, ((T))) Then the model is a special case of that in Section 1.3 by letting
4. If 3, then H' (1, L) L) & 1 ( 11, L) for some Tt (1,,,r) r) O, where ( 11, {f
( 11) I| S L'}.
1
4. Upper Bounds
()((,))
कズे , (1,0) [0, xR. (8)
2
The wavelet-based approximation formula (9) in Section is useful for estimating the function f. Throughout this section, let K" 2 simplify the notations. In order to exploit (9), we make the following assumption regard- ing the existence of a good sample-wise estimator of each wavelet coefficient fHs.
For each of the above regression problems, the optimal rate shown as follows and proved in Appendix D.2. Corollary 2.12. For the nonparametric Gaussion, binary, Poisson and heteroskedastic regression problems, have श Poly(loog N) and R(m,n,I,r) z
R(m,n.l,r) n. 1,), Neeē
(Ness) * /Poly((oog)))
Assumption 4.1. Assume X (T,Y), where T [0, 1] and Y E V. For any H E N and 8 1, ..., K, there exists an estimator fus(X) = h(Y)) (T) of Jn, that is unbiased (E[fH,(X)] fHs) and sub-exponential with parameters (VeiK, K))..
3. Preliminary Results on Sobolev Spaces and Wavelets
We want to find good approximation formulas for the Sobolev space H" 1], L). r, > 0 in order to simplify the L estimation problem in the space. It turns out that the wavelet construction is suitable, since it induces sparse representations of randomly generated data, which is fully exploited in the proof of the upper bound.
The definitions and related properties of sub-exponential random variables can be found in Appendix A.1. In many estimation problems, such the density estimation and re- gression problems in Section 2.3, the construction of the estimator fH (X) in Assumption 4.1 1 is easily seen.
We follow the construction by (Daubechies, 1992), for more details see (Giné& Nickl, 2015; Simon, 1990). Start with two continuous father and mother wavelet functions 6, with S vanishing moments and bounded support on [0, 28 1] and [-S + S] respectively, where S > r. By linear scaling of & and 1/r and correcting them near the boundary, an orthonormal basis for (² 1] is obtained.
Then we can obtain the upper bound in the following theo- rem, which is the main goal of this section. The theorem proved by the estimation protocol and its error analysis in the following two subsections respectively.
We can construct an approximation fd E H" ((0, 1], to the 1 norm with resolution H N by
Theorem
4.2. Under Assumption 4.1, we have R(m,n,4r) - (Ness) 2r44 Poly((oog N).
2
2r
fH
Σ fuscHa:
(9)
4.1. The Layered Estimation Protocol
where {onr) )2" is an orthonormal system and Jns (f, ΦHe). Furthermore, for any function f in the smaller space H"O J. L) S I= 1], useful properties of the ap- proximation f are summarized the following lemma. See Section 4.3 in (Giné Nickl, 2015) and Corollary in (Simon, 1990) for the proof.
It suffices to let S nA (1mm)) x'T,, otherwise we can simply discard the additional bits. That is, we consider Cases 1-4 in the proof of Theorem 2.
The main characteristic of our protocol is that it consists of two layers. The outer layer converts the original nonpara- metric distributed estimation problem into a distribution es- timation problem. The inner layer estimates the parametric distribution. This can be achieved by invoking the proto- col in Lemma A.2 for the distribution estimation problem. The resolution parameter Hf of the wavelet approximation is carefully determined, so that the error induced by inner and outer layers is balanced.
Lemma 3.1. Let f E HT 1), Then the approxima- tion f by (9) satisfies the following.
1. |1o 1 24, 224,for for any 1, l..... 2
2. Let NHs {
(sspp(( ) + 0} for
s 1,,..,?" 2H, Then NH S 2S +2
3. The I convergence rate satisfies
Preparation: Choose the resolution parameters (H, K = 2 based on the parameters (m, n, L)r,, where H is the
|l ش 1/ v 2 2Hr
(10)
5

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
smallest integer such that
Then it computes
(2'm 3-32
for Case 1 for Case 2,
fH Σ
plo' Hisss
(14)
(Im)>riI, Im 2000 log" N (Imen) 2+42
and finally the estimate
225+2 K
for Case 3,
(11)
K f" - fHSSHS.
(15)
for Case 4.
2000 log" N
Remark 4.3. The idea of estimating sparse wavelet co- efficients through estimating a parametric distribution in nonparametric estimation problem is inspired by (Acharya et al., 2024), while only the density estimation problem with n was considered therein. The general estimation problem defined in Section 1.3 with n >> is substantially more difficult and require much more effort. There are two major differences.
Let Ko = cg log N, where 03 is much larger than (e.g. 03 > 400(r + 1)22, cf. Assumption 4.1). Define the
truncation function
Trunck, (w) (w A Ko) V (-Ko).
(12)
The truncation function and the sample-wise estimation function fHs are known to all the encoders and the decoder.
First, the estimator (X) is bounded for the density es- timation problem. However, this is not the case for regres- sion problems and the general estimation problem in Sec- tion 1.3. To overcome the difficulty, in the protocol and show the resulting error is negligible, under a sub-exponential condition of (H)( satisfied by most common problems.
Quantization: For 1,... m. upon observing XT (Tig, Yg))==- the i-th encoder first computes Siy [KTgyl and determines NHs., based on Sij. Then for each j =1 =I...,n and s E .Nssy, the encoder computes (Xi(( (Xig) = Truncko (fns()))) 2Kg
truncate (X)
and (Hi(X)))
(a It is easily seen that
Second, for the estimation of the parametric distribu- tion, the work (Acharya et al., 2024) takes advantage of the simulate-and iiilaate-an---iee and-infer protocol in (Acharya et al., 2020), which is optimal for n but not for 1. Unlike the special case that the optimal protocols for the distribution estimation problem in Lemma A.2 with n > 1 vary across different parameter regimes. Hence there are many possible choices of the parameter and the protocol in the outer and inner layers respectively, and finding the optimal one can be ob- scure. The main work in this section is to determine the optimal parameter and protocol for cases 1-4 in the proof of Theorem 2. so that the optimal rate is always achieved.
Qns (X.j) E 1). Then it generates an i.i.d. random bit sequence (EENs,)) of lengh [WHs., 2$ + 2, and each bit follows the distribution Bern(Q (X.))) The sequence Vi, is the quantization of (X:)) (xj)))eNnnsy
1, we can see from (Yuan et al., 2024)
Next, the i-th encoder computes Wij (Sij, Vij) E {L. } x {0, 1|2422 Denote the alphabet of Way by (1, [[1....,]]]] K} x {0, 1J2842, then [W|- = 225+2 K. Note that (W(s))) denote the distríbution of each W., by (ww).. The i-th encoder holds n i.i.d. samples WT (W;));=1-
are i.i.d random variables, and we
Estimation of the Parametric Distribution pw: The encoders send messages to the decoder for estimation of the parametric distribution Pw following the protocol ASR(m, n, I, (WI introduced Lemma A.2 and (Yuan ct al., 2024). Let the estimate of the distribution be (w))..
4.2. Error Analysis
The following lemma describes the overall error bound in terms of the inner layer error. See Appendix B. for the proof.
Decoding and Reconstruction: Based on the estimate of the parametric distribution of Way, the decoder reconstructs an estimate fd of as follows.
Lemma 4.4. For the estimate jH obtained by the protocol in Section 4.1,
For any s' = 1, H, the decoder computes
ElI - f1 31 K-K2 + K Klog NE [llew Pw [2 (16)
2Ko
1 (s',s)) vro())=1
Σ
2 fow((s)
Next we bound the inner layer error for cases 1-4 by Lemma A.2 and (11). Then the overall error bounds are evaluated accordingly. We present the sketch here, and detailed verification can be found in Appendix B.2.
p(d') HHs
(13)
ifs E NH
0,
if & Nu
6

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
subset of (vn-ho b feez such that the support of v/?" 2
For Case the condition of 3) in Lemma A.2 is satisfied and we have ['llww - Pw 2
Then
is contained in [ zn-no]
mmm
Let k = 2hh { J==1 be a subset of Iwez Irez. where the support of v is contained in [ El discussed above. To construct multiple hypotheses that are useful for the proof, consider finite sieve F(k, Co.e) defined as
Bi|j fM f1 3 (2' mm) - log" N.
For Case 2, the condition of 2) in Lemma A.2 is satisfied
and Elllöw Pwl I log( 22842 K +1)
Then mn
ml
{
Jst S.+ fs - Co + ek
- ((+
Σ
2a ** {{11,1 81
BIII" f12: (lm) T log" N.
(17)
The constant Co depends on the problem. Specifically, it is 1 for the density estimation problem, 0 for Gaussian re- gression, 1 for classification and a positive real number for Poisson and heteroskedastic regression in Section 2.3.
For Case 3, the condition of 1) or 1') in Lemma A.2 is satisfied and roughly Billöw pw 3 248+2,K Then
mnn V mnn'
2
Let E E (0, 1) be small enough such that, i) F(k, Co e) S
EIIS" f121 3 (lm) 2r log"h N.
([, 1]. L); ii) if C. > O, then f= (t) E [ 20 Vt E
[0, 1]. This can be achieved since we have | l| = 2hr
For Case 4, the condition of 1) in Lemma A.2 is satisfied, and we have E[líw Pw 22,12,K
and | Il=c N 24. To simplify the notation, let pet Pf.,
Then mal V mnn
for any function f&- E F(k, Co, and correspondingly,
P,+ = Px"=p"' and E5 = Ex"=p"e" where the meaning will be clear in the context.
ElIF f11] 3 (lmn) Ai log 2 N.
Then we make a few assumptions on the sample distribu- tion Pyt, which are essential to prove the lower bounds.
Combining all cases completes the proof of Theorem 4.2. Remark 4.5. From the construction of the protocol and its error analysis, we find a clear correspondence between the distribution estimation problem in Appendix A.3 and the nonparametric estimation problem considered in this work (cf. Section 1.3). With the help of the outer layer in our protocol, the protocol for the parametric distribution esti- mation can be used as an "oracle" prepared for the inner layer. The optimal rate for each case of the nonparamtric problem is implicitly achieved by protocol for the distri- bution estimation problem.
Assumption 5.1. Assume that X (T,Y), where T [0, and Y E V. For any 2² E {+1}* and s 1, 1..., k. (= E [-=]] x)x = & and the conditional distribution P.u (z|æ E ( kel x y)) only depends on 2,. Specifically, the distribution pa* admits a decomposition
(x((x) = 1. P...,, (z).
(18)
for any x = (t, v) with t E 1 El. where Ps.e. (x) is distribution on 1 Rl x y for any s = 1,... I and
From a high level, we can imagine a "homomorphism" " from the distribution estimation problem to the nonpara- metric estimation problem, and each case of the former is mapped to one case of the latter. We hope this observation can give more insights to investigate various distributed sta- tistical problems as a whole.
2, - +1.
Assumption 5.2. Let the sample-wise log- ligllikeldoodd ratio be
Lx,, e log (o.-2,(x))
(19)
Pe.cs (I)
for any x = (t, with t E [ 22,, = 1.... k and 2, = +1. We assume that for X ~ Pa,,,, Iin,, (X) is sub-cxponential with parameters (v = vC h 2- C2k and [E[L,,., (X)]l S C3 22
5. Lower Bounds
In this section, we establish the lower bounds and show the optimality of the estimation protocol.
Then we have the main theorem of this section, focusing the lower bound. It is proved in the rest of this section.
Recall the wavelet construction in Section 3 and let (t) = (2*x s) for h E N and s E Z. By the construction of ę in (Daubechies, 1992) we have [|unall2 1 = 1. Let hg = [log, (2S' + 2)] and h Z ho- For s 1,-.. ho, there exists s' Z such that the
Theorem 5.3. Under Assumptions 5.1 and 5.2. we have R(m, n, L,) 2 (Ness Poly(log N)) -
5.1. Information Lower Bounding Methods
support of 4/n Ao.s' is contained in fz - Let
W - 20
We define a prior distribution on H" (Jo, 1], L) to be the uniform distribution on the sieve F(k, Co, e). Let Zt
(12 high- = Uh s for such 8'. Then
1==1 is a

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
{Z,)==1 be sequence of i.i.d. Rademacher random vari- ables with mean 0. Then under the prior distribution, the function and the sample distribution are f f2" and Ps pz*, respectively. Then we have the following lemma proved in Appendix C.I.
in these problems sub-Gaussian boundedness condition of the terminal-wise likelihood ratio La.s* (X*) is not sat- isfied. To overcome the difficulty, we establish the bound
of E (X") on the regular event (E(X*) = 1 and then argue that the effect of the irregular event {F((X)) = 1} with small probability is limited in Lemma 5.5.
Lemma 5.4. If & E -==1 (ZziBBr)) S for some & E N, then R(m, n, 1, r) = 2-
Remark 5.8. In the work (Cai & Wei, 2022). similar bound (18) therein for information measures is simpler and makes further analysis easier. However, the proof there depends heavily on the symmetry of the Gaussian random variable, which clearly does not hold for the general estimation prob- lems in this work. Hence we have to handle the small error probability more carefully. This also explains the reason that the work (Cai & Wei, 2022) obtains a tight bound for the Gaussian sequence model, but it is much harder to elim- inate the polynomial factor of log N for the problem here.
With the help of Lemma 5.4, the proof of Theorem 5.3 is reduced to choosing suitable i and showing the informa- tion incquality 1 2 [[2;; BTm I 1. and then we ob- tain that R(m, n. (,) -= k 2r_ Methods to prove the in- equality are different for Cases 1-5. The bounds for Case 5 and Case are easy and shown in Appendices C.2 and C.3. The proof for the other three cases need much more efforts, which is the goal of the remaining parts of this section.
Then we specialize Lemmas 5.5 and 5.6 to Cases 1, 2 and and derive the corresponding bounds. The goal to itself or its second moment. To achieve the goal, the underlying intuition is described as follows. By Assumption 5.1, the terminal-wise likelihood ratio (x,""("=") is related to the sample-wise one in (19) by
5.2. Proof for the Remaining Cases
First we define the terminal-wist likelihood ratio be
bound La (X*)
- (x***
Prt (x*) D" (Ix²)
Le (I²))
(20)
where ² 0* t0t = (/r and e, = ((-1)/>=))
Le (x*)
II Jit, E (2)
exp (x,,,,
(23)
It plays a central role in the rest of the proof, since two of its properties lead different kinds of bounds for k "x=11(2 I(Zg; BT). The following two lemmas describe the bounds respectively, whose detailed proof can be found in Appendix C.4.
Hence c (X*) is a product of many independent factors exp(T1,,== (Xz)). if (T:) is given and X, = (T:, Y.). By Assumption 5.2, each of these factors has a small ampli- tude. If the number of these factors is bounded, then both (X²) and its second moment can be bounded. The number has a clear meaning by Assumption 5.1. It is the number of balls in the s-th bin (denoted by V.) in the classic balls and bins model where n balls are thrown into h bins at random (see Appendix A.4 for details). By bounding Vs, the goal can be achieved and the whole proof is completed. We sketch the proof for each case in the fol- lowing, and details can be found in Appendices C.5, C.6 and C.7 respectively.
Lemma 5.5. If (EE,((CC,,**X' - -1) S a² for any s=
1,...,k I and 2º E 11,, then we have
1
22ma²
(Z,;;
<
(21)
T s=1
2k
Lemma 5.6. If there exists Boolean function Exx") such that
i) ..P [B(X)) = 0] S 81 < 5 for any z* E (=-1 1²:
(x) = 1 if and only if [C,, (In) - 1 S 82 for any
2 E (1,, === I....h.. k.
5.2.1. PROOF FOR CASE
Then we have
The goal is to show R(,,n, Z (2'mn) -ft for Case 1. Note that the expectation of each exp(2 (X)) is roughly exp(2v²) x 1 + 2v² by Assumption 5.2 and the number V, is E on average. Then by (23), for k x (mm22)=+*z we can show that
16ml63 (22)
I(Z:;BT) S mmlog + +8) +
k
Remark 5.7. The idea behind Lemma 5.6 and its proof is similar to Theorem in (Acharya al., 2023), that is to obtain a tight strong data processing constant. The major improvements of Lemma 5.6 is that it admits irregular event (E(X*) = 0} with small probability, while such an event is not included in Theorem 2 in (Acharya et al., 2023). This makes Lemma 5.6 more flexible to use espe- cially for various regression problems (e.g. the nonpara- metric Gaussian regression problem in Example 2.8), since
E. [[C,,,.+** - 1)} 1 ((
Hence Lemma 5.5 implics that
Σ T(Z,: BThh = 22mm
k2r42
Finally, by Lemma 5.4 we complete the proof.
8

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
5.2.2. PROOF FOR CASE 2
optimal rates as the number of samples per terminal varies from sparse to dense, finding interesting phase transitions.
We need show R(m,n, I,,, = (Imlog²m) m) 2+41 for Case 2. With the choice k x (ml log m) m we want to obtain a bound for +* (X*) - 1 with large probability. Instead, we turn to bound log . (X"). By Lemma A.3, we obtain uniform bound for all these numbers Va.
Our work motivates several future directions. First, our framework focused on the estimation of functions in Sobolev type spaces with I,² norm. Considering general Besov spaces and the norm may lead to further findings. Second, the differential privacy is another important con- sideration in distributed estimation or federated learning. How the optimal rates depend on the sample size per ter- minal under privacy constraints is also interesting prob- lem, dual to the problem under communication constraints explored in this work. Third, in many practical settings the Sobelov regularity parameter r may be unknown. Adaptive estimation protocols for r has been considered for several specific settings (e.g. (Szabó & van Zanten, 2020; Cai & Wei, 2022)), and may be useful for problem. More- over, it is interesting to develop adaptive protocols for other parameters like (m,n), which is studied in the distributed kernel ridge problem by (Zhang et al., 2015; Xu et al., 2018; 2019). Finally, we remark that problems with dif- ferent ways of sample generation may need separate study. We concentrate on the random design setting in this work. Our methods may be useful for the analysis of the fixed de- sign setting (Li et al., 2024), while the optimal rates may be different. In Remark 2.4 we compared the difference of our problem with the Gaussian sequence model. More gener- ally, heterogeneous or non i.i.d. data for different terminals raise more interesting problems that have both theoretical and practical meaning.
V I log m 1
max
with probability 1- 100, Based on this event, by (23) and Assumption 5.2 we can further show that
Llgg ,., (X*)) 3 B log
100, Thus we choose 61 Om and d2 (33 log m) in Lemma 5.6, which im- plies that
with probability 1 - m 11000
(ml
ml log" m
I(2,: = =0
+,2+11
Finally, by Lemma 5.4 we complete the proof.
5.2.3. PROOF FOR CASE 4
We need show R(m, n, l,r = (Imn) ( r.r log (2r+3) n for Case 4. With the choice k x (mnl) = 1og we aim at bounding log (X*) similar to the previous case. By Lemma A.3, we have
3 2n+3
n log* n
max V. 1 Saakk
A Acknowledgements
k
Deheng Yuan would like to thank Professor Yuhong Yang for helpful discussions, which brought the communication- constrained estimation problems to his attention.
with probability 1- n 10),++1), Based on this event, by (23) and Assumption 5.2 we can further show that
v2 log n
This work was supported in part by the NSFC Projects No.12025100 104 and 62301 144, in part by the SEU Startup Fund No.RFF1288220000 and in part by the Zhishan Young Scholar Fund No.2242025RCB0033
log fey.=' (X")] =
k
with probability 1 1-n 1- 100(r-1),
Thus can choose 51
Onn (n-1100(+1)) and 82 = O ( which implies that
u log"
in Lemma 5.6,
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
I IZ. BT) =
mnl mmnlogg log* n
1:2+22
Finally, by Lemma 5.4 complete the proof.
References
6. Conclusion and Discussions
Acharya, J.,, Canonne, C. L., and Tyagi. H. Inference under information constraints II: Communication constraints and shared randomness. IEEE Transactions on Infor- mation Theory, 66(12):7856-7877 Dec. 2020. 2,
In this work, we considered the distributed nonparametric function estimation problems under communication con- straints. Specifically, we quantitatively characterized the

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Acharya, J., Canonne, C., Liu, Y., Sun, Z., and Tyagi. H. Distributed estimation with multiple samples per user: Sharp rates and phase transition. In International Con- ference on Neural Information Processing Systems, vol- ume 34, pp. 18920-18931 Dec. 2021. 2,
Lalanne, C., Garivier, A., and Gribonval, R. About the cost of central privacy in density estimation. Transactions on Machine Learning Research, Aug. 2023. 2
Li, K., Liu, R., Xu, G., and Shang. Z. Nonparametric in- ference under b-bits quantization. Journal of Machine Learning Research, 25(19):1-68, Jan. 2024.
Acharya, J., Canonne, C. L., Liu, Y., Sun, Z., and Tyagi, H. Interactive inference under information constraints. IEEE Transactions on Information Theory, 68(1):502- 516, Jan. 2022. 2, 18
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Feder- ated learning: Challenges, methods, and future direc- tions. IEEE Signal Processing Magazine, 37-3),00-60, May 2020. 1
Acharya, J., Canonne, C. L., Sun, Z., and Tyagi, H. Uni- fied lower bounds for interactive high- dimensional esti- mation under information constraints. In International Conference on Neural Information Processing Systems, volume 36, pp. 51133-51165, New Orleans, LA, US. Dec. 2023. 2. 8, 22
Liu, J. Communication complexity of two-party nonpara- metric global density estimation. In Annual Confer- ence on Information Sciences and Systems, pp. 292-297,
Princeton, NJ, USA, Mar. 2022. 2
Liu, J. A few interactions improve distributed nonparamet- ric estimation, optimally. IEEE Transuctions on Infor- mation Theory, 69(12):7867-7886 Dec. 2023. 2
Acharya, J., Canonne, C. L., Singh, A. V., and Tyagi, H. Optimal rates for nonparametric density estimation un- der communication constraints. IEEE Transactions on Information Theory, 70(3):1939-1911, Mar. 2024. 1, 2. 4,6 6
McMahan, B., Moore, E., Ramage, D., Hampson, S., and Arcas, B. A. y. Communication--fficiien learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, vol- ume 54, pp. 1273-1282, Fort Lauderdale, FL. USA, Apr. 2017.
Barnes, L. P., Han, Y., and Ozgur, A. Lower bounds for learning distributions under communication constraints via fisher information. Journal of Machine Learning Re- search, 21(236):1-30. Feb. 2020. 1,2
P. Kairouz, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning. 14(1-2):1-10,, Jun. 2021.
Butucea, C., Dubois, A., Kroll, M., and Saumard, A. Local differential privacy: Elbow effeet in optimal density esti- mation and adaptation over Besov ellipsoids. Bernoulli, 26(3):1727-1766) Aug. 2020. 2
Sart, M. Density estimation under local diffcrential privacy and Hellinger loss. Bernoulli, 29(3):2318 2-241,, Aug. 2023. 2
Cai, T. т. and Wei, H. Distributed nonparametric func- tion estimation: Optimal rate of convergence and cost of adaptation. The Annals of Statistics, 50(2):698-725, Apr. 2022. 2,
Simon, J. Sobolev, Besov and Nikolskii fractional spaces: Imbeddings and comparisons for vector valued spaces on an interval. Annali di Matematica Pura ed Applicata, 157:117-148, Dec. 1990.
Cai, T. T., Chakraborty, A., and Vuursteen, L. Op- timal federated learning for nonparametric regression with heterogeneous distributed differential privacy con- straints, 2024. URL https:/ weeeiiiorrg/abae /bs/ 2406. 06755. 2
Szabó, B. and van Zanten, H. Adaptive distributed methods under communication constraints. The Annals of Statis- tics, 48(4):2347 23802 Aug. 2020. 2,2,4,9
Szabó, B. and van Zanten, H. Distributed function estima- tion: Adaptation using minimal communication. Math- ematical Statistics and Learning, 5(3):159-199, Dec. 2022. 2,4
Daubechies. I. Ten Lectures Wavelets. Society for In- dustrial and Applied Mathematics, Philadelphia, 1992. 5.7
Giné, E. and Nickl, R. Mathematical Foundations of Infenite-iimnniinall Statistical Models. Cambridge University Press, New York, 2015. 5.5
van Handel, R. Probability in high dimension, 2016. URL https: /wwbwwwbb.//////// math, wtt.:aaatth..nm.e.. princeton.nn
pdf. 22
Kroll, M. On density estimation at a fixed point under local differential privacy. Electronic Journal of Statistics, 15 (1)117311813, Jan. 2021.
Wainwright, M. J. High-Dimensiona Statistics: A Non- Asymptotic Viewpoint. Cambridge University Press, 2019. 3,
10

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Xu, G., Shang, Z., and Cheng, G. Optimal tuning for divide-and-conquer kernel ridge regression with massive data. In International Conference on Machine Learning, pp. 5483-5491 Stockholm, Sweden, Jul. 2018. 9
Xu, G., Shang, Z., and Cheng, G. Distributed generalized cross-validation for divide-and-conquer kernel ridge gression and its asymptotic optimality. Journal of Com- putational and Graphical Statistics, 28(4):891-90) Oct. 2019. 9
Yuan, D., Guo, T., and Huang, Z. Adaptive refinement protocols for distributed distribution estimation under ( lo-lossss, 2024. URL https: www.xiii.oo/abbboe.eee 2410. 06884. 1, 2, 4, 6, 12, 13
Zaman, A. and Szabó, B. Distributed nonparametric es- timation under communication constraints, 2022. URL https: /aapi///aaiiii /awxiv.ivvvv////v///eee/eiavavva org/ abs 22044 10373. 1, 4
Zhang, Y., Duchi, J., and Wainwright, M. Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates. Journal of Machine Learn- ing Research, 16(102):3299-3444 Jan. 2015. 9
Zhu, Y. and Lafferty, Distributed nonparametric regres- sion under communication constraints. In International Conference Machine Learning, volume 80, pp. 6009- 6017, Stockholm, Sweden, Jul. 2018. 2, 4

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
A. Preliminary Definitions and Results
A.I. Sub-Gaussian and Sub-Exponential Random Variables
We give definitions and properties of sub-Gaussian and sub-exponential random variables that are useful for this work. More details can be found in (Wainwright, 2019).
A random variable X with mean μ [ is sub-exponential with parameters (u,,3) if
B[eM(X-A)] S - 1K 3' B
Note that a sub-exponemtial random has finite moments of any order.
A random variable X is sub-Gaussian with parameter a if is subexponential with parameter (a, 0), where J is interpreted as co. Then a random vector X" is called uub-Gaussian with parameter a if for any unit vector v", Σj=1 xj is sub- Gaussian with parameter a.
If X [a, bj, then it is sub-Gaussian with parameter be See the discussion after Proposition 2.5 in (Wainwright, 2019) for the proof. Let X be random vector, if X, for = 1, --. n are independent and each Xj is sub-Gaussian random variable with parameter o, then it is casy to verify that X is sub-Gaussian random vector with parameter ø.
Let j. j = I,..., n be i..dd random variables and X, is sub-exponential with parameters (y))b;). Then we can verify that Σj=1 X, is sub-ex exponential with parameters (v /ド=1a3u maxigign by). The following lemma characterizes the tail bound for a sub-exponential random variable, which is by Proposition 2.9 in (Wainwright, 2019).
Lemma A.1. Let X be a sub-exponential random variable with mean p and parameters (v, B). Then
V²
eexp
0S15
2v²
3
P| al 2
(24)
v2
2 cxp
t>
23
3
A.2. Preliminaries on divergences between distributions
Let (u) and (2( be two distributions over U. the KL divergence is defined by
log (U) p2 (U))
Du(pi = Ep,
The x2 divergence is defined by
(plll) -1
)
X2 (pr (w)llp(()) = Epg
(2)
By the convexity of the logarithm function, it is easy to that
Du(pi(w))pzll s (()(p(())
(25)
A.3. Protocols for Estimating a Parametric Distribution
Suppose that we want to estimate a parametric distribution Pw over finite set W with size k = [W] The setting is the same as Section 1.3, except that the task is different. To be precise, there are m encoders and the i-th encoder holds n i.i.d. samples ) Each encoder can send a length message to help the decoder establish an estimate pw (w). such that the L loss Blllsw pw] [| is minimized.
The following lemma is essential, which characterizes the optimal error rates (up to logarithmic factors, cf. (Yuan et al., 2024)) for the above distribution estimation problem.
Lemma A.2. For the above distribution estimation problem, there exists an interactive protocol ASR(m, n, k)) such that for any Pw E Aw, the protocol outputs an estimate pw satisfying,
12

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
1) ifk S n, m(1 A 1000k log" N, then Blllöw Pw [2
O
mml
12) ifk n, 1 log and ml [logn] 2 k, then Rilliw Pw
1
O
k Loo n mni
V
mm
2) ifn & (2'- - 1) n, 2 and ml A n) 2000n log" N, then Elllpw - Pw =
log( d + ml
1
3) if (2' 1) n, 2 4 and ml A n) > 4000m log N, then Billww Pw = O
22'mm
2
The cases in 1-3) are achieved by (Yuan al., 2024), see Theorem I therein for the proof. The proof of I') can be found in Appendix A.3.1.
A.3.I. PROOF OF LEMMA A.2
It remains to show the case 1 I').
The Estimation Protocol
Let = Togn n A and m' mn= Lm Each encoder divides its bits into frames, and there are [logn] bits each frame. Then for each w E W, each frame sufficient for encoding the number of w among the n samples at each encoder. We can allocate mı' frames to the w E W, such that the frames held by the same encoder are allocated to different w, and exactly m' frames are allocated each W.
Each encoder then encodes the number of among its samples to each frame, where the frame is allocated Then it connects all its frames and sends them to the decoder. For each W, the decoder computes num(ww by summing up the number of w. where each number is encoded in one of the m' frames allocated to w. Then it computes Pw( (w) num((w and outputs the estimate Pw- m'n
W.
Error Analysis
For each w E W it is easy to see that num(ww) is the sum of m'n i.id. random variables, and each of them follows the distribution (w))( So have Ellöw(u (w) pw [w]]] O m/'n and [[ll@w Pw (w)(w) (w) [[
1/2 O O log mnn mz completing the proof.
A.4. Analysis of the Balls and Bins Model
Suppose there are n balls and & bins and each ball independently put into a bin at random. Let V, be the number of balls the s-th bin. Then is a sum of i.i.d. (ern(H) random variables. are interested in the maximal number of balls over all & bins, namely maxi gaga V,, which related the strong data processing constant in Section We can obtain the following inequalities characterizing cases n and n 2 k respectively.
Lemma A.3.
Let ls 2 n and E N be sufficiently large, then
(-9
max V, 2 c 1 S keep 15e5k
(26)
2
2. Let 2 k and e N be sufficiently large, then
keep (- cn
P max V. 2 Vs 1....,A
(27)
15eSk
8k
Proof. By the Chernoff's bound, we have
P 2[v22(1+ exp
(-2 (2)k)
(- cn
>0
(28)
Then we can derive the desired inequalities as follows.
13

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Proof of Case I: By letting d' [1 in (28), we have
k n + c) 1] n2
PIV. 2c Sxxp
[1 + 6) + 1
(#))²
22 exp (- -
exp
By applying the union bound, complete the proof.
Proof of Case 2: By letting d' in (28), we have
(c 1)
PP V,
S exp
(c+ 1)h:
(5)
cn 8k
S exp
exp
2ck
The conclusion is then implied by the union bound.
B. Error Analysis for the Protocol in Section 4
B.1. Proof of Lemma 4.4
The overall error can be bounded as follows.
f1 <2 (BII) 131 + =EII -11)1
E| fl. -fHsl 2 2-2HH
K
El f
fnsl?1 K-2r,
where the second inequality is because (Δнz) ) is orthonormal system and (10) in Lemma 3.1 holds, and the last equality by K 2f, Then suffices bound the first term EK Ellfu= fH By the bias decomposition, have
K
K
K Σ
Σ
Blls - 1Hal9 1ii1a-JHaaP11
Σ fH. - E [m)(())]
E
[H - [fma(X)]
(29)
suffices to bound two terms on the right hand side of (29) respectively.
The first term in (29): Note that
fHs E [FHo((X]]
= E [H) FHo(X)]
<E I Iin (x) - Ko)
P [[fmo(X)]] Ku + a) da
By Assumption 4.1, (X) is sub-exponential with parameters (VarK, Hence fIIs(X) has finite second mo- ment, i.e., for some Σ > 0,
(X){ ~ r
(30)
Note that
Ko cak' log x K log N k KK
CVK K
14

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
and by (30),
= B[]fH,(XX|]] = 0(1)
Then by Lemma A.I we have
[[ Ko + aa da
P
(-Ku
Ku + [-Kut0 da K2 exp
Ko (-4 (Aogk3s
2exp
3 VKN-100
where the last step by the choice of og with og 400(r++))2, and then Ko cg log N > 100(r+1) log N (4c22k3)). Then we have
K
Σ
fHe - [x)o())) 3 - N 3 K-2
(31)
since we have K 3 N by the choice of K in (11).
The second term in (29): Since V(s)|X Bern(QH((X)) and (X)
[x)+K)
then
2Kg
1]
Σ
2Ko
Σ
pw(s's (s', (0w(())
1
Σ
2Ko
E Is=s'
Σ
PIV = w|
2
(=t(s)=1
s':sENNo
(:u(a)=1
(P]((s)=|[x}) - 1
Σ
2Kg
11.sss
N'
QHa(()) -880-1111 1)
Σ
1=s 2Ko
d'
Σ
(R(Is=o(na(X)))
E
E
[Ho(X))
E
where the last equality is because (x) = (X) = 0 for s & NHs. Then by (13) and (14), we have
fH.. - E (x)]
pw((',u) pP )
Σ
2Ko
Σ (=
1 -DDw((0)) ps u)
Σ
2Ko
Σ
s'iEEN
=K?
Σ
Σ
(Dw(s',0) pw((',)) +
Σ
(pw(s', dw (w,(
d'ssENna
(:((s)=1
0=
$K3 + 2522
Σ
- - 1)
(
15

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
where the last step is by the Cauchy-Schwarz inequality and [Wrrl s 28 2. By taking the summation, we have
K
fH. E [[ua(x)]]
525 + +2)228+2
Σ (éw(s',u) pw u))
s'=1 s:sEN
<2 + 22)2225+2
liw -
Taking the expectation, we have
k
Σ
[n. - E [x)(
1 K log² NNllw - -Pwl1ž
(32)
Completing the proof: Combining (29), (31) and (32), we have
Bl.Sn - K- + K log NE [léw pw [
B.2. Detailed Error Analysis for Theorem 4.2
B.2.1. ERROR ANALYSIS FOR CASE 1
Recall that (2'mn) 2-12
S K < (2) 2712 225+1
m 2 21+1 and 1 S 2r41 log - Then we can verify that [W]
22842
225+2, K 2 (2'mn) 1-17 > (2'- 1) n and ml1 A n) 2 m > 4000n log
N. Hence the condition of 3) in Lemma A.2
satisfied, and we have B|llpw Pw 11 I
2 K.
2'm
Then by (16) in Lemma 4.4 we have
228+2 K
ElllS -1 + KKlog N
mn2! 3 (2' (2)mm))= - log N.
B.2.2. ERROR ANALYSIS FOR CASE 2
Recall that (1m) 225+2
< K
(mm) I 243-1
and suffices consider the case for
2r41 2 log ..
2r-1 S n. Then
m
we can verify that (2' 1): n W
225+2 K 2 (Im) कंं 2 n and m(1 An) ml 2000n log N. Hence the
log( 22842.x +1)
condition of 2) in Lemma A.2 is satisfied, and we have Elllpw Pw 11 z
ml
Then by (16) in Lemma 4.4 we have
B11 - 3 K Klog² N log( 228+2.K 1) v
1
(Im) I log N.
ml
mn
B.2.3. ERROR ANALYSIS FOR CASE 3
First let m > 225+2, 2000 log² N. Recall that 225 log N $ <
Im
12512-100018 N. n >> m m and 1 < <
Im
Then we can verify that [W|- = 225+2 < Im S n and m(1 WI) = ml
1000 log² N. Hence the condition of 1)
in Lemma A.2 is satisfied, and we have Elll pow Pw 2 2 V
By (16) in Lemma 4.4 and n 2 (ml)2r+1, then we have
22542, K
1 .111) 3 (lm) -2r log 4r N. mn
EH H fl 2 K log² N
mnd
16

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Then let > 225+2. 2000 log" N. Recall that 22842.2000 log? N I K < 225+2-1000 N n > 2r+ In this verify that 1 > logn, [W] 225+2 K Im n and ml [og
and I l 2:TT
m
ml
[W] Hence the
2lg
condition of 1') in Lemma A.2 is satisfied, and we have Elllpw Pw 220+2 12 By (16) in Lemma 4.4 and n 2 (ml)2r+), then we have
man
[225+2, K log K)
Blllf fl K 2r + K logg N
V
= (lm)
2r llog" 4r N.
mnd
mn
If m S 22242 2000 log N and & 228+2, 2000 2000 N, then ml I logg N and the desired bound is vacuous.
B.2.4. ERROR ANALYSIS FOR CASE 4
Recall that 2000 log N I K < 22372. 1000 1000 N. and it suffices to let a V1 S v n 2n+
(Imn) XPi2
(Imn) 1rp
2000 log N 2
mn
Then we can verify that [W] = 228+2 K < (1mm)=44 I and m(1 A (W]) ml 2 (mmn)
2 > 1000 log N.
Hence the condition of 1) Lemma is satisfied, and we have RB[lpw - pw 1121 3 225+2.
mnd mnn
By (16) in Lemma 4.4, then we have
225+2 K
B|II""
11 - K log" N
V
x (lmn) - log
logtrt2 1r+2 N.
mnl
mn
This completes the proof of Theorem 4.2.
C. Proof of the Lower Bounds in Section 5
C.I. Proof of Lemma 5.4
Let P be an (m, n, prootocll defined in Section 1.3, then we have
sup feF
Elllf- f 2
2 Billfo fzx 11
=Bllffp - fz 112]-
First, we convert the estimation problem into a testing problem by the following procedure. Let
2 arg min llfe
fell2-
Then have
115z - f2+ S11fp - fzz ll2 + 1llo f2
<21 S21 2|
fzz 1 Hence we have 4B|I fz 122 2 21
Next establish lower bound for the average testing emoor for any 2" [1,,1]], since (W have pairwise disjoint supports, have
f1
f2n =22k-(244) (2r+1)
| 1e,
2 k- (2n+1)
1 Le,
17

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Hence have
Ellíp fzz 1121 2 Elllfz- - f2x 11
(33)
1 2 x2 12++1)
P[Z + Zz].
Since 2 -x 8m
2 is a Markov chain, similar to Lemma 10 in (Acharya et al., 2022), we have
k Σ
k 5 a=1
IZzs:
21-h
pIZz # Zx]
(34)
k ==1
where ha(p) - p p- (11-p)_a loga - p) is the binary entropy function. By the assumption that 1 2. then by (34) we have
E.=1 I(Zs; BT))
-
&
k
Σ
PlZ.
+
2.1 2 10'
k 2=1
Thus by (33),
BIll 12 11 z
のー
Then we have R(m, n. n,l,r) 2 2-22, 2 completing the proof.
C.2. Proof of the Centralized Bound for Case 5
Consider the centralized bound R(m, n, ž=2 -لं for Case 5. Note that the bound and the following proof is still valid for all the other cases, though it is not tight except in Case 5. It can be immediately obtained by letting A (100mn0C)) शमा in the following lemma.
Lemma C.1. Under Assumption 5.1 and 5.2, we have + E.h I(Z.. BT)) I
mnCa 2
Lemma C.1 is derived from Assumption 5.1 and 5.2 as follows.
Proof. Let ((-1) ===1,8 L,.... k, where de's is equal to 1 if and 0 otherwise. Let O be the element-wiss
product of sequences, i.e., f2, kk O {=)) {2.21) Then ² @ c, is obtained by only flipping the sign of 2, in
By the Markov chain Z - Xmm Bm and the data processing inequality, we have
( <I (Zz; X
Pze (x=")) (I + pP one (z)m)) ]
<E
Dxm=
DDxmm (pze
| patoon (2 (x))))
E DDxmm (pztae, mm (1m (M)))
2
mn
E [Dx (pztae, (x)l
2
mn
E
| x]xy (Ds,- (x) (z))lp....
2k
mn
E,
[Ep,,-z. [-Ios, (x)
2k mnC'
21
where the second and the third inequality is due the convexity of KL divergence, the last equality is due Assumption 5.1
and the last inequality due Assumption 5.2. Then we have > T(Z,,, BT) S 21 completing the proof.
mnCa
18

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
C.3. Proof for Case 3
-2r for the case Since Ze 1, &t are i.id. random variables, have [Zg 11= 0. Then by the chain rule, we have
We show that R(m, n, (,r) 3 (Im)-2r
k
[Zz Bm) S
1 (Z.; BTh Z1:0-1)
Σ I (Z 3 11:--1)
= =I(Z;; BT)
<H(B") S ml.
By letting & 100ml, we have 1 I. E.= I(2,; BT)
1 This combined with Lemma 5.4 completes the proof.
C.4. Technical Bounds by the Terminal-Wise Likelihood Ratio
We establish two technical lemmas to prove the remaining bounds. Recall that the terminal-wise likelihood ratio (for testing xe) defined to
C (x Paroe, (x*)
(35)
D2 (x²))
Then by Assumption 5.1, the terminal-wise likelihood ratio L (x*) can be written as
n II
Oat (xz)
Pa. Pa- 2, (x²) Po.z, (x,)
Cest
II
Pat p.((Ig) 5=1
Jit, E
and hence
log( Ce,22 (x*))=
Σ
La,,,
(36)
In the following two sections, we recall Lemmas 5.5 and 5.6 and give their proof respectively.
C.4.1. EXPONENTIAL BOUND
If Ef+ (X*) - 1) has an upper bound, then we can get an bound for E.= T(Z,; BT) that is exponential in as follows.
Lemma C.2. [f - 1)31 < a² for any = 1,.... k and 2
E 1-,,1 then we have
2'ma²
1 [Z,; BT) -
(37)
2k
Proof.
Similar to the proof of the centralized bound in Appendix C.2, we start by observing that
1 I(Z,; 3")
<E
+ (2
(38)
E (o (pztoe, (bt) (bm"
2
1
E Dioo1p (Pztoe, (b. B 1) (by B15-1))]
2
19

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Note that
Pz (be) B1a-1) E2 [p(b;]X; B1S-1)] = Ezy [p(b,) B1a-1))
and
oze (bi)Bi E Bzooe [p(b//X,, B1a--)]] = Ez [C,, ( (x"))(b;lx"" B1--1))
Then by (25) in Appendix A.2, we have
D1o,11' (Pzroe, (4: 1)p22 (b:(Bi:i-)) Sxio,11 (Wz* (b: || (b:) B B1:i-1)
(39)
[L (X*) 1) p(b, X", (ialiXXBBiiia 1))=
= Σ
Note that
By [C, (X²) 1] 0,
(40)
By [[ 8, (X*) - () (X") 1)] = 0, Vs * *
By (40), {1, (X() - 1, 2 (x 1,... L (X - 13 is an orthogonal system. Then by the Bessel inequality
and Ez [[ (X*) - 1)3] S a² for any 8 ,,.,. k
Ez [[ (X") - p(b;) X", B)=-1)))
(41)
<a Ea (b, B1:--1 a E2 1,t-1))"
where the last inequality is since p(b,) X" B1--1) E [0, 1]. Combining Equations (38), (39) and (41), we have
m'm (Zs;Br) <
2k
completing the proof.
C.4.2. POLYNOMIAL BOUND
(..,"("") is bounded with large probability, then we can get a bound which a polynomial of I, summarized as the following lemma.
Lemma C.3. there exists some Boolean function F((x)) such that,
1. (F(X)) = 0] < 61 < for any z E (-1,1)};
2. E(x*)= 1 if and only if CC (2 1 S for any z² E [f-1,115 1,..,,..
Then we have
b h
I(Z,; BTy) I m(log 2)8F + 81) + 16m153
(42)
k
The nature of Lemma 5.6 is strong data processing inequality with the strong data processing constant 1653. To give tight bound of the constant sufficient for deriving the bound for Σ5 I(Z,; BT)) ), we need to bound 8, and 62 simultane- ously. The task can paraphrased as finding a tight bound Lx,** - that holds with sufficiently large probability. Such problem solved by relating it to the balls and bins model, detailed in the next subsection.
20

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Proof. By the chain rule of the mutual information, have
I(2 I(Z B; By (B.-1)))..
(43)
Recall that each sample x = (t, E [0.1] x V. Let i = [kt] for such z, T = [KT] and Tú = [KTT for = 1, .....
j 1,.... correspondingly. By Assumption 5.1, T." is independent of (Z., B1.-1), hence [(Zs; T,") [1:-1) 0. For each term in the summation in (43), we have
I(2,; Br [(2,; B, (7:
=I(2,; 1 (B:-- + (2,; B T.")
= =I(Z,; B T7').
Then by the assumption I on F(xx)),
I(2,; (12, (T)
=I(2,; ((2; 1 T F (x.)))
((((B(X)))++[EEC)) 0 - B, E(x:)) = 0) = 1]- -( 1))
B.)L E(x,') =
<h(81) + I(Z,; B, E(X 1).
suffices to bound the last term above. Before doing that, we first define the conditional terminal-wise likelihood ratio for any x" with E(*") = to be
Prroe, (z" E(x") 1) 13 (1x E(xx) = 1)
C (x())" =
(44)
Then we can derive the following useful bound for La (x= (c(""",E(s")) = 1). By the assumption 2 on E(x"),
Poroe "(,") 1) EsaGe, (XT)) ( p (in, F((x²)) =
82, 1 + 82).
Eyt I [
Then by the inequality jab 11 S 11 |a| bb- 1/,
Ca,eN (x" 17", E(xx) = =1) -1--11 -1
ph (t" F(xx") =1
-L, (x*)) -1
Prr (in, F((r)) =
(45)
+ 8z
82
1 1 82
<482.
Now consider the term I(2,; B& B15-1, TT, E(X?) = 1). Similar to the proof in Appendix C.2,
1 [(2:: B, E(X.) =
S 2 Di0.11' P2t (b.) 11:-11 7,, F(XT) 1)llpz (ba 7 E(X.)) = =
E Dio.y O2rre, (bilBBii-1, 7Th E(X")
1", E(X") 1
2
21

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
In the above equation, further note that
pz T", = -1)
Bis-1)]
and
P2 oe, 7*, E( =1
T",
E
Pzt === (X"")",EX(")) = 1)p(bli",,BBss>
Then by (25) in Appendix A.2, we have
Pio.jj' (pzroe, (b, E(x") 1) ( (0, =1))
SXoo11
7", F(X 1)]1p=* (b:l B :1:1-1, T F(X") -(x)) =1)
[ (BPAA(TM.EEXX))))) (X"I"" E(X* +| 1)pbb; BLa-1)l)
Σ
(2 [(X*)==))((((b 1X", B15--1)
6.E(0,1)
Combining these results, we can obtain that
I(,;; Bm) S m(h(61) + 61)
27
(46)
E ( ((X")))))))))))-)-
-((")=])) - (X E(X = 1) - (x, B (1m (p(b; X", B1.i-1)
1
E
2k
i=1
b.
s=1
The following transportation lemma is useful for bounding the last term. can be proved by well-known arguments (cf. Remark 4.25 in (van Handel, 2016) and Lemma in (Acharya al., 2023)). The definition and related properties of sub-Gaussian random variables can be found in Appendix A.I.
Lemma C.4 (Transportation Lemma). Let P and Q be two measures on probability space U and P < Q. U is Sab-Gaussian random vector with parameter a under the measure P. Then we have
< D(Q(P))
(47)
Now let X be i.i.d. random variables and each X; is generated following the distribution Pz* (-I7", E(X") = 1). Then by Assumption 5.1 and (23), f (X"(T". F(X") ) = 1) for = 1,... A are independent. By the discussion in Appendix A.1, since each C. (X"[f", E(X") 1) 1 is bounded by 48g in (45) and has mean, it is sub- Gabssaassinn with parameter σ. Then we have (C.. ( E(X") = 1) -1)5_ is a sub-Gaussian random vector with parameter a. Applying the transportation lemma to = (C, (X" (X"
1) 1) P = Pz 1-1T", = 1) and
p(h,)..... then we have dr Ep B1
=( (Co, EX" 1) - 1)p(bi/X" B)
E ((x))))))()==)) (p(b; X", B1:--1)]
p(b,|X", B
<160 E E ((x)=))))))
p(b,|x",
B1 ((+ log
(p [p(b,|X' B1--1)1
22

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal This combined with (46) imply that
k
Bm)
A
5m(h(6i) + + 1662
m
BI ((X") = 1)
k
i=1
Sm((log 2)09 + +81) + 1662
H(.))
k
5m((log)68 + +51 + 16m153
k
completing the proof.
C.5. Detailed Proof for Case
By Assumption 5.2, since و = Okk") >> 2 we have
E Ep,,, [exp(2Ls, (X))] S exp(2n²).
Then by (23) and 1 + x 55e $1+ 2x for 0 S x 1,
Eg (X"))²²
=E,,
exp Σ
ET El
R
E Po.e,
lexp (2 (x)1)
Enj= 23 221
exp
2
T 2
j=1
Σ
n
(1
n-r exp(2u²r)
1
+ h
(exp(2u2) - 1)
S exp
12
(exp(20²) - 1)
Ann²²
exxp
k
Then by (40), we have
[Anv2
8n
(fo,,e 1) = E (CC (X²))) -1 S exp
Sexp
k
as long as ine? k
4Cin < 1. Let k: = (Cymm2)) ماا and a² Snu? k
where C4 is a big constant. Then by satisfied. By Lemma 5.5, we have
8Cin R
m > 2r++1 we have 1e > (C4mn) कィेद ) >
(Ca) अमं n and hence 4nz" <
2 mn 1 k2r+2
I(Z:: B
5
Then by Lemma 5.4, we obtain that R(m, n, l) 2 (mm22))=#t)
23

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
C.6. Detailed Proof for Case
Recall that
+++1 V
S15n. n
(48)
m
Let C1000C log" m) मो.,, where Cs a large constant to be determined, and then we have
V F S k S m
(49)
Let
E(x") = 1, if (6s. - 1| < 20, log logmlmm m. V2 {-1111),, k,..,
0, otherwise.
Then we have 82 < 3 log m immediately. To use Lemma 5.6, we need to bound the quantity Px+ (B(x)) = 0] for any z Note that by (23) and 20, log m k-r log m + 0, we have
(B(X") = 0} = [| = (X*) - 1| S 2C,3 log m, 4 E (-1,1)* 8= 1,... k}
C
S ( log L, f (X < Cs m, V2t E (-111} 11x, 1,,.., k
c
Σ
La,,, (Xi)
< CBB log m, Vs = I, 2o E [1-1,1}
(50)
< Cz log m 1)
Σ
LI (X,)
J:T +1
Σ
Lone (Xx)
2 Cr,Bogg m
Define the event es.,. = [ La (X,) 2 ObBlogmi m cal distribution for (1kt,) 1)}== be
For any x" where xy. (tj.,8). define the empiri-
Vx(x") Σ bE(+
(51)
for any s = 1..... k. Then define E'(x") based on (V)(*")). by
1, if Vz(") s 200 log m, Vs I,...,
E'(x")
0, otherwise.
Note that by the union bound and (50),
P [E("") 0] < PP,
Σ Σ
=1].
(52)
The first term can be bounded by letting Cp log m in (26) where Cp is large constant to be determined, which yields
E.+ E' (x")) 0 < k exx
Co (- 2
log m = km Co
(53)
Now consider each term in the latter summation. Conditioned on j = 1,..., n, (X1)²= are independent. Further- more, on the event {E'(X") = 1). Vx(X)) I Co log m for any = 1,..., k. So we have
V.(X")
Pot Es,,, |KT 1, 1,... n F'(X")= =
Σ Ø=1
T1s,2, (X))
2 Cs.3 log m
24

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
where (x)) are i.d. random variables generated from the distribution Pa.s.- By Assumption 5.2, [)(("") is sub-exponential with parameters (vCor² log m. (3) and E
Lo.,.
|E Ls,e, (x,)
Cn In By (49), we have
C6v² logm
C6Cik
log m
S C3C2k
log C3B log
B
C2k
long as C3
CaCi C2
and
CaCa log
C5 log m = = log >> k log x
k2r
Then Hoeffding's inequality (Lemma A.1 in Appendix A.1) 1) implies that
Ps
[KT = n, E' = 1] s 22cx exp
1 log m
2
2m
233
Thus we have
Pst [E,,2, (' = 1]
= E2'*
P2* Ee,,.
[KTjJ.j = ((x") =1 $1]
Exx))
(54)
Ss
2mm
Combining the bound (52), (53) and (54), we have
P.t (x(") = Skm Co 4km 9
S m
where the last inequality is by (49), as long as Cs and Cs are both big enough. Then we can choose m -00 By Lemma 5.6, the inequality (48) and (49), finally have
16ml0²
(Zos; BT) Sm((log 2)0 + +81) +
6407m18² log? m
<4m
50+1
k
64 log" m k2r+1
<4m
2'
where the last inequality is by the choice of A: (1000C3 C3 log? m) ग Then by Lemma 5.4, we complete the proof.
C.7. Detailed Proof for Case 4
Recall that > $ and
T2 2
n 2r+1
V13l5
A (mm) <
(55)
Let (1000C, (1000C)C7mll) ž④④ς log 2-41 n, where C7 is large constant to be determined, and then have
k < n log² n < n²
(56)
and
2r++1 2 (mnl) 2-12 log
2rl1
2r 2r+3 > n log 2r+3 n >> n log" n.
(57)
Let
Crv2nlog* V2* E (1 1,... h
if (x*) - s / (x²)
F((x)) =
0, otherwise.
25

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Then we have 82 5 v
Crv'n log
immediately. To use Lemma 5.6, we first bound the quantity PP 0] for any
z Note that by (57),
CrePn log log
O. Then by (23) and similar to (50) we have
k
Czu2n log n
(B(X*) 0) =
Σ
Ls,,, (Xx) 2
(58)
k
s=12,=i1
Let Es EI La (Xi)
v logt
Define E"(x") based on (Va(z")) (cf. (51)) by
Can log n
1, if V=("))
<
Vs I,... k,
E'
k
0, otherwise.
Then by Equation (27), we have
(- C.nnloog' n
Cs log n
-n +
E. (x"")) = =0] < kexp
< k exp
(59)
8k
8
(X3 =1 are independent given [KTzJsj ,,,.,, n. And on the event {E'(X") = 1}, V.(X)) <
Can for any
k. So we have
ViXX
Cru2n log'
Pgt Es J.T 1,.... n, E'(x") = P
Σ
Ls,5 (X)) 2
where (X1) are i..dd copies of X By Assumption 5.2,
ΣØ=1 EV-(x*) L,,,, (X,) is sub-exponential with parameters
Che Ing n B) and E
E La,e, (x3) S CaCan Iog" A3r
By (56), we have
Cau log"
log 1r+1
log" k2r+1
Cru2nlog"
x V
and by (57), we have
Crv2n log n
n log n
n nlgg*
CaCanlog" n k2r+1
k2r+1
12r+1
x
Then Lemma A.1 in Appendix A.1 implies that
Crvôn 4k:
Pst Es,s. [AT]J.J = 1, .... n, E'Xx)) = 1] < 2exp
Cr log n
= 2 2exp
2n
2Cxu log
8C'
k
Thus we have
P. E0,,, (E(X")) = 11]
1] 5 2n
80.
(60)
Combining the bounds (58), (59) and (60), we have
[E(X) (E = Σ Σ E,,
1]
<kn Co + 4kn
scg < 100(++1))
where the last inequality is by (56), as long as C2
C₁ and Cs are both big enough. Then we can choose -100r++))
26

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
By Lemma 5.6, (55) and (57), we finally have
k
16m183
I( B 2n²+11 =nlo+(((lg2)) 2) + +51) +
k ==1
k
64C7mnlv2 log" n
<4n
50+1
64C Cymnnd log'
<4n 19
k2r+2
1
2²
where the last inequality is by the choice of k = (1000C;Cymnl) 2-12 log2r+1 28+1 and r > 2.2 By Lemma 5.4, we complete the proof.
2
D. Proof for the Specific Cases in Section 2.3
D.I. Proof of Corollary 2.7
Let T = X and Y then X (T,Y).
D.1.1. VERIFICATION OF ASSUMPTION 4.1
Let h(v) = y, then (x) Φn. (X). By 1) in Lemma 3.1, we have [xH) S C. 2 CVK for some C>> 0, hence (X) is sub-exponential with parameters (VC*K, 0). Moreover, we have
BX]H((X)]= = L. (())))((()d = SH..
hence (X)(X) is an unbiased estimator fH..
1.1.2. VERIFICATION OF ASSUMPTION 5.1
For any 1,... k. 2, +1 and 1 El we have
P. (xx = Sea = 1 + ch (r+ }
vi (x)
1 T. k -
Note that
f (1+ek (1+t)= do = 1,
and by 1) in Lemma 3.1, + ek (x-(r+ 2r 2 1- llek 1 b) 26 2 1 - 0. Hence Pe, (x)
ek ek-((++)) (x)) a distribution function on |= El
D.1.3. VERIFICATION OF ASSUMPTION 5.2
For any 1,..., k, 2g = +1 and I E [=-1] k.
1 ck (r+ 12
2ck 2ck- (r+ 4) 26 (x)
Le,5, (x) log
log
1
1 ck (r+ 2222)/
+ ek (rt 4) 2oth
27

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Then for X Ps.a,* by 1) in Lemma 3.1, IL,,,, (X) S C²k- T for some C' 0, hence L,,,, s, (X) sub-exponential with
parameters (VC2k- 2r 0). Moreover, by the inequality - x² I log(1 [ - x) S -x for [ < 2' then
+ E ( 2ck (r+ (r+ 2 (X)
2
2ck (r+ 2
E
1 + ck (r- () 2/ (X)
|+ ek (rt 2 2/ (x)
30 4: (2++1)
2 = =
completing the proof.
D.2. Proof of Corollary 2.12
In all these cases, X (T.Y) with T [0,
Nonparametric Gaussian Regression Problem in Example 2.8
D.2.1. VERIFICATION oF ASSUMPTION 4.1
Let h(y) = y, then (X) = ( Note that
E[fn&(X)] = Elon = ((oH.(())(T)) [: (())n.(ttdtt= = fHs.
hence (X) is an unbiased estimator fHs.
By in in Lemma 3.1, we have (6)x(7)] S C - = CVK for some C > 0. Then by 4) in Lemma 3.1, (T)) CL'VK almost surely, hence (H.(T)f(T) sub-Gaussian with parameter C'Lv VK. Since Y ~ ((F(T) 1), we have
((0)) (T)) v) E
Then for any R, we have
(
E
(( E E (T
[
E
se O (TT)))((
Se ==
implying that (X) is sub-exponential with parameters ((2)(1+))2,00
D.2.2. VERIFICATION OF ASSUMPTION 5.1 For any 1,... k, 2g +1 and (t, v) with t ( $. have
(v- fo-day Eog.g..00 (0)
1 k
(u-ek (r) 3) (0))
(2)(x)
2m
b
2T
Note that
4
dydl 1,
JR 22T
Hence pa.,, (x) b (y-ez (y- ()))
0 is distribution function
[ $ R.
/2n
D.2.3. VERIFICATION OF ASSUMPTION 5.2
For any s 1, I,... k, 2, +1 and x (t.g) with =
L.,,, (z) (u + - (z+ - (u (g-ck ck (x++))))))) (r) 25)( 4ek (r+ - 4r+) (x+t)))
28

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Then for X (T Pa,s,, L.,, (x) (ek- y (T). Similar the verification of Assumption 4.1, (T) sub-exponential with parameters (v L eters (vC*k- 2- 0).
0) for some C' > Thus La,,, (X) is sub-exponential with param-
Moreover, by 3) in Lemma 3.1 we have
[ se, (X)]
=4ek (r
E
[E|
(T)
=4ck E
=4ck (r+ fi- 0
<4ek -r+ 1) || - hh ho
1|2
Sk sk- ((+ b) v 2 1 k k-
completing the proof.
2. Nonparametric Binary Regression Problem in Example 2.9
D.2.1. VERIFICATION OF ASSUMPTION 4.1
Let h(y) = y. then (X) (T)Y. Note that
[X]n = Elon = =E(on,(T)((T)) [: (())nn(ttdd = sHs
hence (X) is an unbiased estimator of fHs. Morcover, by 1) in Lemma 3.1 and E {0,1), we have [fn,(X) S
C. = CVK for some C > 0, hence fx)(X) is sub-exponential with parameters VVC2KO00
D.2.2. VERIFICATION OF ASSUMPTION 5.1
For any s = 1,... k, 2, = 11 and x = (f.y) y) with t E [ El. we have
(x) -t ? ek (r+ (r+b)) (0)) + - -k---+))
Note that
Σ to + ch (+tt)) + ck 2++b)) - dt = 1,
ch Hence Ps.z. (x) k [ ck (r+ 2/ ck- (r+
(t)) (+))
0 is distribution function
[ f 10.
D.2.3. VERIFICATION OF ASSUMPTION 5.2
For any == 1,... k, 2, = +1 and r = (f.y) with t E [=-1] : d)
( ck ck- (r- 1), (1)] +6 12, (1)
Le,z, (x) = =log
( + ek- (r- +) 2, (t))
[I)
2ek ( +)+ 2i (t) 21 21,=1
= logg
1+
( ck ck- k y-1 + +1 ek 2) 24 15 (1) n
Then for X (T,Y) Pa,z,r by 1) in Lemma 3.1, L.,,, (X) I -'k-r for some C' 0, hence L,,s, (X) is sub-
exponential with parameters 2rr O). Moreover, by the inequality -r x² S log(1 x)) S -r for |xt < }
29

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
then
2ch: (r+ 2r (T) 2211-111-- =
E Ls,,, (X)]l S
( ck -0+ 1
(2 ck (r+ 1) (
27
- (T) 21y
+E
( + ck (r+ 2 (T)) ---(k+++++
ek 2 25 [I))
30 + k (22r+11) 2º x k 2r
completing the proof.
Nonparametric Poisson Regression Problem in Example 2.10
D.2.1. VERIFICATION OF ASSUMPTION 4.1
Let h(y) y, then (X) (T, Note that
(X)) = E(o = B(on.(()f(T)) [: f(t))n.(t)dt= fHo.
hence (X) is an unbiased estimator fus.
By 1) in Lemma 3.1, we have (6Hx(() S C- 2 = CVK for some C' > O. Then by 4) in Lemma 3.1, 10H (T)(() S CL' almost surely, hence on (T)[( is sub-Gaussian with parameter CL' VK. Since YIT ~ Poisson( we
have ( T) e (0..))) -20.. vX For any with [V] < CVK we have (T)H S
1 and then ( (THs(T) 1 (AOH. (T))² Then
E ((
=E E (0
T (11
e (()D (
KX² E (T
Se 10
implying that SHr(X) is sub-exponential with parameters ( L9), CVK).
D.2.2. VERIFICATION OF ASSUMPTION 5.1
For any s = 1,... k, 2, +1 and x = (t.y) with t E [==] $. we have
P.t (x) ke (Co+ok (rt (++3) (Co + ek (rt (rt (t))
y!
Note that
ke (Cotek (rt (1 (Co + ek ()+ ( (1))
1,
y!
WEN
Hence ps.,, (x) (Co+tk Crt os (Cote- =00()))
0 is distribution function
.81 N.
y!
D.2.3. VERIFICATION OF ASSUMPTION 5.2
For any 1,.... k, 24 +1 and x = (t, with /. E [--1 , }.
Co (r+ (r+
L,,,, (x) 2ck -ck- (rt +) (t) yog
Co + ek- (r+
30

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
Now let X (T,Y) Ps, then
L L,,,, (X) 2ck (r+ 2 + Ylog (1 2ck 2)
Co ch (rt 25 25 (T)
By 1) in Lemma 3.1, we have
Co + (r+ (1)
2ek (r+ -r+
4ek (r 200
log
1
-
I CCk
Co + ek (r+ 2
26 260 20 (0,
for some C1 > Then similar to the verification of Assumption 4.1, Ylog 1
is sub-exponential
Catek (r+ ())((T)
with parameters (VC Cf 1.)), C1k-T). C By 1) in Lemma 3.1, hence -
(T) I C2k for some C2 > 0, (r+ ) 2, 1/ (T) is sub-exponential with parameters (vCak-2r, 0). Therefore Lu,,, (X) is sub-exponential with
parameters (2 22) + C2jk-2r, 2 C) (by the discussion in Appendix A.I).
Moreover, note that
C. - ck (r+ (1+3), Co + ck ck- (r+
[B[Ls,,,,
2ek -o+ +) 1) (T)
+ E B[Y[T] log
1 1-C, c c (r+ (r+)))++)2-0 1) 2, (T)
E S(T) log
1 C. ck (rt +)+ +) 2b (T)
Since S(T) O. by the inequality
2r 4x² s log --ا 2x 4x² for [x|| < 1.2
+ 4E f(T) (co (co'ch - 2r )
[E[,,,,, (X)1l $2 f(T)) ck (r+ (rtb),,0)) (T
$2C ck (r+ -1++ +)
fn- + 4L' (o ck (r+ k
sk -k - -h ho- k- < k-
where the second inequality is by 1) Lemma 3.1 and the last inequality is by 3) in Lemma 3.1. This completes the proof.
Nonparametric Heteroskedastic Regression Problem in Example 2.11
1.2.1. VERIFICATION oF ASSUMPTION 4.1
Let h(y) = y², then (X) = (T) Note that
[( [())ns(()d Jn
[[]n((X)) = Eldn =|
hence (X) is an unbiased estimator SHs-
By in Lemma 3.1, we have ( ( C- = OVK for some C' 0. Then by 4) in Lemma 3.1, (HHx(T)((T)) <
CL'VK almost surely, hence @He (TT) is nub-Gaussian with parameter CL'VK. Since Y ~ f(T)xī. we have ()00)(()(03=577))
[T] 21-2NBR.(T)STT
I ((TTTIT)((TIN)) M/ia /CL'K' where the last inequality is by
202 2 I V1
2r for |oc| < 1
For any À with [X] 4CE'R"
1-
E (
=E E
(
<
20
<e
50
implying that (X) is sub-exponential with parameters (V3C=KTT,4CIIVF)
31

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
D.2.2. VERIFICATION OF ASSUMPTION 5.1
For any s 1,, K, 2n +1 and x = (t,y) with & [==1 f. we have
1
k
Cotat -er (
(2) k
2T Co + ck- (r+ - 22,
Note that
u² (Coote (r+ (0t3)
k
dydl 1,
T JR /2T (Go + ek (r+ - 2()
2 (Cotet zomte))
e Hence Pe,a, (I) = 2 (o (00 (0)
O is a distribution function on 1 x R. >
D.2.3. VERIFICATION OF ASSUMPTION 5.2
For any s = I,..., k, 29 +1 and x = (t, with t E [
I1,,z (I) = log ( Co ch ch- (r+
+ 1²2
Co + ch (rt 1) 2 vb
2 Co - c (rt (ot5)
Co + ck (rt b) (t)
Now let x= =TTYY ~ ps,,,, then
2ck - (r+
ck- (1+t))
La,e, (X) =
2 log
1-
+ +
Co + ck (r+ 2bb
C (c+ (1+ (T))2
By 1) in Lemma 3.1, we have
2ck 2ck- (r+ 20
2ck (r+ (x+
log
1
C
2
Co ck (r+ 1) 22
Co + ck
11 (T((
for some C1 > 0. Hence
1/2 log
1 Cotek- (rt (x))
is sub-exponential with parameters (VCtk-2r,00 (0)) By 1)
in Lemma 3.1, we have
ck- (r+ 2) 22 22,
COkk
C3 - (ek (r+ b) (s
ck b'e
Then similar to the verification of Assumption 4.1, Y2 with parameters (V5Ckk-21 L 4C2L'k (V(C) + 5C2 2r, AC2T/k-T (by the discussion in Appendix A.
sub-exponential
C2- (r (lt (T))
Therefore Lu,z, (X) is sub-exponential with parameters
Moreover, note that
Co ck (k+ (1) )] + E.
(r+ (2
[B (X)]I
E
log
E[
Co + ck
+) 2g /
CB (ek (r- 4) 2it 2ith
1
C ck
]]
ck (r+ (x+()))),,0111
E
log
+ E f(T)
2
1 + Co
ck (r 2, (t)
C3 - (rt)
32

---

Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
For the first term, by the inequality -2x 4x² < log +- <
22x 4x² for |2c| < 1.2
o ek (++ }) 2)
log
ck (r+ 2) 21
(r+ x) 20 2 (T) || + 4lb
2 E Co ck
30 2 = kk k-
For the second term, since f(T) > O, then by the inequality x x² S --00 Sx 20r <
E S(T)
C - (ck (4
E [(TT) ck (1+
CO'B ((T)
(+t (T) 2) |
sk - - ph- ho 1 ||2 + b kー
where the second inequality is by 1) in Lemma 3.1 and the last inequality is by 3) in Lemma 3.1. Combining these two parts yields [ T.,,,, (X)]I 3 k-21 22, which completes the proof.
33


Reviews:
[{"review_id": "r9RrvLDRwc", "reviewer": "Reviewer_5nRR", "summary": "The authors consider the communication-constrained problem of nonparametric function estimation, in which m distributed terminal observe each n i.i.d. samples drawn from some distribution parameterized by f, and each can send a message of L bits to a central decoder, which is then interested in estimating f under a minimax quadratic risk. Previously sent messages are observable to all terminals (a blackboard model). The work characterizes the minimax optimal rates under certain regularity assumptions for all regimes, and identify phase transitions of\nthe optimal rates as a function of (m,n).\nThe upper bound is an algorithm that is constructed of two layers: an outer layer that converts the original nonparametric distributed estimation problem into a distribution estimation problem, and an inner layer that estimates the parametric distribution. This is achieved by a clever reduction and invoking protocols for the parametric density estimation problem. The layer bound is information theoretic and consists on analysis the balls and bins model.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your very positive assessment and the suggestions. We are going to revise our paper according to your suggestions in the following aspects.\n\n1.  Adding more details to Sections 3 and 4 on wavelets and upper bounds within the space limitation. The last paragraph of Section 3 that provides preliminary results for the lower bound will be moved to Section 5.\n\n2.  Modifying our paper following the other minor suggestions. The only exception is Remark 2.3, where we consider the case $n = 1$, hence $N_{ess}$ is actually $(2^l m) ^{\\frac{2r+1}{2r+2}} \\wedge m$ instead of $(2^l mn) ^{\\frac{2r+1}{2r+2}} \\wedge ml$ (please also note the $\\wedge mn$ term in the definition (2) of $N_{ess}$).", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods make sense for the problem at hand.", "theoretical_claims": "I checked the correctness of the proofs of the theoretical claims in the main paper and up to Appendix C.", "experimental_designs_or_analyses": "There are no  experimental designs.", "relation_to_broader_scientific_literature": "The authors fully solve the problem by characterizing the optimal rates for all regimes of (n,m), whereas previously only specific cases were considered.", "essential_references_not_discussed": "To my knowledge, there are no essential works not currently discussed in the paper.", "other_strengths_and_weaknesses": "The results are a significant contribution to the field of distributed estimation with communication constraints. The minimax risk is characterized for a large class of estimation problems and all ranges of (m,n) and the proofs are technically complex and require innovative combination of existing results.\nThere are some weaknesses in the way the paper is written. I understand there are space limitations, but I still think elaborating on the upper and lower bounds should greatly improve the paper, in particularly the upper bound and section 3 on Wavelets, which is very terse.", "other_comments_or_suggestions": "Some theorems in the main body are actually corollaries (e.g., 2.7, 2.12),under Remark 2.3 N_ess = (2^l m n) ^{(2r+1)/(2r+2)} \\wedge l m, the last paragraph in section 3 is unclear and should be expanded or moved to section 5, at the bottom of p.8 (last equation), \\log ^ m should be \\log ^4 n.", "questions_for_authors": "I don't have any important questions for the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e7Uobcbnyx", "reviewer": "Reviewer_yQDG", "summary": "The paper studies the problem of distributed nonparametric estimation under communication constraints, where each terminal holds multiple i.i.d. samples. The authors characterize the minimax optimal rates across all regimes, covering the transition from sparse to dense samples per terminal. They propose a two-layer estimation protocol that leverages parametric density estimation methods and wavelet-based estimators, deriving upper and lower bounds using information-theoretic techniques. The results extend the scope of existing works and apply to density estimation, Gaussian regression, and Poisson regression.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading and detailed comments. Here are our point-to-point responses to your concerns.\n\n## Responses to the weaknesses:\n\n-   **... some assumptions seem slightly more substantial than in prior works (e.g., Zaman & Szabó, 2022). ...**\n\nWe want to clarify the rationalities of these assumptions here. We will make the comparisons more clear in the revised paper, by presenting more explanations about them immediately after the formulation of them.\n\n1.  As you see, we want to address the general case not resolved by (Zaman & Szabo, 2022), which is substantially more difficult than some special cases.\n2.  We want to make them easier to verify for specific models. Different from that in (Zaman & Szabo, 2022), all of our assumptions are imposed on single random variables. They also admit simpler expressions than that in (Zaman & Szabo, 2022).\n3.  Even though stronger assumptions are imposed, our framework can also subsume almost all the specific models presented in (Zaman & Szabo, 2022).\n\n-   **The empirical justification is absent.**\n\nAdding synthetic experimental validation is a really good advice to highlight the theoretical contributions. But for the current paper, it seems that there may be little room for that. We will do such experiments in our future work.\n\n-   **The lower bound proof's technical novelty...**\n\nWe give more explanations about our lower bound proof here. Since our contributions are mainly on the matching lower bounds for different parametric regimes, the novelty in the proof's technical novelty was not sufficiently highlighted. To overcome the technically more difficult setting in this work, we make two major improvements on the proof techniques.\n\n1.  Stronger inequalities (eg. Lemmas 5.5 and 5.6) are proved and they are compared with previous methods in Remark C.4 and C.5. We apologize for not including these discussions in the main body due to the page limitation. In short, the boundedness or symmetry properties needed in previous methods are not satisfied for the problem considered here, and we develop effective inequalities to overcome the difficulty.\n2.  We apply these stronger inequalities to new cases that have not been analyzed by previous works. The key to developing lower bounds for all these regimes is to fully characterize the differences in the structures of these regimes. The differences are revealed by analyzing the properties of the log-likelihood ratio defined in (20), shown especially in Section 5.2.2-5.2.3, by incorporating the balls-and-bins model. This is in contrast to previous works, where parametric regimes with $m \\geq n^{2r} > 1$ are not considered and the structure of the problem in these regimes is not investigated.\n\nWe will add more discussions in the revised paper and make our contributions on the lower bound more explicitly.\n\n-   **The discussion of practical communication constraints is somewhat idealized. ...**\n\nIn real-world distributed learning, it is true that the communication between different agents may not use explicit bit quantization strategies. However, it is meaningful to model the practical distributed learning problem by the idealized one with bit quantization strategies. There are two reasons for that.\n\n1.  The basic way of storing and sending messages by computers and any forms of digital communication systems is to encode them into bit strings. The messages may have various forms such as float numbers, but they are encoded into bit strings in their underlying implementation. In this sense, we do not lose too much with the simplified model.\n\n2.  It may seem as if that bit quantization strategies often involve additional noise or compression losses with other ways of quantization like the floating number. But following the first point, as long as digital communications are used, our lower bounds show that the loss in estimation error is only up to logarithmic factors. In other words, the additional losses in the estimation error almost do not affect the convergence rates.\n\nI agree with you that there may be a gap between the idealized model and the practical case, but we hope that analysis of the idealized model can shed light on the understanding of the practical case.\n\n## Responses to other comments or suggestions:\n\n-   **Adding a conclusion section...**\n\nWe will follow this suggestion by adding a conclusion and discussion section at the end of the revised paper.\n\n-   **In the comparisons to prior works, please highlight how the paper's results and proofs utilize prior works especially Acharya et al. (2020) and Yuan et al. (2024).**\n\nWe will revise Subsection 1.2 on comparisons with prior works in our paper, and highlight the contributions compared with prior works Acharya et al. (2020) and Yuan et al. (2024).", "claims_and_evidence": "The claims in the submission are generally well-supported by comprehensive theoretical analysis.", "methods_and_evaluation_criteria": "The proposed algorithm utilizes ideas from recent advances by Acharya et al. (2020) and Yuan et al. (2024) and looks reasonable. However, I didn't find an experimental evaluation for the proposed algorithm, as the paper is primarily theoretical.", "theoretical_claims": "I reviewed the proof sketches for the upper bound, which seemed reasonable. Due to time constraints, I did not check the detailed proofs in the appendix/supplementary.", "experimental_designs_or_analyses": "It is not applicable here as the paper is primarily theoretical.", "relation_to_broader_scientific_literature": "This paper extends prior work on distributed nonparametric estimation under communication constraints by fully characterizing minimax rates across all regimes, from sparse to dense samples per terminal. The two-layer estimation protocol builds on ideas from Acharya et al. (2024), who studied density estimation in the highly sparse case ($n=1$). Still, this work generalizes the approach to handle multiple samples per terminal.", "essential_references_not_discussed": "I don't see additional references to add.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper provides a complete characterization of the minimax rates for distributed nonparametric estimation, filling gaps left by previous studies. \n2. The two-layer estimation protocol is well-structured and theoretically justified. The idea itself also possesses some novelty.\n3. The paper leverages information-theoretic tools, which is a good plus.\n4. The results generalize across various estimation problems, making the algorithm widely applicable.\n\nWeaknesses:\n1. While the results cover all regimes, some assumptions seem slightly more substantial than in prior works (e.g., Zaman & Szabó, 2022). Maybe some further discussion on the restrictiveness of these assumptions is beneficial.\n2. The empirical justification is absent. While the work is primarily theoretical, a small-scale/synthetic experimental validation could illustrate the phase transitions in minimax rates.\n3. The lower bound proof's technical novelty is somewhat limited, as it is unclear if the technique introduces fundamentally new proof strategies beyond adapting existing inequalities and/or constructions.\n4. The discussion of practical communication constraints is somewhat idealized. In real-world distributed learning, bit quantization strategies often involve additional noise or compression losses. How does the model handle these imperfections?", "other_comments_or_suggestions": "- Adding a conclusion section would improve the paper's structure.\n- In the comparisons to prior works, please highlight how the paper's results and proofs utilize (or are inspired by) prior works, especially Acharya et al. (2020) and Yuan et al. (2024).\n- Please also see the prior sections.", "questions_for_authors": "Please see the Strengths and Weaknesses section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8bXCAfb7dE", "reviewer": "Reviewer_nezZ", "summary": "This paper investigates the phase transition in optimal estimation rates as the number of samples per terminal increases from sparse to dense in a distributed setting. The results are purely theoretical, filling gaps in the existing literature and offering a wide range of applications. Overall, the paper is well-written, with a clear and coherent presentation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading and interesting questions. Here are our detailed responses.\n\n## Responses to the weaknesses:\n\n-   **The problem under investigation seems a bit simple. Such one-dimensional problems are way too simple.** $\\hat{f}_{Hs}$ **has a straightforward closed-form expression. ...**\n\nThe model is idealized compared with practical applications. However, there are enough motivations to study it, and we will highlight them in the revised paper.\n\n1.  Our formulation does contain many important statistical estimation problems described in Section 2.3. Assumption 4.1 on the existence of the estimated wavelet coefficient $\\hat{f}_{Hs}$ is satisfied by many specific problems with i.i.d. random generated sample, including density estimation and several common nonparametric regression problems with random design. None of these problems are trivial.\n2.  We assume that the function to be estimated is one-dimensional, but the problem is complex since the function space is infinite-dimensional. As a result, nonparametric function estimation problem can be seen as a useful model of practical applications, providing a theoretical perspective to understand the difficulty of distributed learning.\n3.  Our common goal is to make the model closer to the practical case. This work is only one step towards the goal, but not its end.\n\n## Responses to the questions:\n\n-   **What is the intuition behind the effective sample size given in (2)?**\n\nThe intuition behind the definition of $N_{ess}$ can be obtained by making comparisons between cases with and without communication constraints. If there are no communication constraints, the optimal rate is $N^{-\\frac{2r}{2r+1}}$. In this work we show that the effect of the communication constraints seems to reduce the sample size from $N$ to $N_{ess}$. The optimal rate for the problem is then roughly $N_{ess}^{-\\frac{2r}{2r+1}}$.\n\n-   **Why is it considered impractical to require** $N_{ess}>n$?\n\nIt may be impractical in some real-world system, where it is impossible to put the central decider together with each of the distributed terminals to process the raw data. For example, imagine the case where the terminal is a small unmanned aerial vehicle short of electricity. Since communication is necessary, it is possible that $N_{ess} < n$, where the strict communication constraints severely affect the performance of the system.\n\n-   **What is the specific rate for** $H$ **in each transition phase? ... For the tuning parameter** $\\lambda$ **in the distributed kernel ridge regression, see, e.g., [1], [2], [3]. ...**\n\nSince these two questions are highly related, we respond to them together.\n\n1.  In our estimation protocol, the choice of the resolution $H$ is explicitly given by Equation (11) for each parametric regime in the preparation phase in Section 4.1.\n\n2.  Your understanding of the tuning parameter $H$ is right. Due to the communication constraints, the choice of $H$ by (11) can no longer achieve the optimal rate for the problem without communication constraints, namely $N^{-\\frac{2r}{2r+1}}$. However, it is almost optimal for the communication constrained problem, in the sense that the resulting protocol can almost achieve the corresponding minimax optimal rate $N_{ess}^{-\\frac{2r}{2r+1}}$.\n\n3.  Note that the optimal $H$ has a closed-form expression by (11), as a function of parameters $(m,n,l,r)$. It is slightly different from the case considered in [1], [2], [3], where some of the system parameters may be absent, hence the optimal $\\lambda$ is not a priori and adaptive data-driven method like cross-validation for tuning $\\lambda$ is necessary. The works [1], [2], [3] also provide a good direction for our future work. Thank you for letting us know about them.\n\n-   **... no difference between Theorem 2.12 and 2.11...**\n\nI am a little bit confused with this question since 2.11 is an example but not a theorem. Do you want to ask about Theorems 2.1, 2.7 and 2.12? The difference is that Theorem 2.1 is for the general framework. In contrast, Theorem 2.7 is only for density estimation problems and Theorem 2.12 is only for regression problems. Both problems are subsumed by the general framework.\n\n-   **The work of [4] proposes a different quantization scheme that does not depend on the Fourier coefficients...**\n\nThanks for letting us know about the fantastic work [4] and we will cite it in the revised version. In my understanding, it studies the nonparametric regression problems under fixed design, where the explanatory variables of the $n$ samples at each distributed side are located at $\\frac{1}{n},\\frac{2}{n}...,1$. It is interesting to compare this case with the random design setting (e.g. Examples 2.8-2.11) in our work.\n\n-   **... numerical experiments...**\n\nIt is a good suggestion to add numerical experiments to highlight the theoretical contributions in future works. But for the current paper, due to the page limitation it may be hard to add such an entire section.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "There is no dataset and no empirical study in the paper.", "theoretical_claims": "I did not check the proof line by line, but the arguments make intuitive sense.", "experimental_designs_or_analyses": "There is no experiment.", "relation_to_broader_scientific_literature": "Fill in the theoretical gaps in the literature.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: the paper is well-written and the theoretical results make sense.\nWeakness: the problem under investigation seems a bit simple and there is no strong motivation from the practical applications. There is no numerical investigations to support the theoretical findings.", "other_comments_or_suggestions": "All the examples in Section 2.3 appear quite simple, focusing on nonparametric estimation of a one-dimensional mean, variance, or density function. Such one-dimensional problems are way too simple compared to other works appear in ICML.  One indication of this simplicity is that each estimated wavelet coefficient, $\\hat f_{Hs}$ , has a straightforward closed-form expression, which naturally simplifies the theoretical analysis. However, the practical motivation for this estimation protocol is not entirely clear. In my view, a stronger justification from real-world applications is needed to highlight the importance of such a distributed estimation procedure.", "questions_for_authors": "1. What is the intuition behind the effective sample size $N_{ess}$ given in (2)? Providing such intuition would help readers better understand the phase transition.  \n\n2. In lines 165–167, I don’t fully understand why it is considered impractical to require $N_{ess} > n$. If $N_{ess} < n$, one could simply use data from a single terminal, eliminating communication costs altogether. This approach would also yield a faster convergence rate of $n^{-\\frac{2r}{2r+1}}$ compared to the rate given in the paper, $N_{ess}^{-\\frac{2r}{2r+1}}$. Could you clarify this point?  \n\n3. What is the specific rate for $H$ in each transition phase? The resolution $H$ is essentially a tuning parameter that controls the trade off between the smoothness of the estimated function and the goodness of fit to the data. And the choice of $H$ also affects the communication cost as a larger $H$ indicates more data to be communicated. \n\n4. Related to the previous question, how do you choose the optimal resolution $H$? For the tuning parameter $\\lambda$ in the distributed kernel ridge regression,  the one needs to intentionally under-smooth the function estimator in each terminal (by using a sub-optimal $\\lambda$ ) so that the aggregated function is globally optimal, see, e.g., [1], [2], [3]. In particular, [2] and [3] propose a GCV criterion to empirically choose the best tuning parameter. I suspect that the choice of $H$ in this paper also has similar phenomena, and can you provide some discussion on this important issue?\n\n5. There is no difference between Theorem 2.12 and 2.11, why use two theorems?\n\n6. Consider the same problem studied in Zhu & Lafferty (2018). The work of \\cite{ref4} proposes a different quantization scheme that does not depend on the Fourier coefficients of the underlying function. It would be beneficial to include this in the literature review for completeness.\n\n7. It would be more convincing if some numerical experiments were provided to validate the theoretical findings in the paper.\n\n\nReferences:\n\n[1]. Zhang, Y., Duchi, J., & Wainwright, M. (2015). Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates. The Journal of Machine Learning Research, 16(1), 3299-3340.\n\n[2]. Xu, G., Shang, Z., & Cheng, G. (2018). Optimal tuning for divide-and-conquer kernel ridge regression with massive data. In International Conference on Machine Learning (pp. 5483-5491). PMLR.\n\n[3]. Xu, G., Shang, Z., & Cheng, G. (2019). Distributed generalized cross-validation for divide-and-conquer kernel ridge regression and its asymptotic optimality. Journal of computational and graphical statistics, 28(4), 891-908.\n\n[4]. Li, K., Liu, R., Xu, G., & Shang, Z. (2024). Nonparametric Inference under B-bits Quantization. Journal of Machine Learning Research, 25(19), 1-68.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}, {"review_id": "gP9FCxkX1N", "reviewer": "Reviewer_tqL9", "summary": "This paper studies nonparametric function estimation under communication constraints, where each distributed terminal holds multiple i.i.d. samples and can communicate sequentially. The authors establish nearly minimax optimal rates across different regimes and identify phase transitions as the number of samples per terminal varies from sparse to dense. This work extends previous studies, which were limited to either dense-sample settings or a single sample per terminal.  \n\nTo achieve the optimal rates, the authors propose a layered estimation protocol that builds on parametric density estimation techniques. The proposed two-phase scheme first employes wavelet transform to convert the nonparametric density estimation problem into a parametric one, and then solve it using quantization and other sample assignment tricks. The upper bounds are then complemented with information-theoretic lower bounds based on SDPIs and Assouad-typed inequalities. The results apply to various special cases, including density estimation and regression models with Gaussian, binary, Poisson, and heteroskedastic noise.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed reading and acknowledging the generality of our technique. We will carefully revise our paper according to your suggestions. In the following we provide responses to your questions.\n\n## Responses to the suggestions:\n\n-   **Reorganization of the Introduction and Literature Review.**\n\nIt is a good suggestion. We will reorganize Subsections 1.2 and 2.2 to improve the presentation.\n\n-   **Clarifying the Technical Contributions.**\n\nWe will follow your suggestion and add more discussions to clarify the technical contributions over previous works. Specifically, In Section 4 Remark 4.3, 4.5 about the comparisons of techniques for proving the upper bounds will be highlighted. Parts of Remark C.4 and C.5 will be moved to be Section 5 of main body, to clarify our technical novelty for the proof of the lower bounds.\n\n-   **Potential Broader Impact.**\n\nIt is a good suggestion. We will add a conclusion and discussion section at the end of the revised paper to provide some potential directions with the help of our methods, especially in the privacy-constrained problems.\n\n## Responses to the questions:\n\n-   **Do the authors believe sequential interaction is essential? Could a similar result be achieved under an independent communication model?**\n\nIt may be difficult to design an independent communication model for all regimes discussed in this work. For some regimes it is possible, especially in the case where $l$ is relatively larger. But for others, especially for the regime where the optimal rate depends exponentially on the number of communication bits, it is much more difficult. In light of our two-layer protocol, the solution may depend on an independent protocol for the parametric distribution estimation problem in [Yuan et al. 2024]. But for the latter, we still do not have ideas, especially for the corresponding regime where the optimal rate depends exponentially on the communication budgets.\n\n-   **Additionally, do the lower bound techniques extend to the blackboard communication model, which is more general than the sequential model?**\n\nIt is a good question and we will think about it more carefully. We think it is possible, but it may need some major improvements in the proof techniques.", "claims_and_evidence": "The main theorems appear to be correct to my best knowledge.", "methods_and_evaluation_criteria": "N/A since this is a theory paper.", "theoretical_claims": "The main theorems, including the proposed schemes and the lower bounds, appear to be correct to my best knowledge.", "experimental_designs_or_analyses": "N/A since this is a theory paper.", "relation_to_broader_scientific_literature": "This work closes the gap between distributed nonparametric estimation under communication constraints with multiple sample regimes. Similar techniques may be applied to distributed estimation under privacy constraints as well.", "essential_references_not_discussed": "The references are adequate to my best knowledge.", "other_strengths_and_weaknesses": "This work makes a significant contribution to the study of distributed nonparametric estimation under communication constraints by addressing multiple sample regimes. It successfully closes gaps left by previous research, particularly by characterizing minimax optimal rates across different data regimes and identifying phase transitions in estimation performance. The theoretical insights and proposed techniques offer valuable advancements in this area.  \n\nOverall, I did not identify any major weaknesses in the paper. The results appear sound (although the upper bounds somewhat heavily rely on the prior work [Yuan et al. 2024]), and the contributions are well-motivated. However, I have a few suggestions to improve the clarity and presentation of the work:  \n\n- **Reorganization of the Introduction and Literature Review:** The first two sections could be slightly restructured, as the literature review is spread across Sections 1.2 and 2.2. Integrating these discussions into a more cohesive review of prior work would improve readability and make it easier for readers to understand the context and contributions of this paper.  \n\n- **Clarifying the Technical Contributions:** The proposed upper and lower bounds are derived using different techniques tailored to specific data regimes. The authors could better emphasize these techniques and compare them explicitly with prior methods, which often focus only on particular regimes. This would help highlight the novelty of the approach and provide insights into which aspects of the methodology are new and which build on existing work.  \n\n- **Potential Broader Impact:** Given the generality of the techniques used, the authors might briefly discuss whether their methods could extend to other communication-constrained estimation problems (e.g., other parametric models) beyond the specific settings considered in the paper. Also, does the similar techniques apply to local differential privacy constraints, which are often studied together with the communication constraints?", "other_comments_or_suggestions": "See above.", "questions_for_authors": "The paper considers a sequentially interactive communication model, with the upper bound based on [Yuan et al. 2024], which relies on an adaptive refinement protocol requiring sequential interaction. Do the authors believe sequential interaction is essential? Could a similar result be achieved under an independent communication model?  \n\nAdditionally, do the lower bound techniques extend to the blackboard communication model, which is more general than the sequential model?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the distributed estimation problem in a nonparametric setting. Although there has been a rich line of literature on this topic, this paper focuses on the challenging scenario where each terminal (i.e. distributed node) has multiple observations, whereas most prior work assumes 1 observation per terminal. For general Sobolev balls, this paper completely characterizes the minimax rate of distributed estimation (up to log factors) and shows exact phase transitions from sparse to dense samples per terminal. Both upper and lower bound analyses are technically sound and significant. 

All reviewers unanimously appreciate the significance of this paper. The main concern is on a more detailed comparison with (Zaman and Szabo, 2022), with a more detailed technical discussion on the new Lemma 5.5 and 5.6 in the lower bound proof. I happily recommend acceptance.
Decision: Accept (poster)