Localizing Changes in High-Dimensional Regression Models

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-ofthe-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 computationallyefficient 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.

Automated summary

This paper presents a dynamic programming approach to estimate change points in high-dimensional linear regression models with improved performance and a computationally efficient refinement procedure to reduce localization error. Theoretical bounds on localization error and discussions on signal-to-noise conditions are also provided, supported by extensive numerical results and real air quality data experiments revealing historical change points.