Universality Laws for High-Dimensional Learning with Random Features

Abstract

We prove a universality theorem for learning with random features. Our result shows that, in terms of training and generalization errors, a random feature model with a nonlinear activation function is asymptotically equivalent to a surrogate linear Gaussian model with a matching covariance matrix. This settles a so-called Gaussian equivalence conjecture based on which several recent papers develop their results. Our method for proving the universality theorem builds on the classical Lindeberg approach. Major ingredients of the proof include a leave-one-out analysis for the optimization problem associated with the training process and a central limit theorem, obtained via Stein's method, for weakly correlated random variables.

References in corpus (14)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• To understand deep learning we need to understand kernel learning
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Generalisation error in learning with random features and the hidden manifold model
• SGD Learns the Conjugate Kernel Class of the Network
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• The Gaussian equivalence of generative models for learning with shallow neural networks
• A Precise Performance Analysis of Learning with Random Features
• Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixtures
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• On the Inherent Regularization Effects of Noise Injection During Training
• Universality in Learning from Linear Measurements

Cited by in corpus (13)

• Learning curves of generic features maps for realistic datasets with a teacher-student model
• The Gaussian equivalence of generative models for learning with shallow neural networks
• Probing transfer learning with a model of synthetic correlated datasets
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• On the Inherent Regularization Effects of Noise Injection During Training
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• On the interplay between data structure and loss function in classification problems
• On the Double Descent of Random Features Models Trained with SGD
• Asymptotic Risk of Overparameterized Likelihood Models: Double Descent Theory for Deep Neural Networks
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Minimum complexity interpolation in random features models
• Harmless interpolation in regression and classification with structured features