📊 statistics

Conformal changepoint localization

This paper introduces CONCH, a distribution-free algorithm that leverages exchangeability and a newly proven conformal Neyman–Pearson lemma to construct finite-sample confidence sets for changepoint localization with guaranteed coverage and shrinking set sizes, establishing its universality among all distribution-free methods.

Original authors: Rohan Hore, Aaditya Ramdas

Published 2026-07-29

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Rohan Hore, Aaditya Ramdas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Detective's Dilemma: Finding the Moment Everything Changed

Imagine you are a detective trying to solve a mystery, but instead of a crime scene, your evidence is a long, continuous stream of data. Maybe it's a video feed from a factory, a log of stock prices, or a stream of text messages. Somewhere in the middle of this stream, something fundamental shifted. Before that moment, the data behaved one way; after that moment, it behaved differently. Your job is to pinpoint exactly when that switch happened. This is the problem of "changepoint localization."

In the world of statistics, finding this moment is tricky. Usually, detectives rely on a "profile" of the suspect—they assume the data follows a specific pattern, like a bell curve (the famous "normal distribution"). If the data fits the profile, they can use math to find the change. But what if the data is messy, weird, or comes from a source we don't understand at all? What if the "suspect" is an image, a sentence, or a complex 3D object? Traditional methods often fail here because they get confused by the lack of a neat mathematical shape. They might guess a spot, but they can't tell you how sure they are, or their confidence might be a wild guess that only works if you have infinite data.

This is where the new paper steps in. It introduces a method called CONCH (which stands for CONformal CHangepoint localization). Think of CONCH as a super-smart, rule-abiding detective who doesn't care about the suspect's profile. Instead of guessing the shape of the data, CONCH uses a clever trick called "conformal inference." Imagine you have a deck of cards representing your data. If the change happened at a specific time, the cards before that time and the cards after that time should be shuffleable (permuted) without changing the overall story. CONCH tests every possible "change time" by shuffling the data and seeing if the story still makes sense. If the shuffle breaks the story, that time is likely the real change. The best part? CONCH works even if the data is weird, complex, or comes from a black box, and it gives you a mathematically guaranteed "confidence set"—a list of possible times where the change happened, with a promise that the true time is in there.

The Paper's Big Idea: A Universal Safety Net

The authors, Rohan Hore and Aaditya Ramdas, are tackling the problem of "offline changepoint localization." This means they are looking at a whole dataset that has already been collected, trying to find the single moment where the rules changed. Their main goal isn't just to point to one specific second and say, "It was right here!" (a point estimate). Instead, they want to build a confidence set—a range of time indices that is guaranteed to contain the true changepoint with a high level of certainty (like 95% or 99%), no matter what kind of data they are looking at.

The paper argues that many existing methods are too picky. They often assume the data follows a specific mathematical family (like Gaussian or normal distributions) or rely on approximations that only work when you have a massive amount of data. The authors show that these assumptions are unnecessary and often lead to results that are either too vague (a huge range of possibilities) or not trustworthy in the real world.

What CONCH Actually Does
The core of the paper is the CONCH algorithm. Here is how it works in simple terms:

The "Plausibility Score": For every possible moment in time (let's call it $t$ ), the algorithm asks, "How likely is it that the change happened right here?" It uses a "score function" to measure this. This score can be anything the user wants—a simple difference in averages, a complex machine learning model, or even a neural network.
The Shuffle Test: If the change really happened at time $t$ , then the data before $t$ and the data after $t$ should be "exchangeable." This means you could shuffle the order of the data points before $t$ without changing the story, and do the same for the points after $t$ .
The P-Value: CONCH takes the actual data and shuffles it thousands of times (or uses a mathematical shortcut to simulate this). It checks: "How often does the shuffled data look as 'extreme' as the real data?" If the real data looks very unique compared to the shuffles, it gets a low "p-value," meaning it's unlikely to be the change point. If it looks like a normal shuffle, it gets a high p-value.
The Confidence Set: The algorithm keeps all the time points where the p-value is high enough. The result is a list of candidate times. The paper proves mathematically that this list will contain the true changepoint at least 95% of the time (or whatever confidence level you choose), regardless of how weird the data distributions are.

The "Universal" Discovery
One of the most surprising findings in the paper is a "universality" result. The authors prove that any method that claims to give a distribution-free confidence set for a changepoint is essentially just a specific instance of the CONCH framework. It's like saying that every valid way to build a house without blueprints is just a variation of the same fundamental construction technique. This means CONCH isn't just one good method; it is the universal class that captures every possible valid approach to distribution-free changepoint localization.

Practical Magic: Making it Sharp
While the math guarantees the method works, the authors also want the confidence set to be small and precise (not a huge range like "it happened sometime between Tuesday and next year"). They show that the size of the confidence set depends heavily on the "score function" you choose.

If you use a dumb score (like just counting how many items are in the list), the confidence set will be huge and useless.
If you use a smart score (like a machine learning model trained to spot the difference between the "before" and "after" states), the confidence set shrinks dramatically.

They propose several ways to get these smart scores:

Oracle Score: If you magically know the exact math behind the data, you can get the perfect score.
Learned Score: If you don't know the math, you can train a model (like a classifier) on the data to learn the difference.
Wrapper: You can even take an existing changepoint detector (like one that just gives a single guess) and wrap it inside CONCH to turn that guess into a valid, safe confidence set.

What the Paper Rules Out
The paper explicitly argues against relying on parametric assumptions (assuming the data is Gaussian, bounded, or follows a specific curve). It shows that methods relying on these assumptions can fail or produce invalid results when the data doesn't fit the mold. It also notes that while some older methods give "asymptotic" guarantees (they only work if you have infinite data), CONCH works for finite samples—meaning it works even with small datasets, like 1,000 data points.

How Sure Are They?
The authors are very confident in their theoretical results. They have proved mathematically that CONCH provides finite-sample coverage (it works for any sample size) and that it is the universal framework for this problem.

Simulations: They tested CONCH on simulated data (Gaussian mean shifts) and real-world data (images from DomainNet, text from SST-2). In these simulations, CONCH consistently produced narrow confidence sets that contained the true changepoint.
Real Data: In experiments with images (shifting from "real" photos to "sketches") and text (shifting from positive to negative sentiment), CONCH successfully localized the change with high precision. For example, in a text experiment with 1,000 reviews, it narrowed the changepoint down to just two indices: 400 and 401.
Limitations: The paper admits that if the "score function" is bad (e.g., if the classifier is terrible at distinguishing the two states), the confidence set will be wider. However, even in these "bad" cases, the method remains valid (the true change is still inside the set), just less precise. They also note that while the method is proven for independent data, they have preliminary experiments suggesting it can be adapted for data with time-dependence (like stock prices that influence each other), though this is an area for future work.

The Bottom Line
CONCH is a robust, flexible, and mathematically guaranteed tool for finding when things change in a stream of data. It doesn't care if your data is numbers, pictures, or words. It doesn't care if the data is messy. It simply shuffles the deck, checks the rules, and gives you a safe, narrow list of "when" the change happened. The paper suggests that this approach is not just a new trick, but the fundamental way to solve this problem without making risky assumptions.

Technical Summary: Conformal Changepoint Localization (CONCH)

Problem Statement

The paper addresses the problem of offline changepoint localization in a distribution-free setting. Given an ordered sequence of observations $X_1, \dots, X_n$ with a single unknown changepoint $\xi \in \{1, \dots, n-1\}$ , the goal is to construct a finite-sample confidence set $C$ for $\xi$ such that:
$\inf_{P_0, \xi, P_1 \neq P_0} P(\xi \in C) \geq 1 - \alpha$
The setting assumes that observations before $\xi$ are drawn from a distribution $P_0$ and those after $\xi$ from $P_1$ , with the only structural assumption being exchangeability within the pre-change and post-change segments (e.g., i.i.d. data). The method must not rely on parametric assumptions (e.g., Gaussianity), tail conditions, or asymptotic approximations, and it must apply to complex data modalities like images and text.

Existing methods often fail to meet these criteria: detection-focused methods do not provide localization confidence sets; parametric methods rely on restrictive models; nonparametric methods often offer only asymptotic guarantees; and resampling-based methods lack finite-sample validity.

Methodology: CONCH

The authors propose CONCH (CONformal CHangepoint localization), a framework that leverages conformal inference principles to construct valid confidence sets.

Core Algorithm

ChangePoint Plausibility (CPP) Score: For any candidate index $t$ , a user-specified score function $S: \mathcal{X}^n \to \mathbb{R}^{n-1}$ assigns a score $S_t$ quantifying the plausibility that $t$ is the changepoint.
Split-Permutation Group: For a candidate $t$ , the algorithm defines a permutation group $\Pi_t$ that permutes indices only within the left segment $[1, t]$ and the right segment $[t+1, n]$ , without mixing them. This preserves the exchangeability structure under the null hypothesis $H_{0,t}$ (that $t$ is the true changepoint).
Conformal p-value: The p-value $p_t$ is computed as the normalized rank of the observed score $S_t(X)$ among all scores obtained by permuting the data within $\Pi_t$ :
$p_t = \frac{1}{|\Pi_t|} \sum_{\pi \in \Pi_t} \mathbb{1}\{S_t(\pi(X)) \leq S_t(X)\}$
Confidence Set Construction: The confidence set is defined as the set of indices with p-values exceeding the significance level $\alpha$ :
$C_{1-\alpha}^{\text{CONCH}} = \{ t \in [n-1] : p_t > \alpha \}$

Variants for Scalability and Efficiency

CONCH-MC: To avoid the computational cost of enumerating all permutations for large $n$ , the authors propose a Monte Carlo variant that samples permutations i.i.d. from $\Pi_t$ . This yields a valid p-value with finite-sample guarantees.
CONCH-SPLIT: To reduce the cost of re-fitting complex score functions (e.g., machine learning models) for every permutation, a sample-splitting approach is introduced. One subset of data learns the score function, while the other is used for conformal calibration. This variant is shown to be asymptotically sharp.

Score Function Design

While CONCH is valid for any score function, the paper derives an optimal score based on a novel Conformal Neyman–Pearson Lemma.

Optimal Score: In the i.i.d. setting with known densities $f_0, f_1$ , the optimal score is the likelihood ratio comparing the hypothesis that the changepoint is at $t$ versus the true changepoint $\xi$ .
Practical Scores: Since true densities are unknown, the authors propose practical approximations:
- Weighted Mean Difference: Effective for location shifts.
- Oracle/Parametric LLR: Uses known or parametrically estimated densities.
- Learned LLR: Uses density estimates or classifier logits (e.g., from a neural network) to approximate the log-likelihood ratio.

Key Contributions

Distribution-Free Finite-Sample Validity: CONCH provides a confidence set with guaranteed coverage $1-\alpha$ for any exchangeable pre/post-change distributions, without parametric assumptions.
Conformal Neyman–Pearson Lemma: The authors prove a lemma establishing the form of the optimal score function that minimizes the expected length of the confidence set. This provides a principled guide for score selection.
Asymptotic Sharpness: Under mild regularity conditions, the normalized length of the CONCH-SPLIT confidence set shrinks to zero as the sample size grows, provided the score function is consistent.
Universality Theorem: The paper establishes that any distribution-free changepoint localization method is an instance of CONCH. This implies CONCH is a canonical framework; any valid distribution-free procedure can be viewed as a specific choice of CPP score within this framework.
Calibration Framework: Leveraging the universality result, the authors propose CONCH-CAL, a method to wrap around existing heuristic confidence sets or point estimates (e.g., from bootstrap or Bayesian methods) to convert them into finite-sample valid, distribution-free confidence sets.

Experimental Results

The authors evaluate CONCH on synthetic and real-world datasets:

Gaussian Mean-Shift: CONCH produces significantly narrower confidence sets than previous distribution-free methods (e.g., MCP localization) and competitive performance against parametric methods, especially when using LLR-based scores.
DomainNet (Images): In a domain shift experiment (Real vs. Sketch images), a classifier-based LLR score successfully localized the changepoint with a 95% confidence set of size 2 ( $[350, 351]$ ).
SST-2 (Text): Using DistilBERT logits, CONCH localized sentiment shifts in movie reviews, yielding tight confidence sets even under subtle distributional shifts (e.g., 60% positive to 40% positive).
Calibration: Experiments demonstrate that CONCH-CAL can refine wide or invalid bootstrap intervals into sharp, valid distribution-free sets.
Extensions: Preliminary experiments suggest the framework extends to multiple changepoints (via segmentation) and temporally dependent data (via subsampling).

Significance and Claims

The paper claims that CONCH fills a critical gap in statistical inference by providing the first principled, distribution-free framework for changepoint localization that offers finite-sample validity and informative (narrow) confidence sets.

Key claims regarding significance include:

Universality: The proof that any distribution-free method is an instance of CONCH positions the framework as the fundamental solution space for this problem.
Flexibility: The ability to "wrap" any black-box classifier or heuristic estimator allows practitioners to leverage powerful modern machine learning tools while retaining rigorous statistical guarantees.
Practicality: The Monte Carlo and sample-split variants make the method computationally feasible for large datasets and complex models (e.g., deep learning on images/text).

The authors acknowledge that while the current work focuses on single changepoints and independent observations, future directions include extending the framework to multiple changepoints and general temporal dependence structures.