Window-Based Distribution Shift Detection for Deep Neural Networks
Authors: Guy Bar-Shalom
Yonatan Geifman
Ran El-Yaniv
Venue: NeurIPS 2023 poster (2023)
Keywords: Distribution shift detection
Window-based detection
TL;DR: Our paper proposes a new method for detecting distributional deviations in deep neural networks. Compared to state-of-the-art methods, our approach achieves superior performance while also significantly reducing computational complexity.

Abstract: To deploy and operate deep neural models in production, the quality of their predictions, which might be contaminated benignly or manipulated maliciously by input distributional deviations, must be monitored and assessed. Specifically, we study the case of monitoring the healthy operation of a deep neural network (DNN) receiving a stream of data, with the aim of detecting input distributional deviations over which the quality of the network's predictions is potentially damaged. Using selective prediction principles, we propose a distribution deviation detection method for DNNs. The proposed method is derived from a tight coverage generalization bound computed over a sample of instances drawn from the true underlying distribution. Based on this bound, our detector continuously monitors the operation of the network over a test window and fires off an alarm whenever a deviation is detected. Our novel detection method performs on-par or better than the state-of-the-art, while consuming substantially lower computation time (five orders of magnitude reduction) and space complexity. Unlike previous methods, which require at least linear dependence on the size of the source distribution for each detection, rendering them inapplicable to ``Google-Scale'' datasets, our approach eliminates this dependence, making it suitable for real-world applications. Code is available at [https://github.com/BarSGuy/Window-Based-Distribution-Shift-Detection](https://github.com/BarSGuy/Window-Based-Distribution-Shift-Detection).

Window-Base Distribution Shift Detection for Deep Neural Networks
Guy Bar-Shalom
Yonatan Geifman
Department of Computer Science Technion Israel Institute of Technology guy bâcs. technion. ac.il
Deci.Al yonatan@deci
Ran El-Yaniv
Department of Computer Science
Technion Israel Institute of Technology, Deci.Al raniêcs. technion. ac. i1
Abstract
To deploy and operate deep neural models in production, the quality of their predic- tions, which might be contaminated benignly or manipulated maliciously by input distributional deviations, must be monitored and assessed. Specifically, we study the case of monitoring the healthy operation of deep neural network (DNN) receiv- ing a stream of data, with the aim of detecting input distributional deviations over which the quality of the network's predictions is potentially damaged. Using selec- tive prediction principles, we propose a distribution deviation detection method for DNNs. The proposed method is derived from tight coverage generalization bound computed over a sample of instances drawn from the true underlying distribution. Based on this bound, our detector continuously monitors the operation of the net- work over a test window and fires off an alarm whenever deviation is detected. Our novel detection method performs on-par better than the state-of-the-arr, while consuming substantially lower computation time (five orders of magnitude reduc- tion) and space complexity. Unlike previous methods, which require at least linear dependence on the size of the source distribution for each detection, rendering them inapplicable "Google-Scale
datasets, our approach eliminates this dependence, making it suitable for real-world applications. Code is available at https: gi thub. com cwmmcomm/aa/eeeeeeee BarSaurrr//aaaaa SaaiSGGGy////nwwWna WWindwwwwwwwwn//ii Based--aed----e Distribution Shift-Detectiinn
Introduction
A wide range of artificial intelligence applications and services rely on deep neural models because of their remarkable accuracy. When trained model is deployed production, its operation should be monitored for abnormal behavior, and a flag should be raised if such is detected. Corrective measures can be taken if the underlying cause of the abnormal behavior identified. For example, simple distributional changes may only require retraining with fresh data, while more severe cases may require redesigning the model (e.g., when new classes emerge).
In this paper we focus on distribution shift detection the context of deep neural models and consider the following setting. Pretrained model is given, and we presume it was trained with data sampled from some distribution P. addition to the dataset used in training J. we are also given an additional unlabeled sample of data from the same distribution, which is used to train detector D) (we refer to this as the detection- detection-training set or source set). While f is used in production to process a stream of emerging input data, we continually feed D with the most recent window i of k input elements.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The detector also has access to the final layers of the model f and should be able to determine whether the data contained in Wi came from a distribution different from P. We emphasize that in this paper we are not considering the problem of identifying single-instance out-of-distributin or outlier instances [28, 21, 22, 16, 38, 35, 34, 11], but rather the information residing in a population of k instances. While it may seem straightforward to apply single-instance detectors to window (by applying the detector to each instance in the window), this approach can be computationally expensive since such methods are not designed for window-based tasks; see discussion in Section 3. Moreover, we demonstrate here that computationally feasible single-instance methods can fail to detect population- pasedd deviations. We emphasize that we are not concemed in characterizing types of distribution shifts, nor do we tackle at all the complementary topic of of-distribution robustness.
Distribution shift detection has been scarcely considered in the context of deep neural networks (DNNs), however, it is a fundamental topic in machine learning and statistics. The standard method for tackling is by performing a dimensionality reduction over both the detection trriiinnn--iiingggg (source) and test (target) samples, and then applying a two-sample statistical test over these reduced representations to detect deviation. This is further discussed Section 3. In particular, deep models can benefit from the semantic representation created by the model itself, which provides meaningful dimensionality reduction, that is readily available at the last layers of the model. Using the embedding layer (or softmax) along with statistical two-sample tests
recently proposed by Lipton et al. [29] and Rabanser et al. [37] who termed solutions of this structure black-box shift detection (BBSD). Using both the univariate method, see details below, Rabanser et al. [37] achieve impressive detection results when using MNIST and CIFAR-10 as proxies for the distribution P. As shown here, the KS test is also very effective over ImageNet when a stronger model is used (Res.ee50 vs ResNet18) 18). However, BBSD methods have the disadvantage of being computationally intensive (and probably inapplicable to read-world datasets) due to the use of two-sample tests between the detection-training set (which can, and is preferred be the largest possible) and the window Wa; a complexity analysis is provided in Section 5.
Dolmogorov-Smmmmoo (KS) test and the maximum mean discrepancy (MMD)
We propose a different approach termed Coverage-Based Detection (CBD), which builds upon selective prediction principles [9. 14]. In this approach, a model quantifies its prediction uncertainty and abstains from predicting uncertain instances. First, we develop method for selective prediction with guaranteed coverage. This method identifies the best abstaining threshold and coverage bound for a given pretrained classifier f, such that the resulting empirical coverage will not violate the bound with high probability (when abstention is determined using the threshold). The guaranteed coverage method is of independent interest, and it analogous to selective prediction with guaranteed risk [14). Because the empirical coverage of such a classifier is highly unlikely to violate the bound if the underlying distribution remains the same, systematic violation indicates a distribution shift. To be more specific, given a detection- -erttioottrriing sample Sn, our coverage-base based detection algorithm computes fixed number of tight generalization coverage bounds, which are then used to detect a distribution shift in a window W₁ of test data. The proposed detection algorithm exhibits remarkable computational efficiency due to its ability to operate independently of the size of S.,. during detection, which is crucial when considering "Google-Scale datasets, such as the JFT-3B dataset. In contrast, the currently available distribution shift detectors rely on a framework that requires significantly higher computational requirements (this framework is illustrated in Figure 3 in Appendix A). A run-time comparison of those baselines w.r.t. our CBD method is provided Figure 1.
In a comprehensive empirical study, we compared our CBD algorithm with the best-performing baselines, including the KS approach of [37]. Additionally, we investigated the suitability of single- instance detection methods for identifying distribution shifts. For a fair comparison, all methods used the same (publicly available) underlying models: ResNet50, MobileNeeV3-SS and VTT-T. To evaluate the effectiveness of our approach, we employed the ImageNet dataset to simulate the source distribution. We then introduced distribution shifts using a range of methods, starting with simple noise and progressing to more sophisticated techniques such as adversarial examples. Based on these experiments, is evident that CBD is overall significantly more powerful than the baselines across a wide range of test window sizes.
To summarize, the contributions of this paper are: (1) A theoretically justified algorithm (Algo- rithm 1), that produces coverage bound, which is of independent interest, and allows for the creation of selective classifiers with guaranteed coverage. (2) theoretically motivated "windowed" detection

---

algorithm, CBD (Algorithm 2), which detects distribution shift over a window; this proposed algorithm exhibits remarkable efficiency compared sfate-of-the-art methods (five orders of magni- tude better than the best method). (3) A comprehensive empirical study demonstrating significant improvements relative to existing baselines, and introducing the use of single-instance methods for detecting distribution shifts.
2 Problem Formulation
We consider the problem of detecting distribution shifts in input streams provided to pretrained deep neural models. Let P - Px denote a probability distribution over an input space X, and assume that a model f has been trained on set of instances drawn from P. Consider setting where the model f is deployed and while being used in production its input distribution might change or even be attacked by an adversary. Our goal is to detect such events to allow for appropriate action, e.g.. retraining the model with respect to the revised distribution.
Inspired by Rabanser al. [37], formulate this problem follows. We are given pretrained model f. and a detection-training set, S. ~ pmm Then we would like to train a detection model to be able to detect distribution shift; namely, discriminate between windows containing in-distribution (ID) data, and Wa ~ Q", where Q is possibly different distribution, the objective is determine whether P Q. We also ask what is the smallest test sample size k required to determine that P of Q. Since typically the detection ttriiinntriiing set Sm can be quite large, we further ask whether is possible to devise an effective detection procedure whose time complexity is o(m).
(AD) data. Thus, given an unlabeled test sample window
3 Related Work
Distribution shift detection methods often comprise the following two steps: dimensionality reduction, and two-sample test between the detection-trainie traininn sample and test samples. In most cases, these methods are "lazy" in the sense that for each test sample, they make a detection decision based on a computation over the entire detection-training sample. Their performance will be sub-optimal if only a subset of the train sample is used. Figure 3 in Appendix A illustrates this general framework.
The use of dimensionality reduction is optional. It can often improve performance by focusing on a less noisy representation of the data. Dimensionality reduction techniques include no reduction, principal components analysis [1], sparse random projection [2], autoencoders [39, 36), domain classifiers, [37] and more. In this work we focus on black box shift detection (BBSD) methods [29]. that rely deep neural representations of the data generated by pretrained model. The representation extracted from the model will typically utilize either the softmax outputs, acronymed BBSD-Softmax, the embeddings, acronymed BBSD-Embeedding; for simplicity, we may omit the BBSD acronym. Due to the dimensionality of the final representation, multivariate or multiple univariate two-sample tests can be conducted.
By combining BBSD-Softmax with Kolmogorov- -miinov (KS) statistical test [33] and using the Bonferroni correction [3], Rabanser et al. [37] achieved state-of-the-ard results in distribution shift detection in the context of image classification (MNIST and CIFAR-IO) 10).. We acronym their method as BBSD-KS Softmax (or -S-Softmax). The univariate KS test processes individual dimensions separately; its statistic is calculated by computing the largest difference Z of the cumulative density functions (CDFs) across all dimensions follows: Z = sup_ Fp(2) /up_|Fp(22
Fo(2)), where Fq and Fp are the empirical CDFs of the detection- training and test data (which are sampled from P and Q, respectively; the minimal p-value among all tests is less than 9. where a is the significance level and d is the number of dimensions. Although less conservative approaches aggregation exist [20, 30], they usually assume some dependencies among the tests. The maximum mean discrepancy (MMD) method [18] is a kernel-based multivariate test that can be used to distinguish between probability distributions P. and Q. Formally, MM (M P, Q) = 1|p | 13:.. where Mp and NQ are the mean embeddings of P and Q in a reproducing kernel Hilbert space F. Given kernel K. and samples, I2, ..,, Rm)} ~ pm and {a1, 2z2 ... 23} ~ Q², an unbiased estimator for MMD can be found in [18, 42]. Sutherland et al. [43] and Gretton et al. [18] used the RBF kernel K(2z, x²) 2 1 where 20 is set to the median of the pairwise Euclidean distances
Section 2). The Bonferroní correction rejects the null hypothesis when
3

---

