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

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