On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression

Abstract

We consider the linear model $\mathbf{y}=\mathbf{X}{\beta }_{\star }+\epsilon$ with $\mathbf{X}\in {\mathbb{R}}^{n\times p}$ in the overparameterized regime $p>n$. We estimate ${\beta }_{\star }$ via generalized (weighted) ridge regression: ${\hat{\beta }}_{\lambda }={\left({\mathbf{X}}^T\mathbf{X}+\lambda {\mathbf{\Sigma }}_w\right)}^{†}{\mathbf{X}}^T\mathbf{y}$, where ${\mathbf{\Sigma }}_w$ is the weighting matrix. Under a random design setting with general data covariance ${\mathbf{\Sigma }}_x$ and anisotropic prior on the true coefficients $\mathbb{E}{\beta }_{\star }{\beta }_{\star }^T={\mathbf{\Sigma }}_{\beta }$, we provide an exact characterization of the prediction risk $\mathbb{E}(y-{\mathbf{x}}^T{\hat{\beta }}_{\lambda }{)}^2$ in the proportional asymptotic limit $p/n\to \gamma \in (1,\infty )$. Our general setup leads to a number of interesting findings. We outline precise conditions that decide the sign of the optimal setting ${\lambda }_{\mathrm{opt}}$ for the ridge parameter $\lambda$ and confirm the implicit ${\ell }_2$ regularization effect of overparameterization, which theoretically justifies the surprising empirical observation that ${\lambda }_{\mathrm{opt}}$ can be negative in the overparameterized regime. We also characterize the double descent phenomenon for principal component regression (PCR) when both $\mathbf{X}$ and ${\beta }_{\star }$ are anisotropic. Finally, we determine the optimal weighting matrix ${\mathbf{\Sigma }}_w$ for both the ridgeless ($\lambda \to 0$) and optimally regularized ($\lambda ={\lambda }_{\mathrm{opt}}$) case, and demonstrate the advantage of the weighted objective over standard ridge regression and PCR.

arXiv commentNeurIPS 2020

References in corpus (19)

• Decoupled Weight Decay Regularization
• Overcoming catastrophic forgetting in neural networks
• Benign Overfitting in Linear Regression
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Multiplicative Normalizing Flows for Variational Bayesian Neural Networks
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Benign overfitting in ridge regression
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• A new class of generalized Bayes minimax ridge regression estimators
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Three Mechanisms of Weight Decay Regularization
• Exact expressions for double descent and implicit regularization via surrogate random design
• On the number of variables to use in principal component regression
• Asymptotics of Ridge (less) Regression under General Source Condition
• A Continuous-Time View of Early Stopping for Least Squares
• When Does Preconditioning Help or Hurt Generalization?
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Learning Neural Networks with Adaptive Regularization

Cited by in corpus (6)

• When Does Preconditioning Help or Hurt Generalization?
• Towards an Understanding of Benign Overfitting in Neural Networks
• Dimensionality reduction, regularization, and generalization in overparameterized regressions
• Modeling Structured Data Learning with Restricted Boltzmann Machines in the Teacher-Student Setting
• Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation
• Interpolation can hurt robust generalization even when there is no noise