Training Private Models That Know What They Don’t Know
Authors: Stephan Rabanser
Anvith Thudi
Abhradeep Guha Thakurta
Krishnamurthy Dj Dvijotham
Nicolas Papernot
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
selective classification
selective prediction
abstain option
reject option
uncertainty quantification
misclassification detection
TL;DR: This work provides an initial analysis on the connection between uncertainty quantification / selective prediction and differential privacy.

Abstract: Training reliable deep learning models which avoid making overconfident but incorrect predictions is a longstanding challenge. This challenge is further exacerbated when learning has to be differentially private: protection provided to sensitive data comes at the price of injecting additional randomness into the learning process. In this work, we conduct a thorough empirical investigation of selective classifiers---that can abstain under uncertainty---under a differential privacy constraint. We find that some popular selective prediction approaches are ineffective in a differentially private setting because they increase the risk of privacy leakage. At the same time, we identify that a recent approach that only uses checkpoints produced by an off-the-shelf private learning algorithm stands out as particularly suitable under DP. Further, we show that differential privacy does not just harm utility but also degrades selective classification performance. To analyze this effect across privacy levels, we propose a novel evaluation mechanism which isolates selective prediction performance across model utility levels at full coverage. Our experimental results show that recovering the performance level attainable by non-private models is possible but comes at a considerable coverage cost as the privacy budget decreases.

Training Private Models That Know What They Don't Know
Stephan Rabanser 22, Anvith Thudi 1.2, Abhradeep Thakurta,,
Krishnamurthy (Dj) Dvijotham', Nicolas Papernot University of Toronto, Vector Institute, 'Google DeepMind
Abstract
Training reliable deep learning models which avoid making overconfident but incor- predictions is longstanding challenge. This challenge is further exacerbated when learning has to be differentially private: protection provided to sensitive data comes at the price of injecting additional randomness into the learning process. In this work, we conduct a thorough empirical investigation of selective classifiers- that can abstain under uncertainty-uune underr differential privacy constraint. We find that some popular selective prediction approaches are ineffective in a differentially private setting because they increase the risk of privacy leakage. At the same time, we identify that recent approach that only uses checkpoints produced by an off-the-shelf private learning algorithm stands out as particularly suitable under DP. Further, we show that differential privacy does not just harm utility but also degrades selective classification performance. To analyze this effect across privacy levels, we propose novel evaluation mechanism which isolates selective prediction performance across model utility levels full coverage. Our experimental results show that recovering the performance level attainable by non-private models is possible but comes at a considerable coverage cost as the privacy budget decreases.
Introduction
State of the art machine learning (ML) models are gaining rapid adoption in high-stakes application scenarios such as healthcare CCallen al., 2019, Mozannar and Sontag 2020], finance [Vijh et al.) 2020], self-driving [Ghodsi et al. 2021]. and law [Veiir et al. [222]] However, major challenges remain be addressed to ensure trustworthy usage of these models. One major concern in sensitive applications is to protect the privacy of the individuals whose data an ML model was trained on. To prevent privacy attacks on ML models, (e. 8) differential privacy (DP) [Dwork et al.) 2014) has emerged as the de-facto standard with widespread usage in both academic and industrial applications.
While the introduction of DP successfully protects against privacy attacks, also limits model utility in practice. For instance, the canonical algorithm for training models with DP, DP-SGD (Abadi et al. 2016). clips the per-sample gradient norm and adds carefully calibrated noise. These training time adaptations frequently lead to degradation in predictive performance in practice. This is especially problem for datasets containing underrepresented subgroups whose accuracy has been shown to degrade with stronger DP guarantees (Bagdasaryan et al. 2019]. Faced with this challenge, it is therefore of vital importance detect samples on which DP model would predict incorrectly on.
One popular technique used to detect inputs that the model would misclassify with high probability given by the selective classification (SC) framework [Geifman and El- Yaniv 2017]: by relying on a model's uncertainty in the correct prediction for an incoming data point, the point is either accepted with the underlying model's prediction, rejected and potentially flagged for additional
"Corresoondence to: stephan@cs. wor.ooo....ooooooee...ooo
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

