Thanks for your feedback. We are encouraged that you have a positive evaluation on the significance, as well as the simplicity and effectivenss of our work.

The theoretical results provide only an upper bound for the proposed method. I suggest including additional comparisons and discussions between this bound and existing results.

We think that this is a very good question. Deriving the lower bound of excess risk is hard. However, it can be shown that if we just use scalar labels, the probability of retaining original label decrease polynomially with $K$.

Denote $M_{ij}=P(Z=j|Y=i)$ as the transition probability. Then $\sum_{j=1}^K M_{ij} = 1$. From the $\epsilon$-label LDP constraint, $M_{ii}\leq e^\epsilon M_{ji}$ for all $j$. Taking sum over all $i$ and $j$,

$K\sum_{i=1}^K M_{ii} \leq \sum_{i=1}^K \sum_{j=1}^K e^\epsilon M_{ji} = Ke^\epsilon.$

The average probability of retaining original label satisfies $(1/K)\sum_{i=1}^K M_{ii}\leq e^\epsilon/K$, which decays inversely with $K$.

Therefore, with the increase of $K$, the privatized scalar random variables become increasingly unlikely to retain the original label.

We thank you for the other two valuable suggestions. In our revised paper, we will add experiments with long-tailed distributions or datasets with high class imbalance. The expected result is that classes with minor probability will not obviously affect the performance of our method, but baseline methods will be negatively affected. We will also improve the conciseness.

For the question, Table 3 is about experimentson on CIFAR-100 dataset. It seems that this table does not contain footnotes, thus we are not sure where you are referring to. Would you please explain the question further?

Thanks for your review.

1.The focus on local differential privacy is not clear from the title and abstract, which could be misleading for readers. Revising these sections to clearly indicate this focus would improve accessibility and transparency.

Thanks for this comment. We will change the title to "Enhancing learning with local label differential privacy...". We will also mention it in the abstract.

2.The methods mentioned in the “Others” section of the related work could be discussed in more detail to give readers a clearer understanding of the techniques used in prior studies.

Actually, the related works mentioned in "others" section are not comparable baselines. They are under different settings. Ghazi et al. (2022) and Badanidiyuruetal.(2023) study the regression problem instead of classification. Krichene et al.(2024) and Chua et al.(2024) are about learning problems with some features being public. In our revised paper, we will briefly mention these methods and discuss the relationship between these works and ours.

3. The practical applicability of the method is limited, as it requires training a separate discriminant for each class, which could be cumbersome or impractical for larger or more complex tasks.

This is a misunderstanding. The practical applicability is not limited. We do not require training a separate discriminant for each class. We mention it only for theoretical analysis, which gives an idea why our method outperforms existing methods, especially for large $K$.

On the contrary, as mentioned by reviewer zGeU and nJ8J, our method is simpler than existing methods, instead of being cumbersome or impractical. We do not train the model multiple times as in Ghazi et al. 2021. Moreover, the label randomization also takes less time (only O(K) for each sample).

4. The novelty of the proposed method is questionable, as noted by the authors themselves in lines 232-233, where they acknowledge its prior use in the literature.

As mentioned in lines 232-233, RAPPOR was already proposed before. However, this method was used for frequency estimation, which is different from learning with label DP. Before our work, it was not obvious that RAPPOR can be used into learning with label DP.

In our work, we apply an existing technique for one task to another different task, and achieve significant improvement over existing methods for this new task. We believe that this should be considered novel. The simplicity of our method and the connection with existing methods for other tasks should be an additional merit, instead of a lack of novelty.

5. The authors claim that their method achieves better results by encoding more information in a vector rather than a scalar, but it remains unclear if this added information genuinely benefits the privacy-utility tradeoff. It would be valuable to see a theoretical result similar to Theorem 2 applied to the randomized response mechanism over the simplex to support a comparative analysis.

Thanks for this valuable comment. We refer to the response to reviewer nJ8J.

Deriving the lower bound of the excess risk is hard. However, it can be shown that the probability of retaining the original label decrease significantly with $K$, as long as we use scalar to encode information. Our analysis indicates that the average probability can not exceed $e^\epsilon/K$. Therefore, this added information indeed enhances the privacy-utility tradeoff.

Thanks for your positive evaluation and valuable comments.

Reply to weaknesses

1. Given strong conceptual similarities between ALIBI and the method proposed here, as well as the fact that the former is the current state-of-the-art for label DP task, I would have expected the theoretical analysis to focus on comparing the two methods.

We think that this is a really good question. To make a rigorous theoretical statement, we need to show the lower bound of the risk of ALIBI. ALIBI uses Bayesian inference, which is a bit complex and it is thus hard to obtain a general lower bound. However, we can show that the performance of ALIBI decays with $K$ by a simple example.

Suppose that for all $x$, $\eta_1(x)=1$, $\eta_2(x)=\ldots=\eta_K(x)=0$. Then all samples have label 1. According to eq.(3) in the ALIBI paper,

$p(Y=c|o, \lambda) = Softmax(f(o_c)/\lambda),$

in which we assume uniform prior. Then it can be shown that the probability of making a correct prediction is upper bounded by

$p(Y=1|o, \lambda)\leq \frac{1}{\sum_{c=2}^K 1(f(o_c)\geq f(o_1))}\leq \frac{1}{\sum_{c=2}^K 1(o_c\geq o_1)},$

in which $f(o_c)=-\sum_k |o_k-[c=k]|$, with $[]$ being the Iverson bracket. These are from the original paper of ALIBI. The second inequality holds because if $o_c\geq o_1$, then it can be shown that $f(o_c)\geq f(o_1)$.

