Optimal errors and phase transitions in high-dimensional generalized linear models
From MaRDI portal
Abstract: Generalized linear models (GLMs) arise in high-dimensional machine learning, statistics, communications and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant in problems such as compressed sensing, error-correcting codes or benchmark models in neural networks. We evaluate the mutual information (or "free entropy") from which we deduce the Bayes-optimal estimation and generalization errors. Our analysis applies to the high-dimensional limit where both the number of samples and the dimension are large and their ratio is fixed. Non-rigorous predictions for the optimal errors existed for special cases of GLMs, e.g. for the perceptron, in the field of statistical physics based on the so-called replica method. Our present paper rigorously establishes those decades old conjectures and brings forward their algorithmic interpretation in terms of performance of the generalized approximate message-passing algorithm. Furthermore, we tightly characterize, for many learning problems, regions of parameters for which this algorithm achieves the optimal performance, and locate the associated sharp phase transitions separating learnable and non-learnable regions. We believe that this random version of GLMs can serve as a challenging benchmark for multi-purpose algorithms. This paper is divided in two parts that can be read independently: The first part (main part) presents the model and main results, discusses some applications and sketches the main ideas of the proof. The second part (supplementary informations) is much more detailed and provides more examples as well as all the proofs.
Recommendations
- Generalization performance of Bayes optimal classification algorithm for learning a perceptron
- Learning and generalization errors for the 2D binary perceptron.
- The existence of maximum likelihood estimate in high-dimensional binary response generalized linear models
- Mean field asymptotics in high-dimensional statistics: from exact results to efficient algorithms
- Large scale analysis of generalization error in learning using margin based classification methods
Cited in
(72)- The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
- On the computational tractability of statistical estimation on amenable graphs
- Optimal combination of linear and spectral estimators for generalized linear models
- LASSO risk and phase transition under dependence
- Fundamental barriers to high-dimensional regression with convex penalties
- The asymptotic distribution of the MLE in high-dimensional logistic models: arbitrary covariance
- Hamilton-Jacobi equations for inference of matrix tensor products
- Strong replica symmetry in high-dimensional optimal Bayesian inference
- Concentration of multi-overlaps for random dilute ferromagnetic spin models
- Annealing and replica-symmetry in deep Boltzmann machines
- Finite-sample analysis of \(M\)-estimators using self-concordance
- Nonequilibrium thermodynamics of self-supervised learning
- Phase transition in random tensors with multiple independent spikes
- The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
- A spin Glass model for reconstructing nonlinearly encrypted signals corrupted by noise
- Fundamental limits of weak recovery with applications to phase retrieval
- A new approach to Laplacian solvers and flow problems
- Online stochastic gradient descent on non-convex losses from high-dimensional inference
- Matrix inference and estimation in multi-layer models*
- Generalisation error in learning with random features and the hidden manifold model*
- scientific article; zbMATH DE number 7625184 (Why is no real title available?)
- Approximate message passing with spectral initialization for generalized linear models*
- Disordered systems insights on computational hardness
- The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models
- Analysis of Bayesian inference algorithms by the dynamical functional approach
- On the universality of noiseless linear estimation with respect to the measurement matrix
- Information theoretic limits of learning a sparse rule
- Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
- High-temperature expansions and message passing algorithms
- Entropy and mutual information in models of deep neural networks*
- The committee machine: computational to statistical gaps in learning a two-layers neural network
- Semi-analytic approximate stability selection for correlated data in generalized linear models
- Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm
- Generalized approximate survey propagation for high-dimensional estimation *
- Large dimensional analysis of general margin based classification methods
- A Unifying Tutorial on Approximate Message Passing
- Replica analysis of overfitting in generalized linear regression models
- Prediction errors for penalized regressions based on generalized approximate message passing
- Automatic bias correction for testing in high‐dimensional linear models
- The TAP free energy for high-dimensional linear regression
- An introduction to machine learning: a perspective from statistical physics
- Free energy of multi-layer generalized linear models
- Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
- Universality of regularized regression estimators in high dimensions
- Gibbs sampling the posterior of neural networks
- Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
- Asymptotic mutual information in quadratic estimation problems over compact groups
- Survey on algorithms for multi-index models
- Spectral estimators for structured generalized linear models via approximate message passing
- Correlation adjusted debiased Lasso: debiasing the Lasso with inaccurate covariate model
- A leave-one-out approach to approximate message passing
- High-dimensional learning of narrow neural networks
- Towards a mathematical understanding of neural network-based machine learning: what we know and what we don't
- Sharp thresholds in inference of planted subgraphs
- The generalization error of max-margin linear classifiers: benign overfitting and high dimensional asymptotics in the overparametrized regime
- Hitting the high-dimensional notes: an ODE for SGD learning dynamics on GLMs and multi-index models
- Injectivity of ReLU networks: perspectives from statistical physics
- Equivalence of state equations from different methods in high-dimensional regression
- High-dimensional asymptotics of denoising autoencoders
- Dimension free ridge regression
- Spectrum-aware debiasing: a modern inference framework with applications to principal components regression
- High-dimensional robust regression under heavy-tailed data: asymptotics and universality
- Bayes-optimal learning of deep random networks of extensive-width
- Asymptotic dynamics of alternating minimization for bilinear regression
- High-dimensional asymptotics of VAEs: threshold of posterior collapse and dataset-size dependence of rate-distortion curve
- A phase transition between positional and semantic learning in a solvable model of dot-product attention
- The role of the time-dependent Hessian in high-dimensional optimization
- Isolating the hard core of phaseless inference: the phase selection formulation
- Universality of estimators for high-dimensional linear models with block dependency
- Overlap gap and computational thresholds in the square wave perceptron
- Generalization performance of narrow shallow neural networks in the teacher-student setting
- A nonasymptotic distributional theory of approximate message passing for sparse and robust regression
This page was built for publication: Optimal errors and phase transitions in high-dimensional generalized linear models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222765)
