Implicit Regularization of Random Feature Models

Abstract

Random Feature (RF) models are used as efficient parametric approximations of kernel methods. We investigate, by means of random matrix theory, the connection between Gaussian RF models and Kernel Ridge Regression (KRR). For a Gaussian RF model with $P$ features, $N$ data points, and a ridge $\lambda$, we show that the average (i.e. expected) RF predictor is close to a KRR predictor with an effective ridge $\tilde{\lambda }$. We show that $\tilde{\lambda }>\lambda$ and $\tilde{\lambda }\searrow \lambda$ monotonically as $P$ grows, thus revealing the implicit regularization effect of finite RF sampling. We then compare the risk (i.e. test error) of the $\tilde{\lambda }$-KRR predictor with the average risk of the $\lambda$-RF predictor and obtain a precise and explicit bound on their difference. Finally, we empirically find an extremely good agreement between the test errors of the average $\lambda$-RF predictor and $\tilde{\lambda }$-KRR predictor.

References in corpus (11)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Benign Overfitting in Linear Regression
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Generalization Properties of Learning with Random Features
• Scaling description of generalization with number of parameters in deep learning
• Orthogonal Random Features
• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• Optimal Rates for Random Fourier Features
• Combinatorial theory of permutation-invariant random matrices II: cumulants, freeness and Levy processes
• Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance

Cited by in corpus (6)

• Towards Understanding the Spectral Bias of Deep Learning
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• Getting Better from Worse: Augmented Bagging and a Cautionary Tale of Variable Importance
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
• Early Stopping in Deep Networks: Double Descent and How to Eliminate it