Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions

Wanshan Li, Daren Wang, Alessandro Rinaldo
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:20065-20148, 2023.

Abstract

We develop a novel, general and computationally efficient framework, called Divide and Conquer Dynamic Programming (DCDP), for localizing change points in time series data with high-dimensional features. DCDP deploys a class of greedy algorithms that are applicable to a broad variety of high-dimensional statistical models and can enjoy almost linear computational complexity. We investigate the performance of DCDP in three commonly studied change point settings in high dimensions: the mean model, the Gaussian graphical model, and the linear regression model. In all three cases, we derive non-asymptotic bounds for the accuracy of the DCDP change point estimators. We demonstrate that the DCDP procedures consistently estimate the change points with sharp, and in some cases, optimal rates while incurring significantly smaller computational costs than the best available algorithms. Our findings are supported by extensive numerical experiments on both synthetic and real data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-li23ae, title = {Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions}, author = {Li, Wanshan and Wang, Daren and Rinaldo, Alessandro}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {20065--20148}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/li23ae/li23ae.pdf}, url = {https://proceedings.mlr.press/v202/li23ae.html}, abstract = {We develop a novel, general and computationally efficient framework, called Divide and Conquer Dynamic Programming (DCDP), for localizing change points in time series data with high-dimensional features. DCDP deploys a class of greedy algorithms that are applicable to a broad variety of high-dimensional statistical models and can enjoy almost linear computational complexity. We investigate the performance of DCDP in three commonly studied change point settings in high dimensions: the mean model, the Gaussian graphical model, and the linear regression model. In all three cases, we derive non-asymptotic bounds for the accuracy of the DCDP change point estimators. We demonstrate that the DCDP procedures consistently estimate the change points with sharp, and in some cases, optimal rates while incurring significantly smaller computational costs than the best available algorithms. Our findings are supported by extensive numerical experiments on both synthetic and real data.} }
Endnote
%0 Conference Paper %T Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions %A Wanshan Li %A Daren Wang %A Alessandro Rinaldo %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-li23ae %I PMLR %P 20065--20148 %U https://proceedings.mlr.press/v202/li23ae.html %V 202 %X We develop a novel, general and computationally efficient framework, called Divide and Conquer Dynamic Programming (DCDP), for localizing change points in time series data with high-dimensional features. DCDP deploys a class of greedy algorithms that are applicable to a broad variety of high-dimensional statistical models and can enjoy almost linear computational complexity. We investigate the performance of DCDP in three commonly studied change point settings in high dimensions: the mean model, the Gaussian graphical model, and the linear regression model. In all three cases, we derive non-asymptotic bounds for the accuracy of the DCDP change point estimators. We demonstrate that the DCDP procedures consistently estimate the change points with sharp, and in some cases, optimal rates while incurring significantly smaller computational costs than the best available algorithms. Our findings are supported by extensive numerical experiments on both synthetic and real data.
APA
Li, W., Wang, D. & Rinaldo, A.. (2023). Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:20065-20148 Available from https://proceedings.mlr.press/v202/li23ae.html.

Related Material