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

arXiv: https://arxiv.org/abs/2404.07864 · HTML: https://mlsanity.com/paper/2404.07864/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 87 references that are in the map.
- First posted on arXiv 11 Apr 2024.

## Builds on (most cited first, 30 of 34)

- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [From Denoising to Compressed Sensing](https://mlsanity.com/paper/1406.4175/) (2014)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Phase retrieval in high dimensions: Statistical and computational phase transitions](https://mlsanity.com/paper/2006.05228/) (2020)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [Multiple-change-point detection for high dimensional time series via sparsified binary segmentation](https://mlsanity.com/paper/1611.08639/) (2016)
- [Approximate Message Passing with Spectral Initialization for Generalized Linear Models](https://mlsanity.com/paper/2010.03460/) (2020)
- [High-dimensional changepoint estimation via sparse projection](https://mlsanity.com/paper/1606.06246/) (2016)
- [Inference with Deep Generative Priors in High Dimensions](https://mlsanity.com/paper/1911.03409/) (2019)
- [All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation](https://mlsanity.com/paper/2006.07971/) (2020)
- [The Asymptotic Distribution of the MLE in High-dimensional Logistic Models: Arbitrary Covariance](https://mlsanity.com/paper/2001.09351/) (2020)
- [Random Forests for Change Point Detection](https://mlsanity.com/paper/2205.04997/) (2022)
- [Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality](https://mlsanity.com/paper/1810.09498/) (2018)
- [Automatic Change-Point Detection in Time Series via Deep Learning](https://mlsanity.com/paper/2211.03860/) (2022)
- [Optimal nonparametric multivariate change point detection and localization](https://mlsanity.com/paper/1910.13289/) (2019)
- [Change Point Estimation in a Dynamic Stochastic Block Model](https://mlsanity.com/paper/1812.03090/) (2018)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Optimal Change Point Detection and Localization in Sparse Dynamic Networks](https://mlsanity.com/paper/1809.09602/) (2018)
- [Minimax rates in sparse, high-dimensional changepoint detection](https://mlsanity.com/paper/1907.10012/) (2019)
- [Localizing Changes in High-Dimensional Regression Models](https://mlsanity.com/paper/2010.10410/) (2020)
- [Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models](https://mlsanity.com/paper/2211.11368/) (2022)
- [Approximate Message Passing for the Matrix Tensor Product Model](https://mlsanity.com/paper/2306.15580/) (2023)
- [Approximate l0-penalized estimation of piecewise-constant signals on graphs](https://mlsanity.com/paper/1703.01421/) (2017)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Change point inference in high-dimensional regression models under temporal dependence](https://mlsanity.com/paper/2207.12453/) (2022)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Computationally efficient change point detection for high-dimensional regression](https://mlsanity.com/paper/1601.03704/) (2016)
- [Sparse change detection in high-dimensional linear regression](https://mlsanity.com/paper/2208.06326/) (2022)

## Abstract (arXiv)

We consider the problem of localizing change points in a generalized linear model (GLM), a model that covers many widely studied problems in statistical learning including linear, logistic, and rectified linear regression. We propose a novel and computationally efficient Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations, and rigorously characterize its performance in the high-dimensional limit where the number of parameters p is proportional to the number of samples n. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic Hausdorff error of our change point estimates, and allows us to tailor the algorithm to take advantage of any prior structural information on the signals and change points. Moreover, we show how our AMP iterates can be used to efficiently compute a Bayesian posterior distribution over the change point locations in the high-dimensional limit. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic and real data in the settings of linear, logistic, and rectified linear regression.