Computationally efficient change point detection for high-dimensional regression

Abstract

Large-scale sequential data is often exposed to some degree of inhomogeneity in the form of sudden changes in the parameters of the data-generating process. We consider the problem of detecting such structural changes in a high-dimensional regression setting. We propose a joint estimator of the number and the locations of the change points and of the parameters in the corresponding segments. The estimator can be computed using dynamic programming or, as we emphasize here, it can be approximated using a binary search algorithm with $O(n\log (n)\mathrm{Lasso}(n))$ computational operations while still enjoying essentially the same theoretical properties; here $\mathrm{Lasso}(n)$ denotes the computational cost of computing the Lasso for sample size $n$. We establish oracle inequalities for the estimator as well as for its binary search approximation, covering also the case with a large (asymptotically growing) number of change points. We evaluate the performance of the proposed estimation algorithms on simulated data and apply the methodology to real data.

References in corpus (2)

• Change Point Detection in Correlation Networks
• A model selection approach for multiple sequence segmentation and dimensionality reduction

Cited by in corpus (13)

• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Change-Point Estimation in High-Dimensional Markov Random Field Models
• Oracle Estimation of a Change Point in High Dimensional Quantile Regression
• Statistically and Computationally Efficient Change Point Localization in Regression Settings
• Localizing Changes in High-Dimensional Vector Autoregressive Processes
• Data segmentation algorithms: Univariate mean change and beyond
• Multiple Changepoint Estimation in High-Dimensional Gaussian Graphical Models
• A review on minimax rates in change point detection and localisation
• Localizing Changes in High-Dimensional Regression Models
• Change-point detection in a linear model by adaptive fused quantile method
• Detection and estimation of parameters in high dimensional multiple change point regression models via ${\ell }_1/{\ell }_0$ regularization and discrete optimization
• Sparse Group Fused Lasso for Model Segmentation
• Detection of similar successive groups in a model with diverging number of variable groups