Optimal nonparametric change point detection and localization

Abstract

We study change point detection and localization for univariate data in fully nonparametric settings in which, at each time point, we acquire an i.i.d. sample from an unknown distribution. We quantify the magnitude of the distributional changes at the change points using the Kolmogorov--Smirnov distance. We allow all the relevant parameters -- the minimal spacing between two consecutive change points, the minimal magnitude of the changes in the Kolmogorov--Smirnov distance, and the number of sample points collected at each time point -- to change with the length of time series. We generalize the renowned binary segmentation (e.g. Scott and Knott, 1974) algorithm and its variant, the wild binary segmentation of Fryzlewicz (2014), both originally designed for univariate mean change point detection problems, to our nonparametric settings and exhibit rates of consistency for both of them. In particular, we prove that the procedure based on wild binary segmentation is nearly minimax rate-optimal. We further demonstrate a phase transition in the space of model parameters that separates parameter combinations for which consistent localization is possible from the ones for which this task is statistical unfeasible. Finally, we provide extensive numerical experiments to support our theory. R code is available at https://github.com/hernanmp/NWBS.

References in corpus (7)

• Optimal detection of changepoints with a linear computational cost
• Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation
• DISCO analysis: A nonparametric extension of analysis of variance
• Change-point detection in panel data via double CUSUM statistic
• Change-point detection in high-dimensional covariance structure
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Optimal Covariance Change Point Localization in High Dimension

Cited by in corpus (7)

• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Data segmentation algorithms: Univariate mean change and beyond
• A review on minimax rates in change point detection and localisation
• Change point localization in dependent dynamic nonparametric random dot product graphs
• Scalable Bayesian change point detection with spike and slab priors
• Sequential (Quickest) Change Detection: Classical Results and New Directions
• Online detection of cascading change-points