Enhancing Learning with Label Differential Privacy by Vector Approximation
Authors: Puning Zhao
Jiafei Wu
Zhe Liu
Li Shen
Zhikun Zhang
Rongfei Fan
Le Sun
Qingming Li
Venue: ICLR 2025 Spotlight (2025)
Keywords: label differential privacy
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Label differential privacy (DP) is a framework that protects the privacy of labels in training datasets, while the feature vectors are public. Existing approaches protect the privacy of labels by flipping them randomly, and then train a model to make the output approximate the privatized label. However, as the number of classes K increases, stronger randomization is needed, thus the performances of these methods become significantly worse. In this paper, we propose a vector approximation approach for learning with label local differential privacy, which is easy to implement and introduces little additional computational overhead. Instead of flipping each label into a single scalar, our method converts each label into a random vector with K components, whose expectations reflect class conditional probabilities. Intuitively, vector approximation retains more information than scalar labels. A brief theoretical analysis shows that the performance of our method only decays slightly with K. Finally, we conduct experiments on both synthesized and real datasets, which validate our theoretical analysis as well as the practical performance of our method.

Published as a conference paper at ICLR 2025
ENHANCING LEARNING WITH LABEL LOCAL DIFFER- ENTIAL PRIVACY BY VECTOR APPROXIMATION
Puning Zhao, Jiafei Wu, Zhe Liu"
Zhejiang Lab Hangzhou, Zhejiang, China (pnzhao, wujiafei, zhe. 1ie com
Li Shen
Zhikun Zhang Zhejiang University Hangzhou, Zhejiang, China zhikun@z edu. en
Shenzhen Campus Sun Yat-sen University Shenzhen, Guangdong. China wetthheeniigmme 10ammillml. com
Rongfei Fan
Le Sun
Beijing Institute of Technology fanrongfei@bit edu. on
Nanjing University of Information Science and Technology @nsuin@nuist... edu. cn
Qingming Li
Zhejiang University siqmázju edu. cn
ABSTRACT
Label differential privacy (DP) is a framework that protects the privacy of labels in training datasets, while the feature vectors are public. Existing approaches protect the privacy of labels by flipping them randomly, and then train a model to make the output approximate the privatized label. However, as the number of classes increases, stronger randomization needed, thus the performances these methods become significantly worse. In this paper, we propose vector approximation approach for learning with label local differential privacy, which is easy to implement and introduces little additional computational overhead. Instead of flipping each label into a single scalar, our method converts each label into a random vector with K components, whose expectations reflect class conditional probabilities. Intuitively, vector approximation retains more information than scalar labels. A brief theoretical analysis shows that the performance of our method only decays slightly with K. Finally, we conduct experiments on both synthesized and real datasets, which validate our theoretical analysis as well the practical performance of our method.
INTRODUCTION
Differential privacy (DP) (Dwork et al. 2006) is effective approach for privacy protection, and has been applied extensively (Erlingsson al. 2014 / Ding al. 2017]] Tang al. 2017 Near 2018 Zhang et al. 202I). However, in supervised learning problems, the original definition of DP can be stronger than necessary, resulting in unnecessary sacrifice of utility. In particular, sometimes is reasonable assume that features publicly available, while only labels are highly sensitive and need to be protected, such as recommender systems (McSherry & Mironov 2009), computational advertising (MeMahan al. 2013) and medical diagnosis (Bussone al. 20220). These scenarios usually use some basic demographic information as features, which are far less sensitive than the labels. Under such background, label DP has emerged in recent years (Ghazi al. 202
"Corresponding author

---

Published as a conference paper at ICLR 2025
Malek Esmacili et al. 2021:
Esfandiari al. 2022 Tang al. 2022 Cunningham et al. 2022).
under which the output is only required to be insensitive to the replacement of training labels.
There several existing methods for learning with label DP, such randomized response (Warner 1965). RRWithPrior (Ghazi et al. 202I) and ALIBI (Malek Esmacili et al., (02T). These methods flip training labels Y randomly privatized labels Y to satisfy the privacy requirement. However, common issue is that the performances decrease sharply with the number of classes K. Intuitively, with K increases, is inevitable for the privatized label to be randomly selected from a large number of candidates, thus the probability of maintaining the original label P(Y Y) is small. It is possible to design some tricks to narrow down the candidate list, such as RRWithPrior (Ghazi et al. (021), D
which picks the candidates based on their prior probabilities. However, the performances under e-label DP with small are still far from the non-private baseline. From an information-thoomm perspective, a single scalar can only convey limited information (Cuff' Yu 2016 Wang et al. [0016] AAhaary et al.) (202).. Therefore, as long as the label is transformed into a scalar, with increasing K, is increasingly unlikely to maintain the statistical dependence between the original label and the privatized one, thus the model performance drops with K.
In this paper, we propose a vector approximation approach to solve the multi-class classification problem with large number of classes K under label DP. To satisfy the privacy requirement, each label is transformed into a random vector = (Z(1)..... ((K) E {0,1] and the transformation satisfies c-label DP. Intuitively, compared with sealar transformation, conversion of labels to multi- dimensional vectors preserves more information, which is especially important with large K, thus method achieves better performance.
We then move on to a deeper understanding of our new proposed approach. For a given feature vector x, let A (x) be the maximum estimation error of regression function 7/ (x) over k 1,...; K. Our analysis shows that as long as A (x) is smaller than the gap between the largest and second largest one among {7) (x), ..., 7 (x) the classifier will yield a Bayes optimal prediction. For statistical learning model, such as the nearest neighbor classifier, A (z) can be viewed as a union bound that only grows with O( /Iv K). For deep neural networks, while it is hard analyze the growth rate of (xx over K rigorously, such growth rate is slow by intuition and experience (Widmann et al. 2019 Zhao & Lai 2022 Zhao et al. [021] Kull et al., 2019; Rajaraman et al. 2022). As result, the classification performance of our approach only decreases slowly with K.
Finally, we conduct experiments on both synthesized data and standard benchmark datasets. The goal of using synthesized data is to display how the performance degrades with increasing number of classes K. The results show that with small K, our method achieves nearly the same results with existing approaches. However, with K increases, our vector approximation method exhibits clear advantages. We then test the performance on some standard benchmark datasets, which also validate the effectiveness of our proposed method.
The contributions of this work are summarized as follows.
We propose a vector approximation approach for learning with label DP. Our method is convenient to implement and introduces little additional computational complexity.
We provide brief theoretical analysis showing that the model performance remains rela- tively stable with increasing number of classes K.
Numerical results on synthesized data validate the theoretical analysis, which shows that the performance of our method only decays slightly with K. Experiments on real datasets also validate the effectiveness of our proposed method.
2 RELATED WORK
Central label DP. (Esfandiari et al., 2022 proposes an approach by clustering feature vectors, and then resampling each label based on the samples within the same cluster. Malek Esmaeili et al. (202I) applies PATE-FM (Papernot et al. 2017) into label DP settings, which splits the training datasets into several parts, and each part is used to train a teacher model. The labels are then altered by a majority vote from teacher models. Appropriate noise is added to the voting for privacy protection. Then PATE trains a student model using these altered labels. PATE is further improved in (Tang et al.) 2022). Despite achieving good performances, these methods are designed under central label DP
2

---

Published as a conference paper at ICLR 2025
requirement (see Definition 2), which requires that the curator is trusted, instead of protecting the privacy of each sample individually. Therefore, the accuracy scores are not comparable with ours.
Local label DP. Under local DP, labels privatized before training to protect each sample individu- ally. The performance simple randomized response (Warner 1965 drops with sharply. Here we list two main modifications:
1) RRWithPrior (Ghazi et al. (027). This an important improvement over the randomized response method, which partially alleviates the degradation of performance for large K. RRWithPrior picks transformed labels from some candidate labels with high conditional probabilities, instead of from all K labels, thus it narrows down the list of candidates and somewhat reduces the label noise. However, this method requires multiple training stages to get a reliable estimate of prior probability. As result, the samples in the beginning stages are used inefficiently. Moreover, RRWithPrior optimizes the probability of retaining the original label, i.e. P(Y Y), with Y being the transformed one. Such optimization goal does not always align with the optimization of classification risk.
2) ALIBI (Maeek Esmaeili et al. 2021). This method conducts one-hot encoding first and then adds Laplacian noise to protect privacy. The design shares some similarities with our method. For each sample, ALIBI generates soft label vector using Bayesian inference and normalizes them to 1 using softmax operation. However, as shown in Appendix B.2] ALIBI does not completely overcome the drawbacks of scalar approximation methods, since the soft label value still decreases with K. Moreover, the time complexity for transforming each label is O(K²), thus the computation cost is high with large K. On the contrary, our vector approximation only requires ((K) time for each label transformation.
Others. There are also some works under other settings. (Ghazi et al. 2022 Badanidiyuru et al. 2023) study the regression problem under label LDP. Similar to the classification problem, these methods randomly perturb the label to another. Moreover, (Krichene et al. 2024 Chua et al. 2024
Ma et al. [2024] Ghazi al. 2024) discussed the with both public and private features. There
are also some methods that deal with the drawback of label DP and propose to protect the privacy of
training samples in better way (Wu et al. 2023 Busa-Fekete et al. (023). Furthermore, Wei al.
(2023) gives comprehensive empirical evaluation of label DP algorithms,, and Zhao et al. (2025) provides a theoretical analysis of the fundamental limits of learning with label differential privacy.
In this work, we observe that all methods based on scalar approximation have inherent limitation of information loss. In particular, the probability retaining the original label after local randomization inevitably reduces with K (see Appendix [BI]. With the intuition of preserving more information, instead transforming each label to another scalar label, our vector approximation approach privatizes each label into a vector Z that is not normalized to 1. Compared with existing methods, our approach introduces little additional computational complexity, while achieving better performance with large number of classes K.
3 PRELIMINARIES
3.1 LABEL DP
To begin with, we recall some concepts related to DP and introduce the notion of label DP.
Definition 1. (Differential Privacy (DP) (Dwork et al. 20061). Let e E R2 O. An algorithm A e-differentially private (denoted (-DP) if for any adjacent datasets D and D' and any
S C (A).
P(A(D) S) ('A(A(D)) E S),
(I)
in which two datasets D and D' are adjacent if they differ on a single training sample, including both the feature vector and the label.
In supervised learning problems, the output of algorithm AA is the trained model, while the input is the training dataset. Under Definition both features and labels privatized. However, in some scenarios, protecting features can be unnecessary, and we focus solely on the privacy labels. Correspondingly, the notion of label DP is defined follows:
3

---

Published as a conference paper at ICLR 2025
Definition 2. (Label Differential Privacy (Label DP) (Chaudhuri & Hsu 2011)) An algorithm A is e-label differentially private (denoted as e-label DP) if for any two datasets and D' that differ on the label of single training sample, and any S S range A). 7 holds.
Compared with Definition 1 now the algorithm only needs to guarantee ( when the label of sample changes.
Throughout this paper, consider the local DP setting, i.e. each label is transformed to random variable (or vector) Z = MY) individually by mechanism M y + Z, which ) denotes the set of all labels, while Z is the space of transformed variables vectors. The label LDP is defined as follows.
Definition 3. random mechanism M y - 2 is e-label LDP for any y.y E y and any 5 S Z,
P(M(Y) E S = y) & e cEP((((Y E S/Y = v²).
(2)
Given N training samples (X,, Yi). i = 1..... N, the mechanism M transforms Y; to Z₁ i 1.-.., N. It can be easily shown that label LDP is stronger privacy requirement compared with central label DP (Definition 2. To be more precise, as long as M is local e-label DP, then any learning algorithms using (X,, Z.), I,..., N training samples are central e-label DP.
3.2 CLASSIFICATION RISK
Now we describe the goal and the evaluation metric of the classification task. For a K-class classification problem, the goal is to build a classifier that predicts the label Y E y [K]. in which [K] = (I....: K}, given feature vector X' C RRd In this work, we use - 1 loss for classification. For a classifier y = c(X), in which Y is the predicted label, the risk is defined as the expectation of the loss function:
R| E[1( # YY = P(c(X) # Y).
Define K functions, named m..... [KK as the conditional class probability given a specific feature vector
ny (x) P(Y j x
7i known, then for any test sample with feature vector x, the classifier can make the prediction be the class with maximum conditional probability. Therefore, the Bayes optimal classifier c* is
(x) arg max (x). jE[K]
(5)
The risk corresponds to the ideal classifier cx, called Bayes risk, is
R =
(6)
Bayes risk is the minimum risk among all possible classifiers. In reality, ma is unknown. Therefore, for a practical classifier that is trained using finite number of samples, there is some gap between its risk and the Bayes risk. Such gap R R is called the excess risk. Denote
17" (x) max 17j (x)
as the maximum of m regression functions. The next proposition gives expression of the excess risk.
Proposition
For any practical classifier e: X - V. the excess risk is
(n'(x) f
R- R² = =
(x))
(8)
in which R is the Bayes risk, and f is the probability density function (pdf) of feature vector X. Mess) (x) is just (x)x) with j c(x). Note that c(x) random due to the randomness of the training dataset. Therefore the expectation in (8) is taken over N training samples.
4

---

Published as a conference paper at ICLR 2025
Proof. From 55) and (6), the Bayes risk is
R P(Y * c² (X) / P(Y =
/ (11-0"28)) (
(9)
The actual risk for practical classifier is
R= P(Y + x()) = IE [ (x(x)(x)) f(x)dx)
(10)
From
10p and 9
(((((x)) (l)otx)(x)))fxx)
R R
(11)
The proof is complete.
L
3.3 NOTATIONS
Finally, we clarify the notations. Throughout this paper, a A = min(a, b), a avbb= max(a, b). We claim that x b if there exists constant C such that S Cb. Notation is defined similarly. Lap(A) denotes the Laplacian distribution with parameter A, whose probability density function (pdf) is f(u)) = e --11//> ///l//((2)) (2A). Furthermore, we use capital letters to denote random variables, and lowercase letters to denote values.
THE PROPOSED METHOD
Here we present and explain our new method. Section 4.1 shows the basic idea. Section 4.2 gives an intuitive analysis. Finally, practical implementation with deep learning discussed Section 4.3
4.1 METHOP DESCRIPTION
Instead of transforming label to another scalar, construct random vector Z f0, 1]K which can preserve more information than a random one-dimensional scalar. To be more precise, denote Z(j as the j-th element of Z.
Given the original label Y = j", let the conditional distribution Z(j) be
if j = j
P(Z() 1|Y = j')
(12)
if 1+11
14
and
if j j=
=
14e2 1
(13)
if
14e3
It is ensured that conditional Y, 7(j) are independent for different The privacy mechanism
described by (12 and (13) is a simple form of RAPPOR (Erlingsson et al.) 2014). RAPPOR was analyzed in (Kairouz al. 2016) as one of common frequency estimation methods under LDP. According to (Kairouz et al. 2016), RAPPOR has the optimal convergence rate. Our work shows that RAPPOR be also used in the randomization step of label DP. The following theorem shows the DP property.
Theorem 1.
The privacy mechanism
72
13 is e-label LDP.
Proof. For any j. and any (0, K we have
P(Z z|Y =
P(Z(T) =() = =]
I (P((()) 2(D)Y =J)
P(Z Y j()
P(Z()) =Z0)I = -)P(Z(')= = =
P(Z() =()]Y =j'P(Z(0)) ==000==(=>VV->00
S (e2)² =
(14)
5

---

Published as a conference paper at ICLR 2025
in which the first step holds since (() are conditional independent on l. The second step holds because changing Y from j to j' does not affect the conditional distributions of elements of Z other than the j-th and the j'-th one, i.. P ((Z(1)
2()) = j) (()(1) 2(D) j") for & {i.j"). Therefore, we only need to bound the ratio of the probability mass of the j-th and j' element. The
last step holds since (12) and (13) ensures that P(Z(j) =(j)[V j)/P(Z(j) =()) = j') S
et/2, Therefore, the label LDP requirement in Definition 3 satisfied.
Following above procedures, the labels of all training samples Yi...., YN are transformed into N vectors Zi...., Zx. From (5) the optimal prediction is the class that maximizes n)(x). However, Mi is unknown, and we would like to find a substitute. Towards this end, we train model that can be either parametric (linear models, neural networks, etc.) or nonparametric (k nearest neighbors, tree-based methods, etc.), to approximate Zı.... ZN. The model output can be expressed by
g(x) (g)(x), ................................ .x..........)))) (x))
(15)
(x) denotes the j-th element of the output vector. With a good model and sufficient training samples, (x( approximates B[Z()]X = x]. it expected that picking j that maximizes ny (x) is nearly equivalent to maximizing 9, (x). Therefore, in the prediction stage, for any test sample whose feature vector is x, the predicted label is
Y c(x) arg max gj
(16)
jE[K]
4.2 BRIEF ANALYSIS
Now we briefly explain why our new method works. Define
= : = 1|
(17)
It is expected that the model output (x). .k. (x)) approximates (î (x). 7i (x)). Ide-
ally, (x) = ?ū (x). then from (1)), c(x) = arg max, 7 (x) = arg max; (x) = c* (x) is the
optimal prediction. However, in reality, there are some gaps between (91 (x)...... .. 9K (x) and
(fn (x)..... πI (x)). thus the prediction may be suboptimal. To quantify the effect of approximation error on the excess risk, denote A(x) the maximum approximation error for all classes, i.e.
A Ax)
max (x, - 7 (x)]-
(18)
jE[K]
Then we show the following theorem. Theorem 2. Denote (x) the second largest conditional class probability given i.e.
(x(x)= max n1(xx)
(19)
j#c
Then
R- R² S / (B2A(()))0)))) (xxxx S 2x)(x))
fxx)xx
(20)
which
(x c + et - A(x).
(21)
Proof. From Proposition the prediction is suboptimal if c(x) of c* (x), which happens only if
9e(x) (x) 2 Ie- (x) (x).
(22)
From the definition of A(x) in 18 22 indicates that
Te(x) (x) 2 (x) 2x(x)
(23)

---

Published as a conference paper at ICLR 2025
From 12 13 and 17 for all j E [K],
K
(x(x) =
Σ
P(Y -X
=1)
1=1
60/2
Em(x)
1 ++
1
1
e512 -
ec12 113 (x),
(24)
1+ e0/2
in which the last step holds since from 4 Ej [x(x)) Therefore, (23 is equivalent to
To(x)) (x) (x) (x).
(25)
in which A. has been defined in 21). Note that for all j * c" (x), the value of i7y (x) is at most n7 (x) (recall the definition (19). Therefore, suboptimal prediction c(x) # (x( can happen only if
r/ (x) (x() - (x.
(26)
26 suggests that as long the gap between the largest and the second largest conditional class probability is large enough with respect to e and the function approximation error A (xx), the classifier
will make an optimal prediction, i.e. Ý = c² (x).
Hence
(x) (x)
if 17" n²(x) (x(x)) - (x)
17 (x) (x)
(27)
0 if 17" (x(x) (x(x)) > (x).
Recall Proposition
[
R - R
E [17 (x) Elmc(x) (x))) f(x)dx)
S E / (1) (x) < 2A.(x)) (x)
(28)
The proof of 20 is complete.
Here we interpret Theorem 2 As union bound on the estimation error of all classes, A(x) usually only grows slightly with K. For example, Appendix C we show that for nearest neighbor classifiers, A(x) grows with VIn K. Deep learning models are much harder to analyze rigorously
(Guo et al. 2017), thus we only provide an intuitive argument in Appendix C to show that with
increasing K, A remains nearly stable. Therefore, from (20), if the shape of 1y" (x) - M (*(x)) is nearly
fixed, then the excess error will not grow significantly with K. This happens if K is large but the
conditional class probabilities given x for most classes are very small.
4.3 PRACTICAL IMPLEMENTATION
Finally, we discuss the practical implementation with deep learning. 15) contains K models 91.....9K' Practically, it is not necessary to construct K neural networks. For the convenience of implementation, we can let Wi...., WK share most parameters, except the last layer. Therefore, we only need to construct one neural network. The last layer can use sigmoid activation to match the privatized vector Z using binary cross entropy loss. This will simplify the implementation and avoid extra computation costs. Compared with non-private learning, our method only introduces O(NK) additional time complexity for label transformation.
Here sigmoid activation at the last layer can not be replaced by softmax, since the randomized vector Z does not sum to Instead, may contain multiple elements with value 1, thus we need to use sigmoid activation that the output
(x)) can approximate (x). . (x)).
Now we summarize the differences between the randomized response method (including its modifica- tions (Ghazi et al. 2021) and our new approach. The differences are illustrated in Figure [ Instead of randomly flipping the label and then conducting one-hot encoding, we use a random vectorization according (12) and (3). The resulting vector may contain multiple elements whose values are 1.
The activation of the last layer is also changed to sigmoid. Correspondingly. the loss function for model training is the binary cross entropy loss, instead of the multi-class version.
7

---

Published as a conference paper at ICLR 2025
Softmax
Sigmoid
One hot
Random
Random
encoding
flip
vectorization
(a) Scalar approximation.
(b) Vector approximation.
Figure I: An illustrative figure to compare randomized response and our new method.
NUMERICAL EXPERIMENTS
5.1 SYNTHESIZED DATA
To begin with, we show some results using randomly generated training samples show how the accuracy affected by increasing the number of classes K. Samples in all K classes are normally distributed with mean Jt, = ....., and standard deviation a. μ4 are set be equally spaced on unit circle. For all experiments,
generate N 10000 training samples. We use the k nearest neighbor method with & = 200 as the base learner of all models. We compare our method with the randomized response, LP-2ST (which uses RRWithPrior randomization) (Ghazi et al. 2021) and ALIBI (Malek Esmaeili et al. 2021). All methods satisfy the label LDP requirement with c I. The results are shown in Figure in which each dot represents the average accuracy score over 1, 000 random trials.
1.0
0.8
Accuracy
0.7
AR
0.6
LP2ST
LP2ST
Durs
Durs
Bayas limit
Bayes
10
20
30
40
50
10
20
30
40
50
K
K
(a) 0.05.
(b) a 2/K.
Figure 2: Comparison of the performances of methods of learning with label DP with varying number of classes K. The purple dashed line denotes the accuracy Bayes optimal classifier
Figure ([a) shows the result using 0.05. The result shows that with small K, our method achieves nearly the same accuracy as existing methods. However, with large K, the vector approximation method (the red line) shows clear advantage
other methods. Recall that our theoretical analysis shows that if 77" (x) n> (x) is fixed, the excess risk will not grow significantly with the number of classes K. However, from Figure a). the accuracy of vector approximation still decreases with K. Our explanation is that with large K, there is stronger overlap between distributions for neighboring classes, thus v7 (x) - 7/. (x) becomes lower on average. According to Theorem 2 the excess risk also larger correspondingly. In Figure 2(b), show the result with 2/ K. so that 17" (x) The (x) remains nearly the same with increasing K. In this case, with increasing K, the accuracy of our vector approximation approach remains stable.
In general, the experiment results with synthesized data validate our theoretical analysis and show that method improves existing methods for cases with large number of classes K. Moreover, show some additional experiments in Appendix A with other parameters, which validates that our method consistently outperforms existing approaches with large K.
8

---

Published as a conference paper at ICLR 2025
5.2 REAL DATA
Now evaluate new method on standard benchmark datasets that have been widely used in previous works on differentially private machine learning, including MNIST (LeCun 1998). Fashion MNIST (Xiao al. 2017) CIFAR-10 and CIFAR- MOAAR--00KKrzhhevsyy
al. 2009p. For the MNIST and
Fashion MNIST datasets, we use a simple convolutional neural network composed of two convolution and pooling layers with dropout rate 0.5, which achieves 99% accuracy for non-private training samples, For CIFAR-I0 and CIFAR-100, we use ResNet-18, which achieves 95% and 76% accuracy for non-private data, respectively. In recent years, many new models have emerged, such that the ofate-of-the the-art accuracies on CIFAR- 10 and CIFAR-100 have been greatly improved, such as vision transformer (Dosovitskiy et al. 2020j. However, we still use ResNet-18 for a fair comparison with existing works. In our experiments, we set the batch size to be 400, and use the Adam optimizer with learning rate 0.001. Since our method significantly different from previous ones in both label generation and loss functions, the optimal parameters of our method are different from those in existing methods. Therefore, we compare all methods with their own optimal parameters. Following conventions of existing works (Wei et al. 2022 De al. 2022 Tramer & Boneh 2021). ignore the additional privacy cost caused by parameter tuning.
Table Experiments on MNIST and Fashion MNIST dataset under different privacy levels using a simple CNN. The accuracy for non-private data is 99%.
6
0.2
0.3
0.5
0.7
1.0
2.0
0.5
1.0
1.5
2.0
RR
58.0
64.1
74.9
89.5
95.3
97.7
RR
59.6
74.6
79.7
84.7
LP-2ST
47.5
64.3
81.4
87.9
91.8
97.7
LP-2ST
60.1
75.6
82.4
85.0
ALIBI
50.9
55.1
84.3
89.4
94.5
97.6
ALIBI
54.3
79.8
80.1
84.9
Ours
63.9
78.4
87.9
93.4
96.2
97.4
Ours
75.7
83.4
84.7
85.9
(b) Fashion MNIST
(a) MNIST
the results MNIST and Fashion MNIST datasets. The number in the table refers the accuracy, i.e. percentage of correct predictions. LP-2ST is the method (Ghazi et al. 2021) using two stages. ALIBI comes from (Malek Esmacili et al. 2021). The results show that our new method outperforms existing methods in general. With large e, such that the accuracy is already close to the non- ooriiiitte case, the accuracy may be slightly lower than existing methods due some implementation details and some random factors.
Table Experiments on CIFAR-10 dataset using ResNet-18. The accuracy for non-private data 95%.
4
LP-1ST
60.0
82.4
89.9
92.6
LP-2ST
63.7
86.1
92.2
93.4
LP-1ST*
67.6
84.0
90.2
92.8
LP-2ST*
70.2
87.2
92.1
93.5
ALIBI
71.0
84.2
Ours
75.1
91.6
92.7
93.2
Table shows the result with the CIFAR-10 dataset. In the table, LP-1ST* and LP-2ST* refer to the LP-1ST and LP-2ST methods, respectively, in which models have been pretrained with the CIFAR- 100 dataset, which is regarded as public and no privacy protection is needed. Such setting follows (Abadi et al.) (016)). The results of the first four rows of Table come from (Ghazi et al. 2021). Table 1. The fifth row is the result of ALIBI, which comes from (Malek Esmaeili et al. (022)) Table 1. For the CIFAR- dataset,
method outperforms existing approaches with small c. Note that our method does not use pre-training. However, the results are still better than existing methods even with pre-training. Similar the experiment of the MNIST dataset, the advantage of our method

---

Published as a conference paper at ICLR 2025
becomes less obvious when e is large, and the accuracies of existing methods are already close the non-private baseline.
TableB]shows the result with the CIFAR- 100 dataset. The results of LP-2ST and ALIBI come from Table 2 in (Ghazi et al. 202T) and (Malek Esmaeili et al., 202T). respectively. The results show that method significantly outperforms LP-2ST and ALIBI. The advantage of our method is especially obvious with small c. It is worth mentioning that ALIBI calculates the soft label instead of conducting just label flipping. The soft label can be expressed by vector, thus the idea of ALIBI shares some similarity with our vector approximation method. As a result, ALIBI performs significantly better than LP-2ST. However, from Table 3 our method also outperforms ALIBI.
Table 3: Experiments on CIFAR-100 dataset using ResNet-18. The accuracy for non-private data is 76%.
2
3
4
5
6
8
LP-2ST
28.7
50.2
63.5
70.6
74.1
ALIBI
55.0
65.0
69.0
71.5
74.4
Ours
64.4
67.7
71.8
73.8
74.1
74.4
Here we summarize the experimental results. The synthesized data shows that our vector approxi- mation method has relatively stable performance with the increase of the number of classes K. As a result, with large K, our method has a significantly better performance compared with existing methods. Such observation agrees well with our theoretical analysis in Section 4.2 We have also tested the results using benchmark datasets, which validate our method in real scenarios. It worths mentioning that several works central label DP achieve better accuracy than those reported here, such as PATE (Malek Esmaeili et al., 2021) and its improvement in (Tang et al. 2022). As a weaker privacy requirement compared with label LDP, these results under central label DP not comparable to our results.
CONCLUSION
In this paper, have proposed method for classification with label differential privacy based on vector approximation. The general idea is to generate a noisy random vector first to protect the privacy of labels and train the model to match the privatized vector. Compared with existing scalar approximation methods, which conduct label flipping and let the flipped label match the model outputs, our method has better theoretical convergence properties and empirical performances. In particular, our method solves the problem of the degradation of utility with large number of classes K. Our analysis suggests that the prediction optimal as long as the gap between the largest and second largest conditional class probability is enough, thus the risk only grows slightly with K. Moreover, our method is easier to implement and only requires O(NK) time for label privatization. Numerical experiments with both synthesized data and standard benchmark datasets validate the effectiveness of our proposed method.
ACKNOWLEDGEMENT
The work of Li Shen is supported by STI zhen Basic Research Project (Natural Science Foundation) Basic Research Key Project (NO. JCYJ2024 202 124430041), the Major Project in Judicial Research from Supreme People's Court (NO. GFZDKT2024C08-33 and CCF-DiDi GAIA Collaborative Research Funds (NO. CCF-DiDi GAIA 202419). The work of Zhikun Zhang is supported in part by the NSFC under Grants No. 62441618, 62402431, and Zhejiang University Education Foundation Qizhen Scholar Foundation. The work of Zhe Liu is supported by National Science Foundation China
Projects (No. 20212D0201405), Shen-
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Jayadev Acharya, Clément L Canonne, Ziteng Sun, and Himanshu Tyagi. Unified lower bounds for interactive high-dimensional estimation under information constraints. Advances in Neural Information Processing Systems, 36, 2024.
Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. Annals of Statistics, 2007.
Ashwinkumar Badanidiyuru, Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Jacob Leeman, Pasin Manurangsi, Avinash V Varadarajan, and Chiyuan Zhang. Optimal unbiased randomizers for regression with label differential privacy. In "hirrt--evenni Conference on Neural Information Processing Systems, 2023.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions Information theory, 39(3):330-99) 0400999951111 1993.
Róbert Istvan Busa-Fekete, Andrés Muñoz Medina, Umar Syed, and Sergei Vassilvitskii. Label differential privacy and private training data release. In International Conference on Machine Learning, volume 202. pp. 2231-3251, 2023.
Adrian Bussone, Bakita Kasadha, Simone Stumpf, Abigail C Durrant, Shema Tariq, Jo Gibbs, Karen C Lloyd, and Jon Bird. Trust, identity, privacy, and security considerations for designing a peer data sharing platform between people living with hiv. Proceedings of the ACM Human- Ctman--omppter Interaction, 4(CSCW2):1-22 2020.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor classification. Advances in Neural Information Processing Systems, 27, 2014.
Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 155-186, 2011.
Lynn Chua, Qiliang Cui, Badih Ghazi, Charlie Harrison, Pritish Kamath, Walid Krichene, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash V. Varadarajan, and Chiyuan Zhang. Training differentially private ad prediction models with semi-sensitive features. CORR, abs/2401. 155446, 2024.
Paul Cuff and Langing Yu. Differential privacy as a mutual information constraint. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 43 54, 2016.
Teddy Cunningham, Konstantin Klemmer, Hongkai Wen, and Hakan Ferhatosmanoglu. Geopointgan: Synthetic spatial data with local label differential privacy. CoRR, fas/22055088880 2022.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint drX55 2022.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances in Neural Information Processing Systems, 30, 2017.
Maik Döring, László Györfi, and Harro Walk. Rate of convergence of k-nearest-neighhorr classification rule. Journal of Machine Learning Research, 18(227):1-16. 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
Cynthia Dwork, Frank McSherry. Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York NY, USA, March 4-7, 2006. Proceedings 3, pp. 265- 284. Springer, 2006.
11

---

Published as a conference paper at ICLR 2025
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-10677 2014.
Hossein Esfandiari, Vahab Mirrokni, Umar Syed, and Sergei Vassilvitskii. Label differential privacy via clustering. In International Conference Artificial Intelligence and Statistics, pp. 7055-7075. PMLR, 2022.
Jun Feng, Yefan Wu, Hong Sun, Shunli Zhang, and Debin Liu. Panther: Practical secure two-party neural network inference. IEEE Transactions on Information Forensics and Security, 2025.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy, Advances in Neural Information Processing Systems, 34:27131- 27145, 2021.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan, and Chiyuan Zhang. Regression with label differential privacy. The Eleventh International Conference Learning Representations, 2022.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, and Chiyuan Zhang. On convex optimization with semi-sensitive features. In The Thirty Seventh Annual Conference Learning Theory, pp. 1916-1938. PMLR, 2024.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. In International Conference on Machine Learning, pp.
PMLR, 2016.
Walid Krichene, Nicolas Mayoraz, Steffen Rendle, Shuang Song, Abhradeep Thakurta, and Li Zhang. Private learning with public features. In International Conference Artificial Intelligence and Statistics, volume 238, pp. 4150-4158, 2024.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Meelis Kull, Miquel Perello Nieto, Markus Kängsepp. Telmo Silva Filho, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration. Advances in neural information processing systems, 32, 2019.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
Shiyu Liang and R Srikant. Why deep neural networks for function approximation? In International Conference on Learning Representations, 2016.
Yuheng Ma, Ke Jia, and Hanfang Yang. Locally private estimation with public features. arXiv preprint arXiv:2405. 13481, 2024.
Mani Malek Esmacili, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramer. Antipodes of label differential privacy: Pate and alibi. Advances Neural Information Processing Systems, 34: 6934 6945, 2021.
Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner. Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. Ad click prediction: a view from the trenches. Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1222-1233 2013.
Frank McShery and Iyya Mironov. Differentially private recommender systems: Building privacy into the netflix prize contenders. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 627-636. 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
12

---

Published as a conference paper at ICLR 2025
Joe Near. Differential privacy at scale: Uber and berkeley collaboration. In Enigma 2018 (Enigma 2018), 2018.
Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. International Conference on Leurning Representations, 2017.
Sivaramakrishnan Rajaraman, Prasanth Ganesan, and Sameer Antani. Deep learning model calibration for improving performance in class-imbalanced medical image classification tasks. PloS one, 17 (1):e0262838, 2022.
Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprini arXiv:1709.008 2017.
Xinyu Tang, Milad Nasr, Saeed Mahloujifar, Virat Shejwalkar, Liwei Song, Amir Houmansadr, and Prateek Mittal. Machine learning with differentially private labels: Mechanisms and frameworks. Proceedings on Privacy Enhancing Technologies, 2022.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference Learning Representations, 2021.
Alexandre B Tsybakov. Introduction to Nonparametrie Estimation. 2009.
Kaixin Wang, Kuangqi Zhou, Qixin Zhang. Jie Shao, Bryan Hooi, and Jiashi Feng. Towards better laplacian representation in reinforcement learning with generalized graph drawing. In International Conference on Machine Learning, pp. 1102211102.. PMLR, 2021.
Weina Wang, Lei Ying, and Junshan Zhang. On the relation between identifiability. differential privacy, and mutuallinformation privacy. IEEE Transactions on Information Theory, 62(9):5018- 5029, 2016.
Zihao Wang, Rui Zhu, Dongruo Zhou, Zhikun Zhang, John Mitchell, Haixu Tang, and XiaoFeng Wang. Dpadapter: Improving differentially private deep learning through noise tolerance pre- training. In 33rd USENIX Security Symposium (USENIX Security 24), pp. 991-1008, 2024.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69 1965.
Chengkun Wei, Minghu Zhao, Zhikun Zhang, Min Chen, Wenlong Meng, Bo Liu, Yuan Fan, and Wenzhi Chen. Dpmlbench: Holistic evaluation of differentially private machine learning. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 2621-2635, 2023.
Jianxin Wei, Ergute Bao, Xiaokui Xiao, and Yin Yang. Dpis: An enhanced mechanism for differen- tially private sgd with importance sampling. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 2885-2899, 2022.
David Widmann, Fredrik Lindsten, and Dave Zachariah. Calibration tests in multi-class classification: A unifying framework. Advances in neural information processing systems, 32, 2019.
Ruihan Wu, Jin Peng Zhou, Kilian Q. Weinberger, and Chuan Guo. Does label differential privacy prevent label inference attacks? In International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 4336-4347, 2023.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1rXiv:170..07744 2017.
Zheng Xing and Weibing Zhao. Segmentation and completion of human motion sequence via temporal learning of subspace variety model. IEEE Transactions on Image Processing, 2024.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In
Conference learning theory, pp. 639-649, PMLR, 2018.
13

---

Published as a conference paper at ICLR 2025
Di Zhang. Stochastic Conjugate Subgradient Framework for Sarree-Scaleeee Stochastic Optimization Problems. PhD thesis, University of Southern Califoria,, 2024.
Di Zhang and Suvrajeet Sen. The stochastic conjugate subgradient algorithm for kernel support vector machines. arXiv preprint arXiv:2407.2100), 2024.
Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodu- lar maximization: Boosting via non-oblivious function. International Conference on Machine Learning, pp. 1611643613. PMLR, 2022.
Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. [PrivSyn]: Differentially private data synthesis. In 30th USENIX Security Symposium (USENIX Security 21), pp. 929-946, 2021.
Puning Zhao and Lifeng Lai. Minimax rate optimal adaptive nearest neighbor classification and regression. JEEE Transactions Information Theory, 67(5):3155-3182 2021.
Puning Zhao and Lifeng Lai. Analysis of knn density estimation. IEEE Transactions on Information Theory, 68(12):971-77995 2022.
Puning Zhao, Chuan Ma, Shen, Shaowei Wang, and Rongfei Fan. On theoretical limits of learning with label differential privacy. arXiv preprint arXi:2250.143000 2025.
Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. Calibrating predictions to decisions: A novel approach to multi-class calibration. Advances in Neural Information Processing Systems, 34:22313-22324 2021.
Zhen Zhao, Jingqun Tang, Chunhui Lin, Binghong Wu, Can Huang, Hao Liu, Xin Tan, Zhizhong Zhang, and Yuan Xie. Multi-modal in-context learning makes ego-evolving text recognizer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
15567-15576, 2024a.
Zhen Zhao, Jingqun Tang, Binghong Wu, Chunhui Lin, Shu Wei, Hao Liu, Xin Tan, Zhizhong Zhang, Can Huang, and Yuan Xie. Harmonizing visual text comprehension and generation. 2024b.
A ADDITIONAL NUMERICAL EXPERIMENTS
Here we present some additional experiments.
Higher Figure 2 shows the result with 1. Now set 2, and the results shown in Figure
1.00
0.89
0.95
Accumsty
0.90
RR
LP2ST
0.86
LP2ST
Ours
0.85
Ours
Bayes
Bayes
10
20
30
40
50
10
20
30
40
50
(a) 0.05.
(b) 2/K.
Figure 3: Experiments with simulated data with 2, A: 100.
With a weaker privacy requirement c c= 2, the performances of all methods become better. The vector approximation method still outperforms existing methods.
Other k. Now we still use e = 1. However, recall that previous experiments use = 200. Now we use nearest neighbor method with & 100 the base learner.
14

---

Published as a conference paper at ICLR 2025
1.0
0.8
0.8
0.7
Accuracy
RR
0.5
LP2ST
LP2ST
0.4
0.4
Durs
Durs
Bayas limit
Bayes
0.2
10
20
30
40
50
10
20
30
40
50
K
(a) 0.05.
(b) 2/K.
Figure 4: Experiments with simulated data with 1, k: 100.
B COMMENTS ON EXISTING METHODS
In this section, show some negative results of existing methods, which indicate that the perfor- mance decreases with K inevitably.
B. SCALAR APPROXIMATION METHODS
Here we show that for all scalar approximation methods, which transform the label Y to Z, the probability of retaining the original label decreases with K.
Denote Mij = P(Z = =j = i) as the transition probability. Then Mú, = P(Z i/y = i) is the probability of retaining the original label i. The transition probability matrix normalized, i.c. Σ M,j 1. From the e-label LDP constraint, Mü e Mye for all j. Taking sum over and j. the following inequality holds:
K
K
M
e M Ke..
j=1
Therefore, the average probability of retaining original label satisfies (1/K) Σ M₁ S e E//K, which decays inversely with K. The result indicates that for all scalar approximation methods, the performance degrades inevitably with larger K.
B.2 ALIBI
ALIBI (Malek Esmaeili et al.) 2021) generates a soft label for each input, which partially solves the problem caused by scalar approximation. The algorithm runs as follows. Firstly, let OneHot(Y)) + W, which W Lap(A). Then o e-LDP with respect to Y. thus any learning algorithms based any post-processing of satisfies e-label LDP. If we assume uniform prior, then the soft label is generated as follows:
p c/o, A) (oftmax((fo.)/)))
(29)
in which f(o.) = - De Oox - |c k|], and [.] is the Iverson bracket.
Now show that the performance of ALIBI decays with K by a simple example. Suppose that for all v, n (2r) = 1, (2)) = 1I (x) 0. Then all samples have label 1. According to (2)), can be shown that the probability of making correct prediction is upper bounded by
p(Y 110, <
(30)
Σx 1(f(ac) 2 f(o1))
1 21)
1(.
The second inequality holds because if o, 2 01, then it can be shown that f(o.) 2 s(01).
15

---

Published as a conference paper at ICLR 2025
Recall Algorithm 3 in ALIBI paper, 01 = =1+ W1, o. = for ....., K, in which W, Laplace(A) X) for all j 1...., K. Therefore, expectation, > (0, 2 01) grows linearly with K. As result, p(Y = 1|,, X) decays nearly inversely with K.
From the example above, can found that the performance ALIBI decays significantly with K.
C FURTHER ARGUMENTS ABOUT APPROXIMATION ERROR
C.I NEAREST NEIGHBOR METHOD
Now bound A for k nearest neighbor approach. which has been extensively analyzed in literatures (Chaudhuri & Dasgupta 2014 Döring et al. 2018 Zhao & Lai 2021 Recall that the output structure expressed in (15). For the KNN classifier, let
(x(x)
Σ
2,0),
(31)
iEN(()
in which (x) is the of nearest neighbors of x among
Define px-(x) = [B(x.) f(u)du as the probability mass of B),,r), in which f is the pdf of feature
vector X. Define
ro(x) inf { (x)
2k
(32)
Define p(x) max (x)
X x|| as the kNN distance. Assume that my (x) is L-Lipschitz. Now bound the approximation error as follows.
(x) - 175 (x))
Σ
Zi(i) (x)
(x)
(Z((1) (X.))
(x, mx(xx)
k
k ixAx
iENo (x)
e/2
(Zi(f) 7x.))))
e Lp(x);
(33)
k
(x)
in which the last step uses
24
From Hoeffding's inequality.
Σ (Z.() - f (X.))
> V 2k In
2K
S K
(34)
k (x
Moreover, define n(xx r) as the number of samples in B(x, r), then P(((x) ro(x))
< P(n(x, rx(x)) k)
<NN proPscc) &
S (x) (x)
k
2k (2e)* = (11-n (1-12
(35)
From 33 (1 2
334)
and
35 consider the definition of A in 18 with probability at least - 8
2K
e
(x)
In
Lro.
(36)
2k
e0/2
To avoid confusion, emphasize that lowercase k is the number of nearest neighhor used in the kNN method, while K is the numher of classes.
16

---

Published as a conference paper at ICLR 2025
which grows with Vln.
Finally, we discuss the convergence of A(x) (and the excess risk) with respect to N. With fixed k according (36). A(x) does not converge to zero even if N + oo. Therefore, let grows with 2V with an appropriate speed. We now focus on the case with < 1. In (36) in our paper, assuming that the density is bounded away from zero, then from (32 To ~ e (k/N)
need to
Therefore, to minimize the right hand side of (36). we can let k ~ 6 N2 22/(2+2) (here we neglect logarithmic factors), then A (x) decays with N we have A. (z) ~ (W22)1/((+3) Therefore
According to (20 and 21
R 2 (Ne)) 1/(42))
In addition. in nonparametric classification, commonly used assumption is "Tsybakov margin
condition [Tsybakov] 2009); Audibert & Tsybakov 2007)". which says that P(0 < 17" (X) 17, (X) <
1) $ 17 for some In this case, the convergence rate of the excess risk becomes faster, R R S
(Ne) (N22)((++//(4+2))
C.2 NEURAL NETWORK
Neural networks are much harder analyze compared with traditional methods like kNN. Here we just provide an argument to intuitively show that the approximation Jj gy(x) = (x) holds.
In deep neural network models, the parameters can be expressed as w (W1.... Wk) W1 x X WK. and the output (15) is now 9j (x) = hy [w] x). in which h, is the output of j-th neural network model. w is trained using (X,, Z.), = 1,..., N to minimize the empirical loss:
w arg min
Σ (w/ X,), Z.()), E [K],
(37)
WyEW, N
in which is the surrogate loss function used for training. A typical choice of l is the binary cross entropy loss.
Let 92 Ob Iwy E Wj} be the set of all possible functions Øj parameterized by w,. Then
from 377.
min Ma (wj. X.), Z(0)
(mu(x))
(38)
N 1=1
wEB, N
Denote
{g: : X + [0, 1}} as the set of all functions mapping from X' to [0, 1]. Then
2
( Z())(
min B[((u(X)),
MEG;
(b) min [[((u(()) (X), (((()()),(())
wEg
E
min
Z())|X x]
(39)
wEg
In 339.. (a) holds because from weak law of large number, the right hand side of (38) converges to its expectation. For the left side of (38), theories about generalization has been widely established
(ohri et al.) 2018). The generalization gap converges to zero with the increase of sample size
N. (b) uses the universal approximation theorem (Barron 1993 [Liang & Srikant 2016) Yarotsky 2018). For neural network that is sufficiently wide and deep, each function in 9 can be closely approximated by function in Gy-
From now on, suppose that ( is the binary cross entropy loss, i.c. l(g.p)) p) = -p In (1 -1 In(1 1 q). can be shown that ñ (x) is the minimizer of B[[(u(x), 2()) X x]. Recall that is defined as
the set of all functions mapping from X' to [0, 1]. Hence, 9j (w]) E G. This implies
E [1 (w). X). Z()) 2 E minE]((u(x)) 2 x
(40)
mEG
From 39 the left hand side of (40) is larger than the right hand side too much. Therefore, there
exists 0 > 0 such that
S [[ x), (()) s E min 20)) = xx] + (41)
min E (x((), Z()) = x)
uEg
wEg
17

---

Published as a conference paper at ICLR 2025
Recall the steps in 39 8 goes to zero with the increase of model complexity and sample size N.
continuous in x. Then (g) x), Z()) is also continuous in x. As result, ((g, (wj. x), ()) can not be much larger than minweg ((((( Z()) = x], otherwise there will a neighborhood of x called M (xx., such that [(g) (w). x'), Z()) is much larger than mingeg [[((u(x'), ( X = x'| for all x' (x)),, which violates the second incquality (41). Therefore,
Assume that g, (w(w).
Eg x), - = x] ~ minE)((u(x) x].
(42)
wEG
Recall that denotes the binary cross entropy loss, thus
[(u(x), Z()) (n) (1 - Z())) In - u(x)).
(43)
Recall the definition of ii in 17 we have
[x)(((x), 2()) = - (x) In (xx - (1 - (x)) In(1 - =(()).
(44)
To minimize x = x]. we have u(x) = (x). Therefore, from 42
gy(x) h x) ñl (x).
(45)
Such argument holds for all j = 1, ...., K. Recall (8) Axx) can be obtained by a union bound of gx)x) 72 (x).
18


Reviews:
[{"review_id": "WHHpNq8ew2", "reviewer": "Reviewer_zGeU", "summary": "This paper consider the problem of supervised multi-class learning problem under the setting of \"label differential privacy\" (LDP). This is a setting that is well-studied in recent literature, where the input features are considered public, and only the label is considered sensitive and needs to be protected by differential privacy.\n\nThis paper proposes a new randomizing mechanism that satisfies LDP, and outperforms prior methods studied in literature. The new method is as follows: Suppose there are $K$ possible labels. Given any label $y \\in [K]$, construct the $K$-dimensional one-hot encoding of $y$ and apply the (binary) Randomized Response mechanism on each bit of the one-hot encoding, flipping each bit with probability $\\frac{1}{1 + e^{\\epsilon/2}}$.\n\nA theoretical analysis is done for the k-nearest neighbor learning rule showing that the excess risk grows as $\\sim \\sqrt{\\ln K}$ with increasing $K$ (keeping other parameter fixed).\n\nExperimental results show that this approach outperforms prior methods studied in literature on a synthetic dataset (mixture of Gaussians data with centers around a circle) as well as real data (MNIST, CIFAR).", "questions": "In particular, [Ghazi et al. '21](https://arxiv.org/abs/2102.06062) have an analysis in Appendix F where they show that the excess risk of learning with stochastic gradient descent is $K / \\sqrt{N}$ for pure-DP and $\\sqrt{K / N}$ for approximate-DP. A subsequent paper by [Ghazi et al. '24](https://arxiv.org/abs/2406.19040) provides a more complex method that can theoretically achieve a excess empirical error rate of $\\sqrt{(\\log K) / N}$.\n\nBut I think the $\\sim \\sqrt{(\\log K) / k}$ scaling does not exactly say how the excess error scales with $N$. I would imagine that as $N \\to \\infty$, the optimal learning rule would also be scaling $k$ in some way, and not keep it fixed. I think this analysis might bring in dimensionality factors into the picture, which are necessary for understanding the precise scaling of excess risk with $N$.\n\n---\n\nOn 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)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a simple method and shows that it outperforms prior methods proposed in literature of LP-MST (Label Privacy Multi Stage Training [[Ghazi et al. '21](https://arxiv.org/abs/2102.06062)]) and ALIBI [[Malek et al. '21](https://arxiv.org/abs/2106.03408)].\n\nThe method is also simple to implement with minimal computational overhead relative to prior methods.\n\nThe paper is well written and easy to follow.", "weaknesses": "I feel there is rooom for making the paper stronger on the theoretical side.\n\nI 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 \\to \\infty$ (see more details about this under \"Questions\").\n\nNevertheless, I find it quite interesting that such a simple method shows a clear improvement over prior methods in the experiments, and so I don't think of the above as a significant weakness, since the theoretical analysis is not critical for the experimental results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "8r7Xyg4Ivm", "reviewer": "Reviewer_Vdjs", "summary": "This paper introduces a new approach to local label differential privacy, transforming each label into a K-dimensional vector, where each component is independently randomized with a RAPPOR-like mechanism. This vector-based approach preserves more information than scalar label transformations while maintaining ε-local differential privacy. The authors provide theoretical analysis showing that their method's performance only degrades slightly with increasing number of classes K. They empirically validate their approach using both synthetic data and standard benchmark datasets (MNIST, Fashion-MNIST, CIFAR-10, CIFAR-100), demonstrating that their method significantly outperforms existing approaches, especially when the number of classes is large and the privacy requirements are strict (small ε). Notably, proposed method outperforms a similar approach proposed by Malek Esmaeili et al. (2021), also relying on expanding a label to a vector of probabilities and adding noise to the vector.", "questions": "1. Can you elaborate your reasoning on the line 107: \"However, ALIBI generates outputs using Bayesian inference and normalizes them to 1 using a softmax operation. Intuitively, such normalization causes bias\"?\n2. 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?\n3. To be pedantic, line 87 should say \"Malek Esmaeili et al. (2021) proposes PATE-FM\". Original PATE was introduced by [Papernot et al., 2016](https://arxiv.org/abs/1610.05755), and is not specific to label DP.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper studies an important and well defined problem of label DP, which however does not get as much attention in the literature as traditional DP, while being relevant for many practical applications\n2. The paper proposes a novel method to provide local label-only DP guarantees, and thoroughly explores it. The proposed method provides better utility (at the same privacy budget) compared to the prior methods on standard benchmarks. The paper provides necessary proofs of privacy guarantees, as well as general intuition behind the method.\n3. The paper does a good job of putting this work in the context of the overall field, providing important details of prior works (notably, by Malek Esmaeili et al. (2021) as it shares the most similarities with the current paper)\n4. The evaluation protocol looks solid and follows standard practices and baselines, including what is typically used by prior works.\n5. The proposed practical implementation is quite neat, making the implementation of the method computationally efficient.", "weaknesses": "At it's core, the proposed method can be summarised as applying technique from RAPPOR (Erlingsson et al. (2014)) to the \"soft label\" approach to label DP introduced by ALIBI (Malek Esmaeili et al. (2021)). Both techniques are properly acknowledged by the authors, and combining two existing techniques in a novel way is not a weakness by itself. Especially given the strong empirical results and accompanying theoretical analysis. \n\nHowever, I believe this should affect the focus of the analysis. In particular, the main focus area for the theoretical part of the paper is answering the question \"how does the excess risk grow with the number of classes K\", implicitly comparing it with the randomized response and RRWithPrior (Ghazi et al. (2021)), which are known to degrade in utility with growing K. 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. Or, if the analysis of $\\Delta(x)$ is relevant for comparison with ALIBI, it needs to be shown.\n\nAdditionally, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "p51BWensEe", "reviewer": "Reviewer_DCbg", "summary": "This paper introduces a new (?) approach for local label differential privacy (LDP) in machine learning, presenting both the theoretical framework and a numerical evaluation of the proposed method’s effectiveness. This method is based on a component-wise randomised response mechanism on the one-hot encoding of the class.", "questions": "Could the authors provide justifications or address the weaknesses mentioned above, especially regarding the novelty of the method and the theoretical basis of the claimed improvements? If these concerns are adequately addressed, I would be open to revising my rating and overall assessment of the paper.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-organized and easy to follow, helping readers grasp the main ideas and methodology.\n- The authors provide a numerical evaluation of the proposed methods, which helps to demonstrate its performance in practice.\n- The authors provide a semi formal justification of the performance of the proposed method", "weaknesses": "- 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.\n- 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.\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "37bFTKqWUT", "reviewer": "Reviewer_nJ8J", "summary": "This paper introduces a vector approximation method aimed at improving label differential privacy (label DP) for large multi-class datasets. By encoding labels as vectors rather than scalars, the authors argue that this approach retains more class information, enabling better performance in high-class settings where traditional label DP methods degrade significantly. They present both theoretical analysis and empirical validation on synthesized and benchmark datasets, demonstrating superior accuracy, especially as the number of classes $K$ grows.", "questions": "- What is the purpose of the footnote in Table 3?\n\nAlso, see weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper addresses a meaningful problem: label LDP learning with a large number of label classes. This has important practical relevance, particularly in applications with long-tailed data distributions.\n- The paper proposes a simple yet effective technique to tackle this issue.\n- The theoretical results are adaptable and could be extended to various scenarios under specific assumptions (e.g., smooth regression functions).\n- The experimental results demonstrate significant improvements over previous methods.", "weaknesses": "- 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. Additionally, could the authors establish any lower bounds for previous methods that use scalar labels alone (and possibly find the phase transition between $\\log K$ and $K$ dependence)? Such bounds would clearly demonstrate the necessity of the proposed method. \n- The experiments were conducted on standard datasets. It would be valuable for the authors to conduct experiments on datasets with long-tailed distributions to highlight the method's practical relevance. Furthermore, it would be interesting to discuss how a long-tail distribution or class imbalance might impact the theoretical guarantees of the algorithm.\n- The paper is somewhat repetitive and could benefit from further editing for conciseness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": {}}]

Author rebuttal:

Decision: Accept (Spotlight)