Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality

The problem of univariate mean change point detection and localization based on a sequence of n independent observations with piecewise constant means has been intensively studied for more than half century, and serves as a blueprint for change point problems in more complex settings. We provide a complete characterization of this classical problem in a general framework in which the upper bound σ2 on the noise variance, the minimal spacing Delta between two consecutive change points and the minimal magnitude kappa of the changes, are allowed to vary with n. We first show that consistent localization of the change points, when the signal-to-noise ratio frackappa √Deltaσ < √log(n), is impossible. In contrast, when frackappa √Deltaσ diverges with n at the rate of at least √log(n), we demonstrate that two computationally-efficient change point estimators, one based on the solution to an ℓ0-penalized least squares problem and the other on the popular wild binary segmentation algorithm, are both consistent and achieve a localization rate of the order fracσ2kappa2 log(n). We further show that such rate is minimax optimal, up to a log(n) term.