Thanks for your comment. Now we respond to your questions.

Reply to Question 1

If $\epsilon > 1$, then we just use eq.(65), which is the standard minimax lower bound that holds even for non-private data. We do not need to derive eq.(64) from eq.(62) again. eq.(64) only holds for $\epsilon < 1$. Therefore our proof is correct here.

Following your questions, in our revised paper, we have emphasized this point to make it clearer. The new statements are:

With $\epsilon<1$, let $s\sim 1/\sqrt{nm\epsilon^2}$, then $\text{P}(\hat{V}\neq V)\sim 1$. Hence

\inf_{\hat{\mu}} \underset{Q\in \mathcal{Q}_\epsilon}{\inf} \underset{p\in \mathcal{P}_\mathcal{X}}{\sup}\mathbb{E}[(\hat{\mu}-\mu)^2]\gtrsim \frac{D^2}{nm\epsilon^2}

If $\epsilon>1$, then from standard minimax analysis for non-private problems, \textcolor{blue}{the estimation error can not be smaller than $\sigma^2/(mn)$, with $\sigma^2$ being the sample variance. The maximum value of $\sigma^2$ is $D^2$. Therefore} it can be easily shown that

\underset{\hat{\mu}}{\inf} \underset{Q\in \mathcal{Q}_\epsilon}{\inf}\underset{p\in \mathcal{P}_\mathcal{X}}{\sup}\mathbb{E}[(\hat{\mu}-\mu)^2]\gtrsim \frac{D^2}{nm}.

Reply to Question 2

Thanks for this suggestion. To derive the lower bound, we need to bound the total variation (TV) distance, which is shown in Lemma 10 in Appendix G.

Reply to Question 3

Current model is actually interactive. For example, in the mean estimation problem, we use a two-stage approach, in which the second stage depends on the first stage.

About the novelty of this paper

To the best of our knowledge, our work is the first attempt to study user-level LDP problems for general $\epsilon$. Moreover, it is also the first attempt to study nonparametric classification and regression problem with user-level LDP.

For user-level LDP problems, different privacy budget $\epsilon$ requires different methods. We take the multi-dimensional mean estimation problem as an example. We conduct user splitting (divide users into groups, and each group is responsible for one component) for small $\epsilon$, and budget splitting (let the budget to be $\epsilon / d$ for each component) for very large $\epsilon$. For medium $\epsilon$, we design a new grouping strategy to achieve a smooth transition between these two extremes.

We are looking forward to your further comments and questions.

Thank you very much for your positive feedback. We are encouraged that you have positive evaluation on our significance, organization and completeness of our work.

The references [1-3] are about user-level DP under the central model. Although these works and ours do not have exactly the same background, we will definitely mention them in our revised paper.

To the best of our knowledge, the statement "Moreover, we also provide the first analysis on nonparametric classification and regression problems under user-level $\epsilon$-LDP" is still accurate. [4] studies linear regression instead of nonparametric classification and regression. Since nonparametric statistics do not impose any model assumptions on the distribution, the techniques are crucially different. [5] and [6] are about item-level LDP. However, following your comment, we will discuss them in the related work section.

Thanks for your careful reading of this paper and valuable comments. We reply to your comments as follows.

Reply to Question 1

In industrial applications, from an accuracy-first perspective, companies usually consider only the case with $\epsilon >1$. Moreover, a recently trend is to use message shuffling techniques. In these cases, we usually consider relatively large $\epsilon$. For example:

K.Talwar et al. Samplable Anonymous Aggregation for Private Federated Data Analysis, CCS, 2024. (apple team)

Exposure Notification Privacy-Preserving. "Exposure Notification Privacy-Preserving Analytics (ENPA) White Paper." ENPA_White_Paper. pdf.

Reply to Question 2

We mean that, for arbitrary $m$, if we randomly pick a sample from a user, $n$ users with $m$ samples per user under user-level $\epsilon$-LDP is just equivalent to item-level $\epsilon$-LDP with $n$ samples. The result is not limited to the case with $m=1$.

Reply to Question 3

For user-level $\epsilon$-LDP, $m$ local samples combine together to generate an output, thus local samples within the same user can share information with each other. Therefore user-level $\epsilon$-LDP does not ensure item-level $\epsilon$-LDP.

Reply to Question 4

We explain it from information-theoretic perspective. A precise communication of a continuous random variable requires infinite number of bits. However, in user-level LDP, each user compresses all local samples into only one variable, which can only transmit limited information. As a result, as long as $n$ is fixed, no matter how large is $m$, the precision can not reach infinity. We refer to line 251-252 in our paper, which gives a lower bound. We also refer to line 969-986 for a proof.

Reply to Question 5

In line 322, our paper has stated that "denote $n_0$ as the number of users in each group". Now there are $n$ users divided into $\lceil d/\epsilon \rceil$ groups, thus $n_0=n/\lceil d/\epsilon\rceil$.

Reply to Question 6

Thanks for this comment. We study the bounded gradient case because we want to compare with the item-level case (Duchi et al. .Local privacy and statistical minimax rates. FOCS 2013). We will add the analysis for unbounded gradients in our revised paper.