Thank you very much for your careful reading and valuable suggestions.

Table 1

Thanks for this comment, which is also raised by another reviewer kpNG. We will add citations directly in the table.

Line 122

Thanks. We will correct this typo.

Line 135

Thanks. $\eta^*(x)=\max_k \eta_k(x)$ is the maximum value of regression functions.

Line 137

Thanks. Although the proof is straightforward, we will add the proof for completeness.

Line 139

Assumption 1(b) is for the classification setting only. (a), (c), (d) are also necessary for regression. We will revise the paper accordingly. Further discussions are provided in the reply of line 244.

Line 145

We will add the point that $\mathcal{X}\subset \mathbb{R}^d$.

Line 169

Yes, $\hat{Y}$ is a function of outputs of the mechanism on all inputs. This is not a typo, but we agree that it is better to emphasize it in the paper.

Line 202

This is the same as the comment about Table 1. Line 79-85 provide a brief overview of related works about full DP. The following are three main references about full DP.

[1] Density estimation: Duchi, John C., Michael I. Jordan, and Martin J. Wainwright. "Minimax optimal procedures for locally private estimation." Journal of the American Statistical Association 2018.

[2] Classification: Berrett, T., C. Butucea. Classification under local differential privacy. arXiv:1912.04629, 2019.

[3] Regression: Berrett, T. B., L. Györfi, H. Walk. Strongly universally consistent nonparametric regression and classification with privatised data. Electronic Journal of Statistics, 15:2430–2453, 2021.

The main technical tools are developed in [1]. [2] and [3] generalize the results to classification and regression problems.

Line 244

