Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality

Abstract

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 ${\sigma }^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 $\frac{\kappa \sqrt{\Delta }}{\sigma }<\sqrt{\log (n)}$, is impossible. In contrast, when $\frac{\kappa \sqrt{\Delta }}{\sigma }$ diverges with $n$ at the rate of at least $\sqrt{\log (n)}$, we demonstrate that two computationally-efficient change point estimators, one based on the solution to an ${\ell }_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{{\sigma }^2}{{\kappa }^2}\log (n)$. We further show that such rate is minimax optimal, up to a $\log (n)$ term.

References in corpus (11)

• Optimal detection of changepoints with a linear computational cost
• Properties and refinements of the fused lasso
• Change-point detection in panel data via double CUSUM statistic
• Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
• Uniform change point tests in high dimension
• Multiscale inference about a density
• Change-point detection in high-dimensional covariance structure
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Multiscale Change-point Segmentation: Beyond Step Functions
• Multiple Changepoint Estimation in High-Dimensional Gaussian Graphical Models
• Efficiency of change point tests in high dimensional settings

Cited by in corpus (1)

• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection