SEQUENTIAL COVARIATE SHIFT DETECTION USING CLASSIFIER TWO-SAMPLE TESTS
Year: 2021

Abstract:
A standard assumption in supervised learning is that the training data and test data are from the same distribution. However, this assumption often fails to hold in practice, which can cause the learned model to perform poorly. We consider the problem of detecting covariate shift, where the covariate distribution shifts but the conditional distribution of labels given covariates remains the same. This problem can naturally be solved using a two-sample test—i.e., test whether the current test distribution of covariates equals the training distribution of covariates. Our algorithm builds on classifier tests, which train a discriminator to distinguish train and test covariates, and then use the accuracy of this discriminator as a test statistic. A key challenge is that classifier tests assume given a fixed set of test covariates. In practice, test covariates often arrive sequentially over time—e.g., a self-driving car observes a stream of images while driving. Furthermore, covariate shift can occur multiple times—i.e., shift and then shift back later or gradually shift over time. To address these challenges, our algorithm trains the discriminator online. Furthermore, it evaluates test accuracy using each new covariate before taking a gradient step; this strategy avoids constructing a held-out test set, which can reduce sample efficiency. We prove that this optimization preserves the correctness—i.e., our algorithm achieves a desired bound on the false positive rate. In our experiments, we show that our algorithm efficiently detects covariate shifts on ImageNet.

text: A standard assumption in supervised learning is that the training data and test data are from the same distribution. However, this assumption often fails to hold in practice, which can cause the learned model to perform poorly. We consider the problem of detecting covariate shift, where the covariate distribution shifts but the conditional distribution of labels given covariates remains the same. This problem can naturally be solved using a two-sample test—i.e., test whether the current test distribution of covariates equals the training distribution of covariates. Our algorithm builds on classifier tests, which train a discriminator to distinguish train and test covariates, and then use the accuracy of this discriminator as a test statistic. A key challenge is that classifier tests assume given a fixed set of test covariates. In practice, test covariates often arrive sequentially over time—e.g., a self-driving car observes a stream of images while driving. Furthermore, covariate shift can occur multiple times—i.e., shift and then shift back later or gradually shift over time. To address these challenges, our algorithm trains the discriminator online. Furthermore, it evaluates test accuracy using each new covariate before taking a gradient step; this strategy avoids constructing a held-out test set, which can reduce sample efficiency. We prove that this optimization preserves the correctness—i.e., our algorithm achieves a desired bound on the false positive rate. In our experiments, we show that our algorithm efficiently detects covariate shifts on ImageNet.

heading: 1 INTRODUCTION
text: A key challenge facing deep neural networks is their sensitivity to changes in the data distribution. In particular, supervised learning traditionally assumes that the training and test data are from the same distribution (Vapnik, 1998), but this assumption often fails in practice. For example, an autonomous car using perception to identify obstacles needs to be robust to shifts such as changes in the weather and lighting conditions. We focus on covariate shift (Shimodaira, 2000), where there is a shift in the covariate distribution p(x), and the conditional label distribution p(y | x) remains unchanged. Covariate shift can reduce model performance (Sugiyama & Müller, 2005), invalidate uncertainty estimates (Ovadia et al., 2019; Park et al., 2020), and affect model selection (Sugiyama et al., 2007).
One strategy is to devise an algorithm to detect covariate shift; if detected, the algorithm can alert the user that predictions may be unreliable. Covariate shift detection can be formulated as two-sample hypothesis test (Gretton et al., 2012a; Rabanser et al., 2018; Liu et al., 2020), where the goal is to determine whether two sets of examples are from the same distribution. To test for covariate shift, we choose the first sample to be the data used to train the model and the second sample to be recent test data given as input to the model. Then, the detector returns “covariate shift” if the hypothesis test indicates that the two samples are from different distributions and “no shift” otherwise.
We propose a detection algorithm based on classifier tests (Lopez-Paz & Oquab, 2017; Cheng & Cloninger, 2019; Kim et al., 2021), which use the accuracy of a classifier trained to distinguish the two samples as the test statistic. In particular, if the two samples are from the same distribution, then the accuracy should be 1/2; otherwise, it should be> 1/2. Since the test statistic follows a binomial distribution, we use the Clopper-Pearson interval (Clopper & Pearson, 1934) (an exact confidence interval for the unknown success probability of the Binomial distribution) to derive the cutoff. In contrast, prior work relies on asymptotics to derive the cutoff, which results in approximations.
A key challenge is that the test examples are typically obtained over time—e.g., an autonomous robot continuously perceives its environment, and we want to detect if its distribution of observations shifts at any time. There are two key challenges to leveraging classifier tests in this setting. First, they rely on training a classifier to distinguish training and test examples; doing so on every step would be computationally intractable. Second, they rely on a held-out test set to estimate the test statistic, but constructing such a set online would reduce sample efficiency.
Rather than train a classifier at each step, our proposed algorithm trains a model online using stochastic gradient descent. Then, rather than construct a held-out test set, our algorithm evaluates the accuracy of the model online using each example before taking a gradient step on that example. We prove that this strategy results in an unbiased estimate of the model accuracy; as a consequence, the finite-sample guarantees on the false positive rate provided by the sequential test continue to hold. In addition, we prove bounds on the false negative rate under mild conditions on the classifier (i.e., it achieves nontrivial accuracy distinguishing the two distributions).
We evaluate our approach on both synthetic and natural shifts on the ImageNet (Russakovsky et al., 2015) dataset. In particular, we demonstrate that our approach achieves better sample efficiency than baseline algorithms; furthermore, it uniformly satisfies the desired false positive rate. Thus, our algorithm is an effective strategy for sequential covariate shift detection.
Contributions. We formulate (sequential) covariate shift detection as a two-sample test, and propose a novel algorithm to solve this problem (Section 3). Then, we prove finite sample bounds on false positive rate and false negative rate achieved by our algorithm (Section 4). Finally, we empirically demonstrate that our algorithm effectively detects shifts on ImageNet (Section 5).
Sequential detection vs. sequential tests. While we consider the sequential setting, we deliberately choose not use a sequential hypothesis test, since the covariate shift may occur after a delay or gradually over time. A sequential test only applies if all of the test data is shifted. Furthermore, since we are not using sequential tests, the false positive rate bound only holds per-step, not uniformly across all steps. This is necessary: we cannot guarantee that we detect a covariate shift occurring at a later point in time if we constrain the false positive to be bounded uniformly across all steps. In our experiments, we show that the rate of false alarms remains manageable while enabling our algorithm to detect covariate shift in a number of interesting scenarios.

