Not final; page numbers may change before publication
Proceedings on Privacy Enhancing Technologies ; 2022 (4):332–350

Xinyu Tang*, Milad Nasr, Saeed Mahloujifar, Virat Shejwalkar, Liwei Song, Amir Houmansadr,
and Prateek Mittal

Machine Learning with Differentially Private
Labels: Mechanisms and Frameworks
Abstract: Label differential privacy is a relaxation ofdifferential privacy for machine learning scenarios where
the labels are the only sensitive information that need
to be protected in the training data. For example, imagine a survey from a participant in a university classabout their vaccination status. Some attributes of thestudents are publicly available but their vaccination status is sensitive information and must remain private.
Now if we want to train a model that predicts whether
a student has received vaccination using only their public information, we can use label-DP. Recent works onlabel-DP use different ways of adding noise to the labels in order to obtain label-DP models. In this work,
we present novel techniques for training models withlabel-DP guarantees by leveraging unsupervised learning and semi-supervised learning, enabling us to inject
less noise while obtaining the same privacy, therefore
achieving a better utility-privacy trade-off. We first introduce a framework that starts with an unsupervisedclassifier f0 and dataset D with noisy label set Y , reduces the noise in Y using f0 , and then trains a newmodel f using the less noisy dataset. Our noise reduction strategy uses the model f0 to remove the noisylabels that are incorrect with high probability. Then weuse semi-supervised learning to train a model using theremaining labels. We instantiate this framework withmultiple ways of obtaining the noisy labels and also thebase classifier. As an alternative way to reduce the noise,
we explore the effect of using unsupervised learning: weonly add noise to a majority voting step for associating
the learned clusters with a cluster label (as opposed toadding noise to individual labels); the reduced sensitivity enables us to add less noise. Our experiments showthat these techniques can significantly outperform theprior works on label-DP.
Keywords: Differential Privacy; Label Differential Privacy
DOI 10.2478/popets-2022-0112
Received 2022-02-28; revised 2022-06-15; accepted 2022-06-16.

*Corresponding Author: Xinyu Tang: Princeton University, E-mail: xinyut@princeton.edu

1 Introduction
With emerging applications of machine learning (ML),one of the important requirements of ML models is topreserve privacy of datasets used to train them. Differential privacy (DP) [16, 17] has become the gold
standard of privacy where the training algorithm is required to output a model that will not be too different
from the output of the same algorithm on a neighboringdataset (i.e., the value in one of its elements is swapped).
This DP definition establishes a strong requirement that
preserves the privacy of each individual example in the
training set. However, the existing techniques that provably satisfy DP often suffer from a drop in utility compared to training algorithms without privacy. As a result, researchers study alternative definitions of privacy.
One recently proposed definition of privacy for machine learning is label-DP [23], which is also one kind of
AttributeDP [29]. In label-DP, the privacy constraint isonly imposed on the label set. That is, for a feature set
X and label set Y , the ML algorithm L will output amodel f which satisfies label-DP if f (X, Y ) ≈ f (X, Y 0 ),where Y 0 is a neighboring label set. This definition ismotivated by applications where the feature sets are
publicly available and the labels are the only thing thathave to be protected. For instance, the features could be
the attributes of users of an online social network andthe labels be if the users suffer from mental distress. Using (regular) DP for such a scenario may cause a drop in
utility because DP will provide privacy for the features
as well. For example, imagine a survey from a participant in a university class about their vaccination status.
Some attributes of the students are publicly available
but their vaccination status is sensitive information andmust remain private. Now if we want to train a model topredict whether a student has received vaccination us-

Milad Nasr, Virat Shejwalkar, Amir Houmansadr:
University of Massachusetts Amherst, E-mail: {milad, vshejwalkar, amir}@cs.umass.edu
Saeed Mahloujifar, Liwei Song, Prateek Mittal: Princeton University, E-mail: {sfar, liweis, pmittal}@princeton.edu

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

ing only their public information, we can use label-DP
because other attributes are already public and trying
to protect their privacy will cause an unnecessary drop
in utility.
As the main incentive for choosing label-DP over
DP is improving the utility of the trained models, it isimportant to use the most recent advancements in ML
for such problems. Since prior works [23, 35] for labelDP focus on noise addition algorithm design instead of
how to improve the utility for label-DP, we explore classification algorithms that succeed with imperfect labels.
In particular, the main question in this work is:
How to optimize utility with label-DP, using classification
algorithms that work with imperfect labels?

Specifically, we consider unsupervised learning andsemi-supervised learning as ways for obtaining improved
trade-offs between utility and privacy.

