Statistically and Computationally Efficient Change Point Localization in Regression Settings

Abstract

Detecting when the underlying distribution changes for the observed time series is a fundamental problem arising in a broad spectrum of applications. In this paper, we study multiple change-point localization in the high-dimensional regression setting, which is particularly challenging as no direct observations of the parameter of interest is available. Specifically, we assume we observe $\{x_t,y_t{\}}_{t=1}^n$ where $\{x_t{\}}_{t=1}^n$ are $p$-dimensional covariates, $\{y_t{\}}_{t=1}^n$ are the univariate responses satisfying $\mathbb{E}(y_t)=x_t^{\top }{\beta }_t^{\ast }\text{ for }1\le t\le n$ and $\{{\beta }_t^{\ast }{\}}_{t=1}^n$ are the unobserved regression coefficients that change over time in a piecewise constant manner. We propose a novel projection-based algorithm, Variance Projected Wild Binary Segmentation~(VPWBS), which transforms the original (difficult) problem of change-point detection in $p$-dimensional regression to a simpler problem of change-point detection in mean of a one-dimensional time series. VPWBS is shown to achieve sharp localization rate $O_p(1/n)$ up to a log factor, a significant improvement from the best rate $O_p(1/\sqrt{n})$ known in the existing literature for multiple change-point localization in high-dimensional regression. Extensive numerical experiments are conducted to demonstrate the robust and favorable performance of VPWBS over two state-of-the-art algorithms, especially when the size of change in the regression coefficients $\{{\beta }_t^{\ast }{\}}_{t=1}^n$ is small.

44 pages

References in corpus (5)

• Change-point detection in panel data via double CUSUM statistic
• The group fused Lasso for multiple change-point detection
• Optimal Covariance Change Point Localization in High Dimension
• Change-point detection in dynamic networks via graphon estimation
• An efficient two step algorithm for high dimensional change point regression models without grid search

Cited by in corpus (7)

• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Localizing Changes in High-Dimensional Vector Autoregressive Processes
• Data segmentation algorithms: Univariate mean change and beyond
• A review on minimax rates in change point detection and localisation
• Localizing Changes in High-Dimensional Regression Models
• Sequential (Quickest) Change Detection: Classical Results and New Directions
• Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees