Mixed Regression via Approximate Message Passing
- URL: http://arxiv.org/abs/2304.02229v2
- Date: Tue, 15 Aug 2023 14:46:50 GMT
- Title: Mixed Regression via Approximate Message Passing
- Authors: Nelvin Tan, Ramji Venkataramanan
- Abstract summary: We study the problem of regression in a generalized linear model (GLM) with multiple signals and latent variables.
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.
- Score: 16.91276351457051
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- REAL Sampling: Boosting Factuality and Diversity of Open-Ended Generation via Asymptotic Entropy [93.8400683020273]
Decoding methods for large language models (LLMs) usually struggle with the tradeoff between ensuring factuality and maintaining diversity.
We propose REAL sampling, a decoding method that improved factuality and diversity over nucleus sampling.
arXiv Detail & Related papers (2024-06-11T21:44:49Z) - Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms [22.79595679373698]
Mixed linear regression is a well-studied problem in statistics and machine learning.
In this paper, we consider the more general problem of learning of mixed linear regression from samples.
We show that the AM and EM algorithms lead to learning in mixed linear regression by converging to the population loss minimizers.
arXiv Detail & Related papers (2024-06-03T09:43:24Z) - Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression [5.883916678819683]
We study the trajectory of iterations and the convergence rates of the Expectation-Maximization (EM) algorithm for two-component Mixed Linear Regression (2MLR)
Recent results have established the super-linear convergence of EM for 2MLR in the noiseless and high SNR settings.
arXiv Detail & Related papers (2024-05-28T14:46:20Z) - Max-affine regression via first-order methods [7.12511675782289]
The max-affine model ubiquitously arises in applications in signal processing and statistics.
We present a non-asymptotic convergence analysis of gradient descent (GD) and mini-batch gradient descent (SGD) for max-affine regression.
arXiv Detail & Related papers (2023-08-15T23:46:44Z) - Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood
Estimation for Latent Gaussian Models [69.22568644711113]
We introduce probabilistic unrolling, a method that combines Monte Carlo sampling with iterative linear solvers to circumvent matrix inversions.
Our theoretical analyses reveal that unrolling and backpropagation through the iterations of the solver can accelerate gradient estimation for maximum likelihood estimation.
In experiments on simulated and real data, we demonstrate that probabilistic unrolling learns latent Gaussian models up to an order of magnitude faster than gradient EM, with minimal losses in model performance.
arXiv Detail & Related papers (2023-06-05T21:08:34Z) - Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models [31.58736590532443]
We consider the problem of estimating two statistically independent signals in a mixed generalized linear model.
Our characterization exploits a mix of tools from random matrices, free probability and the theory of approximate message passing algorithms.
arXiv Detail & Related papers (2022-11-21T11:35:25Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression.
Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates.
The proposed approach is implemented in the R package probe.
arXiv Detail & Related papers (2022-09-16T19:15:50Z) - Graph Polynomial Convolution Models for Node Classification of
Non-Homophilous Graphs [52.52570805621925]
We investigate efficient learning from higher-order graph convolution and learning directly from adjacency matrix for node classification.
We show that the resulting model lead to new graphs and residual scaling parameter.
We demonstrate that the proposed methods obtain improved accuracy for node-classification of non-homophilous parameters.
arXiv Detail & Related papers (2022-09-12T04:46:55Z) - Inverting brain grey matter models with likelihood-free inference: a
tool for trustable cytoarchitecture measurements [62.997667081978825]
characterisation of the brain grey matter cytoarchitecture with quantitative sensitivity to soma density and volume remains an unsolved challenge in dMRI.
We propose a new forward model, specifically a new system of equations, requiring a few relatively sparse b-shells.
We then apply modern tools from Bayesian analysis known as likelihood-free inference (LFI) to invert our proposed model.
arXiv Detail & Related papers (2021-11-15T09:08:27Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
We consider the task of heavy-tailed statistical estimation given streaming $p$ samples.
We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
arXiv Detail & Related papers (2021-08-25T21:30:27Z) - Max-Linear Regression by Convex Programming [5.366354612549172]
We formulate and analyze a scalable convex program given by anchored regression (AR) as the estimator for the max-linear regression problem.
Our result shows a sufficient number of noise-free observations for exact recovery scales as $k4p$ up to a logarithmic factor.
arXiv Detail & Related papers (2021-03-12T00:55:54Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.