Here we continue the discussions about line 139. Yes, for assumption (a), here it is about $\eta$ instead of $\eta_j$: $|\eta(x)-\eta(x')|\leq L||x-x'||^\beta$.

(c) and (d) remain the same for the regression case.

We will revise the paper accordingly.

Line 297

Thanks for this suggestion. $Y_i^T$ appears to be better. We will change the notation in our revised paper.

We thank again for your careful reading and fruitful suggestions. We will address these problems in our revised version.

Thank you very much for your positive review and detailed comments.

Firstly, thanks for finding these grammatical errors. We will correct them during revision.

The main challenge and the techniques to overcome them as stated in the abstract aren’t clear to me as a reader at this point. It’s not yet stated that the subject of interest is minimax rates, and so there’s no context for the statement “take infimum over all possible learners” and why that would present a challenge. Generally, I did not have a good idea of what the contribution of this work was from the abstract.

"Take infimum over all possible learners" means that, standard packing method can only be used for statistical problems whose output dimension is fixed. However, to derive the minimax optimal risk of classification and regression, we need to consider all possible learners with arbitrary dimensionality. We will improve the abstract accordingly.

In Table 1, attribution for the full DP rates in the local DP setting as well as the rates in the non-private setting should be given in the table. Also, I think there’s an issue with the parentheses in the local label DP rates for regression with bounded label noise.

Thanks for this comment. Other reviewers also mention adding references to the table. Moreover, the second right parenthesis need to be moved left.

Full DP. references are:

[1] Density estimation: Duchi, John C., Michael I. Jordan, and Martin J. Wainwright. "Minimax optimal procedures for locally private estimation." Journal of the American Statistical Association 2018.

[2] Classification: Berrett, T., C. Butucea. Classification under local differential privacy. arXiv:1912.04629, 2019.

[3] Regression: Berrett, T. B., L. Györfi, H. Walk. Strongly universally consistent nonparametric regression and classification with privatised data. Electronic Journal of Statistics, 15:2430–2453, 2021.

Non-private. There are many related references. Here we only show some standard literatures.

[4] K. Chaudhuri et al. "Rates of convergence for nearest neighbor classification." NeurIPS 2014.

[5] J. Audibert et al.. "Fast learning rates for plug-in classifiers." Annals of Statistics, 2007.

[6] P. Zhao et al. "Minimax rate optimal adaptive nearest neighbor classification and regression." IEEE transactions on information theory, 2021.

In the “Minimax analysis for private data” paragraph, KNLRS11 is attributed with finding the relation between label DP and stochastic queries. This is not accurate, this work characterizes local DP learning by the statistical query model.

Thanks. It is a typo here. We actually mean "finding the relation between local DP and statistical queries." "label" should be "local", "stochastic" should be "statistical".

“We hope that to be as small as possible” -> “we seek to minimize this risk” or something similar

Thanks. "we seek to minimize the risk" is indeed better and we will change it during revision.

In Proposition 2, f(x) is used before it is defined.

Thanks. f(x) is defined in Assumption 1(c) now. We should place it within Proposition 2.

"I didn’t find the proof outline for Theorem 1 or Theorem 3 to be informative at all. It would be good to add more specifics if possible."

Thanks. This point is also raise by reviewer #26J5. We refer to the answer to question 1 and 4 there.

Theorem 1 is relatively simple. It uses existing techniques for standard non-private minimax analysis, as well as standard analysis for local DP (see question 1 in the reply of #26J5). Compared with existing works, we need to bound the divergences between two joint distributions with both public and private parts.

For Theorem 3, the first half and second half of the paragraph (line 214-219) are not connected. We will only expand the second half in the revised paper.

Similar to classical minimax theory, we derive the lower bound by dividing the support into $G$ bins. For each bin, we construct a binary hypothesis. The lower bound of excess risk can then be converted to the lower bound of the error of hypothesis testing. Towards this goal, we develop a new tool (Lemma 1) to derive such a lower bound.

Do you have a sense of how the rates would change for approximate label DP?

Thanks for raising this good question. For approximate $(\epsilon, \delta)$-DP, we usually consider the case with very small $\delta$. Our intuition is that the rates will not be significantly different from pure DP (with small $\delta$). However, currently it seems that there are no effective approaches to derive the minimax lower bound with approximate local DP. Therefore, currently we can not make rigorous statements.

Thank you very much for your valuable suggestion on improvement of presentation.

We agree that Lemma 1 in the appendix is important. In our revised paper, we will move this lemma to the main body of the paper. Moreover, we will also provide a better idea of the proof.

The outline of proving theorem 1, 2 and 3 can be written in another way. In particular, in the revised paper, we will add some discussions (for the contents, see the answers of question 1 and 4 below).

Question 1: What techniques from local DP / minimax theory does Theorem 1 use / how would it vary from e.g. the proof for the corresponding non-private lower bound? Saying you use techniques from certain areas/papers without specifying what they are is not particularly informative to a reader. (even giving a high-level summary of the technique would be ok)

(1) Techniques from non-private minimax theory. In minimax lower bound, one takes minimum of all methods and maximum over all possible distributions. We can then narrowing the whole set of distribution to a small set parameterized by a binary vector $v\in \\{-1,1\\}^m$. Similar analysis can be found in the proof of Theorem 6 in [1], the proof of Theorem 3.5 in [2] and proof of Theorem 2 in [3].

[1] K. Chaudhuri et al. "Rates of convergence for nearest neighbor classification." NeurIPS 2014.

[2] J. Audibert et al.. "Fast learning rates for plug-in classifiers." Annals of Statistics, 2007.

[3] P. Zhao et al. "Minimax rate optimal adaptive nearest neighbor classification and regression." IEEE transactions on information theory, 2021.

These discussions are also used to reply to reviewer kpNG.

(2) Techniques from local DP. We use Theorem 1 in [4], in (c) in eq.(42).

[4] Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association. 2018

(3) New techniques that are not from either local DP or classical minimax theory. The label local DP problem lies in between the full DP and non-private case, so we can not directly bound the divergence based on existing techniques. In this paper, we design a new bound for the divergence between two joint distributions that have both private and non-private parts. See eq.(46) and eq.(47) in the paper.

Theorem 1 is relatively easier than later theorems. We will also provide more discussion about other theorems in the paper.

Question 2: How do you decide the number of bins in your upper bound for Theorem 2? Presumably by optimizing some tradeoff b/t the number of examples per bin and having narrower bins where $\eta$ cannot vary too much within a bin, but I'm not confident about this from reading the main body.

Yes, the number of bins is selected to achieve a bias variance tradeoff. Too large bins will induce strong bias. Too narrow bins will make the random fluctuation of $\eta$ be high.

For the optimal number of bins, in line 189, we have determined $h$. Note that the volume of each bin is $h^d$, thus $G=V/h^d$, with $V$ being the total volume of support $\mathcal{X}$. Therefore $G\sim (N(\epsilon^2\wedge 1)/ln K)^{d/(2\beta+d)}$.

Question 3. $\mathcal{X}$ is a vector space, what does "a bin of length $h$" mean for bins defined over a vector space? I believe it means something like each bin has radius at most $h$ in some appropriate norm, but not sure.

Here $\mathcal{X}$ is a compact set. Note that assumption 1(c) requires that $f(x)\geq c$, which means that $f$ is bounded away from zero. The pdf is normalized to 1, thus the support must be bounded. $\mathcal{X}$ is segmented into many cells, and the length of each cell is $h$. We will clarify it in our revised paper.

Question 4. In Theorem 3, the proof outline's first and second halves seem disconnected. The authors mention the model complexity needs to increase with $N$, how does the second half of the proof outline address this necessity?

We agree that the first and second halves are disconnected. The first half is used to argue that the proof can not simply use existing methods (i.e. packing method), since packing method is only suitable for problems with fixed complexity. Therefore, this problem requires new technical novelties.

We think that it would be better to put the first half below, in order to avoid confusions.

In general, we thank again for these valuable suggestions on improving the readability of this paper. We will revise this paper accordingly.

Thanks for your review and valuable suggestions. We will update our paper in our revised version accordingly.

1. Around line 178, the output of the mechanism for classification is unclear. Why is it not a one-hot vector, or at least why is the L1 norm not equal to 1?

As long as the privacy requirement is satisfied, it is not required to conduct one hot encoding. One hot encoding will induce unnecessary loss of information. If we use standard randomized response:

$P(M(x,y)(j)=1)=e^\epsilon/(e^\epsilon + K - 1)$ if $y=j$,

and

$P(M(x,y)(j)=1)=1/(e^\epsilon + K - 1)$ if $y=j$,

then with the increase of $K$, the probability of remaining the original label will decrease significantly. As a result, the classification risk will also increase.

Moreover, this privatization mechanism is similar to RAPPOR [1].

Also, the $\ell_1$ norm is not necessarily 1 since we use sigmoid instead of softmax activation in the last layer.

2. Some notations are overused. For example, "c" refers to the lower bound of the density function in Assumption 1 and also denotes the classifier in line 186 and subsequent proofs.

Thanks! There is indeed an overuse of notation $c$. We will use different notations in our revised paper.

3. The description of the algorithm before Theorem 2 is vague and lacks clarity.

Thanks for pointing out these. We thought that this part is easier than later theorems, due to space limitation, we only describe the algorithm in a concise way.

Here we explain the idea of eq.(11) again. The label can be one hot encoded to a vector first. However, this is not differentially private. To meet the privacy requirement, we randomly flip each element in the vector with probability $1/(e^{\epsilon / 2}+1)$. The vector after such random flipping satisfies $\epsilon$-local label DP.

Divide the support into $G$ bins. For each bin, we count the number of samples (denoted as $S_{lj}$) with $Z_i(j)=1$ and $X_i\in B_l$. Such number reflects the conditional probability of the label being $j$, given the feature $x\in B_l$. Therefore, the classification rule is to take argmax of $S_{lj}$ .

4. The proofs in the appendix are hard to follow without explanations or discussions. For instance, how is $\phi$ defined in Equation (35), and what purpose does it serve? Why does the construction satisfy the assumptions? There seem to be some typos or missing elements in Equations (39) and (40).

Thanks the reviewer for reading the appendix carefully. Although we are sure about the correctness of the proof, we also agree that are indeed some points that require more explanations.

(1) About $\phi$. As stated in line 489 and eq.(35), $\phi$ can be any function satisfying $\beta$-Holder assumption, i.e. $|\phi(x)-\phi(x')|\leq L||x-x'||^\beta$ which is supported on $[-1/2,1/2]^d$, and $0\leq \phi\leq 1$. Here it is not necessary to specify the form of $\phi$ exactly, as infinite number of possible functions $\phi$ are enough for our proof.

Our construction satisfies Assumption 1. For (a), i.e. the Holder assumption with parameter $\beta$, from the construction eq.(36), $|\eta_v(x)-\eta_v(x')|\leq |\phi(\frac{x-c_k}{h})-\phi(\frac{x'-c_k}{h})|h^\beta\leq L(||x-x'||/h)^\beta h^\beta\leq L||x-x'||^\beta$, satisfying Assumption 1(a).

For (b), from (36), $|\eta_v(x)|\leq h^\beta$. Therefore Assumption (b) holds for $t>h^\beta$. From eq.(37), $m\lesssim h^{\gamma \beta-d}$, we have $mh^d\lesssim h^{\gamma \beta}=(h^\beta)^\gamma$, indicating that Assumption (b) holds for $t=h^\beta$. The case with $t<h^\beta$ can be proved by the continuity of function $\phi$.

Our construction is common in minimax analysis in nonparametric statistics. We refer to the proof of Theorem 6 in [2], the proof of Theorem 3.5 in [3] and proof of Theorem 2 in [4] for other examples that use similar ideas.

(2) About eq.(39) and eq.(40). Thanks for pointing it out. In (39), $P(sign(\hat{\eta}(x)))$ should change to $P(sign(\hat{\eta}(x))\neq \eta_v(x))$, which means the probability of making wrong classification at $x$. The typo in (40) is similar.

We thank the authors for the suggestion. We will add more discussions in the revised version.

Questions. The paper discusses non-private baselines. Are there citations provided for these baselines?

The related works on non-private classification and regression are summarized in line 73-78 in the paper.

(1) Classification. We refer to [2], theorem 4(b), which gives $O(n^{-\alpha(\beta+1)/(2\alpha+1)})$. Here the notations are different: $\alpha$ in [2] corresponds to $\beta/d$ in our paper, and $\beta$ in [2] corresponds to $\gamma$ in our paper. After such adjustment, it becomes $n^{-\beta(\gamma+1)/(2\beta+d)}$ in our paper.

(2) Regression. Without privacy constraints, there are no significant differences between bounded and unbounded label noise. We refer to Theorem 5 in [4]. [4] considers heavy-tailed distributions, while current works focus on the bounded case, thus $\beta$ in Theorem 5 in [4] can be regarded as infinite. $p$ in [4] corresponds to $\beta$ in our paper.

Nonparametric classification and regression have been widely studied and the related works are far beyond those listed above. We refer to a book [5] for a complete overview of nonparametric classification and regression.

In our revised version, we will cite related works directly in the table.

References

[1] P. Kairouz et al. "Discrete distribution estimation under local privacy." ICML 2016.

[2] K. Chaudhuri et al. "Rates of convergence for nearest neighbor classification." NeurIPS 2014.

[3] J. Audibert et al.. "Fast learning rates for plug-in classifiers." Annals of Statistics, 2007.

[4] P. Zhao et al. "Minimax rate optimal adaptive nearest neighbor classification and regression." IEEE transactions on information theory, 2021.

[5] Tsybakov. "Introduction to nonparametric estimation". 2009