A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent

Abstract

This article characterizes the exact asymptotics of random Fourier feature (RFF) regression, in the realistic setting where the number of data samples $n$, their dimension $p$, and the dimension of feature space $N$ are all large and comparable. In this regime, the random RFF Gram matrix no longer converges to the well-known limiting Gaussian kernel matrix (as it does when $N\to \infty$ alone), but it still has a tractable behavior that is captured by our analysis. This analysis also provides accurate estimates of training and test regression errors for large $n,p,N$. Based on these estimates, a precise characterization of two qualitatively different phases of learning, including the phase transition between them, is provided; and the corresponding double descent test error curve is derived from this phase transition behavior. These results do not depend on strong assumptions on the data distribution, and they perfectly match empirical results on real-world data sets.

arXiv commentNeurIPS 2020

References in corpus (18)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• 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
• Benign Overfitting in Linear Regression
• On Lazy Training in Differentiable Programming
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Deterministic equivalents for certain functionals of large random matrices
• Generalization Properties of Learning with Random Features
• Just Interpolate: Kernel "Ridgeless" Regression Can Generalize
• The Emergence of Spectral Universality in Deep Networks
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Exact expressions for double descent and implicit regularization via surrogate random design
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• On Random Matrices Arising in Deep Neural Networks. Gaussian Case
• Concentration of Measure and Large Random Matrices with an application to Sample Covariance Matrices
• Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks
• Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Trained Deep Neural Networks

Cited by in corpus (7)

• On the interplay between data structure and loss function in classification problems
• Conditioning of Random Feature Matrices: Double Descent and Generalization Error
• Benign Overfitting and Noisy Features
• Learning from learning machines: a new generation of AI technology to meet the needs of science
• Asymptotics of Ridge Regression in Convolutional Models
• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models
• Good Classifiers are Abundant in the Interpolating Regime