Optimal errors and phase transitions in high-dimensional generalized linear models

DOI10.1073/PNAS.1802705116zbMATH Open1416.62421arXiv1708.03395OpenAlexW2918745211WikidataQ64084019 ScholiaQ64084019MaRDI QIDQ5222765FDOQ5222765

Authors: Jean Barbier, Florent Krzakala, Léo Miolane, Lenka Zdeborová, Nicolas Macris 

Publication date: 3 July 2019

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1708.03395

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

Mathematics Subject Classification ID

Generalized linear models (logistic models) (62J12) Approximation algorithms (68W25)

Cited In (45)

• Approximate message passing with spectral initialization for generalized linear models*
• Matrix inference and estimation in multi-layer models*
• An introduction to machine learning: a perspective from statistical physics
• LASSO risk and phase transition under dependence
• Gibbs sampling the posterior of neural networks
• Finite-sample analysis of \(M\)-estimators using self-concordance
• The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• A Unifying Tutorial on Approximate Message Passing
• Free energy of multi-layer generalized linear models
• Semi-analytic approximate stability selection for correlated data in generalized linear models
• Nonequilibrium thermodynamics of self-supervised learning
• Analysis of Bayesian inference algorithms by the dynamical functional approach
• Fundamental limits of weak recovery with applications to phase retrieval
• The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
• Annealing and replica-symmetry in deep Boltzmann machines
• The asymptotic distribution of the MLE in high-dimensional logistic models: arbitrary covariance
• Hamilton-Jacobi equations for inference of matrix tensor products
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universality of regularized regression estimators in high dimensions
• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
• Automatic bias correction for testing in high‐dimensional linear models
• Strong replica symmetry in high-dimensional optimal Bayesian inference
• Concentration of multi-overlaps for random dilute ferromagnetic spin models
• Phase transition in random tensors with multiple independent spikes
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
• High-temperature expansions and message passing algorithms
• On the universality of noiseless linear estimation with respect to the measurement matrix
• Prediction errors for penalized regressions based on generalized approximate message passing
• A New Approach to Laplacian Solvers and Flow Problems
• On the computational tractability of statistical estimation on amenable graphs
• Entropy and mutual information in models of deep neural networks*
• The committee machine: computational to statistical gaps in learning a two-layers neural network
• Disordered systems insights on computational hardness
• Generalisation error in learning with random features and the hidden manifold model*
• The TAP free energy for high-dimensional linear regression
• Replica analysis of overfitting in generalized linear regression models
• Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm
• Optimal combination of linear and spectral estimators for generalized linear models
• Information theoretic limits of learning a sparse rule
• A spin Glass model for reconstructing nonlinearly encrypted signals corrupted by noise
• Fundamental barriers to high-dimensional regression with convex penalties
• Large dimensional analysis of general margin based classification methods

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)