Localizing Changes in High-Dimensional Regression Models

Abstract

This paper addresses the problem of localizing change points in high-dimensional linear regression models with piecewise constant regression coefficients. We develop a dynamic programming approach to estimate the locations of the change points whose performance improves upon the current state-of-the-art, even as the dimensionality, the sparsity of the regression coefficients, the temporal spacing between two consecutive change points, and the magnitude of the difference of two consecutive regression coefficient vectors are allowed to vary with the sample size. Furthermore, we devise a computationally-efficient refinement procedure that provably reduces the localization error of preliminary estimates of the change points. We demonstrate minimax lower bounds on the localization error that nearly match the upper bound on the localization error of our methodology and show that the signal-to-noise condition we impose is essentially the weakest possible based on information-theoretic arguments. Extensive numerical results support our theoretical findings, and experiments on real air quality data reveal change points supported by historical information not used by the algorithm.

References in corpus (8)

• Optimal detection of changepoints with a linear computational cost
• Simultaneous analysis of Lasso and Dantzig selector
• On the conditions used to prove oracle results for the Lasso
• Oracle Estimation of a Change Point in High Dimensional Quantile Regression
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Computationally efficient change point detection for high-dimensional regression
• Optimal Covariance Change Point Localization in High Dimension
• Statistically and Computationally Efficient Change Point Localization in Regression Settings

Cited by in corpus (2)

• A review on minimax rates in change point detection and localisation
• Inference on the Change Point for High Dimensional Dynamic Graphical Models