Tracking the risk of a deployed model and detecting harmful distribution shifts
Authors: Aleksandr Podkopaev
Aaditya Ramdas
Venue: ICLR 2022 Poster (2022)
Keywords: Distribution shift
sequential testing

Abstract: When deployed in the real world, machine learning models inevitably encounter changes in the data distribution, and certain---but not all---distribution shifts could result in significant performance degradation. In practice, it may make sense to ignore benign shifts, under which the performance of a deployed model does not degrade substantially, making interventions by a human expert (or model retraining) unnecessary.  While several works have developed tests for distribution shifts, these typically either use non-sequential methods, or detect arbitrary shifts (benign or harmful), or both. We argue that a sensible method for firing off a warning has to both (a) detect harmful shifts while ignoring benign ones, and (b) allow continuous monitoring of model performance without increasing the false alarm rate. In this work, we design simple sequential tools for testing if the difference between source (training) and target (test) distributions leads to a significant increase in a risk function of interest, like accuracy or calibration. Recent advances in constructing time-uniform confidence sequences allow efficient aggregation of statistical evidence accumulated during the tracking process. The designed framework is applicable in settings where (some) true labels are revealed after the prediction is performed, or when batches of labels become available in a delayed fashion. We demonstrate the efficacy of the proposed framework through an extensive empirical study on a collection of simulated and real datasets.

