A Learning Based Hypothesis Test for Harmful Covariate Shift
Authors: Tom Ginsberg
Zhongyuan Liang
Rahul G Krishnan
Venue: ICLR 2023 poster (2023)
Keywords: Covariate Shift
Distribution Shift
Trustworthy Machine Learning
Statistics

Abstract: The ability to quickly and accurately identify covariate shift at test time is a critical and often overlooked component of safe machine learning systems deployed in high-risk domains. While methods exist for detecting when predictions should not be made on out-of-distribution test examples, identifying distributional level differences between training and test time can help determine when a model should be removed from the deployment setting and retrained. In this work, we define harmful covariate shift (HCS) as a change in distribution that may weaken the generalization of a predictive model. To detect HCS, we use the discordance between an ensemble of classifiers trained to agree on training data and disagree on test data. We derive a loss function for training this ensemble and show that the disagreement rate and entropy represent powerful discriminative statistics for HCS. Empirically, we demonstrate the ability of our method to detect harmful covariate shift with statistical certainty on a variety of high-dimensional datasets. Across numerous domains and modalities, we show state-of-the-art performance compared to existing methods, particularly when the number of observed test samples is small.

Published as a conference paper at ICLR 2023
A LEARNING BASED HYPOTHESIS TEST FOR HARMFUL COVARIATE SHIFT
Tom Ginsberg & Zhongyuan Liang & Rahul G. Krishnan Department of Computer Science
University of Toronto Toronto, ON M5S IA1 {t (tomginsberg, zhongyuan, rahulgk) how.:lkkkkec.ttoootoco.oo.
ABSTRACT
The ability to quickly and accurately identify covariate shift test time is critical and often overlooked component of safe machine learning systems deployed in high-risk domains. While methods exist for detecting when predictions should not be made on out-of citto--distribution test examples, identifying distributional level differences between training and test time can help determine when a model should be removed from the deployment setting and retrained. In this work, we define harmful covariate shift (HCS) as a change in distribution that may weaken the generalization of predictive model. To detect HCS, we the discordance between an ensemble of classifiers trained to agree on training data and disagree test data. We derive loss function for training this ensemble and show that the disagreement rate and entropy represent powerful discriminative statistics for HCS. Empirically, we demonstrate the ability of our method detect harmful covariate shift with statistical certainty on a variety of high-dimensional datasets. Across numerous domains and modalities, we show state-ofttee ahtthee-rtt performance compared to existing methods, particularly when the number of observed test samples is small
INTRODUCTION
Machine learning models operate on the assumption, albeit incorrectly that they will be deployed on data distributed identically what they were trained on. The violation of this assumption is known distribution shift and can often result in significant degradation of performance [Bickel jet al., 2009)] Rabanser et al.) 2019 Otles et al., 2021 Ovadia et al.) [019]. There are several cases where mismatch between training and deployment data results in very real consequences human beings. In healthcare, machine learning models have been deployed for predicting the likelihood of sepsis. Yet, [Haib et al. 202T) show, such models can be miscalibrated for large groups of individuals, directly affecting the quality of care they experience. The deployment of classifiers the criminal justice system (Hao) 2019]. hiring and recruitment pipelines (Dastin] 2018 and self delv-driving cars [Smiley] 2022) have all seen humans affected by the failures of learning models. The need for methods that quickly detect, characterize and respond to distribution shift is, therefore, a fundamental problem in trustworthy machine learning. We study a special case of distribution shift, commonly known covariate shift, which considers shifts only in the distribution of input data IP() while the relation between the inputs and outputs PPY XX) remains fixed. In a standard deployment setting where ground truth labels are not available, covariate shift is the only type of distribution shift that can be identified.
For practitioners, regulatory agencies and individuals to have faith in deployed predictive models without the need for laborious manual audits, we need methods for the identification of covariate shift that are sumple-efficient (identifying shifts from a small number of samples), informed (identifying shifts relevant to the domain and learning algorithm), model-agnostic (identifying shifts regardless of the functional class of the predictive model) and statistically sound (identifying true shifts while avoiding false positives with high-confidence).
"ooee available httpttt/////. //gi httpggit............eaoaoaeeee rgkn ab/ httpgkktt///eeeee////// detectron

---

