DUST: A Duality-Based Pruning Method For Exact Multiple Change-Point Detection

par Vincent Runge

mardi 10 févr. 2026, 14:00 → 15:00 Europe/Paris

We address the computational challenge of detecting multiple change points in large time series. In particular, we focus on minimising penalised likelihoods for exponential-family models. While dynamic programming yields exact solutions with at most quadratic complexity, existing pruning methods have important limitations: (i) PELT prunes inefficiently when change points are sparse, and (ii) FPOP is not well suited to multi-parameter models.

We introduce DUST (DUal Simple Test), a duality-based pruning framework that discards candidate change points by comparing a dual function with a threshold. Experiments across regimes and models show that DUST combines PELT’s simplicity with FPOP’s efficiency, with particularly strong gains for non-Gaussian data. A detailed introduction will situate this contribution within the state of the art in dynamic programming for time-series analysis.