betaFeedback

WorksMathematics

Changepoint localization via nested exchangeability tests: from point estimates to confidence intervals

Abstract

We study distribution-free uncertainty quantification for a changepoint estimate in an offline setting. We observe a sequence with a single changepoint and are given an estimate of its location. The pre- and post-change segments are independent and each consists of i.i.d. (or, more generally, exchangeable) observations from arbitrary and unknown distributions. We introduce Changepoint LOcalization via Nested Exchangeability testing (CLONE), a novel method for constructing distribution-free confidence intervals around that estimate by testing exchangeability in nested windows centered at the reference estimate. Under these assumptions, CLONE provides finite-sample coverage for any black-box reference estimator. Using a geometrically shrinking radius grid, CLONE requires only O(logn)O(log n) permutation tests. We characterize optimal scores for the framework and provide practical recommendations that result in sharp confidence intervals. Under mild assumptions, CLONE confidence intervals have asymptotically vanishing normalized length. Simulations and experiments on image and text data support our theoretical findings.

Introduction

Suppose we observe a data sequence with a single changepoint. We study the problem of offline changepoint localization. A long line of classical statistical methods provides point estimates of the change location [16, 10]. More recently, modern machine learning methods, including random forests and neural networks, have also been used to estimate changepoint locations [12] (Li et al. 2024). However, these estimates typically do not come with a finite-sample reliability certificate. Our goal is to provide distribution-free uncertainty quantification for such estimates, turning a preliminary changepoint estimate into a confidence interval that contains the true changepoint with a user-specified coverage probability.

Problem setup

We now formalize the problem. Suppose we observe a sequence X=(X1,…,Xn)∈Xn\mathbf{X} = (X_1,\ldots,X_n) \in\mathcal{X}^n for some n≥2n \ge2, where X\mathcal{X} is a general measurable space. We assume that the sequence X\mathbf{X} admits a single changepoint, denoted by ξ∈[n−1]\xi\in[n-1], where we write [K][K] to denote {1,…,K}\{1,\ldots,K\} for any integer K∈NK \in\mathbb{N}. We make the following assumption on the joint distribution of X\mathbf{X}.

Assumption 1. We assume that the segments (X1,…,Xξ)(X_1,\ldots,X_\xi) and (Xξ+1,…,Xn)(X_{\xi+1},\ldots,X_n) are independent and each exchangeable.

We call the changepoint genuine if the one-dimensional marginal distributions induced by the two segments are different. A canonical example is the i.i.d. changepoint model: the observations are drawn i.i.d. from P0P_0 before the change and i.i.d. from P1≠P0P_1 \ne P_0 after the change. No further knowledge of the distributions, their separation, or any particular structure on X\mathcal{X} is assumed. This in fact poses the main challenge in distribution-free changepoint localization.

Our goal goes beyond obtaining a point estimate of the changepoint ξ\xi. We seek a collection of time points that contains ξ\xi with high probability. We formalize this goal below.

Definition 1. For α∈(0,1)\alpha\in(0,1), a measurable mapping Cn,1−α:Xn→2[n−1]C_{n,1-\alpha} : \mathcal{X}^n \to2^{[n-1]} is a distribution-free confidence set for a changepoint if

PX∼P(ξ∈Cn,1−α(X))≥1−α,\mathbb{P}_{\mathbf{X}\sim P}(\xi\in C_{n,1-\alpha}(\mathbf{X})) \ge1-\alpha,

for every distribution PP with a changepoint at ξ∈[n−1]\xi\in[n-1] and satisfying Assumption Assumption 1.

Existing work

Offline changepoint analysis has a long history; see Truong et al. [20]; Duggins [4] for surveys. A significant part of this literature focuses only on detecting the change. Beginning with CUSUM (Page [13]), a large literature has developed around modern detection procedures, including kernel changepoint procedures (KCP) (Arlot et al. [1]), ChangeForest (Londschien et al. [12]), and conformal martingale methods in the online setting (Vovk et al. [22]; Volkhonskiy et al. [21]).

The goal of this paper is to localize the changepoint efficiently while quantifying uncertainty in its location. Likelihood-based approaches assume specific parametric families, such as Gaussian mean-shift or linear regression models, and derive point estimators and confidence intervals through likelihood theory (Kim and Siegmund [10]; Quandt [16]; Gurevich and Vexler [7]).

Other approaches derive localization guarantees through asymptotic theory, including SMUCE (Frick et al. [5]) and regression-based methods (Xu et al. (2024)). Bootstrap approaches (Cho and Kirch [2]) quantify uncertainty in changepoint estimates but generally lack finite-sample validity and can be computationally intensive.

However, these classical approaches do not meet the requirements of modern applications. Today, data are complex and often scarce, and therefore may not satisfy the model assumptions or justify the large-sample approximations required by these approaches. This motivates the distribution-free formulation outlined in Definition 1. Building on conformal pp-values, recent works (Dandapanthula and Ramdas [3]; Hore and Ramdas [9]) have developed such changepoint localization frameworks with provable finite-sample, distribution-free coverage guarantees. These approaches start from a score function to measure the plausibility of a change at each time point and construct a confidence set by testing, for each candidate location t∈[n−1]t \in[n - 1], whether tt is the true changepoint, retaining the locations that are not rejected.

These conformal frameworks do not immediately provide uncertainty quantification around an existing changepoint estimate. In predictive inference, by contrast, conformal methods are commonly viewed as calibration wrappers: they take a black-box prediction algorithm and quantify uncertainty around its predictions. Since the existing conformal localization approaches rely on n−1n - 1 separate tests, one for each candidate location, it is not immediately clear how to wrap them around existing point estimates.

Preview of our approach: CLONE

A natural way to calibrate an existing changepoint estimate is to construct a confidence interval around it with distribution-free coverage for the true changepoint, thereby quantifying uncertainty in the estimate.

Suppose we are given a preliminary changepoint estimate ξ^\hat{\xi}. We consider nested intervals around it with decreasing radii, eventually reaching the singleton {ξ^}\{\hat{\xi}\}. Starting from the full range of candidate locations, we test exchangeability in successively smaller windows and continue shrinking whenever the test rejects. The intuition is simple: if the true changepoint ξ\xi lies outside a proposed interval, the associated window is homogeneous, so its exchangeability test should typically not reject. We return the preceding interval at the first non-rejection, or the singleton set if every test rejects. We call our proposed method Changepoint LOcalization via Nested Exchangeability tests (CLONE). An illustration of the different hypothesis tests considered by existing conformal frameworks and our proposal is given in Figure 1.

Schematic comparison of existing conformal frameworks and the CLONE proposal

Figure 1. A schematic comparison of the hypotheses tested: green and blue points indicate the true pre- and post-change segments, with changepoint ξ\xi and reference estimate ξ^\hat{\xi}. On the left, we have the hypotheses tested by Hore and Ramdas [9]; Dandapanthula and Ramdas [3]. For each candidate tt, the null asserts that the two disjoint segments determined by tt are independent and each exchangeable; the shaded regions mark these segments. On the right is our proposal: for each radius RR, CLONE tests whether the observations in the associated window around ξ^\hat{\xi} are exchangeable. The pink regions illustrate nested windows, parametrized by radius RR.

The use of nested intervals around a point estimate has previously appeared in the conformal literature. In predictive inference, Gupta et al. [6] consider nested intervals around a point estimate and calibrate them efficiently to produce valid prediction intervals for the unseen test response. There, the nested conformal prediction intervals help measure the uncertainty around the initial estimate. Likewise, CLONE provides uncertainty quantification for any given black-box changepoint estimator. A preview of the CLONE framework is given in Figure 2, where the confidence sets are contiguous intervals around the changepoint estimates and cover the true changepoint ξ\xi in most simulations.

Figure 2. Gaussian mean shift localization with n=200n = 200, ξ=100\xi= 100, and pre- and post-change distributions N(0.5,1)\mathcal{N}(0.5, 1) and N(−0.5,1)\mathcal{N}(-0.5, 1), respectively. Left: a simulated sequence with the true changepoint (dashed), the reference estimate (dash-dotted), and the 90% CLONE confidence interval (shaded). Right: CLONE intervals across ten simulations, with green points marking the corresponding reference estimates. CLONE quantifies uncertainty around each reference estimate through a contiguous confidence interval.

Our contributions

The main contributions of this work are summarized below:

  1. We formally describe the CLONE construction and establish its finite-sample validity. This coverage guarantee holds for any score used to test exchangeability within each window, providing the analyst with flexibility in designing their score. With a radius grid that shrinks geometrically, CLONE requires only O(log⁡n)O(\log n) permutation tests.

  1. An efficient score results in tight confidence intervals. We characterize optimal scores for the individual exchangeability tests in CLONE and give practical recommendations for approximating these scores.

(iii) We establish asymptotic sharpness of CLONE confidence intervals for general scores in the i.i.d. changepoint model through an interpretable signal-to-noise ratio, without requiring consistent estimation of the underlying densities. When the pre- and post-change marginals are known, the CLONE construction attains the rate given by the information-theoretic lower bound on cardinality.

Organization of the paper. The rest of the paper is organized as follows. In § 2, we introduce CLONE and establish its finite-sample validity. In § 3, we develop optimal and practical scores for the exchangeability tests and derive asymptotic localization rates. In § 4, we present simulations and experiments on image and text data. In § 5, we review CONCH and consider its interval hull as a baseline for comparison. We establish the same localization rate for the hull and show that, in the oracle setting, both methods attain the rate given by the information-theoretic cardinality lower bound. We conclude with a discussion in § 6. All proofs are deferred to the appendices.

Changepoint localization via nested exchangeability tests

In this section, we formally describe the CLONE framework. Inspired by the rich literature on split conformal prediction [14], we adopt a split conformal approach to changepoint localization. We compute the reference estimate on one split and use the remaining observations for conformal calibration.

A random split need not place observations from both segments in each split. To preserve the temporal ordering and ensure that both splits contain a change, we use interlaced sample splitting. We assume throughout this paper that the changepoint is away from the boundaries, i.e., ξ∉{1,n−1}\xi\notin\{1,n-1\}, so that both subsequences contain a change. We write T={2,…,n−2}\mathcal{T}=\{2,\ldots,n-2\} to denote the set of possible changepoint locations. Specifically, write m=⌊n/2⌋m=\lfloor n/2\rfloor and form the interlaced splits

Dn,1=(X2i−1,n)i=1⌈n/2⌉,Dn,2=Yn=(Y1,n,…,Ym,n),Yi,n=X2i,n.(1)D_{n,1}=(X_{2i-1,n})_{i=1}^{\lceil n/2\rceil},\qquad D_{n,2}=\mathbf{Y}_n=(Y_{1,n},\ldots,Y_{m,n}),\qquad Y_{i,n}=X_{2i,n}. \tag*{(1)}

Their changepoint indices are ξ′′=⌈ξ/2⌉\xi^{\prime\prime}=\lceil\xi/2\rceil and ξ′=⌊ξ/2⌋\xi^\prime=\lfloor\xi/2\rfloor, respectively, with ∣ξ′′−ξ′∣≤1|\xi^{\prime\prime}-\xi^\prime|\leq1. We refer to Dn,1D_{n,1} and Dn,2D_{n,2} as the training and calibration splits, respectively.

First, we use Dn,1D_{n,1} to learn a reference estimate ξ^n/2∈[m−1]\widehat{\xi}_{n/2}\in[m-1]. We write ξ^n/2\widehat{\xi}_{n/2} to explicitly encode the dependence of the estimate on approximately half of the data.

Next, we calibrate ξ^n/2\widehat{\xi}_{n/2} on the calibration split by considering nested intervals around this estimate. For an integer radius R≥0R\geq0, define

IR={t∈[m−1]:∣t−ξ^n/2∣≤R}.(2)I_R=\{t\in[m-1]:|t-\widehat{\xi}_{n/2}|\leq R\}. \tag*{(2)}

If ξ′∉IR\xi^\prime\notin I_R, then the observations (YLR,n,…,YUR,n)(Y_{L_R,n},\ldots,Y_{U_R,n}) are exchangeable conditional on Dn,1D_{n,1}, where LR=max⁡{1,ξ^n/2−R}L_R=\max\{1,\widehat{\xi}_{n/2}-R\} and UR=min⁡{m,ξ^n/2+R+1}U_R=\min\{m,\widehat{\xi}_{n/2}+R+1\}. This window contains $k_R=U_R-L_R+1\leq 2R+22R+2 observations and motivates hypotheses of the form

H0,IR:(YLR,n,…,YUR,n) is exchangeable conditional on Dn,1.\mathcal{H}_{0,I_R}: (Y_{L_R,n},\ldots,Y_{U_R,n})\text{ is exchangeable conditional on }D_{n,1}.

Consider a strictly decreasing integer sequence R0>R1>⋯>RJ=0R_0>R_1>\cdots>R_J=0, which may be chosen based on the training split Dn,1D_{n,1}, where R0=max⁡{ξ^n/2,m−1−ξ^n/2}R_0=\max\{\widehat{\xi}_{n/2},m-1-\widehat{\xi}_{n/2}\}. By construction, IR0=[m−1]I_{R_0}=[m-1] always contains ξ′\xi'. Moreover, the hypotheses H0,IR\mathcal{H}_{0,I_R} are nested in RR: if R1<R2R_1<R_2 and H0,IR1\mathcal{H}_{0,I_{R_1}} is false, then H0,IR2\mathcal{H}_{0,I_{R_2}} must also be false. We therefore test the windows in decreasing order of radius, stopping at the first non-rejection and retaining the preceding interval.

To test H0,IR\mathcal{H}_{0,I_R}, we first define a window-specific score SR:XkR→RS_R:\mathcal{X}^{k_R}\to\mathbb{R}, which may depend on the training split, with larger values providing greater evidence against exchangeability. Define the conformal pp-value

pwindow,R=1∣SkR∣∑π∈SkR1{SR(π(YLR,n,…,YUR,n))≥SR(YLR,n,…,YUR,n)}.(3)p_{\mathrm{window},R}=\frac{1}{\lvert S_{k_R}\rvert}\sum_{\pi\in S_{k_R}}\mathbb{1}\left\{S_R\left(\pi(Y_{L_R,n},\ldots,Y_{U_R,n})\right)\ge S_R(Y_{L_R,n},\ldots,Y_{U_R,n})\right\}. \tag*{(3)}

where we write SkRS_{k_R} to denote the permutation group on kRk_R items. Define the stopping rule

j^α=min⁡({j∈[J]:pwindow,Rj>α}∪{J+1}).\widehat{j}_{\alpha}=\min\left(\{j\in[J]:p_{\mathrm{window},R_j}>\alpha\}\cup\{J+1\}\right).

References

  1. [1]Arlot, S., A. Celisse, and Z. Harchaoui (2019). A kernel multiple change-point algorithm via model selection. Journal of machine learning research 20(162), 1–56.
  2. [2]Cho, H. and C. Kirch (2022). Bootstrap confidence intervals for multiple change points based on moving sum procedures. Computational Statistics & Data Analysis 175, 107552.arxiv.org/abs/2106.12844
  3. [3]Dandapanthula, S. and A. Ramdas (2026). Offline changepoint localization using a matrix of conformal p-values. Transactions on Machine Learning Research.arxiv.org/abs/2505.00292
  4. [4]Duggins, J. W. (2010). Parametric Resampling Methods for Retrospective Changepoint Analysis. Ph. D. thesis, Virginia Polytechnic Institute and State University.
  5. [5]Frick, K., A. Munk, and H. Sieling (2014). Multiscale change point inference. Journal of the Royal Statistical Society Series B: Statistical Methodology 76(3), 495–580.
  6. [6]Gupta, C., A. K. Kuchibhotla, and A. Ramdas (2022). Nested conformal prediction and quantile out-of-bag ensemble methods. Pattern Recognition 127, 108496.DOI
  7. [7]Gurevich, G. and A. Vexler (2006). Guaranteed maximum likelihood splitting tests of a linear regression model. Statistics 40(6), 465–484.DOI
  8. [8]Harrison, M. T. (2012). Conservative hypothesis tests and confidence intervals using importance sampling. Biometrika 99(1), 57–69.pubmed.ncbi.nlm.nih.gov/23049134
  9. [9]Hore, R. and A. Ramdas (2026). Conformal changepoint localization. arXiv preprint arXiv:2602.06267.arxiv.org/abs/2602.06267
  10. [10]Kim, H.-J. and D. Siegmund (1989). The likelihood ratio test for a change-point in simple linear regression. Biometrika 76(3), 409–423.DOI
  11. [12]Londschien, M., P. Bühlmann, and S. Kovács (2023). Random forests for change point detection. Journal of Machine Learning Research 24(216), 1–45.
  12. [13]Page, E. S. (1955). A test for a change in a parameter occurring at an unknown point. Biometrika 42(3/4), 523–527.DOI
  13. [14]Papadopoulos, H., K. Proedrou, V. Vovk, and A. Gammerman (2002). Inductive confidence machines for regression. In European conference on machine learning, pp. 345–356. Springer.
  14. [15]Peng, X., Q. Bai, X. Xia, Z. Huang, K. Saenko, and B. Wang (2019). Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 1406–1415.arxiv.org/abs/1812.01754
  15. [16]Quandt, R. E. (1958). The estimation of the parameters of a linear regression system obeying two separate regimes. Journal of the American Statistical Association 53(284), 873–880.DOI
  16. [17]Ramdas, A. and T. Manole (2026). Randomized and exchangeable improvements of markov’s, chebyshev’s and chernoff’s inequalities. Statistical Science 41(1), 121–142.arxiv.org/abs/2304.02611
  17. [18]Sanh, V., L. Debut, J. Chaumond, and T. Wolf (2019). DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01108.arxiv.org/abs/1910.01108
  18. [19]Socher, R., A. Perelygin, J. Wu, J. Chuang, C. D. Manning, A. Y. Ng, and C. Potts (2013). Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631–1642.DOI
  19. [20]Truong, C., L. Oudre, and N. Vayatis (2020). Selective review of offline change point detection methods. Signal processing 167, 107299.DOI
  20. [21]Volkhonskiy, D., E. Burnaev, I. Nouretdinov, A. Gammerman, and V. Vovk (2017). Inductive conformal martingales for change-point detection. In Conformal and Probabilistic Prediction and Applications, pp. 132–153. PMLR.arxiv.org/abs/1706.03415
  21. [22]Vovk, V., I. Nouretdinov, and A. Gammerman (2003). Testing exchangeability on-line. In Proceedings of the 20th International Conference on Machine Learning (ICML), pp. 768–775.

Paper details

vlnc:W_curz3kf3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

An AI model

View statement
Looking for related papers…
Contents