Optimal Change-Point Detection and Localization - ENSAE Paris Access content directly
Journal Articles Annals of Statistics Year : 2023

Optimal Change-Point Detection and Localization

Abstract

Given a times series Y in R n , with a piece-wise contant mean and independent components, the twin problems of change-point detection and change-point localization respectively amount to detecting the existence of times where the mean varies and estimating the positions of those change-points. In this work, we tightly characterize optimal rates for both problems and uncover the phase transition phenomenon from a global testing problem to a local estimation problem. Introducing a suitable definition of the energy of a change-point, we first establish in the single change-point setting that the optimal detection threshold is 2 log log(n). When the energy is just above the detection threshold, then the problem of localizing the change-point becomes purely parametric: it only depends on the difference in means and not on the position of the change-point anymore. Interestingly, for most change-point positions, including all those away from the endpoints of the time series, it is possible to detect and localize them at a much smaller energy level. In the multiple change-point setting, we establish the energy detection threshold and show similarly that the optimal localization error of a specific change-point becomes purely parametric. Along the way, tight optimal rates for Hausdorff and l 1 estimation losses of the vector of all change-points positions are also established. Two procedures achieving these optimal rates are introduced. The first one is a least-squares estimator with a new multiscale penalty that favours well spread change-points. The second one is a two-step multiscale post-processing procedure whose computational complexity can be as low as O(n log(n)). Notably, these two procedures accommodate with the presence of possibly many low-energy and therefore undetectable change-points and are still able to detect and localize high-energy change-points even with the presence of those nuisance parameters.
Fichier principal
Vignette du fichier
2010.11470.pdf (766.79 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04251607 , version 1 (20-10-2023)

Identifiers

Cite

Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, Patricia Reynaud-Bouret. Optimal Change-Point Detection and Localization. Annals of Statistics, 2023, 51 (4), pp.1586-1610. ⟨10.1214/23-AOS2297⟩. ⟨hal-04251607⟩
78 View
25 Download

Altmetric

Share

Gmail Facebook X LinkedIn More