1.1 Our Contributions
Using unsupervised learning to add less noise andreduce the effect of noise: Because unsupervised
learning does not use labels for training, it can be leveraged in the label-DP setting without incurring additional label privacy loss. The noise is only added when
performing majority voting on the non-private labels ina cluster to assign a cluster label, and therefore the sen√sitivity is much reduced (`2 sensitivity is only 2 regardless of set size: changing one of the labels, the numberof votes on one class increases by 1 and it decreases by 1
on the other class). We name this technique NoiseCluster, which would be effective when ε is extremely low asa result of much reduced sensitivity.
Another alternative way to leverage unsupervised
learning is to generate cluster labels, which can be used
as a component of DenoiseSSL (explained later) used
to denoise any differentially private label set.
Using semi-supervised learning to reduce the effect of noise: Most of existing techniques proposed
for label-DP use label noise. The label-DP mechanism(e.g., randomized response) adds noise to the labels andreleases the features with the noisy labels. Then, using post-processing arguments, any model trained using
standard learning algorithms on this data also enjoys
label-DP. Leveraging semi-supervised learning (SSL),
we propose a framework that performs a label denoising
step on the dataset before applying the learning algorithm. Our denoising algorithm, DenoiseSSL, leverages

333

the cluster label set from unsupervised learning to identify the labels that are correct with high probability andremoves other labels from the label set. Then it applies
SSL to train the model with the partial set of labels.
A comprehensive comparison with existing techniques: We instantiate our framework using noisemechanisms proposed in PATE-FM [35] and randomized response [23, 56] as well as our proposed techniques
which enables less injected noise, and perform comprehensive experiments on mainstream datasets such as CIFAR10, CIFAR100, and CINIC10. Our evaluations showthat our framework can significantly improve the utilityof obtained models for the entire (reported) range of ε.

1.2 Technical Overview
Label differential privacy is proposed as a relaxationof differential privacy for scenarios when we only need
the labels to remain private. In order to leverage thisrelaxation, existing techniques for label-DP use the factthat we do not need to manipulate the features and only
add noise to the labels. That is, given a labeled dataset(X, Y ) they apply a DP mechanism M on labels andthen they apply a ML algorithm L on (X, M (Y )) to get
the final label-DP model f .
In this work, we take one step beyond this and leverage unsupervised learning and semi-supervised learning.
Denoising framework through unsupervised learning and semi-supervised learning (DenoiseSSL):
DenoiseSSL purifies the noisy labels and converts them
to a smaller set of labels but with higher precision. DenoiseSSL uses a classifier f0 (we consider f0 trained using unsupervised learning) to generate a pseudo label set
without incurring additional privacy cost. We only include labels for samples which have the same noisy label
and pseudo label, and our analysis shows that the average correctness of the remaining labels could be muchhigher than that of all noisy labels. After obtaining thispartial, high quality set of labels, we can apply semisupervised learning on all the instances and the partial
set of labels. Our experiments show that this technique
can achieve better accuracy compared to training witha complete set of noisy labels.
Adding less noise through unsupervised learning (NoiseCluster): When assigning the cluster label
by majority voting over non-private labels in the unsu√
pervised learning model, the sensitivity is 2; we thenadd Gaussian noise to the voting statistics based on thisNot final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

to get the desired privacy level (NoiseCluster). No noise
will be added to individual samples.
Summary of experimental results: Our framework consists of two parts: noise addition mechanisms and learning with the private labels. The noise
addition mechanisms include existing noise mechanisms [23, 35] and our proposed NoiseCluster. To improve the utility for label-DP, in addition to DenoiseSSL, we have also investigated algorithms inlearning with noisy labels area and leveraged AugDescent [39]. Our framework significantly outperforms
previous works (LP1ST (+mixup) [23] and ALIBI [35])on CIFAR10, CIFAR100 and CINIC10 datasets at ε =0.5, 1, 2, 3, 4, 6. For example, our framework achieves
56.2% higher accuracy than LP1ST and 60.8% higher
accuracy than ALIBI on CIFAR10 at ε = 0.5. We also
make specific recommendations regarding our framework based on the value of ε and other factors in Section 6.

2 BackgroundIn this section, we briefly introduce the background on
machine learning, privacy leakages in machine learningmodels, differential privacy and deep learning with differential privacy.

2.1 Machine Learning
In this paper, we consider machine learning (ML) models used for classification tasks, and below, we review the
major learning paradigms used to train these models.
Supervised Learning Let fθ : Rd 7→ Rk be a ML classifier (e.g., neural network) with d input features and kclasses, which is parameterized by θ. For a given example z = (x, y), fθ (x) is the classifier’s confidence vector
for k classes and the predicted label is the corresponding class which has the largest confidence score, i.e.,ŷ = argmaxi fθ (x).
The goal of supervised machine learning is to learn
the relationship between features and labels in given
l and generalize this ability tolabeled training data Dtr
unseen data. The model learns this relationship using
empirical risk minimization (ERM) on the training set
l , where the risk is measured in terms of certain loss
Dtr
function, e.g., cross-entropy loss:X1
l(fθ , z)
min lθ |Dtr |
l
z∈Dtr

334

l | is the size of the labeled training set andHere |Dtrl(fθ , z) is the loss function. When clear from the context,
we use f instead of fθ , to denote the target model.

Semi-supervised Learning When the labeling process is expensive, semi-supervised learning can alleviate the dependence of ML on labeled data, whichchanges the problem setup by introducing a new unul . Generally, the unlabeled data islabeled dataset, Dtr
drawn from a similar distribution as the labeled data.
There is a long line of research on semi-supervised
learning, but in this work, we consider the state-of-theart semi-supervised learning algorithm, FixMatch [48],which is based on the concepts of pseudo-labeling [32]and consistency regularization [3]. FixMatch is shownto achieve state-of-the-art classification performances on
image classification tasks with less than 1% (of totaldata) labeled data.
Unsupervised Learning Unsupervised learning aims
to learn the inherent task-agnostic patterns in unlabeled
ul . It has been shown that thesetraining data, i.e., Dtr
patterns are very useful for various downstream tasks
such as classification, object detection [9, 10]. Unsupervised learning usually relies on representative featuresin the training data to perform well. More specifically,
unsupervised learning first learns an encoder E using
ul that outputs representation E(x) of input x. Then
Dtr
E can be fine-tuned in a task-specific fashion, e.g., finetuning E by pseudo labeling and confidence.
In this paper, we use the state-of-the-art unsupervised learning algorithm SCAN [52] which is basedon contrastive learning SimCLR proposed by Chen etal. [9, 10]. The intuition behind contrastive learning (SimCLR [9, 10], MoCo [25]) is that the model outputs
should be similar for two different augmented versions of
the same input. Unsupervised learning algorithms, e.g.,
SCAN [52], use these representative features to achieve
comparable accuracy as fully supervised learning.
Learning with Noisy Labels Learning with noisy labels is a long-standing problem in machine learning because the labels in training data usually contain noisylabels. Our work in the learning from noisy labels domain utilizes the refining strategies for the training data;
below we elaborate them. Han et al. [24] propose coteaching that allows one model to learn from the othermodel’s most confident outputs. Based on co-teaching,
Li et al. [34] propose DivideMix, which uses Gaussian
Mixture Model (GMM) to obtain more confident samples and leverages augmented samples to refine the noisylabels. Nishi et al. [39] apply more advanced augmentation strategies called Aug-Descent on DivideMix. The

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

latter two methods are specifically designed for image
datasets while co-teaching is a general learning fromnoisy label technique applicable to all data domain.

335

Definition 2 (Rényi Differential Privacy (RDP) [38]).
A randomized mechanism M with domain D is (α, ε)RDP with order α ∈ (1, ∞) iff for any two neighboringdatasets D, D0 ∈ D:
Dα (M(D)||M(D0 ))2.2 Privacy Leakages in ML Models:=
ML models generally require large amounts of training
data to achieve good performances. This data can be ofsensitive nature, e.g., medical records and personal photographs, and without proper precautions, ML models
may leak sensitive information about their private training data. Multiple previous works have demonstrated
this via various inference attacks, e.g., membership inference, property or attribute inference, model stealing,
and model inversion. Below, we review these attacks.
Consider a target model fθ trained on Dtr and atarget sample (x, y). Membership inference attacks [2,45, 46] aim to infer whether the target sample (x, y) wasused to train the target model, i.e., whether (x, y) ∈ Dtr .
Property or attribute inference attacks [37, 50] aim toinfer certain attributes of (x, y) based on model’s inference time representation of (x, y). For instance, even iffθ is just a gender classifier, fθ (x) may reveal the raceof the person in x. Model stealing attacks [41, 51] aim
to reconstruct the parameters θ of the original model fθbased on black-box access to fθ , i.e., using fθ (x). Model
inversion attacks [21] aim to reconstruct the whole training data Dtr based on white-box, i.e., using θ, or blackbox, i.e., using fθ (x), access to model.

P r[M(D) = δ] α
1
log
E
[(
) ]≤ε
α−1
δ∼M(D 0 ) P r[M(D 0 ) = δ](2)

Lemma 1 (Adaptive Composition of RDP [38]). Consider two randomized mechanisms M1 and M2 that provide (α, ε1 )-RDP and (α, ε2 )-RDP, respectively. Composing M1 and M2 results in a mechanism with (α, ε1 +ε2 )-RDP.
Lemma 2 (RDP to DP conversion [38]). If M obeys(α, ε)-RDP, then M is (ε + log( 1δ )/(α − 1), δ)-DP for
all δ ∈ (0, 1).
Lemma 3 (Post-processing of RDP [38]). Given arandomized mechanism that is (α, ε)-RDP, applying arandomized mapping function on it does not increase its
privacy budget, i.e., it will result in another (α, ε)-RDP
mechanism.

2.4 Deep Learning with Differential
Privacy

Differential privacy [15, 17] is the gold standard for data
privacy. It is formally defined as below:

Several works have used differential privacy in traditional machine learning to protect the privacy of
the training data [5, 8, 20, 33, 60]. Many of theseworks [5, 8, 20] use properties such as convexity orsmoothness for privacy analysis, which is not necessarily
true in deep learning, therefore one cannot use many ofsuch methods in practice. Here we briefly introduce DPSGD [1] and PATE [42, 43] (See more in Section 7.1).

Definition 1 (Differential Privacy). A randomized
mechanism M with domain D and range R preserves(ε, δ)-differential privacy iff for any two neighboringdatasets D, D0 ∈ D and for any subset S ⊆ R we have:

DP-SGD Abadi et al. [1] design a deep learning training algorithm, DP-SGD, where they use gradient clipping to limit the sensitivity, and then add noise to gradients proportional to its sensitivity.

2.3 Differential Privacy

Pr[M(D) ∈ S] ≤ eε Pr[M(D0 ) ∈ S] + δ(1)where ε is the privacy budget and δ is the failure
probability.
Rényi Differential Privacy (RDP) is a commonly-usedrelaxed definition for differential privacy.

PATE Private Aggregation of Teacher Ensembles [42,43] (PATE) is a framework based on private knowledge
aggregation of an ensemble model and knowledge transfer. PATE trains an ensemble of “teachers” on disjoint
subsets of the private dataset. The ensemble’s knowledge is then transferred to a “student” model via differentially private aggregation of the teachers’ votes on
samples from an unlabeled public dataset. Only the student model is released as the output of the training, as
it accesses sensitive data via a privacy-preserving inter-

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

face. We use RDP to compute the bounds for PATE
based framework and convert RDP to DP.

As many services are using users’ private data to train
machine learning models, the use of privacy preserving machine learning with strong privacy guarantees
is increasing. As we explained in Section 2.1, data
D = (X, Y ) in machine learning have two main types
of attributes: features X and labels Y . The researchcommunity has considered designing privacy frameworks [27, 30] which generalize differential privacy by
restricting the secrets about individuals as well as enumerating the side information to the attacker. In certain
practical settings, only the labels Y in training data
are of sensitive nature, i.e., are private. Imagine a survey from a participant in a university class about theirvaccination status. Some attributes of the students are
publicly available but vaccination status is a sensitive
information and must remain private. Now if we want
to train a model that predicts whether a student has received vaccination only using their public information,
we can use label-DP. To address this problem, we should
only apply differential privacy to the labels. Such privacy protection is commonly called as label differential
privacy (label-DP).
We start by formally defining label-DP and similarly
label-Rényi DP.
Definition 3. A randomized mechanism M with domain D = X × Y and range R preserves (ε, δ)label-DP iff for any two label neighboring datasets(X, Y ), (X, Y 0 ) ∈ X × Y and for any subset S ⊆ R we
have:
(3)

where ε is the privacy budget and δ is the failure probability. In particular, when δ = 0 M is ε-label-DP.
Definition 4 (label-Rényi DP ). A randomized mechanism M with domain D = X × Y is (α, ε)-label-RDP
with order α ∈ (1, ∞) iff for any two label neighboringdatasets (X, Y ), (X, Y 0 ) ∈ X × Y:
Dα (M(X, Y )||M(X, Y 0 )):=We can also use existing differential privacy mechanisms
to achieve label-DP as proposed below.
Proposition 1. A mechanism M preserves (ε, δ)-labelDP if it also preserves (ε, δ)-DP.

3 Problem Statement: Label
Differential Privacy

Pr[M(X, Y ) ∈ S] ≤ eε Pr[M(X, Y 0 ) ∈ S] + δ

336

(4)
1
P r[M(X, Y ) = δ] α
log
E
[(
) ]≤ε
0
0
α−1
δ∼M(X,Y ) P r[M(X, Y ) = δ]Proof. The notion of neighboring dataset in label-DPrequires that datasets differ in one label. This implies
that the pair datasets also satisfy the notion of neighboring where two datasets differ in one example. Therefore,
if a mechanisms satisfies (, δ)-DP, then it also satisfies(ε, δ)-label-DP.
Proposition 2. If mechanism M0 with domain Y andrange Y satisfies (ε, δ)-DP (with replacement), then amechanism M with domain X ×Y that given (X, Y ) outputs f (X, M 0 (Y )), for an arbitrary function f , satisfies(ε, δ)-label-DP.
Proof. We first show that a mechanism M 00 that outputs (X, M 0 (Y )) is (, δ)-label-DP. For any neighboringdatasets X, Y and (X, Y 0 ) we havePr[M 00 (X, Y ) ∈ A] = Pr[(X, M 0 (Y )) ∈ A].
00

00

Let B = {Y ; (X, Y ) ∈ A}. We have
Pr[(X, M 0 (Y )) ∈ A] = Pr[M 0 (Y ) ∈ B]
Therefore we havePr[M 00 (X, Y ) ∈ A] = Pr[M 0 (Y ) ∈ B]
≤ eε Pr[M 0 (Y 0 ) ∈ B] + δ= eε Pr[M 00 (X, Y 0 ) ∈ A] + δ.
Now since M 00 is (, δ)-label-DP, M is also (, δ)-labelDP by a post-processing argument.
Remark 1. Note that the mechanism M0 could be any
differentially private mechanism. This includes mechanisms that use sub-sampling and shuffling for amplification of privacy. However, these kind of mechanismsthat change the order of labels are not useful for labelDP. This is because we need the association of the labels
and features to be preserved and changing the order oflabels will remove this association.
The next step is to design a ML mechanism which preserves label-DP. A basic idea is to use Proposition 1
and use similar mechanisms as used to train ML models
with differential privacy [1]. However, label-DP is much
more relaxed form of privacy and we can leverage theconstraints in label-DP to design new methods and improve the utility of existing (traditional) DP approaches.
In this work, we use Proposition 2 to provide label-DP.

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

337

Algorithm 2 NoiseCluster

LabelsTraining Set Unsupervised
learning
FeatureClusterModel
MclusterGenerating clusters
on training set

Model M

1
2

Pipeline 1…
N

FeatureTraining Set
LabelsUnsupervised
learning

ClusterModel
MclusterGenerating clusters
on training set

1
2

Pseudo label generation(See Algorithm 7 DenoiseSSL)…

Model M

Pseudo Labels

N
Private Labels on whole training set

Differentially private label generation (Algorithm 3 RandRes or Algorithm 5 PATE-FM)

Learning with Private Labels(Algorithm 6 LDP-AlgName
or Algorithm 7 DenoiseSSL)

Pipeline 3

FeatureSemi-supervised
Learning

Differentially private label
Training Set generation Algorithm 5 PATE-FM
Labels

Pipeline 2

Model M

Private Labels (for only part of training set)

Fig. 1. Our end-to-end framework consists of three pipelines. Pipeline 1 leverages unsupervised learning to learn clusters and only adds
noise when assigning cluster label with no further learning needed. Pipeline 2 will first generate the DP labels, then apply learningalgorithms on the DP labels. Pipeline 3 (PATE-FM [35]) is a variation of PATE under label-DP. Yellow boxes show the features andnon-private labels. The green arrows show the computation related to unsupervised learning. The orange arrow shows the DP label
generation process. Blue arrows show the pseudo label generation process. Gray arrows show the computation which finally outputs themodels. Table 1 summarizes all algorithms in our framework.

In particular, we divide approaches to ML withlabel-DP into two components: (1) obtain the labels withdifferential privacy and then (2) learn from the noisy(differentially private) labels. In the following sections,
we overview and compare with existing works on labelDP, provide our algorithms for each of the aforementioned label-DP components, and finally, discuss the advantages and disadvantages of each of the algorithms.
Overview and comparison with related works
We propose a two-component modular frameworkto achieve the label-DP described above. The first component involves obtaining noisy (differentially private)labels and the second component involves learning on
the differentially private labels. For the first component of obtaining differentially private labels, in addition
to existing works including Randomized Response [56]based approach by Ghazi et al. [23] and PATE [42, 43]
based approach by Malek et al. [35], we also design
one more approach. This is an unsupervised learning
based approach for generating differentially private labels (NoiseCluster), which adds noise to the counts oflabels when assigning cluster labels, thus adding lessnoise compared to existing works (NoiseCluster does notneed further learning with the private labels). For thesecond component of learning with differentially private
labels, we focus on how to denoise the differentially private labels to improve the utility of the resulting mod-els.1 Unlike previous work ALIBI [35], which focuses
on denoising the differentially private labels using only
the label information, we also consider how to leverage
the public feature information to denoise the private labels and therefore utility is much improved. Techniquesin our framework include unsupervised learning, semisupervised learning, and learning with noise labels. We
systematically evaluate our framework and show themuch improved utility compared to existing works.

4 Our Framework
In this section, we present our framework in detail.
Specifically, there are three building blocks: NoiseCluster (i.e., adding noise to the cluster label, see Section 4.1), differentially private labels generation (i.e.,adding noise to individual labels, see Section 4.2), andlearning with differentially private labels (i.e., how todenoise private labels to improve utility, see Section 4.3).
Our framework consists of three pipelines. Pipeline 1

1 We later noticed that Ghazi et al. [23] also investigated using self-supervised learning to improve utility of their LPMST
algorithm. Our framework focuses on using unsupervised learning and semi-supervised learning to add less noise as well as
denoising the differentially private labels.

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

338

Table 1. Summary of algorithms in our framework.
Algorithm name

Function

Intuitive explanation

Alg. 1 LabelCount

Count the samples per class for eachcluster in unsupervised learning model.

Only do counting, no noise added.

Alg. 2 NoiseCluster
Alg. 3 RandRes

Alg. 4 Confident-GNMax

Alg. 5 PATE-FM
Alg. 6 LDP-AlgName

Alg. 7 DenoiseSSL

Generate differentially private label set byunsupervised learning.
Generate differentially private label set
directly from the label set.
Generate the differentially private label fora queried sample given n teacher models
trained by PATE [42, 43].
Generate differentially private label set by
PATE [42, 43] and train a student model.

Add Gaussian noise to the class count for each cluster anddo majority voting, no noise added to individual samples.

Given the differentially private labels, train
the models using AlgName.
Given the differentially private labels, train
the model with purified label set bysemi-supervised learning.

General framework, we investigate LDP-SSL and LDP-LNL(specifically LDP-FixMatch [48] and LDP-AugDescent [39]).
Filter the noisy label set by using pseudo labels fromunsupervised learning to a smaller subset but with higher
precision, then apply semi-supervised learning.

is based solely on NoiseCluster, Pipeline 2 is based on
the combination of differentially private labels generation and learning with differentially private labels, andPipeline 3 (PATE-FM [35]) is a variation of PATE underlabel-DP. Figure 1 presents our end-to-end framework.
Next we detail our three building blocks. We also summarize the algorithms of our framework in Table 1. For
brevity, we assume there are N classes in total, i.e., thelabel cardinality is N , and denote [N ] = {0, 1, ..., N −1}.
We denote Y as clean label set, Ye as noisy label set andŶ as cluster label set from unsupervised learning model.

4.1 NoiseCluster
An easy approach to protect privacy of the private labels is to not use them at all. To this end, there areseveral unsupervised approaches that can be used tocluster the input space. Now we can apply a simple differentially private voting, called NoiseCluster to assign
labels to the clusters with small privacy cost (See Algorithm 2). While this approach has a very low privacy
cost, unfortunately, the utility of the clustering methods
is significantly lower compared to the supervised methods. In Section 5, we show this trade-off. Specifically, we
use SCAN [52] is this paper.2

2 Please note that this procedure is not limited to any specific unsupervised learning. We used SCAN [52], which was thestate-of-the-art unsupervised learning algorithm (at the time of

Probabilistically replace the true label with a random label.
Add Gaussian noise to the counting of teacher model’s
predictions and return the label when the noisy voting
above a threshold.
Use Confident-GNMax to generate differentially private label
set.

Algorithm 1 LabelCount: count the samples per classfor each cluster in unsupervised learning model
Require: dataset D = (X, Y ) or (X, Ye ), an unsupervised model f0 on X with N clusters.
D0 = {}
for all (x, y) ∈ D doŷ ← argmaxi f0 (x)Add (x, y, ŷ) to D0
end forŶ is a N × N matrix with all values initialized as 0.
for all l ∈ [N ] do
Dl = {(x, y, ŷ) : (x, y, ŷ) ∈ D0 , ŷ = l}for all (x, y, ŷ) ∈ Dl doŶ [l, y] = Ŷ [l, y] + 1
end forend forreturn (D0 , Ŷ )Algorithm 2 NoiseCluster
Require: dataset D = (X, Y ), noise parameters σ.
Train unsupervised model f0 on X with N clusters
Run (D0 , Ŷ ) ← Algorithm 1((X, Y ), f0 )for all l ∈ [N ] do
Assign cluster l with arg maxi {Ŷ [l, :] + N (0, σ)}end forreturn model f with assigned clusters

Not final; page numbers may change before publication
339

Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

Algorithm 3 Randomized Response Mechanism
Require: L the true label, N the label cardinality, and1 − p the probability of randomized response.
z ∼ Uniform(0,1)
if z < p thenreturn L
end ifreturn Uniform([N]\L)

Theorem 1. Algorithm 2 is (ε, δ)-label-DP where:
√
√
2
2
εσ
εσ
Φ(
(5)
− √ ) − eε Φ(−− √ )) ≤ δ
2σ
2σ
2
2
Proof.
The `2 sensitivity of Ŷ in NoiseCluster isp√(1)2 + (−1)2 = 2 because by changing one of the labels, the number of votes on one class increases by 1 andit decreases by 1 on the other class. Therefore by Theorem 8 in Balle et al. [4] we conclude that Ŷ + N (0, σ)is (ε, δ)-DP. Then using a post-processing argument,
argmax Ŷ is (ε, δ)-DP as well.

4.2 Differentially Private Labels
If we can get labels with differential privacy, then using
Proposition 2 we can use normal machine learning methods on the differentially private labels and achieve labelDP. In this section we introduce two main approaches
for obtaining differentially private labels.

Theorem 2 (Randomized Response Mechanism). Algorithm 3 with label cardinality N and probability of true
answer p > 1/N satisfies (ε, 0)-label-DP where:
ε = ln((N − 1)p).
1−pProof. For any label y, we know that Pr[M (y) = y] = p.
Therefore if p > 1/N , we have: ∀y 0 , y 00 6= y,Pr[M (y) = y 0 ]Pr[M (y) = y]p(N − 1)≤=
Pr[M (y 00 ) = y 0 ]Pr[M (y 00 ) = y]
(1 − p)As mentioned earlier most of the DP mechanisms work
best when applied on an aggregation of several data
points. To take advantage of this, we can use the ideaof ensemble learning [14]. The approach is similar to
PATE [42, 43] approach where we utilize the noisy
aggregation with differential privacy. However, unlike
PATE [42, 43], we only need to provide differential privacy for the labels. Based on this observation, Malek et
al. [35] propose PATE-FM. Figure 2 illustrates PATEFM. Below, we describe each component of this method.

Feature X

Label Y1

Teacher 1

Label Y2Teacher 2

Label Yn

Teacher n

4.2.1 RandRes
Direct data
feeding

conducting this research) that achieved comparable accuracy as
standard training algorithms on benchmark image datasets.

