# Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression

arXiv: https://arxiv.org/abs/2102.07181 · HTML: https://mlsanity.com/paper/2102.07181/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 14 Feb 2021.

## Builds on (most cited first, 21 of 21)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Probabilistic Backpropagation for Scalable Learning of Bayesian Neural Networks](https://mlsanity.com/paper/1502.05336/) (2015)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Optimal Regularization Can Mitigate Double Descent](https://mlsanity.com/paper/2003.01897/) (2020)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization](https://mlsanity.com/paper/1805.10939/) (2018)
- [The Sample Complexity of Learning Linear Predictors with the Squared Loss](https://mlsanity.com/paper/1406.5143/) (2014)
- [Deep pNML: Predictive Normalized Maximum Likelihood for Deep Neural Networks](https://mlsanity.com/paper/1904.12286/) (2019)
- [A New Look at an Old Problem: A Universal Learning Approach to Linear Regression](https://mlsanity.com/paper/1905.04708/) (2019)
- [Balancing Specialization, Generalization, and Compression for Detection and Tracking](https://mlsanity.com/paper/1909.11348/) (2019)
- [The Generalization Error of the Minimum-norm Solutions for Over-parameterized Neural Networks](https://mlsanity.com/paper/1912.06987/) (2019)
- [Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation](https://mlsanity.com/paper/2011.02696/) (2020)
- [Learning, compression, and leakage: Minimising classification error via meta-universal compression principles](https://mlsanity.com/paper/2010.07382/) (2020)
- [Learning Rotation Invariant Features for Cryogenic Electron Microscopy Image Reconstruction](https://mlsanity.com/paper/2101.03549/) (2021)
- [Minimum weight norm models do not always generalize well for over-parameterized problems](https://mlsanity.com/paper/1811.07055/) (2018)

## Built on by (most cited first, 2 of 2)

- [Collaborative Image Understanding](https://mlsanity.com/paper/2210.11907/) (2022)
- [Beyond Ridge Regression for Distribution-Free Data](https://mlsanity.com/paper/2206.08757/) (2022)

## Abstract (arXiv)

A fundamental principle of learning theory is that there is a trade-off between the complexity of a prediction rule and its ability to generalize. Modern machine learning models do not obey this paradigm: They produce an accurate prediction even with a perfect fit to the training set. We investigate over-parameterized linear regression models focusing on the minimum norm solution: This is the solution with the minimal norm that attains a perfect fit to the training set. We utilize the recently proposed predictive normalized maximum likelihood (pNML) learner which is the min-max regret solution for the distribution-free setting. We derive an upper bound of this min-max regret which is associated with the prediction uncertainty. We show that if the test sample lies mostly in a subspace spanned by the eigenvectors associated with the large eigenvalues of the empirical correlation matrix of the training data, the model generalizes despite its over-parameterized nature. We demonstrate the use of the pNML regret as a point-wise learnability measure on synthetic data and successfully observe the double-decent phenomenon of the over-parameterized models on UCI datasets.