downstream evaluation. Hence, SC introduces trade-off between coverage over the test set (i.e., the goal of accepting as many data points as possible) and predictive performance on the accepted points (i.e., the goal of making as few mistakes as possible). Although identification of misclassified points seems of particular importance under differential privacy, the application of selective prediction to private models is under-explored to date. While lots of past works have studied privacy or selective prediction in isolation, best practices for selective prediction under differential privacy have not been established yet. In this work, are the first to answer the question of whether selective classification can be used to recover the accuracy lost by applying a DP algorithm (at the expense of data coverage).
To analyze the interplay between differential privacy and selective classification, we first show that not all approaches towards selective classification are easily applicable under differential privacy constraint. In particular, approaches relying on multiple passes over the entire dataset to obtain the full SP performance profile [Geifman and HI- Yaniv 2019 [akshminarayanan et al., 2017) suffer significantly under differential privacy. This is due to the fact that the worst-case privacy leakage increases with each analysis made of the dataset which means that each training run forces more privacy budget to be expended. On the other hand, our analysis shows that an SC approach based on harnessing intermediate model checkpoints [Rabanser et al. [022] yields the most competitive results. Notably, this approach performs especially well under stringent privacy constraints (E 1).
Next, we find that differential privacy has a more direct negative impact on selective classification that goes beyond the characteristic drop in utility. Based on a simple synthetic experiment, we observe a clear correlation between differential privacy strength and wrongful overconfidence. In particular, even when multiple private models trained with different e levels offer the same utility on the underlying prediction task, we show that stronger levels of DP lead to significantly decreased confidence in the correct class. This reduction effectively prevents performant selective classification.
Motivated by this observation, we realize need disentangle selective classification from model utility; SC ability and accuracy should be considered independently. To that end, we show that the evaluation metric typically used for non-private selective classification is inappropriate for comparing SC approaches across multiple privacy levels. The in-applicability of the current method stems from the fact that full-coverage accuracy alignment required across experiments. In particular, accuracy- aligning multiple DP models via carly-stopping frequently leads to a more stringent than targeted privacy level, rendering the intended comparison impossible. Due to this limitation of previous evaluation schemes, we propose a novel metric which isolates selective classification performance from losses that come from accuracy degradation of the classifier overall (as frequently caused by DP). The performance metric we propose to tackle this problem computes upper bound on the accuracylcoverage trade-off in model-dependent fashion and measures the discrepancy between the actual achieved trade-off to this bound. Using this score, we determine that, based on a comprehensive experimental study, differential privacy does indeed harm selective prediction beyond a loss utility.
We summarize our key contributions below:
We provide a first analysis on the interplay between seleetive classification and differential privacy. As result, we identify existing SC method as particularly suitable under DP and present an illustrative example showcasing an inherent tension between privacy and selective prediction.
2. We unearth a critical failure mode of the canonical SC performance metric preventing its off-the- shelf usage under DP experimentation. We remedy this issue by introducing novel accuracy- dependent selective classification score which enables us to compare selective classification performance across DP levels without explicit accuracy-alignment.
3. We conduct a thorough empirical evaluation across multiple selective classification techniques and privacy levels. As part of this study, we confirm that selective classification performance degrades with stronger privacy and further find that recovering utility can come at a considerable coverage cost under strong privacy requirements.
2 Background
2.1 Differential Privacy with DP-SGD
Differential Privacy (DP) [Dwork et al. 2014] is a popular technique which allows us to reason about the amount of privacy leakage from individual data points. Training model with differential privacy

---

ensures that the information content that can be acquired from individual data points is bounded while patterns present across multiple data points can still be extracted. Formally, randomized algorithm M satisfies (s. 6) differential privacy, if for any two datasets D, D' C "D that differ in any one record and any set of outputs the following inequality holds:
P PIM(D) E S) & eTT (M(') E +
+
The above DP bound is governed by two parameters: E R4 which specifies the privacy level, and ò E [0, 1] which allows for small violation of the bound.
DP-SGD. A canonical way of incorporating differential privacy in deep learning is via Differentially Private Stochastic Gradient Descení (DP-SG7) (Bassily al. 2014 Abadi al., 2016). We describe the DP-SGD algorithm in detail in Algorithm 2 in the Appendix. The main adaptations needed to incorporate DP into SGD are: (i) per-sample gradient computation, which allows us to limit the per-point privacy leakage in the next two steps; (ii) gradient clipping, which bounds the sensitivity (i.e., the maximal degree of change in the outputs of the DP mechanism); and (iii) noise addition, which introduces Gaussian noise proportional to the intensity of gradient clipping.
2.2 Selective Classification
Supervised classification. Our work considers the supervised classification setup: We assume access to a dataset = {( yn ) consisting of data points (x, y) with æ E X S IRd and y E y (I..... C}. All data points (x, y) are sampled independently and identically distributed from the underlying distribution defined over X' x y. The goal is to learn a prediction function f X y' which minimizes the classification risk with respect to the underlying data distribution p R.
as measured by a loss function e: y x
Selective classification. Selective classification augments the supervised classification setup by introducing rejection class 1 via a gating mechanism [EI- Yaniv and Wiener 2010]. This mechanism produces class label from the underlying classifier if the mechanism is confident that the prediction is correct and abstains otherwise. Note that this mechanism is often directly informed by the underlying classifier f and make this dependence explicit in our notation. More formally, the gating mechanism introduces a selection function : X' x (X' + y) + IR which determines if a model should predict data point If the output of g(æ, f) undercuts given threshold т, return / (a), otherwise we abstain with decision L. The joint predictive model is therefore given by:
[((x) (f.g)(z) - -
ST otherwise.
Evaluating SC performance. The performance of selective classifier (f.g) is based on two metrics: the coverage of g) (corresponding to the fraction of points to predict on) and the accuracy of (f.g) on accepted points. Note that there exists tension between these two performance quantities: naively increasing coverage will lead to lower accuracy while an increase in accuracy will lead to lower coverage. Successful SC methods try jointly maximize both metrics.
(J.g( (æ: g(x, f) < 7
acc+(f.g) ( f(x) y, (0, f) ST
(3)
D
[<x: : g( f) ك +)
To characterize the full performance profile of selective classifier (fs, g), we consider the selective accuracy at coverage level c, formally acc,(f.g) over the full coverage spectrum by computing an wea--undertthe-cure (AUC) score SAUC as follows:
(AUC(J.g) = (C
acc.(S.g) (f.)( for s.t. cov,(J.g) = (4)
Each existing selective classification algorithm proposes a g that tries to maximize this metric. We describe popular approaches below and include additional details in Appendix A.2
Prediction confidence. The traditional baseline methods for selective prediction is the Sofimax Response (SR) method [Hendryeks and Gimpel| 2016 Geifman and Yaniv 2017]. This method uses the confidence of the final prediction model as the selection score. To reduce overconfident predictions yielded by this method, confidence calibration [uuo al. 2017 has been proposed.
3

---

Ensembling, To further improve calibration and to reduce variance, ensemble methods have been proposed which combine the information content of M models into a single final model. The canonical instance of this approach for deep learning based models, Deep Ensembles (DE) [Laksh] minarayanan et al. 2017]. trains multiple models from scratch with varying initializations using a proper scoring rule and adversarial training. Then, after averaging the predictions made by all models, the softmax response (SR) mechanism is applied. To overcome the computational cost of estimating multiple models from scratch, Monte-Cario Dropout (MCDO) [Gal and Ghahramani 2016) allows for bootstrapping of model uncertainty a dropout-equipped model at test time. Another ensembling approach that has recently demonstrated bate-of-the-as selective classification performance is based on monitoring model evolution during the training process. To that end, Selective Classification Training Dynamics (SCTD) [Rabanser et al.) 2022 records intermediate models produced during training and computes a disagreement score of intermediate predictions with the final prediction.
Architecture & loss function modifications. A variety of SC methods have been proposed that leverage explicit architecture and loss function adaptations. For example, SelectiveNet (SN) (Geifman and Yaniv 2019) modifies the model architecture to jointly optimize (f,9) while targeting the model at desired coverage level Cuarget- Alternatively, prior works like Deep Gamblers (Liu et al. 2019] and Self-Adaptive Training (Huang et al., 2020] have considered explicitly modeling the abstention class 1 and adapting the optimization process to provide a learning signal for this class. For instance, Self-Adaptive Training (SAT) incorporates information obtained during the training process into the optimization itself by computing and monitoring an exponential moving average of training point predictions over the training process. Introduced to yield better uncertainty estimates, Liu et al. (2020) employs weight normalization and replaces the output layer of a neural network with a Normalie- Neural Gaussian Process to improve data manifold characterization.
Uncertainty for DP models. An initial connection between differential privacy and uncertainty quantification is explored in Williams and McSherry (2010). which shows that probabilistic inference can improve accuracy and measure uncertainty on top of differentially private models. By relying on intermediate model predictions, SShjwaalkar et al. [2022 has proposed mechanism to quantify the uncertainty that DP noise adds to the outputs of ML algorithms (without any additional privacy cost).
3 The Interplay Between Selective Classification and Differential Privacy
We now examine the interplay between these ap- proaches to selective classification and training algorithms constrained to learn with differential privacy guarantees. We first introduce can- didate selective classification approach which leverages intermediate predictions from models obtained during training. Then, we study how current selective classification approaches im- pact DP guarantees, as each access they make to training data increases the associated privacy budget. Next, we investigate how in turn DP affects selective classification performance. In- deed, DP alters how optimizers converge to solution and as such DP can impact the perfor- mance of SC techniques. Last, we discuss how selective classification performance can be fairly compared across range of privacy levels.
Algorithm 1: SCTD Rabansee et al. 2022]
Require: Checkpointed model sequence
(fi,..,, Jr query point x, weighting parameter is E [0, oo).
1: Compute prediction of last model:
L fr())
2: Compute disagreement and weighting of intermediate predictions:
3: for t E [T] do
4: if f(
then a; t else ag + 1
5: 0/ <- -+)
6: end for
7: Compute sum score: Ssam + -, Uzar
8: if Ssum < T then accept f(x) = L else reject
with f f(z) =
3.1 Performative Private Selective Classification via Training Dynamies Ensembles
As a classical technique from statistics, ensembling methods are often employed for confidence interval estimation (Karwa and Vadhan 2017 Ferrando et al. 20022. uncertainty quantification [Lak] shminarayanan et al. [207]. J. and selective prediction [Zaoui et al. 2020). Under a differential privacy constraint, although for simpler tasks like mean estimation ensembling methods have been proven to
be effective [Brawner and Honaker 2018 Covington al. 2021 Evans et al. 2019 in this paper

---

we demonstrate that they are fairly ineffective for selective classification. This is primarily due to the increased privacy cost due (advanced sequential) composition [Dwork et al. [006].
In light of this challenge, we expect one recent method in particular to perform well in a private learning setting: selective classification via training dynamics (SCTD) (Rabanser et al. 2022 (details described in Algorithm [ For a given test-time point, SCTD analyzes the disagreement with the final predicted label over intermediate models obtained during training. Data points with high disagreement across this training-time ensemble are deemed anomalous and rejected. Most importantly, while SCTD also constructs an ensemble, only a single training run is used obtain this ensemble. As a result of the post-pre proccesins property of DP, the original (E, 6)-DP guarantee can be maintained. To further motivate the effectiveness of relying on intermediate checkpoints, [Shejwalkar et al.) [2022) has shown in adjacent work that intermediate predictions can improve the predictive accuracy of DP training, yielding new state-of-the-an results under DP.
3.2 How Do Other Selective Classification Approaches Affect Privacy Guarantees?
We can extend the previous analysis based on post-processing and composition to other SC techniques. This allows us to group selective classification techniques into three classes: (i) directly optimized; (ii) pros-processing; and (iii) advanced sequential composition. For directly optimized and post- processing approaches, we can obtain selective classification for free. On the other hand, composition- based approaches either require an increased privacy budget or suffer from decreased utility.
Direct optimization. Many selective classification approaches directly modify the loss function and optimization is performed w.r.t. this adapted loss function. As DP-SGD is loss function and architecture agnostic (s, 5) guarantees hold automatically for SC methods that only change the loss function. Applicable to: Softmax Response (SR), Deep Gamblers (DG), Self-Adaptive Training (SAT).
Post-processing. If a function Φ(x) satisfies (c, 8)-DP, then for any deterministic or random function (.), the application of s on o. formally & o ((x), still satisfies (s. 8)DP (Dwork et al., [006). Applicable to: Monte-Carke Dropout (MCDO), Selective Classification Training Dynamics (SCTD).
Advanced sequential composition. in set of aggregated functions (x), @ Ar (x)) each (1(x)) satisfies (s, 6)-DP, then releasing the set of all outputs (b(x)) = ..... dM (1)) satisfies (VMe, M Dwork et al. 2006). To maintain (s, 6 over the aggregated output, each function needs to satisfy RJ
VM M7 DDD.. Applicable to: Deep Ensembles (DE), SelectiveNet (SN).
3.3 How Does Differential Privacy Affect Selective Classification Performance?
After having examined how current selective classification techniques influence differential privacy guarantees, this subsection considers the opposite effect: what is the impact of differential privacy on selective classification? As we will see by means of an intuitive example, we expect that differential privacy impacts selective classification beyond a loss in utility.
To showcase this, we present a synthetic logistic regression example with the softmax response SC mechanism. We generate data from mixture of two wwo-dimensional Gaussians with heavy class-imbalance. Concretely, we generate samples for a majority class {(x,, 1))2090 with each æ; ~ (0, I) and single outlier point form minority class (x*,-10 -1) with xx ~ ~N(110 oj" T). We then train multiple differentially private mechanisms with e E {o0, 7, evaluate all models
(,31] 1} on this datasct and process.
test set produced using the same data-generatie
We show the outcome of this set of experiments in Figure where we plot the test set and the decision boundary of each model across levels. For = co, the model successfully discriminates the majority and the minority class. However, the decision boundary is heavily influenced by a single data point, namely the outlier (x* 11). Note that, even though all models with E E {7, 37,3.11 3.1 misclassify the outlier point (i.e., their utility is aligned), the changing decision boundary also increases the model's s confidence in predicting the incorrect class for the outlier. Hence, even at an aligned utility level, the softmax response approach for SC performs increasingly worse on the outlier point under stronger DP constraints. We provide additional imbalanndd results on realistic datasets in Appendix B.2
5

---

7.0
2.5
2.5
0.
0.-
-25
-2.5
Figure 1: Synthetic example of privacy impacts on selective classification. Shaded regions show softmax response confidence in the red and blue class, respectively. As decreases, the blue outlier point is increasingly protected by DP. Importantly, not only does DP induce a misclassification the outlier point, but stronger levels of DP further increase confidence in the wrong prediction. This overconfidence in the incorrect class prevents selective classification.
3.4 How Should We Evaluate Selective Classification Under Differential Privacy?
As we have now established, we expect differential privacy to harm selective classification perfor- mance. In light of this insight, we now investigating whether the standard evaluation scheme for SC is directly applicable to the differentially private models.
The default approach of using the SC performance metric introduced in Equation free from its bias towards accuracy is align different SC approaches/models the same accuracy. However, accuracy-alige -lliginng can have unintended consequences on SC performance, especially under DP. If are considering SC performance across models trained for multiple levels, accuracy-alignmenn would require lowering the performance of the less private models. One seemingly suitable approach do this is by early-stopping model training at a desired accuracy level. However, storl--ttpping DP training algorithm in fact gives model with greater privacy than the privacy level targeted by the optimization process. This a direct consequence of privacy loss accumulation via privacy accounting during training, and so training for less leads to expending less privacy budget. Hence, instead of comparing models with different privacy guarantees at the same baseline utility, early-stopping yields models with potentially very similar privacy guarantees.
To address this limitation, we propose measure SC performance by how close the observed trade-off is to an upper bound on the achievable SC performance at given baseline utility level (at 100% coverage). To compute this metrie, we first derive an upper bound on selective classification performance (as function of coverage) for given baseline accuracy. We obtain this characterization by identifying the optimal acceptance ordering under particular full-coverage accuracy constraint.
Definition 3.1. The upper bound on the selective classification performance for fixed full-cccr- accuracy agut E [0, 1] and variable coverage level E [0, 1] is given by
acc(apas c) = {(1 0 0< afall
ajdl < c <c<
Measuring the area enclosed between the bound acc( c) and an SC method's achieved aceu- racy/coverage trade-off acco(f, (f g) yields our accuracy-normalized selective classification score.
Definition 3.2.
The sacuracy-normalize selective classification score Saza (J g)) for selective classifier (f.g) with full-coverage accuracy afal given by
Sawe (f.g) S. faco(apaat c) (cce(f.g))dl =
Σ (acc(a ana c) acce (f.g)).
(6)
We provide additional intuition for both the proposed upper bound and our score as part of Figure
Bound justification. To understand the upper bound given in Equation 5 note that a full-coverage accuracy level of dhall means that fraction dnall of points are correctly classified. An ideal selective classification method for this model would, by increasing the coverage e from () to 1, first accept all points that the model classifies correctly: this gives the optimal selective classification accuracy for coverage S agall of 100%. For any coverage level Gfull, note that the accuracy at the coverage

---

200 200( Maal
aec c)
acce
Accuracy
Accuracy
Sapai (..9)
0.5
0.6
correct points
incorect points
0.4
0
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
Coverage (c)
Coverage (c)
(a) Upper bound ace
aco( (190t, c) on the selective classifi- cation performance conditional ajutt As coverage increases from accepts all correct points first (with consistent accu- racy of until c afui) and then spreads the accuracy decrease Shil equally over the remaining coverage 1.
(b) Accuracy-normulizes score for SC performance. The accuracy-normallzzed score for selective clas- sification Sega (J.g) corresonnds
1. optimal selective classifier
the area closed between the upper bound acc(ama, e) and the empirical accuracy/coverage trade-off acc. (f.g). Good selective classifiers should achieve a low score (8amm (f.g) 0), indicating eloseness to the bound.
spectrum, leading to convex drop
Figure 2: Selective classification upper bound and accuracy-normalized score visualization. We present example of selective classifier with full-coverage accuracy aiull 0.4 and show how (a) the corresponding upper bound; and how (b) the accuracy-normalizer score can be obtained.
the number correct points accepted divided by the total number of points accepted. The largest value this take is by maximizing the numerator, and the maximum value for this (as fraction of all points) is aial- Plugging this into the previous statement for accuracy at coverage c, we have the best selective accuracy at coverage is This derives the upper bound stated above function of coverage. We remark that this bound is in fact achievable if selective classifier separates correct and incorrect points perfectly, i.e., accepts all correct points first and then accepts and increasing amount of incorrect points as we increase the coverage of the selective classification method. See Appendix B.3 for experiment that matches the bound exactly.
Experiments
We present detailed experimental evaluation of the interplay between differential privacy and selective classification. All of our experiments are implemented using PyTorch [Paszke et al.) 2019] and Opacus (Yousefpour al. 2021]. We publish our full code-base at the following URL: https: /ttptt....../.gg//gg com/ wtt.//////ccaeee clnverhans labbselective-eeeeeeeeeeebeeeeee wwwssification..
Setup. Our evaluation is based on the following experimental panel. particular, we conduct experiments for each dataset/SC-mmthodd/ combination:
Datasets: FashionMNIST Xiao et al. 2017 CIFAR-10 Krizhevsky et al. 2009 SVHN Netzer
et al. 201T). GTSRB (Houben al. 2013].
Selective Classification Methods:
Softmax Response (SR) [Geifman and E]- Yaniv 2017 Selec-
tiveNet (SN) [Geifman and El- Yaniv 2019). Self-Adaptive Training (SAT) [Huag et al. 2020
Monte-Carlo Dropout (MCDO) [Gal and Ghahramani 2016), Deep Ensembles (DE) Lakshmi
narayanan et al, [017]. Selective Classification Training Dynamics (SCTD) [Rabanser et al. 2022
Privacy levels: E (0o, 3,
Based on recent results from Feng et al. 2023], we (i) apply additional entropy regularization to all methods; and (ii) derive the selective classification scores for SN and SAT by applying Softmax Re- sponse (SR) to the underlying classifier (instead of relying on model-specific abstention mechanisms). Across all private experiments, we set J 10-(N+1) for datasets consisting of training samples on the order of 1 For each combination of SC method, dataset, and privacy level, we train model following the ResNet-18 [He et al. 2016 model architecture using either the SGD optimizer (for & oo) or the DP-SGD optimizer (for all co). All models are trained for 200 epochs using

---

FashiouMNIST
CIFAR-10
SVHN
GTSRB
1.00
1,00
1.00
1.000
Accundey
0.95
0.95
0.98
0.975
0.96
1.0
1.0
1.0
1.0
8= 7.0
Accurdey
0.9
0.9
0.6
1.0
1.0
1.0
1.0
8= 3.0
Accuracy
0.8
0.9
0.9
0.8
0.6
0.8
1.0
1.0
1.0
1.0
Accuncc
8=10
0.9
0.5
0.5
0.8
0.8
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Coverage
Covenge
Coverage
Coverage
XCD0
Figure 3: Accuracy-coverage trade-off' across datasets & & levels. We highlight noteworthy results for SCTD, DE, and SN with bold lines and further show that SN only provides results at coarse-grained coverage levels. SCTD performs best while DE and SN performance is compromised at any e < co.
Table 1: Coverage required for non-private full-coverage accuracy. We observe that differential privacy considerably lowers the allowable coverage to achieve utility level consistent with the non-private model. Across our experiments, SCTD yields the highest coverage across levels.
FishionMNSST
CIEAR-10
SVEN
GTSRB
(2001)
0.80
0.65 (2.00)
(20.02)
0.14:2000))
0:00 (2000)
0.74
(20.0)
0.59
(500))00))
(e0003)
(20.00)
SAT
0.86 (s0,00)
0.81 (:0.01)
867 (20.0))
0.25
0.19 (2tun))
0.00 (10.00
0.72 (20.00)
0.67 (-0.00
0.45 (50.0)
0.74 (2040)))0) (3000)
0.20 (2005)
MC00
0.84 (s0.82)
0.70 (20.00)
0.56 (20.00))
(20.00)
(20022)
0.00 (20.00)
0.74 (20.00
0.64 (20.00
0.25 (20.0)
(.90(20001)
0.69 (22.01 0.14 (ann1)
06
7.75
(50)00)
0175 (20.01)
066 (90:01)
(22000))))
0.09 ce00001
0:00 (60.0)
0.89 (20-01)
0.62 (20.00))0)
0.22 (50.00)
scm
0.86 (40.01)
8.84 (60.82)
(.7.()
(9268)
0.20 (42055
0.64 (48J94)
6.78 (60,01)
0.71 (+0.800
0.59 (60.82)
0.93
0.30 (4R02)
mini-batch size of 128. For all DP training runs, we set the clipping norm c = 10 and choose the noise multiplier adaptively reach the overall privacy budget at the end of training. Note that, since we want to consider a consistent value of across all SC methods, we restrict the overall SN and DE. As explained in Section 3.2 this effectively enforces a reduction in for each individual training run due to sequential composition. Concretely, we train DE with 5 ensemble members and SN with target coverage levels Gurget E {0.1, 0.25, 0.5, 0.75, 1.0]. This leads to reduction of xe v/3 for each trained sub-model in both cases. We account for the precise reduction in the privacy parameter by increasing by the number steps of DP-SGD as measured by a Rényi DP accountant [Mironov] 2017 Yousefpour al. 2021]. All experiments are repeated over 5 random seeds determine the statistical significance of our findings. We document additional hyper-paramene parameters in Appendix B.]
both
Evaluation of selective classification techniques across privacy levels. We report our main results in Figure W where we display the accuracy-covertg trade-off for our full experimental panel. Overall, we observe that Selective Classification Training Dynamics (SCTD) delivers the best accuracy- coverage trade-offs. While this is consistent with non-private [Rabanser et al. [2022], we find that SCTD delivers especially strong performance at lower è levels. This suggests that leveraging training dynamics information is useful for performative selective classification under DP. As expected, based off of the discussion in Section Figure 3 shows that the performance of both Deep Ensembles (DE) and SelectiveNet (SN) suffers under DP, showing increasing utility degradation as decreases.
8

---

Table 2: Accuracy- selective classification performance. Across our panel of experi- ments, we find that decreasing leads to worse (i.e., higher) score, meaning that as & decreases the selective classification approaches all move away from the upper bound.
FashionMNIST
CIFAR-10
00
3
MSP
0,019 (=0.000)
0.023 (=0.000)
0.027 (+0.002)
0.041 (=0.001)
0.019 (=0.000)
0.105 (#0.002)
0.133 (#0.002)
0.205 (#0.001)
(20.000)
0.020 (=0.0011
0.026
(=0.002)
0.010 (20,000)
0.107 (40.000)
(20.000)
(20.002)
MCD0
0.020 (#0.002)
0.023 (+0.001)
0.030 (+0.003)
0.053 (#0.001)
0.021 (=0.001)
0.110000.000
0.142 (+0.000)
0.201 (+0.000)
DE
0.010 (+0.003)
0.027 (+0.002)
0.027 (+0.002)
(+0.000)
0.007 (=0.001)
0.099 (#0.002)
0.138 (+0.000)
0.222 (+0.000)
KNTD
0.007 (=0.001)
0.021 (=0.001)
0.023 (+0.003)
0.032 (=0.002)
0.009 (=0.002)
0.098 (+0.001)
0.107 (20.001)
0.152 (=0.001)
SN
0.008 (#0.002)
0.058 (+0.001)
0.056 (+0.001)
0.064 (+0.0022
0.015 (+0.000)
0.155 (+0.003)
0.154 (+0.002)
0.173 (+0.001)
SVIIN
GTSRB
NSP
0.008 (20.001)
0.020 (=0.001)
0.024 (+0.001) 0,040 (=0.001)
0.001 (=0.000)
0.006 (+0.002) 0.017 (20.000) 0.109 (=0.002)
SAT
0.004 (#0.000)
0.019 (40.000)
0.021 (+0.002)
0.044 (+0.002)
0.001 (=0.001)
0.008 (+0 0010
0.014 (++0000) 0.089 (+0.000)
(20.000)
0.019 (=0.001)
0.027 (+0.002)
0.069 (=0.001)
0.002 (=0.001)
(=0.001)
0.023 (#00001)
0.1 (00.001)
DE
0.004 (20.001)
0.018 (20.001)
0.022 (+0..00))
0.067 (s0.003)
0.001 (20.000)
0.003 (20.002)
0.027 (a0.0044)
0.127 (a0.002)
XWTD
(=0.001)
0.016 (=0.0001
0.018 (+00.002)
0.027 (#0.001)
0.011 (=0.002)
0.005 (=0,000) 0.009 (+0.000)
0.062 (=0.001)
SX
0.004 (=0.000)
0.055 (+0.001)
0.052 (+0.000)
0.096 (+0.000)
0.001 (=0.001)
0.050 (+0.004)
0.044 (+0.001)
0.091 (+0.004)
CIHAR-10 10
SVHN
GISRB
Accurcyy
1.00
1.000
1.000
6-
0.95
0.975
0.975
0.0072
0.0086
0.0028
0.0109
1.0
1.00
1.00
Accurecy
E=70
0.9
0.0211
0.75
0.0982
0.9
0.0156
0.95
0.0050
1.0
1.00
1.0
E=30
Accircy
0.9
0.0227
0.75
0.1074
0.9
0.0184
0.9
0.0092
1.0
1.0
1.00
== 10 Accuracy
0.8
0.0311
0.5
0.1521
0.8
0.0266
0.0621
0.0
0.5
1.0
0.0
0.5
0.0
0.5
1.0
0.0
0.5
1.0
Coverage
Covenge
Coverage
Coverage
Figure 4: Distance to accuracy-dependent upper bound for the SCTD method. We plot both the accuracy-coverage trade-off of SCTD, i.e., acc,(S, g). with a solid line and the upper bound acc(anu, (aman, e) with dashed line. The shaded region enclosed between the two curves corresponds to the normalzydd SC score Sam, (f. We observe that the score grows with stronger DP levels (shown by brighter colors), i.e., selective classification becomes harder at low es.
Recovering non-private utility by reducing coverage. Recall that one key motivation for applying selective classification to a DP model is to recover non-private model utility at the expense of coverage. We investigate this coverage cost in detail by examining how many samples a DP model can produce decisions for while maintaining the utility level of the respective non-pre non-private model (i.c., model trained on the same dataset without DP). The results are outlined in Table T For high (i.c., E 7) and moderate (i.e., 3) privacy budgets, we observe that a reduction of 20% 30% in data coverage recovers non-private utility. However, at low (i.e., E = 1) privacy budget we observe that dataset coverage degrades strongly on most datasets. In particular, we find that for CIFAR-10 (across all 8 values) and GTSRB (at 5 = 1), the coverage reduces to below 30%. This result showcases that, depending on the particular choice of e, recovering non-private model performance from a DP model can come at a considerable coverage cost. Moreover, this coverage cost varies widely across SC methods with SCTD leading to the lowest incurred loss in coverage by far.

---

FashionMNIST
CIFAR-10
SVHN
GTSRB
1.0
1.0
1,000
1,00
Accuncy
0.0097
0.9
0.0070
0.975
0.00-11
0.95
0.0009
0,0106
0.0233
0.0045
0.0048
0.9
1.0
1.0
1.0
1.00
7.0
Accuracy
0.9
0,0267
0
0.9
0,0180
0.75
0.0033
0.0269
1414
0.0229
0.0569
0.5
1.0
1-0 Accuroc
0.222]
0.1273
0.0667
0.1657
0.8
0,0513
0.5
0.1067
1.0
0.5
Coverage
Coverage
Coverage
Coverage
Figure 5: Sequential composition (DE) vs parallel composition (DE-PART) for deep ensembles. We observe that DE-PART (orange) under-perform. DE (blue) for selective classification across all E.
Disentangling selective prediction performance from base accuracy. Recall from Section 3.4 that the standard evaluation pipeline for selective classification is not suitable for comparing DP models across varying privacy guarantees. To overcome this issue, we compute the accuracy deeradded upper bound (Equation [5) for each experiment and measure how closely the achieved accuracy/coverage trade-off aligns with this bound as per Equation 6 We document these results computed over all datasets, SC methods, and e levels Table 2
We find that, as e decreases, all methods perform progressively worse. That is, for stronger privacy, all methods increasingly struggle to identify points they predict correctly on. Recall that this behavior is expected based on our discussion in Section 3.3 Again, we observe SCTD offering the strongest results, leading to the smallest bound deviation. To graphically showcase closeness to the upper bound, we further plot the accuracy-coverage trade-off' and the corresponding upper bound for each experiment with the SCTD method in Figure 4
Parallel composition with partitioned ensembles. As previously stated, Deep Ensembles under- perform under DP due composition. One potential mitigation strategy is to partition the data and train isolated models with no data overlap. This circumvents composition but also limits the utility of individual ensemble members as less data is available for training. We experiment with both setups and report results in Figure 5 Overall, these experimental results indicate that (i) partitioned deep ensembles lead to lower cull-coverage accuracy when compared to non-partitioned deep ensembles while (ii) at the same time being less performant in terms of selective classification performance.
5 Conclusion
In this work we have studied methods for performing selective classification under a differential privacy constraint. To that end, we have highlighted the fundamental difficulty of performing selective prediction under differential privacy, both via a synthetic example and empirical studies. To enable this analysis, introduced novel score that disentangles selective classification performance from baseline utility. While we establish that SC under DP is indeed challenging, our study finds that a specific method (SCTD) achieves the best trade-offs between SC performance and privacy budget.
Limitations. This work presents insights drawn from empirical results and we acknowledge that a more thorough theoretical analysis is needed for deeper understanding of the interplay between SC and DP. Also, we did not carefully investigate fairness implications beyond class imbalance. This connection to fairness requires special attention with past works showing that both DP and SC can negatively affect sensitive subgroups (Jones et al. 2020 Bagdasaryan et al., 2019
Future work. We believe that this work initiates a fruitful line of research. In particular, future work can expand on the intuition provided here to obtain fundamental bounds on selective classification performance in DP setting. Although we did not focus on this here, we believe that the ideas developed in this paper could help mitigate the trade-off's between privacy and subgroup faimesss.
10

---

Acknowledgements
We would like to acknowledge our sponsors, who support our research with financial and in-kind CIFAR through the Canada CIFAR AI Chair, DARPA through the GARD project, NSERC through the COHESA Strategic Alliance and a Discovery Grant, and the Sloan Foundation. Anvith Thudi is supported by Vanier Fellowship from the Natural Sciences and Engineering Research Council of Canada. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. We would further like to thank Relu Patrascu at the University of Toronto for the provided compute infrastructure needed to perform the experimentation outlined in this work. Stephan Rabanser additionally wants to thank Mohammad Yaghini, David Glukhov, Patty Liu, and Mahdi Haghifam for fruitful discussions.
contributions:
References
M. Abadi, Chu, Goodfellow, H. B. McMahan, I. Mironov, Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages 308-318, 2016.
E. Bagdasaryan, O. Poursaeed, and V. Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in neural information processing systems, 32, 2019.
R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464 473. IEEE, 2014.
T. Brawner and J. Honaker. Bootstrap inference and differential privacy: Standard errors for free. Unpublished Manuscript, 2018.
R. Challen, J. Denny, M. Pitt, L. Gompels, T. Edwards, and K. Tsaneva-Atanason Artificial intelligence, bias and clinical safety. BMJ Quality & Safery, 28(3):231-231 2019.
C. Covington, X. He, J. Honaker, and G. Kamath. Unbiased statistical estimation and valid confidence intervals under differential privacy. arXiv preprint arXiv:2110. 14465, 2021.
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory Cryplography: Third Theory of Cryplogruphy Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(344) 2014.
R. El-yaniv and Y. Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 1 11(53):1605-164) 2010. URL http:://mmr uRi.ntp://inntt.oor/ppppppee wttp://pp//pppppp/////
el al-yanivi0a.. html
G. Evans, G. King, M. Schwenzfeier, and A. Thakurta. Statistically valid inferences from privacy protected data. American Political Science Review, 2019.
L. Feng, M. O. Ahmed, H. Hajimirsadeghi, and A. H. Abdi. Towards better selective classification. In The Eleventh International Conference on Learning Representations, 2023.
C. Ferrando, S. Wang, and D. Sheldon. Parametric bootstrap for differentially private confidence intervals. In International Conference on Artificial Intelligence and Statistics, pages 1598-1618. PMLR, 2022.
Y. Gal and Z. Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference machine learning, pages 1050-1059, PMIR, 2016.
Y. Geifman and R. El-Yaniv. Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.

---

Y. Geifman and R. El- Yaniv. Selectivenet: A deep neural network with an integrated reject option. In International conference on machine learning, pages 2151-2159. PMLR, 2019.
Z. Ghodsi, S. K. S. Hari, Frosio, Tsai, A. Troccoli, S. W. Keckler, S. Garg, and A. Anandkumar. Generating and characterizing scenarios for safety testing of autonomous vehicles. arXiv preprint S.KV:2203.074033. 2021.
C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
D. Hendrycks and Gimpel. baseline for detecting misclassified and cut-of-distribution examples in neural networks. arXiv preprint wrXiv:/610.02136. 2016.
S. Houben, J. Stallkamp. J. Salmen, M. Schlipsing. and C. Igel. Detection of traffic signs in images: The German Traffic Sign Detection Benchmark. In International Joint Conference on Neural Networks, number 1288, 2013.
L. Huang, C. Zhang, and H. Zhang. Self-adaptive training: beyond empirical risk minimization. Advances in neural information processing systems, 13:19665- 2020.
E. Jones, S. Sagawa, P. W. Koh, A. Kumar, and Liang. Selective classification can magnify disparities acToss groups. arXiv preprint vxXiv:2010.14134 2020.
V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals. arXiv preprint 171.00071,.03908, 2017.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
J. Liu, Z. Lin, S. Padhy, D. Tran, T. Bedrax Weiss, and B. Lakshminarayanan. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. Advances in Neural Information Processing Systems, 33:7498-7512, 2020.
Z. Liu, Z. Wang, P. P. Liang, R. R. Salakhutdinov, L.-P. Morency, and M. Ueda. Deep gamblers: Learning to abstain with portfolio theory. Advances in Neural Information Processing Systems, 32, 2019.
I. Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEF, 2017.
H. Mozannar and D. Sontag. Consistent estimators for learning defer to an expert. International Conference on Machine Learning, pages 7076-7087. PMLR, 2020.
Y. Netzer, Т. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised unsupervised
feature learning. 2011.
A. Paszke, S. Gross, Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein,
L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. Vito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, Bai, and S. Chintala. PyTorch: An Imperative Style, High- High-Performance Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'chh Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. URL http://paperr http:://ppprrr..euiiippeee nwur cc/paper/ Saile-hiittt -ett--peeeoeeeeeeeeeeeeee-e learning 1iiggry.bbr....
-ta---ytorch----mmeatttttie pdf
S. Rabanser, A. Thudi, K. Hamidich, A. Dziedzic, and N. Papernot. Selective classification via neural network training dynamics. arXiv preprint arXiv:2205.1355 2022.
Shejwalkar, A. Ganesh, R. Mathews, O. Thakkar, and A. Thakurta. Recycling scraps: Improving private learning by leveraging intermediate checkpoints. arXiv preprint arX1v:2210.01864, 2022.
12

---

L. N. Vieira, M. O' O'Hagan, and C. O'Sullivan. Understanding the societal impacts of machine transla- tion: a critical review of the literature on medical and legal use cases. Information, Communication & Society, 24(11:1115-1534 2021.
M. Vijh, D. Chandola, V. A. Tikkiwal, and A. Kumar. Stock closing price prediction using machine learning techniques. Procedia computer science, 167:599-606 2020.
O. Williams and F. McSherry. Probabilistic inference and differential privacy. Advances in neural information processing systems, 23, 2010.
H. Xiao, K. Rasul, and Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, arXiv preprint vrXiv:1708.07747 2017.
A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad. M. Malek, J. Nguyen, S. Ghosh,
A. Bharadwaj, J. Zhao, G. Cormode, and Mironov. Opacus: User-friendly differential privacy library in Py PyTorch. arXiv preprint arXiv: /2298, 2021.
A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. Advances in Neural Information Processing Systems, 33:20073-2000 -20022, 2020.
13

---

A Additional Method Details
A.1 DP-SGD Algorithm
We provide a detailed definition of DP-SGD in Algorithm
Algorithm 2: DP-SGD AAbai et al. 2016
Require: Training dataset D, loss function L, learning rate y, noise multiplier a, sampling rate 4-
clipping norm c, iterations T.
Initialize 0g
2: for t -[T' do
1. Per-Sample Gradient Computation
4: Sample B₁ with per-point prob. from D
5: for E B, do
6: (xx))) Vo, ((0,,(),
7: end for
8: 2. Gradient Clipping
9: (ax))) <- (x(a:// max (1, 11 (1))2)
10: 3. Noise Addition
c
9t B. (r (0,
0.+1 02 19t
13: end for
14: Output 0r, privacy cost (c, 0) computed via a privacy accounting procedure
A.2 Selective Classification Method Details
Softmax Response (SR) The traditional baseline methods for selective prediction is the Softmax Response (SR) method (Hendrycks and Gimpell 2016 Geifman and HI- Yanivy 2017]. This method uses the confidence of the final prediction model as the selection score:
Jss (x, f) max ((x) cEC
While this method is easy to implement and does not incur any additional cost, has been found to be overconfident on ambiguous, hard-to-classify unrecognizable inputs.
SelectiveNet (SN) A variety of SC methods have been proposed that leverage explicit architecture and loss function adaptations. For example, SelectiveNet (SN) [Geifman and El- Yaniv 2019] modifies the model architecture jointly optimize (f.g) while targeting the model desired coverage level Curget- The augmented model consists of a representation function r X - R mapping inputs to latent codes and three additional functions: (i) the prediction function f R + RC for
TR. - [0, 1] representing continuous approximation of the accept/reject decision for æ;; and (iii) an additional auxiliary function L TRC trained for the unconstrained classification tasks. This yields the following losses:
the classification task targeted Carget: (ii) the selection function
C = =aaf, + (1 - Cb
(8)
Li.9 = DM l(f ((xm). 3m) + X c (f,9)²
(9)
cov(f.9)
M
Cn
Σ
(lh r(xm),
(10)
M m=1
The selection score for particular point is then given by:
(an (g o rzx) exp(g r()))
(11)
Self-Adaptive Training (SAT) Alternatively, prior works like Deep Gamblers Liu et al., 2019 and
Self-Adaptive Training (Huang et al. 2020 have also considered explicitly modeling the abstention
14

---

class 1 and adapting the optimization process to provide a learning signal for this class, For instance, Self-Adaptive Training (SAT) incorporates information obtained during the training process into the optimization itself by computing and monitoring an exponential moving average of training point predictions over the training process. Samples with high prediction uncertainty are then used for training the abstention class. To ensure that the exponential moving average captures the true prediction uncertainty, an initial burn-in phase is added to the training procedure. This delay allows the model to first optimize the non-augmented, i.e. original C-class prediction task and optimize for selective classification during the remainder of the training process. The updated loss is defined as:
M (ti, Pt.. Pt.y. + (1 tt,y log
(12)
The rejection/abssention decision is then determined by the degree of confidence in the rejection class:
9Sxr (a., f) = f(())++
(13)
Deep Ensembles (DE) Finally, ensemble methods combine the information content of M models into single final model. Since these models approximate the variance of the underlying predic- tion problem, they are often used for the purpose of uncertainty quantification and, by extension, selective prediction. The canonical instance of this approach for deep learning based models, Deep Ensembles (DE) [Lakshminarayanan et al., 2017], trains multiple models from scratch with vary- ing initializations using proper scoring rule and adversarial training. Then, after averaging the predictions made by the model, the softmax response (SR) mechanism applied:
(1e( f) max cEC M
1
Σ (x))
(14)
Monte-Carlo Dropout (MCDO) To overcome the computational cost of estimating multiple models from scratch, Monte- Carlo Dropout (MCDO) [Gal and Ghahramani 2016] allows for bootstrapping of model uncertainty of a dropout-equipped model at test time. While dropout is predominantly used during training enable regularization of deep neural nets, it can also be used at test time to yield random sub-network of the full neural network. Concretely, given a model f with dropout-probability we can generate M random sub-networks at test-time by deactivating fraction of nodes. For given test input æ we can then average the outputs over all models and apply softmax response (SR):
9иcnc (x, 0)
max CEC
(15)
7=1
Selective Classification Training Dynamics (SCTD) Another ensembling approach that has recently demonstrated state-of-the-art selective classification performance is based on monitoring the model evolution during the training process. Selective Classification Training Dynamics (SCTD) [Rabanser ct al. 2022 records intermediate models produced during training and computes disagreement score of the intermediate predictions with the final prediction for any test-time input æ::
Jacro (a:, f) = Σ (2, with ar(xr, 1] - {
fe, (a) + for (x)
k T
6
Vt
(16)
otherwise
SCTD only observes the training process and does not modify the model architectureetraining ohjpaa
B
Additional Experimental Details
B.1
Hyperparameters
In this section, we document additional hyper- ppper-parameter choices. For Self-Adaptive Training (SAT). we set the pre-training epochs to 100 and momentum parameter 0.9. For Selective Classification Training Dynamics (SCTD), we set the weighting parameter & = 3 and consider checkpoints at a batch resolution. For Monte-Carlo Dropout, we set the dropout probability to 0.1. Entropy regularization suggested in Feng et al. (2033 is employed with 8 0.01.
15

---

Pg
P0 0.25
Pg
Pg 0.01
1.0
1.0
1.0
1.0
Agammyy
0.9
0.9
0.8
0.5
0.0
0.5
1.0
0.0
0.5
1.0
0.5
1.0
0.0
0.5
1.0
1.00
1.0
1.0
8 7:
Accintt
0.75
0.5
0.5
0.5
0.50
0.0
0.0
0.0
0.0
0.5
1.0
0.5
1.0
1.0
1.0
1.0
Ausurac
C-
0.5
0.5
00-
0.0
0.5
1.0
0.0
0.5
1.0
0.5
1.0
0.0
0.5
1.0
1.0.4
1.0
100
Aucuracy
C- c-1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.5
1.0
0.5
Coverage
Choszage
Cooarage
Cheurage
Figure 6: Inducing class imbalance CIFAR-10. We train multiple CIFAR-10 10 models across privacy levels and sampling probabilities for class given by pn- We plot the accuracy/coverage trade-off as well at the exact coverage level at which any point from the minority class is accepted. The accuracy-coverage trade-off for the full dataset is given by the dashed line while the trade-off for the minority group only is given by the solid line. Blue vertical lines show correctly classified points, orange points show incorrectly classified points. Non-private models accept correct points first and do at the end of the coverage spectrum (i.e., majority points are accepted first). As we increase privacy (i.c., decrease E), the model is increasingly unable to rank minority examples based on prediction correctness and even accepts incorrect points first. Moreover, the accuracy of the model on the minority class decreases with stronger DP. These effects are especially strong for small sampling probabilities.
B.2 Class Imbalance Experiments
We provide additional experiments on the effect of class imbalance to extend our intuition from Section 3.3] To that end, we take two data sets from our main results, namely CIFAR-10 and RashionMNiS' and produce four alternate datasets from each dataset. These datasets feature various degrees of class imbalance with po (0.5, 0.25, 0.1, 0.01) specifying the sampling probability for class O. All other classes maintain a sampling probability of 1. We then train the same model as described in Section 4 and apply the softmax response SC algorithm.
We document these results in Figures 6 and 7 For = oo, we observe the expected gains from SC:
minority points accepted towards the end of the coverage spectrum [Jones et al. 2020] and correct points are accepted first. This effect is independent of the sampling probability pa- As we decrease the budget we observe that (i) the acceptance of minority groups starts to spread over the full coverage spectrum; (ii) the accuracy on the subgroup increasingly deteriorates with smaller e, and (iii) wrongful overconfidence the minority reverses the acceptance order at low sampling probabilities po (i.e., incorrect points are often accepted first). These results indicate that employing selective classification on private data can have unwanted negative effects in the presence of subgroups. Future work should investigate this connection more thoroughly.
B.3 Upper Bound Reachability
In Equation 5 we have introduced an upper bound on the selective classification performance on a model with full-coverage accuracy Arull. We now present simple experimental panel across varying
16

---

Pg
Pg 0.25
Po 0.1
Pb
1.0
1.0
1.0
1.0
Accunyy
0.5
0.0
0.5
1.0
0.5
1.0
0.0
1.0
1.00
1.00
7: AcciaaO
0.5
0.5
0.6
0.0
0.0
0.0
0.5
1.0
1.0
1.0
0.0
1.0
0.5
1.0
0.0
1.0
0.5
1.0
1.00
1.00
1.0 Accina
0.8
0.5
0.5
0.0
0.0
0.5
Chucrage
Civerage
Cuverags
Civengge
Figure 7: Inducing class imbalance on FashionMNIST. Same insights in Figure 7
Upper Accuracy-Coverage Bound
Achieved Accuracy-Coerrge Tradeoff
Accunacy
0.5
Covenge
Cowerage
Covengee
Coverage
Covernge
Covenae
Figure 8: Upper bound matching experiment. The experiment as described Section the optimal bound exactly across multiple full-coverage accuracy levels.
B.3
matches
full-coverage accuracy levels showing that this bound in fact reachable by a perfect selective classifier.
assume a binary classification setting which we generate a true label vector y E {0, 1 +o with balanced classes, i.e., no = nı where corresponds to the number points labeled as 0 and n1 corresponds to the number points labeled as Then, based on a desired accuracy level amal we generate prediction vector p which overlaps with y for fraction of afull- Finally, sample scoring vector s where each correct prediction is assigned a score 8; U4,0.5 and each incorrect prediction is assigned score s; U0.5,1 Here, Ha corresponds to the uniform distribution on the interval [a, b). This score is clearly optimal since thresholding the scoring vector s at 0.5 perfectly captures correct/incorrect predictions: all 8; 0.5 correspond
correct prediction, while all 8; 2 0.5 correspond to an incorrect prediction. Computing the accuracy/coverage trade-off this experiment, across various utility levels, matches the bound exactly.
17


Reviews:
[{"review_id": "9uXnktyIo6", "reviewer": "Reviewer_9iMW", "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:\n\n* An existing SC method that uses checkpoints is suitable under DP.\n* A novel accuracy-dependent selective classification score proposed by the authors helps compare selective classification performance across DP levels without explicit accuracy alignment.\n* Selective classification performance degrades with stronger privacy.\n* Recovering utility can come at a considerable coverage cost under strong privacy requirements.\n", "questions": "Please improve the explanation of the proposed metrics (Definition 3.1).", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "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. \n* 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.\n* 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.\n\nGoing beyond this, I think a more rigorous theoretical analysis and characterization between the trade-offs of SC and DP could be an interesting direction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their strong positive assessment of our work! We provide responses inline below.\n\n> 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.\n\nWe provide some more intuition for the bound: A perfect selective classifier accepts all correct points first and all incorrect points last. That is, for as long as possible, we want to maintain a perfect accuracy level of 100% as we accept an increasing number of points. We can only maintain perfect accuracy for as long as there still exists a data point that is classified correctly by the underlying model. This stops being the case once we have reached a coverage of $a_\\text{full}$, where $a_\\text{full}$ corresponds to the full-coverage accuracy. This is since an accuracy of $a_\\text{full}$ means that a fraction $a_\\text{full}$ of predictions are correct and a fraction $1 - a_\\text{full}$ of predictions are incorrect. In the remaining part of the coverage spectrum, i.e. for coverage larger than $a_\\text{full}$, the selective classifier now needs to accept all the incorrect points, which leads to a strictly monotonic decrease in accuracy. In particular, the full-coverage accuracy needs to be spread equally over the remaining accuracy spectrum which leads to $\\frac{a_\\text{full}}{c}$ as long as $a_\\text{full} < c \\leq 1$. We have updated the relevant lines in the paper to include this additional intuition for the coverage region larger than $a_\\text{full}$ and hope that this increases clarity. \n\nWe would further like to point out to the reviewer that Appendix B.3 (Figure 6 in particular) contains an upper bound reachability experiment. This experiment demonstrates that an optimal selective classification mechanism (i.e. a score that has a perfect acceptance ordering of test points) matches the bound exactly, showing that our formalism is indeed correct.\n\n> 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.\n\nWe agree with the reviewer that a more thorough theoretical treatment of the connection between selective prediction and differential privacy would be an exciting direction to pursue as part of future work. In particular, as pointed out to _reviewer atra_ below, we imagine that connecting selective classification and differential privacy via the membership inference angle could be a promising direction.\n"}, {"review_id": "E2KvEJPpBX", "reviewer": "Reviewer_sqFp", "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.", "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?\n\nIn 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. ", "limitations": "Yes, the authors have sufficiently addressed the impact of their work. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "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. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback on our work and address individual concerns below.\n\n> I think additional attention to presentation is necessary to clarify the main contributions of the paper. [...]\n\nTo the best of our knowledge, and as the reviewer acknowledges themselves in the _Strengths_ section, our work is the first to examine the connection between privacy and selective prediction. In particular, we examine both (i) how DP constraints can affect SC performance; and (ii) how SC methods in turn affect DP guarantees. Not only do we establish this connection explicitly for the first time, but we also highlight a challenge in and propose a solution to the evaluation of selective prediction under DP. Further, we provide a comprehensive set of experimental results across common datasets quantifying (i) the exact drop in performance; as well as (ii) the loss in coverage needed to regain non-private utility. We believe that this work can help establish a bridge between the fields of selective classification and privacy with the goal of better understanding the interplay between these important sub-disciplines of trustworthy ML.\n\n> The necessity for new evaluation metrics is also still unclear to me. [...] 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?\n\nThe reviewer is right that the purpose of Equation 4 is not to align accuracy; the purpose of Equation 4 is to evaluate the performance of a given selective classifier $(f,g)$. However, as noted by previous works [1], a meaningful comparison between different selective classifiers using Equation 4 is only possible if the accuracy on the full test set is aligned across all selective classifiers. That way, the effect of accuracy is fixed and Equation 4 solely measures SC performance. \n\nIn non-private models, accuracy alignment is achieved via early stopping. Concretely, all selective classifiers are accuracy-matched to the worst performing model and models that could achieve a better utility level are stopped early in training. However, this approach does not carry over to private models. Private models trained using DP-SGD are iteratively trained to exhaust a desired privacy budget at the end of training. Early stopping a private model yields a more private model than was in fact targeted by the optimization process. However, it is important to ensure a consistent privacy level at which we evaluate private models. Moreover, training private models at varying $\\varepsilon$ levels leads to decreasing accuracy as $\\varepsilon$ decreases. \n\nThese challenges of properly evaluating private models necessitate a new performance metric for selective classification, which is a key contribution of this paper. Although we could compute Equation 4 for all of our experiments on private models, it would be impossible to disentangle the effect of a drop in accuracy from a drop in SC performance; the score would trivially show a decrease in performance as a result of a loss in model utility due to privacy. __But just because model A is less accurate overall than model B, that does not necessarily mean that the model is less capable of identifying which examples it knows to classify well and which examples it doesn’t know how to classify well.__ We have made sure to strengthen this intuition throughout the paper.\n\nThe proposed metric in Equation 6 circumvents this problem by computing closeness to an upper bound on the SC performance. This upper bound measures the optimal SC performance for a model with the particular full-coverage accuracy constraint of the underlying model. Post-hoc accuracy alignment is not required here as the bound is individual to the model and dependent on the overall model accuracy. Finally, not only does this metric allow us to quantify selective classification performance under DP, but it also allows for the comparison of non-private models across full-coverage accuracy levels. For instance, models with different accuracies might arise as a consequence of restrictions to the hypothesis class. As such, this metric can be also applied in more general selective prediction works that do not consider privacy.\n\n[1]: Feng, Leo, et al. \"Towards Better Selective Classification.\" The Eleventh International Conference on Learning Representations. 2023.\nQuestions:\n\n> 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. \n\nThanks for pointing this out! We have added the following sentence to the caption to increase clarity:\nThe shaded color regions indicate degrees of confidence in the red (majority) or blue (minority) class, respectively. Stronger colors correspond to more confident predictions.\n\n> 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.\n\nWe have improved the caption of Figure 4 to clarify the role of the orange and blue lines in particular. All vertical lines shown in the plots constitute samples from the minority class. If a line is shown in blue, then it means that it is classified correctly, if it is shown in orange then it is classified incorrectly. The exact position of the vertical line on the x axis signifies the coverage level at which the minority point is accepted. This plotting technique allows us to inspect the behavior of selective classification for every point from the minority class and derive general distribution patterns over the coverage spectrum.\n\n---\n**We hope that we have addressed the reviewer’s concerns and that the reviewer considers raising their score as a result.**\n"}, {"review_id": "BBDJUK0Hfj", "reviewer": "Reviewer_atra", "summary": "This paper investigates the relationship between selective classification (SC) and differential privacy (DP).\nFirst, the authors consider various SC approaches and if they incur additional privacy/utility costs under the constraint of DP.\nThey 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.\nFinally, the authors introduce a new metric to evaluate SC under DP that takes into account the baseline accuracy of the model.\nAn 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.\nOverall, SCTD (an SC approach that abstains based on the model's disagreement at various checkpoints) is shown to perform the best.", "questions": "- Can the authors comment on the DE approach using the dataset partitioning idea? Perhaps they have tried it.\n- 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?\n", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n- The experimental evaluation contains many different SC techniques. This seems like a large implementation effort and a nice contribution to the community.\n- The example with class imbalance gave a nice intuition for the problem with SC under DP.\n- 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\nThe 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.\n\nI 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).\n\n## DE evaluation\nWhile 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?\n\n## Delta too high\n$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.\n\n## Typos/Clarity\nOverall this paper was incredibly well written. However, below I give a couple of trouble spots that could be made more clear.\n- Line 64: \"more stringent than targeted privacy level\" is clunky/hard to parse\n- 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.\n- Line 203: Incorrect acronym for deep ensembles.\n- Line 215: mechanisms? or models? A mechanism is used to train a model, so I think the model makes more sense.\n- Line 229: This first sentence is somewhat confusing. Specifically, \"free from its bias towards accuracy is to align...\" is a lot to parse.\n- 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).\n- Figure 2: not sure if error bars could be added here, although it might make it too hard to read\n- Table 1: it should be made clear what the $\\pm$ represents. I assume a confidence interval but at what $\\alpha$?\n- 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? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed assessment of our work and address individual concerns below.\n\n> Grouping of SC techniques\n\nThe main reason for a method to fall into the composition category is that these methods require multiple passes over the data (and hence lead to a higher needed privacy budget). While most methods SC methods modify the loss or the architecture, DP-SGD is an optimizer and protects privacy independent of the exact loss function. SelectiveNet is a notable exception because it requires a fixed targeted coverage level at training time. However, in order to obtain a full characterization of the accuracy-coverage spectrum (which is needed for comparison with other methods), we have to train multiple models. This is also the reason why Figure 2 shows the performance of SelectiveNet with discrete dots and dashed lines. We have made sure to clarify the reasons for the grouping in Section 3.2.\n\n> DE evaluation\n\nThis is an interesting and relevant suggestion! The reviewer is right that partitioning the dataset and training isolated models on these subsets would bypass composition and alleviate the need for lowering $\\varepsilon$ on a per-ensemble-member basis. However, as also rightfully pointed out by the reviewer, the partitioning would heavily decrease overall model utility. To showcase this effect, we ran our full experimental panel again but partitioned the dataset into 5 subsets and trained the same set of DP models as in the main experimental section of the paper. We provide a corresponding figure in the PDF document associated with this rebuttal (Figure 1). This figure follows the same style as Figure 3 in the main paper but shows the accuracy-coverage tradeoff and upper-bound closeness for both standard deep ensembles ($\\texttt{DE}$) and partitioned deep ensembles $\\texttt{DE-PART}$.\n\nOverall, these experimental results indicate that (i) the partitioned deep ensembles (orange) lead to lower full-coverage accuracy when compared to non-partitioned deep ensembles (blue) while (ii) at the same time being less performant in terms of selective classification performance. We have included this result together with a discussion in the appendix of the paper.\n\n> Delta too high\n\nThanks for catching this! Our experimental assumptions were based on [2], which claims that for a dataset with order $10^N$ samples $\\delta$ should be set to $\\delta = 10^{-N}$. We concur that this value should have been set to $\\delta = 10^{-(N+1)}$ instead, as seems to be more common in the literature. We have run our experimental panel again with this setting and are happy to report that our results continue to hold even with a smaller delta.\n\n> Line 64: [...]\n\nWe have rephrased this sentence as follows: In particular, accuracy-aligning multiple DP models via early-stopping frequently leads to a privacy level that is more stringent than targeted by the DP mechanism, rendering the intended comparison impossible.\n\n> Line 124: [...]\n\nWe clarify that $c$ always refers to a specified (desired) coverage level while $\\text{cov}_\\tau(f,g)$ refers to the computed coverage at $\\tau$.\n\n> Line 229: [...]\n\nWe have rephrased this sentence as follows: The default approach of using the SC performance metric introduced in Equation 4 without its accuracy bias is to align different SC approaches/models at the same accuracy.\n\n> Line 246: [...]\n\nWe have added a corresponding remark to the caption of Table 2 to make this more obvious to the reader.\n\n> Figure 2: [...]\n\nWe experimented with adding an additional shaded region to emphasize seed randomness but indeed found that it would drastically decrease reliability of the plot. We do however provide $1 \\cdot \\sigma$ regions around all mean results across all experimental tables.\n\n> Table 1: [...]\n\nAs we state in lines 295-296, we conduct all experiments over a total of 5 random runs. Tables 1 and 2 therefore report mean results over all random runs with a $1 \\cdot \\sigma$ interval (with sigma being the standard deviation over the random runs). We have made sure to emphasize this in the captions of Tables 1 and 2.\n\n> Line 203: [...]\n\n> Line 215: [...]\n\n> In Tables 1 & 2, the labels seem quite off. [...]\n\nWe fixed these in our revised paper. \n\n> Although SC does not affect the privacy guarantee, does it increase privacy leakage? [...]\n\nThis is a very interesting question! In fact, a similar question has been preliminarily explored in the Private Aggregation of Teacher Ensembles (PATE) [1] class of models. As a short summary, PATE trains an ensemble of teacher models and transfers the knowledge to a student model. Privacy is provided by training teachers on disjoint data and by a noisy aggregation of teacher answers. A rejection mechanism is employed on the class voting histogram [2, Alg 1]. A point is rejected when there is large disagreement in the noised aggregation of predictions across teachers, otherwise the noised prediction is released. The privacy budget is spread over both the initial consensus checking phase and the prediction release phase. Hence, some points only incur the rejection privacy budget while other points incur both the rejection check and prediction release budget. A rejection decision therefore can therefore provide some signal that could be used by an MI adversary.\n\nThat said, it is not evidently clear how to apply the same chain of reasoning to models that are trained using DP-SGD (which has a single $\\epsilon$ budget). Although membership inference and selective classification often rely on very similar mechanisms (e.g. logit or softmax thresholding), the precise connection between MI (and privacy leakage in general) and selective classification has not been established yet. This should be investigated in future work.\n\n**References:**\n\n[1]: Papernot, Nicolas, et al. \"Semi-supervised knowledge transfer for deep learning from private training data.\" ICLR 2017.\n\n[2]: Papernot, Nicolas, et al. \"Scalable private learning with pate.\" ICLR 2018."}, {"review_id": "omdkpNUfCT", "reviewer": "Reviewer_rhFq", "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.", "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].\n- 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.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback on our work and address individual concerns below.\n\n> 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)$. \n\nWhile we agree with the observation that differential privacy can be ensured in a variety of ways, DP-SGD has become the de-facto standard for training differentially private deep learning models. This is in part due to its ability to be applied to non-convex models with arbitrary architectural modifications and loss functions. In contrast, output perturbation is only useful for convex models, and we are dealing with non-convex models inherently in our work. Hence, the only algorithms at our disposal are noisy first order or second order methods. We further emphasize that selective prediction is especially important for deep learning models as the robustness of deep neural nets constitutes a major open problem. Since DP-SGD is the most flexible and widely used approach to ensure privacy in deep learning, we believe that it is most important to focus our work on the interplay between selective classification and DP-SGD in particular.\n\n> 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.\n\nThe work presented in [1] considers the functional mechanism to ensure $\\epsilon$-DP. However, the noise injection from the functional mechanism (noising weights and objective perturbation) requires strong convexity assumptions [2]. This precludes the functional mechanism to be applied directly to deep neural networks which feature non-convex loss landscapes. As we argue in the previous point, the focus of our work is to study the interplay of differential privacy and selective classification for modern deep neural nets.  \n\n[2]: Ponomareva, Natalia, et al. \"How to dp-fy ml: A practical guide to machine learning with differential privacy.\" Journal of Artificial Intelligence Research 77 (2023): 1113-1201.\n\n> 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].\n\nFull-coverage accuracy refers to the accuracy of a trained model on the entire (i.e., full) test set, formally $a_\\text{full} = \\text{acc}_{c=1}(f,g)$ (using the definition from Equation 4). We have made sure to state this explicitly in our revision to avoid ambiguity.\n\n> 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_\\text{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_\\text{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.\n\nThe advantage of the accuracy-normalized selective classification score $s_{a_\\text{full}}(f,g)$ from Definition 3.2 is the fact that it constitutes a performance measure free from accuracy alignment. As we explain in the second paragraph of Section 3.4, accuracy alignment is not possible under DP which necessitates a new performance metric. This new metric, $s_{a_\\text{full}}(f,g)$ computes how close the observed accuracy-coverage tradeoff aligns with the computed upper bound on the selective classification performance (Equation 5). As such it captures the area enclosed between the achieved accuracy-coverage tradeoff and the corresponding upper bound. As we state in Definition 3.1, $a_\\text{full}$ is fixed (also see response to previous point) and determined by $(f,g)$. This performance metric allows us to compare selective classification performance across privacy levels and further quantifies closeness to a perfect selective classifier. \n\nIt would be appreciated if the reviewer could elaborate on why they believe that the score computed in Equation 6 can be negative. Since we subtract the actual achieved accuracy at a certain coverage level from the computed upper bound at that coverage level, it is ensured that the integrand is non-negative. Subsequent integration of non-negative integrands further guarantees non-negativity. \n\n---\n**We hope that we have addressed the reviewer’s concerns and that the reviewer considers raising their score as a result.**\n"}]

Author rebuttal:
We thank all reviewers for their assessment of our work and have performed a few changes to improve our paper as a result of their feedback. 

First and foremost, we were happy to see that **reviewers found our paper well written, that our idea of examining the connection between differential privacy and selective classification is novel and interesting, and that our experimental suite is comprehensive**. 

Among other points, we have addressed the following key points of criticism in particular:

- **Relevance of a new performance metric for SC under DP**: We provide a more detailed reasoning as to why a new performance metric for SC is needed under DP. As accuracy alignment is not possible across models with various privacy budgets, established methods that rely on accuracy alignment fail. Our newly proposed metric computes the distance of the achieved accuracy-coverage tradeoff to an upper bound on the attainable SC performance (which we also propose in this work).
- **Additional results on partitioned deep ensembles**: We show that deep ensembles trained on partitioned data are inferior to deep ensembles trained on a single dataset but with DP composition.  
- **Reasoning behind the grouping of SC methods**: We explain the grouping into post-processing and composition approaches in more detail, highlighting that taking multiple passess over the data is the decisive factor for a method to fall into the composition category.
- **Reliance on DP-SGD vs other ways of ensuring DP**: We remark that DP-SGD is the most widely used approach to ensure DP in deep neural nets and that alternate methods based on the functional mechanism or on output perturbation are not applicable in our models due to convexity assumptions.

We are happy to further engage with reviewers as part of the discussion phase and hope that the reviewers consider raising their scores.


Meta-review: This work is the first to investigate the interplay between selective classification and differential privacy. Reviewers agreed that this is an interesting topic, and the experiments are thorough and convincing. Very few strong weaknesses were highlighted. I tend to agree overall, and recommend the paper for acceptance.
Decision: Accept (poster)