Published as a conference paper at ICLR 2022
TRACKING THE RISK OF A DEPLOYED MODEL AND DETECTING HARMFUL DISTRIBUTION SHIFTS
Aleksandr Podkopaev Aaditya Ramdas
Department of Statistics & Data Science!
Machine Learning Department
Camegie Mellon University
(podkopaev, aramdas J (cmu. edu
ABSTRACT
When deployed in the real world, machine learning models inevitably encounter changes in the data distribution, and certain -ut not all- distribution shifts could result in significant performance degradation. In practice, it may make sense ignore benign shifts, under which the performance of a deployed model does not degrade substantially, making interventions by human expert (or model retrain- ing) unnecessary. While several works have developed tests for distribution shifts, these typically either use non-sequential methods, detect arbitrary shifts (benign or harmful), or both. We argue that a sensible method for firing off a warning has both (a) detect harmful shifts while ignoring benign ones, and (b) allow contin- uous monitoring of model performance without increasing the false alarm rate. In this work, we design simple sequential tools for testing the difference between source (training) and target (test) distributions leads to significant increase in a risk function of interest, like accuracy or calibration. Recent advances in con- structing time-uniform confidence sequences allow efficient aggregation of statis- tical evidence accumulated during the tracking process. The designed framework is applicable in settings where (some) true labels are revealed after the prediction is performed, or when batches of labels become available in a delayed fashion. We demonstrate the efficacy of the proposed framework through an extensive em- pirical study on a collection of simulated and real datasets.
INTRODUCTION
Developing a machine learning system usually involves data splitting where one of the labeled folds is used to assess its generalization properties. Under the assumption that the incoming test in- stances (target) are sampled independently from the same underlying distribution as the training data (source), estimators of various performance metrics, such as accuracy or calibration, are accurate. However, a model deployed in the real world inevitably encounters variability in the input distri- bution, a phenomenon referred as dataset shift; see the book by Quiioner-Candela et al. (2009) Commonly studied settings include covariate shift (Shimodaira] 2000) and label shift (Saerens et al., 2002). While testing whether distribution shift present has been studied both in offline (Rabanser et al. 2019; Gretton et al. 2012 Hu& & Lei 2020) and online (Vovk et al. 22055] Vovk [020 (021)) settings, natural question is whether an intervention required once there evidence that a shift has occurred.
trustworthy machine learning system has be supplemented with set of tools designed to raise alarms whenever critical changes to the environment take place. Vovk et al. (202T) propose retrain- ing once an i.i.d. assumption becomes violated and design corresponding online testing protocols. However, naively testing for the presence of distribution shift is not fully practical since it does not take into account the malignancy of a shift (Rabanser et al. 2019). To elaborate, users are typically interested in how model performs according to certain prespecified metrics. In benign scenarios, distribution shifts could be present but may not significantly affect model performance. Raising unnecessary alarms might then lead to delays and a substantial increase in the cost of model de- ployment. The recent approach by Vovk et al. (202T) based on conformal test martingales is highly dependent on the choice of conformity score. In general, the methodology raises alarm whenever

---

Published as a conference paper at ICLR 2022
deviation from i.dd is detected, which does not necessarily imply that the deviation is harmful (see Appendix A.2).
Cbes Clas lange Class source Class
Cowe eoarce
Clss Gege
Cooe
Lages
44
100
64 45 8.5 14
(a)
(b)
Figure 1: Samples from the source and the target (hatched) distributions under benign (a) covariate
and (b) label shifts. (a) X ~ (0, 1] x [0, 1J) on the source and X; ~ Beta(1, = 1,2 on the target. Labels satisfy: P (Y = 11 X
= P (xf + x + E 2 1/4) where & ~ NO, 0.01).
(b) Marginal probability of class I changes from पं = 0.7 on the source to .ं = 0.3 on the target.
Covariates satisfy: X Y = y (2g, where μ40 (-2, 0) T, j = (2, 0) T. In both cases,
model which separates well data from the source will generalize well to the target.
In some cases, it is possible to handle structured shifts in post-hoc fashion without performing expensive actions, such as model retraining. One example arises within the context of distribution- free uncertainty quantification where the goal is to supplement predictions of a model with measure of uncertainty valid under minimal assumptions. Recent works (Tibshirani et al,, (2099) Gupta et al. 2020 Podkopaev & Ramdas 2021) show how to adapt related procedures for handling covariate and label shifts without labeled data from the target. However, both aforementioned shifts impose restrictive assumptions on the possible changes in the underlying probability distribution, assuming either that P(X) changes but (X) stays unchanged (covariate shift assumption), or that P(Y) changes but P(X stays unchanged (label shift assumption).
Thinking of distribution shifts only in terms of covariate or label shifts has two drawbacks: such (unverifiable) assumptions often may be unrealistic, and even they were plausible, such shifts may be benign and thus could be ignored. To elaborate on the first point, it is evident that while distribution shifts constantly occur in practice, they may generally have a more complex nature. In medical diagnosis, P(Y) and P(X y) could describe the prevalence of certain diseases in the population and symptoms corresponding to disease y. One might reasonably expect not only the former to change over time (say during flu season or epidemics) but also the latter (due to potential mutations and eaftiall drugs/vaccines), thus violating both the covariate and label shift assumptions. Regarding the second point, model capable of separating classes sufficiently well on the source distribution can sometimes generalize well to the target. We illustrate such benign covariate and label shifts on Figures Ta and respectively. We argue that the critical distinction- from the point of view on raising alarms should be built between harmful and benign shifts, and not between covariate and label shifts.
A related question is whether labeled data from one distribution can be used for training a model in way that it generalizes well to another distribution where it hard obtain labeled examples. apportance-weigheee risk minimization can yield models with good generalization properties on the target domain, but the corresponding statistical guarantees typically become vacuous if the impor- tance weights are unbounded, which happens when the source distribution's 's support fails to cover the target support. Adversarial training schemes (Ganin et al., 2016) 6 Wu et al.) (019) for deep learn- ing models often yicld models with reasonable performance some types of distribution shifts, but some unanticipated shifts could still degrade performance. This paper does not deal with how to
train a model if a particular type of shift is anticipated; it answers the question of when one should consider retraining (or re-evalle revelluatingg) currently deployed model.
We argue for triggering warning once the non-regularitie in the data generating distribution lead to a statistically significant increase in a user- sper-speeiiee risk metric. We design tools for nonparametric sequential testing for an unfavorable change in chosen risk function of any black-box model. The
2

---

Published as a conference paper at ICLR 2022
procedure can be deployed in settings where (some) true target labels can be obtained, immediately after prediction or in a delayed fashion.
During the preparation of our paper, we noticed very recent preprint (Kamulete 202 on broadly the same topic. While they also advise against testing naively for the presence of a shift, their ap- proach is different from ours (a) it is based on measuring the malignancy of a shift based on outlier scores (while we suggest measuring malignancy via a drop in test accuracy or another pre- specified loss), and arguably more importantly (b) their procedure is non-sequential (it is designed to be performed once, e.g, at the end of the year, and cannot be continuously monitored, but ours is designed to flag alarms any moment when a harmful shift is detected), Adapting fixed-time test- ing to the sequential settings requires performing corrections for multiple testing: if the correction not performed, the procedure is no longer valid, but if naively performed, the procedure becomes too conservative, due to the dependence among the tests being ignored (see Appendix A.I). We re- duce the testing problem to performing sequential estimation that allows us accumulate evidence over time, without throwing away any data or the necessity of performing explicit corrections for multiple testing; these are implicitly handled efficiently by the martingale methods that underpin the sequential estimation procedures (Howard et al. 2021 Waudby-Smith & Ramdas 2021
In summary, the main contributions of this work are:
1. We deviate from the literature on detecting covariate label shifts and instead focus on differentiating harmful and benign shifts. We pose the latter problem as a nonparametric sequential hypothesis test, and differentiate between malignant and benign shifts by measuring changes in user-specified risk metric.
2. We utilize recent progress in sequential estimation to develop tests that provably control the false alarm rate despite the multiple testing issues caused by continuously monitoring the deployed model (Section (.2). and without constraining the form of allowed distribution shifts. For example,
do not require the target data to itself be i..d;; our methods are provably valid even if the target distribution is itself shifting or drifting over time.
3. We evaluate the framework on both simulated (Section 3.1 and real data (Section 3.2). illustrating its promising empirical performance. In addition to traditional losses, we also study several generalizations of the Brier score (Brier 1950) to multiclass classification.
2 SEQUENTIAL TESTING FOR A SIGNIFICANT RISK INCREASE
Let X' and y denote the covariate and label spaces respectively. Consider predictors f X' D. Let ((:--) be the loss function chosen to be monitored, with R(J) = E (X(s(X), Y)] denoting the corresponding expected loss, called the risk of f.
We assume from here onwards that é is bounded, which is the only restriction made. This is needed to quantify how far the empirical target risk from the true target risk without making assumptions on P(X.Y). This is not restriction of the current paper only, but appears broadly in statistical learning theory (or the study of concentration inequalities): one picks an unbounded loss function canction-say the logarithmic loss-which can take on infinite values, then it is impossible to say how far the true and empirical risks are without further assumptions, for example that the distribution of P(Y (X) is light tailed. We prefer not to make such assumptions in this paper, keeping it as assumption-light as possible and thus generally applicable in various domains. The restriction to bounded losses is not heavy since examples abound in the machine learning literature; some examples in Appendix B Remark 1. For classification, sometimes one does not predict single label, but distribution over labels. In that case the range of f would be A This poses issue, and it is common to bounded loss functions and risks such as the Brier score, as exemplified
Section 3 On a different note, for regression, the loss (like squared error) is bounded only if the observations arc. This is reasonable in some contexts (predicting rain or snow) but possibly not in others (financial losses).
2.1 CASTING THE DETECTION OF RISK INCREASE AS SEQUENTIAL HYPOTHESIS TEST
We aim to trigger a warning whenever the risk the target domain exceeds the risk the source by a nog-nggligible amount specified in advance. For example, alerting could happen once it is possible conclude with certain confidence that the accuracy has decreased by 10%. Shifts that
3

---

Published as a conference paper at ICLR 2022
lead to a decrease an insignificant increase in the risk are then treated as benign. Formally, aim to construct a sequential test for the following pair of hypotheses:
Ho: RT(f) S Rs(f) + Eml.
H1 Rr(f)= > Rs(f) + Etol+
(1)
where Eual 2 is an acceptable tolerance level, and Rs(f) and (f) stand for the risk of f on the source and target domains respectively. Assume that one observes sequence of data points Z1, Zz..... At each time point i, a sequential test takes the first elements of this sequence and output either 0 (continue) satisfies the property that if the null Hy is true, then the probability that the test ever outputs a and stops (false alarm) is at most 6. In our context, this means that if distribution shift is benign, then with high probability, the test will never output a and stop, and thus runs forever. Formally, level-f sequential test & defined
1 (reject the null and stop). The resulting sequence of Os and 1s
mapping U nnd -> {0, must satisfy: I Pr, (3V 2 1 & ((Z,, 2.) 1) S 8. Note that the sequential nature of a test is critical here as we aim to develop a framework capable of continuously updating inference as data from the target is collected, making it suitable for many practical scenarios. We distinguish between two important settings when we assume that the target data either satisfies (a) an i.i.d. assumption (under the same or different distribution as the source) or (b) only an independence assumption. While the i.idd. assumption may be arguably reasonable on the source, it is usually less realistic on the target, since in practice, one may expect the distribution to drift slowly in non-i.id. fashion instead of shifting sharply but staying i.i.d.. Under setting (b), the quantity of interest on the target domain is the running risk:
( B (E(()))))))) 121, 1,
where the expected value is taken with respect to the joint distribution of (X,, Y;),, possibly different for each test point i. The goal transforms into designing a test for the following pair hypotheses:
Ho: R (f) S Rs(f) + Etol, Vt 2 1, vs. H1: 2 1: R (f) > Rs(f) + Stol- (2)
When considering other notions of risk beyond the misclassification error, one could also be inter- ested in relative changes in the risk, and thus sequential test for the following pair of hypotheses:
Hy: (f( S (1 + Evol Rs(f),
H Rr(f) (1+ Rs
(3)
The proposed framework handles all of the aforementioned settings as we discuss next. The most classical approach for sequential testing is the sequential probability ratio test (SPRT) due to Wald (1945). However, it can only be applied, even for a point null and a point alternative, when the rel- evant underlying distributions
known. While extensions of the SPRT exist the composite null and alternative (our setting above), these also require knowledge of the distributions of the test statis- ties (e.g., empirical risk) under the null and alternative, and being able to maximize the likelihood. Clearly, we make no distributional assumptions and so we require nonparametric approach. We perform sequential testing via the dual problem nonparametric sequential estimation, a problem for which there has been much recent progress to draw from.
2.2 SEQUENTIAL TESTING VIA SEQUENTIAL ESTIMATION
When addressing particular prediction problem, the true risk on neither the source nor the target domains is known. Performance of model on the source domain is usually assessed through a labeled holdout source sample of fixed size ns: {(x,, )- We can write:
Rs(f) + Ecol Ro(f) + (Rs(f) Rs(f)) Etol:
where Rs(s) = (E E(f())), / For any fixed tolerance level ōs E (0, 1), clas- sic concentration results can be used to obtain an upper confidence bound Sappr on the difference Rs(f) - Rs(f), and thus to conclude that with probability at least 1 5gg
Rs( + Eval < Üz(f) + Ecol. where Üs(f) = =R((f) + Eappr.
(4)
For example, by Hoeffding's inequality, n, = 2 points suffice for the above guarantee, but that bound can be quite loose when the individual losses (x()), Y.) have low variance. In such set- tings, recent arriacee-adaptive confidence bounds (Waudby-Smith & Ramdas 2021 Howard al.)
4

---

Published as a conference paper at ICLR 2022
2021) are tighter. It translates to increase in the power of the framework, allowing for detecting harmful shifts much earlier, while still controlling the false alarm rate at prespecified level.
In contrast, the estimator of the target risk has to be updated as losses test instances observed. While the classic concentration results require specifying in advance the size of a sample used for es- timation, time-uniform confidence sequences retain validity under adaptive data collection settings. For any chosen 67 E (0, 1), those yield a time-uniform lower confidence bound on Ry(
P P ( < 1 (F) S gr,
where D7 (f) is the bound constructed after processing i test points. We typically set dg 87 6/2, where refers to the desired type error. Under the independence assumption (equation 2), the form of the drift in the distribution of the data is allowed to change with time. From the technical per- spective, the difference with the i.i.d. setting is given by the applicability of particular concentration results. While the hetting-hased approach of Waudby-Smith & Ramdas (202T) necessitates assum- ing that random variables share a common mean, proceeding with the conjugate-mixture empirical- Bernstein bounds (Howard et al., 2021) allows to lift the common-mean assumption and handle a time-varying mean. We summarize the testing protocol in Algorithm [ and refer the reader to Appendix for review of the concentration results used in this work. One can easily adapt the framework to proceed with fixed, absolute threshold on the risk, rather than a relative threshold Rf( + Ewl, e-g., we can raise warning once accuracy drops below 80,, rather than 5% below the training accuracy.
Algorithm Sequential testing for an absolute increase in the risk.
Input: Predictor f. loss É, tolerance level Ewl, sample from the source {(X,, Y:)
1: procedure
2: Compute the upper confidence bound on the source risk (f):):
3: for t = 1, do
Compute the lower confidence bound on the target risk D (f);
4:
5: if (T))(() (f) > Üs(() + Emi then
6:
Reject Hn (equation D and fire off a warning.
Testing for a relative increase in the risk is performed by replacing the line 5 the Algorithm by the condition T (f) > (1 (()))s((J). For both cases, the proposed test controls type error as formally stated next. The proof is presented in Appendix[D]
Proposition Fix any E (0, 1). Let 8s, dr E 10 be chosen in a way such that 8s + 8r = 6. Let D.G) (f) define time- unne-unifomm lower confidence bound on RT (f) at level 8n after processing t data points (t 2 1), and let (f( define an upper confidence bound on Rs(f) at level 8g. Then:
PHo E 1: 2 (f) > Üs(s) + ExN 5
(5)
PHE 3121 T
(1 +(mm) 56
that is, the procedure described in Algorüthm 0 controls the type I error for testing the hypotheses Ho (equation I and equation 2 and Hi (equation 3
Remark 2. Both the testing protocol (Algorithm D and the corresponding guarantee (Proposition T stated in a form which requires the lower bound on the target risk to be recomputed after pro- cessing each test point. More generally, test data could be processed in minibatches of size m 2 1. Remark 3. Type error guarantee in equation 5 holds under continuous monitoring. This goes beyond standard fixed-time guarantees, for which type error controlled only when the sample size is fixed in advance, and not under continuous monitoring. Define stopping time of a sequential test in Algorithm
N(6) = inf ( 1: > Üs(ʃ) + Eial
Then the guarantee in equation 5 can be restated as: PHo (N < oc) S 6, that is the probability of ever raising false alarm is at most 8.
5

---

Published as a conference paper at ICLR 2022
From sequential testing to changepoint detection. A valid sequential test can be transformed into a changepoint detection procedure with certain guarantees (Lorden 1971). The key character- istics of changepoint detection procedures average run length (ARL), average time to false alarm, and average detection delay (ADD). One way to convert a sequential test into a detection procedure is by running separate test starting each time point t 1, 1,2..... and claiming change whenever the first one of the tests rejects the null. Subsequently. these tests yield a sequence of stopping variables Ni N2((),... ... The corresponding stopping time is defined as:
N (6)
inf (N&(6) + (k- 1)) 1=1,2...
Lorden (1711) established lower bound on the (worst-case) ARL of such changepoint detection procedure the form: EH, [6)) 2 1/6. The (worst-case) average detection delay defined as:
(6) sup ess sup E. (6) - (m - 1))+ ()...)....... (I - m21
where En denotes expectation under Pm. the distribution of sequence (X1, Y1), (X1, Y!)... under which (X Y") is the first term from shifted distribution.
3 EXPERIMENTS
In Section we analyze the performance of the testing procedure on collection of simulated datasets. First, we consider settings where the i.i.d. assumption on the target holds, and then relax it the independence assumption. In Section 3.2 we evaluate the framework real data. We consider classification problems with different metrics of interest including misclassification loss, several versions of the Brier score and miscoverage loss for set-valued predictors. Due to space limitations, we refer the reader to Appendix B for detailed review of the considered loss functions.
3.1 SIMULATED DATA
Tracking the risk under the i.idd assumption. Here we induce label shift on the target domain and emulate a setting where it noticeably harms the accuracy of predictor by modifying the setup from Section I through updating the class centers to No (-1, 0) and μl = (1,0) .akiing the classes largely overlap. The (oracle) oayesaoptimal predictor the source domain is:
कं up((::: 14, I2)
f*xx)
(6)
To
(p(:;; /0, 12) + क 11, I2)
where cp(:; μ4, I2) denotes the probability density function a Gaussian random vector with mean Mg. i {0, } and an identity covariate matrix. Let é be the 0-1 loss, and thus the misclassification risk RT( on the target is:
1
Pr (X) # Y) = P
x (Ju -Mo) Mo) log
(112
11 21 Y ===] 1) ..
+ x TT - Ho) 2 log
+
1 (llez l1
||
IY 0) T/-
For three values of TT. the source marginal probability of class 1, we illustrate how label shift affects the misclassification risk of the Bayes-optimal predictor on Figure 2a noting that is linear nf.. Importantly, whether label shift hurts helps depends on the value of ...
We fix F 0.25 and use the corresponding Bayes-optimal rule. On Figure 2b we compare upper confidence bounds on the source risk due to different concentration results, against the size of the source holdout set. Variance-adaptive upper confidence bounds-pree praudds-prdiitally--nee mixed empirical- Bernstein (PM-EB) and betting-based (see Appendix [E] much tighter than the non-adaptive Hoeffding's 's bound. Going forward, we use a source holdout set of 1000 points to compute upper confidence bound on the source risk, where Epprr from equation is around 0.025.
Next, we fix Enol = 0.05, i.c., we treat a 5% drop in accuracy as significant. For 20 values of of. evenly spaced in the interval 10.1, 0.9), we sample 40 batches of 50 data points from the target

---

Published as a conference paper at ICLR 2022
The Baye-astimnl rak
Thue Bays risk the seante
0.25
Upper confidence bounds via: Fortting
Medboolfaate nec the
1:25
0.5
1.20
Berrng
PM6-8
379
0.38
3138
315
Marginal probabiliy barget
Number samples the
300
(a)
(b)
Figure 2: (a) The misclassification risk the target of the Bayes-optimal predictors for three values of π.. Notice that label shift does not necessarily lead to an increase the risk. (b) Upper confidence bounds (f) on the misclassification risk on the source obtained via several possible concentration results. For each sample size, the results are aggregated over 1000 random data draws. The variance- adaptive confidence bounds (predictably-min -mixedd empirical-BR Bernsssein and the betting-basee one) are much tighter when compared against the non-adaptive one.
distribution. On Figure 3a we track the proportion of null rejections after repeating the process 250 times. Note that here stronger label shift hurts accuracy more. On Figure [bb we illustrate average size of sample from the target needed to reject the null. The results confirm that tighter bounds yield better detection procedures, with the most powerful test utilizing the betting-based bounds "Waudb--Smile & Ramdas 2021). A similar analysis for the Brier score (Brier) 1950)
target metric is presented in Appendix F We further study the performance the framework under the covariate shift setting (Appendix
Degpotion relecions
Beriign ngs
Hamrid settings
mul
PMA-B
Hoolding's CB
Hoofisin's CB
80
PM C8
Beting
Marginll polshilty dass targer
Marginal probublity
of
(a)
(b)
Figure 3: (a) Proportion of null rejections when testing for an increase in the misclassification risk after processing 2000 samples from a shifted distribution. The vertical dashed yellow line separates null (benign) and alternative (harmful) settings. Testing procedures that rely on aariance-adaptvv confidence bounds (CBs) have more power. (b) Average sample size from the target that was needed to reject the null. Tighter concentration results allow to raise an alarm after processing less samples.
Tracking beyond the i.i.d. setting (distribution drifi). Here we consider testing for an increase in the running risk (equation 2}. First, we fix ... = 0.75 and keep the data generation pipeline as before, that is, the target data are still sampled in i.i.d. fashion. We compare lower confidence bounds on the target risk studied before against the conjugate-mixture empirical-Bernseee bound (Howard et al. (022)) We note that this bound on the running mean of the random variables and has to be computed numerically. On Figure
(CM-EB)
does not have lower confidence bounds based on betting are generally tighter only for a small number of samples. Similar results hold for the Brier score a target metric (see Appendix FT.
illustrate that the
Next, we lift the i.idd. assumption by modifying the data generation pipeline: starting with 7. 0.25, we increase πT by 0.1 after sampling each 200 instances, until it reaches the value 0.85. It makes CM-EB the only valid lower bound on the running risk on the target domain. The results of running the framework for this setting are presented on Figure

---

Published as a conference paper at ICLR 2022
3.13
3:18
UCB the scaros rak
8475
LCB on the target nee via:
Bettng
PM FB
Number tomples target
Namber samples from domain
(a)
(h)
Figure 4: (a) Different lower confidence bounds (LCB) on the target risk under the i.i.d. assumption. Betting-basse LCB is only tighter than conjugate-mixture empirical-Bemsserr (CM-EB) for a small number of samples. (b) Under distribution drift, only CM-EB performs estimation of the running risk. The resulting test consistently detects harmful increase in the running risk.
3.2
REAL DATA
In deep learning, out-of-distribution robustness is often assessed based on model performance gap between the original data (used for training) and data to which various perturbations are applied. We focus on two image classification datasets with induced corruptions: MNIST-C (Mu Gilmer 2019) and CIFAR- 10-C (Krizhevsky) 2009 Hendrycks & Dietterich] (2019). We illustrate an exam- ple of clean MNIST image on Figure 5a along with its corrupted versions after applying motion blur, blur along random direction (Figure 5bj, Iranslate, affine transformation along random direction (Figure[5c) 5c), and zigzag, randomly oriented zig7ag over an image (Figure 5 For CIFAR- 10-C, consider corrupting original images by applying the fog effeet with 3 levels of severity as illustrated on the bottom row of Figure [S] For both cases, clean or corrupted test samples are passed input networks trained clean data. While corruptions still hope that they will not significantly hurt classification performance. We use the betting- -baied confidence bounds on the source and conjugate-miss mixture impirical-Bernster confidence bounds on the target domain.
visible to the human eye, one might
8
8
8
(a) Clean
(b) Motion blur
(c) Translate
(d) Zigzag
(e) Clean
(1) Fog, severity: 1
(g) severity: 3 (h) Fog, severity:
Figure 5: EExmmless of MNIST-C ((a)(d)) and CIFAR-10-C ((e)(h) images.
Tracking the risk of point predictor MNIST-C dataset. We train shallow CNN on clean MNIST data and run the framework testing whether the misclassification risk increases by 10%, feeding the network with data in batches of 50 points either from the original or shifted distributions. Details regarding the network architecture and the training process are given in Appendix G On Figure 6al we illustrate the results after running the procedure 50 times for each of the settings.
8

---

Published as a conference paper at ICLR 2022
The horizontal dashed line defines the rejection threshold that has been computed using the source data: once the lower bound on the target risk (solid lines) exceeds this value, the null hypothesis is rejected. When passing clean MNIST data input, do not observe degrading performance. Further, applying different corruptions leads to both benign and harmful shifts. While to the human eye the translate effect is arguably the least harmful one, it is the most harmful to the performance of network. Such observation is also consistent with findings of Mf & Gilmer (2019) who observe that if trained on clean MNIST data without any data augmentation, CNNs tend to fail under this corruption. We validate this observation by retraining the network several times in Appendix G
Tracking the risk of a set-valued predictor on CIFAR-IO-C dataset. For high-conseqqence settings, building accurate models only can be insufficient as it is crucial to quantify uncertainty in predictions. One way to proceed is to output set of candidate labels for each point as a prediction. The goal could be to cover the correct label of a test point with high probability (Vovk et al.) 2005) control other notions of risk (Bates et al., (02T). We follow Bates al.) (202T) who design
procedure that uses a holdout set for tuning the parameters a wrapper built on top of the original model which, under the i.i.d. assumption, is guaranteed have low risk with high probability (see Appendix G for details). Below, we build wrapper around ResNet-32 model that controls the miscoverage risk (equation [4] level 0.1 with probability least 0.95. For each run, CIFAR- 10 test set is split at random into three folds used for: (a) learning wrapper (1000 points), (b) estimating upper confidence bound on the miscoverage risk on the source (1000 points), and (c) evaluation purposes on either clean or corrupted images. We take Stal = 0.05, that is, 5% drop in coverage is treated as significant. Figure 6bb illustrates that only the most intense level of fog is consistently harmful coverage. We also consider setting lower prescribed miscoverage level (0.05) for the set-valued predictor (see Appendix GG. When larger prediction sets are produced, adding fog images becomes less harmful.
Dejetice stankitf Geff
LCB on the target die fo:
373
LCB on the Dagge dikk for.
MaccoeeFraai mnk
Dlaan
Clis
1.2
Zipreg
Transaas
2:13
Frg. levd sevrrty
Tog. led snarite
Frg. countty
3:3
365
30
Number of samples from the Sarget demain
Number of sample from the target domain
(a)
(b)
Figure 6: (a) Performance of the testing framework MNIST-C dataset. Only the translation effect is consistently harmful to the classification performance CNN trained on clean data. (b) Performance of the testing framework the fog lead to a significant degradation in performance measured by a decrease in coverage of a set-valued predictor trained on top of a model trained on clean data.
CIFAR-10-C dataset. Only the most severe version of
4 CONCLUSION
An important component of building reliable machine learning systems making them alarm user when potentially unsafe behavior is observed, instead of allowing them to fail silently. Ideally, a warning should be displayed when critical changes affecting model performance are present, e.g., a significant degradation of the target performance metrics, like accuracy or calibration. In this work, we considered one particular failure scenario of deployed models preseecce of distribution shifts. Relying solely on point estimators of the performance metrics ignores uncertainty in the evaluation, and thus fails to represent a theoretically grounded approach. We developed a set of tools for deciding whether the performance of model on the test data becomes significantly worse than the performance on the training data in a data-adaptive way. The proposed framework based on performing sequential estimation requires observing true labels for test data (possibly, in de- layed fashion). Across various types of distribution shifts considered in this work, it demonstrated promising empirical performance for differentiating between harmful and benign ones.

---

Published as a conference paper at ICLR 2022
Acknowledgements The authors thank Ian Waudby-Smith for fruitful discussions and the anony. mous ICLR 2022 reviewers for comments on an early version of this paper. The authors acknowl- edge support from NSF DMS 1916320 and ARL IoBT CRA grant. Research reported in this paper was sponsored in part by the DEVCOM Army Research Laboratory under Cooperative Agree- ment W91 1011NF-11-220199 (ARL IoBT CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Govern- ment is authorized to reproduce and distribute reprints for Govermment purposes notwithstanding any copyright notation herein.
Ethics Statement. We do not foresee any negative impacts of this work in and of itself; there may be societal impacts of the underlying classification or regression task but these are extraneous to the aims and contributions of this paper.
Reproducibility statement. In order to ensure reproducibility of the results in this paper, we in- clude the following to the supplementary materials: (a) relevant source code for all simulations that have been performed, (b) clear explanations of all data generation pipelines and preprocessing steps that have been performed, (c) complete proofs for all established theoretical results.
REFERENCES
Stephen Bates, Anastasios Nikolas Angelopoulos, Lihua Lei, Jitendra Malik, and Michael I. Jordan. Distribution-free, risk-controlling prediction sets. Journal of the ACM, 2021.
Glenn W. Brier. Verification of forecasts expressed in terms of probability. Monthly Weather Review, 1950.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario March, and Victor Lempitsky. Journal of Machine Learning Research, 2016.
training of neural networks.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola.
A kernel two-sample test. Journal of Machine Learning Research, 2012.
Chirag Gupta and Aaditya Ramdas. Top-label calibration and multiclass-to-bine reductions. In International Conference Learning Representations, 2022.
Chirag Gupta, Alcksandr Podkopaev, and Aaditya Ramdas. Distribution-Fi free binary classification: prediction sets, confidence intervals and calibration. In Advances in Neural Information Process- ing Systems, 2020.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. In International Conference on Learning Representations, 2019.
Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasject Sekhon. Time-uniform, nonpara- metric, nonasymptotic confidence sequences. The Annals of Statistics, 2021.
Xiaoyu Hu and Jing Lei. A distribution-fres test of covariate shift using conformal prediction. arXiv preprint: 2010.07 147, 2020.
Vathy M. Kamulete. Test for non-negligible adverse shifts. arXiv preprint: 2107.02990, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
G. Lorden. Procedures for reacting to a change distribution. The Annals of Mathematical Statis- fies, 1971.
Norman Mu and Justin Gilmer. MNIST-C: A robustness benchmark for computer vision. arXiv preprint: 1906.02337, 2019.
10

---

Published as a conference paper at ICLR 2022
Aleksandr Podkopaev and Aaditya Ramdas. Distribution free uncertainty quantification for classifi- cation under label shift. Conference on Uncertainty in Artificial Intellignce, 2021.
Joaquin Quionero-Candehe Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence. Dataset Shift in Machine Learning. The MIT Press, 2009.
Stephan Rabanser, Stephan Günnemann, and Zachary Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. In Advances in Neural Information Processing Systems, 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel Candès. Classification with valid and adaptive coverage. In Advances in Neural Information Processing Systems, 2020.
Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of classifier to new priori probabilities: A simple procedure. Neural Computation, 2002.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Planning and Inference, 2000.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal pre- diction under covariate shift. In Advances in Neural Information Processing Systems, 2019.
Vladimir Vovk. Testing for concept shift online. arXiv preprint: 2012.142444 2020.
Vladimir Vovk. Testing randomness online. Statistical Science, 2021.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer, 2005.
Vladimir Vovk, Ivan Petej. Ilia Nouretdinov, Ernst Ahlberg, Lars Carlsson, and Alex Gammerman. Retrain or not retrain: conformal test martingales for change-point detection. In Symposium on Conformal and Probabilistic Prediction and Applications, 2021.
Abraham Wald. Sequential tests of statistical hypotheses. The Annals of Mathematical Statisties, 1945.
Ian Waudby-Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. arXiv preprint: 2010:09686, 2021.
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton. Domain adaptation with asymmetrically-rrcasse distribution alignment. In International Conference on Machine Learn- ing, 2019.

---

Published as a conference paper at ICLR 2022
A ISSUES WITH EXISTING TESTS FOR DISTRIBUTION SHIFTS/DRIFTS
A.1 NON-SEQUENTIAL TESTS HAVE HIGHLY INFLATED FALSE ALARM RATES WHEN DEPLOYED IN SEQUENTIAL SETTINGS WITH CONTINUOUS MONITORING
In this work, we propose framework that utilizes confidence sequences (CSs), and thus allows for continuous monitoring of model performance. On the other hand, traditional (fixe--time) test- ing procedures are not valid under sequential settings, unless corrections for multiple testing are performed. First, we illustrate that deploying fixed-time detection procedures under sequential set- tings necessarily leads to raising false alarms. Then, we illustrate that naive corrections for multiple testing-withour taking advantage of the dependence between the tests-leat to losses of power of the resulting procedure.
Deploying fixed-time tests without corrections for multiple testing. Under the i.i.d. setting, our framework reduces to testing whether the means corresponding to two unknown distributions are significantly different. Here consider simplified setting: assume that one observes a sequence Z1, .z.... of bounded i..d. random variables, and the goal is to construct a lower confidence bound for the corresponding mean jr. In this case, a natural alternative to confidence sequences is lower bound obtained by invoking the Central Limit Theorem:
7. Ō
where 25 is (1 - quaantiee of the standard Gaussian random variable and 7, ã. denote the sample average and sample standard deviation respectively computed using first f instances Zi...., Ze. For the study below, we use the critical (significance) level = 0.1. We sample the data as: Ze ~ Ber(0.6), t= 2....... and consider 100 possible sample sizes, evenly spaced between 20 and 1000 on logarithmic scale. Next, we compare the CLT lower bound with the betting- betting-based based one (which underlies the framework proposed this work) under the following settings:
Fixed-time monitoring. For a given sample size I, we sample the sequence Zi,..., Ze, compute the lower bounds and check whether the true mean is covered only once. For each value of the sample size, we resample data 100 times and record the miscoverage rate, that is, the fraction of times the true mean is miscovered.
2. Continuous monitoring. Here, the lower bound recomputed once new data become available. We resample the whole data sequence Zi. Z000 1000 times, and for each value of the sample size, we track the cumulative miscoverage rate, that is, the fraction of times the true mean has been miscovered at some time up to t.
Under fixed-time monitoring (Figure 7ap, the false alarm rate is controlled at prespecified level d by both procedures. However, under continuous monitoring (Figure 7 deploying the CLT lower bound leads to raising false alarms. At the same time, the betting-bant -based lower bound controls the false alarm rate under both types of monitoring.
Deploying fixed-time tests with corrections for multiple testing. Next, we illustrate that adapt- ing fixed-time tests to sequential settings via performing corrections for multiple testing comes at the price significant power losses. Performing the Bonferroni correction requires splitting the available error budget ê among the times when testing is performed. In particular, we consider:
Power correction:
8
2
6
Polynomial correction:
8.
72
Note that the second option is preferable the terms in the decrease slower rate, thus al- lowing for a narrower sequence of intervals. Proceeding under the setup considered in the beginning of this section (data points are sampled from (er(0.))), consider scenarios:
12

---

Published as a conference paper at ICLR 2022
LCB
Betting
Betting
Sample see
Sample sze
(a)
(b)
Figure 7: False alarm rate for the CLT and betting-based lower confidence bound (LCB) under: (a) fixed-time monitoring and (b) continuous monitoring. Note that both bounds control the false alanm rate prespecified level 5 0.1 under fixed-time monitoring. However under continuous monitoring, the false alarm rate of the CLT bound quickly exceeds the critical level = 0.1. At the same time, the betting LCB successfully controls the false alarm rate.
We recompute the CLT lower bound each time batch of 25 samples is received and per- form the Bonferroni correction (utilizing both ways of splitting the error budget described in equation?? 7 We present the lower bounds on Figure Sa (the results have been aggregated over 100 data draws). Observe that:
While the sequence of intervals shrinks in size with growing number of samples under the polynomial correction, this is not the case under the power correction.
Not only the betting confidence sequence is uniformly tighter than the CLT-based over all considered sample sizes, also allows for monitoring arbitrary stopping times. Note that the CLT lower bound allows for monitoring only at certain times (marked with stars on Figure Sa).
2. For fairer comparison with the betting-base based bound, we also consider recomputing the CLT bound each time new sample is received. Since utilizing the power correction quickly Icads to numerical overflows.
utilize only the polynomial correction. We present the lower bounds on Figure 8b (the results have been aggregated over 100 data draws). While the CLT lower bound can be monitored arbitrary stopping times, it is sub- stantially lower (thus more conservative) than the betting-based.
LCB
CLT LCB Polynorial
Sotting
Betting
20
50
206 30
60
Sample
(b)
Figure 8: Adapting the CLT lower bound to continuous monitoring via performing corrections for multiple testing: (a) each time batch of 25 samples received, (b) each time a new sample received. Under both settings, the CLT- based lower bound is more conservative than the betting- based, which, in testing terminology, means that the resulting testing framework has less power.
A.2 CONFORMAL TEST MARTINGALES NOT IN GENERAL DIFFERENTIATE BETWEEN HARMFUL AND BENIGN DISTRIBUTION SHIFTS
Testing the i.i.d. assumption online can be performed using conformal test martingales (Vokk et al. 2021 Vovk 2021 2020). Below, review building blocks underlying conformal test martingale.
13

---

Published as a conference paper at ICLR 2022
1. First, one has to pick conformity score. Assigning lower score to sample indicates abnormal behavior. Vovk et al. (202I) consider the regression setting and, like us. use scores that depends on true labels: for point (I,, Mt), let denote the output of predictor on input T;. The authors propose a score of the form:
a;
3/ Del.
Note that lower scores defined in equation 8 clearly reflect degrading performance of pre- dictor (possibly due to the presence of distribution drift). Under the classification setting, we propose to consider the following conformity score:
a2 Σ fa(z)) 1 (fa()z)) (x.)) = Σ (il(=)) > (x)() (9)
which is a rescaled estimated probability mass of all the labels that are more likely than the true one (here, we assume that predictor f outputs an element of A Rescaling in equation 9 is used to ensure that this score represent the conformity score, that is, the higher the value is, the better given data point conforms. Note that if for a given data point, the true label happens to be top-ranked by predictor f. then such point receives the largest conformity score equal to one. This score is inspired by recent works in conformal classification (Romano al. 2020, Podkoppev Ramdas, 202T).
2. After processing data points, transducer transforms collection of conformity scores into a conformal p-value:
= / (1. as < anl + | (I.....m)
a.
Pn = p (().)))))
71
where u ~ Unif((O, 1)). Conformal p-values are i.i.d. uniform on 00, 1] when the data points are i..dd (or more generally, exchangeable; see (Vovk et al. (021)). Note that the design of conformal p-value P, ensures it takes small value when the conformity score On is small, that is, when abnormal behavior is being observed in a sequence.
3. A betting martingale is used to gamble again the null hypothesis that a sequence random variables is distributed uniformly and independently on [0, 1]. Formally, betting martin- gale is measurable function empty sequence and Z* stands for the set of all finite sequences of elements of Z) and for
[0, 1]' + [0, oo) such that F(D) = (O) defines an
each sequence (u),... Un Un-1) E [0, 1 and any n 2 1:
L. F(u 1 ud F F( (w...... .... un-1).
The simplest example is given by the product of simple bets:
x2 II
F(u Un) E"
14
0,
(10)
but more sophisticated options are available Vook et al. follow, we use simple mixture martingale which is obtained by integrating equation [quationIOOvee over [0. 1].
2005). For the simulations that
Conformal test martingale S, is obtained by plugging in the sequence of conformal p- values PI...., Pa into the betting martingale. The test starts with Sy = and it rejects at the first time when S, exceeds 1/a. They type I error control for this test is justified by Ville's 's inequality which states that for any nonnegative martingale (which S, is, un- der the i...d null), the entire process S, stays below 1/a with probability at least a. Mathematically:
(an: S, 1/a) S
To study conformal test martingales, consider the label shift setting described in Section 3.] Recall that for this setting we know exactly when a shift in label proportions becomes harmful ful (o misclassification risk of the Bayes-optimal rule the source distribution (see Figures 2a and 3a For the simulations that follow, we assume that the marginal probability of class on the source iS TT 0.25, and use the corresponding optimal rule.
We analyze conformal test martingales under several distribution drift scenarios differing in their severity and rate, and start with the settings where sharp shift is present.
14

---

Published as a conference paper at ICLR 2022
1. Harmful distribution shift with cold start. Here, the data sampled i..d. from shifted distribution corresponding to xं" = 0.75. We illustrate 50 runs of the procedure on Fig- ure 9a Recall that when the data are sampled i..d. the conformal p-values are i...d uniform on (0, I. Under the (exchangeability) null, conformal test martingales are not growing, and thus are not able detect that present shift, even though it corresponds harmful set- ting.
2. Harmful distribution shift with warm start. For a fairer comparison, we also consider a warm start setting when the first 100 points are sampled i.i.d. from the source distribution (TI = 0.25), followed by the data sampled i..d. from a shifted distribution (T 0.75). We illustrate 50 runs of the procedure Figure 9b In this case, conformal test martin- gales demonstrate better detection properties. However, a large fraction of conformal test martingales still is incapable of detecting shift.
Time processed somples
1301
Time number samples
(a)
(b)
Figure 9: 50 runs of conformal test martingales (blue dotted lines) under harmful distribution shift with: (a) cold start (shift happens in the beginning), (b) warm start (shift happens in an early stage of a model deployment). The horizontal red dashed line outlines to the rejection threshold due to Ville's inequality. Even though warm start improves detection properties, only a small fraction of conformal test martingales detects shift that leads to more than 10% drop in classification accuracy.
The simulations above illustrate that conformal test martingales are inferior to the framework pro- posed in this work whenever sharp distribution shift happens in the early stage of model deploy- ment, even when such shift is harmful. Next, we consider several settings where instead of changing sharply, the distribution drifts gradually.
3. Slow and benign distribution drift. Starting with the marginal probability of class 1, z 0.1, we keep increasing कं by 0.05 each time batch of 75 data points sampled until it reaches the value 0.45. Recall from Section 3.1 that those values of π] correspond to benign setting where the risk of the predictor on the target domain does not exceed substantially the source risk. We illustrate 50 runs of the procedure on Figure [Oa]
4. Slow and harmful distribution drift. Starting with the marginal probability of class #f 00.5, keep increasing "o by 0.05 each time batch of 75 data points is sampled until it reaches the value 0.85. Recall from Section 3.1 that those values of .. correspond
harmful setting where the risk of the predictor on the target domain is substantially larger than the source risk. We illustrate 50 runs of the procedure on Figure TOb
5. Sharp and harmful distribution drift. Starting with the marginal probability of class 1, x = 0.1, we keep increasing x/ by 0.2 each time batch of 150 data points is sampled until reaches the value 0.9. We illustrate 50 runs of the procedure on Figure 10c
The settings where the distribution drifts gradually illustrate several shortcomings of conformal test martingales:
Conformal test martingales consistently detect only sharp distribution drifts. Recall from Section 3.1 that increasing =/" from 0.1 to 0.9 results in more than 20% accuracy drop. When drift slow (Figures 10a and 10b), conformal test martingales demonstrate much less power.
Inspired by the ideas of Vovk et al. 2022 who assumed, like us, that (some) true data labels are observed, we designed a conformity score that reflects decrease in performance.
15

---

Published as a conference paper at ICLR 2022
30
60
130
30
Time / number processed samples
Time: / number processed samples
(a)
(b)
30
e0 number processed aamples
130
(c)
Figure 10: 50 runs of conformal test martingales (blue dotted lines) under gradual distribution drifts: (a) slow and benign, (b) slow and harmful, (c) sharp and harmful. The horizontal red dashed line outlines to the rejection threshold due to Ville's inequality. Note that conformal test martingales consistently detect only sharp distribution drifts. Moreover, conformal test martingales illustrate similar behavior under (a) and (b) but the corresponding settings are drastically different.
On Figures T0a and T0b conformal test martingales illustrate similar behavior but the cor- responding settings are drastically different. Only one corresponds to benign drift when the risk does not become significantly worse than the source risk. Thus, even though possible to make conformal test martingale reflect degrading performance, it is hard to in- corporate evaluation of the malignancy of a change an interpretable way, like a decrease of an important metric.
Another problem of using conformal test martingales time the corresponding values of the test martingale (larger implies more evidence for shift) could start to decrease as the shifted distribution becomes the 'new normal' (Vovk et al.) 2021). This is because they measure deviations from iid data, not degradations in performance from some benchmark (like source accuracy).
aware is that after some
B LOss FUNCTIONS
For our simulations, we consider the following bounded losses. Below, let (2;; f) = arg maxkey (x) denote the label prediction of model ff given input X.
Multiclass losses. The most common example arguably the misclassification loss and its gener- alization that allows for label-dependent cost of mistake:
emis (f(() = (f(:; f) + y} E (0,1), eu-mis (f(x).)) = ly (0(a;))) E [0, L].
where {Ex key is collection of per-class costs and L max lx. The loss gw-mis more relevant to high-stakes decision settings and imbalanced classification. However, high accuracy alone can often be insufficient. The Brier score (squared error), introduced initially for the binary setting (Brier 1950). is commonly employed to encourage calibration of probabilistic classifiers. For multiclass problems, one could consider the mean mqua-equared error of the whole output vector:
prier peier (f(z). = - [lf(()) - h(v) E 10.
1
(11)
16

---

Published as a conference paper at ICLR 2022
where h : - f0, 1 is one-hot label encoder: hy)(w) = 13 = y) for y. y E y. Top-label
calibration (Gupta & Ramdas 2022) restricts attention to the entry corresponding to the top-ranked label. A closely related loss function, which we call the top-label Brier score, is the following:
gbrier-lop (f(x), v) = (f)))(
(0(2; f) - y})² = (f) - ( E [0,1]. (12)
Alternatively, instead of the top-ranked label, one could focus only on the entry corresponding to the true class. It gives rise to another loss function which call the true-class Brier score:
gbrier-true (f(x), y) = (f(()) 1)² E [0
(13)
The loss functions gaiier ghrierlop Abrier-true trivially reduce the same loss function in the binary setting. In Appendix C we present a more detailed study of the Brier score in the multiclass setting with several illustrative examples.
Set-valued predictors. The proposed framework can be used for set-valued predictors that output a subset of y as a prediction. Such predictors naturally arise in multilabel classification, where more than single label can be the correct one, or as a result processing could target covering the correct label of test point with high probability (Vovk et al.) 2005) or controlling other notions of risk (Bates et al. 2021) like the miscoverage loss:
post-processing point predictors. Post-
Emiseon (v, S(x)) = 1 (v & S(x)).
(14)
where S(x) denotes the output of set-valued predictor any given input x E X. When consid- ering multilabel classification, relevant loss functions include the symmetric difference between the output and the of true labels, false negative rate and false discovery rate.
C BRIER SCORE IN THE MULTICLASS SETTING
This section contains derivations of decompositions stated in Section 2 and comparisons between introduced versions of the Brier score.
Brier score decompositions. Define function c X A with entries (x)
P( = k (()).. In words, coordinates of c(X) represent the true conditional probabilities of belonging to the corresponding classes given an output vector f(X). Recall that h 3 + {0. 1>121 one-hot label encoder. The expected Brier score for the case when the whole output vector considered (that is, the expected value of the loss defined in equation 11] satisfies the following decomposition:
2. Rebieer (ʃ) BXJ((X) -(Y))2
[X) c(X) + c(X) - 1(Y)112
(X) c(X)) + Ello(X) - h(Y))12
EXJ(() x(X)12 Ellc(X) - E [c(X)] + E -
(X) c(X) EX)((X) - E [c(O] 1| EJ)(()) E 12
calibration ernor
shurpness
intrinsic uncertainty
Above, (a) follows by conditioning on f(X) for the cross-term and recalling that [N(Y) I [(X)] c(X). (b) also follows by conditioning on f(X) ) and noticing that E [h(Y)] = E [c(X)] Now, recall that predictor is (canonically) calibrated if f(X) a.s. c(X), in which case the calibration error term is simply zero
Next, we consider the top-label Brier score pbrierlup Define dop X [0, 1]. as:
mo (X) = P = (X: foxxn )x)(x)))
or the fraction of correctly classified points among those that are predicted to belong to the same class and share the same confidence score X. Following essentially the same argument as for the
17

---

Published as a conference paper at ICLR 2022
standard Brier score, get that:
E phrier-top (f(X). Y)]
E (Js(x.)) (X) (Y))
E (Ji(x:)) (X) (X) + (X) -x10
= E (f (X) - c') + E (x) - hig hz)(x:((())
E (X)
E (c - -B [c + C - (x)
Var Var(hg(x))()))
label calibration
top label sharpness
variance misclasilication loss
Note that in contrast the classic Brier score decomposition, the last term in this decomposition depends only on the top-class prediction the underlying predictor, and thus on its accuracy.
Comparison the scores in multiclass setting. Recall that the difference between three versions of the Brier score arises when one moves beyond the binary classification setting. We illustrate the difference by considering a 4-class classification problem where the data represent balanced (that is all classes are equally likely) mixture of 4 Gaussians with identity covariance matrix and mean vectors being the vertices of 2-dimensional unit cube. One such sample is presented on Figure IIa
Next, analyze locally the Brier scores when the Bayes-optimal rule is used predictor, that is we split the area into small rectangles and estimate the mean score within each rectangle by sample average. The results presented on Figures] Ilb [1 and Tid Note that the difference between the assigned scores is mostly observed for the points that lie at the intersection of 4 classes where the support of the corresponding output vectors is large.
underlying
Clw 0
(a)
(b)
144
(c)
(d)
Figure 11: (a) Visualization of 4-class classification problem with all classes being equally likely; (b) localized classic Brier score ghrier (equation 11 (c) localized top-label Brier score (equa-
tion 12 (d) localized true-class Brier score gonertrue (equation 13
Brier scores under label shift. Here we consider the case when label shift on the target domain present. First, introduce the label likelihood ratios, also known the importance weights, wy :=
18

---

Published as a conference paper at ICLR 2022
Ty /m E V. For measuring the strength of the shift, introduce the condition number: sup, wy/ im0 wy. Note that when the shift is not present, the condition number k 1. To evaluate the sensitivity of the losses to the presence of label shift, we proceed as follows: first, the sampled from the Dirichlet distribution
class proportions for both source and target domains (to avoid extreme class proportion, we perform truncation at levels 0.15 and 0.85 and subsequent renormalization). Then we use the Bayes-optimal rule for the source domain to perform predictions on the target and compute the corresponding losses. On Figure 12 we illustrate relative increase in the average Brier scores plotted against the corresponding condition number when all data points considered (Figure 12a) and when attention is restricted to the area where classes highly intersect (Figure [ In general, all three versions of the Brier score suffer similarly on average. but the localized area where classes highly intersect, the top-label Brier score does not increase significantly under label shift.
1.30
Relonve memmoo
6.73
Rebatke
Cank Bier bie sove Tra-daa Brersope sooe
Brir The Biw soor Tra-daa Brier scon
Candition
number
(a)
(b)
Figure 12: (a) Relative increase for different versions of the Brier score in the multiclass setting under label shift; (b) Relative increase for different versions of the Brier score in the multiclass setting under label shift when attention is restricted to the area where classes highly intersect (cube with vertices at #12)), While general, all three versions of the Brier score suffer similarly on average, in the localized area where classes highly intersect, the top-label Brier score does not increase significantly under label shift.
D PROOFS
Proof of Proposition L For brevity, we omit writing f for the source/target risks and the corre- sponding bound upper/lower confidence bounds. Starting with the absolute change and the null Hu Br Rg S Ewl we have:
PHo
Et 2 1 D Üg + Ewl
THe (3/2 (7 RT)
-0s-Rs) Rs) > Ewl (Rr Rs))
< PHo (3t 1: (D RT) (Üs Rs} > 0)
Note that 31 1 : (L RT) - (Üg Rs) > implies that either 3t 1 D(4)
RT > 0 or
Üs Rs < 0. Thus, invoking union bound yields:
3t 2 [ Ri) -(0s- Rs 0)
P PHo
31 21 1: 7 Rr > 0) (Us - Rs < <0)
< P
6T ds.
by construction and validity guarantees for
7 and Üs. Similarly, considering the relative change,
ie., the null: Ho: : Rr I (1 + E((a) Rg, we have:
PHg
3 z 1: 1 (1 + {ww
1::1 1: (Z(0 Rτ) - +1+ e(a)) (Üg - Rs > (1 E - R
= =Prr
< FHz
(3/21
(740 RT) - (1 + k/a Ü - Rs > 0)
19

---

Published as a conference paper at ICLR 2022
Similarly, note that 3/ 2 1: (T.))) RT) (1 (1 +0)) Rs) implies that either 31 1 [ Rr > 0 or Üs Rs < 0. Thus, invoking union bound yields the desired result.
E PRIMER ON THE UPPER AND LOWER CONFIDENCE BOUNDS
This section contains the details for the concentration results used in this work. Results presented in this section are not new were developed in a series of recent works (Waudby-Snin Smith & Ramdas] [20TT] Howard al. 2021). We follow the notation from Waudby-Smith & Ramdas (2021) for consistency and use the superseript (4) when referring to confidence sequences (CS) and (n) when referring to confidence intervals (CI).
Predictably-min Hoeffding's (PM-H) confidence sequence. Then the upper and lower end- points of the predictably-mixed Hoeffding's (PM-H) confidence sequence are given by:
Σ == A
log(1/0) + Ei &H (Ai)
(t) L PM-H
i= A
Σ A
(t)
-i=1
AgZz
log(1/0) + Ei UH (A:)
PM-H
-i=1 Xi
EE A
where (A):
22/8 and \1, A is a predictable mixture. We use a particular predictable
mixture given by:
llg((1/) log(( 1)
PM-H
A 1.
When approximating the risk on the source domain, one would typically have holdout sample of a fixed size n, and so one could either use the classic upper limit the Hoeffding's confidence interval, which recovered by taking equal A = = / (ogg(1/8)//u I...., n, in which case the upper and lower limits simplify to:
Σ
Li=1 Z:
(1(()
E Zi
log(1/8)
(m)
L
2n
2n
or by considering running intersection of the predictably mixed Hoeffding's 's confidence sequence: (mingga (itt) UPM.H. maxign _
Predictablymmixed empirical-Bernstee Bernstein (PM-EB) confidence sequence. The upper and lower endpoints of the predictably-mine mixed Sppirical-Bernster (PM-EB) confidence sequence are given by:
-i=1 AzZe
log(1/8) + El (Ai)
LPM-BB
Σ1 iim1 X
Σ/=1 A log(1/8) + Et= (At)
(t)
ii AiZi
PMBBB
Σ A;
Σ Aa
where
= 4(, -)=1)² and (bE(A) == (- log(11 11 - X) - \) for X (0, 1).
One particular choice of a predictable mixture (APM.FB ) is given by:
2 2l0g(1/))
i= (Zi 22:)2
1 +
Σ i=l Zi
X
PM-EB
H log + Ae, 0.
P.
for some E 1). We 1/2 and also set flo 1/2, ã. 1/4. If given sample of fixed size n, we consider rumning intersection along with the predictable sequence given by:
X
PM-BB
Ac, t 1=
no?
20

---

Published as a conference paper at ICLR 2022
Betting-based confidence sequence. Tighter confidence intervals/sequenner can be obtained by invoking tools from martingale analysis and deploying betting strategies for confidence inter- vals/sequences construction proposed in (Waudby-Smith & Ramdas] 2021). While those can not be computed in closed-form, empirically they tend to outperform previously considered confidence intervals/sequences. Recall that are primarily interested in one-sided results, and for simplicity we discuss. For any m E [0, 1], introduce a capital (wealth) process:
k = II (1 + (m) (m) (Z: m)),
where {Ar (m) } and (m)) - are [0, 1 //mm-valueed and [0, 1 -al-uelued predictable sequences respectively. particular example of such predictable sequences is given by:
(m) = A .m (m
where, for example, c 1/2 or 3/4 and x do not depend on m. Such choice guarantees, in particular, that the resulting martingale is nonnegative. For example, the wealth process KC; (m) incorporates a belief that the true mean p. is larger than m and the converse belief is incorporated in KG (m). that is, the wealth expected to be accumulated under the corresponding belief (e.g.,
consider 0 and the corresponding K. (0) with a high value, and KT (1) with low value). Using that KC, (m) is non-increasing in m, i.e., m2 m., then KCT (m2) S K. (m1), we thus can use grid search (up to specified approximation error Agria) to efficiently approximate ( = inf Bt, where
1 and the corresponding
B == {m []: (m) < 1/6).
that is, the collection of all m for which that the capital wasn't 't accumulated. Then we can consider L maXę<n Lee. When μ is considered, none of K2, (H) is expected be large, since by
Ville's s inequality:
PP (3t 2 1: (Ct(((()))) 2 1/6) 6
and thus we know that with high probability the true mean larger than Bei That is,
P
(1 (mn)
P max 'Bet P (31 1::1::00 inf BT))
(2)
P -3 1: (p) 1/8) 8
By similar argument, we get that with high probability, the mean is less than Ret mingsn sup :
P p U(()
u min sup By = (312 sup B,) 15 =P ( K, (w) 2 1/6) 8.
Cunjugate-mixture impirical-Bernsterr (CM-EB) confidence sequence. Below, we present a shortened description of CM-EB and refer the reader to Howard al. (2021) for more details. Assume that one observes a sequence of random variables Z,, bounded in aa b almost surely for all i, and the goal is to construct a confidence sequence for b = 6-1 E/= E,- 1i, the average conditional expectation. Theorem 4 in Howard al. (2021) states that for any (ž,), [a, v-aluud predictable sequence, and any u, the sub-exponential uniform boundary with crossing probability a for scale e b holds that:
(Zi -2,²²)
IP
Vt
1: Z. 1
2 21-2a. 20,
where reasonable choice for the predictable sequence (Zx) is given by 7, -1-1)-1 Z.
21

---

Published as a conference paper at ICLR 2022
The key challenge which is addressed by conjugate mixtures is obtaining sublinear uniform bound- aries that allows the radius of the confidence sequences to shrink to zero asymptotically. When a closed form of the confidence sequence is not required, the gamma-exponential mixture generally yields the tightest bounds. The procedure relies on the following mixing result (Lemma 2, Howard eet al. (2021) which states that for any a 10, and any chosen probability distribution F [0, Amax):
CM (v) = sup U
s :E:E R
a
yields sub-t uniform boundary with crossing probability a. When the gamma distribution is used for mixing, m(s, v) has a closed form given in [Proposition 9, Howard et al. (202T)]. Subsequently,
the resulting gammaa expommnatxpnnntiall mixture boundary u (v) computed by numerically solving
the equation m(s, v) = 1/a in s. Howard et al. (2021) provide the packages for computing the corresponding confidence sequence.
F EXPERIMENTS ON SIMULATED DATA
Figure 1 illustrates data samples for two settings where the presence of label shift is not expected to cause degradation in model performance (measured in terms of absolute increase in misclassification risk) for the first (No (-2, 0) 14 (2, 0) T) but label shift may potentially degrade
performance for the second (No = (-1,0)
(1, For both cases, samples follow the same data generation pipeline as in Section with only changes in class centers.
Daa 0
Clas
Oau
Clas
(a)
(b)
Figure 13: (a) Simulated dataset with well-separated classes. Presence of label shift presumably will not lead to high absolute increase in the misclassification risk. (b) In contrast, when the classes are not well- sepaasepar,,ed, presence of label shift presumably might hurt the misclassification risk.
BRIER SCORE AS A TARGET METRIC
target metric. Recall that all three multiclass versions of the Brier score discussed this work reduce to the same loss in the binary setting. First, compare upper confidence bounds for the Brier score computed by invoking different concentration results on Figure [4] Similar to the misclassification risk, variance-adaptive confidence bounds exploit the low-variance structure and are tighter when compared against the non-adaptive one.
Here replicate the empirical study from Section 3.1 but the Brier
Next, perform empirical analysis of the power of the testing framework. We take Sml 0.1 which corresponds to testing for a 10% relative increase in the Brier score. We take = 1000 data points from the source distribution to compute upper confidence bound on the source risk (f). Subsequently, we sample the data from the target distribution batches 50, with maximum number of samples from the target set to be 2000. On Figure 14b. present the proportion of cases when the null hypothesis rejected out of 250 simulations performed for each candidate class 1 probability. On Figure [4c] we illustrate average sample size from the target domain that was needed to reject the null hypothesis. When a stronger and more harmful label shift present, less samples required to reject the null, and moreover, the most powerful tests utilize upper/lower
22

---

Published as a conference paper at ICLR 2022
confidence bounds obtained via the betting approach. On Figure 14d different lower confidence bounds.
present the comparison of
0.20
Upper confidence bounds viz
Hluetiig
Proportion of rejecionss
Hoefting' CB Beling
PSSEI
Betting
01:00
0.20
11
0.2
Number
Marginal probabiity of dlsss on the torget, x]
(b)
Sanple sdc sojot the (4))
Hodfi
2.00
Setting
Miter Store
0.80
0.0
UCB on the sourcs me
LCR on the target dikk voe
034
PM.ES
Morgital prothblly trrget.
30
se 30
190 samples target
1900
(d)
Figure 14: (a) Upper confidence bounds (f) on the Brier score for the source domain. Sim- ilar to the misclassification risk, variance-adaptive confidence bounds are tighter when compared against the Hoeffding's ss one. For each fixed number of data points from the source domain used to compute (f), presented results are aggregated over 1000 random data draws. (b) Proportion of null rejections made by the procedure when testing for 10% relative increase of the Brier score. (c) Average sample size from the target distribution that was needed to reject the null. Invoking tighter concentration results allows raise an alarm after processing less samples from the target domain. (d) Different lower/upper confidence bounds on the target/source domain for the Brier score.
G EXPERIMENTS ON REAL DATASETS
G.1 MNIST-C SIMULATION
Architecture and training. For MNIST-C dataset, we train shallow CNN with convolu- tional layers (each with 3 x 3 kernel matrices), each followed by max max-pooling layers. Subsequently, the result flattened and followed by dropout layer (p 0.5), fully-connected layer with 128 neurons and an output layer. Note that the network is trained on original (clean) MNIST data, which split split into two folds with 10% of data used for validation purposes. All images are sealed to [0, range before the training is performed.
Training multiple networks. To validate observations regarding shift malignancy from Sec- tion 3.2. we train 5 different networks (following the same training protocol) and report aggregated (over 25 random ordering of the data from the target) results on Figure 15 The observation that ap- plying translation to the MNIST images represents harmful shift consistent across all networks.
G.2 CIFAR-10-C SIMULATION
Architecture and training. The model underlying set-valued predictor is a standard ResNet-32. It is trained for 50 epochs the original (clean) CIFAR-10 dataset, without data augmentation, using 10% data for validation purposes. All images are scaled to [0, 1] range before the training is performed. The accuracy of the resulting network is 80.5%.
23

---

Published as a conference paper at ICLR 2022
0.55
Test rejection threshold: Os( (isf))tiru ti
0.30
LCB on the target risk for:
Misclassiing Misclassfiicttio risk
0.25
Clean
Translate
01200
Zigzag
Motion Blur
0.35
0.300
11.00
11.00
250
500
750
1000
1250
1500
1750
2000
Number of samples from the target domain
Figure 15: Lines of the same color correspond different CNNs. For each network, the results aggregated over 25 random rums of the testing framework for randomly permuted test data. Applying translate effect consistently harmful the performance of CNNs trained on clean MNIST data. The bar around the yellow dashed line corresponds to 2 standard deviations.
Transforming a point predictor into a set-valued one. To transform point predictor into a set- valued one, we consider a sequence of candidate prediction sets Sx parameterized by univariate parameter X, with larger À leading to larger prediction sets. Under the considered setting, the un- derlying predictor an estimator of the true conditional probabilities [y(z)) F (Y y X X x).
Given learnt predictor / we can define
Py py(x;f) = Σ fz(z) (fe(x)) f((2)}
to represent estimated probability mass of the labels that more likely than y. Subsequently, can consider the following sequence of valuval predictors:
Sxxx) = {y E y P, f) s }}. AE [0, 1].
that is the sequence is based on the estimated density level sets, starting by including the most likely
labels according to the predictions of f. To tune the parameter X, we follow Bates et al. (022 I); we
keep a labeled holdout calibration set, and use it to pick:
π inf ( (*) B, VX > }}.
where R. (X") is an upper confidence bound for the risk function at level B. The resulting set-valued predictor is then (3,1) (2,7)-RCC RCPS, that is,
P (R(SA) S B) 21-7
under the i.i.d. assumption. More details and validity guarantees can be found in Bates et al.
2021
Set-valued predictor when 3 = 0.05 is used prescribed error level. In contrast to 0.1 used in the main paper, we also consider decreasing 3 to 0.05, which in words, corresponds to increasing desired coverage level of the resulting set-valued predictor. Figure [6a compares average sizes of the prediction sets for two candidate values: 31 = 0.05 and 82 = 0.1, when the set-valued predictor passes either clean CIFAR-10 data, images to which fog corruption has been applied. As expected, decreasing 3 leads to larger prediction sets on average, with the size increasing when corrupted images are passes as input, that the size reflects uncertainty prediction. In Figure T6b] we observe that when we run the testing framework for the set-valued predictor corresponding to 8 0.05, only the most severe version corruptions by adding fog is consistently marked as harmful, and thus raising an alarm. Similar to Section 3.2 we also use = 0.05.
H TESTING FOR HARMFUL COVARIATE SHIFT
In this section, we consider a case when covariate shift is present on the target domain, that is, when the marginal distribution P(X) changes but P(Y|X) does not. Consider the binary classification
24

---

Published as a conference paper at ICLR 2022
Ryyettoe shekkadd Oc/
LCB on the target mak for.
Frg. Leantty
Fog. unantyy
Fog. severty
305
360
Type of irput data and presorized enor lovel
Number of samples from the target domain
2018
120
2010
1761
A01
(a)
(b)
Figure 16: (a) Average size of prediction sets for 0.05 and B2 0.1 and different types of input data. First, lower 3, corresponding to higher desired coverage, leads to larger prediction sets on average. Second, average size of the prediction sets increases when more corrupted images are passed as input, thus reflecting uncertainty in prediction. (b) Results of running the framework when 31 = 0.05 is used to construct wrapper. Observe that setting a lower prescribed error level / and thus enlarging resulting prediction sets partially mitigates the impact of corrupting images with the fog effect. However, the most severe form of such corruption still consistently leads to rejecting the null. The bars around dashed and solid lines correspond to 2 standard deviations.
setting with accuracy being a target metric. It is known that the optimal decision rule for this case is the Bayes-optimal rule:
f(()) - ( = 1/2},
which minimizes the probability of misclassifying a new data point. Then one might expect that change in the marginal distribution of X does not necessarily call for retraining if a learnt pre- dictor f is 'close' to I (which itself could be a serious assumption to make). However, a change in the marginal distribution of X could indicate, in particular, that one should reconsider certain design choices made during training a model. To illustrate when it could be useful, we consider the following data generation pipeline:
1. Initially, each point is assigned either to the origin or to a circle of radius centered at the origin with probability 1/2.
2. For points assigned to the origin, the coordinates are sampled from multivariate Gaussian distribution with zero mean and rescaled identity covariance matrix: 36 /2-
3. For points assigned the circle, the coordinates are sampled from multivariate Gaussian distribution with the same covariance matrix but with the mean vector:
Ns cos cos(pp, fly (pp)
where 8 Unif([-n/88 x r/3)) on the source domain and op Uni 2nr) the target domain (see ( for a visualization).
4. Then points are assigned the corresponding labels according to:
1 2 + 2
2
is easy to see that linear predictor, e.g., logistic regression, can achieve high accuracy if deployed on the data sampled from the source distribution. However, it will clearly fail recover the true relationship between the features and responses. In this case, a change in the marginal distribution of X might indicate that updating functional class could be necessary. On this data, we also the proposed framework testing for a 10% increase in misclassification risk (Eus = 0.1). At each run, we use 200 points to train logistic regression and 100 points to estimate the betting-based upper confidence bound on the source risk. On the target domain, we use the lower confidence bound due to conjugate-mixee mixture empirical-Bernstern Bernstein (CM-EB). The results presented on Figure 17c (which have been aggregated over 100 random data draws) illustrate that the framework successfully detects a harmful shift, requiring only a small number of samples to do so.
25

---

Published as a conference paper at ICLR 2022
1.5
1.00
Source, Class
1.0
Source, Class
1.
Target, Class 0
0.5
Target, Class
1181
0.0
0.
-1.5
1.5
-1.0
-1.5
0.01
11.5
1.11
1.5
1.5
1.00
0.6
0.0
1.4
1.5
(a)
(b)
Mistyuitaation ESk
0:20
LCB rik CM
Namber samples from doma
(c)
Figure 17: (a) Data samples from the source (red) and target (blue) distributions for the covariate shift simulation. (b) Logistic regression predictor learnt the source distribution plotted along with a data sample from the target distribution. While learnt predictor clearly has high accuracy on the source domain, it fails to approximate the true underlying data generating distribution. (c) Results of running the framework when testing for 10% increase in the misclassification risk. The framework detects harmful shift after processing only small number of samples.
26


Reviews:
[{"review_id": "uH-mrd9hR2", "reviewer": "Reviewer_oNqc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "$\\textbf{Strengths}$\n\nDetailed and clear with proper explanations and proofs of the presented schema and related propositions.\n\nBuilds on related work in the field with (to the best of my knowledge) a novel contribution.\n\nDiscussion of relevant distribution shifts and their effect on classifiers is really interesting (see weaknesses).\n\n$\\textbf{Weaknesses}$\n\nMinor grammatical/style issues. For example, on page 3 the $\\textbf{Multiclass losses}$ sub-header has a period, but other similar ones do not. I suggest adding a period to all of them for consistency. There are also other grammatical issues such as on page 3: \"those naturally arise in multilabel classification, where more than a single label can be the correct one, or as a result of post-processing point predictors, which could target....\" where \"those\" is a vague pronoun reference and the use of commas is incorrect.\n\nAlthough the contribution is novel (to my knowledge), I think that the paper is missing an explicit discussion as to why this contribution is important (e.g. a particular case where this new schema enables users to prevent something that they otherwise could not and being unable to has negative repercussions). \n\nAlthough the discussion of relevant distribution shifts and their effect on classifiers is really interesting, it left me wanting more. I think the paper could benefit from expressing how the testing schema presented can be used to identify malignant shifts and how to do so (e.g. humans thing translation wouldn't be an issue but it is, how do we discover more facts like this provable?).", "summary_of_the_paper": "This paper proposes a sequential testing schema for identifying malignant distribution shifts that indicate a necessary update such as retraining. The framework presented is designed to be generalizable and applicable to many scenarios (binary, multiclass, set functions, etc.).", "summary_of_the_review": "I give the paper a 6 because I find the contribution novel and clear and would be happy to see it accepted in the conference; however, I would not champion pushing to accept given my belief that there is room for significant improvement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kbdYYIiJaO", "reviewer": "Reviewer_mEfm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The paper applies sequential testing to detect harmful distribution shifts. The setting is quite different from existing work. \n\nWeaknesses: \nWriting. The writing quality and the presentation of the paper can be substantially improved. For example, in section 2, It might be better to move the loss functions to the experimental section, as they are not part of the algorithm. \n\nNovelty. Overall, I don't see enough originality, and it's not very challenging to adapt the sequential testing to this setting. The main idea is to detect the bad distribution shifts by nonparametric sequential testing based on comparing the risk function on the target data and the risk function on the source data. The monitoring statistics are the risk functions (and their CI). \n\nComments. 1. The proposed method requires the labels from the test data, which is a restrictive setting for practical use. The paper claims that the label can be revealed in a delayed fashion, but we could also do batch detection for the past observations (and wait for a period and redo the testing). The paper doesn't provide any expected sample size analysis. I think it'd be better to give some comparison with the batch detection algorithm.  2. Since the algorithm requires to compute the CI at each time step, how efficient is it?", "summary_of_the_paper": "This paper develops a tool for testing online whether the performance of a model on the test data becomes significantly worse than the performance on the training data, which allows differentiating between benign and harmful shifts. The proposed framework is based on sequential testing for a significant risk increase. The theoretical guarantee of the type I error control is provided. The paper also gives simulation and real data experiments to demonstrate the efficacy of the proposed algorithm. ", "summary_of_the_review": "I'd recommend reject at this point.\n\n-----------------------------------------------------\nThank the authors for the response! The authors substantially improved the writing and the presentation in the updated version. They also added new content regarding comparison with other papers/other potential methods, which makes the contribution more clear. I read reviews from other reviewers as well as the corresponding responses. The answer clears most of my concerns. Although I think the theoretical contribution is not significant, adapting sequential estimation to the practical setting would be nice. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "g4oI8T8n5F6", "reviewer": "Reviewer_a6Wo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n1. This paper has studied distribution drift in both i.i.d. and independence settings, where the non- i.i.d. assumption is more realistic and provide stronger results: since in real situation the distribution is more likely to drift gradually instead of a sharp change.\n\n2. The sequential detection method is an intuitive way to continuously monitor model performance. In addition, the authors have also discussed several variants of multiclass losses to be combined with the sequential detection framework, which is commonly used in a variety of tasks.\n\n**Weakness**\n\n1. [Experimental results] All reported results of methods and baselines are proposed in the paper, e.g., Hoeffding, PM-EB, and betting are methods with different confidence bounds. There should be a direct comparison with other baselines and non-sequential methods, or at least show the behavior of a state-of-the-art approach to demonstrate what's the advantage of sequential testing. In addition, it is better to conduct both label and covariate shift experiments in sections 3.1 and 3.2.\n\n2. [Notations] The authors first defined $Z$ in section 2.2 but it first appears in section 2.1; the definition of $R^{(t)} (f)$, what is the expectation over?\n\n3. [Others] In section 1, the authors have mentioned current methods require assumptions on both covariate and label shift. Although the proposed method doesn't need this assumption, it is great to showcase how to overcome this issue when the assumption is violated.\n", "summary_of_the_paper": "This paper proposed a sequential testing method for tracking distribution shifts for deployed models. The main idea is to utilize sequential hypothesis testing on a given objective function in a range of time stamps. The authors have studied a variety of different confidence intervals/sequences that certifies benign or harmful distribution drifts and have also demonstrated theoretical support for their claims. Empirical results on both simulated and real data have shown this sequential testing method is effective in detecting severe distribution drifts.", "summary_of_the_review": "This paper proposes an effective and theoretically sound method for sequentially detecting harmful distribution drifts. Overall, this work is solid but still requires some improvements on the experiment.\n\n## Update after Rebuttal\n\nWe thank the authors for their detailed responses and for updating the manuscripts. The authors have addressed my questions, but we tend to keep the current score based on the significance of the improvements made.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_RiWKLGMpw1", "reviewer": "Reviewer_9YNK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed framework leverages well-established results in statistics to detect dataset shifts. While the framework addresses the problem in the most practical settings (sequential), the points of comparison with the existing frameworks were not made rigorous enough for the reader. Thus, I have the following questions - \n\n1. Why is sequential testing necessary in dataset shift under i.i.d assumption? I can imagine it to be useful under the independence assumption. Under the i.i.d setting, how does the performance of the proposed framework compare to Kamulete, 2021? Is the power of the test comparable? Can a similar curve (Figures 2,3,4)  for a number of samples be obtained for Kamulete, 2021? When will the testing framework of Kamulete, 2021 fail or work better? MNIST-C experiments are under the i.i.d dataset shift. Can a comparison with this testing framework be made? \n\n2. Similarly, when the i.i.d assumption is violated (distribution drift), can the comparison with the testing framework of Vovk et al. 2021 be made? \n\n\nMinor comments - \n- Figure 4(a): Horizontal line is yellow, not red\n- PM and CM are not spelt out in the main paper\n- “the this” often used in the paper\n- “ intervene in a data-adaptive way”: Does this refer to model retraining? Are there other examples?\n", "summary_of_the_paper": "The authors have proposed a framework for detecting dataset shift (under i.i.d assumption or via drift) such that the model’s performance suffers a significant (defined by the user) performance degrade. The framework accommodates several types of risk functions that can be used to evaluate the model’s performance. The underlying engine of the framework is sequential testing via non-parametric sequential estimation. Such a framework can potentially be useful for raising alarms or indicating when the model needs to be retrained. ", "summary_of_the_review": "Based on my knowledge and background research conducted while reviewing this work, I think the authors have proposed a novel framework to detect dataset shifts. It can potentially be used to improve several applications fraught with predictive models. The work is well supported with the help of illustrative examples. My only concern is their comparison with the existing works on dataset shift detection is not well explained/not supported.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JYDBpH3k9ln", "reviewer": "Reviewer_P77d", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work highlights an important problem of alerting when model performance differs from that in training, statistically significantly. The framework is broadly applicable to any model and multiple loss functions. Multiple issues in monitoring of models are addressed such as distribution shifts, sequential testing, different loss function. The solution uses some recent work on non-parametric, non-asymptotic testing in a novel way and has good performance under comprehensive set of experiments.\n\nThe main weakness is the presentation. The resolution of issues with past work, such as shifts and sequential testing, is not described well. Technical details on computing the confidence bounds are missing. Apart from these details, the framework and the experiments are described well.\n\n---\n\n## Questions to address in the response\n\n1. What is the difference in the method between the two settings i.i.d. and independent test examples?\n2. What type of distribution shifts such as covariate, label shift can be addressed?\n3. Please comment on the utility of testing the running risk? As the model decisions have already been made, the running risk tells the risk in the (recent) past and not the imminent risk. If the distribution shifts considerably, then the imminent risk can be considerably different. In what scenarios (or some smoothness assumptions on the drift) can such a test for running risk help in giving early warnings? I feel elaborating on this detail gives a better understanding on when to use such methods.\n4. What can be included to describe the method in more detail? Please see suggestions below. \n5. Does the alternate methods (EB and Hoeffding based ones) provide valid intervals in the considered setting of shifts and sequential testing? How would we expect such methods to perform, too loose or incorrect confidence intervals?\n6. How to choose between betting and conjugate mixture empirical-Bernstein methods for confidence bounds for source and target risk? Both are used in real data experiments, one for source and one for target. My understanding is both provide symmetric intervals and thus are applicable.\n\n---\n\n## Suggestions\n\nThe use of time-uniform confidence sequences to resolve issues with past works should be explained in more detail for readers not familiar with advantages of such confidence sequences. \n\nThe description of the exact testing procedures used needs to be self-contained including how to find upper and lower confidence bounds for the risk in terms of a given model, loss, and confidence parameter \\delta. \n\nThe context for introducing different loss functions at the start of Section 2 is not clear from the Introduction, which mostly talks about sequential testing without much attention to different loss functions. The discussion on loss functions is not related back to the problem or the method.\n\nPlease add the takeaway from Figure 4b. Should we expect other methods to take more samples to detect the harmful shift?\n\nResults for Figure 4a seems to show that the betting based bounds are tighter only for small number of samples and about the same for otherwise. The discussion on the Figure can be made more specific, instead of saying that it is tighter in general.\n\nThe contributions of the work can be outlined at the end of Introduction so that reader has some context.\n\nThe necessity of time-uniform confidence sequences can be elaborated for readers not familiar with multiple testing under dependent data. Consider highlighting the issue with using traditional tests.\n\nPlease briefly describe what is \\beta used in Section 3.2 to output prediction sets in the main text. It is fine to refer to the text in the Appendix for details.\n \nClarify if the method works for any loss function or the theoretical results need some conditions on the loss function.\n\nDescribe the full-form of PM-EB and the formulae for the bound.\n\nIn the expression for running risk before Eq (6), clarify what is the distribution for the expectation.\n\nIt will be worth mentioning (if not already) that instead of comparing against the upper confidence bound for source risk, one can use a given risk threshold deemed to be harmful and the method still applies.\n\nThe line is disconnected from the neighbouring sentences - If accuracy is a guiding performance metric, one would rarely deploy models performing only sightly better than prediction by chance.", "summary_of_the_paper": "The work presents a framework for alerting when the risk of a deployed model exceeds pre-defined levels. Observing a sequence of target instances, coming from possibly different distribution than source one, it defines two hypothesis tests (based on additive and multiplicative error) for harmful changes to the risk. It reduces the problem to sequential estimation of bounds for the target risk and uses recent work on time-uniform confidence sequences to design valid hypothesis testing methods. Empirical performance on a controlled synthetic setting and real world data from MNIST, CIFAR show that the methods detects harmful changes to risk in reasonable samples.", "summary_of_the_review": "The work addresses an important problem for monitoring models after deployment for harmful changes and derives principled hypothesis tests. Empirical study sufficiently validates the method on real datasets. My main concern is the presentation of the method. It lacks details on related to implementation and guarantees for the methods for readers who are unfamiliar with past work (Waudby-Smith and Ramdas 2021, and Howard et al. 2021). The work provides provides a strong contribution and I feel, subject to the response, the presentation can be improved.\n\n---\nBased on the response\n\nThe presentation of the methods has been substantially improved. In particular, the contributions paragraph at the end of Introduction gives a good overview of the work. I would encourage authors to more prominently list the confidence bound variants (betting-based, PM-H, PM-EB, CM-EB, Hoeffding) in Sec 2.2 to more clearly layout the options to implement the tests.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is concerned with the problem of distribution shift, and develops techniques for detecting when the risk of a deployed model performs significantly worse on a testing distribution than on the training distribution.

The reviews for this paper were extremely consistent: after the discussion period, all five reviewers unanimously recommended acceptance, and several praised the authors for significantly improving their paper in response to reviewer criticism. Outstanding issues are (i) motivating the importance of the setting, and (ii) comparing with prior work. None of the reviewers seemed to think that these issues should be barriers to acceptance, but please seriously consider them, and all reviewer concerns.
Decision: Accept (Poster)