On the Universality of the Double Descent Peak in Ridgeless Regression
arXiv:2010.01851
Abstract
We prove a non-asymptotic distribution-independent lower bound for the expected mean squared generalization error caused by label noise in ridgeless linear regression. Our lower bound generalizes a similar known result to the overparameterized (interpolating) regime. In contrast to most previous works, our analysis applies to a broad class of input distributions with almost surely full-rank feature matrices, which allows us to cover various types of deterministic or random feature maps. Our lower bound is asymptotically sharp and implies that in the presence of label noise, ridgeless linear regression does not perform well around the interpolation threshold for any of these feature maps. We analyze the imposed assumptions in detail and provide a theory for analytic (random) feature maps. Using this theory, we can show that our assumptions are satisfied for input distributions with a (Lebesgue) density and feature maps given by random deep neural networks with analytic activation functions like sigmoid, tanh, softplus or GELU. As further examples, we show that feature maps from random Fourier features and polynomial kernels also satisfy our assumptions. We complement our theory with further experimental and analytic results.
arXiv commentPublished at ICLR 2021. 9 pages + 34 pages appendix. Changes in v8: Small corrections. Experimental results can be reproduced using the code at https://github.com/dholzmueller/universal_double_descent
References in corpus (21)
- Gaussian Error Linear Units (GELUs)
- Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
- On the Convergence of Adam and Beyond
- Reconciling modern machine learning practice and the bias-variance trade-off
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- Understanding deep learning requires rethinking generalization
- Searching for Activation Functions
- The generalization error of random features regression: Precise asymptotics and double descent curve
- The loss surface of deep and wide neural networks
- To understand deep learning we need to understand kernel learning
- A Modern Take on the Bias-Variance Tradeoff in Neural Networks
- Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
- Optimal Regularization Can Mitigate Double Descent
- More Data Can Hurt for Linear Regression: Sample-wise Double Descent
- The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization
- Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
- Multiple Descent: Design Your Own Generalization Curve
- Triple descent and the two kinds of overfitting: Where & why do they appear?
- Complex powers of analytic functions and meromorphic renormalization in QFT
- A VEST of the Pseudoinverse Learning Algorithm
- On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels