Post-detection inference for sequential changepoint localization

1. Problem Statement

The paper addresses a fundamental gap in sequential change detection: post-detection inference.

• Context: In sequential analysis, a detector (Algorithm $A$) monitors a stream of data $X_1, X_2, \dots$ and stops at a data-dependent time $\tau$ to declare a change has occurred. The data distribution shifts from a pre-change distribution $F_0$ (or class $\mathcal{P}_0$) to a post-change distribution $F_1$ (or class $\mathcal{P}_1$) at an unknown time $T$.
• The Challenge: Once $\tau$ is reached, standard methods only provide the stopping time. They do not provide a statistically valid confidence set for the actual changepoint $T$.
• The Impossibility of Unconditional Coverage: The authors prove that for any detector with a finite Average Run Length (ARL) to false alarm, it is impossible to construct a confidence set $C \subseteq \{1, \dots, \tau\}$ that satisfies unconditional coverage $P(T \in C) \ge 1-\alpha$. This is because if the detector stops early (false alarm, $\tau < T$), the set $\{1, \dots, \tau\}$ cannot possibly contain the true $T$.
• The Solution Goal: The paper aims to construct confidence sets with conditional coverage:
  $$P(T \in C \mid \tau \ge T) \ge 1 - \alpha$$
  This ensures that if the detector correctly identifies a change (stops after the true changepoint), the confidence set contains the true $T$ with high probability.

2. Methodology

The authors propose a general framework based on inverting hypothesis tests using e-processes (a modern tool for anytime-valid inference).

A. Core Framework (Universal Method)

The method constructs a confidence set $C$ by inverting tests for the null hypothesis $H_{0,t}$: "The change occurred at time $t$."

1. Test Statistic ($M_t$): For a candidate changepoint $t$, the statistic compares the likelihood of the data under $H_{0,t}$ against the alternative that the change happened earlier or later.
   • It utilizes forward e-processes ($R_n^{(t)}$) to accumulate evidence that the change happened at or before $t$ (post-change regime).
   • It utilizes backward e-processes ($S_n^{(t)}$) to accumulate evidence that the change happened after $t$ (pre-change regime).
   • $M_t = \max(\max_{t \le n \le \tau} R_n^{(t)}, \max_{1 \le n < t} S_n^{(t)})$.
2. Thresholding: The set is defined as $C = \{t \le \tau : M_t < \text{Threshold}\}$.
3. Handling Unknown Stopping Probabilities: To achieve the conditional coverage guarantee, the threshold must account for the probability that the detector stops at or after $t$ under the null ($P_{F_0, \infty}(\tau \ge t)$).
   • Universal Threshold: The authors propose using a universal bound ($2/\alpha$) combined with an unbiased estimator $r_t$ of $P(\tau \ge t)$ obtained via Monte Carlo simulation under the pre-change distribution.
   • Theorem 2: Proves that if the pre-change distribution is known, the set $C = \{t \le \tau : M_t < 2/(\alpha r_t)\}$ satisfies the conditional coverage guarantee non-asymptotically.

B. Extensions

1. Composite Pre-change Classes: When $F_0$ is unknown (belongs to a class $\mathcal{P}_0$), the method relies on the existence of a Least Favorable Distribution (LFD) pair. Under Assumption 1 (that an LFD exists and dominates the stopping probabilities), the method extends to provide valid coverage (Theorem 4).
2. Adaptive Methods (Parametric Settings): For parametric settings where distributions are known or belong to parametric families, the authors propose simulation-based adaptive thresholds.
   • Instead of a universal bound, they simulate the distribution of $M_t$ under the specific null hypothesis to find the exact quantile.
   • This handles dependent data (e.g., Markov chains) where constructing backward e-processes is difficult.
   • It allows for composite post-change parameters by using confidence sequences (CS) to integrate over the parameter space.

C. Parameter Inference

The framework naturally extends to estimating the pre- and post-change parameters ($\theta_0, \theta_1$). By fixing a candidate $t \in C$, one can construct confidence sequences for the parameters using the data segments before and after $t$, then union these sets over all $t \in C$.

3. Key Contributions

1. First General Post-Detection Framework: This is the first method to provide nonparametric, non-asymptotic confidence sets for changepoints that are agnostic to the detection algorithm used (works with CUSUM, e-detectors, ML-based detectors, etc.).
2. Theoretical Guarantees:
   • Proves the impossibility of unconditional coverage for finite-ARL detectors.
   • Establishes rigorous conditional coverage guarantees ($1-\alpha$) for both known and composite pre-change classes.
   • Provides bounds on the expected size (width) of the confidence intervals.
3. Handling Dependence: While the universal method assumes independence for backward e-processes, the adaptive simulation-based method works for dependent data (e.g., Markov processes).
4. Black-Box Compatibility: The method treats the detection algorithm as a "black box," requiring only the ability to run it on simulated data. This makes it applicable to complex modern pipelines (e.g., deep learning-based anomaly detection).

4. Experimental Results

The authors validate their methods through extensive simulations and a real-world text sentiment experiment (SST-2 dataset).

• Coverage: The proposed confidence sets consistently achieve conditional coverage close to or exceeding the target (e.g., 90% or 95%), whereas existing asymptotic methods (like those by Wu, 2007) exhibit significant undercoverage in finite samples.
• Size (Width): The confidence sets have reasonable sizes.
  • Adaptive vs. Universal: In parametric settings, the adaptive (simulation-based) method yields tighter (smaller) intervals than the universal method.
  • Nonparametric: The universal method performs well even when distributions are unknown (e.g., Huber-robust settings, non-Gaussian post-change).
• Dependence: The adaptive method successfully localizes changepoints in dependent data (Markov chains), a scenario where previous methods fail.
• Real Data: Applied to the SST-2 dataset to detect a shift in sentiment from positive to negative, successfully localizing the change point with a valid confidence set.

5. Significance

• Bridging a Critical Gap: Sequential change detection has historically focused on when to stop, ignoring where the change actually happened. This paper provides the missing inferential tool.
• Practical Applicability: By being agnostic to the detection algorithm and distributional assumptions, the method is immediately applicable to modern, complex data streams (images, text, high-dimensional data) where classical parametric assumptions (like exponential families) do not hold.
• Robustness: The non-asymptotic nature ensures validity in finite samples, which is crucial for real-time applications where asymptotic approximations may be inaccurate.
• Foundation for Future Work: The use of e-processes and confidence sequences sets a new standard for valid inference in sequential settings, moving beyond the limitations of the CUSUM procedure and exponential family assumptions.

In summary, Saha and Ramdas present a theoretically sound, flexible, and practical framework that transforms a "stopping time" from a sequential detector into a full "confidence set" for the changepoint, valid under minimal assumptions and for any detection algorithm.