Sequential Covariate Shift Detection Using Classifier Two-Sample Tests
Authors: Sooyong Jang
Sangdon Park
Insup Lee
Osbert Bastani
Venue: ICLR 2022 Submitted (2022)

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.

Under review as a conference paper at ICLR 2022
SEQUENTIAL COVARIATE SHIFT DETECTION USING CLASSIFIER TWO-SAMPLE TESTS
Anonymous authors Paper under double-blind review
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 -ie., test whether the current test distribution of covariates equals the training distribution of covariates. Our algo- rithm builds on classifier texts, which train a discriminator to distinguish train and test covariates, and then use the accuracy of this discriminator as test statistic. A key challenge is that classifier tests assume given a fixed set of test covariates. 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 gradually shift over time. To address these challenges, our algorithm trains the discriminator online. Further- more, it evaluates test accuracy using each new covariate before taking gradient step; this strategy avoids constructing a held-out test set, which can reduce sam- ple efficiency. We prove that this optimization preserves the correctness-ic 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.
INTRODUCTION
A key challenge facing deep neural networks is their sensitivity 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, autonomous car using perception to identify obstacles needs to be robust to shifts such as changes in the weather and lighting conditions. We focus covariate shift (Shimodaira (000). where there is shift in the covariate distribution p(æ), and the conditional label distribution ply xr) remains unchanged. Covariate shift can reduce model performance (Sugiyama & Müller 2005), invalidate uncertainty
estimates (Oadia et al. 2019: Park et al.) 2020). and affect model selection (Sugiyama et al. 2007).
One strategy is devise an algorithm 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 al., 2012a Rabanser al. 2018 Liu 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 be the data used to train the model and the second sample be recent test data given 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 detection algorithm based on classifier tests (Lopez-Paz & Oquab, 2017] Cheng & Cloninger 2019 Kim et al., 2021), which use the accuracy of classifier trained to distinguish the two samples the test statistic. In particular, if the two samples are from the same distribution, then the accuracy should be 1 1/2; otherwise, should be > 1/2. Since the test statistic follows binomial distribution, we use the Slopper-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.

---

Under review as a conference paper at ICLR 2022
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 held-out test set estimate the test statistic, but constructing such set online would reduce sample efficiency.
Rather than train a classifier at each step, our proposed algorithm trains model online using stochas- tic gradient descent. Then, rather than construct a held-out test set, our algorithm evaluates the ac- curacy 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 pose 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, empirically demonstrate that our algorithm effectively detects shifts on ImageNet (Section5)).
two-sample test, and pro-
Sequential detection 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 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 number of interesting scenarios.
RELATED WORK
Covariate shift. There has been work on training models 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 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.) (007)). Another strategy is to first learn an invariant representation (Ganin et al. (2066). which is an embedding space where the source and target examples similar, and then train a model 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 s accuracy on a held-out test set (Kim et al.] [202T] Lopez-Paz & Oquab) 2017), or the differences in the classifier's '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 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 Chwialkowski et al. 2015) Jitkrittum et al. One strategy is to nonparametrie kernel 2012a); alternatively, the kernel can also be
embedding as the test statistic (Gretton et al. 201 2a
2016). The key design decision is the choice of kernel.
such as Gaussian radial basis functions (Gretton et al.
optimized to minimize the false negative rate of the resulting test (Gretton et al. 2012b). In addition,
2

---

Under review as a conference paper at ICLR 2022
recent work has shown how to first learn kernel function in the form of 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. (012a).
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) (Gonçalves Jr et al. 2014p. 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 usually very simple (e.g..a a Bernoulli distribution for the 0-1 loss), making it easy to test for drift. In contrast, our approach checks for drift in nigh-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 Lhéritier
& Cazals, 2018 2019, Manole & Ramdas (02T). 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.
SEQUENTIAL COVARIATE SHIFT DETECTION
3.1 PROBLEM FORMULATION
Let X' be the covariate space, S be the source distribution over X, and T1 (Te,, T..+1..... Tea)
be a sequence of target distributions over from time steps t to fz. On time step t. we consider samples ~ S and xy ~ Tr: in practice, S can be taken to be the uniform distribution over the training set. We let Sw.t = (#t-w+1, art denote the recent examples in time window of given size w E N.
and Tw,, = 22
Our goal is to detect covariate shift at any step l. More precisely, we want to determine whether * Twitt where Ta,, = Ek=t-w Ta/w,, i.e., whether the average target distributions over the previous steps is shifted compared to S. For fixed step t, this problem is two-sample hypothesis test (Lchmann & Romano 2006), where the null hypothesis is Ho S = Tw and the alternative
hypothesis is H1 : : + Tun.. That is, a two-le test f is designed to compute
f(Sw. Tw.)) so {)
if * Ta,,
otherwise.
Our goal is to design a two-sample test f for detecting covariate shift with this data stream. While in principle use any two-sample test, our goal is to design 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 a E R2 if S Tw,,, we want to ensure
P P Te,
Tw, Tw. - 2 a-
Ideally, we also want to provide finite sample bounds on the false negative rate; however, for clas- sifier tests, we can only do so under additional assumptions about the model family used to try and distinguish S and Tw,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 Te,,t- Then, our goal is to ensure that if S # Too we have
PS wiie [ Twit a) 1]
M(a,w)
for some function M (a, w) that depends the model family.
3.2
ALGORITHM OVERVIEW
Next, we describe our two two-sample test. We build on classifier two-sample test (C2ST) (Lopez-Paz Paz & Oquab] 2017 Kim et al. 2021). The idea is train classifier ÿ, to try and distinguish Su,,t
3

---

Under review as a conference paper at ICLR 2022
Algorithm Sequential Calibrated Classifier Two-Sample Test
1: Input: significance level window size
2: for each time step do
3: Draw examples X2 S Ti
4: Predict d, = (2,) and 1/22 = gx(xz)
Source-target prediction
5: Detect covariate shift if 0.5 & (2cp(2wfee.. 2w; a) (p) Calibrated covariate shift detection
6: Update 9. using (z,, 0) and 1x),
(D) Online source-target classifier update
7:
end for
from Tw. Intuitively, if and Tw,, are different distributions, then 9, should achieve nontrivial accuracy at distinguishing Sw,t from Tw.s (assuming the model family is sufficiently expressive). Alternatively, if S Tw.,, then J. necessarily achieves trivial expected accuracy of 1/2.
In particular, the accuracy of Jt 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 9t with high probability based on the accuracy of 9: a test set. More precisely, the CP interval is exact confidence interval around the empirical estimate of the mean a Bernoulli random variable. Letting 21,..., 2n ~ Bernoulli(a") be i.i.d. samples from a Bernouli distribution with true mean μ²' the (unnormalized) estimate of its mean n ((21:)) = - 2 has distribution Binomial n. ,²"). Then, the CP interval Ocr(s, a) S [0, 1] is interval around containing j¹ with probability at least 1 a, i.e.
P aa Binomial))
Ocr(s, n; ai) 2 a,
where the probability is taken over 8, a is a given confidence level, and Ocp is function of the Binomial random variable 8 = n (((1m)) The CP interval is concretely defined by
Ocp(s, a))) inf
F(n n; 0) @ 2 sup (0 F(s: n. 0) N 2 1
where F(s; n, f) is the cumulative distribution function (CDF) of Binomial 8). To compute the CP interval, we can use the following equivalent formula:
Ocp(s, n; az)
++1) (
2 1,n (onn-s) =)]
where Q(p, a, b) is pth quantile of a Beta distribution with parameters a, (Hartley & Fitch 1951 Brown et al., 2001). Our algorithm uses the CP interval to determine whether the accuracy of Ge is nontrivial, i.e., > I/2. In particular, the accuracy of ge is the mean of the Bernoulli random variable (g. (x) y). where y is the ground truth indicating whether x is from S or Tw Then, our algorithm rejects if the CP interval does not contain 1/2, since this condition implies that the accuracy of &r does not equal 1/2 with high probability. We describe this step detail below.
The key challenge is what data to use as the test dataset to estimate the accuracy of gr. The traditional strategy split the available data into two parts: one train gr and a second held-out test to estimate its accuracy (Lopez-Pare Paz& & Oquab] 2017 Kim et al. 2021). However, this approach reduces sample efficiency, which is problematic in our setting since we often want w to be small.
To address this challenge, our algorithm exploits the conditional independence structure of classifier predictions. particular, as described below, our algorithm uses each example 2, evaluate the accuracy of ÿ. before using it to train 9.. In the next section, we prove that this strategy maintains the independence of our estimate of the accuracy of 9. (Lemma [T. and that as consequence, our algorithm satisfies the desired false positive rate (for single step
3.3 ALGORITIM DETAILS
Sequential detection algorithm. At each time step f, we observe a source sample S and target sample ø/ ~ T. By using these current samples and previous samples, we detect covariate shifts by updating the souree-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 include details.
4

---

Under review as a conference paper at ICLR 2022
Step 1. Source-target prediction. We predict source-target labels on the current samples z and zy using the current source-target classifier 9c- In particular, we denote prediction on the source sample Ie by D., i.., 3. (x()),, and denote prediction the target sample z by 8% i.e., 02 Ir (z4)). 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 distribution over X' {0, 1), where
1 T (x)) 1(y = =1)
Qw, (2, y)- S(x) 1 = 0) +
2
Then, (1) - y/) is Bernoulli random variable with distribution Bernouli((Wwa) where Fw,, ((..))))... (x)
the accuracy of 9 at distinguishing whether an example æ from distribution S or Tw The unbiased empirical estimate of this accuracy is denoted by
1
Σ
(1 (fi - u1) + 1 1/)))
2w
In fact, 2wfuwee e Binomial random variable with Binomial(2us pw,,) :): thus, the accuracy Muc, can be estimated by the Clopper-Peanse Pearson (CP) interval 0cp(2wfm.cs 2w; a) that includes the unknown parameter Pw,t with high probability, i.e.,
IP Iu" E @cr(2upu.. 2w;; a)] 2 a.
This property can be used for checking the accuracy of ÿt might be 1/2. In particular, our algorithm returns "covariate shift" if 1/2 Ocp (2 2w; a), and "no covariate shift" otherwise, i.e.
f(S a) = {
& Ocr (2w Pn 2w; a))
Here, the Clopper-Pearson interval calibrates the empirical accuracy Pug using the property of the Binomial distribution.
Step 3. Online source-target classifier update. Finally, update binary classifier 9a using new training examples based on the source and target samples, i.e., (Iz, 0) and (z/, 1). In general, år can be any model; we consider it to be a neural network, which case we can update its parameters using stochastic gradient descent with respect to the cross entropy loss.
4 THEORETICAL GUARANTEES
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 predic- tions Ú1.-..,
. Dt (and V/..... i to have valid Clopper-Pearson interval, since they seemingly dependent through the online learned classifier 9t- First, our key result shows that our estimate of the accuracy of 9: is valid-i.e., the predictions Di ii..... Új are conditionally independent (see Appendix A. for proof), thus the accuracy is the parameter of the Binomial distribution:
Lemma 1. If IT j are independent for any i.j where < j. ii...., Uj are conditionally independent given .i....99j-1
Our next result says that our algorithm ensures the desired bound a on the false positive rate (i.c., says "covariate shift" when there is no covariate shift). To this end, we exploit the following obser- vation that any source-target classifier makes the expected accuracy of 1/2 if there no covariate shift. Intuitively, if S = Tw.t, source-targe classification is impossible (Lopez-Paz & Oquab 2017 Liu et al. 2020); we include this lemma for completeness (see Appendix for proof):
Lemma 2. S Tw,,o we have y 1/2 for any source-target classifier 9:-
Since the expected accuracy of gr is 1/2 regardless of how we design and learn ğr. and how many samples are used to learn ÿt. the Poopeer-Paason interval includes the true accuracy with high prob- ability: thus the false positive rate of the proposed covariate shift detector is effectively controlled by the confidence level of the Clopper- Pearson interval, as follows (see Appendix A.3 for a proof):
5

---

Under review as a conference paper at ICLR 2022
Theorem (Bound on false positive rate). IfS Tw.b then for any gv. have
21-a.
Our next result provides bound the false negative rate; first observe that the (lopper-Pearson interval is included in the interval by the Hoeffding'ss ' bound. Intuitively, the Clopper-Pearson interval represents a lower and upper bound of the expected accuracy given empirical accuracy tailored to 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.A for a proof).
Lemma 4. Let Binomial( p) and F(s;n, P) is the CDF of Binomial (n,)); p); ) we have
In 2 2n S inf {o F(n s; n, 0) N a and sup {o F(s:n, 0) 2 n
In 2
n
2
2n
Leveraging this, we have the following bound false negative rate (see Appendix A.5 for a proof).
Theorem 5 (Bound on false negative rate). Assume År achieves nontrivial accuracy, i.e., M 2
1/2 + E, where E (0, 1/2), the accuracy at distinguishing S and Tw, Let alw, a) 2w (2/2 1/2
/ (1og(2/a//4w) and b(w, ex) == 2w(1/2 /22
(log(2/a\/ww) 200t/2-//0///////
IfS + Twg and w LV (2)
O, then we have
P a(Sm Twis a) = aw):a=
2 F
( 2w La(w, at) + +1:
1 2 e) + (T 11: (3)
In the false negative bound, the first term is dominant and increases as w increases, which implies the sample size needs be increased have powerful shift detector; the condition w suggests that
the bound is valid when w 2 201 given a 0.01. We note that the assumption L( == 1 μ S 1/2 e can be achieved under standard conditions. For instance, assume that the model family g of source-targe' classifiers has finite VC dimension (i.e., VC(g) < oo), and that the optimal model
g" has nontrivial inaccuracy L(g") 1/2 for some & R>o then, with probability least
1 - 8 with respect to S,,,t and T T...t and letting = 2w, we have
(log)()) + 1)
log (2/5)
I(O:) - L(g") + +4V
1 2
(log)()o((2m) +
(og(2/0) m
4
m
where the second term (which we have taken be e) satisfies > 0 for sufficiently large m.
EXPERIMENTS
We evaluate the effectiveness of our algorithm at detecting both natural and synthetic covariate shifts of varying forms (c.g., gradual shifts and multiple shifts back and forth), showing that it significantly outperforms natural baselines.
5.1 EXPERIMENT SETUP
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 9, well to train 9t. the baseline instead constructs a held-out test set using every Hh sample. Then, only this held-out test set used to compute the CP interval, and only the remaining samples are used to train ÿ. In experiments, denoted H2, H5, respectively. For Wald's s test, we consider the Bermoulli random variable with a probability p indicating whether the prediction of the source-target classifier is correct for the given
used values of H E (2,5),

---

Under review as a conference paper at ICLR 2022
Table 1: Scenario description for experiments. (a) "M-shift" is Multiple shift, (b) "GI-shift" is shift.
gradually increasing shift, and (c) "GID-shift" is gradually
(b) GI-shift
(c) GID-shift
(a) M-shift
Start position
Description
Prob.
Start position
Description
Prob.
Start position
Description
Proh.
25%
0%
No shift
Shift
0.0
1.0
20%
0%
No shift
Shift
0.0
0.2
20%
No shift
Shift
0.0
40%
Shift
0.4
40%
Shift
0.8
75%
50%
No shift
Shift
0.0
1.0
60%
Shift
0.6
80%
Shift
0.8
80%
No shift
0.0
sample. The hypothesis test is Ho 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 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 trai Or and a held-out test set to estimate the accuracy of 9:; thus, H controls the tradeoff between the number of examples in the training set and held-out test set.
Source-target classifier. We use fully-connected neural network with single hidden layer (with 128 hidden units) and with the ReI.U activation functions as the source-target classifier 9t- We use binary cross-entropy loss for training in conjunction with an SGD optimizer with 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 lin8--dimenioonal feature vector generated by first running pretrained R5 model (He et al., 2016) on the images, and then using these features vectors for the covariates of Swe 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 ("GI- shift"), and gradually serreasing-thenddereee nario. 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 tar- get 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 murrasing-then-deereass scenarios start with no covariate shift for the first 20% of target samples; then, covariate shift is applied with some probability 0 < < 1 by gradually changing over time.
shift ("GIID-shift"). Table [ describes each sce-
shift
Stream data generation. For each shift (i.e., natural shift and synthetic shift), we have a source dataset S and target datasets Te, from which we randomly draw source and target samples for each time step In particular, we consider batch of samples for computational efficiency, where we denote the batch size by B; we use B = 10 for our experiments. That is, we wait for B samples to be collected from the target distribution before checking for covariate shift and the updating the source- target 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).
5.2 NATURAL SHIFT
Dataset. First, we consider 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, 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 consequence, the source and target datasets correspond to different dog breeds, which is a kind of natural distribution shift.
Results. Figure I and Table 2 show results for the natural shift experiment with w 10 and a = 1%. Figure [ illustrates detection rates of the four algorithms with = 100 repetitions (i.c., the fraction of repetitions that reported "covariate shift" at each step). Table shows the number
7

---

Under review as a conference paper at ICLR 2022
180
300
130
Detoction tato over rexntom
Sottec extreio comppoeeett (50 Dodoction fott over reselbin
simbl azo 152)
St KATEEE manta (50
Whid
Suumber of seemoles
Numthe of surrges
Nurriber sumpp
(a) M-shift
(b) GI-shift
(c)
GID-shift
Figure 1: Detection rate for natural shift with R 100, 10, = 1%. The black dashed line indicates shifted sample ratio, i.e., the degree (or probability) of covariate shift.
Table 2: Natural shift results with (a) w = 10, a = 1%, and = 100, and (b) R 20000 In (a), bold the best algorithm. In (b), bold values that exceed the desired 1%.
(a) Number of samples for detection (2 80%)
(b) FPR (%) at selected time
Scenario Algorithm Natural shift
Scenario Algorithm
50 100
150 200
Ours
190
Ours
0.27 0.53 0.73 0,77
M-shilt
H2
720
M-shift
H2
0,29 0.28 0.26 0.33
115
0.34 0.52 0.51 0.56
Wald
640
Wald
0.60 0.47 0.27 0.27
Ours
620
Ours
0.21 0.60 0.76 0.83
GI-shift
GI-shift
H5
H5
0.32
0.43 0.50 0,85
Wald
Wald
0.78 0.57 0.29 0.22
Ours
310
Ours
0,30 0.53 0.70 0.95
GID-shift
GID-shift
H5
H5
0.36
0.56 0.53 0.81
Wald
Wald
0.77 0.58 0.34 0.23
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 I shows the detection rate of each algorithm as each scenario progresses. In multiple shift (Figure lab and gradually increasing taoegg-the--dee then-decreasing shift (Figure Ic], covariate shift disappears after 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 rate higher than 80%. Furthermore, for multiple shift, our algorithm requires fewer than half the number of samples compared to H2. In summary, our al- gorithm 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 S a).
5.3 SYNTHETIC SHIFT
Dataset. Next, we consider synthetic shift on ImageNet. In particular, we split the original Im- ageNet 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.
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 a = 1%. Table shows the number of target samples required by each algorithm 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 shows the detection rates multiple repetitions
Results.
8

---

Under review as a conference paper at ICLR 2022
180
Dotoction tato over resestim 1h0
Shitbe /ememerr Dodoction fott over reseniim Phi
stnfid samola cpo Accursce
Whid
bummter of soumoles
Numther of earrggee
Nurriber sarppte
(a) M-shift
(b) GI-shift
(c) GID-shift
Figure 2: Detection rate for synthetic shifts with Gaussian noise perturbation, Severity 2,
100, 10, a 1%. The black dashed line indicates shifted sample ratio, i.e., the degree (or probability) of covariate shift. The dotted line shows the accuracy ResNet152 on the source and target samples in the given window.
Table 3: Synthetic shift results with (a) Severity 2, w = 10. = 1% and R 100, and (b) R 20000. In (a), we bold the best algorithm. In (b), we bold values that exceed the desired 1%.
(a) Number samples for detection
(b) FPR (%) at selected time
Scenario
Alg.
Contrast
Defocus Blur
Elastic Transform
Gaussian
Gaussian Noise
Scenario
Alg.
500
1000
1500
2000
Blur
Ours
0.73
1.00
0.90
1.00
Ours
230
200
220
210
180
H2
0.40
0.46
0.46
0.50
M-shilt
H2
470
450
450
490
350
M-shift
H5
0.80
0.73
0.84
0.69
410
410
410
460
310
Wald
0.07
0.11
0.04
0.01
Wold
Ours
0.86
0.89
0.92
0.85
Ours
2100
2060
2090
2070
2080
H2
0.62
0.54
0.60
0.50
Gl-shint
H2
4050
3690
4050
4010
3670
G1-shint
H5
0.74
0.71
0.77
0.73
4110
Wald
0.10
0.13
0.07
0.03
Wald
Ours
0.87
0.95
0.92
0.89
Ours
880
560
900
720
610
GID shin
GID-shift
H2
2030
2010
2050
2010
2010
H5
0.73
0.75
0.85
0.89
2060
Wald
0.09
0.08
0.04
0.02
Wald
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 shows the accuracy drop with the shifted samples. 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.
CONCLUSION
We have proposed a novel covariate shift detection algorithm, which uses a classifier two-sample test 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 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, sample guarantees on the false positive rate at a desired level; we also prove bounds on the false negative rate under mild conditions on the trained classifier. Finally, empirically demonstrate that our proposed algorithm is significantly more sample efficient compared to a natural baseline that uses held-out test set in terms of detecting both natural and synthetic shifts ImageNet.
approach provides finite

---

Under review as a conference paper at ICLR 2022
Reproducibility Statement. For our empirical results, 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 theory, have included all proofs Appendix A
REFERENCES
Akshay Balsubramani and Aaditya Ramdas. Sequential nonparametric testing with the law of the 2015.
iterated logarithm. arXiv preprint arXiv:
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in neural information processing systems, pp. 137-144, 2007.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning for differing training and test distributions. In Proceedings of the 24th international conference Machine learning, pp. 81-88. ACM, 2007.
Christopher M Bishop. Puttern recognition and machine learning- Springer, 2006.
Lawrence D Brown, T Tony Cai, and Anirban DasGupta. Interval estimation for a binomial propor- tion. Statistical science, pp. 101-117, 2001.
Xiuyuan Cheng and Alexander Cloninger. Classification logit two-sample testing by neural net- works. arXiv preprint arXiv: 11298, 2019.
Kacper Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast tao-sample testing with analytic representations of probability measures. arXiv preprint arXiv:1506.0472). 2015.
Charles J Clopper and Egon S Pearson. The use of confidence or fiducial limits illustrated in the case the binomial. Biometrika, 26(4):404-413, 1934.
Jerome Friedman. On multivariate goodness-of-fit and two-sample testing. Technical report, Cite- seer, 2004.
João Gama, Indrè Žliobaité, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. A survey on concept drift adaptation. ACM computing surveys (CSUR), 46(4):1-37, 2014.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Francois Laviolette, Mario Marchand, and Victor Lempitsky. Domaan-adversarial training of neural net- works. Journal of Machine Learning Research, 17(59):1-35 2016. URLhttp:: /jmrr momll.orrg orrg
papers/v11// 7/15-111551 120155---9.. 11t.:1111222.mm11 html
Paulo M Gonçalves Jr, Silas GT de Carvalho Santos, Roberto SM Barros, and Davi CL Vieira. A comparative study on concept drift detectors. Expert Systems with Applications, 41(18):8144- 8156, 2014.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf. and Alexander Smola. kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012a.
Arthur Gretton, Dino Sejdinovic, Heiko Strathmann, Sivaraman Balakrishnan, Massimiliano Pontil, Kenji Fukumizu, and Bharath K Sriperumbudur. Optimal kernel choice for large-scale two-sample tests. In Advances in neural information processing systems, pp. -205-1213 Citeseer, 2012b.
HO Hartley and ER Fitch. A chart for the incomplete beta-function and the cumulative binomial distribution. Biometrika, 38(344):433-42,, 1951.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common ruptions and perturbations. Proceedings of the International Conference on Learning Represen- fations, 2019.
10

---

Under review as a conference paper at ICLR 2022
Wittawat Jitkrittum, Zoltán Szabó, Kacper Chwialkowski, and Arthur Gretton. Interpretable distri- bution features with maximum testing power. arXiv preprint 1605v: 2016.
Aditya Khosla, Nityananda Jayadevaprakash, Bangpeng Yao, and Li Fei-Fei. Novel dataset for fine- grained image categorization. In First Workshop on Fine-Grained Visual Categorization, IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, CO, June 2011.
Ilmun Kim, Aaditya Ramdas, Aarti Singh, and Larry Wasserman. Classification accuracy proxy for two-sample testing. The Annals of Statisties, 49(1):411 434, 2021.
Erich L Lehmann and Joseph P Romano. Testing statistical hypotheses. Springer Science & Business Media, 2006.
Alix Lhéritier and Frédéric Cazals. A sequential non-parametric multivariate two-sample test. IEEE Transactions on Information Theory, 64(5):3311-3370, 2018.
Alix Lhéritier and Frederic Cazals. Low-complexity nonparametric bayesian online prediction with universal guarantees. Advances Neurul Information Processing Systems, 12:14581-14599 2019.
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Dougal Sutherland. Learn- ing deep kernels for non- parammeeitiic two-sample tests. In International Conference on Machine Learming. pp. 6316-6320 PMLR, 2020.
David Lopez-Paz and Maxime Oquab. Revisiting classifier two-sample tests. In International Con- ference on Learning Representations, 2017.
Tudor Manole and Aaditya Ramdas. Sequential estimation of convex divergences using reverse submartingales and exchangeable filtrations. arXiv preprint arXiv:2103.09267 2021.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Scbastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. arXiv preprint arXiv: 1906.05000 2019.
Sangdon Park, Osbert Bastani, James Weimer, and Insup Lee, Calibrated prediction with covariate shift via unsupervised domain adaptation. In International Conference on Artificial Intelligence and Statistics, 22-99222.. PMLR, 2020.
Stephan Rabanser, Stephan Günnemann, and Zachary C Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. arXiv preprint arXiv: 11953, 2018
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of compuler vision, 115(3)2111-552 2015.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Masashi Sugiyama and Klaus-Robert Müller. Input-dependent estimation of generalization error under covariate shift. 2005.
Masashi Sugiyama, Mauhias Krauledat, and Klaus-Robert Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(5), 2007.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003-4
Abraham Wald. Sequential tests of statistical hypotheses. The annals of mathematical statistics, 16 17-1177 1945.
11

---

Under review as a conference paper at ICLR 2022
A PROOFS
A.1 PROOF OF LEMMA [
X++1
F++2
9
9++1
9:+2
D++1
i++2
i
Figure 3: The dependency structure of random variables.
Figure 3 represents the graphical model over random variables, where observed random variables 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, # is conditionally independent to for all & < i i 1 since the path to in blocked by 9i+1 (i.e., 9i+1 observed). Similarly, 91+2 is conditionally independent ÿb. for all k 2 i + 3. This proves the claim.
A.2 PROOF OF LEMMA 2
For any source-target classifier 9r, if S = Fw..s the following holds:
pu, IP (a.N)~ [āc(x) yl
Σ (g:(x) y) Que, (I,
(E(1.
S(x) 1 (delz) = y) (1 ((xx) 1(y 0) 1
Σ
(w))(x) 1(y -w)(())1(y=11) da
2
(e(0.1)
/
Σ ((((z) = ())(())
= 0) Σ (āe(a) = y) (w,e(x) = 1)dz
2
1E(0.1)
SE
1
1 (0((z) 5(x) + 1 1) Tw. (r)dz
2
1
/ (9.(3)) 0))()) 1 (g 1) (
2
1
(1 (1)(()) 0) + (0)(x) 1)) S(x)da
2
1
/
S(x)da
2
2'
where the sixth equality holds since S = = the claim follows.
12

---

Under review as a conference paper at ICLR 2022
A.3 PROOF OF THEOREM 3
Denote the event that (x.))~u.1 [0((x) = 5) = 1/2 by and let sw.e 21ofhree. Then, we have
P Sw.t Twit (usss =
(6
vl - -1 PN. l0a(x))
Ocp(Sw.t 200; 200;
[
P PmmatTar
[ Pm. Timi
E @cp(sw, 2wx; xx)
E
2
Sm
E Ocp(swe
2wu; ae)
E
2 O,
where the first equality holds since S = Twne and by Lemma 2 the third equality holds by Lemma and the last inequality holds by the property of the Clopper-Pearsee Pearson interval and Lemmal
A.4 PROOF OF LEMMA 4
We use the tail bound of the binomial distribution using the Hoeffding's inequality i.e.
p(s; S exp { {-21
(p- 8) m
For the upper bound of the upper Clopper- Pearsoo interval, we have
sop 0( 0) 2 a < sup 0
exp
2n
0
8
2
2
a
n
2
In
8
In
sup
<
<
+
2n
2n
8
In
+
(4)
2m
For the lower bound of the lower Clopper- interval, we have
inf ( F(n F(n- s;n, 0) z
inf
0
exp
2m
0
2 ]
5)2) 2)
n
In
In 2
inf
< <
+ |
n
2n
n
2n
In
2
(5)
n
2n
Finally, and 55) imply the claim.
A.5 PROOF OF THEOREM 5
Let the lower and upper bound of the Clopper-Peansee interval Ocp be Ocp and θer. respectively. Recall that denote the CDF of binomial distribution binomial(n,,) p) by F(s,n,p). Then,
13

---

Under review as a conference paper at ICLR 2022
have
P Te.
[SS a)) (00)-11] =1]
Ocp(2wHiuues 2w;a)
1
1
( x Ocp 02 200; 200;
+
Murt
2
1
1 2
Ocp (2ww... 2w0; a))
,u,t
+
$
(6)
2
1
1
1
Tu.
P
$ Ocr(2wp 200
Nu,t
+
2
2
Ocp (2u(2uneees aw;a)
Mumt 2 +e
2
1
@er(2 2w;; a)
#CP(2uru' 2w; a)
Ru,t 2 +e
Pw.
@cpl2wp 2w;
Munt +
1
Tw.e
Gcp(2ur 2w; a))
Muot 2 +
where (6) and (7) hold due to IP sm.,, Thh I 1/2 0 and IP Pm Ionn 2 1/2 + c] from the assumption on år and S # T, respectively.
By Lemma 4 the first term is lower bounded follows:
1
P PSAATTTr. Twxt
Ocp Bcw(2upt 2w; (i)
Must
2
+
2
2
In
2
1
IP Tume
Bwst
V
Mun,
4w
2
1
P
2withor > a(w,a)
2
+
2
Pu
2wihhe, 2 |a(w, a)) +1]
Mune 2 +
1 >F 2w La(w, () + 11; 2w0,
2 =
(8)
where the last inequality holds since the binomial parameter Similarly, the second term is lower bounded as follows:
makes the CDF F smallest.
Sws.,,Tus Tuxt
Ocp(2wpi 2w;; a) <
pww
+e
In 2
1
P Smite
pu, +
Hwwtt
2
+
4w
2
1
P PS
2wpuwoi < b(w,a)
+
E
2
1
P
2wpw S [Tbbb,,, a) -1]
2
F (Ib(w,a) - 1]: 1).
(9)
where the last inequality holds since the binomial parameter pi, makes the CDF smallest. The claim follows by combining 8 and
14

---

Under review as a conference paper at ICLR 2022
180
300
Soituc extrpio netn Dodoction fott over reselbin Ph)
130
Detoction tato over rexettmm
Wiidd 3
simblo ozo
EK
Suumber of neemoles
Numbhr of surrpee
Nurriber sumppe
(a) M-shift
(b) GI-shift
(c) GID-shift
Figure 4: Detection rate for natural shift with R 100, w 10, a 1%. Deep Kernel result is included. The black dashed line indicates shifted sample ratio, i.e. the degree (or probability) of covariate shift.
Table 4: Natural shift results with (a) w 10, 1%, and R = 100, and (b) R= 20000 In (a), we bold the best algorithm. In (b), we bold values that exceed the desired 1%.
(a) Number of samples for detection (2 80%)
(b) FPR (%) at selected time
Scenario Algorithu Natural shift
Scenario Algorithm
100 150 200
Ours
190
0.27 0.53 0.73 0.77
H2
720
H2
0,29
0.28 0.26 0.33
M
Mishin
0.56
Wald
640
Wald
0.60
0.47 0.27 0.27
2.31 2.16 2.54
Ours
620
Ours
0.21 0.60 0.76 0.83
H2
0.21 0.25 0.29 0.36
GI-shitt
H5
Gl-shint
H5
0,32 0.43 0.50 0.85
0.29 0.22
DK
770
DK
2.11 2.67 2.22 3.29
Ours
310
Ours
0,30 0.53 0.70 0.95
H2
H2
0.18
0.21 0.28 0.41
GID GiD-shift
GID-shin
Wald
Wald
0.77 0.58 0.34 0.23
3.42
B ADDITIONAL BASELINE
We include one additional bascline, 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 test using the rest of samples 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 As described in Section 5.2 Figure g shows the detection rates of each algorithms, and Table 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 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.
C ADDITIONAL DISCUSSION
C.I MULTIPLE EPOCHS IN TRAINING
As shown in Algorithm I each example is used only once in updating the souree-target classifier, baselines also follow this setting in all experiments. We consider this single epoch update anticipat- ing that our algorithms being used in the online setting, where is infeasible take multiple passes
15

---

Under review as a conference paper at ICLR 2022
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, can be applied to both ours and other baselines expecting the performance improvement.
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 DETECTION RATE
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 P Figure[T9dissp 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.
16

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
(%%)
Detertionn uver repalition
112
112
'15
60
60
40
40
60
40
20
20
20
Shifted
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samble ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H22
H2
50
30
H5
80
Shifted semole
2000
8000
2000
4000
Number of samples
Number of sampies
(c) Severity 3
(d) Severity =
Detaction Rate over repetition (%)
Ours
(%)
H2
HS
60
40
20
20
Shifted
2000
1000
8000
8000
10000
Number of
(e) Severity
Figure 5: Contrast with R 100, = 10, 1%.
17

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%)
Detertionn uver repalition
112
112
115
60
60
40
40
60
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of sampies
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H2
H2
50
80
80
Shifted semole
2000
8000
2000
4000
Number of samples
Number of sampies
(c) Severity =
(d) Severity =4
Detaction Rate over repetition (%)
Ours
(%)
H2
60
40
20
20
Shifted
2000
1000
8000
8000
10000
Number of
(e) Severity
Figure 6: Defocus blur with R 100, 10, 1%.
18

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%)
Detertionn uver repelition
112
112
115
H9
90
60
60
40
40
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of sampies
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H22
H2
50
80
80
Shifted semole
2000
8000
2000
4000
Number of samples
Number of sampies
(c) Severity =
(d) Severity =
Detaction Rate over repetition (%)
Ours
(%)
H2
60
40
20
Shifted sample
20
2000
1000
8000
8000
10000
Number of
(e) Severity
Figure 7: Elastic transform with R = 100, 10, 1%.
19

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
(%%
Detertionn uver repalition
112
112
115
68
60
40
40
60
40
20
20
20
Shifted
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Ours
100
Shifted samble ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H22
H2
50
30
80
Shifted semole
2000
8000
2000
4000
Number of samples
Number of sampies
(c) Severity =
(d) Severity =4
Detaction Rate over repetition (%)
Ours
(%)
H2
HS
60
40
20
20
Shifted
2000
1000
8000
8000
10000
Number of
(e) Severity
Figure 8: Gaussian blur with R = 100, 10, 1%.
20

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%
Detertionn uver repalition
112
112
115
60
60
40
40
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted semole (%6
Duluction Rale Uver repeltiion
H22
H2
50
80
80
2000
8000
Number of samples
Number of samples (d) Severity =4
(c) Severity 3
Detaction Rate over repetition (%)
Ours
(%)
H2
2200 HS
60
40
20
Shifted sample
20
2000
1000
8000
8000
10000
Number of
(e) Severity
Figure 9: Gaussian noise with R 100, w 10, 1%.
21

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%)
Detertionn uvet repelition
112
112
60
60
40
40
60
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H2
H2
50
80
80
Shifted semole
2000
8000
4000
Number of samples
Number of samples (d) Severity =
(c) Severity =
Detaction Rate over repetition (%)
Ours
(%6
H2
60
40
20
20
Shifted
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 10: Contrast with R = 100, = 20, 1%.
22

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
(%%
Detertionn uvet repelition
112
112
60
60
40
40
60
40
20
20
Shifted
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H2
H2
50
30
80
Shifted semole
2000
8000
4000
Number of samples
Number of samples (d) Severity =
(c) Severity =
Detaction Rate over repetition (%)
Ours
(%6
H2
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 11: Defocus blur with R = 100, 20, 1%.
23

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (9%)
Detertionn uvet repelition
112
112
H15
90
60
60
40
40
60
40
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H2
H2
50
800
80
Shifted semole
2000
8000
4000
Number of samples
Number of sampies (d) Severity =
(c) Severity 3
Detaction Rate over repetition (%)
Ours
(%6
H2
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 12: Elastic transform with R 100, 20, 1%.
24

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%
Detertionn uvet repelition
112
112
115
60
60
40
40
60
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H2
H2
50
80
80
Shifted semole
2000
8000
4000
Number of samples
Number of samples
(c) Severity =
(d) Severity =4
Detaction Rate over repetition (%)
Ours
(%)
H2
60
40
20
20
Shifted
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 13: Gaussian blur with R 100, w 20, 1%.
25

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%
Detertionn uvet repelition
112
112
60
60
40
40
60
40
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted semole (%6
Duluction Rale Uver repeltiion
H2
H2
50
80
80
2000
8000
4000
Number of samples
Number of samples (d) Severity =
(c) Severity 3
Detaction Rate over repetition (%)
Ours
(%)
H2
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 14: Gaussian noise with R = 100, w 20, 1%.
26

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
(%%
Detertionn uvet repelition
112
112
115
90
60
60
40
40
60
40
20
20
Shifted
Mrdbous
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samble ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted semole (%6
Duluction Rale Uver repeltioo
H2
H2
50
80
80
2000
8000
Number of samples
Number of samples (d) Severity =
(c) Severity =
Detaction Rate over repetition (%)
Ours
(%)
H2
Hy
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of (e) Severity
Figure 15: Contrast with R = 100, 50, 1%.
27

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
(%%
Detertionn uvet repelition
112
112
115
60
60
40
40
60
40
20
20
Shifted
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samole ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltioon
H22
H2
50
80
80
Shifted semole
2000
8000
4000
Number of samples
Number of samples (d) Severity =
(c) Severity =
Detaction Rate over repetition (%)
Ours
(%6
H2
Hy
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 16: Defocus blur with R = 100, 50, 1%.
28

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%)
Detertionn uvet repelition
112
112
115
90
60
60
40
40
60
40
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of sampies
(a) Severity
(b) Severity
100
Ours
100
Shifted samole ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted semole (%6
Duluction Rale Uver repeltiio
H2
H2
50
80
80
2000
Number of samples
Number of samples (d) Severity =
(c) Severity 3
Detaction Rate over repetition (%)
Ours
(%)
H2
H5
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 17: Elastic transform with R 100, 50, 1%.
29

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%
Detertion uvet repelition
112
112
115
60
60
40
40
60
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity
100
Curs
100
Shifted samble ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted semole (%6
Duluction Rale Uver repeltioon
H22
H2
50
80
80
2000
8000
4000
Number of samples
Number of samples (d) Severity =
(c) Severity 3
Detaction Rate over repetition (%)
Ours
(%)
H2
Hy
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of
(e) Severity
Figure 18: Gaussian blur with R 100, w 50, 1%.
30

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%%
Detertionn uvet repelition
112
112
115
60
60
40
40
60
40
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Severity
(b) Severity =
100
Curs
100
Shifted samole ratio Accuracy (%)
Detaction Rake over repeiition (9%)
100
Ours
100
(%6
Duluction Rale Uver repeltiion
H22
H2
50
80
80
Shifted semole
2000
8000
Number of samples
Number of samples (d) Severity =
(c) Severity =
Detaction Rate over repetition (%)
Ours
(%)
H2
Hy
60
40
20
Shifted sample
20
2000
1000
8000
8000
10000
Number of
(e) Severity
Figure 19: Gaussian noise with R = 100, w 50, 1%.
31

---

Under review as a conference paper at ICLR 2022
D.1.2 GI-SHIFT
This section includes the plots for GI-shift scenario with different perturbation, window sizes (w), and fixed severity.
100
Ours
Shifted samole ratio Accuracy (%
Detection Rate over repelti (%)
100
100
Shifted /Accuracy (%6
Muuffl
Ralee rspelition
40
40
40
20
20
20
0-
A
2000
6000
6000
8000
10000
2300
<000
6030
8000
10000
samples
samples
(a) Contrast
(b) Defocus blur
Delection Rale over repeliiiin 196)
100
Ours
Shifted sample ratio Accuracy (%6
Detection Rate over repelition (%)
100
Ours
(9%
H2
H2
30
80
H5
80
50
60
60
40
40
20
20
A
2000
4000
6000
8000
10000
2300
4000
6030
8000
10000
Number of samples
Number of samples
(c) Elastic transform
(d) Gaussian blur
Detection Rate over repetition (86)
100
Ours
100
(96)
H2
40
20
Shifted
2000
4000
6000
8000
10000
Number of samp es
(c) Gaussian noise
Figure 20: GI-shift with R 100, w 10. 1%.
32

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repetition (%)
100
Ours
Shifted (%)
Detartion uver repalition
112
112
H5
H9"
50
60
60
40
40
60
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Contrast
(b) Defocus blur
100
Ours
100
Shifted samole ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted (%6
Duluction Rale Uver repeltioo
H2
H2
50
H5%
80
H5"
80
MN
40
20
20
2000
8000
4000
Number of samples
Number of samples
(c) Elastic transform
(d) Gaussian blur
Detaction Rate over repetition (%)
Ours
Shifted (%)
H2
H5
80
60
40
40
20
2,00
1000
8000
8000
10000
Number of es
(e) Gaussian noise
Figure 21: GI-shift with R = 100, 20, 1%.
33

---

Under review as a conference paper at ICLR 2022
100
Ours
Prd
Shifted samole ratio Accuracy (%)
Detaction Rate over repelition (%)
100
Ours
Shifted (%%
Detartion uvei repelition
112
112
H5
H9
50
60
60
40
40
60
40
20
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Contrast
(b) Defocus blur
100
Ours
100
Shifted samole ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted semole (%6
Duluction Rale Uver repeltion
H2
H2
50
415
-00
H5
80
20
20
8000
4000
Number of samples
Number of samples
Elastic transform (c)
(d) Gaussian blur
Detaction Rate over repetition (%)
Ours
(%)
H2
H5
80
60
40
20
Shifted sample
20
2,00
1000
8000
8000
10000
Number of
(e) Gaussian noise
Figure 22: GI-shift with R = 100, 50, 1%.
34

---

Under review as a conference paper at ICLR 2022
D.1.3 GID-SHIFT
Similar the previous two sections, this section includes figures for the GID-shift scenario with different perturbation with severity 2, and different window sizes (w)
100
Ours
Shifted sample ratio Accuracy (%
Detection Rate Rate over repelti (%)
100
100
Shifted sample (%6
Raler rapelition
40
40
40
1
20
20
2000
6000
6000
8000
10000
2300
<000
6030 samples
8000
10000
Number samples
(a) Contrast
(b) Defocus blur
100
Ours
Shifted sample ratio Accuracy 1%6
Detection Rate over repelition 1%g
100
Ours
(%%
Delection Rale over repelition
H2
H2
30
+15
80
+45
80
50
60
60
40
40
20
20
2000
4000
6000
8000
10000
2300
4000
6030
8000
10000
Number of samples
Number of samples
(c) Elastic transform
(d) Gaussian blur
100
Ours
100
(96
Detection Rate over repetition
H2
36
40
M
20
Shifted
3
2000
4000
8000
10000
Number of samp es
(c) Gaussian noise
Figure 23: GlD-shift with 100, 10, 1%.
35

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repelition (%)
100
Ours
Shifted (%%
Detartionn uvet repelition
112
112
11
W
60
60
40
40
40
20
20
2000
6000
6000
8000
10000
2000
6000
6000
8000
10000
Number of samples
Number of samples
(a) Contrast
(b) Defocus blur
100
Ours
100
Shifted samble ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted (%6
Duluction Rale Uver repeltion
H22
H2
50
'155%
30
80
8000
Number of samples
Number of samples
(c) Elastic transform
(d) Gaussian blur
Detaction Rate over repetition (%)
Ours
(%)
H2
80
60
60
40
20
Shifted
2,00
1000
8000
8000
10000
Number of es
(e) Gaussian noise
Figure 24: GID-shift with R = 100, 20, 1%.
36

---

Under review as a conference paper at ICLR 2022
100
Ours
Shifted samole ratio Accuracy (%)
Detaction Rate over repelition (%)
100
Ours
(%%)
Detartionn uver repelition
112
112
H5
30
60
60
60
40
40
20
20
Shifted
2000
6000
6000
8000
10000
2000
6000
6030
8000
10000
Number of samples
Number of samples
(a) Contrast
(b) Defocus blur
100
Curs
100
Shifted samble ratio Accuracy (%6
Detaction Rake over repeiition (9%)
100
Ours
100
Shifted (%6
Dulaction Rale Uver repeltioo
H22
H2
50
745"
300
H9
80
60
40
2000
8000
Number of samples
Number of samples
(c) Elastic transform
(d) Gaussian blur
Detaction Rate over repetition (%)
Ours
4
(%)
H2
H5
80
60
60
40
20
Shifted
2,00
1000
8000
8000
10000
Number of es
(e) Gaussian noise
Figure 25: GID-shift with R = 100, 50, 1%.
37

---

Under review as a conference paper at ICLR 2022
D.2 NUMBER OF SAMPLES FOR DETECTION
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
Table 5: Number of samples for detection with R 100, 10
Defocus Blur
Elastic Transform
Gaussian Blur
Gaussian Noise
Severity
Algorithms
Contrast
Ours
280
240
510
400
220
H2
610
550
1310
950
450
H5
610
460
1610
960
410
Ours
230
200
220
210
180
2
H2
470
450
450
490
350
H5
410
410
410
460
310
Ours
190
170
190
140
140
3
H2
350
370
410
270
270
H5
310
360
360
260
260
Ours
150
140
160
120
120
H2
250
290
290
210
210
H5
210
260
260
210
160
Ours
130
120
140
100
110
H2
210
230
210
170
150
H5
160
210
210
160
160
Table 6: Number of samples for detection with R 100, w 20
Defocus Blur
Elastic Transform
Gaussian Blur
Gaussian
Severity
Algorithms
Contrast
Noise
Ours
300
250
430
360
250
H2
530
430
970
770
410
H5
460
410
1010
710
360
Ours
250
220
240
230
210
H2
430
390
390
410
350
H5
360
360
360
360
310
Ours
220
200
230
170
170
H2
330
330
370
290
270
H5
310
310
360
260
260
Ours
170
170
200
140
140
H2
270
290
310
230
230
H5
260
260
260
210
210
Ours
160
150
170
110
120
H2
250
250
230
190
190
H5
210
210
210
160
160
38

---

Under review as a conference paper at ICLR 2022
Table 7: Number of samples for detection with R 100, w = 50
Defocus Blur
Elastic Transform
Gaussian
Gaussian
Severity
Algorithms
Contrast
Blur
Noise
Ours
360
300
490
430
290
H2
570
510
870
710
470
H5
560
460
810
660
410
Ours
310
270
280
280
250
H2
510
450
470
470
390
H5
460
410
460
460
360
Ours
260
240
270
220
210
H2
410
410
450
330
330
H5
360
360
410
310
310
Ours
210
210
230
170
160
H2
310
370
370
270
270
H5
310
360
360
260
260
Ours
170
170
190
130
130
H2
290
310
290
210
210
H5
260
260
260
210
210
39

---

Under review as a conference paper at ICLR 2022
D.2.2 GI-SHIFT
Table 8: Number of samples for detection with R 100, 20
Defocus Blur
Elastic Transform
Gaussian Blur
Gaussian Noise
Algorithms
Contrast
Ours
2100
2040
2100
2040
2050
H2
2890
2150
2610
2170
2190
H5
4110
4010
4110
4010
4010
Table 9: Number of samples for detection with R 100, 50
Defocus Blur
Elastic Transform
Gaussian Blur
Gaussian
Algorithms
Contrast
Noise
Ours
1580
980
1340
1170
970
H2
2310
2130
2190
2170
2130
H5
2460
2310
2510
2310
2310
D.2.3
GID-SHIFT
Table 10: Number of samples for detection with 100, w = 20
Defocus Blur
Elastic Transform
Gaussian Blur
Gaussian Noise
Algorithms
Contrast
Ours
620
430
530
470
450
H2
1890
990
1670
1170
1030
H5
2010
2010
2060
2010
2010
Table 11: Number of samples for detection with R = 100, w 50
Defocus Blur
Elastic Transform
Gaussian Blur
Gaussian
Algorithms
Contrast
Noise
Ours
590
480
550
520
490
H2
1110
870
1010
970
910
H5
1510
910
1310
1010
960
40


Reviews:
[{"review_id": "tde78jJAAu9", "reviewer": "Reviewer_Wc7g", "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": "### Pros:\n1) This work introduces a novel method to train the classifier and detect covariate shifts in a sequential manner. And the online pipeline is interesting.\n2) This work is well formulated with elaborate proofs and theoretically solid.\n\n### Cons:\n1) This method evaluates each example before taking a gradient step on that example. It means that every sample can be used only once for training the classifier, i.e., training for one epochs. It seems to be a great limitation of this method. With a held-out test set, this problem doesn’t exist. As a common sense, training for more epochs can improve the performance. If the baselines (H2, H5) are better trained, I think their performances would be much better.\n2) Besides, the experiments seem to be a litte unfair. The proposed method and baselines (H2, H5) differ in both training sets and testing sets because of the different sampling strategies. The proposed method use the whole set for both training and testing while baselines sample some examples for testing and use the others for training. \n3) I also concern about the problem of cold boot. At the begining of training, the classifier is with poor performance. how can we evaluate the samples in this stage?\n\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "Though this paper is interesting and theoretically solid, the experimental parts do not convince me. Currently my rating is marginally below the acceptance threshold. I will raise my score if the concerns about the experiments are addressed.\n\n### After rebuttal\nI raise the score from 5 to 6 given that the experimental parts are improved and most concerns are solved. But I will not act as a champion for acceptance.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "XNFKDJXbsDf", "reviewer": "Reviewer_yyGB", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "positives:\nThe authors investigate an essential problem in real-world applications. This draft is well-organized and easy to follow. \n\nnegatives:\n- The proposed method attempts to adapt the offline covariate shift detecter to the sequential detection and learning scenario. However, due to the statistical nature of the two-sample test, the proposed approach still need a relatively large number of data to work. As shown in section 4, the error bound depends on the sample size in the order of $O(1/\\sqrt{m})$. In the online learning scenario, the size of sampled (target) data is usually limited, and thus the effectiveness of this basic guarantee is limited.\n- The experiments are conducted on the modified ImageNet dataset to simulate various covariate shifts. It is suggested to test the performance of the proposed algorithm on a realistic public benchmark dataset.", "summary_of_the_paper": "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.", "summary_of_the_review": "This draft proposes an online covariate shift detection algorithm based on two-sample tests. The theoretical guarantee is based on the size of sampled data, and thus, it is usually hard to make the error (false positive/negative rate) small in real-world online applications. Empirical studies show good performance on the modified benchmark datasets with a relatively large number of sampled data.", "strength_and_weaknesses": "", "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": "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": "6w_wBAK9Fk", "reviewer": "Reviewer_PsoX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Strong points:\n- the method is simple and allows to use any classification model that can be trained in an online manner, which makes it of practical interest \n- the paper is clearly written\n- there is strong theoretical grounding coming from classical statistics\n\nWeak points:\n- there is some obscurity in the proof of the crucial theorem 3, which could hide a flaw\n- an empirical comparison with existing two-sample test would be interesting to better justify the need for this method and as an additional baseline\n- in the experiments, the false positive rate is above the specified level:\n  - the given reason (multiple hypothesis testing) is not convincing\n  - it makes the detection power comparison less meaningful\n\nDetailed review:\n\n### COMPARISON TO SEQUENTIAL TWO-SAMPLE TESTS:\nIt is argued (sections 1 and 2) that sequential tests are not appropriate in the scenarios proposed since they assumed that all the data is shifted. This assumption is only relevant with respect to False Negative Rate guarantees (e.g. consistency). Nevertheless, guarantees on FPR are obtained under the assumption that the distributions are equal. Therefore, sequential two-sample test are applicable to the scenario of this paper.\nProviding comparisons with some of the cited sequential two-sample test would definitely make the paper stronger, justifying better the need for the proposed method and its advantages. You could run a sequential two-sample test by drawing samples from the training set (without replacement---this requires the training set to be roughly as large as the testing horizon) and from the test set in the order they come, until a rejection occurs and then you could reset everything and start testing again.\n\n### LEMMA 1:\nThe notation $x\\_{i..j}$ should be introduced and $i,j$ should be specified.\nDoes $\\hat{g}\\_{i,j-1}$ refer to the classifier itself (in the case of a NN a set of weights and biases?) ?  Or is it the accuracy on the range $i..j-1$?\nIn the proof, $\\hat{g}_{i}$ appears as a random variable, so I guess it represents all the variables defining the model.\nThis should be formalized.\n\n### PROOF OF THEOREM 3\nIt is not clear how Lemma 1 is used:  more precisely, **why can you say that  $s_{w,t}$ is a binomial variable with parameter 1/2?** Before Lemma 1, you say:\n*the key to have valid bounds is proving the independence on predictions $\\hat{y}\\_1, \\dots, \\hat{y}\\_t$ (and $\\hat{y}'\\_1, \\dots, \\hat{y}'\\_t$) to have a valid Clopper-Pearson interval, since they are seemingly\ndependent through online learned classifier $\\hat{g}_t$.\nFirst, our key result shows that our estimate of the\naccuracy of $\\hat{g}\\_t$ valid—i.e., the labels $\\hat{y}\\_{i:j}$ are conditionally independent.*\n\nWhat do you mean exactly by a valid estimate of the accuracy? This should be formalized.\nAlso, where does $t$ lie with respect to $i..j$ ? \n\n### LACK OF CONTROL OF FPR IN EXPERIMENTS:\nIt is suggested that the lack of control of the FPR (which is often around 3% and sometimes above, while the specified level is 1%) is due to multiple hypothesis testing. However, I can't see which multiplicity you refer to. These rates are obtained sample-wise over the $R$ repetitions, and therefore they should be empirical estimates of the theoretical rate considered in Thm 3. A multiple hypothesis testing problem would occur if we use multiple statistics to get to one decision which is not the case here.\nThree possible explanations come to my mind: \n- a possible leak between the data used for training the Neural network and the data used to compute the statistic (i.e. some data points used to train a model $\\hat{g}$ are also used as data points to compute the statistic with $\\hat{g}$)\n- the practical assumption that $\\mathcal{S}$ is a uniform distribution over the training set : even if the training and test set come from the same distribution, this practical assumption will make $\\mathcal{S}$ different from $\\mathcal{T}$.\n- A flaw in theorem 3?\n\nTherefore I suggest to :\n- Clarify the proof of Theorem 3\n-  fix/give a better explanation of the uncontrolled FPR observed in the experiments\n-  provide an empirical comparison to sequential two-sample tests: this would show the need for your approach and make the paper stronger\n\n### MINOR ISSUES/COMMENTS:\n\n1) Bayes Ball algorithm and reference to Bishop 2006: \nCitation should be more precise since it is a text book . In fact, I couldn't find \"Bayes Ball\" in that book.\nIt seems to be called d-separation there.\n\n\n2) \"$\\hat{g}\\_t$ necessarily achieves a trivial accuracy of 1/2\" : I guess you refer to theoretical accuracy. You should make it precise since there could a confusion with the achieved empirical accuracy which is not necessarily exactly 1/2. \n\n3) The description of the algorithm should be improved: in particular, $w$ should be included as input and the formula for $\\hat{\\mu}_{w,t}$ should appear there.\nThe title says \"Sequential Calibrated ...\": the word \"calibrated\" appears nowhere else\n\n4) THEOREM 5: it would be interesting to discuss the consequences of the assumptions $a(w,\\alpha)\\leq w$ and $b(w,\\alpha)\\geq 0$.\n\n5) First inequality using the VC dimension: It would help the reader to give some justification/precise reference for this inequality.\n\n6) Table 2b is misleading : higher FPRs are observed in the plots, when going beyond 200 samples\n\n7) Proof of Thm 5: $\\mu_{\\hat{g}}^*$ seems to correspond to $\\mu_{w,t}^*$ , why this new notation?\n\n8) Equalities (8) and (9) should be inequalities.\n\n9) Definitions should use a different equal sign ($\\equiv$ or $:=$)\n\n\nTYPOS:\n\n\"through online learned classifier\" -> \"through the online learned classifier\"\n\ncovarate, covarite-> covariate\n \nTo checking -> for checking\n\nOur estimate of the accuracy of $\\hat{g}\\_t$ **is** valid\n\nStatement of theorem 5: \"where $\\epsilon\\in(0,1/2]$ is the accuracy\"  Maybe a comma is missing before \"is\"\n\nTables: G-shift -> GI-shift\n\n\n\n\n\n", "summary_of_the_paper": "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.\nThe 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. \nA 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).\n ", "summary_of_the_review": "My main concern is the lack of control on the False Positive Rate (FPR) observed empirically. This is an important issue since it claims to have exact FPR control. This deserves further investigation since the given explanation based on multiple hypothesis testing is not convincing. The proof of the theoretical result that guarantees the FPR contains some obscure parts. \nThe paper also  lacks comparisons to existing sequential two-sample tests, which, even if  they do not provide guarantees on the False Negative Rate in non-iid scenarios,  are natural competitors since they do provide FPR guarantees (under the hypothesis of equal distributions).\n\nTherefore, I recommend rejection in this current form.\n\n**================== After rebuttal ==================**\n\nThe new comparison with Wald's test seems a bit limited by the alternative hypothesis with a fixed epsilon=0.2. Also, the power depends on the choice of the classifier. Cited nonparametric sequential two-sample tests are more flexible and should be considered instead.\nMy concerns on FPR control have been addressed.\n \nFor these reasons, I increase my score to 5.\n", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "6Y7xdaOzr1o", "reviewer": "Reviewer_X4Zb", "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": "Pros:\n\n1.  This research topic is valuable since the community cares about the AI reliability and trustworthy ML. Although deep networks can address many real-world problems, it is not reliable (e.g., OOD) and can be attacked (e.g., adversarial attacks). Thus, detecting such shifts is meaningful in many fields.\n\n2. This paper proposed a test to dynamically detect the distribution shift, which seems novel and interesting.\n\n3. Experiments are conducted in many situations, which supports the effectivenss of the proposed method.\n\nCons:\n\n1. Some key discussions are missing. As reviewed in this paper, kernel MMD is another type of two-sample tests. If we use SGD or Adam to online update the kernel parameters, can kernel MMD be used to address your problem? It would be great to provide some empirical evidence, but detailed discussions are also ok.\n\n2. In (1), what does \\sP stand for?  It is a probability measure without proper explanations/definitions. For a probability measure P, we often use P(A) to represent the measure on a set A.\n\n3. Some key references are missing. In the literature, concept drift detection and adaptation are very close to your problem setting. Please conclude some discussions between your problem and them.\n\n4. How to generate the data used in this paper? What kind of shifts you considered? Mean shift? Covariance shift?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "In general, this paper considers an important problem. However, some points must be clarified before the possible acceptance.", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: This paper proposes to repeatedly apply the classifier two-sample tests (proposed by Kim, Ramdas, Singh, Wasserman, in 2016, and developed further by Lopez-Paz, Oquab, in 2017) for the purpose of detecting covariate shift. The authors propose methods to extend the aforementioned tests to a sequential setting. Overall, the reviewers do not lean towards acceptance, and neither do I. Several constructive suggestions are provided by reviewers, some are summarized below.

The authors claim that sequential tests are not desirable in such a setting, and thus choose to pay a multiple testing price by repeatedly applying a batch test. However, sequential tests are in fact applicable (they will control type-1 error) but may have a worse power if the alternative is not true at the very start --- but these were entirely dropped from the simulations; in fact, comparing the increased type-1 error of the authors' approach to the increased type-2 error of sequential approaches may be worth clarifying. 

Perhaps the "right" solution that the authors are looking for could be gotten by converting a sequential test into a sequential changepoint detection algorithm (via repeated application of a sequential test, each started at a new time). Also see "Conformal test martingales for change-point detection" and "Inductive Conformal Martingales for Change-Point Detection" by Vovk et al., which are currently not cited.
Decision: Reject