Training Private Models That Know What They Don't Know

Summary

This paper explores the combination of differential privacy (DP) and selective classification. It examines the performance variations of existing selective classification methods when equipped with DP-SGD. Additionally, the paper demonstrates the complex correlation between selective accuracy and differential privacy. To address the challenge of disentangling selective classification performance from baseline utility, a new metric is proposed to evaluate different selective classification algorithms under differential privacy. The paper concludes by highlighting the superior performance of the recent algorithm SCTD in DP settings.

Strengths

The paper explores an intriguing intersection between differential privacy and selective classification. The experiments conducted are comprehensive.

Weaknesses

One potential weakness of this work lies in the exclusive use of DP-SGD for all the differential privacy implementations, which could be a subject of questioning. There exist various methods to enforce differential privacy, such as perturbing output scores ($g(x,f)$) or perturbing training data ($x,y$). In the case of ensembling, applying the DP mechanism in the softmax step, as shown in [1], could be considered. Consequently, ensembling methods do not necessarily suffer from DP composition. Therefore, it might be an overstatement to claim that SCTD performs the best in a private learning setting; instead, it can be stated that it performs well with a straightforward adaptation of DP-SGD. [1] Phan, NhatHai, et al. "Differential privacy preservation for deep auto-encoders: an application of human behavior prediction." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. No. 1. 2016.

Questions

- The term "full-coverage accuracy" is repeatedly referenced without a formal definition. It is unclear whether it represents an arbitrary number within the range of [0,1]. - The advantage of Definition 3.2 is not adequately explained. Since integration is additive, Equation (6) seems to yield a negative AUC score plus a constant determined only by $a_{full}$. This may not provide more informative insights than the original AUC score. Consequently, the benefits of this new metric remain unclear. Moreover, Definition 3.2 is rather confusing. Is $a_{full}$ a variable or a fixed value determined by $f,g$? If it is a variable, how is it chosen among different algorithms? If it is algorithm-dependent, then this is just the (negative) original AUC score penalized by a function of the full-coverage accuracy. It would be helpful to elaborate further on the motivation behind this metric.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Yes.

Summary

