Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models

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.

101 pages, 5 figures

References in corpus (26)

• Scikit-learn: Machine Learning in Python
• Message Passing Algorithms for Compressed Sensing
• The information bottleneck method
• Opening the Black Box of Deep Neural Networks via Information
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Statistical physics of inference: Thresholds and algorithms
• The Thermodynamic Limit in Mean Field Spin Glass Models
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Universality in polytope phase transitions and message passing algorithms
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• A generalization of the Lindeberg principle
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Information-theoretic thresholds from the cavity method
• Tractable approximations for probabilistic models: The adaptive TAP mean field approach
• The Mutual Information in Random Linear Estimation
• A note on classical ground state energies
• Statistical mechanics of lossy data compression using a non-monotonic perceptron
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• Bayesian signal reconstruction for 1-bit compressed sensing
• Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization
• Toward Fast Reliable Communication at Rates Near Capacity with Gaussian Noise
• Phase transitions in spiked matrix estimation: information-theoretic analysis

Cited by in corpus (84)

• Machine learning and the physical sciences
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Entropy and mutual information in models of deep neural networks
• Modelling the influence of data structure on learning in neural networks: the hidden manifold model
• Generalisation error in learning with random features and the hidden manifold model
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• The Lasso with general Gaussian designs with applications to hypothesis testing
• High-temperature Expansions and Message Passing Algorithms
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem
• Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm
• Disordered Systems Insights on Computational Hardness
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• Fundamental limits to learning closed-form mathematical models from data
• Annealing and replica-symmetry in Deep Boltzmann Machines
• The committee machine: Computational to statistical gaps in learning a two-layers neural network
• The Asymptotic Distribution of the MLE in High-dimensional Logistic Models: Arbitrary Covariance
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Phase retrieval in high dimensions: Statistical and computational phase transitions
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• High-dimensional rank-one nonsymmetric matrix decomposition: the spherical case
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices
• Fundamental problems in statistical physics XIV: Lecture on Machine Learning
• Learning curves for the multi-class teacher-student perceptron
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• The estimation error of general first order methods
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• Deep learning via message passing algorithms based on belief propagation
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization
• Landscape Complexity for the Empirical Risk of Generalized Linear Models
• On the interplay between data structure and loss function in classification problems
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Thresholds of descending algorithms in inference problems
• Mutual information for low-rank even-order symmetric tensor estimation
• Gardner formula for Ising perceptron models at small densities
• Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing
• Theoretical characterization of uncertainty in high-dimensional linear classification
• Concentration of multi-overlaps for random ferromagnetic spin models
• Bilinear Generalized Vector Approximate Message Passing
• Exact results on high-dimensional linear regression via statistical physics
• Gibbs Sampling the Posterior of Neural Networks
• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
• Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
• CAD: Debiasing the Lasso with inaccurate covariate model
• Inference in Multi-Layer Networks with Matrix-Valued Unknowns
• Analysis of Bayesian Inference Algorithms by the Dynamical Functional Approach
• Semi-analytic approximate stability selection for correlated data in generalized linear models
• Neural-prior stochastic block model
• High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curve
• Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent
• The Geometry of Over-parameterized Regression and Adversarial Perturbations
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Generalization Error of Generalized Linear Models in High Dimensions
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Solvable Model for Inheriting the Regularization through Knowledge Distillation
• Analysis of Diffusion Models for Manifold Data
• On the Cryptographic Hardness of Learning Single Periodic Neurons
• Free energy of multi-layer generalized linear models
• Construction of optimal spectral methods in phase retrieval
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Blind calibration for compressed sensing: State evolution and an online algorithm
• Nonequilibrium thermodynamics of self-supervised learning
• Large dimensional analysis of general margin based classification methods
• High-dimensional inference: a statistical mechanics perspective
• Implicit Bias of Linear RNNs
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Bias-variance decomposition of overparameterized regression with random linear features
• Good Classifiers are Abundant in the Interpolating Regime
• LASSO risk and phase transition under dependence
• Analyzing Training Using Phase Transitions in Entropy---Part I: General Theory
• Fundamental limits and algorithms for sparse linear regression with sublinear sparsity
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Inference in Spreading Processes with Neural-Network Priors
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation