1 Introduction↩︎

As AI/ML systems become integral to real-world applications, ensuring their safety and utility under evolving conditions is essential for responsible deployment. However, even meticulously trained models with apparent reliability guarantees can fail abruptly when shifts in the data distribution or operational environment violate the underlying conditions they were designed for [1]. That is, unforeseen deployment conditions can make it impossible to guarantee reliability for all situations in advance. Consequently, there is growing recognition for the need to continuously monitor deployed AI systems for determining when model updates are required to mitigate downstream harm [2]–[5]. In this work, we moreover argue that such monitoring methods should ideally perform at least three key functions: (1) maintain end-user reliability and minimize unnecessary alarms by adapting online to mild or benign data shifts; (2) rapidly detect more extreme or harmful shifts that necessitate updates; and (3) identify the root-cause of degradation to inform appropriate recovery.

For example, consider a healthcare use case where the goal is to predict the risk of sepsis, a life-threatening infection, \(Y\) from electronic health record inputs \(X\) (e.g., vital signs, lab tests, medical history, demographics) using an AI/ML system (e.g., [6]). Various clinical data shifts pose challenges to monitoring in practice [7]. Figure 1 illustrates hypothetical synthetic-data shifts that can be interpreted through this sepsis example, where for simplicity \(X\) only represents a patient’s age. An example of a benign shift is a mild shift in patient demographics primarily toward young adults; Figure 1a shows a corresponding covariate shift in the marginal \(X\) distribution. Such a mild shift to a younger population would be benign, as younger individuals are well-represented in the training data and also tend to have lower, less variable (easier to predict) sepsis risk—so, there is no need for an alarm. On the other hand, harmful shift examples include if the AI tool were deployed with a much older population than observed in the training data (e.g., Figure 1b) or if a new microbial strain were to arise that was especially severe in children (e.g., Figure 1c). In any such harmful shift case, swift detection and root-cause analysis is essential to initiate and inform retraining, to ultimately minimize harm.

Recent advances in anytime-valid inference [8] and especially conformal test martingales (CTMs) [9], [10] offer promising tools for AI monitoring with sequential, nonparametric guarantees. However, existing CTM monitoring methods (e.g., [2]) all rely on some form of exchangeability (e.g., IID) assumption in their null hypotheses—informally, meaning that the data distribution is the same across time or data batches—and as a result, standard CTMs can raise unnecessary alarms even when a shift is mild or benign (e.g., Figure 1a). Meanwhile, existing comparable monitoring methods for directly tracking the risk of a deployed AI (e.g., [3]) tend to be less efficient than CTMs regarding their computational complexity, data usage, and/or speed in detecting harmful shifts (Sec. 4.3).

Our paper’s contributions can be summarized as follows:

• Our main theoretical contribution is to propose weighted-conformal test martingales (WCTMs), constructed from sequences of weighted-conformal \(p\)-values, which generalize their standard conformal precursors. WCTMs lay a theoretical foundation for sequential and continual testing of a broad class of null hypotheses beyond exchangeability, such as shifts that one aims to model and adapt to.

• For practical applications, we propose WATCH: Weighted Adaptive Testing for Changepoint Hypotheses, a framework for AI monitoring using WCTMs. WATCH continuously adapts to mild or benign distribution shifts (e.g., Figure 1a) to maintain end-user safety and utility (and avoid unnecessary alarms), while quickly detecting harmful shifts (e.g., Figure 1b & c) and enabling root-cause analysis.

2 Background↩︎

Notation: Assume an initial dataset \(Z_{1:n}:= \{Z_i\}_{i=1}^n\), where each datapoint \(Z_i := (X_i, Y_i) \in \mathcal{X} \times \mathcal{Y}=\mathcal{Z}\) is a real-valued (\(\mathcal{X} \times \mathcal{Y} \subseteq \mathbb{R}^d \times \mathbb{R}\)) feature-label pair. For simplicity, further assume that an AI/ML model \(\widehat{\mu}\) is pretrained on a separate dataset.¹ After deploying the AI/ML model, the test points are observed sequentially at each time \(t=1, ..., T\) (batch data can be given random ordering), though for simpler exposition, we initially focus on \(t=1\). We abbreviate indices \([m]:=\{1, ..., m\}\). Random variables are denoted with capital letters (e.g., \(Z_i\)) and observed values with lowercase (e.g., \(z_i\)). For \(Z := Z_{1:(n+t)}\), we let \(F_Z\) denote the joint distribution function, \(f_Z\) the joint density function, and boldface \(\mathbf{F_Z}\) denotes a set of disitributions.

2.1 Conformal Prediction and Conformal \(p\)-Values↩︎

Standard conformal prediction (CP) [12] is an approach to predictive inference: the task of converting a black-box AI/ML prediction, \(\widehat{\mu}(X_{n+1})\), into a predictive confidence interval/set, \(\widehat{C}_{[n], \alpha}(X_{n+1})\), that should contain the true label with a user-specified rate, \(1-\alpha \in (0, 1)\) (e.g., 90%). This objective is called valid (marginal) coverage:² \[\begin{align} \mathbb{P}\big\{Y_{n+1} \in \widehat{C}_{[n], \alpha}(X_{n+1})\big\} \geq 1 - \alpha. \label{eq:coverage95condition} \end{align}\tag{1}\] Constructing the CP set, \(\widehat{C}_{[n], \alpha}(X_{n+1})\), requires a labeled calibration dataset,³ \(Z_{1:n}\), and a “nonconformity”score function, \(\mathcal{\widehat{S}}: \mathcal{X}\times\mathcal{Y} \rightarrow \mathbb{R}\), which generally uses the prefit ML predictor to quantify how “strange” a point \((x, y)\) is relative to the training data. A common example is the absolute-value residual score, \(\mathcal{\widehat{S}}(x, y) = |y - \widehat{\mu}(x)|\).

Though not always framed as such, the CP set \(\widehat{C}_{[n], \alpha}(X_{n+1})\) can be computed via a conformal p-value, which places the “strangeness” of the test point’s score in context of the calibration-data scores. That is, with \(v_i := \widehat{\mathcal{S}}(x_{i}, y_{i})\) for all \(i\in [n+1]\), [12] defines the conformal \(p\)-value for test point \(Z_{n+1}\) relative to calibration data \(Z_{1:n}\) as the fraction of the \(n+1\) scores, \(v_{1:(n+1)}\), that are at least as large as \(v_{n+1}\), with ties broken uniformly at random: \[\begin{align} p_{n+1} := \frac{|\{i : v_i > v_{n+1}\}| + u_{n+1}|\{i : v_i = v_{n+1}\}|}{n+1},\label{eq:unweighted95p95vals} \end{align}\tag{2}\] where \(U_{n+1}\stackrel{iid}{\sim} \text{Unif}[0, 1]\); that is, \(u_{n+1}\) is obtained from an independent standard uniform distribution.⁴ The CP set \(\widehat{C}_{[n], \alpha}(X_{n+1})\) can then be understood as the subset of labels \(y\in \mathcal{Y}\) that would not result in too “extreme” of a test-point \(p\)-value, \(p_{n+1}(X_{n+1}, y)\) (this is explicit notation for \(p_{n+1}\) to emphasize its dependence on the candidate label \(y\)): \[\begin{align} \label{eq:cp95set95def95via95p95val} & \widehat{C}_{[n], \alpha}(X_{n+1}) := \big\{y \in \mathcal{Y} : p_{n+1}(X_{n+1}, y) > \alpha \big\}. \end{align}\tag{3}\]

2.2 Exchangeability Underlies Standard CP Validity↩︎