heading: 2 RELATED WORK
text: Covariate shift. There has been work on training models in the presence of covariate shift. In particular, in the unsupervised domain adaptation setting (Ben-David et al., 2007; Bickel et al., 2007; Ganin et al., 2016), the algorithm has access to labeled examples from the source domain but only unlabeled examples from the target domain, and the goal is to train a model that achieves good performance on the target domain. One strategy is to use importance weighting to upweight source examples that are more similar to target examples (Bickel et al., 2007). Another strategy is to first learn an invariant representation (Ganin et al., 2016), which is an embedding space where the source and target examples are similar, and then train a model on this embedding space using the source examples. If we detect covariate shift, one solution is to retrain the model using these techniques.
Two-sample tests. We focus on classifier two-sample tests (C2ST). In this approach, the idea is to train a binary classifier to distinguish source and target samples, compute a real-valued score based on this classifier as the test statistic, and then use a univariate two-sample test to determine the cutoff for rejecting the null hypothesis (Friedman, 2004). A natural test statistic is the classifier’s accuracy on a held-out test set (Kim et al., 2021; Lopez-Paz & Oquab, 2017), or the differences in the classifier’s logits (Cheng & Cloninger, 2019); in this work, we use the former. One way to compute the cutoff is to use the asymptotic distribution of the test statistic (Lopez-Paz & Oquab, 2017). Nonparametric tests such as permutation tests can also be used (Kim et al., 2021).
Another kind of two-sample test is called a kernel two-sample test. In this approach, the idea is to use the maximum mean discrepancy (MMD) between the two samples according to a given kernel embedding as the test statistic (Gretton et al., 2012a; Chwialkowski et al., 2015; Jitkrittum et al., 2016). The key design decision is the choice of kernel. One strategy is to use a nonparametric kernel such as Gaussian radial basis functions (Gretton et al., 2012a); alternatively, the kernel can also be optimized to minimize the false negative rate of the resulting test (Gretton et al., 2012b). In addition,
recent work has shown how to first learn a kernel function in the form of a deep neural network, and then evaluate the MMD distance on a held-out test set (Liu et al., 2020). The test statistic can be chosen based on finite sample bounds or based on its asymptotic distribution (Gretton et al., 2012a). Nonparametric permutation tests can also be used (Liu et al., 2020) with this approach.
Concept Drift. In the context of concept drift (Gama et al., 2014), there has been work detecting shifts in p(x, y) (Gonçalves Jr et al., 2014). However, this work assumes that ground truth labels are provided for test examples, whereas our approach only requires unlabeled test examples. The former is substantially easier, since it suffices to check for drift in the distribution of prediction errors, which is usually very simple (e.g., a Bernoulli distribution for the 0-1 loss), making it easy to test for drift. In contrast, our approach checks for drift in high-dimensional covariates distribution.
Sequential hypothesis testing. A closely related problem is sequential hypothesis testing, which adaptively decides whether to reject the null hypothesis as samples become available (Wald, 1945). These approaches can also applied to two-sample testing (Balsubramani & Ramdas, 2015; Lhéritier & Cazals, 2018; 2019; Manole & Ramdas, 2021). However, as discussed above, they assume that the each distribution of the two samples does not change over time. In contrast, we are interested in the setting where the test examples might initially be from the same distribution as the training examples, but then shift at a later point in time. Sequential tests are not applicable to this setting.

heading: 3 SEQUENTIAL COVARIATE SHIFT DETECTION

