Research map / Learning theory and algorithms / Matrix and tensor methods
Inferring Change Points in High-Dimensional Linear Regression via Approximate Message Passing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an approximate message passing (AMP) algorithm with non-separable denoisers for estimating signals and change point locations in high-dimensional GLMs (linear, logistic, ReLU), with state evolution guarantees and a posterior over change points.
Problem
Localizing change points in high-dimensional generalized linear models where the signal dimension p grows proportionally with sample size n, with no sparsity assumption required on the signals.
Approach
An AMP iteration with non-separable denoisers that exploit the dependence structure of signal configurations induced by change points; state evolution gives exact asymptotics for Hausdorff error, and AMP iterates yield an approximate Bayesian posterior over change point locations.
Key results
- AMP's empirical normalized Hausdorff distance closely matches state evolution predictions for linear, logistic and ReLU models.
- AMP consistently achieves the lowest Hausdorff distance among DP, DPDU, DCDP and CHARCOAL in sparse linear settings while outperforming most in runtime.
- On the MI data, AMP posterior concentrates on age 66 as a change point in the relation between CHF and medical features; the two fitted logistic vectors have correlation 0.09.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AMP instead of the compared state-of-the-art algorithms | High-dimensional linear regression with sparse or sparse-difference signals · Linear change-point regression | Hausdorff distance | Helped |
| Use AMP rather than binary segmentation | Sparse logistic regression with change points · Logistic change-point regression, maximum of L=3 or 4 signals | Hausdorff distance | No clear effect |
| Use AMP rather than binary segmentation while assuming L=3 | Sparse logistic regression with change points · Logistic change-point regression | runtime | Helped |
| Increase δ | AMP with exactly 3 signals · Logistic change-point regression | Hausdorff distance | Helped |
Limitations
- Theory assumes i.i.d. Gaussian covariates; extension to general designs is left to future work.
- Performance depends on the choice of change point prior and signal priors; misspecification can degrade performance.
- Assumes a known upper bound L on the number of signals.
Experimental setup
Datasets: Myocardial Infarction complications dataset (n=1700, p=111) sparse grayscale image (compressed sensing experiment)
Benchmarks: synthetic linear, logistic, ReLU change point regression Myocardial Infarction complications dataset compressed sensing with change points
Metrics: normalized Hausdorff distance estimated number of change points runtime approximate posterior density
Baselines: DP DPDU DCDP CHARCOAL binary segmentation
Builds on: approximate message passing state evolution mixed linear regression AMP symmetric AMP (Javanmard-Montanari)
Closest papers by meaning
- Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions (ICML 2023 · similarity 0.86)
- Diffusion Models With Learned Adaptive Noise (NeurIPS 2024 · similarity 0.84)
- Provable Posterior Sampling with Denoising Oracles via Tilted Transport (NeurIPS 2024 · similarity 0.83)
- Optimal Online Change Detection via Random Fourier Features (NeurIPS 2025 · similarity 0.83)
- Stochastic Localization via Iterative Posterior Sampling (ICML 2024 · similarity 0.83)
- Adapt and Diffuse: Sample-adaptive Reconstruction via Latent Diffusion Models (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.