Kernel change point detection splits a time series into stretches whose whole distribution, not just its mean, stays the same. It does this by mapping each observation into a rich feature space and finding the segmentation that minimizes within-segment scatter, typically by exact dynamic programming, an algorithm that finds the globally best split rather than greedily adding one boundary at a time. The method is standard: it is the default nonparametric option in the ruptures library and has minimax-optimal localization rates. It still returns only bare boundary positions. A user cannot tell whether a boundary at day 214 is sharp to within a day or uncertain over a month. Real series such as markets, sensors, and running text are also serially correlated, and that correlation makes any naive interval far too narrow.
We propose a direct way to attach confidence intervals to each boundary that kernel dynamic programming returns, with dependence handled explicitly. The key observation is a simple identity. Moving a kernel boundary by one step changes the cost by an amount that depends on the data only through a single scalar function, the MMD witness function. This is the function that best separates the before and after distributions, and MMD (maximum mean discrepancy) is the kernel distance between distributions. Localization uncertainty for a high-dimensional, nonparametric change therefore reduces to the argmax of a one-dimensional dependent random walk built from the witness series. That one-dimensional problem can be calibrated with long-run variance estimates or block resampling, which avoids resampling the whole segmentation pipeline.
Core Claim
Let a boundary separate distributions $P_1$ and $P_2$ with kernel mean embeddings $\mu_1,\mu_2$, and define the witness $g(y)=\langle k(y,\cdot),\mu_1-\mu_2\rangle = \mathbb{E}_{X\sim P_1}k(y,X)-\mathbb{E}_{X\sim P_2}k(y,X)$. Plugging the kernel least-squares segment cost into the difference between a candidate boundary $\tau<\tau^*$ and the true boundary $\tau^*$ gives
$$C(\tau)-C(\tau^*) \approx \sum_{t=\tau+1}^{\tau^*}\Big(\Delta^2 + 2\big(g(y_t)-\mathbb{E}_{P_1}g\big)\Big),\qquad \Delta^2=\|\mu_1-\mu_2\|^2_{\mathcal H},$$
and a mirror expression holds for $\tau>\tau^*$. The cost profile is therefore a two-sided random walk. Its drift is the squared MMD, and its noise is the centered witness series. The approximation error comes from re-estimating the segment means, and it is of lower order when segments are long.
The claim has three parts. First, kernel dynamic programming boundaries have limiting distributions given by the argmax of this walk. When the jump is small relative to noise, the walk is a Brownian motion with drift whose scale on each side is the long-run variance $\sigma^2_{LR,j}$ of $g(y_t)$ under $P_j$. That variance sums all autocovariances, so it is exactly where temporal correlation enters. Second, when the jump is not small, the limit is non-universal, which Change point detection and inference in multivariate non-parametric models under mixing conditions identifies as the obstacle to practical inference. Because the walk is scalar, we can simulate its non-universal limit directly by block-resampling estimated witness residuals on each side. Third, the dependence that seems to break dynamic programming's segment additivity (Gap 3 in the file) costs only lower-order error in the point estimate. It matters mainly in two places, the interval width and the penalty that chooses the number of changes, and both can be corrected without giving up exact dynamic programming.
Research Program
The method has three components that run after an unmodified kernel dynamic programming search.
The first component calibrates the penalty for dependence. A Kernel Multiple Change-point Algorithm via Model Selection derives its penalty under independence. Uncertainty Quantification for Data-Driven Change-Point Learning via Cross-Validation shows that serial correlation leads change point learners to overestimate the number of changes. We therefore inflate the penalty by an estimated ratio of long-run to marginal variance of the centered kernel features, computed on a preliminary over-segmentation. This step is needed for coverage, because intervals around spurious boundaries are meaningless, but it is not the main contribution. We ablate it separately.
The second component is local witness estimation. For each estimated boundary $\hat\tau_k$, we restrict attention to the window halfway to its neighbors, which turns the problem into a single-change problem. We estimate $g$ by cross-fitting: kernel evaluations against observations on each side, with a guard band of a few lag lengths around $\hat\tau_k$ removed so that the estimated witness does not reuse the points whose position is in question. We then form the witness series $\hat g(y_t)$ and estimate $\hat\Delta^2$.
The third component builds the interval in two variants. The asymptotic variant estimates side-specific long-run variances of $\hat g(y_t)$ with a lag-window estimator, using automatic bandwidth selection. It then reads quantiles from the known argmax distribution of two-sided Brownian motion with asymmetric drift and scale. The resampling variant simulates the random walk directly. It draws centered witness residuals in moving blocks from each side, adds drift $\hat\Delta^2$, records the argmax, and repeats. This variant targets the non-vanishing-jump regime. Simultaneous intervals over all $K$ boundaries use a Bonferroni correction. Coverage is analyzed conditionally on correct estimation of $K$, and we report how often that event fails.
On the theory side, we aim to prove that the cross-fitted witness series inherits the $\alpha$-mixing of the data. This follows because $g$ is a bounded function of $y_t$ for bounded kernels. Combined with the localization rates of Consistent change-point detection with kernels, whose proofs assume independence and would need to be extended, this should give asymptotic validity of both variants under mixing. The extension is plausible because Consistent Kernel Change-Point Detection under m-Dependence for Text Segmentation already obtains consistency of kernel dynamic programming under m-dependence, and Model-Free Change Point Detection for Mixing Processes supplies MMD concentration under mixing. The witness view also clarifies a known failure mode. When the kernel exhibits "high-frequency blindness," $\Delta^2$ is small relative to $\sigma_{LR}$, so the intervals widen honestly rather than reporting false precision.
For long series, the Gram matrix cost of $O(N^2)$ applies only to the search. Random Fourier features can approximate the search. Inference itself touches only local windows, so it costs time linear in the window size.
The idea differs from prior work in four specific ways. Change point detection and inference in multivariate non-parametric models under mixing conditions builds intervals under mixing, but it uses kernel-density CUSUM statistics with seeded binary segmentation, assumes change spacing that grows with $n$, and leaves non-vanishing jumps without practical inference. Conformal changepoint localization gives finite-sample sets, but only for one change and only under exchangeability. The m-dependence work uses dynamic programming but provides point consistency only. The cross-validation wrapper quantifies uncertainty in the number of changes, not their locations.
Baselines
The naive reference point is kernel dynamic programming from ruptures: change point detection in Python with the original independence penalty. Its intervals come from the same witness random walk, but with i.i.d. variance in place of long-run variance and with i.i.d. resampling in place of block resampling. This baseline doubles as the key ablation. It shares every component of our method except the dependence correction, so any coverage gap between the two is attributable to that single ingredient. A second ablation keeps dependence-aware intervals but removes penalty inflation, which isolates the effect of spurious boundaries.
The strongest existing competitor is MNSBS from Change point detection and inference in multivariate non-parametric models under mixing conditions. It is the only method in the file that produces location intervals for nonparametric multivariate changes under mixing. On the three-index stock data ($n=515$, $p=3$), it reports six change points and 99% intervals described as having "excellent coverage" and narrowing to "a few days." Lacuna contains no reported numerical coverage or width figure for MNSBS. We will run the authors' algorithm with its default seeded intervals and its block long-run variance estimator. Kernel bandwidths will be selected by the same median heuristic, and both methods get the same tuning grid for block size. Beating MNSBS means one of two outcomes. The first is matching its nominal coverage with shorter median intervals. The second is maintaining coverage in regimes where it loses it: closely spaced changes, and large jumps where its Brownian limit is wrong.
For the single-change regime, we run CONCH Conformal changepoint localization with the same embeddings, using its classifier-based plausibility score. CONCH reports a 95% set of 3 time steps on a Gaussian mean shift at $n=1000$, the interval [400, 401] on SST-2 with DistilBERT, and widths of about 47 and about 10 steps on CIFAR-100 bears-to-beavers, depending on classifier strength. We expect CONCH to stay narrow but undercover once autocorrelation is injected. Our method should hold coverage at a modest width cost. The parametric reference is AR pre-whitening followed by kernel dynamic programming with i.i.d. intervals. A whole-pipeline moving-block bootstrap, which reruns dynamic programming on each resample, is the resampling reference. All methods share data, kernel, and bandwidth, and each resampling method gets 1000 replicates.
Why not just…?
Why not just pre-whiten with an autoregressive model and then segment? A linear autoregressive filter removes second-order correlation. Its residuals, however, are a transformed series in which shape changes such as unimodal-to-bimodal or light-to-heavy tails, which the kernel exists to catch, can be distorted. A Contrastive Approach to Online Change Point Detection stresses that such moment-preserving shifts are invisible to low-order models. Misspecified parametric fits also shift limiting distributions and corrupt coverage, as Asymptotics for change-point models under varying degrees of mis-specification shows. Pre-whitening is still a real threat when the dependence is truly linear and the shift is in the mean. We include that regime deliberately and will report it if pre-whitening wins there.
Why not just block-bootstrap the whole pipeline? Change point locations are non-regular argmax parameters, and the file notes that naive bootstrap theory does not cover them. Resampling the whole pipeline also smears blocks across boundaries and reruns a search whose selection of $K$ is itself unstable under dependence. The cross-validation paper reports overestimation rates as high as 83.0% at a 5% target for a poorly controlled competitor under heavy tails. Our resampling variant bootstraps only the scalar witness residuals within each side, holding the boundary structure fixed. We cannot rule out that the whole-pipeline bootstrap performs acceptably in practice, so it is a head-to-head baseline in every experiment.
Why not just use MNSBS, which already handles mixing? For well-separated changes with small jumps, MNSBS may be as good, and we would treat that outcome as a legitimate result. Our advantages are specific and testable. Global dynamic programming avoids the boundary instability of greedy splitting reported in RNA Structural Segmentation. Our theory does not require spacing that grows with $n$. Simulating the witness walk covers non-vanishing jumps. Kernel costs also apply directly to sentence embeddings, where density estimation is impractical. The crowded-change and large-jump experiments below settle the comparison.
Proposed Experiments
The synthetic study varies four factors: AR(1) and ARCH-type innovations with $\rho\in\{0,0.3,0.6,0.9\}$; shift types including mean shifts, variance shifts, and mean-and-variance-preserving shifts (Gaussian to bimodal, Gaussian to variance-matched $t_3$); jump size (vanishing versus fixed); and minimum spacing, from $n/5$ down to about 30 points. It also includes the hidden Markov mixing setup of Model-Free Change Point Detection for Mixing Processes. Metrics are empirical marginal and simultaneous coverage at 90% and 95%, median interval width, Hausdorff distance, and the rate of overestimating $K$.
The decisive check concerns the ablation. As $\rho$ grows, the i.i.d.-variance version should lose coverage roughly in proportion to the variance ratio $\sigma^2_{LR}/\sigma^2$, while the full method holds near nominal coverage. If the full method also degrades at $\rho=0.9$, that would mark the expected short-memory boundary. We will report that result rather than tune it away.
For semi-real data with known boundaries, we use Choi and Wiki-50 documents embedded with MPNet, as in the m-dependence paper. Sentences within a topic are dependent, and the boundaries come from construction. We also use spliced series built from stationary stretches of the Monterey wave-height and London NO$_2$ records, which preserves real serial dependence while fixing the true change times. For the stock indices, ground truth is unavailable. There we compare interval widths and agreement with the MNSBS intervals, but we make no coverage claims.
The single-change comparison with CONCH reruns its SST-2 and CIFAR-100 constructions with AR-correlated sampling orders, so that the two methods are compared directly where exchangeability fails. The method would be falsified in two cases: if dependence-aware witness intervals fail to beat the i.i.d. ablation on coverage once $\rho\ge0.3$, or if the whole-pipeline block bootstrap matches them on both coverage and width.
References
- Change point detection and inference in multivariate non-parametric models under mixing conditions
- A Kernel Multiple Change-point Algorithm via Model Selection
- Uncertainty Quantification for Data-Driven Change-Point Learning via Cross-Validation
- Consistent change-point detection with kernels
- Consistent Kernel Change-Point Detection under m-Dependence for Text Segmentation
- Model-Free Change Point Detection for Mixing Processes
- Conformal changepoint localization
- ruptures: change point detection in Python
- A Contrastive Approach to Online Change Point Detection
- Asymptotics for change-point models under varying degrees of mis-specification
- RNA Structural Segmentation