For the standard CP set in Eq. 3 , the coverage guarantee in Eq. 1 holds assuming that the calibration data \(Z_{1:n}\) and test point \(Z_{n+1}\) are all exchangeable, meaning that any ordering of the observations is equally likely—independent and identically distributed (IID) data are a prime example. Formally, exchangeability means that the joint distribution function, \(F_Z\), is invariant to permutations \(\sigma\): that is, \(F_Z(z_{\sigma(1)}, ..., z_{\sigma(n+1)}) = F_Z(z_{1}, ..., z_{n+1})\) for all \(z_1, ..., z_{n+1}\in \mathcal{Z}\) and all \(\sigma\). With \(\mathbf{F_Z^{\boldsymbol{ex}}}\) denoting the set of exchangeable joint distributions, we can write the assumption of exchangeability as a (nonparametric) null hypothesis: \[\begin{align} \mathcal{H}_0^{\text{ex}} \;: \;Z_1, Z_2, ..., Z_{n+1} \sim F_Z \;: \;F_Z \in \mathbf{F_Z^{\boldsymbol{ex}}}. \label{eq:H95095exchangeability} \end{align}\tag{4}\] Standard conformal \(p\)-values are valid or “bona fide” \(p\)-values, in the usual statistical testing sense, for the null hypothesis of exchangeablity [12]. That is, assuming \(\mathcal{H}_0^{\text{ex}}\), then \(P_{n+1}\stackrel{iid}{\sim}\text{Unif}[0,1]\) [10] and \[\begin{align} \label{eq:cp95p95val95validity} \mathbb{P}_{\mathcal{H}_0^{\text{ex}}}(P_{n+1}\leq \alpha) \leq \alpha \qquad \forall \;\alpha \in (0, 1). \end{align}\tag{5}\] Thus, observing an extreme value of \(p_{n+1}\) is evidence against \(\mathcal{H}_0^{\text{ex}}\) (Eq. 4 ), or evidence for a distribution shift.

2.3 Standard Conformal Test Martingales: Testing Exchangeability Online via Betting↩︎

Standard conformal test martingales (CTMs) [2], [9], [10] continually aggregate information from a sequence of conformal \(p\)-values (Eq. 2 ) to perform online testing of the exchangeability null, \(\mathcal{H}_0^{\text{ex}}\). They can be constructed on top of any standard CP method, and thus on top of any conformalized AI/ML model, and used to monitor for deviations from \(\mathcal{H}_0^{\text{ex}}\). We will describe CTMs from a game-theoretic “testing-by-betting” interpretation [14], [15].

Under \(\mathcal{H}_0^{\text{ex}}\), a stochastic process \(M_0, M_1, ..., M_t, ...\) is a CTM if it is a nonnegative martingale—i.e., \(M_t\geq 0\) for all \(t\) and \(\mathbb{E}_{\mathcal{H}_0^{\text{ex}}}[M_t \mid M_0, ..., M_{t-1}] = M_{t-1}\)—constructed from a corresponding sequence of conformal \(p\)-values \(p_1, ..., p_t, ...\) via an appropriately defined “betting process.” That is, in the game-theoretic interpretation, a bettor has initial wealth \(M_0\), and at each time \(t=0, 1, ...\), she may use wealth \(M_t\) to bet on the value of \(p_{t+1}\) to be observed next; once \(p_{t+1}\) is revealed, she receives her reward and/or pays her losses, resulting in a new total wealth \(M_{t+1}\). The bettor bets against the null hypothesis \(\mathcal{H}_0^{\text{ex}}\): if \(\mathcal{H}_0^{\text{ex}}\) is true, then \(P_t \stackrel{iid}{\sim} \text{Unif}[0,1]\) and she cannot expect to outperform random guessing; so, if the bettor grows her wealth by a large factor \(M_t/M_0>1\), this is evidence that the bettor “knows” an alternative hypothesis more accurate than \(\mathcal{H}_0^{\text{ex}}\) [10]. \(M_t/M_0\) can be taken as an “anytime-valid” evidence against \(\mathcal{H}_0^{\text{ex}}\)—in other terms, \(M_t/M_0\) is an “\(e\)-value” for \(\mathcal{H}_0^{\text{ex}}\) at all \(t\) [8], [16].

More formally, define a betting function as a function \(g:[0, 1]\rightarrow [0, \infty]\) that integrates to one, i.e., \(\int_0^1g(u)\text{d}u=1\). We follow [10] and assume the betting function \[\begin{align} g_{\epsilon}(p) := 1 + \epsilon (p - 0.5), \label{eq:betting95function} \end{align}\tag{6}\] where \(\epsilon\in \mathbf{E}:= \{-1, 0, 1\}\) (\(\mathbf{E}\) is selected somewhat arbitrarily). The intuition is that \(\epsilon<0\) corresponds to betting on smaller \(p\)-values, \(\epsilon>0\) corresponds to betting on larger \(p\)-values, and \(\epsilon=0\) represents not betting. A CTM can be constructed by selecting a betting strategy \(g_{\epsilon_t}\) at each time \(t\) that may depend only on the past \(p\)-value observations \(p_1, ..., p_{t-1}\); this paper uses the “composite jumper martingale” strategy described in [12]. Then, a conformal (test) martingale \(M_t : [0, 1]^* \rightarrow [0, \infty], t=0, 1, ...\), can be constructed by accumulating the “wealth” attained by the previous bets on the conformal \(p\)-values, \(p_1, p_2, ...\), \[\begin{align} M_t := \int \Big(\prod_{i=1}^tg_{\epsilon_i}(p_i)\Big)\nu\big(\text{d}(\epsilon_0, \epsilon_1, ...)\big), \;\forall \;t, \label{eq:ctm95wealth95def} \end{align}\tag{7}\] where \(\nu\) is the composite jumper Markov chain described by [12] to determine how the “wealth” values are spread across the betting space \(\mathbf{E}\) at each timepoint.

A standard CTM (Eq. 7 ) can be used to test the exchangeability null \(\mathcal{H}_0^{\text{ex}}\) (Eq. 4 ) online either by using \(M_t/M_0\) as an anytime-valid evidence metric, or by raising an alarm when \(M_t/M_0\) exceeds some user-defined threshold \(c\). That is, by Ville’s inequality for martingales [17], CTMs achieve anytime-valid control over the false alarm rate (i.e., over the probability of an alarm despite \(\mathcal{H}_0^{\text{ex}}\) being true), \[\begin{align} \mathbb{P}_{\mathcal{H}_0^{\text{ex}}}\big(\exists \;t : M_t / M_0 \geq c\big) \leq 1/c, \label{eq:ctm95anytime95valid95guarantee} \end{align}\tag{8}\] which is sometimes referred to as strong validity due to its control over ever raising a false alarm [10].

2.4 Weighted Conformal Prediction for Adapting to Distribution Shifts↩︎

Whereas Standard CP computes valid predictive confidence sets assuming exchangeable data, weighted conformal prediction (WCP) (e.g., [18]–[22]) generalizes Standard CP to attain valid coverage (Eq. 1 ) even under various distribution shifts. Weighted CP methods are thus an approach to adapting to distribution shift, that is by computing CP sets on a reweighted version of the empirical calibration set’s scores, which in effect can modulate the size of the prediction sets to maintain coverage.

As we will see in the next section, weighted CP methods are associated with weighted-conformal \(p\)-values, a special-case of which was introduced in [23] for standard covariate shifts, based on [18]. Most recently, [22] also leverage weighted-conformal \(p\)-values to unify various theories of conformal prediction. However, there are several key differences with our contributions: regarding motivation, that work discusses connections to (one-shot) hypothesis testing as a means of framing conformal prediction, while in our paper (sequential) hypothesis testing is the primary focus; the conformal \(p\)-values in that paper are deterministic and conservative to attain conservative validity, whereas we incorporate randomness to achieve exact validity; lastly, whereas that paper primarily focuses on a batch-data setting where all the data are observed simultaneously, we focus on an online monitoring setting where each \(p\)-value is determined only by the current and past data, and we importantly present new theory for when a sequence of WCP \(p\)-values can be distributed uniformly and independently.

3 Theory and Methods: Weighted- Conformal \(p\)-Values and Test Martingales↩︎

Our main theory and method contribution is to introduce weighted-conformal test martingales (WCTMs), constructed from a generalized version of weighted-conformal \(p\)-values, which expand the scope of their standard conformal analogs. WCTMs enable more customizable and informative alarm criteria than standard CTMs, and our specific variants enable adaptation to mild shifts, while in response to severe shifts they raise alarms and enable root-cause analysis.

3.1 Generalized Weighted-Conformal \(p\)-Values↩︎

