Localizing Changes in High-Dimensional Regression Models

Alessandro Rinaldo, Daren Wang, Qin Wen, Rebecca Willett, Yi Yu
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2089-2097, 2021.

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 dimension, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-rinaldo21a, title = { Localizing Changes in High-Dimensional Regression Models }, author = {Rinaldo, Alessandro and Wang, Daren and Wen, Qin and Willett, Rebecca and Yu, Yi}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2089--2097}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/rinaldo21a/rinaldo21a.pdf}, url = {https://proceedings.mlr.press/v130/rinaldo21a.html}, 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 dimension, 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. } }
Endnote
%0 Conference Paper %T Localizing Changes in High-Dimensional Regression Models %A Alessandro Rinaldo %A Daren Wang %A Qin Wen %A Rebecca Willett %A Yi Yu %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-rinaldo21a %I PMLR %P 2089--2097 %U https://proceedings.mlr.press/v130/rinaldo21a.html %V 130 %X 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 dimension, 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.
APA
Rinaldo, A., Wang, D., Wen, Q., Willett, R. & Yu, Y.. (2021). Localizing Changes in High-Dimensional Regression Models . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2089-2097 Available from https://proceedings.mlr.press/v130/rinaldo21a.html.

Related Material