(7)

4.2.2 PATE-FM

Sensitive
Label YOne of the main approaches to achieve differential privacy is to add noise to the data. Differential privacy
usually works well on mechanisms that aggregate several data points, however, supervised learning needs thelabel of each instance. Therefore, we cannot easily use
aggregation mechanisms. Instead, we can use Randomized Response mechanisms [56] (RandRes) to preserve
the differential privacy and provide plausible deniability.
In a nutshell, RandRes for label-DP proposed by
Ghazi et al. [23] returns the true label with probability
p and a uniformly random label other than true labelwith probability 1 − p (See Algorithm 3).

(6)

Partition data
feeding

ConfidentGNMax
Aggregate

Prediction
Completion Y’
semi-supervised
learning

Student+ Feature X
Part of Feature X'

prediction

Fig. 2. PATE-FM: adaption of PATE for label-DP.

Data partitioning and training teachers: Consider
a dataset D = (X, Y ) with features X and labels Y . We
partition D into n subsets (X, Yn ) such that the features
are part of each sub-dataset but we only have labels
for a limited set of the inputs and Yn are disjoint (i.e.
∀i6=j Yi ∩ Yj = ∅). We then train a teacher model on eachsubset (X, Yn ). Instead of discarding the inputs without
the labels and train the teachers in supervised fashion,
we can use the unlabeled data to improve the accuracyof each teacher using semi-supervised learning (SSL),
e.g. FixMatch [48]. Please note that this procedure is
not limited to any specific SSL.

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

Algorithm 4 Confident-GNMax Aggregator
Require: input x, threshold T , noise parameters(σ1 , σ2 ), n teacher models f1 , · · · , fn .
if max{fi (x)} + N (0, σ1 ) ≥ T thenreturn arg max{fi (x) + N (0, σ2 )}end ifreturn ⊥340

4.3 Learning with Private Labels
Using the approach in Section 4.2, we can obtain labelswith differential privacy and we can then use the private labels for the main learning task. However, normal
ML methods are designed to train on true labels while
the private labels are generally noisy. Below, we discussdifferent methods for learning with private labels.

Algorithm 5 Generating Private Labels by PATE-FM
Require: dataset D = (X, Y ), number of teachers n,number of labels for student model L, threshold T ,noise parameters (σ1 , σ2 ).
Train Teacher Models:
Divide the label set Y into n disjoint datasets
Y1 , · · · , Yn
Train n teacher models (model fi will be trained on
Yi and X via semi-supervised learning)
Train Student Model:
Xs ←Select L random samples from X
Ys ←Get the noisy labels using Algorithm 4 for Xs
Train student model on (Xs , Ys ) and X

Aggregating the teachers: After training each submodel, we need to aggregate the outputs of each submodel and publish the output while preserving privacy.
In particular, we will use Confident-GNMax Aggregator [43] (see Algorithm 4). The algorithm only releases
private labels for the data points for which the teacher
votes exceed a noisy threshold. Also, we only consider
the privacy cost for the points that the algorithm decides to release. Moreover, Papernot et al. [43] showedthat by using smooth sensitivity [40] instead of the
global sensitivity it is possible to improve the privacy
analysis (Please see Appendix 1 in Papernot et al. [43]for the privacy analysis of PATE). The privacy cost
analysis is the same as Papernot et al. [43].
Training the student: While we can use the aggregated teachers to answer queries, each query will increase the privacy cost. Therefore, instead we train astudent model. In particular, we can use the idea of the
SSL algorithms to get private labels for a small subsetof the training dataset. Please note unlike the existing
works [42, 43], since we only require label-DP, we do notneed a public dataset. Algorithm 5 summarizes the overall steps of PATE-FM (Pipeline 3). Pipeline 2 queries
the student model of PATE-FM to generate the differentially private labels on the whole training set.

4.3.1 Normal
Given the noisy (differentially private) labels, the next
step is to train the model. Algorithm 6 illustrates thegeneral framework to train a model with the differentially private labels.
Algorithm 6 General framework for learning with differentially private labels: LDP-AlgName
Require: dataset with differentially private labels
D0 = (X, Ye ) by Algorithm 3 or 5 on D.
train a model f on D0 by AlgName.
return return f

Proposition 3. By Proposition 2, Algorithm 6 does
not have additional label privacy cost besides Algorithm 3 or 5.
One simple method is to directly train the machinelearning model with such noisy labels as training withthe (sensitive) true labels by naive machine learning,i.e., supervised learning (directly calculated the gradients with respect to the noisy labels and update weights
accordingly). We denote this as Algorithm 6: LDPNormal. Ghazi et al. [23] propose a Label Privacy MultiStage Training (LP-MST) algorithm to preserve label
privacy for deep learning, and LP1ST is equivalent tonormal training (Algorithm 6: LDP-Normal) with private label set by RandRes (Ghazi et al. [23] considers
mixup [59] to improve utility).
Next, we present two methods to improve theutility-privacy trade-off in label-DP.

4.3.2 DenoiseSSL: Denoising Assisted
Semi-supervised Learning for Label-DP
Suppose that we obtain another set of labels for the
training set without sacrificing the privacy of the la-Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

bels (denoted as pseudo label set and corresponding accuracy as Acc0 ). We then only use the label informationof the samples for which have the same differentiallyprivate label and pseudo label. We next show that thisgives a subset with significantly more accurate labels.
Let us walk through the above denoising idea for
RandRes where p = eε /(eε + N − 1). Our strategy will
select Acc0 ×p samples of which the differentially private
labels are correct and (1 − Acc0 ) × (1 − p)/(N − 1) whichhave wrong labels as their differentially private labels.3
Therefore, the accuracy of the selected subset is

Acc0 ==

Acc0 × p1−p
Acc0 × p + (1 − Acc0 ) × N
−1

p
1−p
0
p + 1−Acc
Acc0 × N −1

=

eε

(8)

0
eε + 1−Acc
Acc0

In the extreme case where the new label set cannot
provide any label information and Acc0 = 1/N , we cansee that (1 − Acc0 )/Acc0 = N − 1 and we have Acc0 = p.
If we increase Acc0 from 1/N , we have (1−Acc0 )/Acc0 <N − 1 and therefore Acc0 > p.
Algorithm 7 DenoiseSSL
Require: dataset with differentially private labels
D0 = (X, Ye ) by Algorithm 3 or 5 on D.
Zpseudo = {}, Ddenoise = {}Train unsupervised model f0 on X with N clusters.
Run (D00 , Ŷ ) ← Algorithm 1((X, Ye ), f0 )for all l ∈ [N ] doassign cluster of l with label arg max{Ŷ [l, :]}, i.e.,add (l, arg max Ŷ [l, :]) to Zpseudo
end forfor all (x, ye, ŷ) ∈ D00 do
get ypseudo from ŷ according to the pseudo label
look-up set Zpseudo
if ypseudo == ye thenadd (x, ye) to Ddenoiseelse
add (x, ⊥) to Ddenoise
end ifend fortrain a model f on Ddenoise by SSL
return return f

3 The denoising algorithm should also work for private label set
generated by PATE-FM, but the private label by PATE-FM isdependent on PATE and cannot be directly estimated.

341

We next introduce how to generate the pseudo label
set without sacrificing the label privacy. As our discussion in Section 4.1, unsupervised learning is immune tolabel noise and we apply majority voting on differentially private labels to get cluster labels as pseudo labels (See Algorithm 7). Following Proposition 2, we do
not incur additional privacy cost.
Next, we only use label information of training samples which have same pseudo label and differentially private label. As we now get a subset of the original training set with more accurate but fewer labels, we apply
semi-supervised learning on the whole data set but onlywith the selected labels (See Algorithm 7).
Proposition 4. By Proposition 2, Algorithm 7 does
not have additional label privacy cost than Algorithm 6.
Although the model is trained with fewer correct labels (as we will fill out p × (1 − Acc0 ) samples whichhave correct labels), we will show that the model will
get higher accuracy than directly applying SSL on theraw differentially private label set; note that the latter
set has more labels but with lower accuracy, when wewant strong label differential privacy, i.e., low ε. However, when ε is high, e.g., ε = 8 for N = 10, we will
get differentially private label set with p ≥ 99.7%. The
performance of denoising will be limited by the performance of unsupervised learning as it will filter out
p × (1 − Acc0 ) ≈ (1 − Acc0 ) correctly labeled samples.
Therefore, we also consider applying semi-supervised
learning with all training samples and noisy labels. We
denote this as Algorithm 6: LDP-SSL and its privacy
analysis is provided by Proposition 3.4

4.3.3 Aug-Descent: Dynamic Denoising in Training
One limitation of DenoiseSSL is that this method divides the clean label set and noisy label set before starting semi-supervised learning and keeps the labeled set
fixed. The model can obtain more label information
within the training procedure. To leverage more valid label information, we need to consider dynamically dividing the dataset during the training process and we adapt
techniques from fields in learning from noisy labels. If

