Generalisation error in learning with random features and the hidden manifold model

Abstract

We study generalised linear regression and classification for a synthetically generated dataset encompassing different problems of interest, such as learning with random features, neural networks in the lazy training regime, and the hidden manifold model. We consider the high-dimensional regime and using the replica method from statistical physics, we provide a closed-form expression for the asymptotic generalisation performance in these problems, valid in both the under- and over-parametrised regimes and for a broad choice of generalised linear model loss functions. In particular, we show how to obtain analytically the so-called double descent behaviour for logistic regression with a peak at the interpolation threshold, we illustrate the superiority of orthogonal against random Gaussian projections in learning with random features, and discuss the role played by correlations in the data generated by the hidden manifold model. Beyond the interest in these particular problems, the theoretical formalism introduced in this manuscript provides a path to further extensions to more complex tasks.

arXiv commentv2: ICML 2020 camera-ready

References in corpus (32)

• Scikit-learn: Machine Learning in Python
• Auto-Encoding Variational Bayes
• API design for machine learning software: experiences from the scikit-learn project
• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Statistical physics of inference: Thresholds and algorithms
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Exploring Generalization in Deep Learning
• On Lazy Training in Differentiable Programming
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Practical and Optimal LSH for Angular Distance
• Deterministic equivalents for certain functionals of large random matrices
• Statistical physics-based reconstruction in compressed sensing
• Scaling description of generalization with number of parameters in deep learning
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• Random Projections through multiple optical scattering: Approximating kernels at the speed of light
• Mean-field message-passing equations in the Hopfield model and its generalizations
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• A jamming transition from under- to over-parametrization affects loss landscape and generalization
• Statistical mechanics of complex neural systems and high dimensional data
• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• Surprises in High-Dimensional Ridgeless Least Squares Interpolation
• Kernel and Rich Regimes in Overparametrized Models
• The Gaussian equivalence of generative models for learning with shallow neural networks
• The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
• Structured adaptive and random spinners for fast machine learning computations
• Kernel computations from large-scale random features obtained by Optical Processing Units
• Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixtures
• ACDC: A Structured Efficient Linear Layer

Cited by in corpus (32)

• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Mapping of attention mechanisms to a generalized Potts model
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)
• Triple descent and the two kinds of overfitting: Where & why do they appear?
• Learning through atypical "phase transitions" in overparameterized neural networks
• A Precise Performance Analysis of Learning with Random Features
• Probing transfer learning with a model of synthetic correlated datasets
• Universality Laws for High-Dimensional Learning with Random Features
• Gaussian Universality of Perceptrons with Random Labels
• On Data-Augmentation and Consistency-Based Semi-Supervised Learning
• On the Inherent Regularization Effects of Noise Injection During Training
• Optimal regularizations for data generation with probabilistic graphical models
• Distributional Generalization: A New Kind of Generalization
• When Does Preconditioning Help or Hurt Generalization?
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Asymptotic theory of in-context learning by linear attention
• Random features and polynomial rules
• On the interplay between data structure and loss function in classification problems
• Theoretical characterization of uncertainty in high-dimensional linear classification
• Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines
• Optimal Learning with Excitatory and Inhibitory synapses
• Testing the Isotropic Cauchy Hypothesis
• High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curve
• Phases of learning dynamics in artificial neural networks: with or without mislabeled data
• Large dimensional analysis of general margin based classification methods
• Minimum complexity interpolation in random features models
• How isotropic kernels perform on simple invariants
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Ising Model Selection Using ${\ell }_1$-Regularized Linear Regression: A Statistical Mechanics Analysis