Published as a conference paper at ICLR 2023
We build off recent progress in understanding model performance under covariate shift using the PQ-Iearning framework [Goldwasser et al., 2020], a framework for selective classifiers that may either predict on reject given sample, that provides strong performance guarantees arbitrary test distributions. Our work uses and extends PQ-learning to develop a practical, model- hypothesis test, named the Detectron, identify potentially harmful covariate shifts given any existing classification model already in deployment.
Our work makes the following key contributions:
We show how construct ensemble of classifiers that maximize out-of-domain disagreement while behaving consistently in the training domain. We propose the disagreement cross entropy for models learned via continuous gradient-based methods (e.g., neural networks), well
generalization for those learned via discrete optimization (e.g., random forest).
We show that the rejection rate and the entropy of the learning ensemble can be used to define a model-aware hypothesis test for covariate shift, the Detectron, that in idcalized settings can provably detect covariate shift.
On high-dimensional image and tabular data, using both neural networks and gradient boosted decision trees, our method outperforms state-of-the-art techniques for detecting covariate shift, particularly when given access to as few as ten test examples.
Finctine g disugen (Preenn c
Daaeremenn Ratee
P
Pretzain mockel I with (Perd)) P
Compare disegroment mite Do, 1l0 fiell
Cocstrain nld to agrre with ff the teaining net
P
dg Leg ((9)s) f(x)) as test fot covariate shift P
Hopaslhand Test Not up
Fiuctune / 2d to diliagnn un absurved Cata (X).... Nel Ox
Ha: dp
G4
Covuriate Shift
P of Q
Figure 1: Overview of the Detectron: Starting with basc classifier f trained on labeled samples from distribution P we train new Constrained Disagreement Claxsifiers (CDCs) 9" and g on a small sets of unseen samples from P as well as a unknown distribution Q. CDCs aim to maximize classification disagreement on unseen data while constrained classify consistently with f on their original training set. The rate & that CDCs disagree is powerful and sample efficient statistic for identifying covariate shift P o Q.
BACKGROUND AND RELATED WORK
Covariate Shift Detection. Covariate shift is the tendency for distribution at test time Prest (4) to differ from that seen during training Puain (1)) while the underlying prediction concept remains fixed e.g. Prrin (z) = Prest (y) (r). Many methods for detecting shift apply dimensionality reduction followed by statistical hypothesis tests for distributional differences in the outputs (from reference and target) RRabanser et al.) 2019). Rabanser et al.) show that using the softmax outputs a pretrained classifier as low dimensional representations for performing univariate KS-tests, method known as black box shift detection (BBSD) [Lipton et al. 2018), is effective at confidently identifying several synthetic covariate shifts imaging data (e.g. crops, rotations) given approximately 200 i.i.d samples. However, applying statistical tests to non-invertible representations of data can never guarantee to capture arbitrary covariate shifts, there may always exist multiple distributions that collapse the
same test statistic (Zhang et al., 2021]. Kifer et al. [2004); Ben- et al.) (2066) introduce some of the earliest learning theoretic approaches for identifying and correcting for covariate shift based on discriminative learning with finite samples. More recent approaches for covariate shift detection including classifier two sample tests [Lopez-Paz and Oquab) (017], deep kernel MMD [Liu et al.. 2020) and H-Divergence [Zhao et al.) 2022] rely analyzing the outputs of unsupervised learning models (see Appendix (sseendix(ubbsctionn ssussection E.3 for more details). In our work we take a transductive learning approach and construct method to directly use the structure of a supervised classification problem to improve the statistical power for detecting shifts.
Out of Distribution Detection. Out of distribution (OOD) detection focuses on identifying when
specific data point admits low likelihood under the original training distributions (Pirain( (x') ss 0)-
useful tool to have inference time. Ren et al. 2019) Morningstar et al. [002 represent
2

---

Published as a conference paper at ICLR 2023
broad class of work that uses density estimation to pose the identification of covariate shift as anomaly detection. Others, including ODIN [Liang et al. 2018). Deep Mahalanobis Detectors [Lee] et al., 2018 and, Gram Matrices (Sastry and Oore 2020 directly use the predictive model (c.g. information from the intermediate representations of neural networks). The majority of modern methods in this space have been designed exclusively for deep neural networks, an uncommon modelling choice particularly for tabular data [Borisov et al. 2022]. Related to OOD, is the task of estimating sources of uncertainty in model predictions [Lakshminarayanan et al. 2017 Ovadia et al. 2019]. Naturally, uncertainty should be large when samples are OOD, however [Ovadia et al. 2019] perform large-scale empirical comparison of uncertainty estimation methods and find that while deep ensembles generally provide the best results, the quality of uncertainty estimations, regardless of method, consistently degrades with increasing covariate shift.
Selective Classification and PQ Learning. Selective classification concerns building classifiers that may either predict on or reject on test samples [Geifman and Hi- EI-Yaniy Yaniv, 2019). Recent work by [Goldwasser et al. 2020] develops formal framework known as PQ learning which extends probably approximately y correct (PAC) learning [Haussler] 1990] to arbitrary test distributions by allowing for selective classification. While PAC learning concerns the development of a classifier with a bounded finite-sample error rate on its training distribution, PQ learning seeks a selective classifier with jointly bounded finite-sample error and rejection rates on arbitrary test distributions. The Rejectron algorithms proposed therein builds an ensemble of models that produce different outputs relative to a perfect baseline on set of unlabeled test samples. We provide a summary of the original Rejectron algorithm in the supplementary material (see (Apenddix A). PQ-Iearning represents major theoretical leap for learning guarantees under covariate shift; however, the majority of the underlying ideas have not been implementedrested experimentally using real-world data. We show how to build PQ learner by generalizing the Rejectron algorithm, overcoming several limitations and assumptions made by the original work including extending beyond simple binary classification to general multiclass and multilabel tasks and reducing the number of samples required for learning at each iteration.
3 DETECTRON
Problem Setup. Let f : X + Y be classification model from a function class F that maps from of classes Y .1,-... N). We assume f was trained
space of covariates X to discrete dataset of labeled samples P {< }1) where each x; is drawn identically from a distribution P over X. In deployment, f is then made to predict on new unlabeled samples Q- = { from a distribution Q over X. Our goal is to determine whether f may be trusted to do so accurately. The problem we address is how to automatically detect, from only a set of finite samples Q, if the new covariate distribution Q has shifted from P in such a way that can no longer be assumed to generalize - we refer to this type of dataset shift as harmful covariate shift.
Harmful Covariate Shift. A shift in the data distribution is not always harmful. In many practical problems, a practitioner may use domain knowledge to embed invariances with the explicit goal of ensuring the predictive performance of a classifier does not, by construction, change under certain shifts. This may be done directly via translation invariance in convolutional neural networks, permutation invariance in DeepSets [Zaheer et al.) 2017) or indirectly via data augmentation or domain adaptation. Such practical heuristics can lead to models generalizing to a more broad range of distributions than can be characterized by just the training set. We refer to such induced generalization set as R. Although R is difficult to characterize and will in general depend on the model architecture, learning algorithm and training dataset, we seek practical method for detecting shift that is explicitly tied to R2 We present a more formal definition of harmful covariate shift as well as a connection domain identification and A distance [Kifer et al. 2004 in Appendix H
Our approach is based both on PQ learning and intuition from learning theory. If there exists a set of classifiers with the same generalization set R but behave inconsistently on samples from distribution Q. then Q must not be a member R. Our strategy will be to create an ensemble of constrained disagreement classifiers, classifiers constrained to predict consistently (i.e., predict the same as f) on R but as differently as possible on Q. If Q is within R then such ensemble will fail to predict differently. When we can find an ensemble that exhibits inconsistent behaviour on Q, there
"See Appendix Gfoor further intuition and concrete example of the generalization set.
3

---

Published as a conference paper at ICLR 2023
must be covariate shift that explicitly lies outside R. To make the idea of constrained disagreement classifiers tangible we propose simple definition which we will translate into a learning algorithm in the following sections.
Constrained Disagreement Classifier (CDC). A constrained disagreement classifier (()P..) or simply y if P and Q are clear with context, is a classifier with the following properties:
1. g belongs to the same model class as f E F and is trained with the same algorithm on P
2. g achieves similar performance on unseen samples drawn i.i.d to P
3. g disagrees maximally with f on elements of dataset Q while not violating and 2
Our definition of CDC aims to explicitly capture the concept of a classifier that learns the same generalization region as f while behaving as inconsistently as possible on
Limitations of PQ Learning. As our work builds on PQ learning, we provide summary of the original framework and clearly state the distinctions in our methodology. In PQ learning we seek selective classifier h that achieves bounded tradeoff between its distribution rejection rate rej, (x) and its out of distribution error erry (X) with respect to a ground truth decision function d. Formally, this tradeoff is defined using the following learning theoretic bound (an extended description can be found in Appendix A.
PQ learning Coolwasssr al. 2020 Learner L (c, n) PO--leQlss for any distributions P, Q over X and any ground truth function d E F, its output h = L(P, d(P), Q) satisfies
P Px-P=n x- [ei,,() + erra (x) S c) 2 8
Goldwasser et al. propose the Rejectron algorithm for PQ learning (summarized in Appendix A in noiseless binary classification setting with zero training error and access to a perfect empirical risk minimization oracle. We highlight several pitfalls that prevent practical realization of Rejectron (1) the classification problem must be binary (2) the optimization objective at each step requires an ERM query with (2(P(²) samples and (3) most significantly there is process control overfitting. By tackling the above issues we derive a practical PQ learner and propose a powerful hypothesis test to identify harmful covariate shift.
Learning to Disagree with the Disagreement Cross Entropy. To train a classifier to disagree in the binary setting, it suffices flip the labels. However, in the multi-class classification, is unclear what a good objective function is. We formulate an explicit loss function that can be minimized via gradient descent to learn CDC. For classification problems, letting 1 == g(x;) be the predictive distribution over N classes with the 4h denoted by ú. f(x)) E (1.... .) the label predicted by f and ()) binary indicator, define the disagreement- enoseeeeeottrroosseereooy (DCE) i as:
1 I-N f(a))e log(ū.)
E(U, f(x))
? "corresponds taking the cross entropy of 9 with the uniform distribution over all classes except (xre). Since the primary criteria is that g(;;) disagrees with (xs), é is designed to minimize the probability of g's prediction for the output of f's while maximizing its overall entropy. Our definition of é is stable to optimize, has a bounded global minimum, and can be shown to have desirable properties for disagreement learning, see Appendix for more details.
Our goal is to agree on P and disagree on Q. Consequently, we learn with the loss in Equation 3 é denotes the standard cross entropy loss and i is the disagreement cross entropy. À is scalar parameter that controls the trade off between agreement and disagreement.
LCDe P. Q) P
Σ
(g(())) + Σ [(ga,,, B.EQ
(S..D)))
When learning CDCs in practice, LCDC should be combined with any additional regularization and data augmentation used in the original training process of to ensure that we retain the true
A discussion on the relation between model complexity of F and the behaviour of CDC's and associated limitations of defintion is given in Appendix
4

---

Published as a conference paper at ICLR 2023
generalization region of f. Furthermore, training and validation metrics must be closely monitored on unseen samples from P to ensure that g achieves similar generalization performance on P.
Choosing A. In the original formulation of Rejectron, selective classifiers trained consisting of P replicated [P| times and Q. Calling an ERM oracle on this data ensures that a misclassification on P is significantly more costly than one impractical number for large datasets. We show that instead we can choose the scalar parameter À in Equation to set learning P as the primary learning objective and only when it cannot be improved, we allow g to learn how to disagree on Q The reasoning is a simple counting argument. Suppose agreeing on each sample in incurs a reward of and disagreeing with each sample in Q a reward of A. To encourage agreement on P as the primary objective, we set À such that the extra reward obtained by going from zero to all disagreements on Q less than that achieved with only one extra agreement on P. this gives X|Q < 1. Practically, we chose x = 1/((Q) + 1) and find that no tuning required.
dataset
but requires (2[ (?) samples, an
Some predictive models require learning with non-differentiable loss functions and/or discrete optimization (e.g., random forest). In such cases we fall back and formulate general disagreement loss by duplicating each sample in Q (N - 1) times, giving each a unique label that is not the target and weight of 1/(N 1). In the continuous case, this corresponds exactly to Equation 2
To learn richer disagreement rules, create ensemble of CDCs where the A4th model is trained only to disagree on the subset of Q that has yet to be disagreed on by models 1 through k - 1. The final disagreement rate Φq is the fraction of unlabelled samples where any CDC provides alternate decision from f. In what follows we use this rate to characterize shift.
From Constrained Disagreement to Detecting Shift with Hypothesis Tests. A natural way to apply the concept of constrained disagreement to the identification of covariate shift is to partition Q into two sets, using the first to train CDC ensemble and the second compute unbiased estimate of its held out disagreement rate Φ We would statistically compare this disagreement rate using a 2 x exact hypothesis test against a baseline estimate for the disagreement rate on P. The following shows that this results in provably correct method to detect shift.
Theorem 1 (Disagreement implies covariate shift). Let ʃ be a classifier trained on dataset P consisting of samples drawn identically from P and their corresponding labels. Let g be classifier that is observed to agree (classify identically) with f on P and disagree on dataset Q drawn from Q. If the rate which g disagrees with f on n unseen samples from Q is greater than that from n unseen samples from P w.p. greater than p* = (1 (1-41 (?))) there must be covariate shift.
Sketch of Proof. We show that under the null hypothesis where P = Q the tightest upper bound on the probability that g is more likely to disagree on Q compared to P is p". The contrapositive argument then states if we deem the probability to be greater than p" there must be covariate shift. This result motivates hypothesis testing approach to determine how probable it is that is truly more likely to disagree on Q given only a set of finite observations. The full proof can be found in Appendix C
Our theory, while simple, has limitation that prevents its direct application. Any approach that requires unseen samples from Q is ill-suited for the low data regime, as it requires splitting Q leaving an even smaller set for computing the disagreement rate. Estimators from small samples result in high variance and ultimately low statistical power Since our objective is to detect covariate shift from as few test samples as possible, splitting Q is not good option. To tackle this issue practically, we take a transductive approach based on intuition from learning theory: creating learning models to disagree on samples from Q while generalizing to R is far easier task when use the relutive increase in disagreement between CDCs on Q and P to capture a quantity that is nearly as informative as the unbiased statistic without reducing samples from Q that we can use.
not in R. We can therefore
The Detectron Test. Our proposed method is to train two CDC ensembles gQ and gp. JQ is trained to disagree on all of Q and a gp is a baseline trained to disagree an unseen set P* from P. Once trained, we compute the ratio of samples ΦQ and Φp that gQ and gp learn to disagree on their sets respectively. Under the null hypothesis where Q belongs to the generalization region of f and P. B[øq] < [[dr], while harmful shift is expressed (i.e.. it is easier to learn how to reject on Q compared to P). We refer to this test as Detectron (Disagreement). To compute the test result at a significance level a first estimate the null
one sided alternative H, : [[Øq] > E[
5

---

Published as a conference paper at ICLR 2023
distribution of op for fixed sample size by training the Detectron for K calibration rounds with different random seeds and sets P The test result is significant if the observed disagreement rate &q is greater than the (1 - a) quantile of the null distribution. For more information the testing procedure see algorithm below and detailed description in Appendix B
We consider additional variant, Detectron (Entropy), which computes the prediction entropy of each sample under the CDC ensemble instead relying solely on disagreement rates. The CDC entropy is computed from the mean probabilities over each N classes of the base classifier and of l: CDCs 91, -k-
CDCentmpy (x)
Σ Po log(pe) where p = + [(x)
1
[(x))
Σ (xr) ==1
We use a KS test compute a p-value for covariate shift directly on the entropy distributions computed for Q and P and guarantee significance using the same strategy as above. The intuition for Detectron (Entropy) draws from the fact that when CDCs satisfy their objective (i.e., in the case of harmful shift) they learn to predict with high entropy on Q and low entropy P resulting in natural way to distinguish between distributions.
Algorithm 1: The Detectron algorithm for detecting harmful covariate shift Input: P: labeled dataset, Q: unlabeled dataset, learning algorithm, K: calibration rounds 100, N: ensemble size = 5, az significance level = 0.05 Output: test result for harmful covariate shift at significance level a
P trains Pval P +
Partition(P)
N
Q L(P trinn vval)
pp
f
// Load or train base classifier on P
repeat
pd < RandomSample(P*.
// Train ensemble of CDCs on p
while n > and iterations & N do
g ConstrainelDisarreennnt/// P urinn P P P", f) // Appendix TODO
pd + {- E and f(x) g(x)}
// Filter out disagreed on data
Φp
p*//N
// Update disagreement rate
end
Append óp to Pp
until K iterations elapse
/ Train an ensemble o CDCs on Q
while and iterations S N do
+ ConsrrainelDissgrremett/.. P irain, val. Q,
Q {or Q and (x) g(x)}
ΦQ - - Q1/N
end
return
Φq [11 a) quantile of pp)
4 EMPIRICAL EVALUATION
Our experiments are carried out natural distribution shifts across multiple domains, modalities, and model types. We use the CIFAR-1O. dataset (Recht al. 2019 where shift comes from subtle changes in the dataset creation processes, the Camelyon/7 datasel [Veeling et al. (0188] for metastases detection in histopathological slides from multiple hospitals, as well as the UCI heart disease dataset [Janosi et al.) 1988) which contains tabular features collected across international health systems and indicators of heart disease. We present unseen source an target domain performance of base models trained source data in Appendix Table 4] which shows significant performance drops as an indicator for the hamrfulness of these shifts. Seel Appendix F for more details on datasets.
Learning Constrained Disagreement. We begin by training ensembles of 10 CDCs using the disagreement cross entropy (DCE) with CIFAR-10 10 as and CIFAR- 10.1 as Q for 100 random runs at sample size of 50 (see Appendix E for training details). The results in Figure 2 empirically validates

---

Published as a conference paper at ICLR 2023
minimizing the DCE as a CDC learning objective. The first observation is that when an unseen set is drawn from a shifted distribution Q, the empirical disagreement rate ΦQ grows significantly larger that CDCs preserve accuracy on data from the training distribution. Finally, as the ensemble size increases (and disagreed upon points are removed) see that the accuracy of the classifier increases. This indicates that the points that are disagreed upon early on in the algorithm are those that would have been misclassified.
than the baseline disagreement rate áp. Next,
In Diontbvrtton Aceureey
Selective ChassBoatton
1.00:
0.600
Diugrotunt Rate
01.95
0.846
0.848
Acouracy
0.90
6. 6.
0.642
0.80
0.840
0.75
0.70
Stibed
Utalibed
10
2
10
10
Ensemble Size
Figure 2: Ensemble Size vs Properties of Constrained disagreement classifiers on CIFAR-10/10.1 (Left) We see that for all ensemble sizes, there is lower disagreement on unshifted data (CIFAR-10) compared to disagreement
shifted data -I.FAR-10.1.. (Center) Constrained disagreement does not compromise in- distribution performance. (Right) As the ensemble grows the selective classification accuracy computed on the set of test examples that all models agree on increases both on in- in-distribution and Confidence intervals are computed as + one standard deviation across experiments.
data.
Shift Detection Setup. We evaluate the Detectron a standard two-sample testing scenario similar to prior work [Zhao et al. 2022]. Given two datasets P {II., }))} (I, drawn from P) and Q = { (6; drawn from Q) and classifier f. we seek to rule out the null hypothesis (P = Q at the 5% significance level. To guarantee fixed significance
employ permutation test by first sampling from the distribution of test statistics derived by the Detectron where the null hypothesis p 2 holds (i.e., Q is drawn P). We then compute a threshold over the empirical test statistic distribution that sets the false positive rate to 5% (see Appendix B Figure 5). This step can be performed in advance of deployment as it only requires access to P. To mimic deployment settings where we wish to identify covariate shift quickly. we assume access to far more samples from P compared to Q. For each dataset, we begin by training a base classifier on the unshifted dataset. We evaluate the detection of covariate shift on 100 randomly selected test sets of n = 10, 20 and 50 samples from Q. In all cases we train a maximum ensemble size (parameter N in algorrihh I). To prevent CDCs from overfitting in the case of small test set sizes, we perform early stopping if in-distribution validation performance drops by over 5% from the measured performance of the base classifier. Hyperparameters and training details for all models can be found in Appendix E.
Evaluation. We report the True Positive Rate at 5% Significance Level (TPR@5) 5) aggregated over 100 randomly selected sets Q. This signifies how often our method correctly identifies covariate shift (P + Q) while only incorrectly identifying shift 5% of the time. This is also referred to as the statistical power of test significance level (a) of 5%.
Baselines. We compare the Detectron against several methods for OOD detection, uncertainty
estimation and covariate shift detection. Deep Ensembles Ovadia al. [2019] using both (1) disagreement and (2) entropy scoring methods as a direct ablation to the CDC approach (3) Black Box Shift Detection (BBSD) [iptton et al., 20188. (4) Relative Mahalanobis Distance (RMD) [Ren et al.)
2021]. (5) Classifier Two Sample Test (CTST) Lopez- Pazz and Oquab 2017]. (6) Deep Kernel MMD
(MMD-D) [Liu al., 2020 (7) H Divergence (H-Div) Zhao et al. 2022 For more information on baselines see Appendix subsection E.3
Shift Detection Experiments. We begin with an analysis of the performance of the Detectron on the UCI Heart Disease dataset. Using a sample size ranging from 10 to 100 we compute the TPR @5 (based on 100 random seeds) and plot the results in Figure 3 We use gradient boosted trees (XGBoost [Chen and Guestrin 2016)) for Detectron and CTST methods while the remaining basclines use 2 layer MLP that achieves similar test performance. We report the mean and standard
error of TPR @5 5 for sample sizes of 10, 20 and 50 on all datasets in Table
4.1 DISCUSSION
Overall Performance. We observe in the bottom rows of Table I that Detectron methods outperform all baselines across all three tasks. This confirms our intuition that designing distribution tests
7

---

Published as a conference paper at ICLR 2023
Desecinus (Baieops)
Datectio
TPRGS
0.6
X3D D
0.0
Day Rowal (Da]
ttaeble Itmmpp
0
BISDO
Sample Size [Q]
Figure 3: True positive rate at the 5% significance level for the Detectron and baseline methods for detection of covariate shift the UCT heart disease dataset. The Detectron (Entropy) is shown uniformly outperform baselines. Confidence intervals are excluded visual clarity but are found Table
Table 1: Results (true positive rate at the 5% significance level) for detection of harmful covariate shift on CIFAR-10. 10.1, Camelyon 17 and UCT Heart Disease benchmarks. The best result each column bolded, results that are within 2% of the best are underlined and the best baseline method is italicized.
CIFAR 10.1
Camelyon
UCI Heart Disease
[Q]
10
20
50
10
20
50
10
20
50
.1244
.38 .05
.03
+ .03
Rel. Mahalanobis
.05 + .02
.03 .03
.04 .02
.16 004
.40 + .05
.89 + +.00
.11 + .03
.36 + .05
.66 +.0
Doep Ensemble (Dis)
23 001
.40 = .5
74 + 04
.10 + 03
.11 = .03
.13
.02 :: 001
.00 # .00
32 .05
Deep Ensemble (Entropy)
.39 19.4.000 .05
.52 = .05
.68 + .05
.14 = .03
.26 +: .01
.82 1::
.13 :: .03
.32 + .05
.64 .05
CTST
.03 .02
004 = .02
04 .02
.11 # .03
.59 # .05
.59 + .05
.15 + 04
.51 + .05
.98 +
MMD-D
24 .04
.10 100:::00 .03
.05 1: .02
.49 1: .5
.62 1: .05
.69 1: .05
.09 L:: .03
.12 1:
.27
.02
+
+: = .03
.23 + .04
db .04
.26
.37 .05
Detectron (Dis)
37 + 05
.54 = 05
88 + 04
.97 + 02
1.0 = 000
.96 + .02
.24 = 0.04
.57 2 0.05
.82 0.04
Detectron (Entropy)
35 +
.05
.56 .05
.92 H: .03
.97 +: 02 1.0 :: .00
1.0 1: .00
.45 4: .05
.88 +: 0.03
1.0 .00
based specifically available data and the outputs of learning algorithms is promising avenue for improving existing methods in the high dimensional/low data regime.
Sample Efficiency. For significant shifts (Camelyon and UCI,, in Table the most significant improvements over baselines in the lowest sample regime (10 data points). The fine- grained result in Figure shows that CTST catches up Detectron 40 samples while deep ensemble, BBSD, and Mahalanobis catch up at 100.
Disagreement vs Entropy. For the experiments on imaging datasets with deep neural networks Detectron (Disagreement) often performs nearly as well as Detectron (Entropy), while Detectron (Entropy) is strictly superior for the UCI dataset. While we recommend entropy as the method to maximize test power, disagreement is more interpretable statistic as it is correlates well with the portion of misclassified samples (see (right) Figure 2}.
Comparison to baselines. Amongst the baselines, there is no clear best method. On average, ensemble entropy is superior on CIFAR, MMD-D on Camelyon, and CTST on UCL Our method may be thought of as a combination of ensembles, CTST, and H-Divergence. As ensembles, we leverage the variation in outputs between a set of classifiers; as CTST, we learn a domain adversarial setting; and as H-Divergence, compute test statistic based data that model trained Lastly, while MMD-D and H-Divergence were shown to be the previous oatee-of-hheeee their performance was validated only on larger sample sizes (2 200).
8

---

Published as a conference paper at ICLR 2023
On Tabular Data. The Detectron shows promise for deployment tabular datasets (bottom right of Table I and Figure 3), where (1) the computational cost training models is low, (2) the model agnostic nature of the Detectron is beneficial as random forests often outperform neural networks in tabular data [Borisov et al. 2021]. and (3) based on our discussions with medical professionals, the ability detect covariate shift from small test sizes is of particular interest in the healthcare domain where population shift is constant problem burden for maintaining the reliability of deployed models.
On computational cost: Our method is more computationally expensive than some existing methods for detecting shifts such as BBSD and Mahalanobis Scores, but is similar complexity to other approaches such as Ensembles. MMD-D and H-Divergence which may require training multiple deep models. However, as the Detectron leverages pretrained model already in deployment, we find in practice that only small number of training rounds are required to create each CDC. Furthermore, looking at the runtime behavior in Figure 4 we see that while allowing for more computation time increases the fidelity of the Detectron, only a small number of training batches may be required to achieve desirable level of statistical significance. In scenarios where the deployed classifier is deemed high-risk (e.g. healthcare, justice system, education) we believe the additional computational expense is justified for an accurate assessment of whether the classifier needs updating. Having established the utility, accelerating the Detectron as well as building a deeper understanding of the runtime performance fertile ground for future work.
0.25
0.20
Detectron (AUROC)
0.15
Disagreement
0.4
Statistic
0.2
0.05
0.0
0.00
20
40
60
Total Training Batches
Figure 4: Runtime Characteristics: We train 100 random runs of CDCs on 100 samples from CIFAR 10 and 10.1 and compute the disagreement satistic as the difference t == E[ ép). While we see that while j peaks near 50 training batches, only 10 batches under the TPR FPR curve (AUROC) of nearly (i.e.. perfect discrimination). Training CDCs for long eventually lowers tp as E[Øa]
required for the Detectron disagreement test reach area
Ej meaning CDCs eventually overfit to disagreeing on all their data.
CONCLUSION, LIMITATIONS AND FUTURE WORK
Our work presents practical method capable of detecting covariate shifts given a pre-existing classifier. On both neural networks and random forests, we showcase the efficacy of our method to detect covariate shift using a small number of unlabelled examples across several real-world datasets. We remark on several characteristics that represent potential directions for future work:
On Generalization and Model Complexity: The definition of the Detectron specifies the use of the same function class for identifying shift as used in the original prediction problem. The Detectron may fail to detect harmful shifts in cases where the base model is learned from an underspecified function class. [Appendix provides additional context, examples and ways to mitigate this limitation. The precise re relationships between model complexity, generalization error, and test power are interesting directions for future work.
Beyond Classification: Our work here focuses on the case classification, however, we believe there is viable extension of our work to regression models where constrained predictors explicitly learned to maximize test error according to the existing metric, such as mean squared error. We leave this exploration for future work.
Finally, wish highlight that while auditing systems such the Detectron show promise to ease concerns when using learning systems high-risk domains, practitioners interfacing with these systems should not place blind trust in their outputs.

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
The speed of the adoption of ML into risk scenarios raises a critical need for methods that ensure trustworthiness and reliability. However, over-reliance such methods brings about critical ethical considerations. As we have seen, Detectron is highly sensitive to picking out discriminative features of data distributions, and, such, its usage may prevent practitioners from deploying models in new environments. As a result, the individuals in those environments may become subject to unfair treatment. For instance, if Detectron determines a model trained on hospital A safe to deploy in hospitals B and C, but not in D, the individuals in population D may experience a lower level of care. In real example, Detectron, when tested on a model trained on subset light-skinned celebrities (CelebA datasct-Liu et al. )2015), ), quickly raises the alarm when given images of those that are not light-skinned. While Detectron can help mitigate potential disasters encountered by deploying models in hazardous domains, it should not be excuse for practitioners avoid collecting richer and more diverse datasets as primary strategy to ensure model reliability.
ACKNOWLEDGMENTS
Tom Ginsberg's research was supported by New Frontiers Research Fund NFRFR-2022-00526, an LG research grant, and Canada Graduate Scholarship (CGS-M). Rahul G. Krishnan supported by CIFAR AI Chair. 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. Additional thanks is given to the many readers who provided valuable feedback: Vahid Balazadeh, Michael Cooper, Edward De Brouwer, Aslesha Pokhrel, Adnan Mohd, Ian Shi, Asic Chen and Stephan Rabanser.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira. Analysis of representations for domain adaptation. In Schölkopf. J. Platt, and Hoffman, editors, Advances in Neural Information Processing Systems, volume 19. MIT Press, 2006, URL
S. Bickel, M. Brückner, and T. Scheffer. Discriminative learning under covariate shift. Journal of Machine Learning Research, 10(75):2137-2155, 2009. URL http: htKL:ttt://mmrr.o/////e/
v10/bicke109a. htmll
V. Borisov, T. Leemann, K. Seßler, Haug, M. Pawelczyk, and G. Kasneci. Deep neural networks and tabular data: A survey. CoRR, abs/21 10.01 889, 2021. URL https::/arxiv.rrg/ 2110. 01
D. Chaki, A. Das, and M. Zaber. comparison three discrete methods for classification of heart disease data. Bangladesh Journal of Scientific and Industrial Research, 50:293-296, 2015.
T. Chen and C. Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 16, pages 785-794, New York, NY, USA, 2016. ACM. ISBN 978- -272---250- doi: 10. 10.1145;
2939672.2939785. hRL/http:/ddo acm. org 10. 1111111419999
2939785
J. Dastin. bias us-ame aamzznn-com-
Amazon
scraps
secret
recruiting
tool that showed
against
women.
https: www. reuters com/ article/
2018. (Accessed
05/11/2022..
J. Deng, W. Dong, R. Socher, L.JJ. Li, K. Li, and L.. Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248 255. leee, 2009.
S. Garg, S. Balakrishnan, 7. C. Lipton, B. Neyshabur, and H. Sedghi. Leveraging unlabeled data predict out-of-distribbtion performance. In International Conference on Learning Representations, 2022. URL https::/ htRp:ttss///peeeeeeeee.ece http://wwww.eteetor.oeoeee..eee.
HsiMPYh
Y. Geifman and R. El-Yaniv. SelectiveNet: deep neural network with integrated reject option. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 2151-2159. PMLR, 09-15 Jun 2019. http:tt:: http://///...eeedd..........c wtt.::/s.w........ss.s.sss/ees fman:////weeeeeennnnnnaaa html
Goldwasser, A. T. Kalai, Y. Kalai, and O. Montasser. Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15859-15870 Curran Associates, Inc., 2020. URL httpps://pzoceeeinggs http://wwwoeeeiing....e......ppp nww.iis........ cc/
oaa.ae/ccc....eee000008885662223 Paper. pdf
A. R. Habib, L. Lin, and R. W. Grant. The Epic Sepsis Model Falls Short-The Importance of External Validation. JAMA Internal Medicine. 18
2021.
K. Hao. is sending people to and getting it wrong htt.p:::www.tthhhoo www.heehhoooooooo wooechoooogrreieewe http:///00000.1333333/////mmmmn. cessed 05/11/2022).
ai/ 2019. (Ac-
D. Haussler. Probably approximately correct learning. In Proceedings of the Eighth National Conference on Artificial Intelligence, pages 1101-1108. AAAI Press, 1990.
J. L. Hodges. The significance probability of the smirnov two-sample test. Arkiv för Matem- atik, 365) 1958. doi: 10.1007/8BF02588500. BF BFC2589501
W. R. Inc. Mathematica, Champaign, II., 2021.
www. http:////ttt///.....oaaaaaaoooo.

---

Published as a conference paper at ICLR 2023
A. Janosi, W. Steinbrunn, M. Pfisterer, and R. Detrano. Heart Disease. UCI Machine Learning Repository, 1988.
D. Kifer, Ben-David, and Gehrke. Detecting change in data streams. Proceedings of the Thirtieth International Conference Very Large Data Bases Volume 30, VLDB '04, page 180-191. VLDB Endowment, 2004. ISBN 0120884690.
D. Kingma and J. Ba. Adam: method for stochastic optimization. In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL /RLLhttp://aree wrw. org/abs/ / 1412. 6980]
D. P. Kingma and M. Welling. Auto-encoding variational bayes. In Y. Bengio and Y. LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Bansf. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http::tp///. http///axvv.vv.. wwwii.orrgg..oo org/ abs /1112 6114
W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Yasunaga, R. L. Phillips, I. Gao, T. Lee, E. David, I. Stavness, W. Guo, B. Earnshaw, I. Haque, S. M. Beery, Leskovee, A. Kundaje, E. Pierson, S. Levine, C. Finn, and P. Liang. Wilds: of in-the-wild distribution shifts. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5637-5664. PMLR, 18-24 Jul 2021. URL https::/proceediingt mlr
benchmark
pxess/v139/koh2l.. html
A. Krizhevsky, V. Nair, and G. Hinton. The cifar-10 dataset. edu/kriz/cifar. html, 55(5), 2014.
online:
http://www. cs. toronto.
B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Proceedings of the 3 International Conference on Neural Information Processing Systems, NIPS' 17, page 6405-6416, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Y. LeCun, Boser, S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation Applied to Handwritten Zip Code Recognition. Neural Computation, 1(4): 541-551, 12 1989. ISSN 7667. doi: 10. 166/neco...... 1989. 1.4.541. URL CtL.https:///tt //doi
org 10 11.00.1162nneeee www.11///ecc.. 190ecc..11988 1989 1.4.8.9......... 4.51
K. Lee, K. Lee, H. Lee, and Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. In S. Bengio, H. Wallach, H. Larochelle, Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
S. Liang, Y. Li, and Srikant. Enhancing the reliability of oft-o--distributiinn image detection in neural networks. In International Conference on Learning Representations, 2018. URL
net fott/
Z. Lipton, Y.-X. Wang, and Smola. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pages 3122-3130. PMLR, 2018.
F. Liu, W. Xu, J. Lu, G. Zhang, A. Gretton, and D. J. Sutherland. Learning deep kernels for non- parametric two-sample tests. In International conference on machine learning, pages 6316-6326. PMLR, 2020.
Z. Liu, P. Luo, X. Wang, and X. Tang. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
D. Lopez-Paz and M. Oquab. Revisiting classifier two-sample tests. In International Confer- ence on Learning Representations, 2017. URL httpss://ppereeiieee ntt.ooruuttttotmmmmommmmmm forum?id 8.
12

---

Published as a conference paper at ICLR 2023
S. Marcel and Y. Rodriguez. Torchvision the machine-vision package of torch. In Proceedings of the 18th ACM International Conference on Multimedia, MM '10, page 1485-1488, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781665589336. doi: 1145//100.111111111 117.911117777771711111111 1874254
10.1 145/1873951. 1874254.
W. Morningstar, C. Ham, A. Gallagher, B. Lakshminarayanan, A. Alemi, and J. Dillon. Density of states estimation for out of distribution detection. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on A Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3232-3240. PMLR, 13-15 Apr 2021. html
URL
mlr. wtt.://.www........eeeeeeaaa.aa. /ttps/////////////ooaoit/ttt///
T. Needham. Complex Integration: Cauchy's 's Theorem, page 377-417. Oxford University Press, 2000.
E. Otles, Oh, B. Li, M. Bochinski, H. Joo, J. Ortwine, E. Shenoy, Washer, V. B. Young, K. Rao, et al. Mind the performance gap: examining dataset shift during prospective validation. In Machine Learning for Healthcare Conference, pages 506-532600 5344. PMLR, 2021.
Y. Ovadia, E. Fertig, J. Ren, Z. Nado, D. Sculley, S. Nowozin, J. Dillon, B. Lakshminarayanan, and J. Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buse E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
E. A. Platanios, A. Dubey, and T. Mitchell. Estimating accuracy from unlaheled data: A bayesian approach. In M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning. volume 48 of Proceedings of Machine Learning Research, pages 1415-1425, New York, New York, USA, 20 22 Jun 2016. PMLR. URL https:/7 proceedings mmr. prwpsppeese..... wtw.ee///v//plaaaaiiossses
html
S. Rabanser, S. Günnemann, and Z. C. Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancou- cc/
ver, BC, Canada, pages 1 394-14406 2019. URL https: / http://rocceiinn..e...ee 6c88 Abst
B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do 10 classifiers generalize to cifar- 2018. URL htttttss://axii..rrrrrr///ee//ee http///aavvvv.// wwwp://wwwwrr/////3/...0.....000 00451
B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do ImageNet classifiers generalize to ImageNet? In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5389-5400, PMLR, 09-15 Jun 2019. URL https:: /
ml wtw.s/..eess/v///
html
J. Ren, P. Liu, E. Fertig, J. Snoek, R. Poplin, M. Depristo, J. Dillon, and B. Lakshminarayanan. Likelihood ratios for duits--dittiitution detection. Advances in neural information processing systems, 32, 2019.
J. Ren, S. Fort, J. Liu, A. G. Roy, S. Padhy, and B. Lakshminarayanan. A simple fix to mahalanobis distance for improving near-ood detection. ICML. workshop on Uncertainty and Robustness in Deep Learning, 2021. URL UtRLattp://wee paper wwwpaaperr07..pppm 307.pdf
gatsby..ss............... wwt.ssbb..c...... www. uk/ /aap.////aaallaaa/a///1111111111
C. Sastry and Oore. Detecting out-of-dist examples with Gram matrices. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8491-8501. PMLR, 13-18 Jul 2020. URL
nggs .ml wtt.ssmww.........eemmemmmmmmeee www.spsssseee.........e v /ts.s//ttataaaaaa.
wptppeee///19///attt222...a html
L. Smiley. i'mm the operator': The aftermath of self-driving tragedy. wired: www.//////t/toeeeeeeeeeee htmm/sttoy/bbbr: 05/11/2022).
https:/ /ww 2022. (Accessed on
13

---

Published as a conference paper at ICLR 2023
N. G. Ushakov. Continuity theorems and inversion formulas. De Gruyter, 2011.
V. N. Vapnik. The nature statistical learning theory. Springer- Verlag New York, Inc., 1995. ISBN 0-387-94559-8.
B. S. Veeling, J. Linmans, J. Winkens, T. Cohen, and M. Welling, Rotation equivariant CNNs for digital pathology. June 2018.
Y. Yu, Z. Yang, A. Wei, Ma, and Steinhardt. Predicting out-of-distribution error with the projection norm. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 25721-25744 PMLR, 17-23 Jul 2022. URL htttps://proceed.ngg prressssssssr.sssssseeess....sss
wwwpss/vvvliee vi http://vv22//222222ememm
M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Zhang, M. Goldstein, and R. Ranganath. Understanding failures out-of-distribution detection with deep generative models. In International Conference on Machine Learning, pages 12427- 12436. PMLR, 2021.
Zhao, A. Sinha, Y. He, A. Perreault, J. Song, and S. Ermon. Comparing distributions by measuring differences that affect decision making. In International Conference Learning Representations, 2022. URL https: /tte::///peeereeeee wwwp://ewweeeeeeeeeeeeeeeeeeeeee sw.
d=
14

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
Learning Algorithms
16
A.1 Rejectron
16
A.2 Constrained Disagreement Classifiers
17
B Hypothesis Tests
17
Two Sample Testing Methodology
B.2 Statistical Tests Used Methods/Baselines
18
C
Proofs
20
D Constrained Disagreement Learning
23
D.1 Disagreement Cross Entropy
................................
23
D.2 Extension To Diserete Models
................................
25
D.3
Disagreement Overparameterized Models
................................
26
E
Experimental Details
27
E.1
Base Classifiers
27
E.2
Constrained Disagreement Classifiers
................................
27
E,3
Description of Baseline Methods
28
Comparison to Generalization Error Prediction
"...............................
29
F
Datasets
29
F Sources and Licensees
29
F2
Prepossessing. Shift Descriptions and Model Performance
30
G Expanding on Generalization Regions
31
Harmful Covariate Shift and Connection to Distance
32
Model Complexity and the Detectron
33
15

---

Published as a conference paper at ICLR 2023
A LEARNING ALGORITHMS
This section presents further details on the primary learning algorithms used and referred in our work.
A.1 REJECTRON
We provide summary of the original Rejectron algorithm for PQ learning [oolwwsssr et al. 2020 as it is the primary motivation for our work. Rejectron algoriihmm 2) takes as input a labeled training set of n samples x (iid over P), an unlabeled test set n samples x (iid over Q), an error e and a weight A. The output is selective classifier, that predicts according to base classifier h if the input x is inside some set S and otherwise rejects (abstains from predicting).
h (x) = (h(x)
x E
(5)
reject
x S
The enror and rejection rate of a selective classifier are defined for a selective classifier h/g with respect to distribution P
rej,, (S) == Pawp Jrr $ S]
em,, = Pa~p [h(x) y yyyrr S]
(6)
The empirical rejection and error rates for a set of samples x = (x: (= and corresponding labels y {4:)_11 are similarly defined as:
rein, (x)
= LAgS erty (x) = i== E
(Layt X L2,es)
(7)
S
1=1
==1
Under the selective classification framework Goldwasser et al.) extend the conventional concept of PAC learning [Haussler 1990) to test samples drawn from an unknown distribution Q.
PQ learning Goldwasser al. 2020/ Learner L (e, n)-PQ-llerns F' for and n. E Z+ if for any distributions P, Q over X and any ground truth function d E F. its output L(P, dP),, Q) satisfies
1, S 1
P Px-P", x~Q0 [rej,, (x) + err (x) S 111
(8)
Under several assumptions and special value e", this selective classifier is guaranteedd with high probability to have error less then 2e* on x and rejection rate below e* on x (see Theorem 5.7 in Goldwasser et al.)
Algorithm 2: Rejectron [Golwwssser al. 2020]
Input: train x E X", labels E Y", test E X", error E [0, 1]. weight A = n + Output: selective classifier hls
h + ERM(x, for t 1,2,3.... do
1. S: = {i X
= =x)) c-1(3)}
2. Choose E C' to maximize (c) == err& (hls, A A.rrxx(,,, over E C
If st (c+) S e, then stop and return llss,
Rejectron starts by querying an empirical risk minimization (ERM) oracle that uses a 0-1 risk score over concept class C for a model h that perfectly learns the training dataset. A primary assumption for Rejectron to output a perfect model as well as for to eventually find a selective classifier that meets the e* bound is that the true decision function (i.e., the function that creates the training labels) also a member of C. The authors refer to this setting as realizable.
On the first iteration of the algorithm, Rejectron finds another model c1 C' that jointly maximizes the error with respect to h on while minimizing on x. The authors show that they can efficiently solve this optimization problem using single ERM query dataset of n² samples (see Lemma 5.1 in Goldwasser et al.).
In every subsequent step t a set S, is created where all models h through to c agree. Another model c, E C' is found that maximizes the same objective as above but only on the intersection of and S,. Upon termination selective classifier hls, is output.
16

---

Published as a conference paper at ICLR 2023
A.2 CONSTRAINED DISAGREEMENT CLASSIFIERS
We formally present the algorithm for creating a constrained disagreement classifier (section 3). fundamental tool used to detect distribution shift in our work. The main inputs a labeled training set, an unlabeled test set, and a classifier trained on P using a learning algorithm L. Three other hyperparameters include a metric evaluate the performance accuracy), tolerance which controls how much the metric may drop during disagreement steps and and a maximum number of epochs.
classifier on labeled dataset (e.g..
Algorithm 3: Constrained Disagreement
Input: L: learning algorithm, P Prain: labeled training dataset {..., (Ii, y.)... ... }. P v labeled
validation dataset {.... (I,, Ji....., J. Q: unlabeled test dataset {.... It....
classifier trained on P. MM evaluation metric (default accuracy), tolerance (default 0.05), k: max epochs (default 10)
Output: Constrained Disagreement Classifier ((S..Q))
Q
// infer pseudo labels Q using f 1/ create a batched dataloader using P and Q PQ + Batched (I,, (2, E A (I, E Q)) + f // Initialize with
((x)) | & Q}
mo & Mif. P(ff.Pval P
// Compute the validation performance of
while M(f,Pral val) mo and iterations k do
1/ Training epoch over PQ
for batch E PPQde do
Tr, yp + ((r, v) (x, v) E batch and (x, E P Pinain
zQ, UQ t [2, (z, E batch and (I, Q}
// Update 9 using an existing learning algorithm for (xp,0p) and the appropriate disagreement update for (æQ,1Q)
9 + Updatelg, L, (KP, (TQ.
end
end return g
Our algorithm a practical generalization of the inner step in Rejectron:
(1) We require tight performance monitoring validation set prevent overfitting observed that training models to disagree on small in-distribution test sets cause a drop in their in-distribution performance on unseen data after many training epochs. (2) We allow for arbitrary- sized train and test sets. (3) We provide a methodology (section 3) Learning to Disagree with the Disagreement Cross Entropy) for updating arbitrary classification models to disagree on test data while agreeing on in-distribution data that leverages the generalization structure of their original learning algorithm while requiring quadractically fewer training samples then Rejectron. Further details on implementation details for step (3) can be found below in Amppendix D
commonly
B HYPOTHESIS TESTS
B. TWO SAMPLE TESTING METHODOLOGY
Our method to detect covariate shift, like prior work, is perform statistical hypothesis test between the distributions of one or low dimensional quantities derived using each element of a possibly shifted target dataset Q and known in-distribution source dataset P that has not been observed in during model development, A significant motivation for our work was that the majority of statistical hypothesis tests used by prior work are formulated in a fashion that is independent of the particular target dataset being tested (e.g., BBSD [Lipton et al., 2018 which uses pre-trained classifier as an ansatz for a dimensionality reduction). However, with the Detectron we follow a transductive approach by building a statistical test by training classifiers to meet carefully crafted objective (i.e., constrained disagreement) on the target data. A drawback of this approach is that low dimensional representations are, in general, not be iid; hence perform fair statistical test, must run the Detectron on a known in didsttibbution dataset under the same experimental conditions (e.g., sample size, learning rate, ensemble size). For other baseline methods that do not take the
17

---

Published as a conference paper at ICLR 2023
transductive approach (e.g., Mahalanobis, BBSD, Ensemble), we not limited to choosing source dataset P* of the same size as the samples can again be assumed to be iid. In practice, for iid methods, we fix the size of P* to 1000 for CIFAR and Camelyon, and in UCI Heart Disease, use only 120 as the dataset is significantly smaller (920 samples).
B.2 STATISTICAL TESTS USED IN BECTHODSBBSSLLINSS
We provide a summary in the context of our work on the three types of statistical tests used in our experiments. We also explain technical details on how we use each test in our experiments.
of the most common non- non-parametric univariate statistical tests. It the two sample setting given datasets X = {=I...... In and Y = <(V1.... Fm the test statistic is computed as the maximum difference between the empirical CDFs of X and Y. An asymptotically correct p-value can is computed using a closed-form expression of the test statistic and sample sizes n and m. An exact p-value can also found by considering the fraction of every possible pair of empirical CDFs that lie within the region with maximum bounded difference; more details can be found in Hodges [958]. In practice we use the KS test implementation found in a scipy. stats.. ks_ ss_2smpp which automatically computes exact p- values when max m] S 10, 000 and otherwise defaults to the asymptotic approximation.
Kolmogorov-Smirnov (KS) Test. The KS test
We use KS tests for any distributions derived from continuous scores within our methods and baselines. For the Relative Mahalanobis Score test [Ren et al. 2021], we compute the p-value for shift via a KS test between the Mahalanobis score for the possibly shifted target data Q and source dataset of unseen in distribution samples P*. In BBSD (Lipton et al. 2018) we compute a KS test on each dimension of the softmax output of classifier between the source and target datasets, the final p-value is found via Bonferroni correction as is done by Rabanser et al. (2019), which simply takes the minimum p-value and divides it by the number of tests (e.g the softmax dimension). Similarly, using Deep Ensemble (Entropy) and Detectron (Entropy), we perform a KS test directly on the distribution of entropy values computed from each sample in the source and target datasets, respectively. See Figure 6 for full description of the Detectron entropy test.
Binomial Test. The binomial test is simple to state and has an elegant closed-form solution. We consider binomially distributed random variable with rate q X ~ Binomial q) for which we observe a single sample v. Since the binomial distribution defined as a sum of iid Bernoulli random variables with the same rate, may equivalently be interpreted as a set of n samples of which are 1 and n - 2 are O. Given a baseline rate we wish to determine the probability of observing an event at least rare as X = z under the null hypothesis that p = q. this quantity can be computed exactly using the symmetry of the binomial distribution.
PP Fx~Bin(n.p) (X is rarer then x) x P P Px-Bii(n.p) (x2 2)
Σ P[X
2
Σ (1 p) ~>kp
12
Bp
B(x,n=x+1
k=
Where (2 3) is the incomplete Beta function and B(a, B) is the beta function. Binomial testing is used in the Deep Ensemble (Disagreement) baseline method where we estimate p as the disagreement rate of deep ensemble on the P (i.e the number of samples in P* where the ensemble does not predict unanimously divided by the size of P*) and test for distribution shift based on the result of a binomial test on the observed disagreement on Q. Binomial testing is also used for the classifier two sample test method (CTST) [Lopez-Paz and Oquab] 2017). First domain classifier trained to separate source and target data then its performance is tested on a set of unseen data where the number of samples of total of N it correctly assigns domain label to is compared to the null distribution Bin 0.5) (i.e. random guessing). For implementation purposes we use scipy stats. binomtest.
Permutation Test. Our ultimate goal is to detect covariate shift p Q at a bounded significance level (i.e. bounded probability of outputting P Q when in fact P = Q). To bound the significance level, we follow the simple and principled approach of the permutation test. Suppose we wish to run the Detectron to test for shift set Q from baseline P* (each of N samples) while Detectron,
18

---

Published as a conference paper at ICLR 2023
any other test, computes a p-value some low dimensional samples derived from Q and Pt, the significance threshold on that test will not in general correspond precisely to the significance for rejecting the original null hypothesis P Q. The permutation test allows to reclaim statistical guarantees by first performing several tests where the null hypothesis holds (e.g., we draw Q from P) and find cutoff for the significance of p-value that sets the false positive rafe exactly 5%.
Our experiments run the Detectron 100 times for each sample size on random sets Q drawn from P. Based these runs compute 95th percentile (7) on the final rejection rate. We then run the actual test using a set of samples Q drawn from Q which we deem significant at the 5% level if the number of rejected samples is greater than 5. A visual description of this method can be found Figure
95% of calibration runs reject v T samples
83% test runs reject > T samples
0.15
0.12
T
T
Probability
0.10
0.10
0.08
0.06
0.05
0.04
0.02
0.00
0.00
12
14
16
18
20
22
24
26
20
25
30
Num. Rejected Samples (N X hp)
Num. Rejected Samples (N x ΦQ)
Figure 5: The Detectron disagreement test: In this example (taken from experiment where P = CIFARIO and Q = CIFAR1O.1 and sample size = 50) pictured we start by training an ensemble of CDCs (we and ensemble size of 5) to reject/disagree from the original training distribution (P*) while constrained to perform consistently with a base model the original training and validation sets used train the base model CIFARIO. We perform 100 of these calibration runs using different random seeds and samples for P to estimate threshold т such that 95% of the runs reject fewer then samples thereby fixing the significance level of the test to 5%. To estimate the test power, we train CDCs using the exact same configuration as the calibration runs except we replace P with random set of N samples Q from Q (CIFAR 10.1). By averaging the number of runs the reject more than samples we can compute the power (or true positive rate) of the test for the configuration.
of N unseen samples
Probabilitty Density
255
Calibration Entropy
Calibration Entropy
p-values
la
15c
siguiflonne Ulnsdioki
Entropy
1.0
Entropy
P p-values
aap
0.3
an
0.0
00
0.5
1.0
1.5
2.
0.0
0.5
1.5
2.0
0.0
0.2
0.1
0.8
Entropy
Entropy
KS test p p-value
start (left) by computing KS test between the continuous entropy values for each calibration run P with the flattened of entropy values from all other 99 calibration runs. Then (center) we compute KS test from each test run Q with random set of all but one calibration runs. Finally (right), we find threshold F on the distribution of p-vuuues obtained from step as the a quantile to guarantee a false positive rate of a. The power of the test is computed as the fraction of p- values computed from 100 test runs Q that are below T.
Figure 6: The Detectron entropy test: Following the experimental setup as Figure 5
19

---

Published as a conference paper at ICLR 2023
C
PROOFS
The full proof of Theorem referencee in secticiion 3 From Constrained Disagreement to Detecting Shift with Hypothesis Tests is presented below. After which, we prove related result that invokes Bayesian perspective on distribution shift to generate tight bound on the probability of shift given observations made by CDCs on unseen data.
Theorem 1 (Disagreement implies covariate shift). Let f be a classifier trained on dataset P consisting of samples drawn identically from P and their corresponding labels. Let g be a classifier that is observed to agree (classify identically) with f on P but and disagree on dataset Q drawn from Q If the rate which g disagrees with f on unseen samples from Q is greater then that from n. --"(("))
unseen samples from P w.p greater than p = (1 -- (?n)) there must be covariate shift.
Proof. Let Rp = 0f +... + +0 where each of is an i.i.d Bernoulli random variable that describes the probability of g disagreeing with f on an unseen sample from P. Additionally, let Rę 0 + be defined similarly for Q. If P and Q are equal then 0." and 8 are equal by definition and the probability of observing Rg > Ry is tightly bounded by Equation 9 This is the tightest upper bound that is not a function of E 10," the proof can be found in Lemma
p P= = P (RR Rp) 2
1 (1-
1-4-a 1-441
2n ((m)=
1 2
O
1
Vn
The more helpful contrapositive statement says that if it is sufficiently likely that Ro > Rp, then covariate distributions P and Q must not be equal.
P (RQ > Rp) > 1(1 1-
2n (2)) ) P
4-
(10)
This result naturally lends itself to identifying P + Q by rejecting an exact statistical hypothesis that RQ Rr in favor of the alternative RQ > Rp.
Lemma 1. Let X and Y be iid binomial random variables with distribution Bin(n,p) then for all n E 2 0:
P(X r) 1 [ - 1-4-
2n
(11)
2
Furthermore, eq. [T] is the tightest possible bound that does not depend on
Proof. Let Z be the distribution X - Y, while Z itself is intractable to write down for arbitrary n, the characteristic function takes a convenient form
(t:p:p) E [cll(=-w] = [e E ity
(12)
(1+pl (++p(-++e") 1 (1+p(-1+ed (-1+)
(13)
(-pèe-t 2pe + 2p² pe -it + pr 2p + 1)" (1 11-2p pcos(t) - ipsin(t) + pcos(t) + sin(t)
(14)
(15)
2p² 1² (1) + ip sin(t) 1² cos(1) ip* sin(
(p² (2 2 cos( (2 cos(t) 2) + 1)"
(16)
Since X and Y are identically distributed P(Z > 0) = P(Z < 0) and so
P(Z > 0) = (1 P(Z = 0))
(17)
2
Equation 17 suggests that a tight upper bound of the form P(Z 0) 2 a implies tight lower
bound in the form P(Z > 0) < (1 a)/2. To bound P(Z = 0) we first write it as an integral
expression using the characteristic inversion formula for discrete random variables [Ushakov] 2011
P(Z = 0) = 2n {
1
oz Óz p)dt
(18)
20

---

Published as a conference paper at ICLR 2023
Since (2 p) has the form (a(t)p² b(t)p 1)" where and b real valued functions and a(t) 2 v R (i.e an integer power of a quadratic equation with positive leading coefficient), then for any choice of Φz (t; p) will be globally minimized if and only if p p bbt)// (2a(t)). For the particular form of Φz (): p¹ is simply 1/2
b(t)
cos(t)
1
p" = 2a(t) 2(2 - 2 cos(t)) 2
(19)
This result is intuitive as the variance of binomial distribution Bin(n, p) is maximized for any fixed choice of n when p 1/2. We should note that Mhat|Equation 19 apppears problematic when cos(t) 1, but in this case p(4;p) becomes constant, hence cannot influence the upper bound. We can now write the upper bound for P(Z 0)
1
/
P(Z 0)
Φz p)dt
(20)
2T
1
Ø
dt
(21)
2T
1
n (cos(t) 1)
(22)
2T
-
22
4- n
(23)
The final expression in eq. residue theorem Needham
23 can be found using the change of variables = = ea and Cauchy's
2000
I == 2m
2 2-
(cos(t) + 1)
(24)
-
1 1 22 +22²
2-n
1+
dz (using lig
(25)
2T |=|=1
2
2=
4" 1ーーー~1
n-1
z + 1) 1)2n dz (simplifying)
(26)
2
|//==
Res (4-"z~n~1 (22 + 1)22 0) (applying Cauchy's Theorem)
(27)
1 lim
dm
dza (z + 1)2m
(28)
4'n!
=10
2n(2n - 1)(2n 2)... -n (n.
(29)
4"n!
2n
-
(30)
Combining eq. 17 with the bound from eq.
23 we arrive at the conjectured upperbound
P(X > x)> P(Z
(1 P(Z 0))
(31)
2
1
(2m) 1
(2n)
1 4-
by eq. 23
(32)
2
(33)
Finally we may use Sterling's approximation to show that 4 (2x) (2m)
E E
VT and hence converges
to - leaving limiting tight upper bound of 1 1/2.
Theorem 2 (Probability of Disagreement: A Bayesian Perspective). Let f be classifier trained on dataset drawn from the distribution P over X and their corresponding labels. Let be a classifier observed agree with on P but disagree on dataset Q drawn from distribution Q over X. We denote the true probabilities that will disagree with f on a sample from P and Q as p and q. respectively. Under a uniform prior (((0,) 1) for p and g, if we observe that g disagrees with f on
21

---

Published as a conference paper at ICLR 2023
out of M tid samples from Q while disagreeing with out of N iid samples from P, then the posterior probability that g is truly more likely to disagree with f on Q compared to P:
(M 1)A(N 1m + 1)!
(m + (M - m + N +)! ply p] =1
(34)
3 (m 1,m M, m +++ 2,m 2, + N + 3;11)
Where p. is the generalized hypergeometric function, implemented in several standard mathematical libraries.
Proof. For simplicity we consider the function dis X {0, 1} that outputs 0 f(x) =g(x) else 1. We define the true disagreement rates and q as
= Eg- Ex>r(dis(z)) and q = E- [dis((])
(35)
Without any a-priori knowledge of dis we define the random variables p and g under uniform prior (i.e p, q Lid ((00, 1)) to encode our belief over the true values and q. Now we draw N samples as Lid x ~ PN and M as
iid QM and compute the number of times dis(x) equals on each set.
72
dis(r) and m = Σ dis(x)
(36)
REX
FE
By definition in Equation 35 we know that n and m are draws from binomial distributions: A ~ Bin(N, p) and M ~ Bin(M, q) respectively. We can then compute the posterior probability density functions of p and conditioned on the observations N = n and M = m using exact Bayesian inference.
(2)n(x) = Plp x\ nl
(37)
x P(P x (L,
P[N = nlp
PW = n/p 2/dr
(38)
=1
N
2) N-n (L
x (1 (N)
NN
(39)
n1
11
= x1 2) N
Bz(n B m=0
(40)
incomplete beta function
n!(N n)!
x² N-n
(41)
1)N!
IN
T (1 - x)) N-N +1)
(42)
The integration in Equation 39 solved using the definition of the incomplete beta function.
Without loss of generality we may also find falm
M
fgmm (x) (M + 11)
x))
M-m
(43)
m
Given these closed form posterior distributions for p and q we may compute the probability that the true value of is greater then p
Pla p/N n, m]
farm Sp) (o)dddd
(44)
y>z
-f' [.¹
folm (v) (x))f(m (x))ddd
(45)
M (NV)
+N) NN). (1- (1- -n n (' y) - nhh dydr
)
n (1 M) +
(46)
22

---

Published as a conference paper at ICLR 2023
1.0
0.8
F/ > pin,
Disagreements uy
0.4
n/3 = 0.4
0.2
n/2
10
15
20
Disagreements Q (m)
Figure 7: Belief that the probability y that two classifiers disagree samples from Q is greater then the probability that they disagree on P given an observation of m disagreements out of M samples from Q and n N disagreements on P. We plot this probability for AM 20 and N 10000. We observe that even for small test set size, M = 20, we can strongly believe that there is true difference when m/M only slightly larger then n/N.
This integral, while daunting, can easily be solved in closed form using the free online Wolfram Mathematica cloud (result link). The solution is exactly [Equation 34
Plu > p\N = M =m] = (M + 1)`(N + 1) + n + 1)!
(47)
(m 1)nm! m) m)) + N 2)!
Fm + 1,m M, m + n 2: m + 2, - 3;1)
To gain intuition, graphical representation of Equation 47 is provided in Figure 7 From a practical standpoint, if practitioner trains two classifiers f and that appear to disagree more often on a new dataset than baseline rate computed observation. (e.g., collected more training data) at a particular belief threshold (e.g.. probability greater than 80%). Furthermore, there is natural link between Equation 47 and covariate shift as exact knowledge of q > by definition implies not only covariate shift P * Q, but type that is harmful by our original definition in section 3 Therefore knowing the probability that q >> p is useful measure of how likely, without any additional assumptions, that we are experiencing a harmful covariate shift.
in-domain test set, they decide
that
D CONSTRAINED DISAGREEMENT LEARNING
We elaborate on the technical details of the objective functions required for training constrained disagreement classifiers.
D.1 DISAGREEMENT CROSS ENTROPY
Intuition. In our methodology, we propose the disagreement cross entropy (DCE) as simple loss function that encourages classifier to disagree with a target label while otherwise outputting high entropy prediction. DCE is equivalent to simply flipping the target label and computing the regular cross-entropy in the binary classification case.
Consider model that outputs a distribution {Pi, 1 1 P1 - P2) over 3 classes, suppose we would
like train it to not output high probability for class i. minimize P3 approach would be to maximize the standard cross entropy loss - log(1 - P1 - -p) that one would equivalently minimize if trying to output high probability for class 3. We show in Figure that this objective is unstable whereas the DCE //((l)((p1) + log(p2)) is convex, and takes on values in similar range to the regular cross entropy.
P1 P2. An intuitive
Loss Function. Let é denote discrete distribution over N classes and f target class E [1,.., N). We define the disagreement cross entropy as the cross entropy of ý with the uniform distribution
23

---

Published as a conference paper at ICLR 2023
05
03
Negative Cross Entropy
Disagreement Cross Entropy
Regular Cross Entropy
Figure 8: Consider a classifier outputs a distribution (pi,P2, 1- 1-p1- over 3 classes. We compare the optimization landscape induced by either (left) minimizing the negative cross entropy for the target = P1 P2 (e.g trying not to predict class 3) (center) minimizing our disagreement cross entropy (DCE) for the same target and (right) minimizing the regular cross entropy (e.g trying to predict class 3). We observe that naively minimizing the negative cross entropy results in an unbounded local minima, while the DCE significantly more stable and scales similarly to the regular cross entropy. Gradients are overlaid to help better visualize the 3D geometry.
over all classes except
((.
Σ 1 Eez log(ū:)
(48)
This expression has the effect of minimizing the predicted probability of the target class dt while maximizing the overall entropy of the prediction. We note that if N = 2 as in binary classification, then Equation 48 falls back simple label flipping. Furthermore we ý Softmax() (1) for some real valued N dimensional logit vector 7.
(01,0) = N Σ Lipale + log
Σ exp(li)
(49)
When learning constrained disagreement classifiers using DCE, minimize the loss function in Equation 3] which applies the regular cross-entropy to the in-distribution samples and the DCE the possibly shifted target samples Q. Losses are combined with weighted sum whose weight should be set to 1/([Q/ + 1) as discussed in ssecteiion (Choosing A).
Validity of the DCE Measure. We introduce dentition of valid disagreement loss function and show that the DCE loss satisfies it.
Definition (A Valid Disagreement Loss Function), Let be the set of all probability vectors of length N whose maximum index is fixed target label y (1...., N). Similarly, let Q be the of all probability vectors whose maximum index is not uniquely equal to y. For instance, in the diree-dimensional case with y
P {11, pı - p22 max(p1)p2)
P1 -P2)
Q = { (pr, P2, P1 P2) s.t. max((1.P2) 2 1 - Pi - -p-2
and P1.P2 1 P2 11
A score S(p: y) is proper for disagreement if
V Vp
P min S(q:v) S S(p:)) qEQ
(50)
which to say that for every probability vector in P there exists a probability vector in Q that achieves score at least as low.
Theorem 3. The Disagreement Cross Entropy Loss is a valid disagreement loss function.
Proof. We show that the minimum DCE for probability vector q E is log(N 1) while the minimum DCE for e is log(N). First note that by definition of the DCE in Enquatioon 48 the unique probability vector that globally minimizes it with respect to target class y the vector
24

---

Published as a conference paper at ICLR 2023
with elements 1/ 1) for all indices v, where i # y and Vy = 0. v member of Q because it does not have a unique maximum at position y. Computing the DCE of v with respect to the target gives:
1
1 log
-
1
DCE(v.
log(v:)
x (N -)
(51)
- N
1 N
N N
log((N - 1)
(52)
Next note that since Py does not contribute to minimizing the DCE which the form Epepip, lpg(p) the minimal solution must minimize the term Py- However enforce p P we must have that V i E .I...., N) y, Py > Ps. Hence minimizing Py while making sure p E enforces Py > I/N for some some p: 2 I/N and produce vector p E Q. Without loss of generality choosing РИ 1/N a for some small >> 0 we must chose all other p; 1/N s.t. all E; 0 and Lie(1......)) NYW 4 E.
and all other p; < 1/N since if Py 1// could also chose
This gives a DCE of:
DCE(p, v)
1
log(p:)Lizv
1
Σ
log N 4
(53)
1 N
1 -N iE(
where lim e-0 1
Σ
log - = log(NN)
(54)
N
Ny
For all vectors p E P we cannot achieve a DCE of less than log(N) but the minimum DCE in Q is log(N- - 1) which is less than log(N), hence proving that the DCE is suitable scoring rule for disagreement.
Implementation. We provide a simple PyTorch style implementation for batched computation of the CDC objective in Eqquation given batch of logits and targets. We assume logits a floating point vector of (batch_sizz x N) logit values, targets is integer vector (batch_size) of target classes, mask a 0-1 mask size) that at index if logits [i] is P and 0 otherwise.
import torch, import torch. nn. functional F def edc_lcss (logits, targets, mask, weight-1/ (size of test 1))
select data in p
logits_P, targets_p = logiks targets [mask]
seiect data in Q logits targets_q
logits/l-man la-mask,, targets 1-mask]
cross entropy on with targets
loss_p F. F.cross_entropy (logits_P, targets_ reduction-None)
DCB on Q zero hot =
F.one_hor hot (targets_q, num classes-N)
loss_q (logits_e
het) sum (dim=l) (1
torch. logsumexp (logits_gg
Weighted mean
return torch.cal ([loss_p, weight loss_gl) mean ()
D.2 EXTENSION TO DISCRETE MODELS
When training models with arbitrary discrete or non-differentiable parameters concerning their objective (e.g., random forest), we must find more general solution for creating CDCs. Such solution should (I) reduce to the DCE when the model is, fact, continuous and trained using the standard cross-entropy, and (2) reduces to label flipping when N = 2 (binary classification). Our simple solution is to replicate every sample in Q exactly N 1 times and create a unique label for each from the set S == NN. where is the disagreement target. We also each sample weight of 1/(N - 1). In the case of N 2, this corresponds to no replication and simply assigning the opposite label. In the case where the model learns by cross-entropy, it equals Eqquatio
25

---

Published as a conference paper at ICLR 2023
Proof. We prove this statement starting with the definition of the cross entropy
N l- log(ūe)
CE(D.V)
(55)
Now we consider the sum of the cross entropy for each label in S:
N
E
Σ
c=y log(Ue)
(56)
yES
VES
Σ Login e log(ū.)
(57)
(N 1)DCE v)
(58)
Hence when giving each sample a weight of (N 1)-1 we recover the exact form of DCE.
0
D.3 DISAGREEMENT WITH OVERPARAMETERIAZ MODELS
Many existing tests for covariate shift that rely overparameterized models do not perform well in the small sample regime due to catastrophic overfitting. In this section, we explain how this phenomenon, if ignored, also be catastrophic for the Detectron but is easily fixable with simple early stopping technique. We recall the main hypothesis on which the Detectron is built:
Given base classifier f E F that well fit to a training dataset P, it is easier to learn another classifier F that disagrees with f unlabeled data Q but agrees with f on when the distribution of Q is far from that of
Restated with the ideas introduced in this work, the above translates the CDC objective being more easily satisfied when there is a harmful shift. This hypothesis is exemplified in Figure to the right, where we see that the CDC dis- agreement rate grows significantly more rapidly when Q is chosen to be out-of-distribun curve) versus in distribution (black curve). How- ever, as the models are overparameterized, the disagreement rate eventually reaches 1 indepen- dently of whether we use the true OOD data Q or the ID data P Since our test is computed based on the disagreement rate dq falling above 1 - a quantile of the calibration distribution of Φp the test will be highly uninformative if σQ = ΦQ =
1.0
Disagroement Rate
0.8
0.6
(blue
0.4
P
0.2
0.0
50
100
150
200
250
300
Training Batches
Figure 9: CDC Training Dynamies for Overparame- terized Models: Using the same experimental setup as the runtime study in Figure 4 we record the associated CDC disagreement rate both unseen in distribution data P (CIFAR 10) and known covariate shift Q (CIFAR 10.1). When we trained such an overparam- eterized model for too long the disagreement rate ap- proaches on both in and out-of-distribun leading to maximally uninformative test; it is, there- fore, erucial perform early stopping hefore the distribbutiiiii disagreement rate reaches
Note that it is critical to use the exact same train- ing algorithm on both the given test set Q and P ensure the statistical soundness of the Detectron, so one can tune the CDC learning algorithm on either Q or P* to achieve desired result then apply the exact same algorithm the other set and test for statistical differences. In our experiments with overparameterized models, we picked a relatively low number of training iterations to use (see subsection E.2 for details) practically eliminating the issue of overfitting. However, in general, one should fix training budget for CDCs so that they are far from reaching an ID disagreement rate of óp = 1. Knowing the exact level of Φp to stop at will depend the dataset and learning algorithm used but general guideline suggest 0.5 to allow for a large gap between ID and OOD disagreement rates while giving enough compute budget to achieve non-trivial results.
the in-distribution calibration
datasets
26

---

Published as a conference paper at ICLR 2023
E EXPERIMENTAL DETAILS
E BASE CLASSIFIERS
For each dataset used our experiments, we begin by training a hase classifier on the source domain portion of the dataset to use in subsequent experiments and baselines. For brief description of the datasets used and base classifiers, see seelea 4adnd for more detailed description of each dataset as well as what we have considered precisely as the source and shifted domains, see subsection F.2
We use a standard Resnet18 model pre-trained on ImageNet (Deng et al. 2009] made available in the torchvision library [Marcel and Rodriguez 2010) although we reinitialize the last network layer to have an output size of 10. We use stochastic gradient descent (SGD) with a base learning rate of 0.1, L2 regularization of 5 X 10-4, momentum of 0.9, batch size of 128 and cosine annealing learning rate schedule with a maximum 200 iterations stepped once per epoch for total of 200 epochs. We use the standard CIFAR-10 training split normalized by its mean (n [0. (0.4914, 4, 0.4822, 0.4465|) and standard deviation (a = [0.2023, 0994,, 0.2010)). Every epoch, randomly crop each image size of 32 x 32 after applying 0 padding of four pixels each spatial dimension, and we apply horizontal flip with probability 0.5. This model achieves a test performance of 87%. While this score is far from state-of-the-art on CIFAR-IO, our goal is not to construct perfect model. We wish to create reasonably good model as an example of model that could realistically be deployed in real-world settings. When training deep ensembles, we only vary the random seed in the range [0.....4). 4).
CIFAR 10.
We follow a similar approach to CIFAR 10. However, we use two output features (for binary classification of cancerous or benign pathology), batch size of 512, the ADAM opti- mizer [Kingma and Ba, 2015) with a base learning rate of 0.001, L2 regularization of 10-5 and a total of 5 training epochs for which we select the model with the best validation accuracy. This model achieves a test accuracy of 0.93. When training deep ensembles, we only vary the random seed in the range (0.....4]. 4].
Camelyon 17.
UCI Heart Disease. We train both neural networks and gradient boosted trees using the XGboost library [Chen and Guestrin 2016). For the neural network model, we use a simple MLP with input dimension of 9, 3 hidden layers of size 16 with ReLU activation followed by a 30% dropout layer and linear layer to 2 outputs (heart disease present or not). We use 358 samples for training and 120 for validation. We train for a maximum of 1000 epochs and select the model with the highest AUC on the validation set, performing early stopping if the validation AUC has not increased in over 100 epochs. This model achieves a test AUC computed on 119 samples of 0.85. As with CIFAR 10 and Camelyon 17. we only vary the random seed in the range [O......) 9] when training deep ensembles. Note that we chose a larger ensemble size here as models are fairly cheap to train. Another important trick when using small Q sizes is to sample all of Q in each batch filling the best with a random set of samples from P. Of procedure artificially inflates the size of Q so the hyperparameter À must account for this by picking up an extra multiplicative factor equal to (batches per epoch)
When training gradient boosted trees using XGboost we employ standard library parameters (1) = 0.1, auc,, max_ pox__dep== 6, subsample= 0.8, bytreeeee.br 88, min www._chlld_weihheee 1, objective= num_round= 10). This model while taking less then 5s to train achieves test AUC of 0.88.
E.2 CONSTRAINED DISAGREEMENT CLASSIFIERS
We expand on the experimental details for learning constrained disagreement classifiers (??). When training a CDC ((F.P.Q) we start by creating a new dataset that combines all elements of the labeled set P and the unlabeled set Q with pseudo labels inferred by the base classifier f. We store a single bit for each sample in the combined dataset to indicate if sample was originally drawn from P or Q. When training CDCs with neural networks, we use the DCE loss Equation 3 under similar semantics the pseudo-code implementation provided above. When training discrete models, we resort to our generalized approach in suusecttionn D.2 To reduce training time we initialize g using the exact same architecture/weights used to train ff (see sucessubecttonn E. I). For CIFAR 10, we train each CDC for a maximum of 10 epochs performing early stopping if the model drops in in-distribution validation performance by over 5%.
f and apply the exact same optimization algorithm/leaming rate
27

---

Published as a conference paper at ICLR 2023
We enforce the early stopping criteria to help prevent CDCs from overfitting to the disagreement loss when the target dataset has not come from a harmfully shifted domain. The intuition is the following: under the null. if target dataset Q comes from the same distribution P. then learning to disagree with f on Q while constrained to agree on all of P can only be solved by overfitting to predict with high entropy on the specific examples in Q, versus learning distinet pattern that distinguishes the distributions. Forcing a model to predict with high entropy on a subset of in-distribution datapoints can only hurt its associated in-distribution generalization, phenomenon which we can directly assess by measuring validation performance.
training dataset
The details for training CDCs on Camelyon 17 are the same as those described for CIFAR 10, however due to the large training set size (302436 samples) we simply select a random subset of size 50, 000 as P each epoch - number we experimentally deemed as sufficient to achieve low in-distribution generalization error. When training CDCs on the UCI Heart Disease dataset, we use XGBoost [Chen and Guestrin 2016] with the same hyperparameters described in /subsection E.
For the runtime experiment presented in Figure 4 we train each CDC for only one batch, where each batch contains a set of 100 samples Q and is filled up to batch size of 512 with random samples from P uuann After every batch we eliminate all samples where the CDC disagrees with the base predictions. We continue this for a maximum of 150 batches, but perform early stopping if 10 batches pass without at least one sample getting disagreed
E.3 DESCRIPTION OF BASELINE METHODS
We compare the Detectron against several methods for OOD detection, uncertainty estimation and covariate shift detection found in recent literature.
1. Deep Ensembles shown by Ovadia et al. (2019] to provide the most accurate estimates of predictive confidence under covariate shift. To compare directly with Detectron we test both the disagreements rates and the entropy distributions of the ensemble. SeeeAppen for more information on how these tests are run.
2. Black Box Shift Detection (BBSD) [Lipton et al., 2018 is overall best method across numerous synthetic benchmarks for covariate shift detection evaluated by Rabanser et al. We follow the same evaluation and perform univariate KS test on each dimension of the softmax output of the base classifier between Q and a held out set from the training distribution. Bonferroni correction is used to compute single p-value the minimum value divided by the number of tests. We guarantee significance using the same permutation approach described in Appendix B]
3. Relative Mahalanobis Distance (RMD) [Ren et al. 2021 (a method designed specifically for identifying near OOD samples) using the penultimate layer of a pretrained model. We test for covariate shift by performing a KS test directly on the distribution of RMD confidence scores derived on Q and P
4. Classifier two sample test (CTST) [Lopez-Paz and Oquab) 2017]. Using the same architecture and initialization as the base classifier we reconfigure the output layer and we train domain classifier on half the test data with source data labeled as 0 and test data as 1. We then test this models accuracy on the other half of the test data and compare its performance to random chance using a binomial test (see [Appendix B for more details). While this method is technically sound it is not suitable for the low data regime where learning a domain classifier on half the test data is unlikely to generalize beyond random performance on the other half.
5. Deep Kernel MMD (Liu et al. 2020 We use the authors original source code available at
com fenglin90/DK- for TSTT to perform the deep kernel
MMD test.
6. H- I--Divergence [Zhao et al. 2022]. Most similar to our approach, this work proposes a two sample test based on the output of learning model after training on either source or target data. Specifically, the authors fit a model to both the source dataset P, the target dataset Q and a uniform mixture (P + 2). Under the null hypothesis P Q the loss in each case is equal in expectation. However when P # Q, the generalized entropy of the mixture distribution may be be larger. In practice the authors fit three VAE (Kingma and Welling
28

---

Published as a conference paper at ICLR 2023
2014 models and compute the test statistic <((P Q)/2) min({(Q), where & is the VAE loss computed as a sum of the binary cross entropy reconstruction loss and the KL divergence regularizer. The perform 100 runs where the null hypothesis (e.g. sample Q from P) and one where it does not. Significance is determined in the standard way be observing if the true test statistic exceeds the 95th percentile of the test statistic distribution under the null hypothesis. Unfortunately this method, while state of the art on several benchmarks including the MNIST Fake MNIST two sample test, demonstrated low utility on more complex tasks with smaller sample sizes. After a discussion with the authors, we attempted to improve the results by first pretraining the VAE to produce valid samples and reconstructions under the source distribution and computing the H-Divergence statistic after finetuning. Despite this effort, we still was low statistical significance with small sample sizes likely due to the noisy nature of training VAE's in the low data regime. We use the authors original source code available here https: h //ggttgttthh///gg/// com/ a 7lb23/ Dtt//----iveeeeeeee
E.4 COMPARISON TO GENERALIZATION ERROR PREDICTION
Related distribution shift detection is the problem of estimating out of distribution generalization error on unlabeled data. Any method that estimates generalization error can be thought of as a regression from dataset on a real valued test statistic tb which represents the estimated generalization сгтor. As such we can calibrate the distribution of & based on unseen iid data in P and test for distribution shift by determining if the predicted generalization error on Q within the 5% extreme of the calibration distribution.
Many recent methods (Platanios et al. [016 Yu et al., 2022 Garg al., 2022] have been proposed to address this problem. Garge et al. propose the simplest approach their method is conceptually identical to BBSD when applied to the task of shift detection. Hence we compare only with the Projection Norm approach of Yu et al.] as it presents the current state of the art and provides well documents experimental repository. A comparison on the CIFAR10/10.1 benchmark is found in Table 2] and a further analysis of the scaling is given in Table 3 Ultimately, the Projection Norm presents another useful approach for identifying covariate shift, however the computational complexity is at least equal in most cases greater than the Detectron and the performance is in all cases lower.
Table 2: Comparison of Detectron (Entropy) and the Projection Norm Yu et al.
2022
We report the
TPR @5 for both methods using sample sizes of 10, 20 and 50.
QQ| = 10
[Q]
20
[Q] 50
ProjNorm Yu et al. 2022
.11 + .03
.17 +: .04
.39 + .05
Detectron (Entropy)
.35 +: .05
.56 +: .05
.92 + .03
Table 3: Projection Norm results YYu et al.
2022 on larger samples sizes of CIFARIO/10.1 We observe that ze 500 samples are required reach near perfect test power.
Q
100
[Q]
200
[Q
500
Q
1000
ProjNorm Yu et al. 2022
.48 + .05
.76 + .04
.99 +: .01
1.0 = 0
F DATASETS
F.I SOURCES AND LICENSEES
CIFAR-10 (MIT License Copyright (c) 2013 Valay Shah)
Camelyon- 17 (CCO 1.0 Universal Public Domain Dedication)
UCI Heart Disease (Creative Commons Attribution 4.0 International)
29

---

Published as a conference paper at ICLR 2023
F.2 PREPOSSESSING SHIFT DESCRIPTIONS AND MODEL PERFORMANCE
We provide full details on the three datasets used in our experiments, including any preprocessing steps and what splits we considered source domain and target domain Q
CIFAR 10/10.1. We use the well known CIFAR 10 dataset (Krizhevsky et al. 2014 as the source domain for training base classifiers (subsection E.1 and the new CIFAR 10 set CIFAR 10.1 containing 2000 class balanced images |eect et al. 2019] as source of harmful distribution shift. Although the images in CIFAR 10.1 appear to be visually very similar CIFAR most classifiers trained on CIFAR 10 drop significantly in performance (3% to 15% [Recht et al. 2019) when tested on CIFAR 10.1.
CIFAR 10.1
CIFAR 10 (Original)
Figure 10: Cifar 10 vs Cifar 10.1. (Image borrowed from the technical report "Do CIFAR-10 Classifiers Generalize to CIFAR- 10?" [Recht al. 2018
Camelyon 17. As described by the original authors [Veeling al. 2018 the Camelyon benchmark a new and challenging image classification dataset consisting of 327,680 color images (96 x 96) extracted from histopathologic scans of lymph node sections. Each image annotated with binary label indicating the presence of metastatic tissue in the center 32 x 32 pixel region. In our experiments, we use the WILDS [Koh et al. 2021] framework facilitate download, preprocessing, as well as source/target splits for Camelyon. As shown in |Figure I1] the source domain is chosen as data from hospitals 1, 2, contrast, the test domain collected from hospital 5, which visually shows significantly higher contrast due to different data acquisition equipment/methods.
Train
Hosp 1-3
Hosp
Hosp
Figure 11: Samples images from the Camelyon 17 dataset Vveling et al. 2018 Using the standard set by the WILDS framework (Koh al. 2021] hospitals 1-3 the source domain for training and validating models, and hospital 5 as the target domain for assessing distribution shift.
30

---

Published as a conference paper at ICLR 2023
age
resting pressure
resting electrocardiograpiic results
0.5
0.6
0.4
0.5
0.20
0.3
0.4
0.15
0.3
0.2
0.10
0.1
30
50
60
70
80
0.0
200
0.0
-0.5
0.0
0.5
1.0
155
2.0
25
Sex
cholesterol
maximum heart achieved
1.0
0.8
0.15
0.15
0.8
0.10
0.4
0.00
0.00
-0.5
0.0
0.5
1.0
1.5
pain lype
fasting sugar
exercise induced angina
0.7
0.7
0.8
0.8
0.6
0.5
0.5
0.4
0.3
0.3
0.2
0.1
0.0
0.0
Figure 12: Marginal distributions for each of the nine variables chosen from the UCI Heart Disease dataset for our experiments. The source domain (yellow) is chosen from the Cleveland and Hungary patient databases, while the shifted target domain (blue) is selected from the Swiss and Long Beach databases. Although the distributions are visually similar, simple neural network classifier that achieves AUC of 0.85 on the source domain drops to 0.42 on the target domain.
UCT Heart Disease. The UCI Heart Disease (UCI-HD) dataset (Janosi et al. 1988 consists of 76 attributes collected from four unique patient databases in Cleveland, Hungary, Switzerland, and the VA Long Beach. We select nine features out of the commonly used 14 to minimize the portion of missing values. These features are (age, sex, chest pain type, resting blood pressure, serum cholesterol, fasting blood sugar, resting clectrocardiographic results, maximum heart rate achieved, exercise-induces angina). The prediction task is to determine the diagnosis of heart disease (also known as angiographic disease status), which is given in range from 0-4, where indicates healthy and 1 1-4 indicates a severity level based on the narrowing major blood vessels. Following prior work [Chaki et al. 2015) we only consider the simplified binary classification task for differentiating patients with normal angiographic status (label of 0) from those with abnormal status (label >> 0). We select the source domain as the Cleveland and Hungary databases and the target domain as the Switzerland and VA Long Beach databases. A graphical overview of the marginal feature distributions for the source and target domain is shown in Figure 12
To allow for out-of-the-box training of deep neural networks the UCI HD dataset, we use the missing value synthesis functional in Wolfram Mathematica [Inc.). The algorithm uses density estimation and mode finding conditioned distributions synthesize missing values. See the language guide page titled Synthesize Missing Values in Numeric Data for more detailed descrip- tion. To aid in future research, provide copy of our processed dataset in Kour github repo> / dat
summary of the three datasets used as well the description of shifts and effects model performance provided in Table
G EXPANDING ON GENERALIZATION REGIONS
We expand the concept of the generalization region R proposed in section 3 We highlight that not all covariate shifts will be harmful to the performance of a model, as in many cases, the model will generalize to region more extensive than the support of the training distribution. We informally
31

---

Published as a conference paper at ICLR 2023
Table 4: Datasets: We investigate three different forms of covariate shift. To verify that these shifts indeed harmful the models, we report performance both the shifted and unshifted domains. Examples and further descriptions of unshifted/shifted splits of each dataset are given in Appendix
Domain/Task
Dataset
Shift
Metric
(Unshifted)
(Shifted)
Natural Images Object classification
CIFAR-10/10.1
Data Collection
Accuracy 0.87 (Resent18) 0.77 (Resent18)
Recht et al. 2019
Process
Histopathological Tmages
Camelyon- 17
Different Hospitals
Accuracy 0.93 (Resent18) 0.81 (Resent18)
Metastases Detection
Veeling ct al. 2018
Tabular Medical Data Angiographic Status
UCI Heart Disease Janosi et al. 1988
Different Countries
0.88 (xgboost)
0,70 (xgboost)
AUROC
0.85 (MLP)
0.42 (MLP)
1.0
0.9
Test Accuracy
0.8
Train
0.7
Test
0.6
-20
20
40
60
80
100
2
2
2
Rotation Angle
Figure 13: We train CNN with the LeNet-5 architecture [LeCun et al. 1989 dataset consisting of MNIST images rotated from ( to 80 degrees counterclockwise in steps of 20. We test the model using rotations of 25 to 125 degrees in steps of 5. We observe that the model achieves nearly identical test accuracy on all test angles between -5 and 85, indicating that has generalized to angles outside of its training set.
refer this region and note that characterizing it precisely is intractable as it depends the complex interaction between a model, dataset, and learning algorithm. When detecting distribution shifts, we primarily concerned with those that will harm the performance of predictive model in deployment; those are shifts that are not simply any changes in the training distribution but ones that assign high probability samples outside of the generalization region. The Detectron aims to use not just model and dataset to detect shifts but also the learning algorithm to tie the detection of shifts directly with R.
While this argument is informal, we present an experiment to show that a non-trivial generalization region does exist in a simple machine learning task. Figure 13 shows that LeNet-5 model [LeCun) et al. 1989) trained rotated MNIST images can match in-distribution performance when tested on various rotations outside of its training set. We train this model for ten epochs using the ADAM optimizer base learning rate of 0.001. By leveraging model's existing learning algorithm when detecting shifts using the Detectron we can detect new and unlabeled datasets are likely to belong to model that is constrained to learn the same behavior over R while encouraging
R training to predict randomly otherwise. While this experiment is simplistic, shows that learning algorithms can generalize to outside their training distribution.
H HARMFUL COVARIATE SHIFT AND CONNECTION TO A DISTANCE
Given labeled training set P well as another labeled dataset Q, identify using standard statistical estimation if model performs more poorly on Q compared to P. However, a practical scenario, decision models are deployed unlabeled datasets; hence directly computing model
32

---

Published as a conference paper at ICLR 2023
performance is impossible. To decide then if Q has been drawn from distribution that may cause to fail, we formulate an adversarial learning style definition of harmful covariate shift that does not require access to labeled examples.
Definition: (l, a, H--Harfful Covariate Shift.
A covariate shift from distributions P + Q over X is (f, a; F)y-hrrful with respect set of decision models F, if there exists any subset of models of two or more models f F that achieve a source domain loss e(J; P) I for all f while being more likely disagree with each other on an unseen sample from Q compared to P.
C V f P() 2 and
(59)
P3 ft. E f s.t. fi(x) + fx(x)) > Pa-p(3 Jz E s.t. fi(x) + [2())
(60)
In plainer words, define harmful covariate shift based on the existence of multiple good models on P that tend to disagree on O. The Detectron algorithm is designed to learn these models (constrained disagreement classifiers) and statistically test their disagreement rates.
We can connect our definition of harmfulness to the well-studied concept of A distance from Kifer al. (2004). The A is generalization of the total variation to an arbitary collection of measurable events A.
(P, 2) = sup [Pro[A] Pr AEA
(61)
Ben-David al. 2006) shows that when they chose a class of events whose characteristic functions are functions in F, the A distance in connection with VC theory [Vapnik 1995] allows for finite
sample generalization bounds on the performance of arbitrary decision models from F under covariate shift. BBn--David et al. (2006) go on to show that the A distance defined for a binary function class F equal
dr 2) = (1
min err(s) 1 JEF
(62)
where min err(f) is the minimum error that domain classifier from F can achieve on the task of distinguishing samples from and (i.e. if = Q the best domain classifier will have error of 0.5 and (P, Q) = O and if P and Q can be perfectly discriminated by some f E F the dr(P, Q) is maximized and equal to 2). In our characterization of harmful covariate shift, we consider not just the discriminative power of F' but the broader generalization region (Appendix G) induced by training f to achieve a certain source domain loss on P. For instance, if a model naturally learns rotational invariance, shown in Figurre 13 one would also want to use shift detector that will not detect shifts that only comprise of rotations. Beyond the concept of harmfulness, we empirically show that learning to detect shifts using CDCs instead of domain classifiers improves shift detection performance.
I ON MODEL COMPLEXITY AND THE DETECTRON
In our methodology, we aim to specifically detect covariate shifts that lead to unpredictable behavior of models over given function class F. To better understand how the complexity of F changes the behavior of the Detectron, we present a simple example in Figure 14
The Detectron is designed to work in the central and right case of Figure 14 (e.g., where we learn function class F that contains the true underlying mechanism that labels our data). However, the types of shifts considered harmful will change with the complexity of F. In the ideal case where the model class complexity matches that of the true mechanism, we see that the model family does not allow significant variation on the decisions for points outside but close the training distribution meaning the Detectron will not, by design, detect nearby shifts. When models are overly complex, more types of shifts should naturally be considered harmful as there more variation than models from F can possess outside of the training domain, meaning we can never guarantee that we have chosen the correct model. In the last case, where the model family is too simple to contain the true mechanism, the Detectron loses its power to identify shifts that may result in performance penalties, as would any comparable method from OOD/uncertainty estimation that relies on a sufficiently well-calibrated classifier. The inability of our approach to handle this case is unavoidable limitation of our methodology. However, models that are simpler than their underlying mechanism will often exhibit poor held performance even on in-distribution tasks, drastically limiting the likelihood of deployment.
33

---

Published as a conference paper at ICLR 2023
Figure 14: Investigating the relation between CDC model complexity and the ability to identify covariate shift. We consider toy example where the ground truth labels generated using quadratic decision boundary, shown as a black dashed line. The blue points correspond to training samples, and the orange/green points correspond two different covariate shifts, one closer to training distribution When we choose an overly simplified model family (e.g., linear classifiers). there exists no CDC that reports different explanations for the orange and green points. (Center) When we choose a quadratic function family, there exists enough variation within the space of models that explain the training to offer different explanations on the distance shift (orange) not the near shift (green). (Right) When we learn from overly expressive function family (polynomials of degree 3+), the space models that explain the training set can offer different explanations of even near covariate shifts (green points).
the other further. (Left)
In general, choosing a model family that is well specified for a given task is nontrivial and still an open question in machine learning. This concern somewhat diminished in cases where models are over perr-arrmeteeized (e.g.. deep neural networks) models are built using expert knowledge related to the true underlying mechanism, as is often the case practical machine learning problems.
34


Reviews:
[{"review_id": "e_60FLLjhv", "reviewer": "Reviewer_wkvQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work develops a new hypothesis testing procedure for identifying harmful covariate shifts. To identify harmful covariate shifts, the authors propose to use disagreement cross entropy for multiple models and present Detectron (Disagreement) based on a permutation test. ", "summary_of_the_review": "The submitted paper considers an interesting problem, and the proposed approach makes sense at a high level. However, it lacks clarity which causes much confusion, so I think it is not ready for publication.\n\n", "strength_and_weaknesses": "- Strength\n  - The idea of using an ensemble of models that maximize out-of-domain disagreement makes sense. \n  - Related work section fairly covers literature in the field.\n  - Extensive experiments are performed.\n \n- Weakness\n  - The paper critically lacks clarity and is not mathematically rigorous. It really causes lots of confusion. Please see Clarity, Quality, Novelty, And Reproducibility.\n  - Implication of Theorem 1 is not clear. As far as I understand, it is almost impossible to know when the following condition holds: the rate which $g$ disagrees with $f$ on $n$ unseen samples from $\\mathcal{Q}$ is greater than that from $n$ unseen samples from $\\mathcal{P}$ w.p. greater than $p^{*} = (1-4^{-n} \\binom{2n}{n} )/2$. Given that the probability is derived from the expectation of such random experiments, we might need multiple sets of $n$ unseen samples, which is not realistic. \n\n- Question:\n  - Theorem 1: do you have an insight into why $p^*$ is independent of $N$? Does it imply that this theorem holds even $N=1$? It is not intuitive... \n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VfBCGMb30a", "reviewer": "Reviewer_C9Zo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method for detecting covariate shift by training two classifiers to agree on a distribution P and disagree on another distribution Q, and then build a hypothesis test on top of these two classifiers. Their proposed method is able to detect covariate shifts better than several competing approaches. However, there seems to be potential failure cases for the method that the authors do not discuss sufficiently. \n", "summary_of_the_review": "This paper propose an interesting approach for detecting covariate shifts, and the authors spend a lot of effort in its theoretical and empirical analysis. However, there seems to be potential cases that the method can fail which the authors do not cover sufficiently. A better discussions on these, even listing them as limitations or assumptions, can help improve the paper. \n", "strength_and_weaknesses": "Strengths: \n- The authors provide very detailed theoretical and empirical analysis of their method, in both the main paper and the appendix. \n- The proposed method works well, beating several other methods for detecting covariate shifts in the experiments. \n\n\nWeaknesses: \n- While the approach provides good empirical performance, the core idea of the method is still unclear to me, in terms of how the assumptions might fail. The main idea of the method is to detect harmful covariate shifts by training two classifiers, forcing them to agree on P while disagreeing on Q. There are several possible scenarios: \n  1. If it's possible to train such a pair of classifiers f and g, it does not necessarily mean the shift from P to Q is harmful. Consider linear model on disjoint supports P and Q. It just means P and Q are different. If we just want to detect shifts between P and Q, why do we not use non-parametric tests such as the KS test, or train a logistic regression model distinguishing P and Q as commonly used in covariate shift correction? \n  2. If it's not possible to train such a pair of classifiers f and g, it might just be that the models are underfitting. Consider fitting linear models to quadratic target y = x^2 between -1 and 1. P is positive region, Q is negative region. It is not possible to fit linear models that agree on P but disagree on Q, but P and Q are distinct.  \n\n  Although these are specific boundary cases on potential failure modes, the fact that the current method does not seem to cover them properly make me uncertain about the the method. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SNppwAJUduR", "reviewer": "Reviewer_En7A", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of detecting covariate shifts where a trained model would perform differently. In particular, the authors propose a framework that prepares new models that disagree with the base model and then uses the disagreement rates (or prediction entropy) to build the statistical test.", "summary_of_the_review": "While the proposed framework provides interesting solutions for training different models and building the statistical tests, this paper might require further work on involving and discussing critical related work before getting published as high-impact research.\n\n\n=======After author feedback============\n\nThank the authors again for the extensive feedback. The added explanation and experiments regarding performance estimation are a nice addition to the paper. I have decided to change the score to 6 as a result, but I think some systematic refinement on the paper would make it much stronger (i.e. the disagreement loss, and connections to performance estimators). ", "strength_and_weaknesses": "(+) The problem of detecting performance change with an unlabelled dataset is a practical question for many ML applications.\n\n(+) The proposed framework of training disagreeing models and using the model predictions to build test statistics provides an interesting development to the research problem.  \n\n(-) While this paper has good coverage of related work on drift (covariate shift) detection, the coverage of methods that estimate the model performance on unlabelled datasets is limited. This limited coverage could be crucial as some methods use similar ideas of modelling the disagreement among multiple models and can be used directly to solve the targeted research problem. (See below for details.)\n\n(-) Some details of the paper might need additional justification, such as the objective learning function for model disagreements, the proposed test statistics, and baseline approaches. (See below for details). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "41ch1Dv9D0k", "reviewer": "Reviewer_DJjN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a learning-based testing method to identify distribution shifts (a new domain) with access to finite samples of the test domain. The authors define harmful covariate shift (HCS) that may weaken the generalization of a predictive model, and constrained disagreement classifiers (CDC) that performs consistently on ID data and inconsistently on OOD data. Then they detect HCS by the inconsistency of the outputs of the constrained disagreement classifiers. Theoretical analysis shows that the disagreement rate of CDCs can be used to detect covariate shifts. The proposed algorithm uses the empirical distribution of the CDCs on the training data to determine the reject region.", "summary_of_the_review": "I recommend marginal rejection. Overall, this is a potentially promising work. But I do not think the current version is ready for publication. ", "strength_and_weaknesses": "**Strength:**\n1. The authors propose disagreement cross-entropy to improve the optimization procedure of the PQ-learning problem.\n2. This work develops a hypothesis testing method to detect covariate shifts and the detection principle is consistent with the common theoretical understanding that extrapolation increases the variance of outputs.\n3. Experiments show that the proposed method is sample efficient.\n\n**Weakness:**\n\n1. The motivation is unclear. In Section 3, the generalization set $\\mathcal{R}$ is a set of distributions. Is it possible that $\\mathcal{P}$'s support set overlaps with $\\mathcal{Q}$'s support set? If $\\mathcal{Q}$'s support set is a subset of $\\mathcal{P}$'s support set, how to understand the harmful covariate shift? Can you disentangle the effect of correlation shift ( the relation between the inputs and outputs $P(Y|X)$ ) and the effect of harmful covariate shift? \n2. Need more analysis on the utility of disagreement-cross-entropy. In Eq. (3), if we remove the disagreement-cross-entropy loss, how does the performance of Detectron change? Does the learning procedure of $g$ change the correlation between $Y$ and the features in $f(X)$? \n3. What are the requirements for the pre-trained model $f$? Is $f$ required to achieve good prediction accuracy? How does the proposed detection method perform if the ID data is ImageNet?\n4. If the pre-trained model $f$ is over-parameterized, can we force the disagreement rate on ID data to be 0%? Then how to implement Algorithm 1?\n5. Theorem 1: \"… If the rate … greater than … there must be covariate shift.\" This is already a hard threshold. Why do you still consider a hypothesis test approach?\n6. Can we consider the task in this paper as an OOD detection task with auxiliary data? If so, a comparison with recent OOD Detection methods is required, e.g. POEM.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster