stat.MEMay 1, 2026

Pi-Change: A Prior-Informed Multiple Change Point Detection Algorithm

Authors: Jonathon Jacobs, Shanshan Chen

Abstract

Statistical change point (CP) detection methods typically rely on likelihood-based inference and ignore contextual information about plausible CP locations beyond the observed sequence. Although informative priors provide a natural way to incorporate such information, general and computationally efficient methods for doing so are lacking, especially for multiple CP detection. To address this gap, we propose a prior-informed CP detection algorithm (Pi-Change) that incorporates prior information on CP locations through a time-varying penalty term. We prove that the proposed penalty can be embedded in the Pruned Exact Linear Time framework while preserving the dynamic programming recursion and pruning rule required for efficient multiple CP detection. Across simulation studies and three time-series applications, Pi-Change discourages spurious CPs unsupported by prior information, remains robust to prior misspecification, and improves detection accuracy. More broadly, Pi-Change extends multiple CP detection beyond purely data-driven fitting by incorporating partial prior knowledge in a computationally efficient and interpretable way. It is particularly useful when CPs arise from heterogeneous mechanisms or are associated with known external events, helping quantify the delay between an event and the resulting structural change.

Explore similar work

CardsList
May 31, 2026stat.ML

Distribution-free changepoint localization after sequential change detection

This paper introduces a distribution-free framework for constructing post-detection confidence sets for changepoints after stopping a sequential change detection procedure. It is well known that conformal test martingales can be used to sequentially detect changes in distribution, but by themselves provide no inference for the time at which a proclaimed change occurred. Past work on post-detection inference requires pre- and post-change classes of distributions to be known, but this paper accomplishes localization of the changepoint without any distributional assumptions. We establish finite-sample coverage guarantees (conditional on correct detection). We provide non-asymptotic bounds on the conditional expected size of the confidence sets. Under suitable asymptotic regimes, we prove that the conditional expected size of the confidence set remains uniformly bounded and demonstrate strong empirical performance on simulated and real data. To the best of our knowledge, this is the first general distribution-free framework for sequential changepoint localization with valid post-detection coverage.
Aytijhya Saha, Aaditya Ramdas
Change-Point DetectionChange DetectionChangeConformal Test MartingalesConfidence Estimation
AskPDF
Dec 8, 2025stat.ML

High-Dimensional Change Point Detection via Graph Spanning Ratio

Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data across low to high dimensions. This versatile approach is applicable to Euclidean and graph-structured data with unknown distributions, while maintaining control over error probabilities. Theoretically, we demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate, which scales on the order of nd\sqrt{nd}. Our method outperforms other techniques in terms of accuracy for both Gaussian and non-Gaussian data. Notably, it maintains strong detection power even with small observation windows, making it particularly effective for online environments where timely and precise change detection is critical.
Katerina Papagiannouli, Yang-wen Sun, Vladimir Spokoiny
Change-Point DetectionChange DetectionAcyclic GraphsChangeGraph Structure
AskPDF
May 13, 2026stat.ML

The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

We study multiple change point localization under bandit feedback. An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs, and each query returns a noisy evaluation of the function. The goal is to identify a prescribed number of discontinuities, known as change points, within a target precision ηη and confidence level 1−δ1-δ, while using as few samples as possible. We propose an adaptive algorithm that first detects intervals likely to contain change points and then refines their locations to precision ηη. We establish non-asymptotic upper bounds on its sample budget, together with corresponding lower bounds. Prior work shows that jump magnitudes alone determine the asymptotic sample complexity as δ→0δ\to 0. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general δδ and ηη, the complexity is jointly governed by the jumps and the relative positions of the change points.
Maximilian Graf, Victor Thuot
Change-Point DetectionOptimal Sample ComplexitySample ComplexityBanditsNatural Language Feedback
AskPDF