Inferring Change Points in High-Dimensional Linear Regression via Approximate Message Passing

Gabriel Arpino, Xiaoqi Liu, Ramji Venkataramanan
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:1841-1864, 2024.

Abstract

We consider the problem of localizing change points in high-dimensional linear regression. We propose an Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations. Assuming Gaussian covariates, we give an exact asymptotic characterization of its estimation performance in the limit where the number of samples grows proportionally to the signal dimension. Our algorithm can be tailored to exploit any prior information on the signal, noise, and change points. It also enables uncertainty quantification in the form of an efficiently computable approximate posterior distribution, whose asymptotic form we characterize exactly. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic data and images.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-arpino24a, title = {Inferring Change Points in High-Dimensional Linear Regression via Approximate Message Passing}, author = {Arpino, Gabriel and Liu, Xiaoqi and Venkataramanan, Ramji}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {1841--1864}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/arpino24a/arpino24a.pdf}, url = {https://proceedings.mlr.press/v235/arpino24a.html}, abstract = {We consider the problem of localizing change points in high-dimensional linear regression. We propose an Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations. Assuming Gaussian covariates, we give an exact asymptotic characterization of its estimation performance in the limit where the number of samples grows proportionally to the signal dimension. Our algorithm can be tailored to exploit any prior information on the signal, noise, and change points. It also enables uncertainty quantification in the form of an efficiently computable approximate posterior distribution, whose asymptotic form we characterize exactly. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic data and images.} }
Endnote
%0 Conference Paper %T Inferring Change Points in High-Dimensional Linear Regression via Approximate Message Passing %A Gabriel Arpino %A Xiaoqi Liu %A Ramji Venkataramanan %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-arpino24a %I PMLR %P 1841--1864 %U https://proceedings.mlr.press/v235/arpino24a.html %V 235 %X We consider the problem of localizing change points in high-dimensional linear regression. We propose an Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations. Assuming Gaussian covariates, we give an exact asymptotic characterization of its estimation performance in the limit where the number of samples grows proportionally to the signal dimension. Our algorithm can be tailored to exploit any prior information on the signal, noise, and change points. It also enables uncertainty quantification in the form of an efficiently computable approximate posterior distribution, whose asymptotic form we characterize exactly. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic data and images.
APA
Arpino, G., Liu, X. & Venkataramanan, R.. (2024). Inferring Change Points in High-Dimensional Linear Regression via Approximate Message Passing. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:1841-1864 Available from https://proceedings.mlr.press/v235/arpino24a.html.

Related Material