# Beyond Ridge Regression for Distribution-Free Data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 17 Jun 2022.

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

- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparison](https://mlsanity.com/paper/1703.00512/) (2017)
- [Near-Optimal Linear Regression under Distribution Shift](https://mlsanity.com/paper/2106.12108/) (2021)
- [Single Layer Predictive Normalized Maximum Likelihood for Out-of-Distribution Detection](https://mlsanity.com/paper/2110.09246/) (2021)
- [Ridge Regression: Structure, Cross-Validation, and Sketching](https://mlsanity.com/paper/1910.02373/) (2019)
- [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)
- [Revisiting minimum description length complexity in overparameterized models](https://mlsanity.com/paper/2006.10189/) (2020)
- [Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation](https://mlsanity.com/paper/2011.02696/) (2020)
- [Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression](https://mlsanity.com/paper/2102.07181/) (2021)
- [Utilizing Adversarial Targeted Attacks to Boost Adversarial Robustness](https://mlsanity.com/paper/2109.01945/) (2021)

## Abstract (arXiv)

In supervised batch learning, the predictive normalized maximum likelihood (pNML) has been proposed as the min-max regret solution for the distribution-free setting, where no distributional assumptions are made on the data. However, the pNML is not defined for a large capacity hypothesis class as over-parameterized linear regression. For a large class, a common approach is to use regularization or a model prior. In the context of online prediction where the min-max solution is the Normalized Maximum Likelihood (NML), it has been suggested to use NML with ``luckiness'': A prior-like function is applied to the hypothesis class, which reduces its effective size. Motivated by the luckiness concept, for linear regression we incorporate a luckiness function that penalizes the hypothesis proportionally to its l2 norm. This leads to the ridge regression solution. The associated pNML with luckiness (LpNML) prediction deviates from the ridge regression empirical risk minimizer (Ridge ERM): When the test data reside in the subspace corresponding to the small eigenvalues of the empirical correlation matrix of the training data, the prediction is shifted toward 0. Our LpNML reduces the Ridge ERM error by up to 20% for the PMLB sets, and is up to 4.9% more robust in the presence of distribution shift compared to recent leading methods for UCI sets.