Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal

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.

Responses to the suggestions:

• Reorganization of the Introduction and Literature Review.

It is a good suggestion. We will reorganize Subsections 1.2 and 2.2 to improve the presentation.

• Clarifying the Technical Contributions.

We 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.

• Potential Broader Impact.

It 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.

Responses to the questions:

• Do the authors believe sequential interaction is essential? Could a similar result be achieved under an independent communication model?

It 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.

• Additionally, do the lower bound techniques extend to the blackboard communication model, which is more general than the sequential model?

It 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.

Thanks for your careful reading and interesting questions. Here are our detailed responses.

Responses to the weaknesses:

• 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. ...

The model is idealized compared with practical applications. However, there are enough motivations to study it, and we will highlight them in the revised paper.

1. 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.
2. 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.
3. 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.

Responses to the questions:

• What is the intuition behind the effective sample size given in (2)?

The 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}}$.

• Why is it considered impractical to require $N_{ess}>n$?

It 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.

• 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]. ...

Since these two questions are highly related, we respond to them together.

1. 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.

2. 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}}$.

3. 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.

• ... no difference between Theorem 2.12 and 2.11...

I 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.

• The work of [4] proposes a different quantization scheme that does not depend on the Fourier coefficients...

Thanks 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.

• ... numerical experiments...

It 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.

Thanks for your careful reading and detailed comments. Here are our point-to-point responses to your concerns.

Responses to the weaknesses:

• ... some assumptions seem slightly more substantial than in prior works (e.g., Zaman & Szabó, 2022). ...

We 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.

1. 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.
2. 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).
3. Even though stronger assumptions are imposed, our framework can also subsume almost all the specific models presented in (Zaman & Szabo, 2022).

• The empirical justification is absent.

Adding 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.

• The lower bound proof's technical novelty...

We 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.

1. 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.
2. 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.

We will add more discussions in the revised paper and make our contributions on the lower bound more explicitly.

• The discussion of practical communication constraints is somewhat idealized. ...

In 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.

1. 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.

2. 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.

I 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.

Responses to other comments or suggestions:

• Adding a conclusion section...

We will follow this suggestion by adding a conclusion and discussion section at the end of the revised paper.

• 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).

We 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).

Thanks for your very positive assessment and the suggestions. We are going to revise our paper according to your suggestions in the following aspects.

1. 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.

2. 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}$).