In this section we present a general version of weighted-conformal \(p\)-values.⁵ Sequences of these generalized weighted-conformal \(p\)-values will lay a theoretical foundation for online testing of a broad range of null hypotheses beyond exchangeability. To begin, observe that standard conformal \(p\)-values (Eq. 2 ) can be equivalently written as \[\begin{align} p_{n+1} = \sum_{i=1}^{n+1}\frac{1}{n+1}\Big[\text{\usefont{U}{bbm}{m}{n}1}\{v_i > v_{n+1}\} + u_{n+1}\text{\usefont{U}{bbm}{m}{n}1}\{v_i = v_{n+1}\}\Big], \end{align}\] where the purpose of this notation is to isolate where the comparison of \(v_{n+1}\) to each \(i\)-th score is given uniform weight \(\tfrac{1}{n+1}\). For some arbitrary weight vector \(\tilde{w} = (\tilde{w}_1, ..., \tilde{w}_{n+1})\in [0,1]^{n+1}\) where \(\sum_{i=1}^{n+1}\tilde{w}_i=1\), it is then straightforward to define weighted-conformal \(p\)-values as \[\begin{align} p_{n+1}^{\tilde{w}} = \sum_{i=1}^{n+1}\tilde{w}_i\Big[\text{\usefont{U}{bbm}{m}{n}1}\{v_i > v_{n+1}\} + u_{n+1}\text{\usefont{U}{bbm}{m}{n}1}\{v_i = v_{n+1}\}\Big]. \label{eq:weighted95p95vals95arbitrary95def} \end{align}\tag{9}\] Note that existing (split or full) weighted CP methods (e.g., [18], [19], [21] and certain methods in [20]) can be also be defined by weighted-conformal \(p\)-values by plugging \(p_{n+1}^{\tilde{w}}(X_{n+1}, y)\) in for \(p_{n+1}(X_{n+1}, y)\) in Eq. 3 , where \(\tilde{w}\) is an appropriately chosen weight vector.⁶

To understand the meaning of the weights \(\tilde{w}\) for our hypothesis testing purpose, we draw from the general view of weighted CP described in [21], which expounded analysis from [18]: For setup, let \(E_z\) denote the event \(\{Z_1, ..., Z_{n+1}\} = \{z_1, ..., z_{n+1}\}\), meaning that the empirical distribution of the datapoints has been observed, but we do not know whether \(Z_{i}=z_i\), and so on. Then, the oracle weights \(\tilde{w}^o\) would be given by entries \[\begin{align} \label{eq:general95weights} \tilde{w}_i^o = & \;\mathbb{P}\{V_{n+1} = v_i \mid E_z\} \\ = & \;\frac{\sum_{\sigma:\sigma(n+1)=i}f(z_{\sigma(1)}, ..., z_{\sigma(n+1)})}{\sum_{\sigma}f(z_{\sigma(1)}, ..., z_{\sigma(n+1)})},\nonumber \end{align}\tag{10}\] where \(f\) is the joint probability density function (PDF) and \(\sigma\) is a permutation of \([n+1]\). In words, the oracle weight \(\tilde{w}_i^o\) we would ideally use for \(\tilde{w}_i\) is the probability that the test score \(V_{n+1}\) took on the value \(v_i\), conditioned on the empirical distribution \(E_z\). For further exposition, see [21]. While for arbitrary \(f\), computing Eq. 10 is intractable due to requiring knowledge of \(f\) and the factorial complexity, we next turn to how simplifying or approximating \(\tilde{w}^o\) can be useful in practical hypothesis testing.

3.2 Expanded Hypothesis Testing with Weighted-Conformal \(p\)-Values↩︎

A main theoretical insight in our paper is that the weighted-conformal \(p\)-values introduced in Eq. 9 can be used to test a variety of null hypotheses that are broader than exchangeability. Let us begin by using \(\mathcal{H}_0(\hat{f})\) to denote any set of assumptions on \(f\) used to estimate Eq. 10 , and hereon let \(\tilde{w}:= \tilde{w}(\mathcal{H}_0(\hat{f}))\) denote the weight vector computed with this approximation. For example, if we assume exchangeability as our null hypothesis (\(\mathcal{H}_0(\hat{f})=\mathcal{H}_0^{\text{(ex)}}\)), then \(f(z_{\sigma(1)}, ..., z_{\sigma(n+1)})=f(z_{1}, ..., z_{n+1})\) and Eq. 10 reduces to \(\tilde{w}_i=\frac{1}{n+1}\), which recovers standard conformal \(p\)-values. More generally, \(\mathcal{H}_0(\hat{f})\) can denote some other set of invariance assumptions on \(f\) or density-ratio estimates (see Sec. 3.3 for an example). Then, assuming \(\mathcal{H}_0(\hat{f})\), the weights \(\tilde{w}\) yield a weighted empirical distribution \[\begin{align} \label{eq:weighted95conditional95score95dist} V_{n+1}\mid E_z \sim \sum_{i=1}^{n+1}\tilde{w}_i\delta_{v_i}, \end{align}\tag{11}\] from which it follows (via the probability integral transform and marginalizing over the draw of \(E_z\)) that \(P^{\tilde{w}}_{n+1}\) is IID uniformly distributed on [0, 1] and is thus a valid \(p\)-value for testing \(\mathcal{H}_0(\hat{f})\). We next state this formally.

We defer the proof to Appendix 7. The proof builds on those for standard CTMs in [24] and [25], which leverage the idea of “reversing time.” That is, we imagine that the sequence of data observations \((z_1, ..., z_T)\) is generated in two steps: first, the unordered bag or multiset of data observations, \(\{z_1, ..., z_T\}\), is generated from some probability distribution; then—here generalizing [24] and [25] by weighting permutations according to their likelihood—from all possible permutations \(\sigma\) of the values \(\{z_1, ..., z_T\}\), each possible sequence \((z_{\sigma(1)}, ..., z_{\sigma(T)})\) is chosen with probability proportional to \(f(z_{\sigma(1)}, ..., z_{\sigma(T)})\), where \(f:=f_Z\) is the probability-density function⁷ for the distribution \(F_Z\). Roughly (ignoring borderline effects), the second step ensures that, conditionally on knowing \(\{z_1, ..., z_T\}\) (and therefore unconditionally), that \(P_{T}^{\tilde{w}^o}\) has a standard uniform distribution; when \(Z_T=z_{\sigma(T)}\) is observed, this settles the value of \(P_{T}^{\tilde{w}^o}=p_{\sigma(T)}^{\tilde{w}^o}\), and conditionally on knowing \(\{z_1, ..., z_T\}\) and \(Z_T=z_{\sigma(T)}\) (and therefore, after relabeling indices, on knowing \(\{z_1, ..., z_{T-1}\}\)), that \(P_{T-1}^{\tilde{w}^o}\) also has a standard uniform distribution, and so on.

3.3 Main Practical Testing Objective: Testing for {Concept Shift or Unanticipated Covariate Shift}↩︎

We now provide a worked example for how weighted-conformal \(p\)-values can be used to test a common assumption in the robust ML literature: namely, the covariate shift [26], [27] assumption, where the marginal input distribution \(F_X\) may shift to some other distribution \(F_X^T\) at test time, but the conditional label distribution \(F_{Y \mid X}\) is assumed to remain invariant. Under the covariate shift assumptions, the oracle weights \(\tilde{w}_i^o\) in Eq. 10 are proportional to density-ratio weights \(f_X^T(X_i)/f_X(X_i)\) [18]. A common goal is to adapt to covariate shift by reweighting data with this density ratio, which requires learning an approximate density-ratio function \(\widehat{f}_X^T(x)/f_X(x)\) (e.g., [18], [27]–[29]).

