Antipodes of Label Differential Privacy: PATE and ALIBI
Authors: Mani Malek Esmaeili
Ilya Mironov
Karthik Prasad
Igor Shilov
Florian Tramer
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
label differential privacy
PATE
ALIBI
memorization attacks

Abstract: We consider the privacy-preserving machine learning (ML) setting where the trained model must satisfy differential privacy (DP) with respect to the labels of the training examples. We propose two novel approaches based on, respectively, the Laplace mechanism and the PATE framework, and demonstrate their effectiveness on standard benchmarks.

While recent work by Ghazi et al. proposed Label DP schemes based on a randomized response mechanism, we argue that additive Laplace noise coupled with Bayesian inference (ALIBI) is a better fit for typical ML tasks. Moreover, we show how to achieve very strong privacy levels in some regimes, with our adaptation of the PATE framework that builds on recent advances in semi-supervised learning.

We complement theoretical analysis of our algorithms' privacy guarantees with empirical evaluation of their memorization properties. Our evaluation suggests that comparing different algorithms according to their provable DP guarantees can be misleading and favor a less private algorithm with a tighter analysis.

Code for implementation of algorithms and memorization attacks is available from https://github.com/facebookresearch/label_dp_antipodes.

Antipodes of Label Differential Privacy: PATE and ALIBI
Mani Malek
Iya Mironov
Karthik Prasad"
Igor Shilov*
Florian Tramèr'
Abstract
We consider the crivacy-preservie machine learning (ML) setting where the trained model must satisfy differential privacy (DP) with respect to the labels of the training examples. We propose two novel approaches based on, respectively, the Laplace mechanism and the PATE framework, and demonstrate their effectiveness on standard benchmarks.
While recent work by Ghazi et al. proposed Label DP schemes based on domized response mechanism, we argue that additive Laplace noise coupled with Bayesian inference (ALIBI) is better fit for typical ML tasks. Moreover, show how to achieve very strong privacy levels in some regimes, with our adaptation the PATE framework that builds recent advances in semi-supervised learning.
We complement theoretical analysis of algorithms' privacy guarantees with empirical evaluation of their memorization properties. Our evaluation suggests that comparing different algorithms according to their provable DP guarantees can be misleading and favor less private algorithm with a tighter analysis.
Code for implementation of algorithms and memorization attacks is available from htap::////tthan wwt.cc/oooorrrerrrraaaaall.....p antipodes
Introduction
Sophisticated machine learning models perform well on their target tasks despite of-or thanks to to-their predilection for data memorization [39 17 When such models are trained on non-public
inputs, privacy concerns become paramount 31 6 which motivates the actively developing area
of privacy-pren privacy-rreeevvng machine learning.
With some notable exceptions, which we discuss in the related works section, existing research has focused on "all nothing" privacy definition, where all of the training data, i.e. both both features and labels, is considered private information. While this goal is appropriate for many applications, there are several important scenarios where label-only privacy is the right solution concept.
prominent example of label-only privacy is in online advertising, where the goal to predict conversion of an ad impression (the label) given user's profile and the spot's context (the features). The features are available to the advertising network, which trains the model, while the labels (data on past conversion events) visible only to the advertiser. More generally, any two-party setting where data is vertically split between public inputs and (sensitive) outcomes is a candidate for training with label-only privacy.
In this work we adopt the definition of differential privacy as our primary notion of privacy. The defi- nition, introduced in the seminal work by Dwork et al. (13). satisfies several important properties that make it well-suited for applications: composability, robustness to auxiliary information, preservation under protesroces,,ng, and graceful degradation in the presence of correlated inputs (group privacy). Following Ghazi et al. [18]. we refer to the setting of label-only differential privacy as Label DP.
(manimalek,, imironov, shilov)@0) com, Facebook AL.
'tramerecs. Cramer@cs.stanford swwanordddd...... edu, Stanford University.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Our contributions. We explore two spproaches-wine very different characteristics--tovv Label DP. These approaches and our methodology for estimating empirical privacy loss via label memorization are briefly reviewed below:
PATE: We adapt the PATE framework (Private Aggregation of Teacher Ensembles) of Papernot et al. (28) to the Label DP setting by observing that PATE's central assumption- availability of public unlabeled dataset-can be satisfied for free. Indeed, a public unlabeled dataset is simply the private dataset with the labels removed! By instantiating PATE with a state-of satte-of-theaare art technique for sumi-supervised learning, we demonstrate an excellent tradeoff between empirical privacy loss and accuracy.
ALIBI (Additive Laplace with Iterative Bayesian Inference): We propose applying additive Laplace noise to one-hot encoding of the label. Since differential privacy is preserved under prot-proesssing. we can de-noise the mechanism's ' output by performing Bayesian inference using the prior provided by the model itself, doing so continuously during the training process. ALIBI improves, particularly in high-privacy regime, Ghazi et al.'s approach based randomized response [18]
Empirical privacy loss. We describe a memorization attack targeted at the Label DP scenario that efficiently extracts lower bounds for the privacy parameter that, in some cases, come within a factor of 2.5 from the theoretical, worst-case upper bounds against practically relevant, large-scale models. For comparison, recent, most advanced black-box box attacks on DP-SGD have approximately a 10x gap between the upper and lower bounds 26).
Both algorithms, PATE and ALIBI, come with rigorous privacy analyses that, for any fixed setting of parameters, result in an (c, 8)-DP bound. We emphasize that these bounds are just that that-they are upper limits on an attacker's is ability to breach privacy (in a precise sense) on worst-case inputs. Even though these bounds can be pessimistic, intuitively, a smaller e for the same corresponds to a more private instantiation of a mechanism, and indeed this is likely the case within an algorithmic family.
Can the privacy upper bounds be used compare diverse mechanisms with widely dissimilar analyses, such as ours? We argue that focusing on the upper bounds alone may be misleading to the point of favoring less private algorithm with tighter analysis over a more private one whose privacy analysis is less developed. For a uniform perspective, we estimate the empirical privacy loss of all trained
models by evaluating the performance of a black-box membership inference attack (31 20 26).
Our attack directly measures memorization of deliberately mislabeled examples, or canaries (6] Following prior work (26] 20]. we the success rate of our attack to compute lower bound on the level e of label-DP achieved by the training algorithm. To avoid the prohibitive cost of retraining a model for each canary, we propose and analyze a heuristic that consists in inserting multiple canaries into one model, and measuring an attacker's s success rate in guessing each canary's 's label. In some settings, we find that the empirical privacy of PATE (as measured by our attack) is significantly stronger than that of ALIBI, even though the provable DP bound for PATE is much weaker.
Finally, to characterize setups where label-only privacy may be applicable, it is helpful to distinguish between inference tasks, where the label is fully determined by the features, and prediction, where there is some uncertainty to the eventual outcome, despite (hopefully) some predictive value of the feature set. We are mostly concerned with the latter scenario, where the outcome is not evident from the features, or protecting choices made by individuals may be mandated or desirable (for connection between privacy and self-determination see Schwartz (30)). While we do use public data sets (CIFAR-IO 10 and CIFAR-100) in which it is possible "infer" the label, we do so only to evaluate our approaches on standard benchmarks. We completely remove the triviality of inference by adding mislabeled canaries in our attack, thereby introducing a measure of non-determinism.
2 Notation and Definitions
Throughout the paper we consider standard supervised learning problems. The inputs are (a, pairs where x E X are the features and y E Y are the labels. (If some labels are absent, the problem becomes semi-supervised learning.) The cardinality of the set Y is the number of classes C. The task to learn model M parameterized with weights W that predicts y given x. To this end the training algorithm has access to a training set of n samples (z v.)
2

---

Differential privacy due to Dwork et al. [13 is rigorous, quantifiable notion of individual privacy for statistical algorithms. (See Dwork and Roth [14] and Vadhan (33) for book-length introductions.)
Definition 2.1 (Differential Privacy). We say that randomized mechanism M: U - R satisfies (E. 6) differeenia privacy (DP) for all adjacent inputs D, D' E U that differ in contributions of single sample, the following holds:
VS C Pr(M(D) E S -P((M(D)) ES] +
If 8 0, we refer to it as c-DP.
The notion of adjacency between databases D and D' is domain- and application-dependen. To instantiate the Label DP setting, say that D and D' are adjacent if they consist of the same number of examples {(r,, y:) and are identical except for difference in a single label at index i": (1-) D and (t-) D'.
3 Background and related work
DP and machine learning. Differential privacy aligns extremely well with the goal of machine learning, which is produce valid models or hypotheses the basis of observed data. In fact, the relationship can be made precise. An important metric in ML is generalization error, which measures the model's performance on previously unseen samples. Differentially private mechanisms provably generalize (IT]. For an introduction to some important early results on connections between differential privacy and learning theory see Dwork and Roth [14 Chapter 11].
Randomized response (RR). As a disclosure avoidance methodology, randomized response (RR) (36] precedes the advent of differential privacy. In RR's basic form, with some probabil- ity the sensitive input is replaced by a sample drawn uniformly from its entire domain. RR can be implemented at the source, making it essential building block in achieving Local DP (16).
More generally, RR an instance of the input perturbation technique, which leaves the ML training algorithm intact and achieves differential privacy via input randomization. Input perturbations methods are particularly friendly to implementers as they require minimal changes to existing algorithms, treating them as black boxes.
Additive noise mechanisms. Another important class of differentially private mechanisms are additive noise methods. Two canonical examples are additive Laplace [13) and additive Gaussian [12] that can be applied to vector-valued functions. Their noise distributions are calibrated the function sensitivity the maximal distance between the function's 's outputs on adjacent inputs (D and D' in
Definition 2.1 under the ε or & metrics for the Laplace and Gaussian mechanisms respectively.
PATE. Private Aggregation of Teacher Ensembles (PATE) 28 29 is a framework based on private knowledge aggregation of ensemble model and knowledge transfer. PATE trains ensemble of "teachers" on disjoint subsets of the private dataset. The ensemble's 's knowledge is then transferred "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
interface.
Since PATE consumes the privacy budget each time the student queries the teachers, the training algorithm must be optimized to minimize the number of queries. To this end, Papernot et al. explore the use of semi-supervised learning techniques, most notably GANs. Recent advances in semi- supervised learning have been shown to boost the performance of PATE standard benchmarks (5)
FixMatch. FixMatch (32 is a of-te-of-thh-rr semi- cemi-superyised learning algorithm, which achieves high accuracy benchmark image datasets with very few labeled examples. It is based on the concepts of pscudo-labeling [23] and consistency regularization [3]: FixMatch uses a partially trained model to generate labels weakly-augmented unlabeled data, and then, if the prediction is confident enough, uses the output as a label for the -aggge-d version of the same data point.
Label-only privacy. The setting of label-only DP was formally introduced by Chaudhuri and Hsu (8). who proved lower bounds on sample complexity for private PAC-learners. Beimel et al. 4 demonstrated that the sample complexity of Label DP matches that of non-private PAC learning (ignoring constants, dependencies on the privacy parameters, and computational efficiency). Wang and Xu 34) considered the linear regression problem in the local, label-only privacy setting.

---

Most recently, Ghazi et al. (18) considered label-only privacy for deep learning. They propose a Label Privacy Multi-Stage Training (LP-MST) algorithm, which we revisit in Section [5] The algorithm advances in stages (Ghazi et al. evaluate it up to four), training the model on disjoint partitions of the dataset. each stage, the private labels are protected using a randomized response scheme.
The most innovative part of LP-MST happens at the point of transition between stages. Labels of the training examples of the next partition are perturbed using randomized response. The (soft) output of the previous stage's 's model is interpreted as prior, which is used to choose parameters for the randomized response algorithm separately for each example. For instance, if the current model assigns high probabilities to labels 1-10 and low probabilities to labels 1 11-100, the randomized response will be constrained to outputting a label within the set 1-10.
We build on the insights of Ghazi et al. by making two observations. First, training algorithms used naturally handle soft labels (i.e., probability
for deep learning (such SGD and its variants) distributions over the lahel space); there is thus no need to force hard labels by sampling from the posterior. Second, by applying additive noise, we can repeatedly recompute the posterior distribution as better priors become available without consuming privacy budget. By following the "once and done" approach to label perturbation, we forgo the need split training into disjoint stages.
To summarize, Ghazi et al. fix the prior at the beginning of the stage, choose parameters of the randomized response algorithm perturbed label. We flip the order of these operations by applying a DP mechanism (additive Laplace) first, and then repeatedly use Bayesian inference by combining the prior that changes with each model update and the observables that do not.
the basis of this prior, and update the model by feeding it the
To our knowledge, we are the first to explore connections between PATE and Label DP.
4 PATE with Semi-Supervised Learning
The PATE framework (28) splits the learning procedure into two stages. First, T teachers are trained on disjoint partitions of the private dataset. Second, student acquires labels for training its own model by querying the teacher ensemble on samples drawn from public (non-sensitive) unlabeled dataset. Differential privacy is enforced at the interface between the student and the teachers, by means of a private aggregation of the teachers' votes.
The critical observation underlying the PATE privacy analysis is that a private sample taints at most one teacher due to disjointedness of the teachers' training sets. The voting mechanism bounds the maximal impact of single teacher's ' votes across all student queries by injecting noise in each voting instance. (We use the Confident Gaussian aggregation mechanism and its analysis from (29).
The Label DP setting allows for unrestricted use of the features. We leverage this capability for training both teachers and the student:
The unlabeled examples on which the student queries the teacher ensemble are random samples from the dataset without labels. All models-the the teachers and the are trained with the FixMatch algorithm that uses (few) labeled examples and has access to the entirety of the original dataset as the supplementary unlabeled data.
adapt Algorithms and adapt PATE to the Label DP setting. To draw a distinction between the PATE framework, which is generic and black-box, and its instantiation with the FixMatch algorithm for semi-supervised learning, we refer to the latter as PATE-FM.
The PATE framework does not require the student and the teacher models to have identical architecture. or share hyperparameters. In our experience, however, the optimal privacy/accuracy trade-off's force very similar choices on these models.
The selection of the number of teachers, T, balances two competing objectives. On the one hand, each teacher has access n labeled and unlabeled examples, which means that smaller T corresponds to higher accuracy teacher models (due to more labeled examples per teacher). On the other hand, larger T allows for a higher level of noise and lower privacy budget per query.
similar dynamic controls K, the number of labels requested by the student. A higher number allows for more accurate training but inflates the privacy budget.

---

1: PATE-FM. www.ianneaaeeerneeebbi..a Aa
Input: Dataset D <- {z11 yI),..., (I B. number of teachers T,, training procedure basMatch(labbeled data, unlabeled_dan
Define the unlabeled part of D: D + f InF
Partition D into T equal-sized disjoint subsets D D(T)
for i f 1 to T do teacher, + FixMatch(D(().. ,
end
Output: Model ensemble [teacher I.... teacherr)
Algorithm PATE-FM. TrainStudent
Input: Dataset D (z1 (Z11 .i,,..., (Ins Bn)}. number of label classes C, number of teachers T, training procedure DixMMacch(laaelle data, unlabeled .atbbelledddta),. number of student samples K, noise parameters 01, 02, voting threshold
Define the unlabeled part of D: D + (Z1....,,n) In
Initialize student dataset Ds f teacheri...... ....... teacherr } TreiaTTacchrrSneeebbl(.....11 while [Ds] < do random sample from D
for i < to C. do // tallying up the votes 12 [j: teachery (x) 1}
end
max; +OO, ) 2 then y 4 argmaxx [w; + (0, o
Ds + Ds U {x,
end end
student FixMatch(Ds.. D
Output: Model student
Boosting teachers' accuracy for a given number of labels and minimizing the number of student queries and their privacy costs are key to producing high utility models with strong privacy guarantees. To this end, we use the state-of-the-an algorithm for semi-supervised learning FixMatch (32].
The FixMatch algorithm's primary domain is image classification: in addition labelled and unlabelled examples, it assumes access to a pair of weak and strong data augmentation algorithms. The loss function of FixMatch is weighted sum of two losses that enforce consistency of the model's prediction (i) between labeled examples and their weakly augmented versions, and (ii) between weakly and strongly augmented unlabeled images (restricted high-confidence instances).
5 ALIBI: Additive Laplace with Iterative Bayesian Inference
We describe the general approach of Soft Randomized Response with post-processing and its concrete instantiation, ALIBI.
5.1 Soft Randomized Response
Consider the application of Randomized Response (RR) to the setting of Label DP. In its standard form, the random perturbation maps labels to labels, i.e., the label either retains its value with probability or assumes a random value with probability -pp
We deviate from RR by replacing label randomization with a differentially private mechanism applied to one-hot encoding of the training sample label; we refer to this mechanism as Soft Randomized Response (Soft-RR). By retaining more information (without significantly impacting privacy analysis), we support several possible post-processing algorithms (Section 5.2) Additionally, we argue that Soft-RR performs better than RR in practice since it does not force wrong hard labels.

---

Algorithm 3: Additive Laplace with Iterative Bayesian Inference, ALIBI
Input: Dataset D {(111 ......... (Ins
Vn)]. noise parameter X, Bayesian post-processing
mechanism BPP o, A, prior) defined in Eq. (3), optimizer Update(model, model, imput, (oft__abels)
Initialize noised dataset D +- 01
for f to n do // noising labels
< OneHot(y,) (1:) Laplace(A)
D - D" D' ((,,, ((z,,
end
Randomly initialize model M repeat
for (z, o) in D* do
pred - (xx)
post < BPP(o, A. pred)
M + Update(M, x, post)
end until convergence;
Output: Model M
Following standard analysis (Dwork and Roth [1 Chapter 3.3]), e-DP can be achieved with additive Laplace noise with per-coordinate standard deviation 2/2/e. Analogously, Gaussian noise sampled from (0, Ic) results in (c, 6) if 22 and E, 8 < 1 ((14 Appendix A)).
5.2 Post-processing of Soft Randomized Response
The output of Soft-RR no longer a valid soft label rector-valuse are not necessarily constrained to the [0.1] interval and do not sum up to 1. Thankfully, the fundamental property of DP allows privacy preservation under post-p post-processing which we use to obtain a probability mass function on perturbed labels to de-noise the mechanism's output. Treating the noisy labels the observables, and X as the noise parameter, we can calculate the posterior p(y = e o, A) by Bayes' rule as:
p(o y c, c, ply c)
ply = c o, o,
Σn p(o = A) p(y k)
In the context of SGD, the current model's output can be interpreted prior probability distribution over the classes (p(y)).
ALIBI, or Additive Laplace with Iterative Bayesian Inference, is algorithm that applies Bayesian post-processing to the output of the Laplace mechanism (Algorithm 3p. With Laplace noise, the output of the mechanism for specific label is distributed as:
p y = k. A) x loN 1/A II
1o/1/A
(2)
Plugging 2 into we derive:
ply e o, A) SoftMax((foo)/A> + logp(y c)),
where f(oo)= - |o: -c k|| and [:] is the Iverson bracket.
At given privacy level, ALIBI empirically outperforms iterative Bayesian inference on additive Gaussian noise and naïve "uninformed" post-processing strategies, the details of which are deferred Section Dectionn((SSt (Spplemental materials).
Evaluation
The algorithms are evaluated by training the Wide-ResNet architecture [38 on the CIFAR-10 and CIFAR-100 datasets (22). The widening factor set to 4 and for CIFAR-10 and CIFAR-100 respectively. To facilitate comparison of privacy assured by the two approaches, we train our models

---

to achieve similar accuracy levels and provide the computed theoretical (s, 6) upper bound. (Ignoring the privacy costs of hyperparameter tuning and of reporting the test set performance. The former can be minimized, with a modest loss in accuracy, by applying the selection procedure of Liu and Talwar (24).) We also provide the empirical privacy loss lower bound, Em. as estimated by the black-box attacks (Section 7
PyTorch-based implementations of ALIBI, PATE-FM, and memorization attacks, including configu- ration options and hyperparameters, are publicly available T
6.1 PATE-FM
PATE-FM parameters are given in Table 3 (Supplemental materials). The student and the teacher models share the same architecture and are trained using Fix.Matc [32 21) with hyperparameters from Sohn et al. 32] (we use the RandAugment variant (9). The number of epochs is set so that the test accuracy reaches plateau: for CIFAR-10, 200 epochs; for CIFAR-100, we train both the teachers and the student for 125 epochs. To report privacy, we set 5 10-5 The student's accuracy is reported as the average of three runs (for fixed teacher ensemble).
train teachers for 40 epochs and the student for
There are several hyperparameters affecting privacy/utility trade-off in PATE: number of teachers, level of noise, voting threshold, and number labeled samples the student dataset. Apart from the expected dependencies (increasing noise and the number of teachers benefits privacy some accuracy cost), we observe the following:
The number of labeled student samples beyond a certain level (10-25 samples per class) has little effect on the eventual model accuracy. This contrast with the standard (non-private) FixMatch where increasing the number of labeled samples usually improves accuracy.
The voting threshold r needs be kept between 10% and 75% of the overall number of teachers. As pointed out in Papernot et al. [29). lack of consensus between teachers hurts both privacy and utility, as the teacher ensemble errs more often on such inputs and a single vote can have more impact the outcome. Setting the threshold too high leads to selection bias in training samples, forcing the student model to train only on the most trivial samples. Even in the zero-noise regime, the threshold above 75% considerably hurts the accuracy.
6.2 ALIBI
We use mini- batch SGD with a batch size of 128 and momentum of 0.9, We train all models for 200 epochs and pick the best checkpoint. We tune the learning rate, weight decay and noise multiplier to obtain the desired accuracy while minimizing privacy E (see Table i Supplemental materials). Since ALIBI is based on the Laplace mechanism, it achieves pure DP corresponding to 8 = 0.
6.3 Results
Table prreeents the privacy budget and the memorization metric at three levels of accuracy across our two approaches for the both datasets. Additionally, for ALIBI, we provide the results of a higher accuracy model on the CIFAR-100 task; this higher accuracy was not attainable with PATE-FM.
For correct comparison with LP-2ST on 100, we factor out modelling differences by applying both mechanisms to training the same to suit the task. Results are presented in Table 2 For reference, non-private baselines with this model achieve 2 95.5% on CIFAR-10 10 and 2 79% on CIFAR-100.
[19 25 with appropriate modifications
We note that there a significant difference in computational resources required to train with PATE-FM and ALIBI. The reasons are twofold. First, in our experiments, models trained in semi-supervised regime with few labeled examples take longer to converge. Second, PATE requires training the teacher ensemble, in which computational costs scale linearly with the size of the ensemble. Overall, this accounts for PATE-FM consuming 1,000-1,500x more computational resources (rP compared to ALIBI.
7

---

Table 1: Privacy of PATE-FM [28]
and ALIBI, on CIFAR-10 and CIFAR-100 using Wide- ResNet18, 8, matched by test accuracy levels. for PATE is at 10-6. Empirical privacy loss Em. is reported as a 95% confidence interval (CI).
32]
Dataset
Accuracy level
Algorithm
Accuracy
E
95%-CI Em
PATE-FM
93.7%
1.6
0.0-0.9
High
ALIBI
94.0%
8.0
2.9-4.0
PATE-FM
86.9%
0.29
0.0-0.6
CIFAR-10
Medium
ALIBI
84.2%
2.1
1.0-2.2
PATE-FM
73.4%
0.18
0.0-0.4
Low
ALIBI
71.0%
1.0
0.0-2.2
PATE-FM
Very High
ALIBI
75.3%
8.1
3.5 4.5
PATE-FM
69.9%
715
0,4-1.0
High
ALIBI
71.4%
6.3
2.8-3.5
CIFAR-100
PATE-FM
50.0%
16
0,2-0.7
Medium
ALIBI
51.6%
3.0
1.4-2.4
PATE-FM
30.5%
7.9
0,2-0.6
Low
ALIBI
31.4%
2.0
0.6-1.0
Table 2: Test accuracy of ALIBI and LP-2ST matched by
18
Table 4]. on CIFAR-100 applied to ResNet18,
Algorithm
= 3
8
=
5
=
6
ALIBI
55.0
65.0
69.0
71.5
74.4
LP-2ST
28.7
50.2
63.5
70.6
74.1
7 Measuring Memorization
We complement our evaluation with an empirical study the (label) memorization abilities of classifiers trained with PATE-FM and ALIBI. While we can derive provable upper-bounde the level of e-Label DP provided by both algorithms, a direct comparison between the (actual) privacy of both algorithms is challenging they rely very different privacy analyses. As will see, for CIFAR-100 PATE-FM empirically appears to provide much stronger privacy guarantees than ALIBI, though the privacy analysis suggests the opposite.
To empirically measure privacy loss, we effectively instantiate the implicit adversary in the DP definition 226 20 We construct two datasets D, D' that differ only in the label of one example, and train a model on one of these two datasets. We then build an attack that "guesses" which of the two datasets was used. The attacker's advantage lower bound on the mechanism's 's differential privacy. A formal treatment of memorization attacks using the framework of security games appears in Section B (Supplemental materials).
random guess can be used to derive empirical
We point out following differences between our approach and prior work. When providing lower bounds on privacy leakage, it is appropriate to consider the most powerful attacker pursuing the least challenging goal. the context of standard DP (privacy for labels and fcatures), it means an attacker that can add remove sample and seeks to determine whether the sample was part of the training dataset (i.c., membership inference (3I).. contrast, we operate within the constraints of Label DP, where the attacker's 's power is limited to manipulating single label and the goal is to infer which label was used during training. (The closest analogue is attribute inference (37].)
Prior work replicates a memorization experiment many times (e.g.. 1,000 times (26)) to lower bound with standard statistical tools 26 20). As this approach is prohibitively expensive in our setting (prior work computed DP lower bounds for simpler datasets such as MNIST), we introduce the following heuristic: we train single model on a training set with 1,000 labels randomly flipped to different class. For each of these "canaries"
[6] with (flipped) label y'. the attacker has to guess whether

---

correct guess
incorrect guess
correct guess
incorrect guess
Proportion
Proportion
10-10
108 10 10
100
Model confidence
Model confidence
(a) ALIBI (CIFAR-100, High)
(b) PATE-FM (CIFAR-100, High)
Figure I: Comparison of the adversary's success rates in guessing the label of inserted canaries with ALIBI and PATE-FM (for CIFAR-I00, 100, with High accuracy level). We sort canaries by the model's maximal confidence on the two labels y', y that the adversary has to guess from. The violin plots show the proportion of correct guesses (the model is more confident in the canary label) and incorrect guesses. To maximize the adversary's 's distinguishing power, we limit the adversary to only issuing guesses for canaries where the model's s confidence either y or y" is above 99% (zoomed-in box). ALIBI is clearly more vulnerable to the attack (i.e., it is easier for the adversary to guess a canary's 's label), even though its theoretical privacy analysis yields much lower bound on than for PATE-FM.
the canary's 's assigned label is y or y", where v" # y/ is a different random incorrect label. If the adversary has accuracy a in this guessing game, we can lower bound by 1 -log( As in prior work 26 20]. we compute a 95% confidence interval on the adversary's guessing accuracy a and thus on the level of privacy against our attack. We formally define our attacking game and analyze the relationship between the attacker's success and the privacy budget in Section (Supplemennal
materials).
To isolate the impact that can be attributed to the difference between privacy-preserving training procedures, apply ALIBI and PATE-FM to the same target model architecture and tune their privacy parameters to achieve similar accuracy levels. (For discussion of confounders, see Erlingsson et al. [15].) Furthermore, we deliberately limit memorization attacks to be traincr-agnostic, to avoid privileging, for instance, a more complex training procedure over a simpler one.
Our empirical estimates of the privacy loss Em are given in Table I The estimates for ALIBI are approximately within a factor of theoretical privacy analysis of ALIBI is close tight. On the other hand, for PATE-FM our empirical estimates of the privacy loss are up to three orders of magnitude smaller than the theoretical upper bound. While we have no guarantee that our attack is the strongest possible (and it likely is not), our experiment does suggest that for a fixed accuracy level, PATE-FM is much less likely to memorize labels compared to ALIBI (see Figure Tp. Empirically, thus appears that PATE-FM provides much better privacy-utility tradeoff than ALIBI, even though the theoretical analysis suggests the opposite.
the theoretical upper bound on e. This suggests that the
This being said, we encourage critical interpretation of privacy claims backed by memorization esti- mates. Attacks, and the corresponding lower bounds on privacy loss, are provisional and conditional; they can be shattered with better algorithms or additional resources. The empirical lower bounds should be contrasted with provable upper bounds that provide the most conservative guidance in selecting
algorithms and setting their parameters.
8 Conclusion
We have proposed and evaluated two approaches toward achieving Label DP in ML: ALIBI and PATE-FM (the PATE framework instantiated with FixMatch). We have demonstrated that both approaches can achieve state-of-the-arr results on standard datasets. As the two approaches have different theoretical foundations and exhibit very different performance characteristics, they also present an interesting combination of trade-offs.
PATE-FM offers impressive empirical privacy despite very conservative theoretical privacy analysis. On the other hand, its training setup is fairly complicated. The dependency on semi-supervised learning techniques further restricts the tasks this method can be used for present.
In contrast, ALIBI's implementation and interpretation are quite simple. (1) It generic algorithm that is compatible with any iterative procedure for ML training, such as SGD or its variants. It is not

---

black-box however, and requires the ability to update training data labels as they are processed by the training algorithm. (2) enjoys a tighter privacy analysis resulting a more realistic upper bound on the privacy budget, but appears to offer less privacy than PATE-FM empirically. (3) It can be used to train models to accuracy levels which PATE cannot achieve without significantly more data.
In addition to privacy and performance trade-offs,, our two algorithms also differ significantly in their time and computational resource requirements (as discussed in the Section 6.3).
Beyond the concrete improvements offered by our new techniques, our work emphasizes the need for more research across multiple avenues: (1) bridging the gap between privacy lower bounds, backed by attacks, and upper bounds, based on privacy analyses (in particular for PATE); (2) making the privacy analysis of different approaches comparable; (3) designing stronger attack models to better capture empirical privacy guarantees.
Acknowledgements and Funding Sources
The authors are grateful to NeurIPS anonymous reviewers and area chairs for their helpful comments. Florian Tramèr is supported by NSF award CNS-1804222,
References
https://github. /t/.////ooottttttoooooooooooooo http://wwwmmo.eeoooeeerrrrraaaap
[1]
Available under MIT
License.
[2]
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. "A closer look at memorization in deep networks". In: International Conference on Machine Learning (ICML). PMLR. 2017, pp. 233-242..
[3] Philip Bachman, Ouais Alsharif, and Doina Precup. "Learning with pseudo-ensembles". In: Advances in Neural Information Processing Systems (NeurIPS). Ed. by Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger. Vol. 27. 2014.
[4] Amos Beimel, Kobbi Nissim, and Uri Stemmer. "Private learning and sanitization: pure vs. approximate differential privacy". In: Theory of Computing 12.1 (2016), pp. 1-61.
[5] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. "MixMatch: A holistic approach to semi-s semmi-sueervised learning". In: Advances in Neural Information Processing Systems (NeurIPS), Ed. by H. Wallach, H. Larochelle, A. Beygelzimer. F. d' Alché-Buc, E. Fox, and R. Garnett. Vol. 32. 2019.
[6] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. "The Secret Sharer: Evaluating and testing unintended memorization in neural networks". In: 28th USENIX Security Symposium. 2019, pp. 267-284.
[7] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Úlfar Erlingsson, Alina Oprea, and Colin Raffel. "Extracting training data from large language models". In: 30th USENIX Security Symposium. 2021, pp. 2633-2650.
[8] Kamalika Chaudhuri and Daniel Hsu. "Sample Complexity Bounds for Differentially Private Learning.. In: Proceedings of the 24th Annual Conference Learning Theory (COLT). Ed. by Sham M. Kakade and Ulrike von Luxburg. Vol. 19. June 2011, 1, pp. 155-186.
[9] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. "RandAugment: Practical automated data augmentation with reduced search space" In: Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition Workshops. 2020, pp. 702-703.
[10] John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. "Efficient Projections onto the ball for learning in high dimensions". In: Proceedings of the 25th International Conference on Machine Learning (ICML). 2008, pp. 272-279.
[11] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. "Preserving statistical validity in adaptive data analysis". In: Proceedings of the forty-seventh annual ACM Symposium on Theory of Computing (STOC). 2015, pp. 117-126.
[12] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. "Our data, ourselves: Privacy via distributed noise generation". In: Advances Cryptology EUROCRYPT 2006, Ed. by Serge Vaudenay. 2006, pp. 486-503.
10

---

[13] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. "Calibrating noise to sensitivity in private data analysis". In: Proceedings of the 3rd Conference on Theory of Cryptography (TCC). Fd. by Shai Halevi and Tal Rabin. 2006, pp. 265-284.
[14] Cynthia Dwork and Aaron Roth. "The algorithmic foundations of differential privacy." In: Foundations and Trends in Theoretical Computer Science 9.3-4 (2014), pp. 211-407.
[15] Úlfar Erlingsson, llya Mironov, Ananth Raghunathan, and Shuang Song. "That which we call private". In: CoRR abs/1908 15660590003366 (2019).
[16] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. "RAPPOR: Randomized aggregatable ordinal response". In: Proceedings of the 2014 ACM SIGSAC Conference Computer and Communications Security (CCS). Nov. 2014, pp. 1054-1067.
[17] Vitaly Feldman. "Does learning require memorization? A short tale about long tail". In: Proceedings of the 52ndl Annual ACM SIGACT Symposium on Theory of Computing (STOC). 2020, pp. 954-959.
[18] Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi. and Chiyuan Zhang. On deep learming with label differential privacy. 2021. arXiv: 2102.06062 [cs LG]
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. "Deep residual learning for image recognition".. In: 2016 IEEE Conference on Computer Vision and Puttern Recognition (CVPR). 2016, pp. 770-778.
[20] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. "Auditing differentially private machine learning: How private is private SGD?" In: Advances in Neural Information Processing Systems (NeurIPS). Ed. by H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin. Vol. 33. 2020. pp. 222052220222 -2221..
[21] Jungdae Kim. FixMatch-pyttorch http://p/gggggoooooooo///////a/a Available under MIT License.
[22] Alex Krizhevsky. Learning multiple layers of features from tiny images. Tech. rep. 2009.
[23]
Dong-Hyun Lee. "Pseudo-label: The simple and efficient semi- supervise learning method for deep neural networks". In: Workshop on challenges in representation learning, ICML. Vol. 3.
2. 2013.
[24] Jingeheng Liu and Kunal Talwar. "Private Selection from Private Candidates". In: Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing (STOC). pp. 298- 309.
[25]
Kuang Liu. https:://////
reanet. py Available under MIT License.
[26] Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. "Adversary instantiation: Lower bounds for differentially private machine learning".. In: 202/ IEEE Symposium on Security and Privacy (S&P). May 2021, pp. 1183-1199.
[27] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. "The geometry differential privacy: The sparse and approximate cases". In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC). 2013, pp. 351-360.
[28) Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian J. Goodfellow, and Kunal Talwar. "Semi-supervised knowledge transfer for deep learning from private training data". In: 5th International Conference on Learning Representations (ICLR). 2017.
[29] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. "Scalable private learning with PATE". In: 6th International Conference on Learn- ing Representatiions (ICLR). Code available from https: / github. com/ / tensorflow/ wwwaacc/brree/masterrreeee
2018 under Apache 2.0 license. 2018.
[30] Paul M Schwartz. "Privacy and democracy in cyberspace". In: Vanderbilt Law Review 52 (1999), pp. 1607-1702.
[31] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. "Membership inference attacks against machine learning models". In: 2017 IEEE Symposium on Security and Privacy (S&P). 2017, pp. 3-18.
[32] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. "FixMatch: Simplifying semi- supervised learning with consistency and confidence". In: Advances in Neural Information Processing Systems (NeurIPS). Fd. by H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin. Vol. 33, 2020, pp. 596-608.

---

[33] Salil Vadhan. "The complexity of differential privacy". In: Tutorials on the Foundations of Cryptography. Springer, 2017, pp. 347-450.
[34] Di Wang and Jinhui Xu. "On sparse linear regression in the local differential privacy model". In: Proceedings of the 36th International Conference Machine Learning (ICML). Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov. Vol. 97. PMLR, June 2019, pp. 6628-6637,
[35] Weiran Wang and Miguel Á. Carreira- Carreira-Perpiñann Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. 2013. arXiv: 1309. 1541 [cs.LG]
[36] Stanley L Warner. "Randomized response: A survey technique for eliminating evasive answer bias". In: Journal of the American Statistical Association 60.309 (1965), pp. 63-69.
[37] Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. "Privacy risk in ma- chine learning: Analyzing the connection to overfitting". In: 3 IEEE Computer Security Foundations Symposium (CSF). 2018. pp. 268-282.
[38] Sergey Zagoruyko and Nikos Komodakis. "Wide residual networks". In: Proceedings of the British Machine Vision Conference (BMVC). Ed. by Richard C. Wilson, Edwin R. Hancock, and William A. P. Smith. Sept. 2016, pp. 87.1-87.12.
[39] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. "Under- standing deep learning requires rethinking generalization". In: 5th International Conference Learning Representations (ICLR). 2017.
12


Reviews:
[{"review_id": "wH8g4G7g7ix", "reviewer": "Reviewer_ufMh", "summary": " The paper considers the label DP setting and proposes ALIBI and PATE-FM  to achieve Label DP. Their ALIBI approach combines Laplace noise and Bayesian inference and improves over the prior work. Moreover, they introduce a memorization attack in the Label DP scenario. \n", "questions": "", "limitations": "", "rating": 6, "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": " \nClarity: The paper is well written and easy to follow. The background and related work section is complete and helpful. \n\nWeak points:\n1. The proposed PATE-FM lacks algorithmic novelty.  There is no clear difference between PATE and the proposed PATE-FM except that teachers in PATE-FM can jointly reuse unlabeled private data. In other words, the label-DP was supposed to improve performance by sacrificing privacy protections for features. However, the authors use it in a naive way ---  incorporating more unlabeled free data in training. Therefore, I did not see the clear connections between the PATE-FM and label-DP as we can apply the same semi-supervised training in the DP-SGD algorithm and call it an improved algorithm under label-DP. \n\nStrong points:\n1. The paper studies a new and important problem --- improving the privacy-utility trade-offs in the label-DP setting. \n\n2. This paper provides an interesting view on comparing different DP approaches. They empirically estimate the privacy loss based on the black-box membership inference. Moreover, the findings on ``PATE-EM is much less likely to memorize labels compared to ALIBI’’ are novel though the constructed attack may not be the strongest possible attack. \n\nQuestion: \nUsually, we consider the Gaussian mechanism is stronger than the Laplace mechanism due to its more concentrated noise. I am confused on why  ALIBI improves over iterative Bayesian inference on additive Gaussian noise? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Given the limited algorithmic novelty in PATE-FM and the interesting experiments, I think the paper is marginally above the acceptance threshold.   There isn't potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours."}, "extra_text": {}}, {"review_id": "qbB14U0xVjV", "reviewer": "Reviewer_K4t7", "summary": "The paper studies the problem of supervised learning under label privacy, which only imposes differential privacy constraints on the labels of training samples. The paper proposes two algorithms based on different privatization techniques. (1) PATE-FM: The first algorithm divides samples into $K$ equal subsets and trains $K$ non-private teacher classifiers using FixMatch, a semi-supervised learning technique with the unlabeled features from all $n$ samples and labels of samples from the corresponding subset. Then the algorithm trains a private student network using the PATE framework, which is based on private processing of predictions from teacher classifiers. (2) ALIBI: The algorithm randomly perturbs the label of each sample by adding Laplace noise onto the one-hot encoding of the labels. After normalizing the noisy vector, the private soft labels can be then used for subsequent training.\n\nThe paper then performs experiments to evaluate the privacy/accuracy tradeoff for both methods and the LP-2ST algorithm proposed in reference [17]. The paper also performs label inference attacks to estimate the empirical privacy for both methods.", "questions": "", "limitations": "", "rating": 6, "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": "The paper is nicely written.  Although the paper builds heavily on previous techniques in the literature, the paper still has some interesting ideas, i.e, combining semi-supervised learning techniques with PATE to preserve label privacy. I am tending towards accepting the paper. \n\nComments:\n1. In table one, the privacy utility tradeoff for PATE-FM is better on CIFAR-10 and ALIBI is better on CIFAR-100. Is this related to the size of the dataset (number of labels)?\n\n2. I am not quite convinced by the way the empirical privacy cost is calculated. If 1000 labels are flipped, this might significantly bias the obtained model. Hence more experiments are recommended to support the discussion on empirical losses.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "VOCBGsYPup", "reviewer": "Reviewer_bt7g", "summary": "The authors consider label differential privacy (DP) where the goal is to satisfy DP with\nrespect to the labels of the examples. This model was formally introduced by Chaudhuri\nand Hsu (COLT 2011).\n\nThey propose two models for label DP:\n\n1) Based on ALIBI (Additive Laplace noIse coupled with Bayesian Inference)\n\n2) Based on PATE (Private Aggregation of Teacher Ensembles)\n\nA prominent example where label DP is quite useful is in online advertising where the goal is to,\ngiven a user's profile, predict the advert conversion probability (the label). If we assume that\nthe training is done by the advertising network (e.g., a tech company) who has the data (the features),\nthe goal is to make sure the advertiser (some company who wishes to advertise on a tech platform)\ncannot infer the labels.\n\nThey estimate the *empirical* privacy loss of the trained models via the lens of black-box\nmembership inference attacks.\n\nThe novelty of this work, it seems, lies in the (previously unexplored) connections between\nPATE and label DP. Ghazi et al. also proposed randomized response mechanisms for label privacy.\n\nThey experimentally evaluate the performance of their algorithms on CIFAR-10, CIFAR-100 where\nthey show medium to high accuracy results\n(e.g., 93.7% on $\\epsilon = 1.6$).\n\n", "questions": "", "limitations": "", "rating": 7, "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": "The authors propose label privacy mechanisms based on ALIBI (and soft randomized response)\nand PATE.\n\nThe PATE Framework\n------------------\n\nPATE splits learning into stages. First, a number of \"teacher\"s are trained on disjoint\npartitions of the non-public labeled dataset. Second, a \"student\" trains its own model by querying the\n\"teacher\"s on samples drawn from public unlabeled data. DP guarantees are enforced at the\ncommunication points between the teachers and the student.\nBecause of the disjointness of the \"teacher\"'s data, one private sample affects at most one\n\"teacher\".\n\nTheir Adaptation of PATE:\nEach teacher gets $n/T$ labeled examples and $n$ unlabeled examples. And $K$ is the number of labels\nrequested by the student. Note that the choice of $T, K$ results in two competing objectives.\n\nRandomized Response and ALIBI\n-----------------------------\n\nGhazi et al. already proposed a randomized response mechanism. In this framework, the true label is\npredicted with probability $p$ and the other label (assuming we're in the binary case)\nis predicted with probability $1-p$. The authors deviate from previous work in the use of\none-hot encoding of the training sample label (Soft-RR).\nBecause the output of Soft-RR results in values not necessarily in [0, 1] they use\npost-processing and Bayesian inference.\n\n\n\nMinor Comments\n--------------\n- In Table 1, 2 the accuracy of ALIBI and PATE-FM are shown. Can you also include the non-private\naccuracies? [response acknowledged]\n\n- $\\epsilon = 715?$ in the PATE-FM high accuracy level in table 1? [response acknowledged]\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they adequately discuss limitations of their work. See their conclusions where they state that their techniques could lead to more work that can help with \"bridging the gap between privacy lower bounds, backed by attacks, and upper bounds, based on privacy analyses (in particular for PATE); (2) making the privacy analysis of different approaches comparable; (3) designing stronger attack models to better communicate empirical privacy guarantees.\"", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "BI80hVd5X-g", "reviewer": "Reviewer_zWa1", "summary": "This paper focuses on deep learning with level differential privacy (DP), in which the privacy of only the label is preserved. The authors propose two new algorithms: a variation of PATE using a recent semi-supervised learning approach and the fact that features are public in label DP to train better teacher models and use fewer student model queries which consume DP budget ; and a new approach based on local DP noise for the labels, and a Bayesian post-processing that uses the current version of the model to refine guesses about the true underlying label. Finally, the authors run a label memorization attack to empirically assess the privacy.\n", "questions": "", "limitations": "", "rating": 6, "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": "The paper is interesting, and proposes neat algorithmic improvements that seem like they would be useful. The fact that ALIBI supports a local DP type interaction is also promising. However there are two points that would gain to being studied in more depth.\n\nThe point that different DP analysis tightness can lead to the choice of less private models feels both obvious and somewhat irrelevant. The whole point of DP is to provide an upper-bound on the privacy loss: of course if that bound is not tight, another algorithm with a tighter bound could look better. However, empirical measures of privacy like the one discussed in the paper, which is a lower bound on the privacy loss, does not seem like a good metric to decide which algorithm to chose. The discussion should emphasize that more, even earlier in the paper.\nThe empirical observation seems interesting, in particular with the switch between CIFAR-10 and 100, but it should be studied in more depth. Is there a reason to expect the analysis to break down in that case, maybe dure to the larger number of classes? The discussion would be more interesting if you could pinpoint the slackness, and see if there might be hopes to fix it. This would make the gap much more interesting.\n\nIt would be interesting to analyze the ALIBI algorithm a bit more formally. For instance, can it be seen as some type of EM or empirical Bayes procedure, and what would be the implications of that?\n\nEvaluation:\n- For ALIBI, how do you choose the best checkpoint with DP, and how is it accounted for in the total budget?\n- It would be important to have some details about the attacks used for the empirical DP evaluation.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In private deliberation, reviewers seemed to feel that the paper was sound, but perhaps not the most exciting (in particular, not the most novelty in PATE-FM). Nonetheless, they felt it was thorough enough and above the bar for NeurIPS.
Decision: Accept (Poster)