4 Please note that DenoiseSSL and LDP-SSL are not limited toany specific SSL. We used FixMatch [48], which was the state-ofthe-art SSL algorithm (at the time of conducting this research)that achieved high accuracy on benchmark image datasets withvery few labeled examples.

Not final; page numbers may change before publication
342

Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

we view the differentially private labels as noisy labels
generated in the label collection process, we can adapt
existing learning with noisy labels technique to improvethe utility-privacy trade-off in learning with label-DPguarantee. Specifically, we consider Aug-Descent [39],which applies Gaussian Mixture Model in each iteration
to identify high confident samples as labeled samples
and others as unlabeled samples, does label-refinement
on labeled samples and labeled-sharpening on unlabeled
samples, then learns on the refined and sharpened labels (See Algorithm 4 in Aug-Descent [39] for more details). We denote this as Algorithm 6: LDP-Aug-Descentand its privacy analysis is provided by Proposition 3.

5.2 Evaluation of Differentially Private
LabelsTable 2 presents the private label accuracy of the training set by RandRes and PATE-FM on the whole training set.5 We can compute the theoretical private labeleεaccuracy for RandRes6 by acc(ε) = eε +N−1 , while for
PATE-FM, the private label accuracy is determined by
the performance of PATE-FM and composition theorem of differential privacy. In addition, PATE-FM uses
Gaussian noise and has an additional private parameterδ compared to RandRes. In this work, we set δ = 10−5 .
Table 2. The accuracy of the differentially private label set (i.e.
for training set) by RandRes and PATE-FM.

5 Experiments
DP label. Method

In this section, we first briefly introduce the datasetsand model architectures used to train the classification models in Section 5.1. Next we present the performance of RandRes and PATE-FM in Section 5.2.
Then we present the overall performance of our framework with each specific algorithms in Section 5.3. Finally we compare our framework with previous works(LP1ST (+mixup) [23] and ALIBI [35]) in Section 5.4.

label-DP level
CIFAR10

RandRes (δ = 0)
PATE-FM (δ = 10−5 )ε = 0.5

ε=1

ε=2

ε=4

15.5%
93.2%

23.2%
93.7%

45.2%
94.9%

85.9%
94.9%

ε=1

ε=2

ε=4

ε=6

2.7%
42.5%

6.9%
48.1%

35.8%
61.9%

80.4%
69.3%

ε = 0.5

ε=1

ε=2

ε=4

15.4%
30.2%

23.2%
77.3%

45.0%
79.9%

85.9%
85.1%

CIFAR100

RandRes (δ = 0)
PATE-FM (δ = 10−5 )CINIC10

5.1 Experimental Setup
Dataset. We use three benchmark datasets for image
classification and target models which are widely usedin the study of prior non-private learning algorithms.
CIFAR10-100 CIFAR10 and CIFAR100 [31] bothcontain 60,000 32 × 32 color (RGB) images (50,000 images as training set and 10,000 images as test set). CIFAR10 contains 10 classes and CIFAR100 contains 100
classes.
CINIC10 CINIC10 [11] contains 60,000 CIFAR10 images and 210,000 color (RGB) images rescaled to 32×32
from ImageNet [12]. This dataset uses 90,000 images
for training/validation/test set. CINIC10 contains 10classes, which is consistent with CIFAR10, but is more
complicated than CIFAR10 as it has much more images.
Models. We use ResNet-18 [26] for all threedatasets and all algorithms. We also vary model architectures on the comparison between our framework
and previous works in Appendix A to show the effectiveness of our framework. We instantiate our unsupervised learning algorithms by SCAN [52], semisupervised learning algorithms by FixMatch [48].

RandRes (δ = 0)
PATE-FM (δ = 10−5 )For CIFAR10, PATE-FM is significantly better than
RandRes: even at ε = 0.5, PATE-FM provides 93.2% accuracy of differentially private labels (A single modelin PATE-FM can have accuracy higher than 90%).
For CIFAR100, PATE-FM is better than RandRes for
ε = 1, 2, 4, (RandRes adds large noise for ε = 1 andthe label accuracy is just 2.7%), but worse for ε = 6.
This is because CIFAR100 is a more difficult dataset
compared to CIFAR10 as it has 100 classes and fewer
samples (500 per class) and any single teacher model in
PATE-FM can not achieve accuracy higher than 75%.

5 NoiseCluster does not need any further learning process aftergenerating the differentially private cluster and we will evaluate
its performance in the next subsection.
6 Both of CIFAR10 and CINIC10 have 10 classes, so they havesame theoretical accuracy acc(ε) for same ε, though the reported
accuracy in Table 2 differs a little due to randomness.

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

Therefore, even when no noise in Algorithm 5, the label
generated from PATE-FM may be worse than RandRes(80.4%). RandRes is not affected with this fewer samples fact. With a fixed N , the value of p increases as εincreases and RandRes outputs a label set with higher
accuracy (80.4% at ε = 6 by Equation (6)) accuracy. For
CINIC10, PATE-FM is much better than RandRes for
ε = 0.5, 1, 2 while a little worse for ε = 4.

5.3 Evaluation of Our Whole Framework
Tables 3, 4 and 5, summarize the main results of thepaper. We also include the non-private baseline in these
Tables by running our framework on the clean label set
and reporting the respective highest accuracy on eachdataset as the non-private baseline. For each ε column,
the bold number is the highest accuracy.
Overall Performance. We can see that most of
the highest accuracy model are from Aug-Descent except for ε = 0.5 on CINIC10 (by RandRes+DenoiseSSL)
and ε = 2 on CIFAR100 (by PATE-FM+SSL). Moreover, for highest accuracy model from Aug-Descent, we
can find that when ε is low, the highest accuracy are byprivate label set generated by PATE-FM, and when εbecomes higher, the highest accuracy are by private label set generated by RandRes. Our analysis is that, forrelative low ε where the private label set does not include much noise, e.g., CIFAR10 at ε = 1 by RandRes or
PATE-FM, Aug-Descent can perform better than otheralgorithms. In addition, PATE-FM may be limited to
the feature information as ε increases, while the valueof p for label set by RandRes increases as ε increases
with fixed N , e.g., CIFAR100 at ε = 6. Next we analyze
the components of our framework in detail.
NoiseCluster performs well at low ε. Even
without any specific individual label information, unsupervised learning can perform well to cluster samples ofthe same class to a single cluster. Besides, to get the label information of each cluster, NoiseCluster only needs
to add noise to the counting of samples per class for eachcluster instead of adding noise to each individual sample, therefore, it adds less noise to the label set in totalcompared to RandRes and PATE-FM. Please note thatthe same as PATE-FM, NoiseCluster also has a δ parameter. In this work, we set δ = 10−5 . Though we only
provide ε = 0.5 for CIFAR10/CINIC10 and ε = 1 for CIFAR100 in Tables, the lowest ε that NoiseCluster can
provide without sacrificing utility is 0.003 for CIFAR10,
0.4 for CIFAR100 and 0.02 for CINIC10. In contrast,
other pipelines which rely on RandRes and PATE-FM

343

have worse performance compared to NoiseCluster as
too much noise added when ε is much lower.
DenoiseSSL
solvesthelimitationof
NoiseCluster as ε increases. One limitation of
NoiseCluster for label-DP is that it will not utilize theprivate label set during the clustering process so thatthe utility is limited to the clustering performance, evenwhen the private label set has little noise. For example,
on CIFAR100, the label set accuracy by RandRes is
80.4% at ε = 6 and 2.7% at ε = 1, while NoiseCluster islimited to 34.5% accuracy. DenoiseSSL overcomes thislimitation by leveraging both the feature informationand the private label information. For all three datasets,
the classification accuracy of DenoiseSSL increases as
the private label set has less noise. Besides, DenoiseSSL
is better than LDP-SSL when ε is low, while worse
when ε is higher, e.g., ε = 6 by RandRes on CIFAR100,
as we have discussed in Section 4.3.
For most cases, DenoiseSSL performs better than
NoiseCluster as DenoiseSSL benefits both from unsupervised learning and semi-supervised learning while
NoiseCluster solely relies on unsupervised learning.
However, when the accuracy of the noisy label set isextremely low, DenoiseSSL fails to achieve good accuracy and is even worse than NoiseCluster, this is because
DenoiseSSL derives the purified label set from the noisylabel set generated by adding noise to individual samples, which adds more noise to the label set comparedto NoiseCluster. For example, for ε = 1 by RandRes on
CIFAR100, the private label accuracy (2.7%) is worse
than the clustering accuracy (34.5%).
PATE-FM+SSL benefits from the choice of
flexible number of queries to add less noise. After
training the teacher models, querying each instance tobe used for training the student model will increase theprivacy cost. Therefore, the fewer queries, the less noise.
The performance of PATE-FM+SSL is better than RandRes+DenoiseSSL on CIFAR10. Also, PATE-FM+SSL
is better than RandRes+DenoiseSSL at ε = 1, 2, 4 on
CINIC10. For ε = 0.5, we analyze that ε = 0.5 might
be too low, therefore the limited number of labels andlimited accuracy of the labels makes it hard for PATEFM+SSL to perform better than denoising.
Aug-Descent outperforms other approaches
as a benefit of dynamic division of labeled set
and unlabeled set. DenoiseSSL divides the labeled set
and unlabeled set before SSL, and the wrong label information in labeled set will keep misleading the training
process. The Aug-Descent algorithm [39] dynamicallydivides the labeled set at each round of the training
process to better utilize the label information of sam-

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

344

Table 3. CIFAR10 (non-private baseline: 97.2%). For each ε column, the bold number is the highest accuracy.
Private Label Method

Learning Method with Private Labels

ε = 0.5

ε=1

ε=2

ε=4

NoiseCluster (SCAN)

N.A.

88.3%

88.3%

88.3%

88.3%

RandResDenoiseSSL (SCAN+FixMatch)
LDP-SSL (FixMatch)
LDP-Aug-Descent

90.7%
36.2%
37.7%

90.8%
61.9%
94.1%

91.2%
84.6%
95.2%

93.6%
92.7%
96.5%

PATE-FMSSL (FixMatch)

94.1%

94.5%

95.1%

95.1%

PATE-FM

DenoiseSSL (SCAN+FixMatch)
LDP-SSL (FixMatch)
LDP-Aug-Descent

93.3%
93.4%
94.6%

93.6%
94.2%
95.0%

93.7%
94.5%
95.1%

93.7%
94.5%
95.1%

Table 4. CIFAR100 (non-private baseline: 83.3%). For each ε column, the bold number is the highest accuracy.
Private Label Method

Learning Method with Private Labels

ε=1

ε=2

ε=4

ε=6

NoiseCluster (SCAN)

N.A.

34.5%

34.5%

34.5%

34.5%

RandResDenoiseSSL (SCAN+FixMatch)
LDP-SSL (FixMatch)
LDP-Aug-Descent

8.3%
1.8%
2.6%

25.5%
3.5%
10.8%

43.3%
51.4%
75.3%

50.2%
70.5%
79.5%

PATE-FMSSL(FixMatch)

31.9%

55.1%

59.0%

68.1%

PATE-FM

DenoiseSSL (SCAN+FixMatch)
LDP-SSL (FixMatch)
LDP-Aug-Descent

30.7%
41.2%
46.0%

34.7%
47.4%
55.0%

40.3%
54.0%
60.1%

42.8%
58.1%
65.3%

Table 5. CINIC10 (non-private baseline: 90.0%). For each ε column, the bold number is the highest accuracy.
Private Label Method

Learning Method with Private Labels

ε = 0.5

ε=1

ε=2

ε=4

NoiseCluster (SCAN)

N.A.

62.8%

62.8%

62.8%

62.8%

RandResDenoiseSSL (SCAN+FixMatch)
LDP-SSL (FixMatch)
LDP-Aug-Descent

65.6%
20.8%
42.6%

66.3%
53.9%
80.7%

68.2%
73.6%
85.7%

72.1%
83.8%
88.7%

PATE-FMSSL (FixMatch)

25.5%

76.0%

81.1%

85.4%

PATE-FM

DenoiseSSL (SCAN+FixMatch)
LDP-SSL (FixMatch)
LDP-Aug-Descent

14.8%
18.2%
18.9%

70.5%
81.7%
87.6%

71.1%
82.0%
87.9%

71.8%
83.5%
88.1%

Table 6. Comparison with the existing works.
CIFAR10

MethodOur work
ALIBI [35]
LP1ST [23]Non-private
baseline

CIFAR100

CINIC10ε = 0.5

ε=1

ε=2

ε=3

ε=4

ε=1

ε=2

ε=4

ε = 0.5

ε=1

ε=2

ε=3

ε=4

94.6%
33.8%
38.4%

95.0%
70.0%
61.4%

95.2%
81.9%
83.2%

96.2%
87.2%
89.5%

96.5%
89.6%
92.0%

46.0%
4.7%
2.6%

55.1%
20.4%
7.6%

75.3%
60.8%
52.6%

65.6%
30.6%
19.7%

87.6%
58.2%
52.0%

87.9%
69.8%
71.8%

88.1%
76.1%
80.1%

88.7%
79.5%
84.6%

97.2%

83.3%

90.0%

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

ples which is correct with high confidence. In most cases,
the highest accuracy of our framework (i.e., in bold), arefrom Aug-Descent Algorithms either on label set from
RandRes or PATE-FM. When ε is low (e.g., CIFAR10
at ε = 0.5), the highest accuracy is usually from PATEFM+Aug-Descent while as ε increase (e.g.,CIFAR100 at
ε = 6), Aug-Descent+RandRes is better because RandRes provides the label set with higher accuracy.
One special case is CIFAR100 at ε = 4. Our explanation for why PATE-FM generates the private label
set at ε = 4 with higher accuracy than RandRes while
Aug-Descent on PATE-FM performs worse includes two
folds. Firstly, the private label set by PATE-FM can bebiased, which worsen utility. Secondly, PATE-FM generates the private label set mainly from the feature spaceand model, while RandRes is from the ground truthlabel alone, therefore, though the private label set by
PATE-FM is more accurate than that by RandRes, itdoes not provide enough label information.
We have already discussed the performance andanalysis of our framework in detail. Next we compare
the performance of our framework with existing works.

5.4 Comparison with Existing Works
Table 6 compares our work and other label-DP mechanisms [23, 35] on CIFAR10 at ε = 0.5, 1, 2, 3, 4, CIFAR100 at ε = 1, 2, 4 and CINIC10 at ε = 0.5, 1, 2, 3, 4.
For our framework at each ε , we will report the highest
accuracy in our framework.
Comparison
with
LP1ST
(+mixup).
LP1ST (+mixup) imposes a significant accuracy dropcompared to training with non-private label (for evaluated ε, at most 58.8% on CIFAR10, at most 80.7% on
CIFAR100 and at most 70.3% on CINIC10), while ourmethod achieves comparable utility as non-private label
training process on CIFAR10 and CINIC10 and significant utility advantage compared to LP1ST (+mixup) on
CIFAR100: among three evaluated datasets, our method
improves classification accuracy by 45.9% ∼ 56.2% at
ε = 0.5, 33.6% ∼ 43.4% at ε = 1, 12.0% ∼ 47.5% at
ε = 2, by 6.7% ∼ 8.0% at ε = 3, and by 4.1% ∼ 22.7%
at ε = 4. As ε increases, the utility advantage of ourframework over previous algorithms decreases but isstill significant.
Comparison with ALIBI. Our method achieves
a better utility than ALIBI on all three datasets.
ALIBI achieves a slightly worse performance than
LP1ST (+mixup) on CIFAR10 and CINIC10 whichhave 10 classes for most cases, while performs much

345

better on CIFAR100 which has 100 classes as ALIBI
benefits adding much less noise for high label cardinality. However, ALIBI still incurs additional classification
accuracy drop compared with our work: 35.0% ∼ 60.8%
for ε = 0.5, 25.0% ∼ 41.3% for ε = 1, 13.3% ∼ 34.7%
for ε = 2, 9.0% ∼ 12.0% for ε = 3 and 6.9% ∼ 14.5%
for ε = 4. Similarly as LP1ST, as ε increases, the utility
advantage of our framework over previous algorithms
decreases but is still significant.

6 Discussion
In this section we first discuss the impact of label cardinality on utility advantage of our framework. We thendiscuss two limitations of our framework. Finally weprovide some insights on how to best maximize ourframework performance under different scenarios.
Discussion of label cardinality Our experiment results include the label cardinality N = 10 and N = 100,
which show that the noisy label accuracy by RandRes
for 10 classes is higher than that at the same ε by RandRes for 100 classes. Therefore, the advantage of leveraging our framework on CIFAR10 is smaller than thaton CIFAR100. For smaller label cardinality, e.g., binaryclasses, this is also true. We expect the utility advantage
of our framework to exist for various label cardinality,
though the advantage may be smaller for lower N .
Limitations: While our framework significantly improves the utility on CIFAR10, CIFAR100 and CINIC10
datasets, here we discuss two limitations of our work.
1. One limitation of our framework is that it requires
more computing resources. Table 8 and Table 7
summarizes the computation time of generating thedifferentially private labels and training the models under label-DP respectively on CIFAR10. In Table 8, we can see that RandRes and ALIBI only incur negligible computation time, while NoiseCluster requires 21.3 h as it needs to train unsupervised learning model. PATE-FM requires much
more time: it needs to train hundreds of models in
the teacher model and therefore needs around 6000
GPU·h (though this process can be parallelized).
For model training process, our framework also incurs much more computational resources. For example, DenoiseSSL needs sequential steps, i.e., we firstneed to train an unsupervised model f0 (though f0
can be used for both NoiseCluster and DenoiseSSL),
we then use semi-supervised learning.

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

346

Table 7. The computation time of training models on a single NVIDIA Tesla-P100 GPU under label-DP on CIFAR10.
Algorithm Name

LP-1ST(+mixup)

ALIBI

DenoiseSSLLDP-SSLLDP-AugDescent

Time

2.3 h

2.9 h

47.6 h26.9 h

10.0 hTable 8. The computation time of DP label on CIFAR10.
AlgNameNoiseCluster

RandRes

PATE-FM

ALIBI

Time

21.3 h0.5 s∼6000 GPU·h

0.03 s2. All three datasets evaluated are image datasets. For
non-vision datasets, we expect that in our framework, NoiseCluster will still add less noise comparedto RandRes and PATE-FM under the same ε privacy level, DenoiseSSL can generate a smaller label
set with higher accuracy and LDP-LNL can improveutility, though the utility advantage may not be as
significant as that on vision datasets.
Recommendations on how to make a choice of
our framework: Here we provide some insights on
how to best maximize our framework performance whenoffering label-DP guarantee under different scenarios:
1. When ε is extremely low and therefore much noiseis added to the label set, for example, ε = 0.003
on CIFAR10, NoiseCluster provides a strong performance, i.e., 88.3% accuracy. In contrast, RandRes
provides private label set of 10.03% accuracy.
2. If abundant computing resource is available andwith a high label cardinality N and a low ε, forexample CIFAR100 at ε = 1, PATE-FM is competitive: it adds less noise compared to RandRes (andtherefore FixMatch and Aug-Descent on PATE-FM
can performs better and are usually preferred), but
requires much more computing resources to train
hundreds of models. The improvement in GPU technology are making the computing resources cheap
while the privacy threat remains severe, therefore
we recommended PATE-FM if abundant computing
resource is available. We consider the constraint ahigh N because at the same level of privacy, a higher
N will have lower accuracy by RandRes, i.e., the accuracy decrease is different between RandRes andPATE-FM as N increases. Compare CIFAR10 and
CIFAR100 at ε = 2. For CIFAR10, RandRes gives
45.2% while PATE-FM gives 94.9%. For CIFAR100,
RandRes gives 6.9%, while PATE-FM gives 48.1%,
i.e., the relative decreased accuracy is much lower
than RandRes. We consider the constraint a low εbecause for high ε, RandRes can be more accurate