However, there is a need for testing for misspecifications in \(\widehat{f}_X^T(x)/f_X(x)\) or unsafe shifts in \(Y\mid X\), which our work enables. That is, by Theorem 1, weighted-conformal \(p\)-values (Eq. 9 ) with weights set by an approximated density-ratio function \(\tilde{w}_i=\widehat{f}_X^T(X_i)/f_X(X_i)\) permit testing the following null hypothesis: \[\begin{align} \label{eq:cs95null} \mathcal{H}_0^{\text{(cs)}} :=\begin{cases} (X_{i}, Y_{i}) \sim F_{Y \mid X}\times F_{X}=F_Z\in \mathbf{F_{Z}^{\text{ex}}} , \;& i \in [n] \\ (X_{n+t}, Y_{n+t}) \sim F_{Y \mid X}\times \widehat{F}_{X}^T, & t>0 \\ \qquad \qquad \qquad \quad F_{Y \mid X} \in \mathbf{F^{\text{ex}}_{Y \mid X}}& \end{cases} \end{align}\tag{13}\] which can be roughly read as assuming both that \(Y\mid X\) is invariant and that \(\widehat{f}_X^T(x)/f_X(x)\) is a close approximation of the true density ratio function. Thus, observing a small value of \(p^{\tilde{w}}_{n+1}\) would convey evidence against \(\mathcal{H}_0^{\text{(cs)}}\), meaning that there has either been a concept shift in \(Y\mid X\) or that the density-ratio adaptation \(\widehat{f}_X^T(x)/f_X(x)\) is inaccurate.

3.4 Weighted-Conformal Test Martingales for Continual Monitoring↩︎

With Theorem 1 at hand, weighted-conformal test martingales (WCTMs) can be constructed from a sequence of weighted-conformal \(p\)-values to enable continual, anytime-valid monitoring of a customizeable null hypothesis \(\mathcal{H}_0(\hat{f})\). Just as in the construction of standard CTMs (Section 2.3), WCTMs require a betting function \(g\) (we assume the betting function in Eq. 6 ) and a strategy \(\nu\) for placing bets \(\epsilon_t\) at each time \(t\) that can only depend on past \(p\)-value observations (we use the composite jumper strategy from [12]). Then, a WCTM is constructed by feeding a sequence of weighted-conformal \(p\)-values \(p_1^{\tilde{w}(\hat{f})}, ..., p_t^{\tilde{w}(\hat{f})}, ...\) into Eq. 7 (i.e., by setting \(p_i:=p_i^{\tilde{w}(\hat{f})}\) in Eq. 7 ). Due to the \(P_t^{\tilde{w}}\) being distributed IID uniformly on [0,1] (Theorem 1), the stochastic process \(\tilde{M}_0, \tilde{M}_1, ..., \tilde{M}_t\) is a nonnegative test martingale for \(\mathcal{H}_0(\hat{f})\), and by Ville’s inequality [17] it achieves the anytime-valid control over false alarms in the following theorem (proof in Appendix 7).

However, the strength of Eq. [thm:wctm95anytime95valid95guarantee] can sometimes be overly conservative. Thus, to improve the efficiency (speed in detecting true shifts), we can follow [2], [10] by moreover augmenting WCTMs with standard changepoint detection metrics such as CUSUM [30] and Shiryaev-Roberts [31], [32] while achieving a weaker form of multistage validity. For example, consider the Shiryaev-Roberts procedure applied to WCTMs \(\tilde{M}_t\), whose \(k\)-th stage alarm time is \[\begin{align} \tau_k := \min\big\{t > \tau_{k-1} : \sum_{i=0}^{t-1}\frac{\tilde{M}_t}{\tilde{M}_i}\geq c\big\}, \;k \in \mathbb{N}. \label{eq:SR95procedure} \end{align}\tag{14}\] This Shiryaev-Roberts procedure based on standard CTMs controls the average run length (ARL) under \(\mathcal{H}_0(\hat{f})\), where the procedure is expected to be reset after \(c\) timesteps.

3.5 WCTM Implementation in WATCH: Dynamic Online Adaptation and Root-Cause Analysis↩︎

All our implementations and experiments in this paper focus on WCTMs that continuously adapt to mild covariate shifts (e.g., Fig 1a) while raising alarms in response to either extreme covariate shifts (e.g., Fig 1b) or concept shifts in \(Y|X\) (e.g., Fig 1c). These goals correspond to monitoring the \(\mathcal{H}_0^{(cs)}\) null hypothesis given in Eq. 13 . Our adaptation procedure performs online density ratio estimation with an online probabilistic classifier (e.g., a logistic regression model similar to in [29]) to update the estimation of \(\widehat{f}_X^{T(t)}(x)/f_X(x)\) at each timestep \(t\).

Online Adaptation with Dynamic Initialization  For the initial adaptation stage, a key question is when to begin the adaptation procedure, or when to begin estimating \(\widehat{f}_X^{T(t)}(x)/f_X(x)\). Our methods make this determination automatically and dynamically by running a secondary standard CTM that is restricted to only monitoring for changepoints in the marginal \(X\) distribution via a nearest-neighbor nonconformity score [2]. At deployment, the main WCTM method is initially a standard CTM (with uniform weights); then, once the secondary “\(X\)-CTM” method exceeds a pre-determined adaptation threshold (see gray paths in Fig 1) at some time \(t_{\text{ad}}\), this triggers the adaptation of the main WCTM monitoring method (blue paths in Fig 1) and corresponding weighted CP intervals. For efficiency purposes, after the adaptation time \(t_{\text{ad}}\), the CP calibration set \([n+t_{\text{ad}}]\) is treated as fixed (no longer adding test points to it online), meaning the weighted-conformal \(p\)-values are computed summing only over \([n+t_{\text{ad}}]\cup \{n+t\}\), \[\begin{align} p_{n+t}^{\tilde{w}} = \sum_{i\in[n+t_{\text{ad}}]\cup \{n+t\}}\tilde{w}_i^{(t)}\Bigg[\begin{matrix}\text{\usefont{U}{bbm}{m}{n}1}\{v_i > v_{n+t}\} \quad \quad \\ + u_{n+t}\text{\usefont{U}{bbm}{m}{n}1}\{v_i = v_{n+t}\}\end{matrix}\Bigg], \label{eq:weighted95p95vals95fixed95cal} \end{align}\tag{15}\] where here \(\tilde{w}_i^{(t)}\propto \widehat{f}_X^{T(t)}(X_i)/f_X(X_i)\).

Root-Cause Analysis with Parallelized WCTM and \(X\)-CTM  The parallel implementation of both the primary WCTM and the secondary \(X\)-CTM method furthermore enables root-cause analysis, that is to determine whether performance degradation was due to a harmful covariate shift (Fig 1b) or a fundamental concept shift (Fig 1c). That is, if both the WCTM and the \(X\)-CTM have detected changepoints, then a harmful shift can be diagnosed as an extreme covariate shift (Fig 1b); on the other hand, if the \(X\)-CTM does not detect a changepoint, this suggests that no covariate shift is present, and the WCTM alarm was instead due to a concept shift in \(Y|X\) (Figure 1).

4 Experiments↩︎

We conduct a comprehensive empirical analysis of the WATCH framework on real-world datasets with various distribution shifts. Our results show that WATCH adapts effectively to benign shifts (Section 4.1) and triggers alarms only when it fails to adapt (Section 4.2), while also detecting potentially harmful shifts with minimal delay (Section 4.3). Details on the datasets, models, and additional results, can be found in Appendix 8. Code to reproduce all experiments is available at the following repository: https://github.com/aaronhan223/wtr.

Baselines  We compare the proposed WCTM methods that constitute WATCH against standard CTMs [2] in all experiments. To evaluate detection speed on true harmful shifts (sec 4.3), we also compare against methods for directly performing sequential hypothesis testing and changepoint detection on the set-prediction miscoverage risk, as proposed by [3].

In all experiments and for all baselines, the underlying ML predictor being monitored was a neural network. On the tabular data, we used the scikit-learn [33] MLPRegressor (with L-BFGS solver and logistic activation); for the image data, we used a 3-layer MLP with ReLU activations on the MNIST datasets and a ResNet-32 [34] on CIFAR-10 datasets. For weight estimation, we use a 3-layer MLP with ReLU activations to distinguish between source and target distributions.

4.1 WCTMs Adapt to Mild and Benign Shifts to Avoid Unnecessary Alarms↩︎

