Technical Summary: Distribution-free Changepoint Localization after Sequential Change Detection

Problem Statement

The paper addresses the fundamental problem of sequential changepoint localization in an arbitrary observation space $\mathcal{X}$. While a vast body of literature exists on designing stopping rules (e.g., CUSUM, Shiryaev–Roberts, conformal test martingales) to detect when a distributional change occurs, there is a lack of rigorous methods to construct statistically valid confidence sets for the unknown changepoint $T$ after an alarm has been raised.

Existing post-detection inference methods (e.g., Ding, 2003a; Wu, 2007; Saha and Ramdas, 2026) typically require restrictive assumptions:

1. Known Distributions: The pre-change ($F_0$) and post-change ($F_1$) distributions must be known or belong to specific parametric families (e.g., exponential families).
2. Disjoint Classes: The sets of possible pre- and post-change distributions must be disjoint and known a priori.
3. Asymptotic Guarantees: Many provide only asymptotic coverage guarantees.

The authors aim to construct confidence sets for $T$ that satisfy finite-sample coverage guarantees without any distributional assumptions on $F_0$ and $F_1$, other than the assumption that they are distinct. The goal is to achieve conditional coverage:
$$P_{F_0,T,F_1}(T \in C \mid \tau \ge T) \ge 1 - \alpha$$
where $\tau$ is the stopping time of a sequential detector.

Methodology

The proposed framework decouples the detection phase from the localization phase. It acts as a "wrapper" around any existing sequential change detection algorithm (regardless of whether the detector itself is distribution-free). The core methodology relies on conformal test martingales and the exchangeability of data segments.

1. Core Assumptions

• Exchangeability: The pre-change segment $X_1, \dots, X_{T-1}$ is exchangeable (Assumption 2), and the post-change segment $X_T, X_{T+1}, \dots$ is exchangeable (Assumption 1).
• Black-Box Access: The localization procedure has access to the stopping time $\tau$ and the data sequence up to $\tau$, but treats the detection algorithm as a black box.
• Distribution-Free Estimation: An unbiased (or negatively biased) estimator $\hat{r}_t$ for the probability of no false alarm up to time $t$ ($P_{F_0, \infty}[\tau \ge t]$) is required. This can be estimated via Monte Carlo simulation using i.i.d. data from any convenient distribution, provided the detector's stopping time distribution under the null is independent of the specific $F_0$ (Assumption 3).

2. Construction of Confidence Sets

The method constructs one-sided confidence sets separately and intersects them to form a two-sided interval.

Lower Confidence Set ($C^{\alpha}_{low}$)

• Goal: Identify a time $t$ such that the true changepoint $T \ge t$.
• Hypothesis Test: For a candidate $t$, test $H_0: T = t$ against $H_1: T > t$.
• Mechanism: If $T > t$, the segment $X_t, \dots, X_\tau$ contains a mixture of pre- and post-change data, violating exchangeability. If $T = t$, the segment is purely post-change and exchangeable.
• Procedure:
  1. Compute sequential conformal p-values $p^j_t$ for $j \ge t$ based on score comparisons within the window $[t, j]$.
  2. Transform p-values into e-values using a calibrator function $f_{t,j}(p) = 1 + \lambda_{t,j}(p - 0.5)$.
  3. Aggregate evidence via a martingale $M_t = \prod f_{t,j}(p^j_t)$.
  4. Retain $t$ in $C^{\alpha}_{low}$ if the maximum martingale value over the window does not exceed the threshold $1/(\alpha \hat{r}_t)$.

Upper Confidence Set ($C^{\beta}_{up}$)

• Goal: Identify a time $t$ such that the true changepoint $T \le t$.
• Hypothesis Test: For a candidate $t$, test $H_0: T = t$ against $H_1: T < t$.
• Mechanism: Similar to the lower set but operates in the backward direction. If $T < t$, the segment $X_1, \dots, X_t$ contains a mixture, violating pre-change exchangeability.
• Procedure: Compute backward sequential conformal p-values $q^j_t$ for $j \le t$, aggregate via a martingale, and retain $t$ if the statistic remains below the threshold.

Two-Sided Confidence Set

The final confidence set is the intersection: $C = C^{\alpha}_{low} \cap C^{\beta}_{up}$. By the union bound, this satisfies $P(T \in C \mid \tau \ge T) \ge 1 - \alpha - \beta$.

3. Calibrator Learning

While theoretical bounds assume an "oracle" calibrator (optimally chosen $\lambda$), the paper proposes using online convex optimization (specifically Online Newton Step with Follow-The-Leading-History) to learn the sequence of $\lambda_{t,j}$ adaptively. This ensures logarithmic regret, maintaining the validity of the confidence sets while optimizing their size.

Key Contributions

1. First General Distribution-Free Framework: The paper introduces the first framework for post-detection changepoint localization that provides finite-sample coverage guarantees without requiring knowledge of $F_0$ or $F_1$, or assuming disjoint distribution classes ($P_0 \cap P_1 = \emptyset$).
2. Decoupling Detection and Inference: The method allows arbitrary sequential detectors (including those based on ARL or PFA control) to be wrapped with a distribution-free inference layer.
3. One-Sided and Two-Sided Constructions: The authors develop distinct constructions for lower and upper bounds, acknowledging the intrinsic asymmetry of sequential localization. They prove finite-sample coverage for both.
4. Non-Asymptotic and Asymptotic Bounds:
   • Finite-Sample: Explicit bounds on the conditional expected size of the confidence sets are derived.
   • Asymptotic: Under suitable regimes (where the detection delay scales logarithmically with the changepoint $T$), the expected size of the confidence set is shown to remain uniformly bounded (or grow sub-linearly), even without distributional assumptions.
5. Practical Estimation of Null Probabilities: A method to estimate the critical normalization term $\hat{r}_t$ via Monte Carlo simulation using arbitrary i.i.d. data, bypassing the need for the specific null distribution $F_0$.

Results

Theoretical Results

• Coverage: Theorem 1 and Theorem 2 establish that the lower and upper sets achieve conditional coverage of at least $1-\alpha$ and $1-\beta$, respectively. Corollary 1 extends this to the two-sided set.
• Size Bounds:
  • Theorem 3 & 4: For the lower confidence set, the expected pre-change length is $O(1)$ or $O(\log T)$ depending on the signal strength $\delta$ and the detection delay regime.
  • Theorem 5 & 6: For the upper confidence set, the expected post-change length is $O(1)$ under mild conditions on the detector's stopping time distribution.
  • Theorem 7 & 10: The combined two-sided set size is uniformly bounded or grows very slowly (sub-linearly) in $T$ under appropriate asymptotic regimes.
• Adaptive Learning: Theorems 8, 9, and 10 show that using online learning for calibrators (with logarithmic regret) preserves these bounds, with only minor adjustments to the constants.

Empirical Results

The authors validate the method on three datasets:

1. Gaussian Mean Change: Simulations with $N(-1, 1) \to N(1, 1)$. The method successfully localized the changepoint with tight confidence intervals (e.g., width $\approx 5$ for $T=500$).
2. MNIST Digit Change: A high-dimensional setting where the distribution shifts from digit '3' to '7' (or mixed distributions). Using a pre-trained CNN for scoring, the method achieved sharp intervals (e.g., $[395, 400]$ for $T=400$).
3. Wine Quality Dataset: A real-world application simulating a switch from white to red wine. The lower confidence bound was found to be 387 (true $T=400$), allowing operators to certify samples up to time 386 as "white" with 90% confidence.

Significance and Claims

The paper claims to provide the first general distribution-free framework for sequential changepoint localization with valid post-detection coverage guarantees.

• Motivation: In real-world systems (industrial monitoring, network security), data generating mechanisms are often complex, high-dimensional, and poorly specified, making reliable distributional modeling infeasible. Existing methods requiring known $F_0/F_1$ or disjoint classes are often unrealistic in these settings.
• Advantage over Prior Work: Unlike Saha and Ramdas (2026), which requires $P_0 \cap P_1 = \emptyset$, this framework allows $P_0 = P_1 = \mathcal{P}$ (the universe of all distributions), requiring only that the specific realized $F_0 \neq F_1$.
• Practical Utility: The lower confidence bound is highlighted as particularly useful for quality control, providing a "safe time threshold" after which a system is guaranteed to be in a post-change (potentially faulty) state, allowing for targeted isolation of affected products.
• Robustness: The validity of the procedure does not rely on modeling assumptions; models (e.g., for scoring) only affect statistical efficiency (the size of the interval), not the validity of the coverage guarantee.

The authors conclude that reliable changepoint localization is possible even without distributional assumptions, offering a conceptually simple, broadly applicable tool for sequential analysis. Future work is suggested to extend this to multi-stream settings.