on PATE-FM as the PATE-FM will be limited tothe single model’s performance. In fact, for high ε,even with a high N , RandRes is less affected compared to PATE-FM when samples are significantly
smaller as PATE-FM needs enough data to train theteacher model to get good accuracy, e.g., CIFAR100
at ε = 6.
3. Without above specific conditions, choosing RandRes makes the things simpler. Specifically, RandRes generally provides private label set with highaccuracy for high ε. We can estimate the value of p
by setting the label cardinality and epsilon. Whenε is relatively low, it’s advisable to consider our DenoiseSSL and algorithms like Aug-Descent to improve utility. For example, for CIFAR10 at ε = 1,
the noisy label accuracy is 23.2%, and we advise thereaders to consider our DenoiseSSL (90.8%) AugDescent (94.1%), which both are significantly higher
than 23.2%, while at ε = 8, the noisy label accuracy
is 99.7%, reader can simply consider LP1ST.

7 Related Work
7.1 Deep Learning with Differential
Privacy
To achieve differential privacy in modern ML models,Abadi et al. [1] design DP-SGD training algorithm.
Compared to the conventional SGD training algorithm,
DP-SGD involves two additional steps: (1) gradient clipping to bound sensitivity, where the gradient per eachtraining sample is clipped to make sure its norm isno larger than the clipping bound; (2) noise addition
to achieve DP guarantees, where a random Gaussian
noise is added to per-sample gradient before aggregating for gradient descent. For the added Gaussian noise,
its mean is 0 and its standard deviation is proportional
to the clipping bound in the gradient clipping step.
Furthermore, deep learning models are usually
trained with a large number of iterations. Abadi et al. [1]propose the moments accountant to compute accumulated privacy loss during training by tracking higher
moments of the privacy loss random variable, which isNot final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

shown to achieve tighter privacy analysis than standard
strong composition theorem in DP [19]. The researchcommunity further proposes tight privacy estimation
methods by using concentrated differential privacy [18]for privacy accounting [57], analyzing Rényi differential
privacy amplification [38] with sub-sampling [54], tracking the privacy loss distribution with central limit theorem [49]. Meanwhile, researchers also design methods toimprove the utility of differentially private deep learning models including using bounded activation functions [44], smoothing training loss functions [53]. Besides
image classification datasets evaluated in the original
paper [1], DP-SGD can also be applied into language
models [36] and federated learning settings [22].
When public data is available, Papernot et al. [42,43] propose another DP training algorithm by leveraging the semi-supervised knowledge transfer architecture.
They first train an ensemble of independent teacher
models on disjoint subsets of sensitive private training data. The predictions by these teacher models arethen aggregated and added a Laplacian/Gaussian noiseto achieve differential privacy guarantees. Finally, theytrain a student model as the final output on public datalabeled by the private aggregation of teacher ensembles.

347

7.3 Other Privacy Frameworks
Besides the standard differential privacy definition, theresearch community also seeks other quantification ofprivacy loss such as Rényi-DP [38], correlated-DP [61]and KL-DP [55] and capacity bounded DP [7]. Section 3
in Desfontaines et al. [13] gives a comprehensive survey
on how to quantify the privacy loss.
Another line of research focuses on identifying features/attributes to be preserved and designing frameworks accordingly. Section 3 in Desfontaines et al. [13]gives a comprehensive summary on how to identify theneighboring dataset, e.g., changing the sensitive property [29] (record or attribute), Pufferfish [30], privacy
axioms [28], Blowfish [27] and extension of DP using
metrics [6]. These frameworks generalize DP by restricting the secrets about individuals that should not be inferred by the attacker, as well as explicitly enumerating the side information available to the adversary, andtherefore allow to design novel, application specific privacy definitions that can achieve better privacy-utility
trade-offs than the original DP (e.g., achieved using DPSGD). Label-DP can be modeled as an instantiation of
AttributeDP, Pufferfish or Blowfish, where the secrets
to protect are the labels of training data (instead of bothfeatures and labels as in original DP).

7.2 Deep Learning with Label Differential
PrivacyGhazi et al. [23] propose the first label DP training
algorithm for deep learning. Similar as Section 4.2.1,
they first obtain differentially private training labels
by directly adding noises to labels with randomized response mechanism. To further improve standard supervised learning accuracy, they further employ a multistage training algorithm: the training set is divided into
multiple non-overlapping subsets, on each stage, they
use the last trained model to obtain predictions on a
new training subset and add randomized response noises
using these predictions as priors.
Malek et al. [35] further propose two label DP approaches. Their first approach is PATE-FM (see our
Section 4.2.2). The second approach ALIBI proposes asoft randomized response mechanism by directly adding
Laplace noises to one-hot encodings of training labels.
Based on the post-processing property of DP, they further leverage Bayes formula to compute the valid soft
training labels from the above noisy labels. After that,they perform standard optimization with soft labels.

8 Conclusion
In this work, we consider unsupervised learning andsemi-supervised learning (SSL) and investigate threepipelines for label-DP. Pipeline 1 NoiseCluster is basedon unsupervised learning and does not include private
labels in the learning phase, therefore much less noise
added. Pipeline 2 focuses on how to leverage the private
labels in the learning phase which includes our proposed
denoising algorithm DenoiseSSL based on unsupervised
learning and semi-supervised learning. Pipeline 3 which
is PATE-FM which benefits from only querying a partial
set of training set to reduce added noise. For evaluation,
we first investigated the quality of private label generation mechanisms, RandRes and PATE-FM. Next weevaluate our three pipelines and compare with previous
works. We also state our discussion on label cardinality, limitations and how to make the right choice in our
proposed framework. We hope this work can provide
insights on how to design label-DP systems.

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

Acknowledgements
We are grateful to anonymous reviewers at PoPETs forvaluable feedback. This work was supported in part by
the National Science Foundation under grants CNS2131910, CNS-1553437, CNS-1553301, CNS-1704105,
and CNS-1953786, the ARL’s Army Artificial Intelligence Innovation Institute (A2I2), the Office of Naval
Research Young Investigator Award, the Army Research
Office Young Investigator Prize, Schmidt DataX award,
and Princeton E-ffiliates Award.

References[1]

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan,
I. Mironov, K. Talwar, and L. Zhang, “Deep learning withdifferential privacy,” in Proceedings of the 2016 ACM
SIGSAC Conference on Computer and Communications
Security, 2016, pp. 308–318.
[2] G. Ateniese, L. V. Mancini, A. Spognardi, A. Villani, D. Vitali, and G. Felici, “Hacking smart machines with smarter
ones: How to extract meaningful data from machine learningclassifiers,” International Journal of Security and Networks,
vol. 10, no. 3, pp. 137–150, 2015.
[3] P. Bachman, O. Alsharif, and D. Precup, “Learning withpseudo-ensembles,” in Advances in Neural Information Processing Systems, 2014.
[4] B. Balle and Y.-X. Wang, “Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising,” in Proceedings of the 35th International
Conference on Machine Learning, 2018, pp. 394–403.
[5] R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error
bounds,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, pp. 464–473.
[6] K. Chatzikokolakis, M. E. Andrés, N. E. Bordenabe, andC. Palamidessi, “Broadening the scope of differential privacy
using metrics,” in Privacy Enhancing Technologies, 2013,
pp. 82–102.
[7] K. Chaudhuri, J. Imola, and A. Machanavajjhala, “Capacity
bounded differential privacy,” in Advances in Neural Information Processing Systems, 2019.
[8] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization.” Journal of Machine Learning Research, vol. 12, 2011.
[9] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in Proceedings of the 37th International Conference
on Machine Learning, 2020, pp. 1597–1607.
[10] T. Chen, S. Kornblith, K. Swersky, M. Norouzi, and G. E.
Hinton, “Big self-supervised models are strong semisupervised learners,” in Advances in Neural Information
Processing Systems, 2020.
[11] L. N. Darlow, E. J. Crowley, A. Antoniou, and A. J. Storkey,“Cinic-10 is not imagenet or cifar-10,” arXiv preprint

348