This paper investigates the relationship between selective classification (SC) and differential privacy (DP). First, the authors consider various SC approaches and if they incur additional privacy/utility costs under the constraint of DP. They then investigate the effect of DP on SC algorithms and find that DP can drastically reduce the efficacy of SC as models become overconfident in the wrong class under DP. Finally, the authors introduce a new metric to evaluate SC under DP that takes into account the baseline accuracy of the model. An extensive experimental evaluation is given, showing which SC techniques perform best, the coverage needed to provide non-private accuracy, and an evaluation under the new metric. Overall, SCTD (an SC approach that abstains based on the model's disagreement at various checkpoints) is shown to perform the best.

Strengths

- This is a very interesting problem and a clever way to give private learning a boost in accuracy. The coverage required for the non-private accuracy table, in particular, was quite interesting. - The experimental evaluation contains many different SC techniques. This seems like a large implementation effort and a nice contribution to the community. - The example with class imbalance gave a nice intuition for the problem with SC under DP. - The SCTD approach is a nice way to make use of intermediate checkpoints. It is often argued these intermediate model checkpoints are a waste of privacy budget or assume too strong of an adversary. It was nice to see them actually utilized here to improve classification accuracy.

Weaknesses

## Groupings of SC techniques The discussion of why the SC techniques were grouped as post-processing or composition was non-existent. There was discussion of why the DE technique affects privacy/utility, but none of the other approaches received any discussion as to why they were ``free" or had an effect. I believe the SN approach was grouped with composition as it would also affect utility by changing the loss function (but not privacy, as DP-SGD is applied to the gradients, not the loss). But, the authors do not make this argument. Furthermore, by my previous logic, I expect DG or SAT to affect utility as they also modify the loss function. In general, this section on grouping the techniques had the least justification. I would like to see more justification here. It would also be beneficial to explain why specific approaches are free, as I think post-processing is an oversimplification (as some require modifying the training algorithm). ## DE evaluation While I agree the DE approach affects privacy (needing multiple models), I wasn't convinced that composition was the only way to fix this problem. I was curious what would happen if one instead portioned the dataset between the models in the ensemble and used the parallel composition theorem. I realize this would decrease utility, but how would that compare to the composition? ## Delta too high $1/n$ is too large for a delta parameter. It technically allows a trivial mechanism that publishes a single record of the database. The general rule of thumb is that $\delta << 1/n$ [Dwork & Roth](https://www.nowpublishers.com/article/Details/TCS-042). I don't believe changing the delta would affect the overall conclusions of the paper, so I am willing to let it go, but I wanted to bring attention to it. ## Typos/Clarity Overall this paper was incredibly well written. However, below I give a couple of trouble spots that could be made more clear. - Line 64: "more stringent than targeted privacy level" is clunky/hard to parse - Line 124: Overloading the notation of $acc_c$ was rather confusing. I am not sure if this is normal in the SC literature, but having $c$ represent both a threshold and coverage with no clear distinction is rather confusing. - Line 203: Incorrect acronym for deep ensembles. - Line 215: mechanisms? or models? A mechanism is used to train a model, so I think the model makes more sense. - Line 229: This first sentence is somewhat confusing. Specifically, "free from its bias towards accuracy is to align..." is a lot to parse. - Line 246: It should be stated somewhere that this metric lower is better (as opposed to the previous metric that higher is better). To save the reader having to figure that out (although it is easy to figure out). - Figure 2: not sure if error bars could be added here, although it might make it too hard to read - Table 1: it should be made clear what the $\pm$ represents. I assume a confidence interval but at what $\alpha$? - In Tables 1 & 2, the labels seem quite off. First, there are six techniques, but only five appear in Table 1. Second, MSP and NNTD are not defined. I assume NNTD = SCTD and MSP=SR?

Questions

- Can the authors comment on the DE approach using the dataset partitioning idea? Perhaps they have tried it. - Although SC does not affect the privacy guarantee, does it increase privacy leakage? For example, could a membership inference attack use the absence of a prediction to rule out non-member samples and increase overall attack performance?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors do a good job of acknowledging limitations. I agree the initial experimental evaluation is a significant contribution, but theoretical evaluations are important for future work.

Summary

This paper explores the interaction between differential privacy and selective classification. Several methods for training selective classifiers are considered and evaluated for their compatibility with DP-SGD. Experimental results are given that show decreasing privacy parameters leads to selective classifiers becoming increasingly confident in incorrect predictions. An alternative performance metric for selective classification is proposed for the purposes of evaluating DP selective classifiers.

Strengths

The paper, to the best of my knowledge, is the first to empirically investigate the degradation of performance of selective classifiers under the constraint of differential privacy. It addresses interesting questions regarding the training and evaluation of DP selective classifiers, and highlights important distinctions between SC training methods that become particularly relevant in the setting of differential privacy.

Weaknesses

I think additional attention to presentation is necessary to clarify the main contributions of the paper. The punchline of the experiment in the body of the paper is that the observed overconfidence in an incorrect classification prevents selective classification, but this is an underspecified claim. I take it to mean that highly accurate selective classification based on prediction confidence is in tension with strong privacy guarantees, but this is consistent with known privacy/accuracy tradeoffs and doesn't seem terribly surprising. The necessity for new evaluation metrics is also still unclear to me. The metric given in equation 4 is an area under the curve of accuracy as a function of coverage, as coverage ranges from 0 to 1, but then the stated motivation for the new evaluation metric is that we want to avoid aligning selective classifiers based on accuracy. As stated, it doesn't seem like equation 4 is aligning on accuracy, and that training two selective classifiers with different privacy parameters would allow for a meaningful comparison by (an approximation) of equation 4.

Questions

My main questions are reiterations of earlier critique. Why do existing evaluation metrics fail in the case of private selective classification? Is there additional significance to the empirical results beyond the extension of privacy/utility tradeoffs to the case of selective classification? In Figure 1, it would be nice to have the meaning of the various colors used explicitly stated, ideally in the caption. It's inferable from context, but additional description would probably save the reader time. I also found the results in figure 4 and 5 were challenging to parse, mostly the significance of the blue and orange lines. Additional explanatory text to help the reader interpret these lines would be greatly appreciated.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

2 fair

Limitations

Yes, the authors have sufficiently addressed the impact of their work.

Summary

The paper studies selective classification with differential privacy (DP). In particular, the authors conduct a comprehensive empirical study of different selective classifiers under DP. The key findings and contributions are: * An existing SC method that uses checkpoints is suitable under DP. * A novel accuracy-dependent selective classification score proposed by the authors helps compare selective classification performance across DP levels without explicit accuracy alignment. * Selective classification performance degrades with stronger privacy. * Recovering utility can come at a considerable coverage cost under strong privacy requirements.

Strengths

* The paper initializes the study of the interplay between DP and SC. This is the first study of its kind. The proposed metric is effective in evaluating the performance of SC under different coverage. Thus, the significance of the proposed metric is beyond the study of the paper. * The paper might have an impact on the community in the long run since it bridges previously disconnected fields (SC and DP). Thus, The paper pushes the community in a new, interesting/important direction. * The paper is well-written and clearly organized. The evaluation is also comprehensive.

Weaknesses

I do not find any obvious weaknesses in the paper. One minor point that could be improved is the explanation of the proposed metrics (Definition 3.1) in lines 255-260. It takes me some time to digest why the authors define the upper bound in this way. Going beyond this, I think a more rigorous theoretical analysis and characterization between the trade-offs of SC and DP could be an interesting direction.

Questions

Please improve the explanation of the proposed metrics (Definition 3.1).

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors have adequately addressed the limitations.

Thank you for the rebuttal

Thanks for the reply. The rebuttal have addressed some of my concerns. However, I am still not totally convinced by the justification of Eq. (6). To clarify, I did not say the score can be negative. What I meant is that the integration in Eq. (6) can be decomposed into two parts $A-B$, where term $A$ is merely a function of $a_{full}$ and term $B$ is just the AUC. In other words, for two algorithms with the same $a_{full}$, comparing the metric in Eq. (6) is just equivalent to comparing the negative AUC. If $a_{full}$ is determined by the selective classification algorithm, then I may get a bit of this definition, which makes sense for normalization. I have updated my evaluation accordingly.

Reply to Rebuttal

I want to thank the Authors for a very detailed response to the reviews. - Thanks for clarifying the grouping; this makes much more sense. I would still argue post-processing is not quite the correct name, as changing the utility function/architecture can not be done after training, but I am ok with it (now it is more clearly explained). - I really appreciated the additional partitioned DE evaluation and am convinced by the results. - Also, thanks for the discussion on MI. I agree it will be interesting to pursue this connection further (but out of the scope of this work). Overall I am satisfied with the response and have updated my score.

Thank you

We were happy to see that our rebuttal has helped the reviewer to understand the motivation underlying our submission better! We also thank the reviewer for raising their score and kindly ask the reviewer to consider updating their sub-scores for **Presentation** and **Contribution** as well. Unfortunately, although an interesting problem, the interplay of cryptographic adversaries and selective classification is beyond the scope of our work. We are not aware of this connection having been explicitly established so far. In terms of related work, we note that the connection between some selective classifiers, in particular Bayesian classifiers, and mutual information classifiers has been preliminarily explored [1]. Moreover, there exists a definition of DP that is based on a mutual information constrain which yields a definition of DP that sits in between $\varepsilon$-DP and $(\varepsilon, \delta)$-DP in terms of the provided guarantees and attack surface [2]. Finally, we do believe that quantifying predictive uncertainty and abstaining from prediction under high uncertainty does indeed constitute a valuable tool that can be of use in the bit security setup as described in the paper provided by the reviewer. As mutual information is intimately connected to entropy, it can quantify certainty in a prediction which can constitute a valuable signal for rejection. As such, future work should investigate to what extent recent advances in selective prediction can be helpful in the context of cryptographic adversarial applications. [1]: Hu, Bao-Gang. "What are the differences between Bayesian classifiers and mutual-information classifiers?." IEEE transactions on neural networks and learning systems 25.2 (2013): 249-264. [2]: Cuff, Paul, and Lanqing Yu. "Differential privacy as a mutual information constraint." Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016.

Thank you for the rebuttal!

[copying my previous comment to the appropriate rebuttal, apologies for any confusion] Thanks to the authors for help in understanding the challenges in SC evaluation in the private setting. I believe I misunderstood the existing approaches for evaluation, but the explanation and reference to prior work were enlightening. I've updated my score accordingly. This is unlikely to be useful, but I wonder what connections there might be between evaluating selective classifiers (in the non-private setting) and cryptographic adversaries. For instance, https://eprint.iacr.org/2018/077.pdf proposes a metric for evaluation of abstaining adversaries that follows from some analysis of the mutual information between the adversary's predictions and the correct label.