We study the generalization capability of nearly-interpolating linear
regressors: $\boldsymbol{\beta}$'s whose training error $\tau$ is positive but
small, i.e., below the noise floor. Under a random matrix theoretic assumption
on the data distribution and an eigendecay assumption on the data covariance
matrix $\boldsymbol{\Sigma}$, we demonstrate that any near-interpolator
exhibits rapid norm growth: for $\tau$ fixed, $\boldsymbol{\beta}$ has squared
$\ell_2$-norm $\mathbb{E}[\|{\boldsymbol{\beta}}\|_{2}^{2}] =
\Omega(n^{\alpha})$ where $n$ is the number of samples and $\alpha >1$ is the
exponent of the eigendecay, i.e., $\lambda_i(\boldsymbol{\Sigma}) \sim
i^{-\alpha}$. This implies that existing data-independent norm-based bounds are
necessarily loose. On the other hand, in the same regime we precisely
characterize the asymptotic trade-off between interpolation and generalization.
Our characterization reveals that larger norm scaling exponents $\alpha$
correspond to worse trade-offs between interpolation and generalization. We
verify empirically that a similar phenomenon holds for nearly-interpolating
shallow neural networks.

我们研究了接近插值线性回归器的泛化能力，证明了任何接近插值器都表现出快速的范数增长，并且精确表征了插值和泛化之间的渐进权衡。