Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression
This work provides a unifying theory for understanding overfitting and regularization in high-dimensional linear regression, which is incremental but offers precise risk characterizations for practitioners and theorists.
The paper tackles the problem of analyzing excess risk in linear regression, particularly for interpolation learning and regularization, by developing a refined optimistic rate bound that avoids hidden constants and logarithmic factors, recovering tight guarantees for low-norm interpolators and classical results for ridge and LASSO regression.
We study a localized notion of uniform convergence known as an "optimistic rate" (Panchenko 2002; Srebro et al. 2010) for linear regression with Gaussian data. Our refined analysis avoids the hidden constant and logarithmic factor in existing results, which are known to be crucial in high-dimensional settings, especially for understanding interpolation learning. As a special case, our analysis recovers the guarantee from Koehler et al. (2021), which tightly characterizes the population risk of low-norm interpolators under the benign overfitting conditions. Our optimistic rate bound, though, also analyzes predictors with arbitrary training error. This allows us to recover some classical statistical guarantees for ridge and LASSO regression under random designs, and helps us obtain a precise understanding of the excess risk of near-interpolators in the over-parameterized regime.