Exact Multiple Change-Point Detection Via Smallest Valid Partitioning
Abstract
We introduce smallest valid partitioning (SVP), a segmentation method for multiple change-point detection in time-series. SVP relies on a local notion of segment validity: a candidate segment is retained only if it passes a user-chosen validity test (e.g., a single change-point test). From the collection of valid segments, we propose a coherent aggregation procedure that constructs a global segmentation which is the exact solution of an optimization problem. Our main contribution is the use of a lexicographic order for the optimization problem that prioritizes parsimony. We analyze the computational complexity of the resulting procedure, which ranges from linear to cubic time depending on the chosen cost and validity functions, the data regime and the number of detected changes. Finally, we assess the quality of SVP through comparisons with standard optimal partitioning algorithms, showing that SVP yields competitive segmentations while explicitly enforcing segment validity. The flexibility of SVP makes it applicable to a broad class of problems; as illustrations, we demonstrate robust change-point detection and change-point detection in autoregressive time series by simply adapting the validity test to the setting of interest.
Related
- Multiple change-point detection for Poisson processes
- Multiple change-point detection via bottom-up scanning
- Laplacian U-Processes for Multiple Change-Point Detection in Dependent Text Networks: An Application to Historical Chinese Articles
- The cost of an exact position: tolerant losses, integrated positions and detection thresholds for change-points
- Multiple Change Point Detection in the Mean and Covariance of High-Dimensional Matrix Time Series
BibTeX
@misc{runge2026exact,
title = {{Exact Multiple Change-Point Detection Via Smallest Valid Partitioning}},
author = {Vincent Runge and Anica Kostic and Alexandre Combeau and Gaetano Romano},
howpublished = {HAL},
year = {2026},
month = sep,
eprint = {2602.04322},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05491126v2},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Exact Multiple Change-Point Detection Via Smallest Valid Partitioning
AU - Vincent Runge
AU - Anica Kostic
AU - Alexandre Combeau
AU - Gaetano Romano
PY - 2026
DA - 2026/09/23
PB - HAL
UR - https://hal.science/hal-05491126v2
AB - We introduce smallest valid partitioning (SVP), a segmentation method for multiple change-point detection in time-series. SVP relies on a local notion of segment validity: a candidate segment is retained only if it passes a user-chosen validity test (e.g., a single change-point test). From the collection of valid segments, we propose a coherent aggregation procedure that constructs a global segmentation which is the exact solution of an optimization problem. Our main contribution is the use of a lexicographic order for the optimization problem that prioritizes parsimony. We analyze the computational complexity of the resulting procedure, which ranges from linear to cubic time depending on the chosen cost and validity functions, the data regime and the number of detected changes. Finally, we assess the quality of SVP through comparisons with standard optimal partitioning algorithms, showing that SVP yields competitive segmentations while explicitly enforcing segment validity. The flexibility of SVP makes it applicable to a broad class of problems; as illustrations, we demonstrate robust change-point detection and change-point detection in autoregressive time series by simply adapting the validity test to the setting of interest.
ER -