Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models

Abstract

Recent work showed that there could be a large gap between the classical uniform convergence bound and the actual test error of zero-training-error predictors (interpolators) such as deep neural networks. To better understand this gap, we study the uniform convergence in the nonlinear random feature model and perform a precise theoretical analysis on how uniform convergence depends on the sample size and the number of parameters. We derive and prove analytical expressions for three quantities in this model: 1) classical uniform convergence over norm balls, 2) uniform convergence over interpolators in the norm ball (recently proposed by Zhou et al. (2020)), and 3) the risk of minimum norm interpolator. We show that, in the setting where the classical uniform convergence bound is vacuous (diverges to $\infty$), uniform convergence over the interpolators still gives a non-trivial bound of the test error of interpolating solutions. We also showcase a different setting where classical uniform convergence bound is non-vacuous, but uniform convergence over interpolators can give an improved sample complexity guarantee. Our result provides a first exact comparison between the test errors and uniform convergence bounds for interpolators beyond simple linear models.

References in corpus (16)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Generalization Properties of Learning with Random Features
• Uniform convergence may be unable to explain generalization in deep learning
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Does data interpolation contradict statistical optimality?
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• A Precise Performance Analysis of Learning with Random Features
• Understanding Double Descent Requires a Fine-Grained Bias-Variance Decomposition
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Failures of model-dependent generalization bounds for least-norm interpolation
• On Uniform Convergence and Low-Norm Interpolation Learning