arXiv:1810.03505, 2018.
[12] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. FeiFei, “Imagenet: A large-scale hierarchical image database,”in 2009 IEEE Conference on Computer Vision and Pattern
Recognition, 2009.
[13] D. Desfontaines and B. Pejó, “Sok: differential privacies,”
Proceedings on Privacy Enhancing Technologies, vol. 2020,
no. 2, pp. 288–313, 2020.
[14] T. G. Dietterich, “Ensemble methods in machine learning,”
in International Workshop on Multiple Classifier Systems,
2000, pp. 1–15.
[15] C. Dwork, “Differential privacy: A survey of results,” in International Conference on Theory and Applications of Models of Computation, 2008, pp. 1–19.
[16] ——, “Differential privacy,” in Encyclopedia of Cryptography and Security, 2nd Ed, 2011, pp. 338–340.
[17] C. Dwork and A. Roth, “The algorithmic foundations ofdifferential privacy,” Found. Trends Theor. Comput. Sci.,
vol. 9, no. 3-4, pp. 211–407, 2014.
[18] C. Dwork and G. N. Rothblum, “Concentrated differential
privacy,” arXiv preprint arXiv:1603.01887, 2016.
[19] C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting anddifferential privacy,” in 2010 IEEE 51st Annual Symposium
on Foundations of Computer Science, 2010, pp. 51–60.
[20] V. Feldman, I. Mironov, K. Talwar, and A. Thakurta, “Privacy amplification by iteration,” in 2018 IEEE 59th Annual
Symposium on Foundations of Computer Science (FOCS),
2018, pp. 521–532.
[21] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion
attacks that exploit confidence information and basic countermeasures,” in Proceedings of the 22nd ACM SIGSAC
Conference on Computer and Communications Security,
2015, pp. 1322–1333.
[22] R. C. Geyer, T. Klein, and M. Nabi, “Differentially private
federated learning: A client level perspective,” arXiv preprint
arXiv:1712.07557, 2017.
[23] B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, andC. Zhang, “Deep learning with label differential privacy,” inAdvances in Neural Information Processing Systems, 2021.
[24] B. Han, Q. Yao, X. Yu, G. Niu, M. Xu, W. Hu, I. W. Tsang,and M. Sugiyama, “Co-teaching: robust training of deepneural networks with extremely noisy labels,” in Advances in
Neural Information Processing Systems, 2018.
[25] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, “Momentum
contrast for unsupervised visual representation learning,”
in 2020 IEEE/CVF Conference on Computer Vision and
Pattern Recognition (CVPR), 2020.
[26] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in 2016 IEEE/CVF Conference
on Computer Vision and Pattern Recognition (CVPR), 2016.
[27] X. He, A. Machanavajjhala, and B. Ding, “Blowfish privacy:
Tuning privacy-utility trade-offs using policies,” in Proceedings of the 2014 ACM SIGMOD International Conference on
Management of Data, 2014, p. 1447–1458.
[28] D. Kifer and B.-R. Lin, “Towards an axiomatization of statistical privacy and utility,” in Proceedings of the TwentyNinth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010, p. 147–158.
[29] D. Kifer and A. Machanavajjhala, “No free lunch in data
privacy,” in Proceedings of the 2011 ACM SIGMOD Interna-

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

tional Conference on Management of Data, 2011.
[30] ——, “Pufferfish: A framework for mathematical privacy
definitions,” ACM Transactions on Database Systems(TODS), vol. 39, no. 1, 2014.
[31] A. Krizhevsky, “Learning multiple layers of features fromtiny images,” 2009.
[32] D.-H. Lee, “Pseudo-label: The simple and efficient semisupervised learning method for deep neural networks,” inWorkshop on Challenges in Representation Learning, ICML,
vol. 3, no. 2, 2013, p. 896.
[33] H. Li, L. Xiong, L. Ohno-Machado, and X. Jiang, “Privacy
preserving rbf kernel support vector machine,” BioMed Research International, 2014.
[34] J. Li, R. Socher, and S. C. Hoi, “Dividemix: Learning withnoisy labels as semi-supervised learning,” in International
Conference on Learning Representations, 2019.
[35] M. Malek, I. Mironov, K. Prasad, I. Shilov, and F. Tramèr,“Antipodes of label differential privacy: Pate and alibi,” inAdvances in Neural Information Processing Systems, 2021.
[36] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang,“Learning differentially private recurrent language models,”in International Conference on Learning Representations,2018.
[37] L. Melis, C. Song, E. De Cristofaro, and V. Shmatikov, “Exploiting unintended feature leakage in collaborative learning,” in 2019 IEEE Symposium on Security and Privacy(SP), 2019, pp. 691–706.
[38] I. Mironov, “Rényi differential privacy,” in 2017 IEEE 30th
Computer Security Foundations Symposium (CSF), 2017,
pp. 263–275.
[39] K. Nishi, Y. Ding, A. Rich, and T. Höllerer, “Augmentation
strategies for learning with noisy labels,” in 2021 IEEE/CVF
Conference on Computer Vision and Pattern Recognition(CVPR), 2021.
[40] K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” in Proceedingsof the Thirty-Ninth Annual ACM Symposium on Theory ofComputing, 2007, p. 75–84.
[41] T. Orekondy, B. Schiele, and M. Fritz, “Knockoff nets:
Stealing functionality of black-box models,” in 2019
IEEE/CVF Conference on Computer Vision and Pattern
Recognition (CVPR), 2019.
[42] N. Papernot, M. Abadi, U. Erlingsson, I. Goodfellow, andK. Talwar, “Semi-supervised knowledge transfer for deeplearning from private training data,” in International Conference on Learning Representations, 2017.
[43] N. Papernot, S. Song, I. Mironov, A. Raghunathan, K. Talwar, and Ú. Erlingsson, “Scalable private learning withpate,” in International Conference on Learning Representations, 2018.
[44] N. Papernot, A. Thakurta, S. Song, S. Chien, and Ú. Erlingsson, “Tempered sigmoid activations for deep learningwith differential privacy,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 10, 2021.
[45] S. Sankararaman, G. Obozinski, M. I. Jordan, andE. Halperin, “Genomic privacy and limits of individual detection in a pool,” Nature genetics, vol. 41, no. 9, pp. 965–967,
2009.
[46] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,”349

in 2017 IEEE Symposium on Security and Privacy (SP),2017, pp. 3–18.
[47] K. Simonyan and A. Zisserman, “Very deep convolutional
networks for large-scale image recognition,” in International
Conference on Learning Representations, 2015.
[48] K. Sohn, D. Berthelot, N. Carlini, Z. Zhang, H. Zhang,
C. A. Raffel, E. D. Cubuk, A. Kurakin, and C.-L. Li, “Fixmatch: Simplifying semi-supervised learning with consistency
and confidence,” in Advances in Neural Information Processing Systems, 2020.
[49] D. M. Sommer, S. Meiser, and E. Mohammadi, “Privacy
loss classes: The central limit theorem in differential privacy,” Proceedings on Privacy Enhancing Technologies, vol.
2019, no. 2, pp. 245–269, 2019.
[50] C. Song and V. Shmatikov, “Overlearning reveals sensitive
attributes,” in International Conference on Learning Representations, 2019.
[51] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart, “Stealing machine learning models via prediction apis,”in USENIX Security, 2016.
[52] W. Van Gansbeke, S. Vandenhende, S. Georgoulis,
M. Proesmans, and L. Van Gool, “Scan: Learning to classify
images without labels,” in European Conference on Computer Vision, 2020, pp. 268–285.
[53] W. Wang, T. Wang, L. Wang, N. Luo, P. Zhou, D. Song,and R. Jia, “Dplis: Boosting utility of differentially private
deep learning via randomized smoothing,” Proceedings on
Privacy Enhancing Technologies, vol. 2021, no. 4, pp. 163–
183, 2021.
[54] Y.-X. Wang, B. Balle, and S. P. Kasiviswanathan, “Subsampled rényi differential privacy and analytical moments
accountant,” in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019, pp.
1226–1235.
[55] Y.-X. Wang, J. Lei, and S. E. Fienberg, “On-average klprivacy and its equivalence to generalization for max-entropy
mechanisms,” in International Conference on Privacy in
Statistical Databases, 2016, pp. 121–134.
[56] S. L. Warner, “Randomized response: A survey technique for
eliminating evasive answer bias,” JASA, vol. 60, no. 309, pp.
63–69, 1965.
[57] L. Yu, L. Liu, C. Pu, M. E. Gursoy, and S. Truex, “Differentially private model publishing for deep learning,” in 2019
IEEE Symposium on Security and Privacy (SP), 2019, pp.
332–349.
[58] S. Zagoruyko and N. Komodakis, “Wide residual networks,”
in British Machine Vision Conference, 2016, pp. 87.1–87.12.
[59] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz,“mixup: Beyond empirical risk minimization,” in International Conference on Learning Representations, 2018.
[60] Z. Zhang, B. I. Rubinstein, and C. Dimitrakakis, “On the
differential privacy of bayesian inference,” in Proceedingsof the AAAI Conference on Artificial Intelligence, vol. 30,
no. 1, 2016.
[61] T. Zhu, P. Xiong, G. Li, and W. Zhou, “Correlated differential privacy: Hiding information in non-iid data set,” IEEE
Transactions on Information Forensics and Security, vol. 10,
no. 2, pp. 229–242, 2014.

Not final; page numbers may change before publication
Machine Learning with Differentially Private Labels: Mechanisms and Frameworks

Table 9. Comparison with the existing works of different model architectures on CIFAR10.
ResNet-18

VGG-16

WRN-28-4

Method

ε=2

ε=3

ε=4

ε=2

ε=3

ε=4

ε=2

ε=3

ε=4

Our work
ALIBI [35]
LP1ST [23]

95.2%
81.9%
83.2%

96.2%
87.2%
89.5%

96.5%
89.6%
92.0%

94.5%
81.6%
83.5%

95.0%
86.0%
87.0%

95.4%
88.3%
91.8%

93.1%
73.0%
75.7%

94.1%
82.8%
88.7%

94.7%
86.9%
92.7%

Non-private baseline

97.2%

A Ablation Study on Different
Model Architectures
In addition to ResNet-18 [26], we use two more architectures including VGG-16 [47] and WideResNet-284 (WRN-28-4) [58] and present the comparison of ourframework and previous works on CIFAR10 dataset atε = 2, 3, 4 in Table 9. On all three different model architectures, we can see that our framework is much better than previous works LP1ST (+mixup) and ALIBI.
Specifically, at ε = 4, our framework is close to the nonprivate baseline, which shows the effectiveness of ourframework across different model architectures.

95.8%

96.9%

350