WCTMs Adapt to Benign Covariate Shifts  Figure 2 compares the average performance (across 200 random seeds) of WCTMs to standard CTMs across 3000 sequentially-observed test datapoints, where the true changepoint shift is induced after the 500th test point. From the conformal coverage plots in the first column, it is clear that all the shifts are benign in that coverage for the corresponding (standard or weighted) CP methods—a metric of prediction safety—does not degrade below the target level (0.9) after the changepoint. In fact, for the baseline method (orange), coverage increases, which could be considered a “beneficial” shift; nonetheless, the standard CTM raises unnecessary alarms across all datasets, for both its anytime-valid (fourth column) and scheduled (fifth column) monitoring criteria. In contrast, the proposed WCTM (blue) avoids these unnecessary alarms across all datasets and both monitoring criteria. That is, the WCTM adapts to the benign covariate shift by decreasing its interval widths (second column)—indicating more informative predictions—while maintaining target coverage. The relatively uniform distribution of the postchangepoint weighted \(p\)-values (third column, blue) is empirical evidence validating Theorem 1; meanwhile, the martingale (fourth column) and Shiryaev-Roberts (fifth column) WCTM paths avoiding alarms supports Theorems 2 and 3 respectively.

4.2 From Mild to Extreme Covariate Shifts: WCTMs Raise Alarms if Unable to Adapt↩︎

We demonstrate such a property of WCTM using image corruption experiments. The models were trained on original clean data and then evaluated on corrupted variants. To enable greater flexibility in controlling the level of distribution shift, we combine clean and corrupted samples using self-defined mixture ratios when defining the source and target distributions. Figure 3 illustrates the behavior of WCTM in comparison to CTM on CIFAR-10 under varying levels of brightness corruption. When the target distribution is completely clean (a), neither method triggers a false alarm, but the martingale paths of WCTM are more stable. We then introduce level-1 brightness corruption while retaining over \(50\%\) clean samples (b), creating a very mild, benign shift. In this scenario, CTM quickly raises an unnecessary alarm, whereas WCTM successfully avoids it. Next, we increase the corruption to level-3 and reduce the clean-sample ratio to \(40\%\) (c). Although WCTM reacts to this shift, it still does not trigger an alarm. Finally, at corruption level-5, with the clean-sample ratio reduced to \(30\%\) (d), WCTM does raise the alarm. Throughout these changes, the baseline CTM shows little variation, while our method displays strong adaptivity to different degrees of distribution shift.

We conduct a quantitative evaluation of monitoring performance on the image corruption experiments. Our evaluation metrics include the average detection delay (ADD), following [3], the average number of unnecessary alarms and missed alarms. First, WCTM exhibits shorter detection delays compared to CTM. Given that CTM often doesn’t trigger alarms in the face of severe corruption, which significantly increases its overall ADD. Additionally, as the corruption level intensifies, WCTM detects shifts more quickly, whereas CTM’s detection speed shows minimal change—consistent with our earlier visualizations. To evaluate unnecessary alarms, we again create a mild, benign shift in the target distribution by mixing clean samples into MNIST and level-1 CIFAR-10 corruption data, while treating higher-level corruptions as harmful. We find that WCTM’s unnecessary alarm rate is roughly one-third that of CTM. Moreover, WCTM also exhibits fewer missed alarms, especially under more severe corruptions. These findings highlight the flexibility of our framework, which not only avoids unnecessary alarms but also better detects harmful shifts.

4.3 WCTMs Detect Harmful Concept Shifts Faster than Sequentially Tracking Loss Metrics↩︎

Because concept shifts fundamentally change the \(Y|X\) relationship, they are generally harmful, and monitoring methods should detect them as quickly as possible. Our experiments compare the average detection delay (ADD) of WCTM methods relative to comparable CTM methods, as well as against methods for sequentially tracking the loss metrics directly with comparable false-alarm control. That is, the sequential testing procedures proposed in [3] (PR-ST) have anytime-valid control comparable to (W)CTMs, while the changepoint detection procedure in [3] (PR-CD) has average-run-length control comparable to running the Shiryaev-Roberts procedure 14 on top of (W)CTMs. Both PR-ST and PR-CD methods can be used to monitor the miscoverage risks of either weighted CP or standard CP methods, though they are less data efficient (requiring an extra holdout set for computing concentration inequalities). We compared to the betting-based -process in [3] (with \(\epsilon_{\text{tol}}=0\)) because those methods were reported to perform the best and are more comparable to (W)CTMs, which are also betting-based. We compared WCTMs to sequential testing variant with standardized anytime-false alarm rate of 0.01; for SR-WCTMs we compared vs changepoint detection variant with common average-run-length (under the null) of 20,000.

Table 1 reports the average detection delay (ADD) results for monitoring methods grouped by false-alarm control type, with proposed methods in blue. Among the anytime-valid monitoring methods, WCTMs and CTMs achieve comparably fast ADD; however, relative to comparable PR-ST methods, (W)CTMs are over three times faster. Meanwhile, among the stagewise monitoring methods, WCTM and CTM-based SR procedures are comparable, but with significantly faster ADD than PR-CD run either online or in minibatches. PR-CD-online has lower ADD than in minibatches, but its wall-clock runtime is far slower—this is due to the method’s \(\mathcal{O}(t^2)\) time complexity, whereas the proposed WCTM and SR-WCTM methods are \(\mathcal{O}(t)\).

5 Summary and Future Directions↩︎

In this paper we introduced novel weighted conformal test martingales (WCTMs), which we constructed from sequences of weighted conformal \(p\)-values, and we demonstrated how WCTMs enable continual monitoring of deployed AI/ML models via flexible sequential hypothesis testing for changepoints. The proposed approach, WATCH, continuously adapts to benign covariate shifts without raising unnecessary alarms, while also detecting harmful shifts more rapidly. Our empirical results show that WATCH’s adaptation reduces unnecessary alarms relative to standard CTMs [2] while still detecting harmful shifts faster than comparable betting-based \(e\)-processes that directly track the risk (i.e., from [3]). WATCH is further able to perform root-cause analysis to diagnose whether a harmful shift causing degradation was an extreme covariate shift or a fundamental concept shift. Promising future theory directions include developing WCTMs for testing other data-generating assumptions, connections to conditional permutation tests [35], and finer-grained root-cause analysis. For applications, extensions of WATCH to monitor the risks of generative models and AI agents could be valuable.

Impact Statement↩︎

This paper presents research aimed at propelling advancements in the broad domain of machine learning. The implications of our findings are wide-ranging, with potential high-stake applications in sectors including healthcare, autonomous driving, and e-commerce. Based on our current understanding, this research does not warrant an ethics review, and a detailed discussion of the potential societal impacts is not required at the current stage.

Acknowledgements↩︎

D.P. was funded by a PhD fellowship from the Amazon Initiative for Interactive AI (AI2AI); D.P., X.H., A.L., and S.S. were partially funded by the Gordon and Betty Moore Foundation grant #12128; D.P., X.H., and S.S. were partially funded by National Science Foundation (NSF) grant #1840088. A.L. is also supported by an Amazon Research Award. The authors would like to thank Yaniv Romano for helpful discussions on a draft of this paper; Jwala Dhamala and Jie Ding for helpful discussions throughout the JHU + AI2AI collaboration; and the anonymous ICML reviewers for informative feedback.

6 Related Works↩︎

This work is motivated by developing methods for monitoring AI/ML deployments that perform three key functions: (1) online adaptation to mild or benign data shifts; (2) rapid detection of extreme or harmful shifts that necessitate updates; and (3) identifying the root-cause of degradation to inform appropriate recovery. Although these monitoring goals could be viewed from many perspectives, in discussing related work we primarily focus on methods in anytime-valid inference, sequential testing of nonparametric null hypotheses, and especially conformal test martingales, which most closely related to our own.

Sequential testing for changepoints in the data distribution: Sequential hypothesis testing to detect changes in the data distribution is an old and widely-studied problem, dating at least to Wald’s sequential probability ratio test [36]. However, classic sequential changepoint detection methods often required a prespecified stopping time and were primarily designed for testing simple, often parametrically-specified null hypotheses—for an overview of classic parametric methods, we defer to a relevant textbook [37] and review articles [38], [39]. In contrast, our weighted-conformal test martingale (WCTM) methods belong to a more recent literature called sequential anytime-valid inference (SAVI), which allow for arbitrary stopping times, and specifically our work is situated in the recent SAVI literature on testing composite and nonparametric null hypotheses. We refer readers to [8] for a recent review of the SAVI literature, as well as to the textbook by [14] on the closely related topic of testing-by-betting.

