  A fundamental tenet of learning theory is that a trade-off exists between the
complexity of a prediction rule and its ability to generalize. The
double-decent phenomenon shows that modern machine learning models do not obey
this paradigm: beyond the interpolation limit, the test error declines as model
complexity increases. We investigate over-parameterization in linear regression
using the recently proposed predictive normalized maximum likelihood (pNML)
learner which is the min-max regret solution for individual data. We derive an
upper bound of its regret and 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 that it can
successfully predict the double-decent phenomenon using the UCI dataset.
