Deep Learning with Label Differential Privacy
Authors: Badih Ghazi
Noah Golowich
Ravi Kumar
Pasin Manurangsi
Chiyuan Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
label differential privacy
randomized response
deep learning
self-supervised learning

Abstract: The Randomized Response (RR) algorithm is a classical technique to improve robustness in survey aggregation, and has been widely adopted in applications with differential privacy guarantees. We propose a novel algorithm, Randomized Response with Prior (RRWithPrior), which can provide more accurate results while maintaining the same level of privacy guaranteed by RR. We then apply RRWithPrior to learn neural networks with label differential privacy (LabelDP), and show that when only the label needs to be protected, the model performance can be significantly improved over the previous state-of-the-art private baselines. Moreover, we study different ways to obtain priors, which when used with RRWithPrior can additionally improve the model performance, further reducing the accuracy gap between private and non-private models. We complement the empirical results with theoretical analysis showing that LabelDP is provably easier than protecting both the inputs and labels.

Deep Learning with Label Differential Privacy
Badih Ghazi Google Research badi highaigggogggleeeee
Noah Golowich EECS, MIT nzg@mit.edi
Ravi Kumar Google Research ravi @owi..k3@gmil. com
Pasin Manurangsi Google Research pasinggoogle.cm com
Chiyuan Zhang Google Research chiyuan@google.c com com
Abstract
The Randomized Response (RR) algorithm 26 is classical technique improve robustness in survey aggregation, and has been widely adopted applications with differential privacy guarantees. We propose novel algorithm, Randomized Response with Prior (RRWi thPrior). which can provide more accurate results while maintaining the same level of privacy guaranteed by RR. We then apply RRWi thrriorr to learn neural networks with label differential privacy (LabelDP), and show that when only the label needs to be protected, the model performance can be significantly improved over the previous state-of fate--ofttee ff--the-rt private baselines. More- over, we study different ways to obtain priors, which when used with RRWi thPrior can additionally improve the model performance, further reducing the accuracy gap between private and non-private models. We complement the empirical results with theoretical analysis showing that LabelDP is provably easier than protecting both the inputs and labels.
Introduction
The widespread adoption of machine learning in recent years has increased the concerns about the privacy of individuals whose data is used during the model training. Differential privacy (DP) << [3]]
has emerged as popular privacy notion that has been the basis of several practical deployments in
industry [55 12
9 29 and the U.S. Census [3
classical algorithm that predates DP and initially designed eliminate evasive answer biases in survey aggregation- is Randomized Response (RR) [96]: when the input an element from a finite alphabet, the output is equal the input with certain probability, and is uniform random other element from the alphabet with the remaining probability. This simple algorithm is shown to satisfy the strong notion of local DP 3S 58 whereby the response of each user is protected, in contrast with the so-called central DP setting where a curator has access to the raw user data, and only the output of the curator required to be DP. We note that schemes building on RR have been studied in
several previous works on DP estimation (c.g., 30 57 )) and have been deployed in practice 32)
17 has stimulated significant research aiming to improve its accuracy, mostly by relaxing to weaker privacy models (c.g., 36 24 4). this work. different approach and seek to improve RR by leveraging available prior information. (A recent work of Liu et al. multiplicative weights algorithm, which applies in the central DP setting.) The prior information can consist of domain-specific knowledge, (models trained on) publicly available data, or historical
Mcanwhile, the large error incurred by RR (c.g..
( also used priors to improve accuracy, but the context of the DP
Part of this work was done while at Google Research.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

runs of a training algorithm. Our algorithm is presented in Section (Algorithm 2). At a high level, given a prior distribution p on the alphabet, the algorithm uses p to prune the alphabet. the prior is reliable and even if the alphabet is only minimally pruned, the probability that the output equals the input is larger than when RR is applied to the entire alphabet. On the other hand, if the prior is uniform over the entire alphabet, then our algorithm recovers the classical RR. To implement the above recipe, one needs to specify how to effect the pruning using p. It turns out that the magnitude of pruning can itself vary depending this. Interestingly, by studying a suitable linear program, we show that the resulting RRWi thPrior strategy is optimal in that among all E-DP algorithms, it maximizes the probability that the output equals the input when the latter is sampled from p (Theorem 3
p. but we can obtain closed-form formula for determining
1.1 Applications to Learning with Label Differential Privacy
There have been a great number of papers over the last decade that developed DP machine learning
algorithms (e.g.. [19 102
88 83 78) In the case of deep learning, the seminal work of Abadi
et al. 2 introduced a DP training framework (DP-SGD) that was integrated into TensorFlow
[80] and
Py 1921. Despite numerous followup works, including, e.g., (75/77 67 98
71
20 933. and
extensive efforts, the accuracy of models trained with DP-SGD remains significantly lower than that of models trained without DP constraints. Notably, for the widely considered CiFAR-10 dataset, the highest reported accuracy for DP models is 69.3% [93] which strikingly relies on handcrafted visual features despite that in non-private scenarios learned features long been shown to be superior. Even using pre-training with external (CIFAR-100) data, the best reported DP accuracy, 73% is still far below the non-private baselines (> 95%). The performance gap becomes a roadblocker for many real-world applications adopt DP. In this paper, we focus on more restricted, but important, special case where the DP guarantee is only required to hold with respect to the labels, as described next.
In the label differential privacy (Da) setting, the labels are considered sensitive, and their privacy needs to be protected, while the input points are not sensitive. This notion has been studied in the PAC setting 18 13 and for the particular case of sparse linear regression 194] and it captures several practical scenarios. Examples include: (i) computational advertising where the impressions known to the Ad Tect and thus considered non-sensitive, while the conversions reveal user interest and are thus private (see, e.g., Nalpas and Dutton [X and [8), (ii) recommendation systems where the choices are known, e.g., to the streaming service provider, but the user ratings are considered sensitive, and (iii) user surveys and analytics where demographic information (e.g., age, gender) is non-sensitive but income is sensitive-in fact, this was the motivating reason for Warner [66] to propose RR many decades ago! We present a novel multi-star stage algorithm (LP-MST) for training deep neural networks with Labe LDP that builds on top of RRWi thPrior (see Section 3 and Algorithm b). and we benchmark its empirical performance (Section 5 on multiple datasets, domains, and architectures. including the following.
On CIFAR-10, we show that it achieves 20% higher accuracy than DP-SGO
On the more challenging CIFAR-100, we present the first non-trivial DP learning results. On MovieLens, which consists of user ratings of movies, we show improvements via LP-MST.
In some applications, domain specific algorithms can be used to obtain priors directly without going through multi-stage training. For image classification problems, we demonstrate how priors computed from a (non-prie coon-rrivate) eelf-supervised learning 22 23 5 [6] phase on the input images can be used to achieve higher accuracy with LabelDP guarantee with extremely small privacy budgets (e & 0.1, see Section 5.2 for details).
We note that due to the requirement of DP-SGD to compute and clip per-instance gradient, it remains technically challenging to scale to larger models or mini-batch sizes, despite numerous attempts to On the other hand, our formulation allows us to use ot
minigate this problem [42 5 26
90
For DP parameters of s 8 and 10 5 cited from Abadi et al.
2 Figure 6]. For formal definition of
DP, we refer the reader to Definition 2.1
Add tech (abbreviating Advertising Technology) comprises the tools that help agencies and brands target, de- liver, and analyze their digital advertising efforts; see, e.g.. alog.hubbsper cetpppot.coo//markeeee wwt.//arkeeeineeeeeee wiwpi//ggwwwatii-ioiee ad- tech)
*We remark that the notion of e e-DP in 2 770 775 is nor directly comparable to E L-Label DP in our work in
that they use the addittoon/remoal notion whereas we use the substitution one. Please see the Supplementary
Material for more discussion on this.
2

---

the-art deep learning architectures such as ResNet [5I]. We also stress that our LP-MST algorithm goes beyond deep learning methods that are robust label noise. (See [87 for a survey of the latter.)
Our empirical results suggest that protecting the privacy of labels can be significantly easier than protecting the privacy of both inputs and labels. We find further evidence this by showing that for the special case of stochastic convex optimization (SCO), the sample complexity of algorithms privatizing the labels is much smaller than that of algorithms privatizing both labels and inputs; specifically, we achieve dimension- dimension-inudependenn bounds for Labe IDP (Section o good prior can ensure smaller population error for non-convex loss. (Details are in the Supplementary Material.)
We also show that
2 Preliminaries
For any positive integer K, let [K] : [l,..., ......,K,, Randomized response (RR) 16 is the following: let e 2 0 be parameter and let y E [K] be the true value known to RR. When observer queries the value of y, RRg responds with random draw 7 from the following probability distribution:
for ÿ = y otherwise.
Pr 5]
In this paper, focus the application of learning with label differential privacy. We recall the definition of differential privacy (DP), which is applicable to any notion of neighboring datasets. For textbook reference, we refer the reader Dwork and Roth (32
Definition 2.1 (Differential Privacy (DP) B3 B41). Let ò E R22. A randomized algorithm A taking
as input a dataset said to be (e, -)dfffrrrrntl private ()-D) if for any two neighboring datasets D and D', and for any subset S of outputs of A, it is the case that Pr[A(D) S] S
ex Pr(A(DD) E S] + 5. If 5 = 0, then A is said to be E-differentially private (s-DP).
When applied machine learning methods in general and deep learning in particular, DP is usually enforced on the weights of the trained model [see, e.g., 19 59 In this work, we focus on the notion of label differential privacy.
Definition 2.2 (Label Differential Privacy). Let Rz0. A randomized training algorithm A taking as input a dataset is said to be (s, 8')-abel differentially private ((s, d)-LabelDP) if for any two training datasets D and D' that differ in the label of single example, and for any subset S of outputs of A, it is the case that Pr[A(D)= E S] < e Pr(A(DD) E S] + d. If = 0, then A is said to be s-label differentially private (c (p-LabeLDP).
All proofs skipped in the main body are given in the Supplementary Material.
3 Randomized Response with Prior
In many real world applications, a prior distribution about the labels could be publicly obtained from domain knowledge and help the learning process. In particular, we consider setting where for each (private) label y in the training set, there is an associated prior p (PI....,, .Pkk. The goal is to output a randomized label ý that maximizes the probability that the output is correct (or equivalently maximizes the signal-to-noise ratio), i.e., Pr(y = 7). The privacy constraint here is that the algorithm should be DD with respect to y. (It need not be private with respect to the prior p.)
We first describe our algorithm RRWi thPrior by assuming access such priors.
3.1 Algorithm: RRWithPrior
We build our RRWithPrior algorithm with a subroutine called RRTop-k, as shown in Algorithm I which is a modification of randomized response where we only consider the set of l labels i with largest p;. Then, if the input label y belongs to this set, we use standard randomized response on this set. Otherwise, we output a label from this set uniformly random.
The main idea behind RRWi thPrior is to dynamically estimate an optimal k* based on the prior p. and run R with k". Specifically, we choose k* by maximizing Pr Pr(RRTop-k(y) v]. It is not
3

---

Algorithm RRTop-k
Input: A label y E [K]
Parameters: k E [K], prior p - (pI,...,PK)
1. Let Y2 be the set of k labels with maximum prior probability (with ties broken arbritrarily).
2. If y Yk, then output y with probability e* and output y Yx \ {リ} with probability
+
3. If y & Ys, output an element from Y& uniformly at random.
hard to see that this expression is exactly equal to e++k-T (Evers Pb) if ~ RRWithPrior is presented in Algorithm
Algorithm 2 RRWithPrior
Input: label y E [K]
Parameters: prior (pI,...,Pk)
1. For & E [K]:
(a) Compute = =- (Eyev, Pb)
where Y2 is the set of & labels with maximum prior probability (ties broken arbritrarily).
2. Let k" arg max Wk.
3. Return an output of RRTop-k (y) with & = k..
3.1.1 Privacy Analysis
It is not hard to show that RRTop-k is g-DP.
Lemma 1. RRTop-k is e-DP.
The privacy guarantee of RRWi thPrior follows immediately from that RRTop-k (Lemmal I since choice of & does not depend on the label y:
Corollary 2. RRWithPrior is E-DP.
For learning with a LabelDP guarantee, we first use RRWithPrior to query a randomized label for each example of the training set, and then apply general learning algorithm that is robust to random label noise to this dataset. Note that unlike DP-SGD [2] that makes new queries on the gradients in every training epoch, we query the randomized label once and reuse it in all the training epochs.
3.2 Optimality of RRWithPrior
In this section will prove the optimality of RRWi thPrior. For this, we will need additional notation. For any algorithm R that takes as input label y and outputs randomized label ÿ. we let Objp (R) denote the probability that the output label is equal the input label y when y is distributed as p. i.e Obi, (R) = Prw-p RRy) y), where the distribution of y ~ is Pr(y = i] P: for all E [K].
The main result of this section is that, among all s-DP algorithms, RRWithPrior maximizes Objp (R). stated more formally next.
Theorem 3. Let be any probability distribution on [K] and R be any e-DP algorithm that random- izes the input label given the prior p. We have that
Obi, (RRwith (R).
Before we proceed to the proof, we remark that our proof employs a lincar program (LP) to character- ize the optimal mechanisms; generic form of such LPs has been used before in 4% 3 However, these works focus on different problems (linear queries) and their results do not apply here.
Proof of Theorem Consider any e-DP algorithm R. and let dyly denote Pr(R(y) 5]- Observe that Obip (R) Eye(M) Py Julv-

---

Since y is probability distribution, we must have that
Oply = 1, Vy E [K], and dple 2 0, Vý. y E [K].
Finally, the e-DP guarantee of R implies that
4yly S e Oglv
Vy. v.y. E [K].
Combining the above, Objp (R) is upper-bounded by the optimum of the following linear program (LP), which we refer to LP1:
Σ Py
max
Aulv
VE(R)
s.t.
fyly
e 'glv'
Vū. v E [K],
(2)
P5ly = 1
Ay E [K].
(3)
]E[K]
Oplv 2 0
Vg.y E [K].
Notice that constraints 2 and
3
together imply that:
Oylv t
S1
Vy E [K]-
In other words, the optimum of LP1 is at most the optimum of the following LP that we call LP2:
Σ
max
Py
Oy
s.t.
Gylv + c
4slo S 1
Vy E [K]
(4)
Aulv 20 0
Vy [K].
(5)
optimal solution to LP2 must be vertex (aka extreme point) of the polytope defined by and (5) Recall that an extreme point of a K K-dimensional polytope must satisfy K independent constraints with equality. In our case, this means that one of the following occurs:
Inequality (5) is satisfied with equality for all E [K] resulting in the all-zero solution (whose objective zero), or, For some non-empty subset Y C [K]. inequality is satisfied with equality for all Y, and inequality
5 satisfied with equality for y E [K] Y. This results in
ifye if y & Y.
Pyly
0
This yields an objective value of or In conclusion, we have that
+ EyEy Pv.
6
(b) S max
Pu
BFYS(R] e + +
DEY
e
Σ Ps
max
max
KE[K] E + k
YCKKI.M
=
NEY
e
Σ Pv BEY
max KE[K] E + -k-1
max Wk: kE[K]
where the last two equalities follow from our definitions of YE and Obj, (RRWii max Wk. Thus, we get that Obj, (RRWi (herior)r 2 Obj, (R) as de- sired.
Notice that
5

---

Application of RRWithPrior: Multi-Stage Training
Our RRWi thPrior algorithm requires publicly available priors, which could usually be obtained from domain specific knowledge. In this section, describe training framework that bootstraps from uniform prior, and progressively learns refined priors via multi-stage training. This general framework be applied to arbitrary domains
when no public prior distributions are available.
Specifically, we assume that we have training algorithm A that outputs a probabilistic classifier which, on given unlabeled sample x, can assign a probability Py to each class [K]. We partition our dataset into subsets 8(1),... ..... S(T), and we start with trivial model M (9) that outputs equal probabilities for all classes. At each stage / [T]. we use the most recent model ( to assign the probabilities (Pi..... .PK) for each sample x, from S(0 Applying RRWi thPrior with this prior on the true label yr. we get randomized label ÿ x,. We then use all the samples with randomized labels obtained so far to train the model M())
The full description of our LP-MST (Label Privacy Multi-Stage Training) method is presented in Algorithm 3 We remark here that the partition 5(1) ;.... STT) can be arbitrarily chosen, as long as does not depend the labels ........ ................................ Y/. We also stress that the training algorithm need not be
private. We use LP-1ST to denote our algorithm with one stage, LP-2ST to denote our algorithm with two stages, and on. We also note that LP-1ST is equivalent to using vanilla RR. The 7th stage of multi-stage algorithm is denoted stage-t.
Algorithm 3 Multi-Stage Training (LP-MST)
Input: Dataset S = {(x1, yn ..... (Xn,
)
Parameters: Number T of stages, training algorithm
1. Partition S into (())
...., _ 5(7)
2. Let ( be the trivial model that always assigns equal probability to cach class.
3. For = 1 T:
(a) Let ((t)
= 0.
(b) For each (x:, 3.) E S(t;
i. Let = (pi..... PK) be the probabilities predicted by ( on X
ii Let V4 RRWithPrion
iii. Add (x, Ji) to 5(0)
(c) Let M be the model resulting from training on 5(1) U.00 using A.
4. Output M
The privacy guarantee of LP-MST is given by the following: Observation 4. For any 0, if RRWithPrior is e-DP, then LP-MST is e-LabelDP.
Proof. We will in fact prove a stronger statement that the algorithm is e-DP even when we output all the T models M (1). M (T)
(T) together with all the randomized labels V1.... In. For any possible output models m (1) m (T) and output labels 21, Zn. we have
(r(M()) (l) MT) m (T), Ø1 21, Dn zn]
ÿr zi M m/(-u1]
I
Pr M (4)
Ú: ===
Pr (ES())
II
Consider any two datasets D. D' that differ on single user's label; suppose this user j and that the user belongs to partition E [T'. Then, the above expression for D and that for D' are the same in all but one term: Pr Ι = z, (M((- = m which is the probability that RRWi twwrior (t-))))))(()) outputs 2, Since RRWi ihrr is e-DP, we can conclude that the ratio between the two probabilities is at most ef as desired.
We stress that this observation holds because each sensitive label y is only used once Line ((bjii of Algorithm B as the dataset S is partitioned at the beginning of the algorithm. As result, since each

---

Table 1: Test accuracy (%) 100. The baseline performances taken from previously published results correspond to DD- with 10 10-5. The star" indicates the use of CIFAR-II 100 pre-trained representations.
Algorithm
8
8
=3
e =
8 0C
DP-SGD w/ pre-train"
67
70
73
80
DP-SGD 7
61.6(e=7.53)
76.6
Tempered Sigmoid
66. 66.2(c=7.53)
Yu et al.
28
44.3(e=6.78)
Nasr et al. A
55
Chen and Lee
20
53
ScatterNet+CNN
93
69.3
LP-1ST
59.96
82.38
89.89
92.58
93.58
94.70
94.96
LP-2ST
63.67
86.05
92.19
93.37
94.26
94.52
LP-1ST w/ pre-train"
67.64
83.99
90.24
92.83
94.02
94.96
95.25
LP-2ST w/ pre-train"
70.16
87.22
92.12
93.53
94.41
94.59
Table 2: Experiments on CIFAR-100 100. The non-private baseline (c oc) is 76.38% test accuracy.
Algorithm
3
8
=
4
=
5
==
C =
LP-1ST
20.96
46.28
61.38
68.34
73.59
LP-2ST
28.74
50.15
63.51
70.58
74.14
stage is E-LabelDP, the entire algorithm is also e-LabelDP. This is known (an adaptive version of a) parallel composition [68]
Finally, we point out that the running time of our RRWi thPrior algorithm is quasi-linear in K (the time needed to sort the prior). This is essentially optimal within multistage training, since O(K) time will be required to write down the prior after each stage. Moreover, for reasonable values of K, the running time will be dominated by back pock-propagation for gradient estimation. Morcover, the focus of the current work is on small to modest label spaces (i.e., values of K).
5 Empirical Evaluation
We evaluate RRWI thPrrir standard benchmark datasets that have been widely used in previous works on private machine learning. Specifically, in the first part, we study our general multi-stage training algorithm that boostraps from uniform prior. We evaluate it image classification and collaborative filtering tasks. the second part, we focus on image classification only and use domain- specific techniques to obtain priors for RRWi thPrior. We use modern neural network architectures (e.g., ResNets (51) and the mixup [OI regularization for learning with noisy labels. Please see the Supplementary Material for full details on the datasets and the experimental setup.
5.1 Evaluation with Multi-Stage Training
CIFAR-10 60 is 10-class image classification benchmark dataset. We evaluate our algorithm and compare it to previously reported DP baselines in Table [ Due to scalability issues, previous DP algorithms could only use simplified architectures with non-private accuracy significantly below the state-of-ther art. Moreover, even when compared to those weaker non-private baselines, large performance drop is observed in the private models. In contrast, we use ResNet18 with 95% non- private accuracy. Overall, our algorithms improve the previous state-of of of-the-art by margin of 20% across e's. Abadi et al. [2] treated CIFAR- as public data and use it to pre-train a representation to boost the performance of DP-SGD. We also observe performance improvements with CIFAR-100 pre-training (Table T bottom rows). But even without pre-training, our results are significantly better than DP-SGD even with pre-training.
7

---

Table 3: Experiments on MovieLens- IM. The numbers show the test RMSE.
Algorithm
=
5 = 2
8 == 3
8 == 4
== 8
È' = oc
LP-1ST
1.122 1.034
0.981
0.902
0.877
0.867
0.868
LP-2ST
0.928
0.891
0.874
0.865
Gaussian DP 15
0.915 (e 10)
In Table 2 we also show results on 100, which is more challenging variant with 10x more classes. To the best of our knowledge, these are the first non-trivial reported results CIFAR-100 for DP learning. For E = 8, our algorithm is only 2% below the non-private baseline.
In addition, we also evaluate on MovieLens- IM 49 which contains million anonymous ratings of approximately 3, 900 movies, made by 6,040 MovieLens users. Following [[5], we randomly split the data into 80% train and 20% test, and show the test Root Mean Square Error (RMSE) in Table B
Results on MNIST 61 Fashion MNIST 97.. and KMNIST 25 and comparison more baselines can be found in the Supplementary Material. In all the datasets we evaluated, our algorithms not only significantly outperform the previous methods, but also greatly shrink the performance gap between private and non-private models. The latter is critical for applications of deep learning systems in real-world tasks with privacy concerns.
Beyond Two Stages. In Figure I Ta), report results on LP-MST with T' 2. For the cases tried, we consistently observe 1-2% improvements on test accuracy when going from LP-2ST to LP-3ST. In our preliminary experiments, going beyond T >> 4 stages leads to diminishing returns on some datasets.
5.2 Evaluation with Domain-Speccfic Priors
The sulti-stage training framework evaluated in the previous section is a general domain- aggnosicc algorithm that bootstraps itself from uniform priors. In some cases, domain-spectie
priors can be obtained to further improve the learning performance. In this section, we focus on image classification applications, where new advances in self-supervised learning (SSL) 22
23
44
53
Tol show that
high-quality image representations could learned on large image datasets without using the class labels. In the setting of LDb the unlabeled images are considered public data, so we design an algorithm to use SSL to obtain priors, which then fed to RRwi for discriminative learning.
Specifically, we partition the training examples into groups by clustering using their representations extracted from SSL models. We then query a histogram of labels for each group via discrete Laplace mechanism (aka Geometric Mechanism) 41 If the groups are largely homogeneous, consisting of mostly examples from the same class, then we can make the histogram queries with minimum privacy budget. The queried histograms are used as label priors for all the points in the group. Figure [b)) shows the results on two different SSL representations: BYOL EKl, trained on unlabeled CIFAR- images and DINO [16,, trained ImageNet (27 images. Comparing to the baseline, the SSL-based priors significantly improves the model performance with small privacy budgets. Note that since the SSL priors are not true priors, with large privacy budget (s = 8), it actually underperforms the uniform prior. But in most real world applications, small are generally more useful.
Theoretical Analysis
Previous works have shown that LabelDP can be provably easier than DP in certain settings; specif- ically, in the PAC learning setting, Beimel al. [33 proved that finite VC dimension implies learnability by LabelDP algorithms, whereas it is known that this is not sufficient for DP algo-
rithms
We extend the theoretical understanding of this phenomenon to the stochastic convex optimization (SCO) setting. Specifically,, we show that, by applying on the labels and running SGD on top of the resulting noisy dataset with an appropriate debiasing of the noise, one can arrive at the following dimension
dimensioonindependdee independent excess population loss.

---

90
0.9
80
test accuracy
test accuracy
0.8
Fashion MNIST
CIFAR-10
CIFAR-10 (w/ pre-train)
0.7
CIFAR-100
60
0.6
Uniform Prtor
DINO ImageNet
50
BYOL on CIFAR-10
0.5
2
0.05
0.1
0.2
0.5 1.0
12.0
(a)
num stages
(b)
privacy budget (E)
Figure I: (a) Test accuracy (%) on various datasets with LP-MST for T 2. The curve "CIFAR-I0 w/ pre-train" is using CIFAR-100 as public data to pre-train the model. (b) RRWi thPrior with priors obtained from histogram query based clustering in various SSL representations. We also plot recent results (ClusterRR) from Esfandiari et al. 37 which is a clustering based LabelDP algorithm.
Theorem (Informal). For any E E (0, 1), there an E-Labe algorithm for stochastic convex optimization with excess population loss Ô (DL. =yR
K where denotes the diameter of the
parameter space and L denotes the Lipschitz constant of the loss function.
The above excess population loss can be compared to that of Bassily et
who gave an (c, 6)- DP algorithm with excess population loss OD,L V vP where p denote the dimension of the parameter space: this bound is also known to be tight in the standard DP setting. The main advantage of our guarantee in Theorem ilis that it is independent of the dimension p. Furthermore, we show that our bound is tight up to polylogarithmic factors and the dependency on the number of classes K.
The above result provides theoretical evidence that running RR on the labels and then training this noisy dataset can be effective. We can further extend this to the setting where, instead of running RR, run RRTop-k before running the aforementioned (debiased) SGD, although pettoougghpprhpps as expected-our bound on the population loss now depends on the quality of the priors
Corollary (Informal). Suppose that we are given a prior Pa: for every x and let Y denote the set of top-k labels with respect to Then, for any s E (0, 1), there is an E-LabelDP algorithm for stochastic convex optimization with excess population loss Ô [DL. ( + +P((a.))DDyy $ xK()
where D, L are defined in Theorem 5 and 'D is the data distribution.
When our top-k set is perfect (i.c., y always belongs to Y the bound reduces to that of Theorem 5 but with the smaller k instead of K. Moreover, the second term is, in sense, penalty we pay the excess population loss for the inaccuracy of the top-k prior. We defer the formal treatment and the proofs the Supplementary Material, in which also present additional generalization results for non-convex settings.
Note that Corollary i not in the exact setup we run in experiments, where we dynamically calculate an optimal for each given generic priors (via RRWi RRW thPrior), and for which the utility is much more complicated to analyze mathematically. Nonetheless, the above corollary corroborates the intuition that good prior helps with training.
Conclusions and Future Directions
In this work, we introduced a novel algorithm RRWi thPrio (which can be used to improve on the traditional mechanism), and applied it to LabelDP problems. We showed that prior information can be incorporated to the randomized label querying framework while maintaining privacy constraints. We demonstrated two frameworks apply RRWi thPrior: (i) a general multi-stage training algorithm LP-MST that bootstraps from uniform priors and (ii) an algorithm that build priors from clustering with

---

SSL-based representations. The former is general purpose and can be applied to tasks even when no tomain-specifie priors are available, while the latter uses nomain-specific algorithm to extract priors and performs well even with very small privacy budget. As summarized by the figure on the right, in both cases, by focusing on LabelDP, our RRWi thPrior significantly improved the model performance of previous sate-of-the-art DP models that aimed to protect both the inputs and outputs. We note that, following up on our work, additional results on deep learning with LabelDP were obtained [66 [00) The narrowed performance gap between private and non-private models is vital for adding DP to real world deep learning models. We nevertheless stress that our algorithms only protect the labels but not the input points, which might not constitute a sufficient privacy protection in all settings.
Our work opens up several interesting ques- tions. Firstly, note that our multi-stage train- ing procedure uses very different ingredients than those of Abadi et al. [2] (which employ DP-SGD, privacy amplification by subsampling.
90
CIFAR-10 test accuracy
and Renyi accounting); can these tools be used to further improve LabelDP? Secondly, while
80
LP-ST. Z
CPARIP-55L 55L BYOL 6
IragheesSS in DIO, 6
our procedure can be implemented in the most
RP-SED (Abecl 20161, 2-6666--110 1-12
stringent local DP setting 5 (58), can it be im-
(Foperox ot 20201. 5-101
proved in the weaker central (aka trusted cura-
tor) DP model, assuming the curator knows the prior? Thirdly. while our algorithm achieves pure DP (i.e., = 0), is higher accuracy possi- ble for approximate DP (i.e., 5 > 0)?
60
50
0.05
0.1
0.2
0.5
2
4
Acknowledgements
(privacy loss)
The authors would like thank Sami Torbey for very helpful feedback on an early version of this work. At MIT, Noah Golowich was supported by a Fannie and John Hertz Foundation Fellowship and NSF Graduate Fellowship.
References
[1] M. Abadi, A. Agarwal, P. Barham, Brevdo, Chen, C. Citro, Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp. G. Irving, M. Isard, Y. Jia, R. Joze- fowiez, L. Kaiser, M. Kudlur, Levenberg, Mané, R. Monga, S. Moore, Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Va- sudevan, Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning on heterogencous systems, 2015. Software avail- able from tensorflow.or
[2] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. CCS, pages 308-318, 2016.
[3] J. M. Abowd. The US Census Bureau adopts differential privacy. In KDD, pages 2867-2867. 2018.
[4] J. Acharya, K. Bonawitz, P. Kairouz, D. Ramage, and Z. Sun. Context aware local differential privacy. ICML, pages 52-62, 2020.
[5] A. Agarwal and I. Ganichev. Auto-vectorizing tensorflow graphs: Jacobians, auto-batching and beyond. MXXv:1903.04244 2019.
[6] A. Agarwal, P. Bartlett, P. Ravikumar, and M. J. Wainwright. Information-theoreti lower bounds on the oracle complexity of convex optimization. In NIPS, page 1-9, 2009.
[7] N. Alon, R. Livni, M. Malliaris, and S. Moran. Private PAC learning implies finite Littlestone dimension. In STOC, pages 852-860, 2019.
'They in fact be implemented the slightly weaker sequentially interactive local DP model 31
10

---

[8] E. Anderson. Masked learning, aggregation and reporting workflow (masked lark). https:
//gi www.th..c./.ai.... htwp://c/w....aa...eeeerrnaaaaaa
.dd, 2021.
[9] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017.
[10] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In FOCS, pages 464 473, 2014.
[11] R. Bassily, V. Feldman, K. Talwar, and A. Thakurta. Private stochastic convex optimization with optimal rates. 0rX9970908.0997, 2019.
[12] Bassily, V. Feldman, K. Talwar, and A. G. Thakurta. Private stochastic convex optimization with optimal rates. In NeurlPS, pages 1129--11289 2019.
[13] A. Beimel, K. Nissim, and U. Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. ToC, 12(1):1661, 2016.
[14] O. Bousquet, S. Boucheron, and G. Lugosi. Introduction to statistical learning theory. In Summer School Machine Learning, pages 169-207. Springer, 2003.
[15] Z. Bu, Dong, Q. Long, and W. Su. Deep learning with Gaussian differential privacy. Harvard Data Science Review, 2020(23), 2020.
[16] M. Caron, H. Touvron, I. Misra, H. Jégou, J. Mairal, P. Bojanowski, and A. Joulin. Emerging properties in self-supervised vision transformers.
N0w:2104.14299, 2021.
[17] T. H. Chan, E. Shi, and D. Song. Optimal lower bound for differentially private multi-party aggregation. In ESA, pages 277-288, 2012.
[18] Chaudhuri and D. Hsu. Sample complexity bounds for differentially private learning. In COLT, pages 155-186, 2011.
[19] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. JMLR, 12(3), 2011.
[20] C. Chen and J. Lee. Stochastic adaptive line search for differentially private optimization. In Big Data, pages 1011-1020, 2020.
[21] P. Chen, B. Liao, G. Chen, and S. Zhang. Understanding and utilizing deep neural networks trained with noisy labels. In ICML, pages 1062-1070, 2019.
[22] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. A simple framework for contrastive learning visual representations. In ICML, pages 1597-1607, 2020.
[23] T. Chen, S. Kornblith, K. Swersky, M. Norouzi, and G. Hinton. Big self-superrised models are strong semi supervied learners. In NeurlPS, 2020.
[24] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In EUROCRYPT, pages 375-403, 2019.
[25] T. Clanuwat, M. Bober-Irizar, A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha. Deep learning for classical Japanese literature. arXiv:1812.0077 2018.
[26] F. Dangel, F. Kunstner, and P. Hennig. Backpack: Packing more into backprop. 19Xiv:1912.10900 2019.
[27] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, pages 248-255, 2009.
[28] T. DeVries and G. W. Taylor. Improved regularization of convolutional neural networks with cutout. arXiv:/708S 770.0455,, 2017.
[29] Ding, J. Kulkarni, and Yekhanin. Collecting telemetry data privately. In NIPS, pages 3571-3588 2017.

---

[30] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and minimax bounds: sharp rates for probability estimation. In NIPS, pages 1529-1537, 2013.
[31] J. Duchi, M. Jordan, and M. Wainwright. Minimax optimal procedures for locally private estimation. JASA, 113(521):182-201, 2018.
[32] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-40) 2014.
[33] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486-503, 2006.
[34] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
[35] U. Erlingsson, V. Pihur, and A. Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In CCS, pages 1054-1067, 2014.
[36] Ú. Erlingsson, V. Feldman. I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta. Amplifi- cation by shuffling: From local to central differential privacy via anonymity, In SODA, pages 2019.
[37] H. Esfandiari, V. Mirrokni, U. Syed, and S. Vassilvitskii. Label differential privacy via clustering. arXiv:2110.02159, 2021.
[38] A. Eyfimievski, J. Gehrke, and R. Srikant. Limiting privacy breaches in privacy preserving data mining. In PODS, pages 211-222, 2003.
[39] V. Feldman and T. Zmic. Individual privacy accounting via Rényi filter. arXiv:2008. 1993, 2020.
[40] V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Optimal rates in linear time. In STOC, page 439
439944444444 449,4499944 2020.
[41] Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maiimizing privacy mechanisms. SICOMP, 41(6):1673-1693 2012.
[42] I. Goodffllow. Efficient per-example gradient computations.
[43] A. Greenberg. Apple's "differential privacy" is about collecting your data but not your data. Wired, June, 13, 2016.
[44] J.-B. Grill, F. Strub, F. Altché, C. Tallec, H. Richemond, E. Buchatskaya, C. Doersch, B. A. Pires, Z. D. Guo, M. G. Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. In NeurIPS, 2020.
[45] A. Gupta, K. Ligett, F. McSherry, A. Roth, and K. Talwar. Differentially private combinatorial optimization. In SODA, pages 1106-1125, 2010.
[46] B. Han, Q. Yao, X. Yu, G. Niu, M. Xu, W. Hu, I. Tsang, and M. Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurIPS, pages 8527-8537, 2018.
[47] B. Han, G. Niu, X. Yu, Q. Yao, M. Xu, I. W. Tsang, and M. Sugiyama. Sigua: Forgetting may make learning with noisy labels more robust. In ICML, pages 4006-4016 2020.
[48] M. Hardt and K. Talwar, On the geometry of differential privacy. In STOC, pages 705-714, 2010.
[49] F. M. Harper and J. Konstan. The MovieLens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), 2015.
[50] H. Harutyunyan, K. Reing, G. V. Steeg, and A. Galstyan. Improving generalization by controlling label-noise information in neural network weights. In ICMI., pages 4071-4081, 2020.
12

---

[51] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[52] He, X. Zhang. S. Ren, and Sun, Identity mappings in deep residual networks. ECCV, pages 630 645,645,,25 2016.
[53] K. He. H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pages 9729-9738, 2020.
[54] X. He, L. Liao, Zhang, L. Nie, X. Hu, and T.-S. Chua. Neural collaborative filtering. In WWW, pages 173-182, 2017.
[55] W. Hu, Z. Li, and D. Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. JCLR, 2020.
[56] L. Jiang, D. Huang, M. Liu, and W. Yang. Beyond synthetic noise: Deep learning on controlled noisy labels. In ICML, pages 4804-4815, 2020.
[57] P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy. In ICML, pages 2436-2444 2016.
[58] S. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SICOMP, 40(3):93-28 2011.
[59] D. Kifer, A. Smith, and A. Thakurta. Private convex empirical risk minimization and high- dimensional regression. In COLT, pages 25.1-25.40, 2012.
[60] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical Report TR-2009, University of Toronto, 2009.
[61] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):2278-2324 1998.
[62] M. Ledoux and M. Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer Science & Business Media, 2013.
[63] T. Liu, G. Vietri, T. Steinke, J. Ullman, and Z. S. Wu. Leveraging public data for practical private query release. In ICMI., 2021.
[64] M. Lukasik, S. Bhojanapalli, A. K. Menon, and S. Kumar. Does label smoothing mitigate label noise? In ICML, pages 6448-6458, 2020.
[65] X. Ma, H. Huang, Y. Wang. S. Romano, S. Erfani, and J. Bailey. Normalized loss functions for deep learning with noisy labels. In ICML, pages
2020.
[66] M. Malek, I. Mironov, K. Prasad, I. Shilov, and F. Tramèr. Antipodes of label differential privacy: PATE and ALIBI. In NeurIPS, 2021.
[67] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang. Learning differentially private recurrent language models. In ICLR, 2018.
[68] F. McSherry. Privacy integrated queries: extensible platform for privacy data analysis. CACM, 53(9):89-97, 2010.
[69] K. Menon, A. S. Rawat, S. J. Reddi, and S. Kumar. Can gradient clipping mitigate label noise? In ICLR, 2019.
[70] M. Nalpas and S. Dutton. A more private way to measure ad conversions, the Event Con- version Measurement API, October 2020. http::://ebb..eecccceerrsoooomm
[71] M. Nasr, R. Shokri, et al. Improving deep learning with differential privacy using gradient encoding and denoising. arXiv:2007.11524 2020.
[72] Natarajan, I. Dhillon, P. Ravikumar, and A. Tewari. Learning with noisy labels. In NIPS, volume 26, pages 1204, 2013.
13

---

[73] S. Nemiirvskk and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, Chichester, 1983.
[74] D. T. Nguyen, C. K. Mummadi, T. N. Ngo, T. H. P. N.Nuynn, L. Beggel, and T. Brox, Self: Learning to filter noisy labels with self-ensembling. In /CLR, 2019.
[75] N. Papernot, M. Abadi, U. Erlingsson, I. Goodfellow, and K. Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In ICLR, 2017.
[76] N. Papernot, Song, I. Mironov, A. Raghunathan, K. Talwar, and U. Erlingsson. Scalable private learning with PATE. In ICLR, 2018.
[77] N. Papernot, A. Thakurta, S. Song, S. Chien, and U. Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. In AAAI, 2021.
[78] H. Phan, M. T. Thai, H. Hu, R. Jin, T. Sun, and D. Dou. Scalable differential privacy with certified robustness in adversarial learning. In ICML, pages 7683-7694, 2020.
[79] G. Pleiss, T. Zhang, E. R. Elenberg, and K. Q. Weinberger. Identifying mislabeled data using the area under the margin ranking. In ICML, 2020.
[80] C. Radebaugh and U. Erlingsson. Introducing TensorFlow Privacy: Learning with Differential Privacy for Training Data, March 2019. blog. tensorflow.org
[81] O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In ICMI., page 1-71-1-79, 2013.
[82] S. Shankland. How Google tricks itself to protect Chrome user privacy. CNET, October, 2014.
[83] R. Shokri and V. Shmatikov. Privacy-preserving deep learning. In CCS, pages 1310-1321, 2015.
[84] M. T. Smith, M. A. Álvarez, M. Zwiessele, and N. Lawrence. Differentially private regression with Gaussian processes. In AISTATS, 2018
[85] M. T. Smith, M. A. Álvarez, and N. Lawrence. Differentially private regression and classifica- tion with sparse Gaussian processes. arXi::1909.09147 2019.
[86] H. Song, M. Kim, D. Park, and J.-G. Lee. Prestopping: How does early stopping help generalization against label noise? arXiv: 19110809, 2019.
[87] H. Song, M. Kim, D. Park, and J.-G. Lee. Learning from noisy labels with deep neural networks: A survey. arXiv:2007.08/99 2020.
[88] S. Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with differentially private updates. In GlobalSIP, pages 245-248, 2013.
[89] T. Steinke and J. Ullman. Between pure and approximate differential privacy. J. Priv. Confi- dentiality, 7(2), 2016.
[90] P. Subramani, N. Vadivelu, and G. Kamath. Enabling fast differentially private SGD via just-in-time compilation and vectorization. In PPML, 2020.
[91] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In CVPR, pages 1-9, 2015.
[92] D. Testuggine and I. Mironov. PyTorch Differential Privacy Series Part 1: DP-SGD Algorithm Explained, August 2020. Indiumm com
[93] F. Tramèr and D. Boneh. Differentially private learning needs better features (or much more data). In ICLR, 2021.
[94] D. Wang and Xu. On sparse linear regression in the local differential privacy model. In ICML, pages
2019.
14

---

[95] D. Wang, M. Ye, and J. Xu. Differentially private empirical risk minimization revisited: Faster and more general. In NIPS, pages 2719-2728, 2017.
[96] S. L. Warner. Randomized response: survey technique for eliminating evasive answer bias. JASA, 60(309):63-6,, 1965.
[97] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. orXiv:/708.07:: 2017.
[98] L. Yu, L. Liu, C. Pu, M. E. Gursoy, and S. Truex. Differentially private model publishing for deep learning. In S P. pages 332-349, 2019.
[99] Yu, Han, J. Yao, G. Niu, I. W. Tsang, and M. Sugiyama. How does disagreement help generalization against label corruption? In ICML, pages 7164-7173, 2019.
[100] S. Yuan, M. Shen, I. Mironov, and A. C. Nascimento. Practical, label private deep learning training based on secure multiparty computation and differential privacy. Cryptology ePrint Archive, 2021.
[101] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz. Mixup: Beyond empirical risk minimization. ICLR, 2018.
[102] J. Zhang, Z. Zhang, X. Xiao, Y. Yang, and M. Winslett. Functional mechanism: regression analysis under differential privacy. VLDB, 1367)1136--1355, 2012.
[103] J. Zhang, K. Zheng, W. Mou, and L. Wang. Efficient private ERM for smooth objectives. In IJCAI, pages 3922-3928, 2017.
[104] Z. Zhang and M. Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In NeurlPS, pages 8778-8788, 2018.
[105] S. Zheng, Wu, A. Goswami, M. Goswami, D. Metaxas, and C. Chen. Error-bounded correction of noisy labels. In ICML, pages 11447-11457, 2020.
15


Reviews:
[{"review_id": "vBEUh3khnha", "reviewer": "Reviewer_cLnW", "summary": "This paper studies a Randomized Response algorithm with prior (RRwithPrior), which takes as input a label y, a prior distribution p on the possible labels [K], and outputs a randomized label aiming to maximize the probability that the output is y, while preserving epsilon-DP. The first claim of the paper is that the proposed algorithm is optimal among all epsilon-DP algorithms, given that the label y is actually distributed according to the prior distribution p. This is proven by arguing that RRwithPrior gives the optimal solution to a Linear Program that models this problem. \n\nThen, the authors use the RRwithPrior algorithm as a subroutine to LP-MST, a multi-stage algorithm for training NNs with label differential privacy (LabelDP). LabelDP is a weaker notion of privacy where neighboring data sets differ on the label of a single example. The algorithm proceeds in stages, in each of which a model is trained on disjoint partitions of the dataset and the private labels are protected using RRwithPrior. An important thing to note is that LP-MST does not require a prior and is essentially boosting the prior that RRwtihPrior uses: it starts with the uniform distribution over all [K] classes, then labels the first batch of examples according to RRwithPrior with this uniform prior and moves to the next stage using the new model as a prior. LP-MST with one stage (called LP-1ST) is equivalent to Randomized Response (without prior). The performance of the epsilon-LabelDP model output by variations of LP-MST is empirically evaluated against other methods, demonstrating increased accuracy. The authors also experiment with new advances in self-supervised learning to retrieve useful priors.\n\n\nThe above are the main contributions of the paper, but this work also includes a study of SGD with LabelDP. The authors give a version of SGD with Randomized Response which satisfies epsilon-LabelDP and achieves a excess true risk in the order of K/(epsilon*sqrt(n)), hiding the dependence on the diameter of the parameter space and the Lipschitz constant. They also give a (not very tightly matching) lower bound of 1/\\sqrt(epsilon*n). They extend the study to (epsilon, delta)-LabelDP, saving a sqrt(K) factor from the upper bound. The lower bound above works for (epsilon, delta)-LabelDP as well so in this case the gap between the two is smaller. In the process of deriving the lower bound, the authors give lower bounds on the empirical loss and give an extension of a known reduction from private SCO to private ERM from Bassily et al. to the case of LabelDP. They finally consider a slightly different algorithm and give bounds that depend on the quality of the priors.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n- RRwithPrior seems to be a simple primitive which could be useful in several settings (e.g. as a building block as in the current paper) and this paper gives a clean analysis of its guarantees.\n- For cases when label DP is appropriate, this approach seems to give a significant empirical performance boost compared to the stricter DP guarantee, making it potentially much more useful in practice.\n- Although theoretical results in the paper depend on the assumption that the labels are indeed drawn from the known prior p, experiments with different priors show that in practice the approach is more robust. In the case of SCO, the authors give bounds that depend on the quality of the prior.\n\nWeakness:\n- I found it a bit hard to extract a main story from the paper. But I think that this is partly due to the fact that it includes a lot of results in an effort to study LabelDP and NN from many perspectives.\n\n*Score justification*:\nI think that overall this paper aims to do an extensive study, both theoretical and experimental, of the perks of LabelDP for NN, and it manages to demonstrate its usefulness.\n\n*Detailed comments/typos*:\n- It might be more convincing to motivate the use of priors with examples, as is done for LabelDP in the introduction, and add these to the sentence “In many real world applications, a prior distribution about the labels could be publicly obtained from domain knowledge and help the learning process”.\n- lines 183+184: I was not sure what the proof referred to, because I did not expect an observation to have a proof, so it might be useful to indicate it. Also in the first line of the proof, shouldn’t that be epsilon-LabelDP\n- Theorem 9: right bracket missing\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think that there is a point that could be stressed more: making the distinction between cases where features+labels vs just labels should be protected is crucial. I think that the (weaker) type of privacy that is guaranteed by these methods should be made clear to the practitioners who might use these methods for their good accuracy.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "s1gxBB-zhf", "reviewer": "Reviewer_CTDz", "summary": "This paper proposes the Randomized Response with Prior algorithm and then uses it as a preprocessing step to learn neural networks with label differential privacy. It shows the RRWithPrior algorithm is optimal in privatizing a label. It also provides extensive experimental results to show that labelDP is easier than protecting both the inputs and labels. Finally, it gives theoretical analysis to understand this phenomenon to the stochastic conveys optimization setting. ", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is well-written and easy to follow. Somehow, I felt the technical contribution is not strong enough. I've listed my main comments below.\n\n1. I think in most applications, we are more interested in protecting the features rather than the label. I would suggest the authors provide some real applications as motivating examples.\n\n2. Intuitively, LabelDP is much easier than protecting the entire individual record, so the LP-MST with other DP methods are not comparable. It's worth showing the accuracy is much better, but it's far from surprising.\n\n3. I found the claim regarding Theorem 3 is a bit overly strong. R is just any \\eps-DP algorithm when just randomizing a single label. (Just curious, is it possible that the RRWithPrior is equivalent to the exponential mechanism with properly defined score functions?)\n\n4. If K is large, will the running time be too long?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper provides several open questions in the conclusions section. I would suggest the authors to add more discussion on the limitations. I don't see any negative societal impact of this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "j8IwVYKxy3M", "reviewer": "Reviewer_De6X", "summary": "The paper introduces a Randomized response (RR) concept to provide more accurate results at the same level of privacy protection of LabelDP. The method can be incorporated into LP-MST and SSL frameworks to improve model performance. To achieve that, the authors propose RRWithPrior, which maximizes the probability that the output label is correct, and a novel LP-MST for training deep neural networks with LabelDP and RRWithPrior. They show formal proof of optimality of RRWithPrior and some open research questions. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Originality: The work is a novel combination of well-known techniques. The LabelDP is built on k-ary RR [Kairouz et al., 2016]. The method has not been evaluated with other privacy protection for labels, such as using Gaussian noise [1] or Laplace noise [2], or Functional mechanism [3].\n[1] Wang, D., & Xu, J. (2019, May). On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning (pp. 6628-6637). PMLR.\n[2] Phan, H., Thai, M. T., Hu, H., Jin, R., Sun, T., & Dou, D. (2020, November). Scalable differential privacy with certified robustness in adversarial learning. In International Conference on Machine Learning (pp. 7683-7694). PMLR.\n[3] Zhang, J., Zhang, Z., Xiao, X., Yang, Y., & Winslett, M. (2012). Functional mechanism: regression analysis under differential privacy. arXiv preprint arXiv:1208.0219.\n\nQuality: The submission is technically sound and well supported by theoretical analysis and experiments. \nDoes the LP-MST currently work with non-interactive settings in local DP models? In which setting it works currently: centralized setting or federated setting? It seems to me that this is applied to local models, which are under the federated setting. But in that case, how can authors partition the dataset S into subsets and learn the model M in Algorithm 3.\n\nClarity: It is well-organized and has enough information to reproduce the results. \nThe self-supervised learning (SSL) framework looks interesting but not well-motivated in the main body from the beginning. \n\nSignificance: The results are interesting, and others can use the ideas.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work does not have a negative societal impact that needs to be addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "YKvTFGtC71K", "reviewer": "Reviewer_Jhzq", "summary": "This study considers the label differential private training of the classification model with DNN.  The basic idea is the randomized response, while the labels with top-k prior probabilities are returned when labels are randomized. Furthermore, given a prior label distribution, the proposed scheme can choose k adaptively so that the probability that the input label is returned by the mechanism is maximized. The proposed mechanism is proved to be optimal in the sense that the probability that the input label is returned by the mechanism is equal or greater than any label-DP mechanism. \n\nIn application to model training, the authors proposed a multi-stage strategy. Splitting the training data into several subsets and starting from the uniform label prior distribution, it gradually updates the label prior used for the mechanism. The performance of the presented mechanism is demonstrated with CIFAR10 and movie lens dataset with comparison to DP-SGD and its variants. The results show that the classification performance of their label-DP mechanism is significantly better than the existing DNN model with differential privacy. \n\n \n\n\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The story and contribution are clear. The reviewer would like to consider the following issues in revision:\n\n(1) The proposed mechanism is label-DP while the comparison methods are regular DP. So direct comparison is not fair. The discussion section should be revised considering this point.\n\n(2) In Theorem 5, the authors proved that the excess population loss is independent on the dimension of the parameter space, which would be greatly advantageous in the training of DNN. Is it possible to demonstrate this effect experimentally?\n\n(3) In Collolary 6, a probability is contained in the complexity, which looks weird. I understand that this is an informal version of the theorem, but I think some remarks on this point should be contained in the main body to clarify why this term is contained in O().\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I could not find any paragraphs that mention the limitations and societal impact of this study.\nSince the proposed scheme basically improves privacy, it would have a good social impact. However, differently from regular DP, the coverage of label DP is more restricted compared to regular DP. So it would be nice to explain in what situations label-DP is sufficient for privacy protection.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an algorithm for learning ML models under label DP. While label DP provides weaker protection than regular DP, the authors make a convincing case that it may be sufficient for certain applications. The paper demonstrates that cleverly exploiting label DP allows significant increase in model utility compared to learning under full DP.

The reviews are divided with two reviewers recommending acceptance and two recommending rejection. However, the main arguments for rejection seem to be based on dismissal of label DP as a valid topic of research without clear supporting evidence.

As a result, I tend to recommend acceptance as the paper seems to yield significant improvements for a problem with at least some practical relevance.

While the paper includes very extensive bibliography, it seems that the authors have missed at least the following previous papers and methods for learning under label DP: "Differentially Private Regression with Gaussian Processes" and "Differentially Private Regression and Classification with Sparse Gaussian Processes".
Decision: Accept (Poster)