heading: 3.1 PROBLEM FORMULATION
text: Let X be the covariate space, S be the source distribution over X , and Tt1:t2 = (Tt1 , Tt1+1, . . . , Tt2) be a sequence of target distributions over X from time steps t1 to t2. On time step t, we consider samples xt ∼ S and x′t ∼ Tt; in practice, S can be taken to be the uniform distribution over the training set. We let Sw,t = (xt−w+1, xt−w+2, . . . , xt) and Tw,t = (x′t−w+1, x ′ t−w+2, . . . , x ′ t) denote the recent examples in a time window of a given size w ∈ N. Our goal is to detect covariate shift at any step t. More precisely, we want to determine whether S 6= T̄w,t, where T̄w,t = ∑t k=t−w+1 Tk/w, i.e., whether the average target distributions over the previousw steps is shifted compared to S. For a fixed step t, this problem is a two-sample hypothesis test (Lehmann & Romano, 2006), where the null hypothesis is H0 : S = T̄w,t, and the alternative hypothesis is H1 : S 6= T̄w,t. That is, a two-sample test f̂ is designed to compute
f̂(Sw,t, Tw,t) ≈ {
1 if S 6= T̄w,t 0 otherwise.
Our goal is to design a two-sample test f̂ for detecting covariate shift with this data stream. While we can in principle use any two-sample test, our goal is to design one that is both sample and computationally efficient while achieving high accuracy for high-dimensional data such as images. In addition, we want the test f̂ to come with finite sample guarantees on the false positive rate. In particular, given α ∈ R>0, if S = T̄w,t, we want to ensure
PSw,t∼Sw,Tw,t∼Tt−w+1:t [ f̂(Sw,t, Tw,t;α) = 0 ] ≥ 1− α.
Ideally, we also want to provide finite sample bounds on the false negative rate; however, for classifier tests, we can only do so under additional assumptions about the model family used to try and distinguish S and T̄w,t. Intuitively, we assume that (i) the model family has bounded complexity (e.g., Rademacher complexity), and (ii) some model exists in the family that achieves nontrivial accuracy at distinguishing S and T̄w,t. Then, our goal is to ensure that if S 6= T̄w,t, we have
PSw,t∼Sw,Tw,t∼Tt−w+1:t [ f̂(Sw,t, Tw,t;α) = 1 ] ≥ 1−M(α,w)
for some function M(α,w) that depends on the model family.

heading: 3.2 ALGORITHM OVERVIEW
text: Next, we describe our two-sample test. We build on classifier two-sample test (C2ST) (Lopez-Paz & Oquab, 2017; Kim et al., 2021). The idea is to train a classifier ĝt to try and distinguish Sw,t
Algorithm 1 Sequential Calibrated Classifier Two-Sample Test 1: Input: significance level α, window size w 2: for each time step t do 3: Draw examples xt ∼ S, x′t ∼ Tt 4: Predict ŷt = ĝt(xt) and ŷ′t = ĝt(x ′ t) (.) Source-target prediction
5: Detect covariate shift if 0.5 6∈ ΘCP(2wµ̂w,t, 2w;α) (.) Calibrated covariate shift detection 6: Update ĝt using (xt, 0) and (x′t, 1) (.) Online source-target classifier update 7: end for
from Tw,t. Intuitively, if S and T̄w,t are different distributions, then ĝt should achieve nontrivial accuracy at distinguishing Sw,t from Tw,t (assuming the model family is sufficiently expressive). Alternatively, if S = T̄w,t, then ĝt necessarily achieves a trivial expected accuracy of 1/2. In particular, the accuracy of ĝt can be used as a test statistic for the two-sample test. To choose the cutoff for rejecting the null hypothesis, we use the Clopper-Pearson (CP) interval (Clopper & Pearson, 1934) to construct an interval that contains the true accuracy ĝt with high probability based on the accuracy of ĝt on a test set. More precisely, the CP interval is an exact confidence interval around the empirical estimate of the mean of a Bernoulli random variable. Letting z1, ..., zn ∼ Bernoulli(µ∗) be i.i.d. samples from a Bernoulli distribution with true mean µ∗, the (unnormalized) estimate of its mean n · µ̂(z1:n) = ∑n i=1 zi has distribution Binomial(n, µ
∗). Then, the CP interval ΘCP(s, n;α) ⊆ [0, 1] is an interval around µ̂ containing µ∗ with probability at least 1− α, i.e.,
Ps∼Binomial(n,µ∗)[µ ∗ ∈ ΘCP(s, n;α)] ≥ 1− α, (1)
where the probability is taken over s, α is a given confidence level, and ΘCP is a function of the Binomial random variable s = n · µ̂(z1:n). The CP interval is concretely defined by
ΘCP(s, n;α):= [ inf { θ ∣∣∣ F (n− s;n, 1− θ) ≥ α
2
} , sup { θ ∣∣∣ F (s;n, θ) ≥ α
2
}] ,
where F (s;n, θ) is the cumulative distribution function (CDF) of Binomial(n, θ). To compute the CP interval, we can use the following equivalent formula:
ΘCP(s, n;α) = [ Q (α
2 ; s, n− s+ 1
) , Q (
1− α 2
; s+ 1, n− s )] ,
where Q(p, a, b) is the pth quantile of a Beta distribution with parameters a, b (Hartley & Fitch, 1951; Brown et al., 2001). Our algorithm uses the CP interval to determine whether the accuracy of ĝt is nontrivial, i.e., > 1/2. In particular, the accuracy of ĝt is the mean of the Bernoulli random variable 1(ĝt(x) = y), where y is the ground truth indicating whether x is from S or T̄w,t. Then, our algorithm rejects if the CP interval does not contain 1/2, since this condition implies that the accuracy of ĝt does not equal 1/2 with high probability. We describe this step in detail below.
The key challenge is what data to use as the test dataset to estimate the accuracy of ĝt. The traditional strategy is to split the available data into two parts: one to train ĝt and a second held-out test set to estimate its accuracy (Lopez-Paz & Oquab, 2017; Kim et al., 2021). However, this approach reduces sample efficiency, which is problematic in our setting since we often want to w to be small.
To address this challenge, our algorithm exploits the conditional independence structure of classifier predictions. In particular, as described below, our algorithm uses each example xt to evaluate the accuracy of ĝt before using it to train ĝt. In the next section, we prove that this strategy maintains the independence of our estimate of the accuracy of ĝt (Lemma 1), and that as a consequence, our algorithm satisfies the desired false positive rate (for a single step t).

heading: 3.3 ALGORITHM DETAILS
text: Sequential detection algorithm. At each time step t, we observe a source sample xt ∼ S and a target sample x′t ∼ Tt. By using these current samples and previous samples, we detect covariate shifts by updating the source-target classifier in online learning. In particular, our algorithm consists of three steps: (1) source-target prediction, (2) covariate shift detection, and (3) online source-target classifier update. The following and Algorithm 1 include details.
Step 1. Source-target prediction. We predict source-target labels on the current samples xt and x′t using the current source-target classifier ĝt. In particular, we denote prediction on the source sample xt by ŷt, i.e., ŷt = ĝt(xt), and denote prediction on the target sample x′t by ŷ ′ t, i.e., ŷ ′ t = ĝt(x ′ t). These predictions and previous predictions are used in covariate shift detection in the following step.
Step 2. Calibrated covariate shift detection. Let Qw,t be a distribution over X × {0, 1}, where
Qw,t(x, y):= 1 2 · S(x) · 1(y = 0) + 1 2 · T̄w,t(x) · 1(y = 1).
Then, z = 1(ĝt(x) = y) is a Bernoulli random variable with distribution Bernoulli(µ∗w,t), where
µ∗w,t = P(x,y)∼Qw,t [ĝt(x) = y]
is the accuracy of ĝ at distinguishing whether an example x is from distribution S or T̄w,t. The unbiased empirical estimate of this accuracy is denoted by
µ̂w,t = 1
2w t∑ i=t−w+1 (1 (ŷi = yi) + 1 (ŷ ′ i = y ′ i)) .
In fact, 2wµ̂w,t is a Binomial random variable with Binomial(2w, µ∗w,t); thus, the accuracy µ ∗ w,t can be estimated by the Clopper-Pearson (CP) interval ΘCP(2wµ̂w,t, 2w;α) that includes the unknown parameter µ∗w,t with high probability, i.e.,
P [µ∗ ∈ ΘCP(2wµ̂w,t, 2w;α)] ≥ 1− α. This property can be used for checking the accuracy of ĝt might be 1/2. In particular, our algorithm returns “covariate shift” if 1/2 6∈ ΘCP(2wµ̂w,t, 2w;α), and “no covariate shift” otherwise, i.e.
f̂(Sw,t, Tw,t;α) = 1
( 1
2 6∈ ΘCP (2w · µ̂w,t, 2w;α)
) .
Here, the Clopper-Pearson interval calibrates the empirical accuracy µ̂w,t using the property of the Binomial distribution.
Step 3. Online source-target classifier update. Finally, we update a binary classifier ĝt using new training examples based on the source and target samples, i.e., (xt, 0) and (x′t, 1). In general, ĝt can be any model; we consider it to be a neural network, in which case we can update its parameters using stochastic gradient descent with respect to the cross entropy loss.

heading: 4 THEORETICAL GUARANTEES
text: In this section, we describe our finite sample bounds on the false positive and false negative rates of our covariate shift detector f̂ ; the key to have valid bounds is proving the independence on predictions ŷ1, . . . , ŷt (and ŷ′1, . . . , ŷ ′ t) to have a valid Clopper-Pearson interval, since they are seemingly dependent through the online learned classifier ĝt. First, our key result shows that our estimate of the accuracy of ĝt is valid—i.e., the predictions ŷi, . . . , ŷj are conditionally independent (see Appendix A.1 for a proof), thus the accuracy is the parameter of the Binomial distribution: Lemma 1. If xi, . . . , xj are independent for any i, j ∈ N where i < j, ŷi, . . . , ŷj are conditionally independent given ĝi, . . . , ĝj−1.
Our next result says that our algorithm ensures the desired bound α on the false positive rate (i.e., f̂ says “covariate shift” when there is no covariate shift). To this end, we exploit the following observation that any source-target classifier makes the expected accuracy of 1/2 if there is no covariate shift. Intuitively, if S = T̄w,t, source-target classification is impossible (Lopez-Paz & Oquab, 2017; Liu et al., 2020); we include this lemma for completeness (see Appendix A.2 for a proof): Lemma 2. If S = T̄w,t, we have µ∗w,t = 1/2 for any source-target classifier ĝt.
Since the expected accuracy of ĝt is 1/2 regardless of how we design and learn ĝt, and how many samples are used to learn ĝt, the Clopper-Pearson interval includes the true accuracy with high probability; thus the false positive rate of the proposed covariate shift detector f̂ is effectively controlled by the confidence level of the Clopper-Pearson interval, as follows (see Appendix A.3 for a proof):
Theorem 3 (Bound on false positive rate). If S = T̄w,t, then for any ĝt, we have
P(Sw,t,Tw,t)∼Sw×Tt−w+1:t
[ f̂(Sw,t, Tw,t;α) = 0 ] ≥ 1− α. (2)
Our next result provides a bound on the false negative rate; we first observe that the Clopper-Pearson interval is included in the interval by the Hoeffding’s bound. Intuitively, the Clopper-Pearson interval represents a lower and upper bound of the expected accuracy given an empirical accuracy tailored to a Bernoulli random variable; the Hoeffding’s bound can similarly bound the mean but in a more general setup. Thus, the Clopper-Pearson interval can be smaller (see Appendix A.4 for a proof).
Lemma 4. Let s ∼ Binomial(n, p) and F (s;n, p) is the CDF of Binomial(n, p); we have
s n − √ ln 2α 2n ≤ inf { θ ∣∣∣ F (n− s;n, 1− θ) ≥ α 2 } and sup { θ ∣∣∣ F (s;n, θ) ≥ α 2 } ≤ s n + √ ln 2α 2n .
Leveraging this, we have the following bound on false negative rate (see Appendix A.5 for a proof).
Theorem 5 (Bound on false negative rate). Assume ĝt achieves nontrivial accuracy, i.e., µ∗w,t ≥ 1/2 + , where ∈ (0, 1/2], is the accuracy at distinguishing S and T̄w,t. Let a(w,α) := 2w(1/2 +√
log(2/α)/4w) and b(w,α) := 2w(1/2− √ log(2/α)/4w). If S 6= T̄w,t and w−1−b √ w log(2/α)c ≥
0, then we have
P [ f̂(Sw,t, Tw,t;α)=1 ] ≥F ( 2w − ba(w,α) + 1c; 2w, 1 2 − ) +F ( db(w,α)− 1e; 2w, 1 ) . (3)
In the false negative bound, the first term is dominant and increases asw increases, which implies the sample size needs to be increased to have a powerful shift detector; the condition on w suggests that the bound is valid when w ≥ 201 given α = 0.01. We note that the assumption L(ĝt) := 1− µ∗ ≤ 1/2 − can be achieved under standard conditions. For instance, assume that the model family G of source-target classifiers has finite VC dimension (i.e., VC(G) < ∞), and that the optimal model g∗ ∈ G has nontrivial inaccuracy L(g∗) = 1/2− ξ for some ξ ∈ R>0; then, with probability at least 1− δ with respect to Sw,t and Tw,t and letting m = 2w, we have
L(ĝt) ≤ L(g∗) + 4 √
VC(G)(log(2m) + 1) m +
√ log(2/δ)
m
≤ 1 2 −
( ξ − 4 √ VC(G)(log(2m) + 1) m − √ log(2/δ) m ) ︸ ︷︷ ︸
=:
,
where the second term (which we have taken to be ) satisfies > 0 for sufficiently large m.

heading: 5 EXPERIMENTS
text: We evaluate the effectiveness of our algorithm at detecting both natural and synthetic covariate shifts of varying forms (e.g., gradual shifts and multiple shifts back and forth), showing that it significantly outperforms natural baselines.

heading: 5.1 EXPERIMENT SETUP
text: Baselines. We compare our algorithm to three baselines: two of them differ in the way they use the samples at each time step, the third uses Wald’s sequential likelihood test (Wald, 1945). For the first two baselines, while our approach uses all samples to construct the CP interval around the accuracy of the source-target classifier ĝt as well as to train ĝt, the baseline instead constructs a held-out test set using every Hth sample. Then, only this held-out test set is used to compute the CP interval, and only the remaining samples are used to train ĝt. In our experiments, we used values of H ∈ {2, 5}, denoted H2, H5, respectively. For Wald’s test, we consider the Bernoulli random variable with a probability p indicating whether the prediction of the source-target classifier is correct for the given
sample. The hypothesis test isH0 : p = 0.5 vs. H1 : p = 0.5+ , where = 0.2 in our experiments; we restart the test each time it makes a decision.
This baseline is essentially the online version of an existing classifier two-sample test (C2ST) (Kim et al., 2021; Lopez-Paz & Oquab, 2017), which splits the (fixed) training dataset into a training set to train ĝt and a held-out test set to estimate the accuracy of ĝt; thus, H controls the tradeoff between the number of examples in the training set and held-out test set.
Source-target classifier. We use a fully-connected neural network with a single hidden layer (with 128 hidden units) and with the ReLU activation functions as the source-target classifier ĝt. We use a binary cross-entropy loss for training in conjunction with an SGD optimizer with a learning rate of 0.01 (for natural shift experiments) and 0.001 (for synthetic shift experiments). Finally, since the inputs are ImageNet images (Russakovsky et al., 2015), we use a 2048-dimensional feature vector generated by first running a pretrained ResNet152 model (He et al., 2016) on the images, and then using these features vectors for the covariates of Sw,t and Tw,t.
Scenarios. We run each algorithm to test whether the target distribution in the given window is shifted with three different scenarios: multiple shift (“M-shift”), gradually increasing shift (“GIshift”), and gradually increasing-then-decreasing shift (“GID-shift”). Table 1 describes each scenario. For example, the multiple shift scenario proceeds as follows: (i) it starts with no covariate shift at the beginning; (ii) after observing 25% target samples (i.e., 250th samples for natural shift experiments and 2500th samples for synthetic shift experiments), covariate shift is applied to all target samples (with probability 1) by adding random perturbations for synthetic shift and by drawing samples from a target distribution for natural shift; (iii) after 50% of target samples, it reverts to no covariate shift; and (iv) finally after observing 75% target samples, the covariate shift is applied to the all target samples. Gradually increasing shift and gradually increasing-then-decreasing shift scenarios start with no covariate shift for the first 20% of target samples; then, covariate shift is applied with some probability 0 < p < 1 by gradually changing p over time.
Stream data generation. For each shift (i.e., natural shift and synthetic shift), we have a source dataset S and target datasets Tt, from which we randomly draw source and target samples for each time step t. In particular, we consider a batch of samples for computational efficiency, where we denote the batch size byB; we useB = 10 for our experiments. That is, we wait forB samples to be collected from the target distribution before checking for covariate shift and the updating the sourcetarget classifier; then, we begin collecting the next batch. Finally, we evaluate each approach using multiple random repetitions, which we denote by R (the value of R depends on each experiment).

heading: 5.2 NATURAL SHIFT
text: Dataset. First, we consider a natural shift on ImageNet. To construct such a shift, we consider the subset of dog classes; in particular, 120 of the 1000 of the ImageNet classes are of dogs (Khosla et al., 2011). Then, we randomly select half (i.e., 60) of these classes to be the source dataset, and the other half to be the target dataset; thus, the number of source and target images is 2997 each (after removing duplicated images). As a consequence, the source and target datasets correspond to different dog breeds, which is a kind of natural distribution shift.
Results. Figure 1 and Table 2 show results for the natural shift experiment with w = 10 and α = 1%. Figure 1 illustrates detection rates of the four algorithms with R = 100 repetitions (i.e., the fraction of repetitions that reported “covariate shift” at each step). Table 2a shows the number
of shifted samples required to reach at least 80% of covariate shift detection rate under the shift. Table 2b shows false positive rate (FPR) after 50, 100, 150, and 200 samples with R = 20000 repetitions.
Discussion. Figure 1 shows the detection rate of each algorithm as each scenario progresses. In multiple shift (Figure 1a) and gradually increasing-then-decreasing shift (Figure 1c), covariate shift disappears after a certain point, and all algorithms correctly detect this change. However, as shown in Table 2a, our approach always requires fewer samples to detect the shift. While H5 does not achieve 80% detection and H2 and Wald reach 80% only for multiple shift change scenario, our approach always detects covariate shift at a rate higher than 80%. Furthermore, for multiple shift, our algorithm requires fewer than half the number of samples compared to H2. In summary, our algorithm is significantly more sample efficient at detecting covariate shift compared to the baselines, most likely since it utilizes all samples for both training the source-target classifier and constructing the CP interval. For FPR, all algorithms always satisfy the FPR bound (i.e., FPR ≤ α).

heading: 5.3 SYNTHETIC SHIFT
text: Dataset. Next, we consider a synthetic shift on ImageNet. In particular, we split the original ImageNet validation set into equal sized source and target datasets. To construct the target dataset, we add synthetic perturbations on original images. We (separately) consider five perturbation types from (Hendrycks & Dietterich, 2019)—in particular, Contrast, Defocus Blur, Elastic Transform, Gaussian Blur, and Gaussian Noise, with five different severity levels.
Results. The experiment results are shown in Figure 2 and Table 3 for the experiments with the perturbation severity of 2, window size w = 10, and significance level α = 1%. Table 3a shows the number of target samples required by each algorithm to detect the first covariate shift in the detection rate of at least 80%. Table 3b shows the false positive rate (FPR) after 500, 1000, 1500 and 2000 samples for each of the three scenarios. Figure 2 shows the detection rates over multiple repetitions
for each of the three scenarios using the Gaussian noise perturbation. Results for other perturbation types and severities are shown in Appendix D.
Discussion. As can be seen, our approach outperforms the baselines in terms of sample efficiency for the covariate shift detection as was the case of the natural shift. Our algorithm requires about half as many samples before detecting covariate shift compared to the baselines. In terms of FPR, our approach always satisfies the FPR bound. Finally, Figure 2 shows the accuracy drop with the shifted samples. In particular, the red dotted line shows the accuracy of ResNet152 on the examples in the source and target samples of the given window; as can be seen, the accuracy decreases as the degree of the shift increases. Covariate shift detection can be successfully used to notify a user that an accuracy drop may have occurred.

heading: 6 CONCLUSION
text: We have proposed a novel covariate shift detection algorithm, which uses a classifier two-sample test to check whether the current test examples differ in distribution compared to the training examples. Our approach ensures sample efficiency by avoiding the need to split the dataset into a training set and a held-out test set, and instead using all the data to both train the source-target discriminator and to evaluate its accuracy. We prove that even with this optimization, our approach provides finite sample guarantees on the false positive rate at a desired level; we also prove bounds on the false negative rate under a mild conditions on the trained classifier. Finally, we empirically demonstrate that our proposed algorithm is significantly more sample efficient compared to a natural baseline that uses a held-out test set in terms of detecting both natural and synthetic shifts on ImageNet.
Reproducibility Statement. For our empirical results, we stated our algorithm in Algorithm 1, hyperparameters in Section 5.1, and dataset setups in Section 5.2 and 5.3. We have included the source code in the supplement for reproducing the experimental results. For our theory, we have included all proofs in Appendix A.

heading: A PROOFS

heading: A.1 PROOF OF LEMMA 1
text: Figure 3 represents the graphical model over random variables, where observed random variables are colored in gray. We prove the conditional independence using the d-separation (also called the Bayes ball algorithm) (Bishop, 2006), which is a set of rules that can determine the conditional dependency between two random variables based on the graphical model and observed random variables. In particular, ŷi+2 is conditionally independent to ŷk for all k ≤ i+ 1 since the path to ŷk is blocked by ĝi+1 (i.e., ĝi+1 is observed). Similarly, ŷi+2 is conditionally independent to ŷk for all k ≥ i+ 3. This proves the claim.

heading: A.2 PROOF OF LEMMA 2
text: For any source-target classifier ĝt, if S = T̂w,t, the following holds:
µ∗w,t = P(x,y)∼Qw,t [ĝt(x) = y]
= ∫ ∑ y∈{0,1} 1 (ĝt(x) = y)Qw,t(x, y)dx
= ∫ ∑ y∈{0,1} 1 (ĝt(x) = y) ( 1 2 · S(x) · 1(y = 0) + 1 2 · T̄w,t(x) · 1(y = 1) ) dx
= 1
2 ∫ ∑ y∈{0,1} 1 (ĝt(x) = y)S(x)1(y = 0) + ∑ y∈{0,1} 1 (ĝt(x) = y) T̄w,t(x)1(y = 1)dx
= 1
2
∫ 1 (ĝt(x) = 0)S(x) + 1 (ĝt(x) = 1) T̄w,t(x)dx
= 1
2
∫ 1 (ĝt(x) = 0)S(x) + 1 (ĝt(x) = 1)S(x)dx
= 1
2
∫ (1 (ĝt(x) = 0) + 1 (ĝt(x) = 1))S(x)dx
= 1
2
∫ S(x)dx
= 1
2 ,
where the sixth equality holds since S = T̂w,t; the claim follows.

heading: A.3 PROOF OF THEOREM 3
text: Denote the event that P(x,y)∼Qw,t [ĝt(x) = y] = 1/2 by E, and let sw,t = 2wµ̂w,t. Then, we have
PSw,t,Tw,t [ f̂(Sw,t, Tw,t;α) = 0 ] = PSw,t,Tw,t [( 1
2 ∈ ΘCP(sw,t, 2w;α)
) ∧ ( Px,y [ĝt(x) = y] = 1
2 )] = PSw,t,Tw,t [E]PSw,t,Tw,t [ 1
2 ∈ ΘCP(sw,t, 2w;α) ∣∣∣∣ E] = PSw,t,Tw,t [ 1
2 ∈ ΘCP(sw,t, 2w;α) ∣∣∣∣ E] ≥ 1− α,
where the first equality holds since S = T̂w,t and by Lemma 2, the third equality holds by Lemma 2, and the last inequality holds by the property of the Clopper-Pearson interval and Lemma 1.

heading: A.4 PROOF OF LEMMA 4
text: We use the tail bound of the binomial distribution using the Hoeffding’s inequality—i.e.
F (s;n, p) ≤ exp { −2n ( p− s
n
)2} .
For the upper bound of the upper Clopper-Pearson interval, we have
sup { θ ∣∣∣ F (s;n, θ) ≥ α
2
} ≤ sup { θ ∣∣∣∣ exp{−2n(θ − sn)2 } ≥ α 2 }
= sup θ ∣∣∣∣∣∣ sn − √ ln 2α 2n ≤ θ ≤ s n + √ ln 2α 2n  = s
n + √ ln 2α 2n . (4)
For the lower bound of the lower Clopper-Pearson interval, we have
inf { θ ∣∣∣ F (n− s;n, 1− θ) ≥ α
2
} ≥ inf { θ ∣∣∣∣ exp{−2n(θ − sn)2 } ≥ α 2 }
= inf θ ∣∣∣∣∣∣ sn − √ ln 2α 2n ≤ θ ≤ s n + √ ln 2α 2n  = s
n − √ ln 2α 2n . (5)
Finally, (4) and (5) imply the claim.

heading: A.5 PROOF OF THEOREM 5
text: Let the lower and upper bound of the Clopper-Pearson interval ΘCP be ΘCP and ΘCP, respectively. Recall that we denote the CDF of a binomial distribution binomial(n, p) by F (s;n, p). Then, we
have
PSw,t,Tw,t [ f̂(Sw,t, Tw,t;α) = 1 ] = PSw,t,Tw,t [ 1
2 /∈ ΘCP(2wµ∗w,t, 2w;α) ] = PSw,t,Tw,t [( µ∗w,t < 1
2 + ∨ µ∗w,t ≥
1 2 +
) ∧ ( 1
2 /∈ ΘCP(2wµ∗w,t, 2w;α) )] = PSw,t,Tw,t [( µ∗w,t ≥ 1
2 +
) ∧ ( 1
2 /∈ ΘCP(2wµ∗w,t, 2w;α)
)] (6)
= PSw,t,Tw,t [ µ∗w,t ≥ 1
2 +
] PSw,t,Tw,t [ 1
2 /∈ ΘCP(2wµ∗w,t, 2w;α) ∣∣∣∣ µ∗w,t ≥ 12 + ]
= PSw,t,Tw,t
[ 1
2 /∈ ΘCP(2wµ∗w,t, 2w;α) ∣∣∣∣ µ∗w,t ≥ 12 + ]
(7)
= PSw,t,Tw,t [ ΘCP(2wµ ∗ w,t, 2w;α) > 1
2 ∨ΘCP(2wµ∗w,t, 2w;α) <
1
2 ∣∣∣∣ µ∗w,t ≥ 12 + ]
= PSw,t,Tw,t [ ΘCP(2wµ ∗ w,t, 2w;α) > 1
2 ∣∣∣∣ µ∗w,t ≥ 12 + ]
+PSw,t,Tw,t [ ΘCP(2wµ ∗ w,t, 2w;α) < 1
2 ∣∣∣∣ µ∗w,t ≥ 12 + ] ,
where (6) and (7) hold due to PSw,t,Tw,t [µ ∗ w,t < 1/2 + ] = 0 and PSw,t,Tw,t [µ ∗ w,t ≥ 1/2 + ] = 1 from the assumption on ĝt and S 6= T , respectively. By Lemma 4, the first term is lower bounded as follows:
PSw,t,Tw,t [ ΘCP(2wµ ∗ w,t, 2w;α) > 1
2 ∣∣∣∣ µ∗w,t ≥ 12 + ]
≥ PSw,t,Tw,t µ̂w,t − √
ln 2α 4w > 1 2 ∣∣∣∣∣∣ µ∗w,t ≥ 12 + 
= PSw,t,Tw,t [ 2wµ̂w,t > a(w,α) ∣∣∣∣ µ∗w,t ≥ 12 + ]
= PSw,t,Tw,t [ 2wµ̂w,t ≥ ba(w,α) + 1c ∣∣∣∣ µ∗w,t ≥ 12 + ]
≥F ( 2w − ba(w,α) + 1c; 2w, 1 2 − ) , (8)
where the last inequality holds since the binomial parameter 12 − makes the CDF F smallest. Similarly, the second term is lower bounded as follows:
PSw,t,Tw,t [ ΘCP(2wµ ∗ w,t, 2w;α) < 1
2 ∣∣∣∣ µ∗w,t ≥ 12 + ]
≥ PSw,t,Tw,t µ̂w,t + √
ln 2α 4w < 1 2 ∣∣∣∣∣∣ µ∗w,t ≥ 12 + 
= PSw,t,Tw,t [ 2wµ̂w,t < b(w,α) ∣∣∣∣ µ∗w,t ≥ 12 + ]
= PSw,t,Tw,t [ 2wµ̂w,t ≤ db(w,α)− 1e ∣∣∣∣ µ∗w,t ≥ 12 + ]
≥F (db(w,α)− 1e; 2w, 1) , (9) where the last inequality holds since the binomial parameter µ∗w,t = 1 makes the CDF F smallest.
The claim follows by combining (8) and (9).

heading: B ADDITIONAL BASELINE
text: We include one additional baseline, adapted version of Deep Kernel MMD (Liu et al., 2020). This Deep Kernel (DK) requires training of the kernel parameters and the network for extracting features. We use half of samples for this training process and conduct a test using the rest of samples as H2. We run this algorithm for Natural shift as in Section 5.2.
Results. The experimental results with DK are shown in Figure 4, and Table 4. As described in Section 5.2, Figure 4 shows the detection rates of each algorithms, and Table 4 presents FPR at selected points. Our approach outperforms this adapted version of Deep kernel MMD approach. First, in terms of the false positive rate (FPR), DK violates the desired FPR bound, while ours satisfies the bound (Table 4b). Furthermore, Table 4a shows that our approach generally requires a smaller number of samples for detection. In the M-shift case, ours needs ten more samples. In the other two shifts, however, ours shows superior performance compared to DK. In the GI-shift, our approach requires 150 fewer samples, and in GID-shift, our approach uses 310 samples for the detection, while DK cannot achieve 80 % detection.

heading: C ADDITIONAL DISCUSSION

heading: C.1 MULTIPLE EPOCHS IN TRAINING
text: As shown in Algorithm 1, each example is used only once in updating the source-target classifier, baselines also follow this setting in all experiments. We consider this single epoch update anticipating that our algorithms being used in the online setting, where it is infeasible to take multiple passes
over the training data. However, without consideration of the online setting, each example can be used multiple times during training with the restriction that the example can be used only once in the CP interval, which can improve the performance. As this strategy is orthogonal to our approach, it can be applied to both ours and other baselines expecting the performance improvement.

heading: D ADDITIONAL EXPERIMENTAL RESULTS

heading: D.1 DETECTION RATE
text: This section shows the additional detection rate plots for the different perturbations, severities, and window sizes (w) including figures in the main paper.
D.1.1 M-SHIFT
Figure 5 - Figure 19 display the detection rate plot for M-shift scenario with different settings. These all different settings show the similar pattern with the figures in the main paper.

heading: D.1.2 GI-SHIFT
text: This section includes the plots for GI-shift scenario with different perturbation, window sizes (w), and fixed severity.

heading: D.1.3 GID-SHIFT
text: Similar to the previous two sections, this section includes figures for the GID-shift scenario with different perturbation with severity 2, and different window sizes (w).

heading: D.2 NUMBER OF SAMPLES FOR DETECTION
text: This section presents the required number of samples for detecting covariate shift over repetitions (Rate ≥ 80%) with different perturbations, severities, and window sizes (w).
D.2.1 M-SHIFT

heading: D.2.3 GID-SHIFT

heading: D.2.2 GI-SHIFT

Review summaries:
In traditional machine learning, there is a basic assumption that training and test sets are from the same distribution. When this assumption holds, we can expect low prediction error in the test set. However, in the real world, this assumption may be broken. For example, when the images change from daylight to night, the distribution changes. As a result, we cannot fully trust a classifier trained with daylight images. To address this issue and make predictions reliable, detecting such covariate shifts seems promising. Although we can directly use a two-sample testing method to complete this detection task, it cannot fit the online requirement. This paper presents a new sequential classifier two-sample test to address these dynamic covariate shifts. This paper proves that their optimization preserves the correctness—i.e., the proposed algorithm achieves a desired bound on the false positive rate. In the experiments, they also show that the proposed algorithm efficiently detects covariate shifts on ImageNet.

This paper proposes a new method to sequentially detect covariate shift which is the problem encountered when training and test covariates are not equally distributed. This methods builds on existing work that uses classifiers to distinguish between the two datasets and its accuracy as the statistic. The contribution of this paper is proposing a sequential version, where the classifier is trained in an online manner  and the accuracy computed on a sliding window (of training and test samples) is used for each test set observation.  A criterion to reject the equality of the distributions in the sliding window is given using on the well known Clopper-Pearson interval. A lower bound on the probability of correctly accepting the null hypothesis is derived from the properties of the aforementioned interval. A lower bound on the probability of correctly rejecting is derived, under the assumption that the classifier has at least some discriminating power (i.e., that it is non trivial).  

This paper proposes a new covariate shift detection method, which distinguishes whether training data and test data come from the same distribution. This method sequentially evaluates each example before taking a gradient step on that example, avoiding constructing a held-out test set. Experiments on ImageNet validate its effectiveness at detecting both natural and synthetic covariate shifts.

This draft proposes an online covariate shift detection algorithm based on the two-sample test with source and target data in a fixed sliding window. The proposed method is based on the accuracy of the source-target classifier to identify the covariate shift: if the source-target classifier cannot distinguish the source or target data, then the proposed method considers they are generated from the same distribution and vice versa. Experiments on the modified ImageNet dataset validate the effectiveness of the proposed method.