Beyond Ridge Regression for Distribution-Free Data
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.