Optimal Implicit Bias in Linear Regression
Authors:
Preprint
Abstract
Most modern learning problems are over-parameterized, where the number of learnable parameters is much greater than the number of training data points. In this over-parameterized regime, the training loss typically has infinitely many global optima that completely interpolate the data with varying generalization performance. The particular global optimum we converge to depends on the implicit bias of the optimization algorithm. The question we address in this paper is, ``What is the implicit bias that leads to the best generalization performance?". To find the optimal implicit bias, we provide a precise asymptotic analysis of the generalization performance of interpolators obtained from the minimization of convex functions/potentials for over-parameterized linear regression with non-isotropic Gaussian data. In particular, we obtain a tight lower bound on the best generalization error possible among this class of interpolators in terms of the over-parameterization ratio, the variance of the noise in the labels, the eigenspectrum of the data covariance, and the underlying distribution of the parameter to be estimated. Finally, we find the optimal convex implicit bias that achieves this lower bound under certain sufficient conditions involving the log-concavity of the distribution of a Gaussian convolved with the prior of the true underlying parameter.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Universality of regularized regression estimators in high dimensionsThe Annals of Statistics, 2023
- SLOPE for Sparse Linear Regression: Asymptotics and Optimal RegularizationIEEE Transactions on Information Theory, 2022
- Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently2022
- The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuningThe Annals of Statistics, 2021
- High-dimensional asymptotics of prediction: Ridge regression and classificationThe Annals of Statistics, 2018
- Statistical Mechanics of Optimal Convex Inference in High DimensionsPhysical Review X, 2016
- Sharp MSE Bounds for Proximal DenoisingFoundations of Computational Mathematics, 2015
- The LASSO Risk for Gaussian MatricesIEEE Transactions on Information Theory, 2011
- The convolution inequality for entropy powersIEEE Transactions on Information Theory, 1965