between all samples. By performing permutation test on the kernel matrix, the p-value is obtained. In our experiments (see Section 6.4), we thus use four population based baselines: KS-Softmax, KS-Embeddings, MMD-Softmax, and MMD-Embeddingg,
As mentioned in the introduction, our work is complementary the topic of single-instance out-of- distribution (OOD) detection [28, 21, 22, 16, 38, 35, 34, 11]. Although these methods can be applied each instance in a window, they often fail to capture population statistics within the window, making them inadequate for detecting population-basee changes. Additionally, many of these methods are computationally expensive and cannot be applied efficiently to large windows. For example, methods such as those described in [41, 27] extract values from each layer in the network, while others such as [28] require gradient calculations. We note that the application of the best single- instance methods such as [41, 27, 28] in our (large scale) empirical setting is computationally challenging and preclude empirical comparison to our method. Therefore, we consider (in Section 6.4) the detection performance of two computationally efficient single-instance baselines: Softmax-Respont (abbreviated as Single-instance SR or Single-SR) and Entropy-based (abbreviated as Single-instance Ent or Single-Ent), as described in [4, 6, 21J. Specifically, we apply each single-instance OOD detector to every instance in the window and the Eetection-training set. We then use a two-sample 1-test to determine the p-value between the uncertainty estimators of each sample.
Finally, we mention [14] who developed risk generalization bound for selective classifiers [9]. The bound presented in that paper is analogous to the coverage generalization bound we present in Theorem 4.2. The risk bound in [14] can also be used for shift-detection. To apply their risk bound to this task, however, labels, which are not available, are required. CBD) detects distribution shifts without using any labels.
4 Proposed Method - -Coverage-Based Detection
In this section we present Coverage- Detection (CBD), a novel technique for detecting a distribution shift based on selective prediction principles (definitions follow). We develop tight generalization coverage bound that holds with high probability for ID data, sampled from the source distribution. The main idea is that violations of this coverage bound indicate distribution shift with high probability. Section 6.2, we offer an intuitive demonstration that aids understanding our approach.
4.1 Selection with Guaranteed Coverage
We begin by introducing basic selective prediction terminology and definitions that are required describe our method. Consider a standard multiclass classification problem, where X' is some feature space (e.g., raw image data) and y is a finite label set, y = {1, 2, 3, .... C), representing C classes. Let P(X, Y' be probability distribution over X' x Y, and define a classifier as a function f: x We refer to P as the source distribution. A selective classifier [9] is pair (f. g). where is a classifier and g : X' + {0, 1} is selection function [9], which serves as binary qualifier for f as follows,
(f.)(=)) & ff(x),
if g(x) = 1; if g = 0.
don't [do''tknow, know,
A general approach for constructing a selection function based on given classifier f is to work in terms of confidence-rate/ function [15], Ky X' + Rt, referred
refferree to as CF. The CF Ny should quantify
confidence in predicting the label of æ based on signals extracted from f. The most common and well-known CF for a classification model ff (with softmax at its last layer) is its softmax response (SR) value [4, 6, 21J. A given CF Ky can be straightforwarddy used to define a selection function: (x(x) 2 { = 11 [<)(()) 2 0j, where 0 is a user-defined constant. For any selection function, we define its coverage w.r.t. a distribution P (recall, P A Px. see Section 2), and its empirical coverage w.r.t. sample S A [21,22,. ... xk), c(0, P) A Ep Ex[go(=)); and a(0, St) A E respectively.
Di=1 (0.).).
Given a bound on the expected coverage for a given selection function, we can use it to detect distribution shift via violations of the bound. We will now formally state the problem, develop the bound, and demonstrate its use in detecting distribution shifts.

---

Problem statement. For a classifier f. a detection-training sample Sm pm,, confidence parameter ó > and desired coverage O, our goal is to use Sn to find a value (which implies a selection function go) that guarantees the desired coverage, with probability 1 - 6, namely,
Prom. {c(0,P) < <.
This means that under coverage should occur with probability of at most d.
A threshold 0 that guaran- tees Equation (1) provides a probabilistic lower bound, guaranteeing that coverage c of ID unseen population (sampled from P) satisfies c > e* with probability of at least 1 5. For the remaining of this sec- tion, we introduce the se- lection with guaranteed cov- erage (SGC) algorithm (Al- gorithm 1), which outputs bound (b*) and its corre- sponding threshold (0).
Algorithm 1: Selection with guaranteed coverage (SGC)
Input:
detection-trainiin set: Sm, confidence-rate function: Kf, confidence parameter ò. larget coverage: c².
Sort S.. according to Ky (.r:). æ4 S., (and now w.l.o.g. that indices reflect this ordering).
Amin = 1, Amax = m71
for = to k = flog2 m do
[Zmin Zmax
(x;)))
Calculate 6 (0., 5m)
Solve for bj (m, m Sm)); () (sce Lemma 4.1)
if 67 (m, m (0,, Sm), x) <e then
10
Zeax
11
else
12
Amiin
The SGC algorithm receives input a classifier f. a CF ky. confidence parameter ö, a target coverage e", and a detection-training set Sm
end if
14 end for
15 Output: bound: by (m, m (Os, Sm), 2). threshold:
The algorithm performs binary search to find the optimal coverage lower bound with confidence 6, and outputs cover- age bound 6* and the corresponding threshold 0, defining the selection functioo. A pseudo code of the SGC algorithm appears in Algorithm 1.
Our analysis of the SGC algorithm makes use of Lemma 4.1, which gives tight numerical (general- ization) bound on the expected coverage, based on a test over a sample. The proof of Lemma 4. is nearly identical to Langford's proof of Theorem 3.3 in [26], p. 278, where instead of the empirical error used in [26), we use the empirical coverage, which is also Bernoulli random variable.
Lemma 4.1. Let P be any distribution and consider selection function with a threshold 6 whose coverage is c(0, P). Let Sm. sampled i..dd from P. Let bz (m, ε(0, Sm), 8) be the solution of the following equation:
be given and let c(0, Sm.) be the empirical coverage w.r.t the set
org min b
Σ 1=
(1 b)m=- 51 51- (
m (m)
(2)
Then,
Prs... (c(0,P) < 6" (m, c(0, < 6.
(3)
The following is uniform convergence theorem for the SGC procedure stating that all the calculated bounds are valid simultancously with a probability of at least 1
Theorem 4.2. (SGC- Uniform convergence) Assume Sn is sampled ii.d. from P, and consider an application Algorithum 1. For k = [log, m], let bç (m, (0, Sm); { and 0 be the values obtained in the gh iteration of Algorithm Then,
Prs., {i: c(O,, P) < 67 (m, m 2, Sm), {) < 8.
5

---

Proof (sketch see full proof in the Appendix B.1). Define.
Be, & bg (m, m C,, Sm), ) Co. - c(0, P), then,
!
Prs.. (3i: : Co. < B = Σ
d0' Prs... (Cy < Bor }. Prs 10; = 0'}
1=
d0' Prsm (0, - 00'
6.
k
1=1
i=1
We would like to note that addition to Algorithm 1, we also provide a complementary algorithm that returns tight coverage upper (rather than lower) bound, along with the corresponding threshold. Details about this algorithm and its application for detecting distribution shifts are discussed in Appendix F.
4.2 Coverage-Based Detection Algorithm
Our coverage-based detection (CBD) algorithm applies SGC to Carget target coverages uniformly spread between the interval [0.1, I], excluding the coverage of 1. We set Crarge 10, 8 = 0.01, and ky(xx)
(ntropy(x) for all our experiments; our method appears to be robust to those hyper-parameters, as we demonstrate in Appendix E. Each application j of SGC on the same sample Sm. ~ pm with a target coverage of c; produces a pair: (g), which represent bound and threshold, respectively. We define 8(ē(b") to be a binary function that indicates bound violation, where è is the empirical coverage (of sample) and b* is bound, 5(clb") = 1[e < b*). Thus, given window of h samples from an alternative distribution, W Qt, we define the sum of bound violations, V, follows,
Cura
Guze
V
Σ (bj 6(0,, Wo)) 8(8(0), Wi)lb)) 1 Cuuret
Σ Σ (b) 90, (x.)) 8(6, 1b)),
(4)
Cuaget
1m1
where we obtain the last equality by using é & 8(0), Wi) = 1/2 E Io, (2.). Considering Figure 2b in Section 6.2, the quantity V is the sum of distances from the violations (red dots) to the lincar diagonal representing the coverage bounds (black line).
When Q equals P, which implies that there is no distribution shift, we expect that the bounds (computed by SGC over Sm) will hold over Wa, namely 6(2, b)) = 0 for every iteration j: in this case, V 0. Otherwise, V will indicate the violation magnitude.
Algorithm 2: Coverage-Based Detection
// Fit
Input Training: Sm. 8.8 Curgei
Generntee Curge uniformly spread coverages for j = to Carre
$3.9g B00 5, 8.c7.
end For
Since represents the average of k Cuaya values (if at least one bound violation oc- curs), for cases where is Gunga > 30 (as in all our experiments), that V follows nearly normal distribu- tion [25] and perform t-test' to test null hypothesis, Ho : V = O, against the alternative hypothesis, H₂ : V > O. The null hypothesis is rejected if the p-value is less than the specified significance level a. pseudocode of our coverage-bane -aaed de- lection algorithun appears in Algorithm 2.
Output Training:
Cuage (33.0,))321
// Detect
Input Detection: ((b), 0,)) Kt.. k
Cruga
can assume
10
while True do
11
Receive window Wa = {x1 .2. ]x) Calculate V (see Equation (4) Obcain p-value H-iest, Ho if Paste a then Shift_detecce Output Detection: Saiit_derected Prilee
12
13
14
15
True
16
17
and
18
and while
To fit our detector, we apply SGC (Algo- rithm 1) on the detection-training set, Sm. for Cusga times, in order to construct the pairs {(b). ( detection model utilizes these pairs to monitor a given model, receiving at each time instant a test sample window of size & (user defined), We { {2, ... 2' }, which is inspected to see if its content is distributionally shifted from the underlying distribution reflected by the detcetion-training
Carp Our
S...
In experiments, use SciPy's stats. ttest_teeeeeeeeee _eampp implementation [44] for the t-test.

---

Our approach encodes all necessary information for detecting distribution shifts using only Curga scalars (in our experiments, Carge 10), which independent of the size of Sm. In contrast, the baselines process the detection-training set, Sm. which typically very large, every detection they make. This makes our method significantly more efficient than the baselines, see Figure and Table I in Section 5.
5
Complexity Analysis
This section provides complexity analysis of our method well as the baselines mentioned in Section 3. Table summarizes the complexities of each approach. Figure shows the population- approaches run-time (in seconds) as a function of the detection detection-training set size, denoted as m.
All population baselines are lazy learners (analogous to nearest neighbors) in the sense that they require the entire source (detection-traing trainint)) set for cach detection decision they make. Using only a subset will result in sub-optimal performance, since it might not capture all the necessary information within the source distribution, P.
In particular, MMD is permutation test [18] that also employs kernel. The com- plexity of kernel methods is dominated by the number of instances and, there- fore, the time and space complexities of 122 + mk)) and O(m² + +² + mk), respectively 2, where the case of DNNs, is the dimension of the embedding or softmax layer used for computing the kernel, and is the window size. The KS test [33] is a univariate test, which is applicd rately and then aggregates the results via Bonferroni correction. Its time and space complexities are O (d(m log m k log k)) and O (d(mm + k)), respectively.
Detection Method
Space
Time
MMD
(m² 8a mk) (d(m + k))
Old(m² + k² mk))
KSS
Odd(m log m + kt logk))
MMD are Odd(m²
Single-instance
(k))
(kk)
CBD (Ours)
(k))
(I:)
Table I: Complexity comparison. bold entries indicate the best detection complexity. m, k refers to the detection- training size (or source size), and window size, respectively. d refers to the number of dimensions after dimensionality reduction.
each dimension sepa-
The single-instanee baselines simply con- duct t-test on the heuristic uncertainty estimators (SR or Entropy-bassed between the detection detection-training set and the window data. By initially determining the mean and standard deviation the detection detection-training set, we can efficiently perform the t-test with a time and space complexity (A:).
The fitting procedure of our coverage-based detection algorithm incurs time and space complexities of Omm logm) m) and ((m). respectively. Each subsequent detection round incurs time and space complexi- ties of (k)) which is independent of the size of the detection- training (or source) set. Our method's superior efficiency is demonstrated both theoretically and empirically, shown in Table and Figure 1, respectively. Figure shows the run-time (in seconds) for each population-bass detection-trainigg set size, using a ResNet50 and a fixed window size of k 10 samples. Our detection time remains constant regardless of the size of the detection-training set, as opposed to the bascline methods, which exhibit run-time that grows function of the dnrectioo-training the best performing baseline, KS-Sofimax, when
detection method as a function of the
size. In particular,
method achieves
five orders of magnitude improvement in run-time the detection detection-training set size 1,000,000*. Specifically, our detection time is 5.19. 10-4 seconds, while KS-Softmax's 's detection time is 97.1 seconds, rendering it inapplicable for real-world applications.
Experiments Detecting Distribution Shifts
In this section we showcase the effectiveness of our method, along with the considered baselines, in detecting distribution shifts. All experiments were conducted using PyTorch, and the corresponding code is publicly available for replicating our results?.
With preprocessing in the fitting stage, this reduces to (ddkk² + mkk) per detection decision. MMD netection-training set is capped 1,000 due kemel method's unfavorable size dependence. "This specific experiment simulated synthetically (since the ImageNet validation set size 50,000).
5 https:/ htt///gitttuu cwm/ Baee///rrruyyyeaae CeneGGuyy/iiiie Saindov--asee Based- Distribution-Sii Shift- Detection.
7

---

