mlsanityData to 7 Oct 2026

Mixed Regression via Approximate Message Passing

arXiv 2304.02229 ↗First posted 5 Apr 2023stat.ML cs.IT cs.LGcited by 3

On the map: Mixture-of-experts → MoE theory and gating functions

Abstract (arXiv)

We study the problem of regression in a generalized linear model (GLM) with multiple signals and latent variables. This model, which we call a matrix GLM, covers many widely studied problems in statistical learning, including mixed linear regression, max-affine regression, and mixture-of-experts. In mixed linear regression, each observation comes from one of L signal vectors (regressors), but we do not know which one; in max-affine regression, each observation comes from the maximum of L affine functions, each defined via a different signal vector. The goal in all these problems is to estimate the signals, and possibly some of the latent variables, from the observations. We propose a novel approximate message passing (AMP) algorithm for estimation in a matrix GLM and rigorously characterize its performance in the high-dimensional limit. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic mean-squared error. The state evolution characterization can be used to tailor the AMP algorithm to take advantage of any structural information known about the signals. Using state evolution, we derive an optimal choice of AMP `denoising' functions that minimizes the estimation error in each iteration. The theoretical results are validated by numerical simulations for mixed linear regression, max-affine regression, and mixture-of-experts. For max-affine regression, we propose an algorithm that combines AMP with expectation-maximization to estimate intercepts of the model along with the signals. The numerical results show that AMP significantly outperforms other estimators for mixed linear regression and max-affine regression in most parameter regimes.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Placed in MoE theory and gating functions, one of 12 directions in Mixture-of-experts. Builds on 41 of its 99 references that are in the map. First posted on arXiv 5 Apr 2023.

Builds on

41 of 99 references.

Closest ancestors · 3

Same direction, newest first

  1. 2019Convergence Rates for Gaussian Mixtures of Experts9 Jul
  2. 2019Learning in Gated Neural Networks6 Jun
  3. 2018Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms21 Feb

Other references · 38

  1. 2017Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layercited by 3,413
  2. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 131
  3. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  4. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  5. 2018A modern maximum-likelihood theory for high-dimensional logistic regressioncited by 79
  6. 2017Hard Mixtures of Experts for Large Scale Weakly Supervised Visioncited by 67
  7. 2013Phase Retrieval using Alternating Minimizationcited by 58
  8. 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
  9. 2021A unifying tutorial on Approximate Message Passingcited by 49
  10. 2020Meta-learning for mixed linear regressioncited by 44
  11. 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
  12. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
26 more
  1. 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
  2. 2021Graph-based Approximate Message Passing Iterationscited by 35
  3. 2020Approximate Message Passing algorithms for rotationally invariant matricescited by 31
  4. 2019Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Momentscited by 26
  5. 2013Spectral Experts for Estimating Mixtures of Linear Regressionscited by 22
  6. 2014Phase transitions and sample complexity in Bayes-optimal matrix factorizationcited by 22
  7. 2020Approximate Message Passing with Spectral Initialization for Generalized Linear Modelscited by 22
  8. 2015Regularized EM Algorithms: A Unified Framework and Statistical Guaranteescited by 19
  9. 2017Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximizationcited by 19
  10. 2021Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initializationcited by 18
  11. 2022A Non-Asymptotic Framework for Approximate Message Passing in Spiked Modelscited by 18
  12. 2015A Computational Framework for Multivariate Convex Regression and its Variantscited by 16
  13. 2020Universality of Approximate Message Passing Algorithmscited by 16
  14. 2019Iterative Least Trimmed Squares for Mixed Linear Regressioncited by 13
  15. 2020Alternating Minimization Converges Super-Linearly for Mixed Linear Regressioncited by 12
  16. 2022On Learning Mixture of Linear Regressions in the Non-Realizable Settingcited by 10
  17. 2019Fitting Tractable Convex Sets to Support Function Evaluationscited by 7
  18. 2019Sample Complexity of Learning Mixtures of Sparse Linear Regressionscited by 7
  19. 2022Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Modelscited by 7
  20. 2023Statistical-Computational Tradeoffs in Mixed Sparse Linear Regressioncited by 7
  21. 2018Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrievalcited by 6
  22. 2021Support Recovery of Sparse Signals from a Mixture of Linear Measurementscited by 6
  23. 2020Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regressioncited by 5
  24. 2022Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxationcited by 4
  25. 2013Phase retrieval for imaging problemscited by 3
  26. 2023Imbalanced Mixed Linear Regressioncited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 1.

3 papers.

  1. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  2. 2023Linear Regression using Heterogeneous Data Batchescited by 3
  3. 2024Inferring Change Points in High-Dimensional Regression via Approximate Message Passingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Matrix-Free Least Squares Solvers: Values, Gradients, and What to Do With Them
  2. 2026Learning with Synthetic Data via SGD in High-Dimensional Linear Regression
  3. 2019Regularized Estimation and Feature Selection in Mixtures of Generalized Linear Experts
  4. 2025Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression
  5. 2021Non-asymptotic model selection in block-diagonal mixture of polynomial experts models
  6. 2026A Random Matrix Theory Perspective on the Consistency of Diffusion Models
  7. 2026Free Decompression with Algebraic Spectral Curves
  8. 2026SSR-Merge: Subspace Signal Routing for Training-Free LoRA Merging in Diffusion Models