Standard conformal test martingales: Within the SAVI literature, our work is most closely related to conformal test martingales (CTMs), which are martingales constructed from a sequence of standard conformal \(p\)-values for continually testing the assumption that the data are exchangeability or independent and identically distributed (IID). Our WCTM methods generalize standard CTMs for testing a broader range of null hypotheses, including those where one wishes to accommodate or adapt to certain anticipated changes in the data distribution (e.g., adapting to mild covariate shifts). Standard CTMs were initially introduced by [25], while drawing on theory for the calibration of online conformal prediction methods developed in [24]. Since then, various works have further developed standard CTMs, such as by introducing new betting and score functions for more efficient changepoint detection, ensembling CTMs, and demonstrating their performance on real-world applications [2], [9], [10], [40]–[44]. CTMs are also discussed in textbooks on conformal prediction [45], [46].

In particular, [9] developed inductive CTMs (i.e., CTMs based on inductive or split conformal [11], [47]) with score and betting functions specifically taylored to fast changepoint detection; [2] proposed an approach to using standard CTMs to monitor for when a deployed AI/ML system should be retrained; and [10] provided a comprehensive and detailed review of CTMs as methods for testing the IID or exchangeability assumptions. [48] implement methods based on CTMs for test time-adaptation of a classifier’s point prediction and [49] leverage multiple CTMs over different feature spaces to aid in diagnostic runtime monitoring. Several works have developed or used CTMs for testing for concept shift (i.e., shift in \(Y\mid X\)) [40], [43], [44], [50], but all of these have focused on a classification setting with a limited number of classes (e.g., to implement label-conditional CTMs, or using standard CTMs that lack ability to disambiguate between covariate and concept shifts). In contrast, our specific WCTMs implemented in this paper are able to test for concept shift in both regression and classification settings while also being able to disambiguate between concept shifts and extreme covariate shifts with the aid of an additional \(X\)-CTM.

Confidence sequences, \(e\)-processes, and other multiple-hypothesis testing methods: Our work also relates more broadly to other SAVI and testing-by-betting methods outside of CTMs such as confidence sequences and \(e\)-processes—we refer to the review paper of [8] for full exposition of these topics. In particular, in the main paper we empirically compared our WCTM methods against the betting-based sequential testing and changepoint detection methods in [3] (the theory for which was developed in [51]) because this paper is the closest to ours in its motivation of monitoring deployed AI/ML deployments among (non-CTM) SAVI papers. As we note in the main paper, for monitoring the risk of a set-valued (e.g., conformalized) AI/ML predictor, our WCTM methods are generally more data-efficient (not requiring separate datasets for conformalization and testing, as [3] does); our WCTM-based Shiryaev-Roberts procedure is more computationally efficient than the compareable changepoint detection method in [3] (i.e., \(\mathcal{O}(t)\) versus \(\mathcal{O}(t^2)\)); and, empirically we found that our methods often detect harmful concept shifts faster than comparable methods in [3]. More recently, [52] built on [3] by developing similar methods for when ground-truth labels do not become available and need to be estimated.

A key target of the SAVI literature on testing composite or nonparametric null hypotheses has been developing new approaches for testing the IID or exchangeability assumptions. Other than CTMs, the other main nontrivial approach to sequentially testing exchangeability was developed in [53] based on the ideas of universal inference [54]; more recently, other approaches have emerged based on pairwise betting [55] and sequential Monte Carlo testing [56], the latter of which can be viewed as a special case of CTMs [10] streamlined for a particular alternative hypothesis. Otherwise, there are various and proliferating other methods for sequential nonparametric changepoint detection (e.g., [57]–[61]). SAVI and testing-by betting methods are also being leveraged for a wide variety of applications including interpretability [62], conditional independence testing [63], applications in finance [14], and more.

Testing-by-betting, which is fundamental to SAVI [8], can be understood as one approach to multiple hypothesis testing that is especially advantageous in sequential settings. Other related works that leverage conformal prediction for hypothesis testing while accounting for multiple-testing corrections, but in batch settings, include [64]–[68].

Weighted conformal prediction and adapting to distribution shifts: Weighted conformal prediction (e.g., [18]–[20], [22], [28], [69]–[76]) is broadly an approach to proactively adapting the validity of conformal predictive sets to distribution shift by reweighting nonconformity scores using either knowledge or estimates of the distribution shift. Any weighted CP prediction set is associated with a weighted-conformal \(p\)-values, as described in the main paper; accordingly, a WCTM can be constructed on top of any weighted CP method deployed on a sequence of data observations to continually monitor the assumptions or approximations underlying that WCP method’s implementation. There are of course many other approaches to adapting to distribution shifts at test time; for example, one work that is similar to ours with regard to this motivation, but that does not fall under weighted CP, is [48], which leverages standard CTMs to guide the test-time adaptation of a classifier’s point prediction by entropy matching.

7 Proof of Theorems↩︎

7.1 Proof for Theorem 1 (Weighted Conformal \(p\)-value Validity)↩︎

The proof can be viewed as a generalization of the proofs for Theorem 1 in [25] and Theorem 2 in [24], while drawing on analysis from [18] and exposition and discussion from [21]. The key difference relative to [24] and [25] is that, whereas those papers use the assumption of exchangeability to place equal weight on every permutation of the data observations, here we avoid this assumption by first proving a general result for an arbitrary (potentially non-exchangeable) joint distribution. We then describe how this implies that the validity of more specific and tractable methods is premised on the assumptions or approximations used for practical implementation.

The basic idea for the proof begins with setup from [24], for “reversing time.” In particular, we imagine that the sequence of data observations \((z_1, ..., z_T)\) is generated in two steps: first, the unordered bag or multiset of data observations, \(\{z_1, ..., z_T\}\), is generated from some probability distribution (that is, the image of \(F_Z\) under the mapping \((z_1, z_2, ...) \rightarrow \{z_1, ..., z_T\}\)); then—here generalizing [24] and [25] by weighting permutations according to their likelihood—from all possible permutations \(\sigma\) of the values \(\{z_1, ..., z_T\}\), each possible sequence \((z_{\sigma(1)}, ..., z_{\sigma(T)})\) is chosen with probability proportional to \(f(z_{\sigma(1)}, ..., z_{\sigma(T)})\), where \(f:=f_Z\) is the probability-density function⁸ for the distribution \(F_Z\). Roughly (ignoring borderline effects), the second step ensures that, conditionally on knowing \(\{z_1, ..., z_T\}\) (and therefore unconditionally), that \(P_{T}^{\tilde{w}^o}\) has a standard uniform distribution; when \(Z_T=z_{\sigma(T)}\) is observed, this settles the value of \(P_{T}^{\tilde{w}^o}=p_{\sigma(T)}^{\tilde{w}^o}\), and conditionally on knowing \(\{z_1, ..., z_T\}\) and \(Z_T=z_{\sigma(T)}\) (and therefore, after relabeling indices, on knowing \(\{z_1, ..., z_{T-1}\}\)), that \(P_{T-1}^{\tilde{w}^o}\) also has a standard uniform distribution, and so on.

With Lemma 1 in hand, we can now proceed with the proof for the main theorem. Temporarily fix a positive integer \(T\); following the strategy of [25], we will first prove by induction that for any \(t=1, ..., T\) and any \(\alpha_1, ..., \alpha_t\in[0,1]^t\), that \[\begin{align} \label{eq:conditional95iid95bernoulli} \mathbb{P}\{P_t^{\tilde{w}^o} \leq \alpha_t, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \mid E_{z}^{(t)}\} = \alpha_t \cdots \alpha_1. \end{align}\tag{18}\]

For \(t=1\), Eq. 18 immediately follows from Lemma 1. For \(t>1\), by the law of total probability over \(\sigma(t)\) (i.e., over the last index value after drawing a permutation \(\sigma\) from \(E_z^{(t)}\)), the fundamental bridge between probability and expectation, and properties of the indicator function, we have \[\begin{align} \mathbb{P}&\{P_t^{\tilde{w}^o} \leq \alpha_t, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \mid E_{z}^{(t)}\} \\ & = \sum_{\sigma(t)=1}^t\mathbb{P}\{P_t^{\tilde{w}^o} \leq \alpha_t, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \mid E_{z}^{(t)}, Z_t = z_{\sigma(t)}\}\cdot \mathbb{P}\{Z_t = z_{\sigma(t)} \mid E_{z}^{(t)}\}\\ & = \sum_{\sigma(t)=1}^t\mathbb{E}\big[\text{\usefont{U}{bbm}{m}{n}1}\{P_t^{\tilde{w}^o} \leq \alpha_t, ..., P_1^{\tilde{w}^o} \leq \alpha_1\} \mid E_{z}^{(t)}, Z_t = z_{\sigma(t)}\big]\cdot \mathbb{P}\{Z_t = z_{\sigma(t)} \mid E_{z}^{(t)}\} \\ & = \sum_{\sigma(t)=1}^t\mathbb{E}\big[\text{\usefont{U}{bbm}{m}{n}1}\{P_t^{\tilde{w}^o} \leq \alpha_t\}\cdot\text{\usefont{U}{bbm}{m}{n}1}\{P_{t-1}^{\tilde{w}^o} \leq \alpha_{t-1}, ..., P_1^{\tilde{w}^o} \leq \alpha_1\} \mid E_{z}^{(t)}, Z_t = z_{\sigma(t)}\big]\cdot \mathbb{P}\{Z_t = z_{\sigma(t)} \mid E_{z}^{(t)}\} \end{align}\] Next, observe that conditioning on \(E_{z}^{(t)}\) and \(Z_t = z_{\sigma(t)}\) in the expectation term settles the value of \(\text{\usefont{U}{bbm}{m}{n}1}\{P_t^{\tilde{w}^o} \leq \alpha_t\}\) to be \(\text{\usefont{U}{bbm}{m}{n}1}\{p_{\sigma(t)}^{\tilde{w}^o} \leq \alpha_t\}\); that is, noting that the score function \(\widehat{\mathcal{S}}\) is bijective, \(\{E_{z}^{(t)}, Z_t = z_{\sigma(t)}\}\implies \{E_{z}^{(t)}, V_t = v_{\sigma(t)}\} \implies P_{t}^{\tilde{w}^o}=p_{\sigma(t)}^{\tilde{w}^o}\). So, \(\text{\usefont{U}{bbm}{m}{n}1}\{P_t^{\tilde{w}^o} \leq \alpha_t\}=\text{\usefont{U}{bbm}{m}{n}1}\{p_{\sigma(t)}^{\tilde{w}^o} \leq \alpha_t\}\) can be pulled out from the expectation to obtain \[\begin{align} \mathbb{P}& \{P_t^{\tilde{w}^o} \leq \alpha_t, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \mid E_{z}^{(t)}\} \\ & = \sum_{\sigma(t)=1}^t\text{\usefont{U}{bbm}{m}{n}1}\{p_{\sigma(t)}^{\tilde{w}^o} \leq \alpha_t\}\cdot\mathbb{E}\big[\text{\usefont{U}{bbm}{m}{n}1}\{P_{t-1}^{\tilde{w}^o} \leq \alpha_{t-1}, ..., P_1^{\tilde{w}^o} \leq \alpha_1\} \mid E_{z}^{(t)}, Z_t = z_{\sigma(t)}\big]\cdot \mathbb{P}\{Z_t = z_{\sigma(t)} \mid E_{z}^{(t)}\}. \end{align}\]

Now, observe that conditioning on \(E_{z}^{(t)}\) and \(Z_t = z_{\sigma(t)}\) implies that \(\{Z_1, ..., Z_{t-1}\}=\{z_1, ..., z_t\}\backslash \{z_{\sigma(t)}\}\), which we can denote as \(E_{z}^{(t-1)}\) (relabeling data indices as needed); in other words, observing the bag of \(t\) data values (i.e., observing \(E_{z}^{(t)}\)) and the value taken on by the \(t\)-th random variable (\(Z_t = z_{\sigma(t)}\)) implies that each of \(Z_1, ..., Z_{t-1}\) takes a value in \(\{z_1, ..., z_t\}\backslash \{z_{\sigma(t)}\}\). Moreover, as the value taken on by \(P_{t'}^{\tilde{w}^o}\) is a function of the values taken on by \(Z_1, ..., Z_{t'}\), the \(P_{t-1}^{\tilde{w}^o}, ..., P_{1}^{\tilde{w}^o}\) do not depend on the value of \(Z_t\), so \[\begin{align} \mathbb{P}& \{P_t^{\tilde{w}^o} \leq \alpha_t, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \mid E_{z}^{(t)}\}\\ & = \sum_{\sigma(t)=1}^t\text{\usefont{U}{bbm}{m}{n}1}\{p_{\sigma(t)}^{\tilde{w}^o} \leq \alpha_t\}\cdot\mathbb{P}\{P_{t-1}^{\tilde{w}^o} \leq \alpha_{t-1}, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \mid E_{z}^{(t-1)}\}\cdot \mathbb{P}\{Z_t = z_{\sigma(t)} \mid E_{z}^{(t)}\}. \end{align}\]

Using the inductive assumption and Lemma 1, this becomes \[\begin{align} \mathbb{P}\{P_t^{\tilde{w}^o} \leq \alpha_t, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \mid E_{z}^{(t)}\}& = \sum_{\sigma(t)=1}^t\text{\usefont{U}{bbm}{m}{n}1}\{p_{\sigma(t)}^{\tilde{w}^o}\leq \alpha_t\}\cdot\alpha_{t-1}\cdots\alpha_{1}\cdot \mathbb{P}\{Z_t = z_{\sigma(t)} \mid E_{z}^{(t)}\}\nonumber \\ & = \mathbb{P}\big\{P_t^{\tilde{w}^o}\leq \alpha_t \mid E_{z}^{(t)}\big\}\cdot\alpha_{t-1}\cdots\alpha_{1} \nonumber \\ & = \alpha_{t}\cdots\alpha_{1}, \end{align}\] which proves Eq. 18 . Note that Eq. 18 is a conditional result for any \(t=1, ..., T\); marginalizing over the event \(E_{z}^{(t)}\) and taking \(t=T\) implies \[\begin{align} \label{eq:unconditional95iid95bernoulli} \mathbb{P}\{P_T^{\tilde{w}^o} \leq \alpha_T, ..., P_1^{\tilde{w}^o} \leq \alpha_1 \} = \alpha_T \cdots \alpha_1. \end{align}\tag{19}\] We have proven that \(P_1^{\tilde{w}^o},P_2^{\tilde{w}^o}, ..., P_T^{\tilde{w}^o}\stackrel{iid}{\sim}\text{Unif}[0, 1]^T\); this implies the analogous result for the infinite sequence, that is, \(P_1^{\tilde{w}^o},P_2^{\tilde{w}^o}, ...\stackrel{iid}{\sim}\text{Unif}[0, 1]^{\infty}\) [25], [77].

Note that Eq. 19 holds in theory for an arbitrary joint PDF \(f\), but it is an abstract statement because it relies on the oracle weights in Eq. 17 , which are intractable due to requiring knowledge of \(f\) and factorial complexity. Thus, if the oracle weights in Eq. 17 are simplified using some assumptions or approximations on \(f\) (e.g., conditional independence or invariance assumptions, density-ratio estimations) that we denote by \(\mathcal{H}_0(\hat{f})\), and denoting the resulting approximated weights as \(\tilde{w}\), then the \(P_{t}^{\tilde{w}}\) are IID uniformly distributed, assuming \(\mathcal{H}_0(\hat{f})\): \[\begin{align} \label{eq:H040hat40f414195iid95bernoulli95app} \mathbb{P}_{\mathcal{H}_0(\hat{f})}\big\{P_T^{\tilde{w}} \leq \alpha_T, ..., P_1^{\tilde{w}} \leq \alpha_1 \big\}= \alpha_T \cdots \alpha_1. \end{align}\tag{20}\]

Eq. 20 implies that \(P_1^{\tilde{w}},P_2^{\tilde{w}}, ..., P_T^{\tilde{w}}\mid \mathcal{H}_0(\hat{f})\stackrel{iid}{\sim}\text{Unif}[0, 1]^T\). Similarly as before, this result for a fixed number of points \(T\) implies the corresponding result for infinite sequences [25], [77], that is, \(P_1^{\tilde{w}},P_2^{\tilde{w}},... \mid \mathcal{H}_0(\hat{f}) \stackrel{iid}{\sim}\text{Unif}[0, 1]^{\infty}\).

