Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

The 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.
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. 

Comments:
1. 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)?

2. 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.



limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

main_review:  
Clarity: The paper is well written and easy to follow. The background and related work section is complete and helpful. 

Weak points:
1. 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. 

Strong points:
1. The paper studies a new and important problem --- improving the privacy-utility trade-offs in the label-DP setting. 

2. 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. 

Question: 
Usually, 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? 
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_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider label differential privacy (DP) where the goal is to satisfy DP with
respect to the labels of the examples. This model was formally introduced by Chaudhuri
and Hsu (COLT 2011).

They propose two models for label DP:

1) Based on ALIBI (Additive Laplace noIse coupled with Bayesian Inference)

2) Based on PATE (Private Aggregation of Teacher Ensembles)

A prominent example where label DP is quite useful is in online advertising where the goal is to,
given a user's profile, predict the advert conversion probability (the label). If we assume that
the training is done by the advertising network (e.g., a tech company) who has the data (the features),
the goal is to make sure the advertiser (some company who wishes to advertise on a tech platform)
cannot infer the labels.

They estimate the *empirical* privacy loss of the trained models via the lens of black-box
membership inference attacks.

The novelty of this work, it seems, lies in the (previously unexplored) connections between
PATE and label DP. Ghazi et al. also proposed randomized response mechanisms for label privacy.

They experimentally evaluate the performance of their algorithms on CIFAR-10, CIFAR-100 where
they show medium to high accuracy results
(e.g., 93.7% on $\epsilon = 1.6$).


main_review: The authors propose label privacy mechanisms based on ALIBI (and soft randomized response)
and PATE.

The PATE Framework
------------------

PATE splits learning into stages. First, a number of "teacher"s are trained on disjoint
partitions of the non-public labeled dataset. Second, a "student" trains its own model by querying the
"teacher"s on samples drawn from public unlabeled data. DP guarantees are enforced at the
communication points between the teachers and the student.
Because of the disjointness of the "teacher"'s data, one private sample affects at most one
"teacher".

Their Adaptation of PATE:
Each teacher gets $n/T$ labeled examples and $n$ unlabeled examples. And $K$ is the number of labels
requested by the student. Note that the choice of $T, K$ results in two competing objectives.

Randomized Response and ALIBI
-----------------------------

Ghazi et al. already proposed a randomized response mechanism. In this framework, the true label is
predicted with probability $p$ and the other label (assuming we're in the binary case)
is predicted with probability $1-p$. The authors deviate from previous work in the use of
one-hot encoding of the training sample label (Soft-RR).
Because the output of Soft-RR results in values not necessarily in [0, 1] they use
post-processing and Bayesian inference.



Minor Comments
--------------
- In Table 1, 2 the accuracy of ALIBI and PATE-FM are shown. Can you also include the non-private
accuracies? [response acknowledged]

- $\epsilon = 715?$ in the PATE-FM high accuracy level in table 1? [response acknowledged]

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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.

The 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.
The 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.

It 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?

Evaluation:
- For ALIBI, how do you choose the best checkpoint with DP, and how is it accounted for in the total budget?
- It would be important to have some details about the attacks used for the empirical DP evaluation.

limitations_and_societal_impact: N/A
review_title: null

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)