Recall Algorithm 3 in ALIBI paper, $o_1=1+W_1$, $o_c=W_c$ for $c=2,\ldots, K$, in which $W_j\sim Laplace(\lambda)$ for all $j=1,\ldots, K$. Therefore, in expectation, $\sum_{c=2}^K \mathbf{1}(o_c\geq o_1)$ grows linearly with $K$. As a result, $p(Y=1|o, \lambda)$ decays nearly inversely with $K$.

From the example above, it can be found that the performance of ALIBI decays significantly with $K$.

Hope that the above example provides some intuition. However, currently it is hard to provide a complete analysis since deriving the lower bound of risk is usually much harder than the upper bound.

2.citing computational efficiency ($O(K^2)$ vs $O(K)$) when comparing the new approach with ALIBI (Malek Esmaeili et al. (2021)) looks misplaced, when in any practical ML application the cost of training would dominate over the computational cost of flipping labels.

In this paper, we discuss general methods for label randomization under local label DP. The base learner is not necessarily a deep learning model. It can also be statistical machine learning methods. Therefore we think that it is worthwhile to mention the complexity. For example, in our numerical experiments using $k$ nearest neighbors, the computation cost of ALIBI is about 3-4 times higher than our method.

Reply to questions

1. Can you elaborate your reasoning on the line 107

Thanks for this comment. The softmax operation normalizes the output to 1, which makes the values of each component smaller if the previous sum was larger than 1, or larger if the previous sum is smaller than 1, thus this operation introduces bias. For simplicity, suppose $o_1=1$ and $o_2=\ldots=o_K=0$, then $f(o_1)=0$ and $f(o_2)=-2$. According to eq.(3) in ALIBI paper, after softmax operation, the probability $p(y=1|o,\lambda)<1$, while $p(y=c|o, \lambda)>0$ for $c\neq 1$. This is an example that the softmax operation introduces bias.

However, we agree that readers may get confused when reading this sentence at the first time. Therefore in the revised paper, we will restate this sentence, and mention the example in the reply of weakness 1.

2. In section 4.3 Practical Implementation, how does changing the activation function of the last layer affects the model performance? Do you use this in the experiments chapter and if yes, how do you modify the training process?

The changing of activation function is required by our analysis. We hope that $g_j(x)$ approximates $E[Z(j)|X=x]$ (see the discussion after eq.(15) in our paper). Therefore, here we need to use the sigmoid activation. If we use softmax activation, then the network learns $E[Z(j)|X=x]/\sum_l E[Z(l)|X=x]$.

3. To be pedantic, line 87 should say "Malek Esmaeili et al. (2021) proposes PATE-FM". Original PATE was introduced by Papernot et al., 2016, and is not specific to label DP.

Thanks for this comment. We will change the statement and cite the original paper of Papernot et al.

Thank you very much for your positive review. We are encouraged that you have a positive evaluation on the simplicity and effectiveness of our proposed method, as well as the clarity of our paper.

In what follows, we reply to the weaknesses and questions you have raised.

Reply to Weaknesses

1.I feel there is rooom for making the paper stronger on the theoretical side.

Thanks for this comment. According to other reviewer's comment (Vdjs and nJ8J), it would be better to include the analysis of all methods based on scalar approximation. Moreover, we will also provide an analysis of ALIBI.

2.I feel the analysis of k-NN is a bit incomplete (Appendix B.1) and doesn't highlight the complete picture. What I would have liked to see is how the excess risk decreases as $N\rightarrow \infty$.

This is indeed an important point. With fixed $k$, the excess risk does not decrease to zero even if $N\rightarrow \infty$. Therefore, we need to let $k$ grows with $N$ with an appropriate speed. We now focus on the case with $\epsilon < 1$. In eq.(36) in our paper, assuming that the density is bounded away from zero, then $r_0\sim \epsilon(k/N)^{1/d}$ (see also eq.(32)). Therefore, to minimize the right hand side of eq.(34), we can let $k\sim \epsilon^{-2d/(d+2)}N^{2/(d+2)}$ (here we neglect logarithmic factors), then $\Delta(x)$ decays with $\epsilon^{d/(d+2)} N^{-1/(d+2)}$. According to eq.(20) and eq.(21), we have $\Delta_\epsilon(x)\sim (N\epsilon^2)^{-1/(d+2)}$. Therefore $R-R^*\lesssim (N\epsilon^2)^{-1/(d+2)}$.

In addition, in nonparametric classification, a commonly used assumption is "Tsybakov margin condition", which says that $P(0<\eta^*(X)-\eta_s(X)<t)\lesssim t^\gamma$ for some $\gamma$. In this case, the convergence rate of the excess risk becomes faster, $R-R^*\lesssim (N\epsilon^2)^{-(1+\gamma)/(d+2)}$.

In the revised paper, we have added the discussions in Appendix B.

Reply to Questions

About Ghazi et al's two papers.

As explained in the response to weakness 2, we will add the convergence with respect to $N$. However, the result is not comparable with Ghazi et al. 2021 and Ghazi et al. 2024. These two papers consider the stochastic optimization problem, thus the risk is the optimization risk instead of the classification risk. The optimization excess risk does not include the approximation error, i.e. the gap between the risk of current model (under optimal parameters) with the minimum risk over all models. If the hypothesis space of a learning model does not contain the ground truth, then the approximation error is nonzero.

On the experimental side, I am wondering if the authors have also considered datasets with non-uniform distribution over labels. For example, one could consider MNIST or CIFAR datasets by additional duplicates of certain labels to make the distribution of labels to be biased. How does the proposed method perform against prior methods, especially methods that use prior information (such as RRWithPrior or LP-MST)?

Thanks for this comment. We will run more experiments with non-uniform distribution of labels.