9.71x 1011x10- (s)
10
Methods
CBD (Ours)
KS-Embeddings
10
KS-Softmax
MMD-Embeddings
Run-time (s)
MMD-Softmax
100
10
2.03x10-²
10
10
5.19x 10 (())
10
10a
102
10a
10
10
10
Detection-training set size (m)
Figure 1: Our method outperforms the baselines in terms scalability, with significant five orders of magnitude improvement in run-timg compared to the best baseline, KS-Softmax, when using detection-training set of 1, 000, 000 samples. One-a error-bars are shadowed.
6.1 Setup
Our experiments are conducted on the ImageNet dataset [7], using its validation dataset as proxies for the source distribution, P. We utilized three well-known known architectures, ResNet50 [19). PobileNert33SS [24], and VIT-T [8], all of which publicly available in timm's repository [45], our pre pre-trained models. To train detectors, we randomly split the ImageNet validation data (50,000) into sets, detection-trrining a validation set (1,000) applying shift. ensure the reliability
which
used the detectors' (49,000) of our results, we repeated the shift detection performance evaluation on 15 random splits, applying the same type of shift to different subsets of the data. Inspired by [37]. we evaluated the models using various window sizes, [Wa | (10, 20, 50, 100, 200, 500, 1000).
6.1.1 Distribution Shift Datasets
At test time, 1,000 validation images obtained our split can be viewed the in-distribution (positive) examples. For out-of-distribution (negative) examples, we follow the common setting for detecting OOD samples distribution shifts [37, 21, 28], and test on several different natural image datasets and synthetic noise datasets. More specifically, investigate the following types of shifts:
(1) Adversarial via FGSM: We transform samples into adversarial ones using the Fast Gradient Sign Method (FGSM) [17], with E (7- 10 10-10--4 10-4, 1. 10-4 ,5 10-4) 4). (2) Adversarial via PGD: We convert samples into adversarial examples using Projected Gradient Descent (PGD) [31], with e = 1 100 we use 10 steps, ==1 1- and random initialization. (3) Gaussian noise: We corrupt test samples with Gaussian noise using
standard deviations of a E (0.1, 0.3. 0.5, 1). (4) Rotation: We apply image rotations, 0 (5" 10" 20" 25 (5) Zoom: We corrupt test samples by applying zoom-out percentages of (90%, 70%, 50%). ). (6) ImageNet-O: We use the ImageNet-O dataset [23], consisting natural out-of-dixtribution samples. (7) ImageNet-A: We use the ImageNet-A dataset [23], consisting of natural adversarial samples. (8) No-shift: We include the no-shift case to check for false positives. To determine the severity of the distribution shift, we refer the reader to Table 3 Appendix C.
6.2 Maximizing Detection Power Through Lower Coverages
In this section, provide intuitive understanding of proposed method, well demonstration of importance considering lower coverages, when detecting population-base distribution shifts. all experiments in this section, we employed ResNet50 [19] and used a detection training set which was randomly sampled from the ImageNet validation set.
We validate the effectiveness of our CBD method (Algorithm 2) by demonstrating its performance on two distinct scenarios, the sh-sh and the shift case. In the no-shift scenario, depicted Figure 2a, randomly

---

0.3
Empiicl
01-
X
Tagal coverage
X
0.5
Couarage
66-
0.5
0.-
0.3
012
02-
0.1
0.7
0.3
0.4
055
0.6
Target coverage
Target coverage
(a) No-shift case.
(b) Shift case.
Figure 2: Visualization of our detection algorithm, Algorithm 2.
selected 1,000 sample window from ImageNet dataset that did not overlap with the detection-training set. We then tested whether this window was distributionally shifted using our method. The shift scenario, as depicted in Figure 2b, involved simulating distributional shift by randomly selecting 1,000 images from the ImageNet-O dataset. Each figure showeases the target coverages of each application, the coverage bounds provided by SGC, the empirical coverage of cach sample (for cach threshold), and the bound violations (indicated by the red circles), when they occur.
Both figures show that the target coverages and the bounds returned by SGC are essentially identical. Consider the empirical coverage of each threshold returned by SGC for cach sample. In the no-shift case, illustrated in Figure 2a, it is apparent that all bounds are tightly held; demonstrated by the fact that each empirical coverage slightly above its corresponding bound. In contrast, the shift case, depicted in Figure 2b, exhibits bound violations, indicating a noticeable distribution shift. Specifically, the bound holds at a coverage of 0.9, but violations occur at lower coverages, with the maximum violation magnitude occurring around a coverage of 0.4. This underscores the significance of using coverages lower than 1, and suggests that the detection power might lay within lower coverages.
6.3 Evaluation Metrics
In order to benehmark our results against the baselines, we adopt the following metrics to measure the effective- ness in distinguishing between in- and out-of-distribuut windows: (1) Area Under the Receiver Operating Characteristic 1 (AUROC) is threshold indeeeddddddeeedeent metric [5]. The ROC curve illustrates the relationship between the true positive rate (TPR) and the false positive rate (FPR), and the AUROC score represents the prohability that positive example will receive higher detection score than a negative example [10]. A perfect detector would achieve AUROC of 100%. (2) Area Under the Precision- Precision-Recall + (AUPR) is another preshold-indepeedden metric [32, 40]. The PR
a graph that depicts the relationship between precision (TP (TP FP)) and recall (TP (TP + FN)). AUPR-In and AUPR- Out in Table represent the area under the precision-recall curve where in-distribution and out-of diitt---iittiittion images are considered as positives, respectively. (3) False positive rate (FPR) at 95% true positive rate (TPR) L, denoted as FPR @95TPR, is performance metric that measures the FPR specific TPR threshold of 95%. This metric is calculated by finding the FPR when the TPR is 95%. (4) Detection Error J. is the probability misclassification when TPR fixed at 95%. It's a weighted average of FPR and complement of TPR, given by P. = 0.5(1 TPR) - 0..5 PR. Assuming equal probability of positive and negative examples in the test set. We note that 1 indicates larger value is better, and indicates lower values is better.
6.4 Experimental Results
In this section we demonstrate the effectiveness of our CBD method, as well as the considered baselines. To ensure fair comparison, mentioned in Section 6.1 we utilize the ResNet50, MobileNetV3-S, and ViT-T architectures, which pretrained NetgeNet and their open-sourced code appear at timm [45]. We provide code for reproducing our experiments".
Table 2 presents a comprehensive summary our main results, which clearly demonstrate that CBD outperforms all baseline methods in the majority of cases (combinations of model architecture, window size, and metrics considered), thus providing a clear indication of the effectiveness of our approach. Our method demonstrates the highest effectiveness in the low mid window size regime. Specifically. for window sizes of 50 samples,

---

our method outperforms all baselines across all architectures, with statistical significance for all considered metrics, by large margin. This observation is true for window sizes of 100 samples well, except for the MobileNet architecture, where KS-Softmax shows slightly better performance in the metrics of Detection Error and FPR @95TPR. The second-best performing method overall appears to be KS-Softmax (consistent with the findings of [37]), which seems to be particularly effective in large window sizes, such as 500 or more. CBD stands out for its consistent performance across different architectures. In particular, AUROC score of over 90% across all architectures tested when using window size of 50++, while the second best performing method (KS- Kof-ootta,,, fails to achieve such score even with window size 100 samples, when using the ResNet50 architecture.
method achieves an
It is evident from Table 2. that as far as population population-based detection tasks are concerned, neither of the single- instance baselines (SR and Entropy) offers an effective solution. These baselines show inconsistent performance across the various architectures considered. For instance, when ResNer50 is used over window size of 1,000 samples, the baselines scarcely achieve a score of 90% for the grreshold-independen metrics (AUROC, AUPR-In II, and AU,,-Out), while other methods achieve near-perfect scores. Morcover, even in the low sample regime (e.g., window size of 10), these basclines fail to demonstrate any superiority over population- methods.
Finally, based on our experiments, ResNet50 appears to he the best model for achieving low Detection Error and FPR @PR@95TPR; and a large window size is essential for achieving these results. In particular, our method and KS-Sofimax both produced impressive outcomes, with Delection Error and [PR@95TPP scores under 0.5 and 1, respectively, when window size of 1,000 samples was employed. Moreover, we observe that when small window sizes are desired. ViT-T is the best architecture choice. In particular, our method applied with ViT-T, achieves phenomenal 86%+ score in all threshold independent metrics (i.e. AUROC, AUPR- In, AUPR-ON Out), over a window size of 10 samples, strongly out tut-prrfornnn the contenders (around 20% margin). Appendix D presents the detection performance on a representative selection of distribution shifts, analyzed individually.
Wilden
Andibecteee
Metked
MORO AAAIFR- 361 FALTR :Deaciioaione
100
200
1000
Dekalilige
15/74 T3) 26 196
06/13/7 54/00
#9/86/78/ 24/
250 75076/796-22 02/0232200 146
76/79/76/ (0) 46
MDDD
Sefteat
96 38-28-2 72
76/78777766 PM
62205/992 377F2
79/20/72/211
67J99/96/166 14/00
BSUISVESS 24
Segk- Innt
Enrrey
4R
56 24/6/55-1188 16
22/73/70/223 103
7677877//2608
78,75,73
756/66
72/78 05,
94/06/24/17//
85 85/880
BY 18/009
CHO (0kmn)
78/71/8 1622
WT 267
9PT
(97 /8
16/70/0966//
Beelowiings
02/146 107 215
17/700
(99
20 20/38/00 72/70/997 (10
64/00/95 155
N6 NNT 96 10/30
19-00 (ST) 166
M4
MMn
4r (0 (8//9630/00 776
48/00 000 37774
121722 220/4
SK
50 5010//922172 720
Burreyy
52 (2/ 26/ 722
G6/77 29/17
17/23
CBD (Oun))
80 73 92' (40/40
00:85 76:
54' 55 290 30
94/94/94 213/21
95/92 5/15
90 12:98:990 99/44
trehskingg
96 66/4/71 118//1/00/000 /M
19/
78 moy 12) 20/44
MEF
MBMU
Bebaldilgg
01, (8) 44 95
74/77 (4 26/10
93 82/16/92200 20/-40
82 02/ 48
780 /2/700 06/222 24
17.700
24L-4
5k
27.70/00200000 141
59106
45
(1)
8/330
Forreyy
21/70/9/21/41
46.07/97/14//
(6) (/007777
CRD (Oand)
89 06/ 080 /55/36
93 10-000992 (34/47
94 /03 (8F (33 22
WF (90
9F (66 (97
90 (96 96 96.4
99 (9/ 190
Table 2: Comparison of different evaluation metrics over ResNet50, MobileNetV3-s. ViT-T with the discussed baselines methods. The superscript* " to the bolded result when it is statistically significant.
best performing method is highlighted in bold; we add the
7 Concluding Remarks
We presented a novel and powerful method for the detection of distribution shifts within a given window of samples. This coverage-based detection algorithm is theoretically motivated and can be applied to any pretrained model. Due to its low computational complexity, our method, unlike typical baselines, which are order-of- magnitude slower, practicable. Our comprehensive empirical studies demonstrate that the proposed method works very well, and overall significantly outperforms the baselines on the ImageNet dataset, across number of neural architectures and a variety of distribution shifts, including adversarial examples. In addition, our coverage bound is of independent interest and allows for the creation of selective classifiers with guaranteed coverage.
Several directions for future research are left open. Although we only considered classification, our method can be extended to regression using an appropriate confidence-rate function such as the MC-dropout [12]. Extensions to other tasks, such as object detection and segmentation, would be very interesting. In our method, the information from the multiple coverage bounds was aggregated by averaging, but it is plausible that other statistics or weighted averages could provide more effective detections. Finally, an interesting open question is whether one can benefit from using single-instance instance or outlier/adversariall detection techniques combined with population- based detection techniques (as discussed here).
10

---

Acknowledgments
This research was partially supported by the Israel Science Foundation, grant No. 710/18.
References
[1] Hervé Abdi and Lynne J Williams. Principal component analysis. Wiley intendisciplinnrry reviews: computational statistics, 2(4):433 459, 2010.
[2] Ella Bingham and Heikki Mannila. Random projection in dimensionality reduction: applications image and text data. In Proceedings the seventh ACM SIGKDD international conference Knowledge discovery and data mining, pages 245-250 2001.
[3] Martin Bland and Douglas Altman. Multiple significance tests: the bonferroni method. Bmj. 310 (6973):170, 1995.
[4] Luigi Pietro Cordella, Claudio De Stefano, Francesco Tortorella, and Mario Vento, A method for improving classification reliability of multilayer perceptrons. IEEE Transactions on Neural Networks, 6(5):1140 1147, 1995.
Jesse Davis and Mark Goadrich. The relationship between precision- recall and curves. Proceedings of the 23rd international conference on Machine learning, pages 233-240, 2006.
[6] Claudio De Stefano, Carlo Sansone, and Mario Vento. reject not reject: that the question- an answer in case of neural classifiers. IEEE Transactions on Systems, Man, and Cybernetics, Part (Applications and Revievs), 30(1) :0(1):84994 2000.
[7] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: scage-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Ieee, 2009.
[8] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbom, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference on Learning Representations, 2021. URL https : h/ap:::://paaa http///ppppeeeeeee//eeee/ee/eeet www.eeiiweieeeeorruereeee net/forum? id=VicbFaNTTy.
[9] Ran El- Yaniv et al. foundations noise-free selective classification. Journal of Muchine Learning Rexearch, 11(5), 2010.
[10] Tom Fawcett. introduction to roc analysis. Pattern recognition letters, 27(8):811-874, 2006.
[11] Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan. Exploring the limits of out-of-distribution detection. Advances Neural Information Processing Systems, 34:7068-7081, 2021.
[12] Yarin Gal and Zoubin Ghahramani. Dropout a bayesian approximation: Representing model uncertainty in deep learning. international conference on machine learning. pages 1050-1059, PMLR, 2016.
[13] Ido Galil, Mohammed Dabbah, and Ran El-Yaniv. What learn from the selective prediction and uncertainty estimation performance of 523 imagenet classifiers? In The Eleventh International Conference on Learning Representations, 2023. URL https: httt::://openevvek ntt/ http//ooommddd666211.
[14] Youatan Geifman and Ran Yaniv. Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
[15] Yonatan Geifiman, Guy Uziel, Ran Yaniv. Bias-reduced uncertainty estimation for deep neural classifiers. In International Conference on Learning Representations, 2019. URL https:///penrevvier htt//forrmmddSSffff666
[16] Izhak Golan and Ran Eaniv..v. Deep anomaly detection using geometric transformations. Advances in neural information processing systems, 31, 2018.
[17] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL http:://rxivv org/ abs/ 1412.
6572.
[18] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel sao-le test. The Journal of Machine Learning Research, 13(1):723-773 2012.
11

---

[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016. doi: 10.1 110./C/R..006......
[20] Nicholas A Heard and Patrick Rubin-Delanchy. Choosing hetween methods of combining-values. Biometrika, 105(1):239-246, 2018.
[21] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distriuutin examples in neural networks. In International Conference on Learning Representations, 2017. URL https:
// //opereeviee.... //ppen/erievv.ee//forummttteteee nett:/forurr.dd-HllttIttt..
[22] Dan Hendrycks, Mantas Mazeika, and Thomas Dietterich, Deep anomaly detection with outlier exposure. In International Conference on Learning Representations, 2019. URL httpe:://ppaureviov..ee net/ forum??id-HyyxxxRRcYY.
[23] Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15262- 15271, 2021.
[24] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang. Yukun Zhu, Ruoming Pang. Vijay Vasudevan, al. Searching for mobilenetv3. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1314-1324, 2019.
[25] Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning. volume 112. Springer, 2013.
[26] John Langford and Rohert Schapire. Tutorial on practical prediction theory for classification. Journal of machine learning research, 6(3), 2005.
[27] Kimin Lee, Kibok Lec, Honglak Lec, and Jinwoo Shin. A simple unified framework for detecting out- of-distribution samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
[28] Shiyu Liang, Yixuan Li, and R. Srikant. Enhancing the reliability outtof-distributtio image detection in neural networks. In International Conference on Learning Representations, 2018. URL https: / //pp///eeee.nne//////ee wwt.::wwwweeeeeeeeneeeeeee/aaaae ---
[29] Zachary Lipton, Yu- Xiani Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pages 3122-3130, PMLR, 2018.
[30] Thomas M Loughin. systematic comparison methods for combining p-values from independent tests. Computational statistics & data analysis, 47(3):467 485, 2004.
[31] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018. URL https: httts:://pppneeeeeee //tp//////e/.eeeeee////// net wtffformmmddrrritiier
[32] Christopher Manning and Hinrich Schutze. Foundations of statistical natural language processing. MIT press, 1999.
[33] Frank J Massey Jr. The aallmogorov-sminnng test for goodness of fit. Journal of the American statistical Association, 46(253))68-78, 1951.
[34] Zachary Nado, Neil Band, Mark Collier, Josip Djolonga, Michael W Dusenberry, Sebastian Farquhar, Qixuan Feng, Angelos Filos, Marton Havasi, Rodolphe Jenatton, al. Uncertainty baselines: Benchmarks for uncertainty & robustness in deep learning. arXiv preprint arXiv:2106.0440 2021.
[35] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, and Balaji Lakshminarayanan. Detecting out-of- distribution inputs to deep generative models using typicality. arXiv preprint arXiv:1906.022 2019.
[36] Yunchen Pu, Zhe Gan, Ricardo Henao, Xin Yuan, Chunyuan Li, Andrew Stevens, and Lawrence Carin. Variational autocncoder for deep learning of images, labels and captions. Advances in neural information processing systems, 29, 2016.
[37] Stephan Rabanser, Stephan Günnemann, and Zachary I Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. Advances in Neural Information Processing Systems, 32, 2019.
[38] Jie Ren, Peter Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark Depristo, Joshua Dillon, and Balaji Lakshminarayanan. Likelihood ratios for out-of-distribtiion detection. Advances in neural information processing systems, 32, 2019.
12

---

[39] David E Rumelhart, Geoffrey E Hinton. Ronald J Williams, et al. Learning internal representations by propagation, 1985.
[40] Takaya Saito and Mare Rehmsmeier. The precision-recat plot is more informative than the moc plot when evaluating binary classifiers imbalanced datasets. PloS one, 10(3):0118432, 2015.
[41] Chandramouli Shama Sastry and Sageev Oore. Detecting out-of-distribution examples with gram matrices. In International Conference Machine Learning, pages 8491-8501. PMLR, 2020.
[42] Robert J Serfling, Approximation theorems of mathematical statistics, volume 162. John Wiley & Sons, 2009.
[43] Danica J. Sutherland, Hsiao-Y Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alex Smola, and Arthur Gretton. Generative models and model criticism via optimized maximum mean discrepancy. In International Conference on Learning Representations, 2017. URL https://oppererviate net/forum? id=HJWHIKggl.
[44] Pauli Virtanen, Ralf Gommers, Travis Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau. Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261 272, 2020.
[45] Ross Wightman. Pytorch image models. https: http::://gtttttcomoe/e 2019.
13

---

A Shift-Detection General Framework
The general framework for shift-detection can be found the following figure, Figure 3.
X sourve
Two-Samplc Test(s)
Combined Test Statistic Shift Detection
Dimensionality Reduction
X target
Figure The procedure of detecting a dataset shift using dimensionality reduction and then two-sample statistical test. The dimensionality reduction is applied to both the detection-training (source) and test (target) data, prior to being analyzed using statistical hypothesis testing. This figure taken from [37].
B Proofs
B.1
Proof for Theorem 4.2
Proof.
Define
6 ) Be, - (m, (, Sm);
Co, c(0., P).
Consider the i-th iteration of SGR over detection-trainin Sm, and recall that, 0. (y(xx), E Sm. (see Algorithm 1). Therefore, 0; is random variable (between and one), since is function of random variable (ar E Sm). Let Prs... (0. 0'} } probability that 0'.
Therefore.
Prsm. (Co, < Bo,
dd' Prsp (Co, < Ba, 10, 0'} -- Prs... (0: = 0
d0'Prs, (Car < Bor } Prsm (0, 0'}.
Given that at the i-th iteration 0, 0', and considering that Bor is derived using Lemma 4.1 (refer to Algorithm 1), we obtain,
8 K.' Prsm. {Co, < Ba.
Prsm. (Cor < Bar }
Thus,
18 Prsm (Cor Bor} Prsm (0, 0')
d0'
Prs... (0: (0;=0')
Hh Prsm (0: = =8)
(5)
Te'
The following application of the union bound completes the proof,
Prs B Co, < Bo, Σ Pre (Co, < Bo,
6.
1=1
14

---

15

---

C Exploring Model Sensitivity: Evaluating Accuracy on Shifted Datasets
In this section. we present Table 3, which displays the accuracy (when applicable) as well as the degradation from the original accuracy the ImageNet dataset, of the considered models each of the simulated shifts mentioned Section 6.1.I.
ResNet550
MovileNetV3
VIFT ImageNet Degradation
Acc.
ImageNet Degradation
Acc.
ImageNet Degradation
Acc.
FGSM 7 10
76.68%
-3.7%
62.09%
-3.15%
72.51%
-2.95%
FGSM 1-10
75.19%
-5. 19%
60.72%
-4,52%
71.49%
-3.97%.
FGSM 3-10
66.15%
-14.23%
52.09%
-13.15%
65.06%
-10.4%
FGSM 5- 10
59.23%
-21.15%
44.45%
-20.79%
58.9%
-16,56%
PGD 1-10
74.64%
-5.74%
60.63%
-4.61%
71.35%
-4.11%
GAUSSIAN 0 0.1
79.02%
-1.36%
62.82%
-2.42%
71.79%
-3.67%
GAUSSIAN 0 0.3
74.63%
-5.75%
55.06%
-10.18%
50.86%
-24.0%
GAUSSIAN 0.5
68.56%
-11.82%
42.55%
-22.69%
22.25%
-53.21%
GAUSSIAN
46.1%
-34.28%
13.82%
-51.42%
0.56%
-74.9%
700M 50%
65.53%
-14.83%
36.96%
-28.28%
46.04%
-29.42%
ZOOM 70%
74.31%
-6.07%
53.53%
-11.71%
62.69%
-12.77%
ZOOM
78.6%
-1.78%
61.28%
-3.96%
72.08%
-3.38%
ROTATION 5
76.7%
-3.68%
62.42%
-2.82%
71.27%
-4.19%
ROTATION 10"
72.4%
-7.98%
58.22%
-7.02%
67.29%
-8.17%
ROTATION 20"
68.29%
-12.09%
49.96%
-15.28%
62.38%
-13.08%
ROTATION 25'
70.08%
-10.3%
500.95%
-14.29%
60.97%
-14.49%
Table 3: Shifted dataset accuracy and comparison with ImageNet. We display the accuracy for each shifted dataset and model combination, along with the accuracy degradation when compared the original ImageNet dataset.
16

---

D Extended Empirical Results
In this section, we present a detailed analysis of our empirical findings on the ResNet50 architecture. We report the results for each window size. |Wx/E I (10, 20, 50, 100, 200, 500, 1000). and for several shift cases discussed Section 6.1.1. In particular, we show the detection performance of all the discussed methods, for the following shifts: FGSM (Table 4), ImageNet-O (Table 5), ImageNet-A A (Table 6), and the Zoom out shift, 90% (Table 7),
Window size Enteatioonrree FFRRSSTTRR
Method
AUROC 1 FAUIPR-In
AAUIR--OU
1000
Softmax
922-45/441:
M12
47/35 (66--44)) foL
G4 72/28)) (44/09
72/72//3528 73/38/17 T7
50 (07 /00/ 18/36
108: 100: 2/4
190: 100, 1000 0010
Emtealiing
54/58/ 35,444
54/044/10/
41/48/ (11/4//8/50//0 90
37/48 (45/
60/ TO, 70,590//000 (00
71/77,161/ (0110//////00
Sufhnox
96/15//1//45/
11/50//4//22
41/41/51/19//
Enthalinngs
61,55//500
57/57//90/ (997//99//8888
(56,38)
67/ (330
Single-insaacee
Eztroyy
SR
42/44) 44/ 794
$1/45/440 AUS
09/108 /23//2///22
65) (40 (03/47/ 192
40) (90)44) 46,999
(57 (9./500 (0.
58/54/01
28:
(G))
/47//43
692, (56)
60: (55) 09/77
64) 713/59/25, (35,77
(B) (20, 46/990
64/ (01/00/ 46/990
77/ 109/75//44/00
CBD (Curs)
71,64/ 75: /5/62/992
77 (2/882/75//5 25/51"
$8 (98/885 20, 14, 86: 184; 25 449
99" (99 /99
96, 86/19/ /0/////0
100; 100; 1000
Table 4: Comparison of different evaluation metrics over ResNet50 with the discussed baselines methods, over the FGSM shift with e = 0.0001. The best performing method is highlighted in bold; we add the superscript to the bolded result when it is statistically significant.
Windowe sine
Methed
AUROCT AUUR--I
AALIPR-OUE 1 Devectionttooo. 21PM099TIP
1000
Sotmaa
R0A-00y000 194
166-109 MM1/5/111
3100 T000
1990 10:10
T0U 1100-10
Endeodiis
55, 56,89/766/188
97, 197/6" (12"
50) (90/910////0 5,79
100; 100/00/0
100; 100; 100/0000
100:
100, 0/-0
100; 100:00:0
MMD
Sofins Libssdings
/97
74y755/78
700.000
100,
(10//300/700 110000000
194/190 (01) /41
100,
1000 100000000
100: 100//000000000000
Single instance
Enneps
SK
66 (66, 985 (0) 64
(63, 900 43//57
BIL BIL/433 /55/ 455--8888888 198
50/-42/555 (5/55)5) (4//00
(1//52) (15/144/000 (50
47,56) 44,4 /86
16
56,
/63//46 /95
/15
51//5L /63//48/99
54/54, /55/ 19/100
3/7 077/41/-2//
(22 55,,
(00-310
641 11/185.) (4/ 220
42/444/47 (49/1000
CRO (Chrs)
/1//0/ /01//42/ 84/89/277 18//37
(4), 90//99/00/5/88
160); 10,01
100, 1100/00000000
100, 100/00/0
100) 100; 1000/0/00
Table 5: Comparison of different evaluation metrics over ResNet50 with the discussed baselines methods, over the ImageNet-O O shift. The best performing method is highlighted in bold; we add the superscript to the bolded result when it is statistically significant.
Window slne
Method
AUROCT /AUPPIIa
/AUPR-OU Out DesocconnEaree F
1000
Sofunas
100
1000 10/O
100 18/0
N00:100::10 1100:100/00/0 1000/0/0
1800 10:10
100:
100:
1000-10000000
Frbboldlings
98,
(8,19)
100/
MMD
Emboddiins
Solmmax
100 200
300/
(.00 10/0
100/100 (00//00/100/ 100000100000 10/10
1000
100/100; 100, 10/0
T09/ 1100 10/10
B00
7100
100,00 10
140: 1148,
160: 100,00/0
3100/3000
100/
10000000
$900/100 1000/10800000 100000010
(000
10000000000000000000000000000000 00:0
Sinple instunee
kimropy
SR
100/
180/ 100,
100) 1800
1000
10/10
10/0
100) 1/61) 100/
E00,
L880: 100
90
190) 100/ 310
160:
100;
800,
10/0
11/0
100,
300,
1000 100
1000 10/10
1000: 3000 1000/00/00
800: 100: 100.000000000
1000 (1A) 10
500: (100 100000000000000
00110
500: 100: 10-00
D001: 1000 1000-0/10
CBD (Ouss)
100/ 1000
100, 1/00/ 90/9
100 10/0
100 10/10
100: 100/0000
100: 190/000
100/ 1,0
Table 6: Comparison of different evaluation metrics over ResNet50 with the discussed baselines methods, over the ImageNet-A shift. The best performing method is highlighted in bold; add the superscript* * to the bolded result when it is statistically significant.
17

---

Method
TNUPR-OOI
10
30
50
100
200
500
1000
35/300
1901
T100/
Encheläing
48,00 (130L//2//400
26 66/ 64286
(B/ 44)
40 (63/06//00000 60,96
36:44; (42
27/38: 11//9///80 (8/60) $0,990
41,998
MMD
Embollängs
Softesa
57,99 (00)445,
68:51 /90/466-05
60/64/80 190/1000
$4/68, (533//0//44 181//3
$3/557
68/677
52:57
28/41/ (5)449 49/
S1, /90/
50/153 1944-800000
18/05/344 49)
2000
73/74/60,
CHI
78, 77/00/955
69) TX, 28/70
81 75/
72/75 18/07
76/ 77,70/
98/90//4/15) 10///////0000
100 T1A0) TON,
Table 7: Comparison of different evaluation metrics over ResNet50 with the discussed baselines methods, over the Zoom out (90%) shift. The best performing method is highlighted bold; we add the superseript to the bolded result when it is statistically significant.
E
Ablation Study
this section, we conduct multiple experiments to analyze the various components our framework: all those experiments are conducted using ResNe150. We explore several typer-parameter choices, including Cargn- 8, and ky. More specifically, we consider Curget {1, 10, 1000. and à E {0.1, 0.01, 0.001, 0.0001 }. and two different CFs Ky, namely SR and catropy-bbsedd
To evaluate the performance of our detectors under varying hyper- parametrs,,,,,s, have selected a single metric that believe be the most important, namely, AUROC [13]. Additionally, since performance may vary depending window size, we display average AUROC across window sizes that we have considered our experiments. These window sizes include: {10, 20, 50, 100, 200, 500, 1000}. In Figure 4, we summarize our findings by displaying the average AUROC value function of the chosen hyper-parameters. These results presented heatmaps.
0.81
0.9
Clarpe
Clerget
0.5
0.1
601
000L
0,500L
0.1
6.11
0.001
0.0011
0.02
(a) Ki = (1 Entropy).
(b) KT = SR.
Figure 4: AUROC performance of our detector under different choices of hyper-parameters.
Figure 4a, displays our AUROC detector's performance when use Entropy-based as our CF We observe that the optimal choice of hyper-parameters is 0.01 and Curget However, increasing the value of Cunger leads more consistent and robust detector, as changes in value of do not significantly affect the detector's performance. Additionally, we note that using Curget = 1 yields relatively poor performance, indicating that single coverage choice is insufficient to capture the characteristics of the distribution represented by the sample Sn- Similar results obtained when using SR the CF, as shown in Figure 4b. These results suggest that selecting high value of Curga and low value of is the effective approach for ensuring a robust detector. Finally, the heatmaps demonstrate that Entropy- based CF outperforms (by a low margin) SR. in terms of detection performance.
resulting in the highest performance.
F Upper Coverage Bound Development and Application
this section, we discuss the complementary problem to outlined Section 4.1, which is solved by Algorithm 3: we also show its application for detecting distribution shifts, Algorithm 4. Finally, we introduce unified algorithm, Algorithm 5, for detecting distribution shifts, while accounting for both under-coverage and over-coverage, details follow.
18

---

Problem statement. For classifier J. deteccion- traiiiiinn-- sample Sm ~ pm, a confidence parameter å >> 0. and desired coveruge e² O, our goal S.. find value (which implies selection function ge). such that coveruge satisfies.
Prs... (o(0, P) > c² <.
(6)
This means that over coverage should occur with probability of most 6.
The pseudo code of the algorithm that finds the optimal coverage upper bound (with confidence SGC-UP, appears in Algorithm 3.
Algorithm 3: Selection with guaranteed coverage Upper bound (SGC-UP)
Input: train set: Sm. confidence-raie rate function: кi,, confidence parameter ō target coverage: c². Sort Sm according Ky (xt;), Dy E Sm. (and now assume w.l.o.g. that indices reflect this ordering).
3 Amin 1, Emax = m11
for i to k flog2 m do
2 = [Z2min + mmax) /
8, (2))
Calculate (0,, Sm) Solve for by (m, m (0,0, Sm); ) {see Lemma F.1)
if 6J (m, m (0,, Sm), ) 2 e* then
else 10
2mi
12
7max
end if
end for
Output: bound: (m,, m (Ox, Sm), 4), threshold: 0g.
To deduce Equation (6) we make use of Lemma F.1, which is nearly identical to Lemma 4.1.
Lemma F.I. Let P be any distribution and consider a CF threshold with a coverage of c(0, P). Let 0 < 8 < be given and let E(0, Sm.) be the empirical coverage w.r.s the set Sm. sampled i..dd. from P. Let
6 (m, a(0, Sm)) :) be the solution of the following equation:
arg min
Σ
-11-- 5o
m
6 (1
(7)
Then,
Prs... (o(0, P) > 6" (m, 6(0, Sm,) <
(8)
The following uniform convergence theorem for SGC-UP (Algorithm 3) procedure stating that all the calculated bounds are valid simultaneously with probability
least
Theorem F2. Assume S., is sampled ii.dd from P. and consider an application of Algorithm 3. For k [log, m], (m, m (O. Sm). { and 0, the values obtained in the t iteration of Algorithmm Then,
Prsm (3i: c(O,, P) by (m, m è, (0., Sm), 23 <
The proof for Theorem F.2 can be easily deduced from the proof of Theorem 4.2, given in Appendix B.1.
F.1 Application of Upper Bound Algorithm for Detecting Distribution Shifts
In this section, we demonstrate the application of Algorithm 3 for detecting shifts in distribution. Specifically, Algorithm 3 is useful in identifying distribution shifts towards 'over-confidence'" where the model exhibits excessive confidence in its predictions input data. It's important note that this scenario was not empirically observed our experiments, leading to the exclusion this section from the main body of paper.
Our ever-confidence' detection algorithm is analogous Algorithm 2. We start by applying SGC-UP to Cuager target coverages uniformly spread between the interval [0.1, 1]. excluding the coverage of 1. Each application of SGC-UP UP on the same sample S., ~ P.,. with a target coverage of ej dap produces pair: (67 6,)) which represents threshold and bound, respectively.
19

---

Define, (²"(2 1 2 b']. thus. given window of k samples from an alternative distribution, W. ~ Q" we define the of upper bound violations, V as follows,
Ciarga
V
")" (a(0 Wx) b):0)) (E(0) (o)
(9)
Cuuget
j=1
Corgg
Σ
(go0((e)) 6,:00) 8 (2,00,1
h Cuager
j=1
where obtain the last equality by using 6 = 600 Wx) = = Dap (x.) (344.
Similarly V in Equation (4), the term V denotes the magnitude of the violation, where V indicates an absence of over-confieence in the predictions.
pseudocode of our algorithm for detecting over-confidence in predictions appears in Algorithm
Algorithm 4: Goverage-Based Detection over confidence
// Fit Input Training: Sm, 8, Ky,, Cunger
Generate Crarget uniformly spread coverages e* for j = 1 to Cirguet do
6,.h .0" SGC-UP(Sm, 6, cj 152)
end for
Output Training: ((6, (),"" () Cam
// Detect
Input Detection: ((b) , (0 Sur Ng. k
10
while True do
11
Receive window Wa { Z2. ,2...., Tt Calculate 4u (see Equation (9)
13
Obtain p-value from t-test, Hu V
V
14
Poulue < then
15
Shift_ fert__dteeteedeee 4- True
Output Detection: Shift_ detected, Pvalue
17
end
end while
F.2 Unified Algorithm for Distribution Shift Detection
In this section, we introduce unified algorithm designed to detect shifts in distribution, accommodating both scenarios of over-confidence and under-confidence in predictions.
Define violations (SOV).
Corpet
SOV á V + L
bp
(6
1 UF
(b)
-((5)b))))
(10)
Cragge
A pseudocode of our unified algorithm for detecting both over and under confidence in predictions appears in Algorithm 5.
20

---

Algorithm 5: Coverage-Based Detection Unified
// Fit
Input Training: Sm, 8, Ki,, Cumes
Generate Crarget uniformly spread coverages e²
for j 1 to Curger do
67. SGC(Sm. 8, cj. k5g)
by sm 88" SSCm 6, Cj. Ki))
end
Output Training: ((6), 02)) Cuna {(b) )3
Cura
// Detect
10 Input Detection: [(6). 03)) 0,)) Cuesa ((b,"0 (f Cura Ky,, a, k
11 while True do
12
Receive window Wa = {II, ,2.....,EA. .x)
13
Calculate SOV {see Equation (10))
Obtain p-value from t-test, Hu SOV 0, H1 SOV if Pralue then
15
16
Shift_detected 4- True
17
Output Detection: Shift_deteccceeeeeee detected, Pralue
18
end
19
end while
21


Reviews:
[{"review_id": "jFETBXQPkC", "reviewer": "Reviewer_a2HS", "summary": "This paper draws attention to the problem of window-based distribution shift detection and introduces a new method for it. The method is theoretically sound and demonstrated empirically to be effective on datasets with multiple types of shifts.", "questions": "- In equation 2, what does $|m\\cdot \\hat c(\\theta, S_m)|$ intuitively stand for? Why not just add up to $m$?\n- Is this typo? line 55: \"read-world\".", "limitations": "See the weaknesses above.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is evaluated on extensive datasets with various types of shifts and outperforms selected baselines.\n- The computational complexity is impressively low. \n- Due to its lower computational complexity, the proposed method is scalable compared to the baselines.", "weaknesses": "There aren't significant weaknesses in my opinion, but several minor ones might need clarification:\n- I am concerned with the novelty of Algorithm 1, selection with guaranteed coverage, since most parts here are similar to SGRC in [1].  Is coverage the only modification here?\n- The paper set out with a window-based shift detection task, which feels like a generalization from the single-instance task to me. However, there are no results of $|W_k|=1$. Can the proposed method still outperform baselines in this case? (Authors don't have to add new experiments here).\n- The goal is to detect if there is a shift in a window $W_k$ of test data. I'd like to know how the proposed method will behave when only a portion of $W_k$ is from a different distribution.\n\n[1] \"Selective Classification for Deep Neural Networks\", 2017", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive feedback! We are glad you have found our approach to be effective and scalable. Below, we reply to more specific comments and questions.\n\n**\"I am concerned with the novelty of Algorithm 1, selection with guaranteed coverage, since most parts here are similar to SGRC in [1]. Is coverage the only modification here?\"**\n\nWe respect your comment. In relation to paper [1], coverage, rather than risk, is a major innovation of Algorithm 1. However, we wish to emphasize that SGRC, as outlined in [1], fundamentally relies on labeled data for its operation, which disqualifies it as an engine for detecting distribution shifts, where labels are unavailable. Thus, although Algorithm 1 and SGRC are syntactically similar, they are semantically completely different in the sense that they are designed for completely different use cases. By focusing on coverage, our technique offers a unique feature that isn't found in [1].\n\n**\"The paper set out with a window-based shift detection task, which feels like a generalization from the single-instance task to me. However, there are no results of $W_k=1$. Can the proposed method still outperform baselines in this case? (Authors don't have to add new experiments here).\"**\n\nWe would like to clarify that our method (nor any of the population-based baselines) supports a window size of $W_k=1$. This is primarily due to the fact that coverage is a property based on population. If we attempt to apply our method to a single sample only, the empirical coverage would be binary -- covered (signifying an empirical coverage of 1), or not covered (yielding an empirical coverage of 0).\n\n**\"The goal is to detect if there is a shift in a window of test data. I'd like to know how the proposed method will behave when only a portion of $W_k$ is from a different distribution.\"**\n\nFollowing your suggestion, we attach here results from a preliminary experiment under a nearly identical setting, which we ran in the early stages of our research and wasn't included in the paper. In this experiment, we deliberately adjusted the proportion ratio $p$ to allow a mix of OOD and ID samples within a window. The ImageNet dataset was used as in-distribution (ID) and EfficientNetB0 was chosen as the model. In Table 3 of the attached PDF file, we present results for a proportion ratio of $p=1/3$ (i.e., one-third of the window is contaminated).\n\nWe will be happy to include (and extend -- should time allow) these preliminary results in the final version of the paper if the reviewer thinks that this is important!\n\n**\"In equation 2, what does $|m\\cdot \\hat{c}(\\theta, S_m) |$ intuitively stand for? Why not just add up to $m$?\"**\n\nLet us clarify: $|m\\cdot \\hat{c}(\\theta, S_m) |$ stands for the number of samples covered if using the threshold $\\theta$; see the equation of empirical coverage, $\\hat{c}(\\theta, S_m)$ (in line 186), and the equation for $g_\\theta(x)$ (in line 183). We wish to point out, that adding up to $m$ will correspond to an empirical coverage of 1, and our method relies on the idea of using coverages lower than 1. In fact, in Section 6.2 we demonstrate the effectiveness of using coverages lower than 1. In particular, in Fig. 2 we demonstrate the bound violation by the red circles (which indicate a distribution shift), as a function of the target coverage; the largest violation occurs around a target coverage of 0.4.\n\n**\"Is this typo? line 55: \"read-world\".\"**\n\nThanks for this note. This is indeed a typo, and we will fix it to ``real-world''.\n\n"}, {"review_id": "jkqV1JumXT", "reviewer": "Reviewer_MZpo", "summary": "The authors tackle the problem of out-of-distribution detection on a stream of instances. They introduce a method for coverage-based detection (CBD) that creates bounds and thresholds for monitoring by applying a newly derived selective with guaranteed coverage algorithm and then conducts a t-test on the violation sum between a window of newly received samples and a given detection dataset. The method is then analyzed for complexity and evaluated experimentally against ImageNet with various architectures. The method scales up with the size of the detection-training set size given more favourable complexity than previous baselines.", "questions": "1. It seems that while the method scales with the size of the detection-training set, it converges with other methods as the window size increases (except with ViT-T architecture). Increasing the window size leads to a bigger jump in evaluations like Detection Error once the window size is above a certain threshold. What is the relationship between m, k with respect to out-of-distribution evaluation and is there any reason why someone might prefer to scale up the window size rather than the detection-training set and thus nullify the complexity advantages of this method?", "limitations": "1. Requiring access to the final layer of weights in the model rather than being fully black-box like some of the other methods. \n2. The authors don't highlight any particular limitations for practitioners to watch out for. Even suggestions around tuning the threshold parameters in different data settings could be helpful (or perhaps they are correct that the defaults they use are sufficient for all cases).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The case is made that at large scales of data the provided method is more practical for implementation and can match or outperform existing methods for detecting distribution shift on streams of data.\n\n2. The authors provide a wide range of data and analysis to back up their claims: \n2.1 Derivation of the SGC and CBD algorithms for estimating coverage and detecting violations.\n2.2 Lower complexity\n2.3 Experimental validation on ImageNet with various architectures and types of distribution shifts.\n2.4 Showing a walkthrough of bound and threshold identification which helps \t\n\n3. They provide a thorough explanation of their method and how it differs from existing baselines like KS and MMD based tests that are popular both in research and industry. Based on the results here I could easily see CBD replacing either of these methods in existing setups.\n", "weaknesses": "\n1. Experimental setup:Window-based methods in any task rely quite heavily on the dataset in question. It would have been great to see a more diverse set of benchmarks for out-of-distribution detection if they could be modified to the given problem statement. E.g. Wilds (Koh et. al., 2021) That being said I appreciate the various shifts applied to test on different kinds of distribution shifts.\n\n2. Presentation: I found Table 2 hard to parse and dense. I understand it is hard to fit in all the data but there could be some improvements.\n\n3. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive feedback and suggestions. We are glad that you believe our method could serve as a superior alternative to the baselines in distribution shift detection tasks! Below, we will address each of the points you raised.\n\n**\"Experimental setup:Window-based methods in any task rely quite heavily on the dataset in question. It would have been great to see a more diverse set of benchmarks for out-of-distribution detection if they could be modified to the given problem statement. E.g. Wilds (Koh et. al., 2021) That being said I appreciate the various shifts applied to test on different kinds of distribution shifts.\"**\n\nWe agree that the application of diverse OOD datasets, like those in Wilds (Koh et. al., 2021) could enhance our work's comprehensiveness. However, our methodology was inspired by ref. [10] in the paper, and expanded upon it, both in terms of the OOD datasets employed and the variety of models utilized.\n\n**\"Presentation: I found Table 2 hard to parse and dense. I understand it is hard to fit in all the data but there could be some improvements.\"**\n\nIndeed it is due to space constraints. we will do our best to improve its readability in the final version of the paper.\n\n**\"It seems that while the method scales with the size of the detection-training set, it converges with other methods as the window size increases (except with ViT-T architecture). Increasing the window size leads to a bigger jump in evaluations like Detection Error once the window size is above a certain threshold. What is the relationship between m, k with respect to out-of-distribution evaluation and is there any reason why someone might prefer to scale up the window size rather than the detection-training set and thus nullify the complexity advantages of this method?\"**\n\nRegarding $m$ (the detection-training set size), the ideal strategy would be to maximize it as much as possible. The reason is that, as $m$ increases, a detector captures the underlying distribution of the in-distribution (ID) data more accurately. In particular, for ``Google-Scale'' datasets (approximately a billion images), the reliability of a detector is questionable without fitting it to a sufficiently large $m$.\nRegarding the window size $k$, its selection depends on the user's specific application. However, we wish to emphasize, that the top-performing methods achieve a nearly perfect score in all metrics for sufficiently large $k$, for example, our method exhibits a score of 99+ for the metrics AUROC, AUPR-In, and AUPR-Out for $k=1000$, for all architectures considered; see Table 2 in the paper. Thus, The intriguing question, in our opinion, is which method excels for smaller $k$ values.\n\n**\"Requiring access to the final layer of weights in the model rather than being fully black-box like some of the other methods.\"**\n\nWe would like to clarify that neither our method nor the baseline methods needs access to the final layer of weights. Our approach employs only the softmax function, while the baseline methods utilize either the softmax or the embedding layer, depending on the specific baseline in question.\n\n**\"The authors don't highlight any particular limitations for practitioners to watch out for. Even suggestions around tuning the threshold parameters in different data settings could be helpful (or perhaps they are correct that the defaults they use are sufficient for all cases).\"**\n\nWe refer the reviewer to the second paragraph of the introduction section, specifically lines 33-41, where we discuss the limitations of our work. To clarify, our study's primary limitation is that we don't consider identifying single-instance out-of-distribution examples, characterizing types of distribution shifts, or addressing the complementary topic of out-of-distribution robustness.\n\n\n\n"}, {"review_id": "u4pNSPa8IX", "reviewer": "Reviewer_HyPc", "summary": "A method to detect shifts in the input distribution of deep neural-networks is presented. The method takes a window of samples as input and calculates deviation from a tight coverage generalization bound. Here, coverage is empirically defined as the fraction of input samples that are non-rejected based on a confidence function, i.e. those which are predicted with sufficiently high confidence. The method is evaluated on standard image classification datasets using various commonly used CNN architectures.", "questions": "There are questions of a few technical aspect which I'm hoping the authors can help clarify.\n\n1. It is mentioned that in reference 12, \"a risk generalization bound was developed for selective classifiers\" but that application of that would require labels, but that theirs doesn't. Given the duality between risk- and coverage-based analysis in the two papers (ref. 12 and this manuscript), can the authors provide some more details to support this statement  please?\n\n2. The bounds are calculated on a dataset of size $m$ while the test window is of a different size $k$. Should these not be matched? \n\n3. What value of $k$ is used for the visualization in Fig. 2? It would be good to understand the impact of the window-size $k$ on the curves for both the no-shift case and the shift case. Specifically, would the coverage bound and empirical coverage continue to remain nearly identical even when $k$ drops to a low value?\n\n4. Should the inequality in Step 9 of Algorithm 1 be $\\geq$ instead of $\\leq$?", "limitations": "No societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The method is well motivated and the detection metric ('sum bound violations') is defined and derived in a principled manner. Since the method is based on principles of selective classification, a by-product is a confidence threshold $\\theta$ and a corresponding selection function $g_\\theta(x)$, which are useful to have in practical situations. What is interesting is that the method does not detection a distribution-shift based on uncertainty or confidence of the input samples, but rather by the deviation of coverage from pre-calculated bounds at several target values based on these uncertainties. Similar to reference [12], the method does not rely on uncertainty values being calibrated.", "weaknesses": "1. The derivation of the main steps of the algorithm (Section 4.1) mirrors closely the derivation of the selection-based classifier in Section 3 of the paper cited as reference [12] in the manuscript. This isn't a weakness or limitation in my view, but it is worth noting the close conceptual similarities.\n\n2. What is concerning though is the rather weak experimental evaluation:\n\n    a. The authors claim that single-instance will not perform as well as their window-based method. However, the only single-instance baselines compared against are softmax response and entropy. These are rather weak baselines and there are several stronger baselines (several of which have been cited by the authors) that should have been compared against. \n\n    b. It would have been really interesting and useful to see this method applied with different types of uncertainty values apart from softmax (feature-based such as Mahalanobis, predictive uncertainty from Bayesian neural networks, etc.). That would have served as a much stronger evidence of its superiority over other methods such as KS and MMD. Admittedly, it's not possible to cover all aspects in one paper, but this would have been a rich addition in my view.\n\n    c. It is mentioned that 49000 out of 50000 samples in the imagenet validation set are used as detection training set. I am curious why use the validation data for this purpose. Why not select 49000 samples from the training set of 1 million+ images? 1000 samples to apply the shift to seems rather small. Can the authors please explain this?\n\n3. Somewhat confusing and overlapping notation. $k$ is used for $\\lceil \\log_2 m \\rceil$ in theorem 4.2 and also as size of window $W_k$. Would improve readability if different variables were used for these two different quantities.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We have addressed each of your concerns below.\n\n**\"a. The authors claim that single-instance will not perform as well as their window-based method. However, the only single-instance baselines compared against are softmax response and entropy. These are rather weak baselines and there are several stronger baselines (several of which have been cited by the authors) that should have been compared against.\"**\n\nIn fact, we have tried to address this issue in the last paragraph of the related work section. In general, it is true that including stronger single-instance baselines in our comparison would provide a more robust evaluation. However, the top-performing single-instance methods for out-of-distribution detection require extracting values from each layer in the network [24,25], performing gradient calculations [1], and other costly (time-wise) operations. Therefore, from a practical standpoint, when applied to windows, these methods can significantly grow in complexity, and are non-efficient for the task we consider in this paper; in particular, given the time and space efficiency of our method (see Fig. 1 in the paper). Nevertheless, despite previous works (for example ref. [9,10] in the paper) excluding single-instance methods, we included some.\n\n**\"b. It would have been really interesting and useful to see this method applied with different types of uncertainty values apart from softmax (feature-based such as Mahalanobis, predictive uncertainty from Bayesian neural networks, etc.). That would have served as a much stronger evidence of its superiority over other methods such as KS and MMD. Admittedly, it's not possible to cover all aspects in one paper, but this would have been a rich addition in my view.\"**\n\nWe understand your perspective. We Indeed focused on specific uncertainty estimators, and we believe that this serves as a good example to convey the strength of our method. We consider feature-based uncertainty estimator to be beyond the scope of this paper, although we agree that this would be an interesting extension to consider for future work. We'll comment on that in the conclusion section.\n\n**\"c. It is mentioned that 49000 out of 50000 samples in the imagenet validation set are used as detection training set. I am curious why use the validation data for this purpose. Why not select 49000 samples from the training set of 1 million+ images? 1000 samples to apply the shift to seems rather small. Can the authors please explain this?\"**\n\nSure, we use the validation data to prevent bias in our detection model. In particular, if we had used data from the training set as the validation data, then the model's uncertainty estimation for this validation data, and the data that is fed to the model during test time, might not be consistent. This inconsistency is equivalent to the difference observed between train data accuracy and test data accuracy. By using a separate validation set, our method ensures that we provide more reliable results.\n\n**\"Somewhat confusing and overlapping notation. $k$ is used for $\\lceil \\log_2 m \\rceil$  in theorem 4.2 and also as size of window $W_k$. Would improve readability if different variables were used for these two different quantities.\"**\n\nThanks for the note. We will fix this in the final version.\n\n**\"It is mentioned that in reference 12, \"a risk generalization bound was developed for selective classifiers\" but that application of that would require labels, but that theirs doesn't. Given the duality between risk- and coverage-based analysis in the two papers (ref. 12 and this manuscript), can the authors provide some more details to support this statement please?\"**\n\nCertainly. The dependence of [12] on labels (their algorithm requires labeled data to operate), basically disqualifies them to be distribution shift detectors, since if labels are provided during test time, there is basically no need to detect a distribution shift. In contrast, our method provides a different approach, which doesn't need labels to operate. We will be happy to further clarify this point in the paper.\n\n**\"The bounds are calculated on a dataset of size $m$ while the test window is of a different size $k$. Should these not be matched?\"**\n\nNo, it is not necessary for the two sample sizes to be matched. This situation is analogous to applying a two-sample t-test, where it is acceptable to have different sample sizes. Therefore, in our case, having different sizes for the in-distribution dataset ($m$) and the test window ($k$) does not pose any issues.\n\n**\"What value of $k$ is used for the visualization in Fig. 2? It would be good to understand the impact of the window-size $k$ on the curves for both the no-shift case and the shift case. Specifically, would the coverage bound and empirical coverage continue to remain nearly identical even when $k$ drops to a low value?\"**\n\nThis is a good point. For Fig. 2 (in the paper) we used a window size of $k=1000$ and indeed as $k$ decreases to lower values ($k=10$), there is less ``agreement'' between the coverage bound and the empirical coverage. To address this point and provide further clarity on this issue, we have prepared additional figures: these are Figures 1a-1h in the attached PDF file. These figures show four more pairs of shift and no-shift cases, for $k=10, k=100, k=200, k=500$; we will incorporate these new figures in an Appendix.\n\n**\"Should the inequality in Step 9 of Algorithm 1 be $\\leq$ instead of $\\geq$ ?\"**\n\nAfter careful review of your comment, we confirm that the inequality should indeed remain $\\geq$. Let us explain: let's consider the i-th iteration: if $b_i$ is less than $c^*$, then we'd want to search for larger bounds. Thus, we aim to find smaller $z$ values than the current one (given that $\\kappa_f(x)$ is sorted in ascending order). Therefore, to ensure $z$ decreases in the subsequent iteration, we set $z_{max} = z$, so that the use of $\\geq$ is correct in this context.\n\n\n\n"}, {"review_id": "YcJVPrEoPt", "reviewer": "Reviewer_BTJN", "summary": "The paper presents a new method for detecting distribution shifts within a given window of samples. This coverage-based detection algorithm is theoretically motivated and can be applied to pre-trained models. The authors claim the low computational complexity of their framework, and experiments show that the framework outperforms the baselines across a variety of distribution shifts such as pixel-space adversarial examples. ", "questions": "Please address my concerns and questions in the weakness section.\n\nTo summarize, this paper is a fair contribution to the OOD research. Although the paper is well-structured with a clear storyline, given several major concerns stated in the weakness section, I will rate it as borderline accept at this stage. I will keep track of authors' responses, and consider revising the rating based on the soundness of responses.", "limitations": "The authors discussed potential improvements and future works in section 7.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written with a good storyline that formulates the proposed framework.\n2. The window setting is an attractive problem that has yet to be well explored by past works. The target models comprehensively include convolution-based and attention-based.\n3. The paper well defines the domain and assumptions of the task, making it clearly comparable to OOD frameworks.\n3. The authors motivate the framework by theoretical analysis, as well as conducting empirical experiments that demonstrate the effectiveness of the framework.\n", "weaknesses": "1. From the perspective of pixel-space adversarial attack detection, authors only evaluate the most basic baselines of FGSM and PGD. It will be constructive to the validation of the work if authors conduct additional experiments on the CW attack [1] and GAN perturbations [2].\n\n2. Authors intend to claim that the framework is effective to detect naturally (semantically) mutated images. However, the authors did not elaborate sufficient validations on the line of research for semantic adversarial examples [3]. It will be beneficial to the work if the authors have discussions on the effectiveness of the work for this line of research.\n\n3. The framework should be evaluated on scalable benchmarks proposed in recent years such as WILDS [4] V1/V2.\n\n[1] Towards Evaluating the Robustness of Neural Networks\n\n[2] Generating Adversarial Examples with Adversarial Networks\n\n[3] Semantic Adversarial Attacks: Parametric Transformations That Fool Deep Classifiers.\n\n[4] WILDS: A Benchmark of in-the-Wild Distribution Shifts", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We're pleased to note from your feedback that you recognize the importance of our research topic and believe our paper is a valuable addition to OOD research. We will try to address each of the issues you raised. We hope, that based on our responses, you would kindly reconsider your rating. Your consideration is highly appreciated!\n\n**\"1) From the perspective of pixel-space adversarial attack detection, authors only evaluate the most basic baselines of FGSM and PGD. It will be constructive to the validation of the work if authors conduct additional experiments on the CW attack [1] and GAN perturbations [2].\n2) Authors intend to claim that the framework is effective to detect naturally (semantically) mutated images. However, the authors did not elaborate sufficient validations on the line of research for semantic adversarial examples [3]. It will be beneficial to the work if the authors have discussions on the effectiveness of the work for this line of research.\"**\n\n1)+2) We appreciate the reviewer's suggestion to incorporate additional evaluation using CW attack [1] and GAN perturbations [2], and we indeed would like to include that in the paper. While it may not be feasible to run large-scale experiments within the rebuttal time frame, we would like to present a preliminary experiment we have conducted using EfficientNetB0 as the model, ImageNet as the ID (in distribution) dataset, and to your request, the CW attack as the OOD (out of distribution) dataset. These preliminary results are presented in Table 2 in the attached PDF file. In response to your request, we will be happy to include these results, extend upon them, and further discuss them in the final paper.\n\n**\"3) The framework should be evaluated on scalable benchmarks proposed in recent years such as WILDS [4] V1/V2.\"**\n\nAlthough we believe we have conveyed the strength of our method across a wide range of shifts -- such as ImageNet-O ([40]), ImageNet-A ([40]), adversarial ([38,39]), rotations, and more -- we acknowledge that this would be a nice addition to our work. Thus, should time allow, we will do our best to incorporate some results along this line in the final version of the paper. We would like to note, though, that our methodology was inspired by reference [10] and expanded upon it, both in terms of the OOD datasets employed and the variety of models utilized.\n\n**References**\n\n[10]  Failing loudly: An empirical study of methods for detecting dataset shift. NeurIPS,\n\n[38] Explaining and harnessing adversarial examples. ICLR.\n\n[39] Towards deep learning models resistant to adversarial attacks. ICLR.\n\n[40] Natural adversarial examples. CVPR.\n\n\n"}, {"review_id": "Hfb0H9d4wO", "reviewer": "Reviewer_7FwS", "summary": "The paper proposes a methodology to detect distribution shifts in windows (set) of observations for pre-trained deep learning models on computer vision tasks. The method compares the empirical coverage of a selection function to pre-determined computed bounds. During the fit stage, a guaranteed coverage selection algorithm determines C_target different bounds. During inference, the method computes the empirical coverage of the window to compute the total violations to the bounds. Finally, since V follows a normal distribution, a t-test statistic detects distribution shifts. The proposed method requires orders of magnitude less time and memory than the current SotA for large datasets. The paper presents a comprehensive comparison with SoTA methods in ImageNet.   \n", "questions": "- Which target coverage is used in the appendix when C_target=1? \n- Have authors considered using other datasets than ImageNet?", "limitations": "The paper does not properly discuss limitations (see above). ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper focuses on identifying distribution shifts, a very important problem with multiple applications.\n- The methodology is appealing and very simple.\n- The proposed method is theoretically supported.\n- The results demonstrate the method is faster and requires less memory than the current SoTA.\n- The paper is well written, and the ideas are clearly motivated.\n- The experimental setting is comprehensive and well-designed.\n- Code to replicate results is provided.", "weaknesses": "- The proposed method performs better on smaller windows (k~50), which is contrary to the main claims of the paper that the proposed method can leverage population-level information.\n- One of the main applications to motivate the problem is determining the need to retrain pre-trained models. However, the size of windows (k) used in the experiments seems small for this application, especially since large models are potentially deployed in datasets with millions of observations.\n- The performance benefits of larger samples (k~1,000) are smaller than existing methods such as KS.\n- The paper only tests the simple method where V is an average of the C_target scalars.\n- Coverage is an established metric, and it could be directly used as a distribution-shift detector for the type of application discussed in the paper. It would be interesting to compare the method with a single coverage target value to better understand the benefits of the extension proposed in the paper. Appendix E presents this ablation study but is missing some important information. For instance, what value of C^* is used when C_target=1?\n- Limitations are not properly discussed. It seems that the accuracy advantages of the method are limited to the less useful setting where k is small. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback. We are glad that you found the paper well-written and appreciated the theoretical and experimental analysis. We will try to address each of the issues you raised.\n\n**\"The proposed method performs better on smaller windows (k~50), which is contrary to the main claims of the paper that the proposed method can leverage population-level information.\"**\n\nWe see your concern. Please note that by ``population-based'', we intended to refer to any case where $k > 1$; since the literature is basically divided to methods applicable for $k=1$ (for example references [1,24,25]), and for $k>1$ (for example references [9, 10]). We will clarify this in the final version.\n\n**\"One of the main applications to motivate the problem is determining the need to retrain pre-trained models. However, the size of windows (k) used in the experiments seems small for this application, especially since large models are potentially deployed in datasets with millions of observations.\"**\n\nWe wish to clarify that the choice of $k$ as a maximum value of $1,000$ was guided by our empirical findings that most metrics get a nearly perfect score around this point (for the top-performing methods). For example, our method exhibits a score of 99+ for the metrics AUROC, AUPR-In and AUPR-Out for $k=1000$, for all architectures considered; see Table 2 in the paper. Furthermore, the detectors' performance can be observed to increase with $k$, a trend illustrated in Table 2, therefore, larger values of $k$ will just strengthen the scores.\n\n**\"Coverage is an established metric, and it could be directly used as a distribution-shift detector for the type of application discussed in the paper. It would be interesting to compare the method with a single coverage target value to better understand the benefits of the extension proposed in the paper. Appendix E presents this ablation study but is missing some important information. For instance, what value of $C^\\ast$ is used when $C_{target}=1$?\"**\n\nWe see your point. In the scenario you mentioned, where $C_{target}=1$, we have set $C^* = 0.5$. We recognize that this information is missing from Appendix E, and we will ensure to include it in the revised version of the paper. If there are any other details or clarifications needed, we will be happy to provide them.\n\n**\"Limitations are not properly discussed. It seems that the accuracy advantages of the method are limited to the less useful setting where k is small.\"**\n\nWe refer the reviewer to the second paragraph of the introduction section, specifically lines 33-41, where we discuss the limitations of our work. To clarify, our study's primary limitation is that we don't consider identifying single-instance out-of-distribution examples, characterizing types of distribution shifts, or addressing the complementary topic of out-of-distribution robustness. Regarding your comment about the value of $k$, we think that superior performance on smaller $k$ values is actually more useful; since in our observations, most metrics get a nearly perfect score when $k=1000$ (for the top-performing methods). For example, our method exhibits a score of 99+ for the metrics AUROC, AUPR-In and AUPR-Out for $k=1000$, for all architectures considered; see Table 2 in the paper.\n\n**\"Have authors considered using other datasets than ImageNet?\"**\n\nYes. While the time constraint for rebuttal prevents us from conducting new experiments, we can indeed share some findings from an experiment under nearly identical setting, conducted at the beginning stages of the paper. We used CIFAR10 as the ID dataset, and employed two pretrained models, ResNet-18 and ResNet-50. We simulated the following shifts:\n* **Rotations**: We implemented rotations with angles $\\theta \\in ${ $10, 40, 90$ }.\n* **Gaussian noise**: We introduced Gaussian noise with standard deviations $\\sigma \\in$ { $\\frac{40}{255}, \\frac{60}{255}, \\frac{80}{255}$}.\n* **OOD Datasets**: We utilized the CIFAR-100 and SVHN datasets as out-of-distribution (OOD) sets.\n* **Adversarial**: We employed the fast gradient sign method, projected gradient descent, and Carlini Wagner, commonly referred to as FGSM, PGD, and CW respectively.\n\nThe results can be found in Table 1 in the attached PDF file. Should the reviewer recommend it, we will be happy to include those results in the final paper.\n\n**References**\n\n[1] Enhancing the reliability of out-of-distribution image detection in neural networks. ICLR.\n\n[9] Detecting and correcting for label shift with black box predictors. ICML.\n\n[10] Failing loudly: An empirical study of methods for detecting dataset shift. NeurIPS.\n\n[24] Detecting out-of-distribution examples with gram matrices.ICML.\n\n[25] A simple unified framework for detecting out-of-distribution samples and adversarial attacks. NeurIPS.\n\n\n\n"}, {"review_id": "ZLCU0zq3VQ", "reviewer": "Reviewer_M7ue", "summary": "The paper proposes a window-based distribution shift detection method to detect whether the samples in the window are in-distribution (ID) or OOD. The method takes a window containing samples as input and computes a confidence score using the proposed coverage-based detection algorithm. The method is evaluated on various OOD benchmarks when imagenet is ID dataset. The results demonstrate that the proposed method is computationally more efficient than the existing methods and achieve high accuracies in majority cases. ", "questions": "Please address my concerns in the weaknesses section.", "limitations": "Limitations of the method are not discussed. \nI don't see any potential negative societal impact of the work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The idea of detecting OOD samples within a window is interesting and in a different direction than the majority of OOD detection literature.\n- The paper aims to present a theoretically supported and computationally efficient algorithm for this problem.", "weaknesses": "- Lack of intuition and convoluted description of the method: The intuition behind the proposed method is unclear. I didn't quite understand why this method should perform better than the existing ones. The theoretical part should be explained after giving some motivation for the method. \n\n- Lack of experiments: The paper presents results only when ImageNet is ID dataset. There should be experiments with different ID dataset to understand if the results generalize to other datasets.\n\n- Some experimental details are not clear: It is unclear to me how windows are created in test time. Can a window contain both ID and OOD samples? Since the method labels the whole window as OOD or ID, I wonder how the method's performance changes with different ID and OOD sample ratios within a window.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback. We have provided detailed point-to-point responses, which we believe can address your major concerns. We wonder whether you would kindly reconsider your rating based on our responses to your questions/concerns. Your consideration is highly appreciated. Many thanks!\n\n**\"Lack of intuition and convoluted description of the method: The intuition behind the proposed method is unclear. I didn't quite understand why this method should perform better than the existing ones. The theoretical part should be explained after giving some motivation for the method.\"**\n\nWe understand your concerns and thank you for pointing out areas for improvement. The essence of our method's intuition is illustrated in Figure 2,b (p.8, Section 6.2). The coverage violation peaks when its value approaches 0.4, thus providing a compelling rationale for adopting coverages under 1. Unlike our approach, the baselines do not account for coverages less than 1, and we demonstrate (in Table 2) that lower coverages strengthen distribution shift detection. As for the theoretical part, in light of your comments, we will expand our theoretical discussion in the final version of the paper. Specifically, we intend to introduce a clarifying paragraph at the beginning of sections 4.1 and 4.2 to further clarify the theoretical aspects of our method. In any case, let us explain our method in a few words: we develop a robust generalization coverage bound that holds with high probability for data sampled from the source distribution. The main idea is that if this coverage bound is violated, it likely signifies a shift in the distribution.\n\n**\"Lack of experiments: The paper presents results only when ImageNet is ID dataset. There should be experiments with different ID dataset to understand if the results generalize to other datasets.\"**\n\nWe understand your point. While we are unable to conduct a new experiment within the rebuttal time frame, we can illustrate the generalizability of our method to other datasets by presenting results from an experiment that we have conducted (in early stages of the work presented in the paper) on the CIFAR10 dataset (as the ID dataset). This experiment was done under a nearly identical setting, but we have not included it in the paper. We used two pre-trained models, ResNet-18 and ResNet-50, and implemented the following simulated shifts:\n\n* **Rotations**: with angles $\\theta \\in$ \\{$10, 40, 90$ \\}.\n* **Gaussian noise**: with STD $\\sigma \\in$ \\{ $\\frac{40}{255}, \\frac{60}{255}, \\frac{80}{255}$ \\}.\n* **OOD Datasets**: employing the CIFAR-100 dataset and the SVHN dataset as OOD datasets.\n* **Adversarial**: fast gradient sign method, projected gradient descent, and Carlini Wagner, abbreviated as FGSM, PGD, and CW respectively.\n\nThe results of this experiment can be found in Table 1 in the attached PDF file. If the reviewer suggests it, we are prepared to incorporate those results into the final paper.\n\n**\"Some experimental details are not clear: It is unclear to me how windows are created in test time. Can a window contain both ID and OOD samples? Since the method labels the whole window as OOD or ID, I wonder how the method's performance changes with different ID and OOD sample ratios within a window.\"**\n\nTo clarify this point, each window exclusively contains OOD samples, not a mix of both. Nevertheless, to directly address your point, we would like to present a preliminary experiment, which again, was conducted in the beginning stages of this work (and was not included in the paper). In this experiment, we deliberately adjusted the proportion ratio $p$ to allow a mix of OOD and ID samples within a window. The ImageNet dataset was used as ID and EfficientNetB0 was chosen as the model. As an example, we show in Table 3 in the attached PDF file, the results corresponding to a ratio of $p=1/3$, i.e., one-third of the window is contaminated with OOD data. \n\nAgain, we will be happy to include those results in the final paper.\n\n**\"Limitations of the method are not discussed.\"**\n\nWe want to refer the reviewer to lines 33-41, where we discuss the limitation of our work. Notably, we do not address single-instance OOD detection, nor do we characterize the nature of distribution shifts. To further emphasize that, we will broaden this discussion for the final version of the paper.\n\n"}, {"review_id": "TpkdBV4VFc", "reviewer": "Reviewer_UhJJ", "summary": "This paper studies the topic of model monitoring through the lenses of input distribution shift detection during test time. They propose a distribution deviation detection method based on selective prediction coverage bound violation counting. They detect data distribution shift based on windows and studies the adaptation of single-instance confidence functions for this task. They compare to baselines such as the KS test and MMD method over the softmax or penultimate layer embeddings, and two single instances baselines based on the maximum softmax response and the output entropy with a t-test. The experimental benchmark is over ImageNet with popular models and shifts based on adversarial attacks, data corruption, and semantically different data.", "questions": "\n1. The test set evaluation setup is unclear to me. The testing windows are pure out-of-distribution/corrupted data? What about mixed windows with in-distribution and ood data, which would be a more realistic setting. Have the author tried windows with a mixture of in-distribution and out-of-distribution data? I would strongly encourage adding an experiment in these lines to strengthen the experimental part of the paper.\n\n2. For the case of k=1000, is there a single window? It would mean that you compute the prediction for each method over the 15 seeds and compute the metrics in these predictions?\n\n3. Could the authors elaborate more on the claim that \"detection power might lay within lower coverages\" (line 362)? To my understanding, lower coverage simply gives a higher (more selective) threshold $\\theta$ for the CF, thus, it rejects more less confident samples.\n\n4. Could you explain in more details the novelty of Algorithm 1, Lemma 4.1 and Theorem 4.2 w.r.t references [11,12]?\n\n5. A more open ended less important question. Why do some baselines and your method decrease/oscillate performance with window size on some types of drift?\n", "limitations": "The authors do not discuss the limitations of their work in great detail. A greater effort in this direction would be appreciated. For instance, on ImageNet-O, there appears that MMD Embeddings exibits better performance. So maybe the presented method is more appropriated to some types of drifts. Also, I would argue that a variation of 5% in AUROC on the ablation of $\\delta$ and $C_{target}$ shows some sensitivity to hyperparameters.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- They present an original perspective on drift detection inspired from selective classification focused on real-world application.\n\n- The algorithm exhibits great time complexity, space complexity, and good performance.\n\n- Clean theoretical formulation of their algorithm, easy to understand.\n\n- Extensive experimental benchmark and comprehensive ablation study on the hyperparameters.\n\n- Overall, the paper is well-written and easy to follow.", "weaknesses": "- The choice of confidence-rate function might be a bottleneck of the method. Some models can exhibit over-confident predictions even to far OOD data. Relying on the softmax output as a confidence method might present a risk.\n\n- The formulation by counting the violations of the coverage bounds is interesting but it lacks motivation. It is hard to understand why computing the coverage bound would be more powerful than the t-tests with the confidence function values for each $x_k$.\n\n- Contribution (1) does not seem very useful. Why would someone desire to limit coverage without controlling risk?\n\n- In Table 1, the time complexities for MMD and KS might be inflated, as they could be improved by slightly changing the implementation. E.g., for MMD, the term with $O(dm^2)$ time complexity could be computed offline on a fit step.\n\n### Secondary observations\n\nIn line 375 the authors defined FPR@95TPR but following on in the paper they call it TNR@95TPR. Figure 4 would be easier to read if the AUROC numbers were written in the heatmap instead of the colorbars.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback! we'll address below the issues raised.\n\n**\"The choice of confidence-rate function might be..\"**\n\nWe understand your point, and in addition to Algorithm 1, we have developed a symmetric algorithm that construct an upper coverage bound (as opposed to a lower coverage bound). This algorithm can be valuable in detecting overconfidence in predictions. Although we did experiment with this bound, we found it to be rarely useful in practice, and thus decided not to include it in the paper. However, to address your concern and also for the sake of completeness, we will include an Appendix section that introduces the symmetric algorithm and provides a discussion in response to your point.\n\n**\"The formulation by counting the violations of the coverage..\"**\n\nThe motivation behind using the coverage bound stems from a complexity standpoint. By employing the bound, we can encode all essential information for detecting distribution shifts using only $C_{target}$ scalars, which in our experiments is set to $C_{target}=10$. In contrast, the 2-sample t-test would require the data from both the in-distribution (typically very large) and the window data to make a detection, making it (significantly) less efficient.\n\n**\"Contribution (1) does not seem very useful. Why would..\"**\n\nYou raise an interesting/important point. We will try to motivate this algorithm with a practical scenario. Consider a hospital where doctors have the capacity to examine only 70\\% of the available X-ray results by the next day, yet all results must be analyzed within this time-frame. Our algorithm can help in this situation by constructing a selective classifier. This classifier is assured (with a probability of $1-\\delta$) to cover the remaining 30\\% of the X-rays that the doctors are unable to reach. Importantly, our selective classifier ensures that this 30\\% is the portion upon which it would have the least risk.\n\n**\"In Table 1, the time complexities for MMD and KS might be..\"**\n\nWe see your point. Indeed, the term with $O(dm^2)$ time complexity in MMD can be computed offline during a fit step and we'll clarify this in the final version of the paper. However, we would like to point out that the remaining terms in MMD ($mk + k^2$), along with the complexity of the KS algorithm, cannot be further improved, considering they are computed based on the interaction between in-distribution (ID) and potential OOD data. In simpler terms, unlike our method whose detection complexity remains independent of the ID size ($m$), the baselines still exhibit dependence on the ID size ($m$), rendering them unsuitable for handling ``Google-Scale'' datasets.\n\n**\"In line 375 the authors defined..\"**\n\nThanks! Indeed we mean ``FPR@95TPR'', this will be fixed for the final version.\n\n**\"Figure 4 would be easier to..\"**\n\nThat's a good point. We will change this for the final version.\n\n**\"The test set evaluation setup is unclear to me..\"**\n\nTo clarify, each window exclusively contains OOD samples, not a mix of both. Nevertheless, to directly address your point, we draw your attention to a preliminary experiment, that we have conducted in the beginning stages of this work. In this experiment, we deliberately adjusted the proportion ratio $p$ to allow a mix of OOD and in-distribution (ID) samples within a window. The ImageNet dataset was used as ID and EfficientNetB0 was chosen as the model. For illustration, we present in Table 3 in the attached PDF file, the results corresponding to a ratio of $p=1/3$, i.e., one third of the window is contaminated with OOD data. We will be happy to include these preliminary results in the final version of the paper if the reviewer thinks that this is important.\n\n**\"For the case of k=1000..\"**\n\nYes.\n\n**\"Could the authors elaborate more..\"**\n\nYou are right about this claim. To further clarify, we direct your attention to Fig. 2(b) in the paper. In this figure, you can observe the margin between the violations (indicated by the red circles) and the coverage bounds (indicated by the black line). Notably, the largest margin (violation) occurs when the target coverage is around 0.4. This implies that the violations (which are indicators of a distribution shift) are more substantial when using lower coverages (lower than 1); thus, we suggested that the ``detection power might lay within lower coverages''.\n\n**\"Could you explain in more details..\"**\n\nCertainly,  our Algorithm 1, Lemma 4.1, and Theorem 4.2 function without relying on labeled data; by focusing on coverage, rather than risk. This significantly contrasts with the approaches outlined in ref. [11,12], as their reliance on labeled data disqualifies them as engines for detecting distribution shifts. Thus, although Algorithm 1 seems similar to those found in the references mentioned, they are semantically completely different in the sense that they are designed for completely different use cases. By focusing on coverage, our technique offers a unique feature that isn’t found in [11, 12].\n\n**\"A more open ended less important..\"**\n\nWe hypothesize that it stems from the number of random splits used to average the results. To note, we've utilized 15 random splits in our study, a significant number when taking into account common practice in distribution shift detection. For comparison, the study referenced as [10] (in our paper) used 5 random splits.\n\n**\"The authors do not discuss the..\"**\n\nWe appreciate this comment. In response, we will enhance Appendix D with added insights. Moreover, in relation to your concerns about limitations, please refer to lines 33-41 in the paper, where we discuss the limitations of our work. To clarify, the primary limitation of our study is that we don't consider identifying single-instance out-of-distribution examples, characterizing types of distribution shifts, or addressing out-of-distribution robustness. If the reviewer advises, we'll further emphasize these limitations in the final version.\n"}]

Author rebuttal:
We are grateful to all reviewers for their feedback and constructive comments and happy to see that in general our work was positively received (4 reviewers with a score  $\geq$ 6).

In particular, the validity and importance of our proposed method have been specifically recognized: 
* "attractive problem" (**BTJN**)
* "The idea of detecting OOD samples within a window is interesting" (**M7ue**)
* "Based on the results here I could easily see CBD replacing either of these methods in existing setups" (**MZpo**)
* "a very important problem with multiple applications" (**7FwS**)
* "The case is made that at large scales of data the provided method is more practical" (**MZpo**)

As an important part of our work, we have proposed a significant improvement in detection complexity. This aspect has been positively appreciated as well: 

* "The computational complexity is impressively low" (**a2HS**)
* "more favorable complexity than previous baselines" (**MZpo**)
* "The algorithm exhibits great time complexity, space complexity, and good performance" (**UhJJ**)
* "The results demonstrate the method is faster and requires less memory than the current SoTA" (**7FwS**)
* "Due to its lower computational complexity, the proposed method is scalable compared to the baselines" (**a2HS**)

Finally, we were also very happy to notice that the reviewers have found our experimental setting to be "comprehensive and well-designed" (**7FwS**), `"The proposed method is evaluated on extensive datasets with various types of shifts and outperforms selected baselines" (**a2HS**), and that the paper is "well written" (**BTJN**, **7FwS**), "easy to follow" (**UhJJ**), and "well motivated" (**HyPc**).

For the final version of our paper, we will take into consideration all the comments, suggestions, and other feedback provided by the reviewers. In particular, as requested by **BTJN**, we present new results over the CW attack as the out-of-distribution (OOD) dataset, see Table 2 in the attached PDF file. Furthermore, reviewers **M7ue**, **UhJJ** suggest that an experiment with windows containing a mix of both in-distribution and out-of-distribution samples will strengthen the paper. Thus, we also present a preliminary experiment along this line in the attached PDF file, see Table 3. In addition, to the specific request of reviewer **HyPc**, we show the new Figure 1 in the attached PDF file, which effectively illustrates the shift/no-shift scenarios for values of $k$ other than the specified value of $k=1000$. 
Finally, in response to reviewers **M7ue** and **7FwS** requests to verify the generalizability of our method to other in-distribution datasets, we've also included preliminary results that confirm this issue. These results, which use CIFAR10 as the in-distribution dataset, can be found in Table 1 of the attached PDF file.

Next, we provide responses to each reviewer so as to address their comments in detail and answer their specific questions.



Meta-review: All reviewers voted for accept. After discussion, we agree that this work merits a NeurIPS acceptance.
Decision: Accept (poster)