7.2 Proofs for Proposition 2 (WCTM Anytime False-Alarm Control) and Proposition 3 (Average-Run-Length Control for WCTM-based Shiryaev-Roberts Procedure)↩︎

The proofs for Proposition 2 and Proposition 3 follow from Theorem 1 and [10]’s results for standard conformal test martingales. By Theorem 1, weighted conformal \(p\)-values have IID uniform distribution on [0,1] premised on some assumptions \(\mathcal{H}_0(\hat{f})\). Thus, a sequence of weighted conformal \(p\)-values is a sequence of IID random variables drawn from [0,1], assuming that the null hypothesis \(\mathcal{H}_0(\hat{f})\) is true. Because the construction of a weighted conformal test martingale (e.g., Eq. 7 ) is only allowed to depend on the data via the sequence of weighted conformal \(p\)-values, we can draw from [10]’s results that construct betting martingales that only assume a sequence of IID uniform [0,1] random variables. That is, by construction, weighted conformal test martingales are a betting martingale [10] whose validity is premised on the assumptions \(\mathcal{H}_0(\hat{f})\) (used to compute the weights). Then, Proposition 2 follows by Ville’s inequality [17] and Proposition 3 follows from Proposition 4.2 in [10].

8 Experiment Details↩︎

8.1 Datasets↩︎

The evaluation datasets include both real-world tabular and image datasets. The tabular datasets are for regression tasks (where conformal methods used the absolute value residual nonconformity score \(\widehat{S}(x,y)=|y-\widehat{\mu}|\)), and the datasest span various sizes and dimensionalities: the Medical Expenditure Panel Survey (MEPS) dataset (33005 samples, 107 features) [78], the UCI Superconductivity dataset (21263 samples, 81 features) [79], and the UCI bike sharing dataset (17379 samples, 12 features) [80]. The image datasets were for classification tasks (where conformal methods used the one-minus-softmax score \(\widehat{S}(x,y)=1-\widehat{p}(y_i\mid x_i)\)) were the MNIST-corruption [81] (60000 clean samples, 10000 corrupted samples) and CIFAR-10-corruption [82] (50000 clean samples, 10000 corrupted samples), which are standard benchmarks for assessing distribution shifts.

8.2 Simulating Shifts in Tabular Data↩︎

To evaluate the online adaptation performance of our proposed WCTMs on the tabular, regression-task datasets, we simulated mild or benign covariate shifts by exponentially tilting (i.e., up-sampling) the test samples from the full dataset based on selected covariates. On the MEPS healthcare dataset, \(h\) was selected to simulate a demographic shift towards younger, higher-educated patients (expected to be a benign shift due to youth tending to correlate with fewer, less variable health issues). On the bike-sharing dataset, \(h\) simulated a shift in weather patterns to colder, windier days; meanwhile, a more complex shift was simulated on the superconductivity dataset by sampling proportional to the projection onto the first principal component representation of the training data. Harmful concept shifts in tabular data were simulated by biasing the label values as a function of selected input covariates for each dataset.

9 Additional Experimental Results↩︎

9.1 Root-Cause Analysis with WCTMs↩︎

9.2 What Makes a Covariate Shift Mild, Moderate, or Extreme?↩︎

While the distinction between mild, moderate, and extreme covariate shifts can be gradual, problem-specific, and sometimes user-driven, these disctinctions are not arbitrary, and WCTMs arguably even provide an approach to such delineation with statistical guarantees. Intuitively, benign shifts can be considered those where the “safety” of the CP coverage is maintained nontrivially (i.e., without the prediction set covering the whole label space). This intuition corresponds to the WCTMs’ null hypothesis (and, harmful shifts violate it), as follows:

• Benign: The betting martingale’s null hypothesis is that the WCP \(p\)-values are IID \(\text{Unif}[0, 1]\) (Appendix 7.2); this null implies that coverage is satisfied (exactly) for all \(\alpha\in(0,1)\) (ie, the martingale’s null \(\implies\) intuitive definition of “benign” regarding coverage validity).

• Harmful: (Contrapositive of the above.) If coverage is not satisfied (exactly) for some \(\alpha\in (0, 1)\), then the \(p_{t}^{\tilde{w}}\) are not IID \(\text{Unif}[0, 1]\) (ie, violation of coverage validity \(\implies\) violation of martingale’s null, thus possibility for detection). Larger violations are easier to detect, and thus more likely to quickly raise an alarm. Note that this can be due to under-coverage (safety violation) or over-coverage (uninformative prediction sets); we further penalize trivial overcoverage—i.e., when \(\widehat{C}(X_{n+t})=\mathcal{Y}\)—by using anticonservative WCP \(p\)-values whenever this occurs. (See pseudocode in Appendix 10.)

• Medium: A shift may initially be “harmful” as described above, due to density-ratio estimator having insufficient data, but later become “benign” once enough data has been collected.

Figure 5 provides an ablation study illustrating synthetic data example of WATCH performance for different magnitudes of covariate shift (in the input \(X\) distribution). Each row corresponds to a specific magnitude of covariate shift and illustrates WATCH’s response regarding coverage (prediction safety), interval widths (prediction informativeness), and WCTMs (monitoring criteria for alarms). The post-changepoint test points are sampled from the full source distribution with probabilities proportional to \(exp(|x-18|*\lambda)\); larger values of \(\lambda\) thus correspond to more severe covariate shift toward extreme (and particularly toward large) values of the input \(X\). Experiments are averaged over 20 seeds.

9.3 Ablation Experiments for Density-Ratio Weight Estimation↩︎

Another factor determining whether a covariate shift can be considered benign or harmful to deployment is whether a deployed density-ratio estimator is well-specified and thus able to approximate the shift. Figure 6 provides selected synthetic-data example where logistic regression is a misspecified probabilistic classifier for distinguishing between pre- and post-changepoint data, but where a neural network (MLP) is able to accurately discriminate between the same pre- and post-changepoint data. That is, in this example the pre- and post-changepoint data are not linearly separable in the input \(X\) domain, so logistic regression is not able to reliably discriminate, and thereby it is unable to reliably estimate density-ratio weights via probabilistic classification. The result is that the changepoint causes a large increase in coverage, despite some adaptation (decreasing interval widths); the estimator’s misspecification thus causes WCTMs to raise an alarm, indicating that the covariate shift cannot be adapted to by the estimator. In contrast, the MLP estimator is able to appropriately adapt by maintaing target coverage, improving interval sharpness, and avoiding unnecessary alarms.

9.4 Ablation Experiments for Betting Function↩︎

The primary role of the betting function in (W)CTMs and testing-by-betting more broadly is for quickly rejecting the null hypothesis (i.e., raising an alarm) when it is violated. Figure 7 provides ablation experiment on the betting function used for X-CTMs and WCTMs, on three settings of the synthetic-data example. The "Composite" Jumper betting function is the betting function used in all other experiments, and it is an average of Simple Jumper betting functions over “jumping parameters” \(J\in [0.0001, 0.001, 0.01, 0.1, 1]\); here, we set the Simple Jumper baseline to have \(J=0.01\). See Vovk et al. (2021) for pseudocode and exposition of the Simple Jumper algorithm. \(J=1\) means conservatively spreading bets across all options to avoid cumulative losses, while smaller \(J\) encourages “doubling down” on bets that were previously successful. The CTMs with Composite betting are thus lower bounded at \(M_t = 0.2\), whereas those with Simple betting continually decrease, resulting in slightly delayed detection speed relative to Composite.

9.5 WCTM Quickly Reacts to Harmful Shifts↩︎

For the image-data experiments, Figure 10 provides additional example results on harmful shifts with different corruption types.

9.6 Further Details of Image Classification Experiments↩︎

We provide further discussions on the image classification experiments from Section 4.2. Figure 11 demonstrates the coverage rates and set sizes of different corruption levels as discussed in the main paper. Details of model architectures and training configurations can be found in Table 3 - Table 6.

10 Algorithms↩︎

Only limited algorithm pseudocode is provided at this time; more comprehensive pseudocode will be included in a final version of this paper.

References↩︎