On Uniform Convergence and Low-Norm Interpolation Learning

Introduction

In the past several years, it has become empirically clear that – contrary to traditional intuition – it is possible for models which exactly interpolate noisy training data to reliably generalize well on practical problems, especially in deep learning . We refer to this phenomenon as “interpolation learning.” It is closely related to the (re-)discovery of the “double descent” phenomenon , where many models first improve as their size is increased, then get much worse around the point where they can first interpolate the data, and then improve again as they become more and more overparametrized. Understanding interpolation learning, therefore, seems to be a key step on the path towards better theoretical understanding of the successes of deep learning.

We now know of a few settings where interpolating models can be shown to generalize well . In particular, significant recent attention has been paid to the minimum-norm linear interpolator (“ridgeless” regression) in certain high-dimensional linear regression regimes . This setting is of particular interest not only because it is reasonably accessible to study while exhibiting many of the surprising properties of more complex models, but also because this predictor is the same one found by (stochastic) gradient descent initialized at the origin, and so it seems plausible that its properties may generalize to more complex settings. Much is now understood about the properties of the minimum-norm interpolator for (sub-)Gaussian data, including necessary and sufficient conditions for its consistency. This line of inquiry has proved quite fertile for extensions to related settings and further results .

One striking feature of this body of work is that none of it is based on the core workhorse of learning theory, uniform convergence; most instead uses various tools, mostly from random matrix theory, to directly analyze the generalization error of a particular predictor. Indeed, some have argued that uniform convergence is unlikely to be able to explain interpolation learning; for instance, Mikhail Belkin has saidTalk at the Simons Institute for the Theory of Computing, July 2019: simons.berkeley.edu/talks/tbd-65 that “there are no [uniform generalization] bounds” with constants tight enough to explain interpolation learning, “and no reason they should exist.” Meanwhile, have also raised significant questions about the ability of uniform convergence arguments to explain learning in certain high-dimensional regimes. Perhaps, then, it is time to wholly abandon uniform convergence in favor of other tools.

We connect these two avenues of work by studying uniform convergence in a particular overparametrized linear regression problem (Section 2) where the minimal-norm interpolator is consistent. We prove that, indeed, uniform convergence bounds based on predictor norm cannot show any learning in this setting (Theorem 3.2). We also prove, following , that no uniform convergence bound can show consistency (Theorem 3.3), not only for the minimal-norm interpolator but even for a wide variety of natural interpolation algorithms.

Yet, even in this setting where the situation looks bleak, we need not abandon uniform convergence entirely. One option would be sidestep the negative results by considering uniform convergence not of our predictor, but of a surrogate separately shown to be not too different . We instead demonstrate that it is possible to show uniform convergence of our predictor directly if we allow ourselves a slightly weaker notion of uniform convergence, one long in common use in realizable PAC analyses: uniform convergence for predictors with zero error. Such a bound would be implied by, for example, “optimistic rates” , although existing results are not tight enough to show consistency in our setting. Instead we prove (Theorem 4.1) that a tight version of this notion of uniform convergence does hold in our setting for low-norm predictors. Our result exactly characterizes the asymptotic worst-case generalization gap for predictors of a given norm via a novel analysis based on strong duality of a particular non-convex problem, and show that while neither having a low norm nor interpolation is sufficient for generalization in our setting, the combination is. By doing so, not only do we prove consistency of the minimal-norm interpolator with a uniform convergence-type argument, we also provide new insight about the behavior of interpolation learning for solutions with low but not minimal norm.

Problem setting

We begin with a standard linear regression setup, with Gaussian data and errors. Take i.i.d. observations $(x_{1},y_{1}),...,(x_{n},y_{n})\sim\mathcal{D}^{n}$, where the joint distribution $\mathcal{D}$ is given by

We consider a “junk features” setting, where $x$ decomposes into “signal” and “junk” components, and analysis of interpolation learning is particularly appealing:

We will focus on the regime where $d_{S}$ is fixed, and $d_{J}\to\infty$ for finite values of $n$, e.g. $\lim_{n\to\infty}\lim_{d_{J}\to\infty}L_{\mathcal{D}}(\hat{w})$. This setting enables relatively easy calculation of many quantities of interest, and can recover many interesting behaviors of overparametrized interpolation, including consistency and the double descent phenomenon.

We will be primarily concerned with the behavior of the minimal-norm interpolator,

This predictor is in fact consistent in Setting B when $\lambda_{n}=o(n)$ and we consider $d_{J}\to\infty$ for each $n$. We here use a slightly broader notion of consistency than is traditional [28, e.g. in]: we mean that

for our sequence of learning problems in the given asymptotic regime. Specifically:

The proof follows from Lemmas 2.2 and 2.3, which establish first – because the setting was designed exactly to make this trueIf the noise scaling were $\omega(1/d_{J})$, then as $d_{J}\to\infty$, the minimal-norm solution would exploit the exploding magnitude of the noise components, and all of the signal would “bleed” into the noise dimensions , giving $\lVert\hat{w}_{\mathit{MN}}\rVert\to 0$ and $L_{\mathcal{D}}(\hat{w}_{\mathit{MN}})\to L_{\mathcal{D}}(0_{p})$ – in the ridge regression equivalence, we let the regularization weight go to infinity. On the other hand, if the noise scaling were $o(1/d_{J})$, then we would have $\lVert\hat{w}_{\mathit{MN}}\rVert\to\infty$, significantly complicating matters. $\Theta(1/d_{J})$ is the only scaling in which $\lVert\hat{w}_{\mathit{MN}}\rVert$ is bounded but nonzero. – that $\hat{w}_{\mathit{MN}}$ becomes equivalent to ridge regression on the signal part of $X$ with regularization weight $\lambda_{n}$, and then that ridge regression is consistent in this setting.

By the strong law of large numbers, we have that $X_{J}X_{J}^{\mathsf{T}}=\lambda_{n}\frac{Z_{J}Z_{J}^{\mathsf{T}}}{d_{J}}$ converges almost surely to $\lambda_{n}I_{n}$. Writing $\hat{w}_{\mathit{MN}}=(\hat{w}_{\mathit{MN},S},\hat{w}_{\mathit{MN},J})$, we can easily verify that

$\hat{w}_{\mathit{MN},S}=X_{S}^{\mathsf{T}}(X_{S}X_{S}^{\mathsf{T}}+X_{J}X_{J}^{\mathsf{T}})^{-1}Y\stackrel{{\scriptstyle a.s.}}{{\to}}\hat{w}_{\lambda_{n}}$ by the continuous mapping theorem.

$\hat{w}_{\mathit{MN},J}=X_{J}^{\mathsf{T}}(X_{S}X_{S}^{\mathsf{T}}+X_{J}X_{J}^{\mathsf{T}})^{-1}Y$. Drawing a new $x_{J}\sim\mathcal{N}(0,\frac{\lambda_{n}}{d_{J}}I_{d_{J}})$, $X_{J}x_{J}\stackrel{{\scriptstyle a.s.}}{{\to}}0_{n}$ and so $\langle\hat{w}_{\mathit{MN},J},x_{J}\rangle\stackrel{{\scriptstyle a.s.}}{{\to}}0$.

This implies that for any fixed $x$, $\langle\hat{w}_{\mathit{MN}},x\rangle\stackrel{{\scriptstyle a.s.}}{{\to}}\langle\hat{w}_{\lambda_{n}},x_{S}\rangle$, and hence via continuity we have that $(\langle\hat{w}_{\mathit{MN}},x\rangle-y)^{2}\stackrel{{\scriptstyle a.s.}}{{\to}}(\langle\hat{w}_{\lambda_{n}},x\rangle-y)^{2}$. Taking expectations over $(x,y)$ to get $L_{\mathcal{D}}$ and then over the training set, then exchanging the limit with each expectation,Both exchanges can be justified using dominated convergence thoerem and the techniques from the proof of Proposition 4.6, which independently shows a stronger statement. we obtain the desired result. ∎

The proof, as for all the following results, is in the appendix. Taking $\lambda_{n}=o(n)$ ensures the bias due to regularization is negligible; the minimax-optimal scaling would be $\lambda_{n}\propto\sqrt{n}$ .

The results of apply to our setting, also showing consistency of $\hat{w}_{\mathit{MN}}$. Although they do not require $p\to\infty$ for finite $n$ as we study, their results show that consistency of $\hat{w}_{\mathit{MN}}$ is only possible when the effective $p$ grows much faster than $n$. \Citetmuthukumar:interpolation showed that no interpolation method can be consistent in Setting A for $p=\mathcal{O}(n)$; we re-derive this (simple) result in Proposition 4.3, since it will also be important for our purposes.

hastie:surprises and various follow-ups, on the other hand, employ the standard asymptotic regime of random matrix theory, where $n/p\to\gamma\in(0,\infty)$, mostly focusing on $\Sigma=I$. Although no interpolator can achieve consistency here, they exactly evaluate $\lim_{(n,d)\to\infty}L_{\mathcal{D}}(\hat{w}_{\mathit{MN}})$. The setting of is related, with general $(n,p)$ but again with $\Sigma=I$, where $\hat{w}_{\mathit{MN}}$ is not consistent.

Uniform convergence

We now know, via Proposition 2.1, that $\hat{w}_{\mathit{MN}}$ is consistent in this setting. Could we have discovered this fact directly via uniform convergence? Typically, we would find some class $\mathcal{W}_{n,\delta}$ such that $\Pr(\hat{w}_{\mathit{MN}}\in\mathcal{W}_{n,\delta})\geq 1-\delta$, and bound the generalization gap

As $L_{\mathbf{S}}(\hat{w}_{\mathit{MN}})=0$, this would directly provide an upper bound on $L_{\mathcal{D}}(\hat{w}_{\mathit{MN}})$ with probability $1-2\delta$.

As $n\to\infty$ in Setting B, if $\lambda_{n}$ is both $o(n)$ and $\omega(1)$, then

We could then find $\epsilon_{\mathcal{W}}(n,\delta)$ by studying the Rademacher complexity, given by

Standard Rademacher bounds are for Lipschitz losses, which the squared loss is not. If we let $T_{n}$ be a uniform upper bound on all the labels and $Q_{n}$ on all the predictions, however, the absolute value of the derivative of the squared loss is at most $2\lvert\hat{y}-y\rvert\leq 2(Q_{n}+T_{n})$, and so we can treat it as $2(Q_{n}+T_{n})$-Lipschitz with high probability. We then obtain in the setting of Proposition 3.1 that

To show consistency, we need a bound exactly approaching $\sigma^{2}$ as $n\to\infty$, i.e. $Q_{n}+T_{n}\to\frac{1}{4}\sigma$. But in fact, each of $Q_{n}$ and $T_{n}$ diverge to $\infty$ as $n\to\infty$, because we have more and more chances to see a large value. Thus for $n\to\infty$, (4) says nothing at all.

Now, the path to (4) was potentially quite loose, particularly in the Lipschitz step; perhaps, then, we could simply put more effort in to obtain the bound we want. This is not the case: balls which are big enough to contain $\hat{w}_{\mathit{MN}}$ also contain predictors with unbounded generalization gaps as $n\to\infty$.

B.2 shows that the gap is at least $\lVert\Sigma-\hat{\Sigma}\rVert(\lVert\hat{w}_{\mathit{MN}}\rVert-\lVert w^{*}\rVert)^{2}+o(1)$ using (1) and then aligning $w-w^{*}$ with $\Sigma-\hat{\Sigma}$. By Proposition 3.1, $(\lVert\hat{w}_{\mathit{MN}}\rVert-\lVert w^{*}\rVert)^{2}$ grows like $n/\lambda_{n}$. Now $\lVert\Sigma-\hat{\Sigma}\rVert$ goes to , but only at the rate of $\sqrt{\lambda_{n}/n}$ , so the product grows as $\sqrt{n/\lambda_{n}}$. ∎

Norm balls around $w^{*}$, rather than the origin, fare no better; they would merely remove the asymptotically irrelevant $\lVert w^{*}\rVert$ term from the result of Proposition B.2.

2 Uniform convergence over algorithm- and distribution-dependent hypothesis classes

Choosing $\mathcal{W}_{n,\delta}$ as a Euclidean norm ball, then, cannot yield the result we want (or, indeed, any meaningful result at all for large $n$). But a norm ball doesn’t fully capture everything we know about $\hat{w}_{\mathit{MN}}$: for instance, we know that its norm is not likely to be very small. Perhaps taking a shell rather than a ball would help? Following , we show that in fact, no choice of $\mathcal{W}_{n,\delta}$ can demonstrate consistency using the most common two-sided uniform convergence bounds.

Specifically, let $\mathcal{S}_{n,\delta}$ be a set of typical training examples $\mathbf{S}=(X,Y)$ such that $\Pr(\mathbf{S}\in\mathcal{S}_{n,\delta})\geq 1-\delta$, let $\mathcal{A}(X,Y)$ be any learning algorithm, and then take the class of typical outputs of $\mathcal{A}$, $\mathcal{W}_{n,\delta}^{\mathcal{A}}=\{\mathcal{A}(X,Y):(X,Y)\in\mathcal{S}_{n,\delta}\}$. (Clearly, no bound based on $\mathcal{S}_{n,\delta}$ could choose a smaller $\mathcal{W}_{n,\delta}$.) The tightest algorithm-dependent uniform convergence bound is then

In interpolation learning, where $L_{\mathbf{S}}$ is zero, we need $\lim_{n\to\infty}\epsilon_{\mathcal{A}}^{\mathcal{D}}(n,\delta)=\sigma^{2}$ to obtain consistency. show that in a particular high-dimensional linear classification setting, stochastic gradient descent has asymptotic loss, but $\epsilon_{\mathcal{A}}^{\mathcal{D}}(n,\delta)$ must be nearly $1$ for any $\mathcal{S}_{n,\delta}$. We show a similar result in our setting, not only for $\mathcal{A}=\hat{w}_{\mathit{MN}}$ but indeed for many interpolation methods.Lemma 5.2 of is closely related; it covers Setting A in general, but applies only to $\hat{w}_{\mathit{MN}}$ and shows a smaller gap.

In Setting B, let $\mathcal{A}$ be an algorithm outputting interpolators, $X\mathcal{A}(X,Y)=Y$, with

For any $\delta\in(0,\frac{1}{2})$ and set of typical training examples $\mathcal{S}_{n,\delta}$ satisfying $\Pr(\mathbf{S}\in\mathcal{S}_{n,\delta})\geq 1-\delta$, let $\mathcal{W}_{n,\delta}^{\mathcal{A}}=\left\{\mathcal{A}(X,Y):(X,Y)\in\mathcal{S}_{n,\delta}\right\}$ denote the set of typical outputs. Then

From (2), we can see that $\hat{w}_{\mathit{MN}}$ satisfies the symmetry condition in (6). In fact, Proposition B.3 (in Section B.3) shows this is also true of many more algorithms, including interpolators which minimize $\lVert w\rVert_{1}$ (basis pursuit) or even $\lVert w-w^{*}\rVert$: any algorithm that picks the interpolator minimizing $f_{S}(w_{S})+f_{J}(w_{J})$, where each function is convex and $f_{J}(-w)=f_{J}(w)$.

The attentive reader may have noticed that Theorem 3.3, like Theorem 3.2, applies only to bounds on $\lvert L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)\rvert$, whereas the general argument as in (3) only needs to bound $L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)$. Indeed, the proof of Theorem 3.3 exhibits a hypothesis with low generalization error but high training error – not a particularly concerning failure mode. Whenever $\mathcal{A}$ is consistent, it is trivially guaranteed that there is a $\mathcal{W}_{n,\delta}$ where (3) holds with $\epsilon_{\mathcal{W}}(n,\delta)\to L_{\mathcal{D}}(w^{*})$, and so ’s approach is not meaningful for one-sided bounds.Take $\mathcal{S}_{n,\delta}=\{(X,Y):L_{\mathcal{D}}(X,Y)\leq L_{\mathcal{D}}(w^{*})+\epsilon_{n,\delta}\}$; consistency implies that there is a choice of $\epsilon_{n,\delta}\to 0$ such that $\Pr(\mathbf{S}\in\mathcal{S}_{n,\delta})\geq 1-\delta$ and $\epsilon_{n,\delta}\geq\sup_{\mathbf{S}\in\mathcal{S}_{n,\delta}}\sup_{w\in\mathcal{W}_{n,\delta}^{\mathcal{A}}}L_{\mathcal{D}}(w)\geq\sup_{\mathbf{S}\in\mathcal{S}_{n,\delta}}\sup_{w\in\mathcal{W}_{n,\delta}^{\mathcal{A}}}L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w).$ Thus it is not possible to mathematically rule out that one could prove a one-sided bound on $\sup_{w\in\mathcal{W}}L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)$ using a uniform convergence-type technique. (Again, since one-sided uniform convergence is always a consequence of consistency, this question is essentially one of viewpoint: do you first show uniform convergence and then bound consistency through uniform convergence, or do you establish uniform convergence as a consequence of consistency?) In any case, as argued by , existing uniform convergence proofs essentially bound $\lvert L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)\rvert$, not $L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)$.

Uniform convergence for interpolating predictors

In Setting B, we now know it is impossible to prove consistency of $\hat{w}_{\mathit{MN}}$ with a bound on $\sup_{w\in\mathcal{W}}\lvert L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)\rvert$ for any fixed choice of $\mathcal{W}$, and it seems quite unlikely that we can do so with bounds on $\sup_{w\in\mathcal{W}}L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)$ either. However, since we are concerned only with zero-training-error predictors, perhaps we should instead look at bounds on

Although $L_{\mathbf{S}}(w)$ is identically in (8), we write it to emphasize that this is still fundamentally a bound on the generalization gap as in (3). When $L_{\mathbf{S}}(w)=0$, of course, one-sided and two-sided convergence become the same. Moreover, when $B=\lVert\hat{w}_{\mathit{MN}}\rVert$, (8) becomes identically $L_{\mathcal{D}}(\hat{w}_{\mathit{MN}})$, which we know from Proposition 2.1 is small. Our questions are (a) whether we could have shown this via uniform convergence, and (b) precisely how small $B$ has to be compared to $\lVert\hat{w}_{\mathit{MN}}\rVert$ in order to maintain consistency.

The uniform convergence of (8) is a weaker notion than that of Section 3, as the hypothesis set is sample-dependent. But it is still a standard and common form of “uniform convegnce” at the basis of classical learning theory, and is well understood to be necessary for obtaining tight learning guarantees when we expect the training error to be zero. For example, this is the notion used by to first establish standard (realizable) PAC-learning guarantees, and is the starting point for standard textbooks, as in Section 2.3.1 of , or Theorem 2.1 of where that book first introduces the term “uniform convergence bound.”

A bound on (8) would be implied by bounds with “optimistic rates” , which interpolate between a “fast” rate for $L_{\mathcal{D}}(w)-L_{\mathbf{S}}(w)$ and a “slow” one depending on $L_{\mathbf{S}}(w)$. For instance, the result of implies that if $\xi_{n}$ is a high-probability upper bound on $\max_{1\leq i\leq n}\lVert x_{i}\rVert^{2}$, we have uniformly over all $w$ with $\lVert w\rVert\leq B$ that

But the hidden constants and logarithmic factors in (9) do not meet our needs: to show consistency (as we discuss shortly) we need an asymptotic coefficient of 1 on $B^{2}\xi_{n}/n$, while showed only an upper bound of $200\,000\log^{3}(n)$. It seems likely given their extremely indirect proof technique, though, that a much tighter version holds – especially in the special case of bounded-norm linear predictors for square loss. Given Proposition 3.1, it is reasonable to suspect that something like the following may hold fairly generally:

But ($\star$ ‣ 4) would also do more than this: it makes predictions about the generalization error of interpolators with larger-than-minimal norm, not yet known in the literature. In the setting of Proposition 3.1, ($\star$ ‣ 4) would imply that

These predictions are important in their own right: outside of linear models, we rarely expect to obtain the interpolator with exactly minimal norm.

The predictions made in (11) in fact hold, with equality.

In Setting B with $\lambda_{n}=o(n)$, fix a sequence $(\alpha_{n})\to\alpha$, with each $\alpha_{n}\geq 1$. Then

The proof of Theorem 4.1 is based on bounding (8) directly, although it will take us several steps to get there which we now outline. Along the way, we provide results, especially Proposition 4.3, which are applicable well beyond Setting B.

The first tool we will require in our analysis is the best-conceivable interpolator for a given $X$ and $\mathcal{D}$:

The minimal-risk interpolator [21, Section 3.3] is

In Setting A, the expected risk of the minimal-risk interpolator is

We use $\hat{w}_{\mathit{MR}}$ as a constructive tool in our proofs: Theorem 4.5 expands the generalization gap around a fixed predictor in terms of that predictor’s risk, and so the minimal-risk predictor is an obvious choice for understanding the gap. 4.3 also provides lower bounds on interpolation methods: if $p=\mathcal{O}(n)$, then $\hat{w}_{\mathit{MR}}$ is not consistent, and hence no interpolator is. For instance, LASSO is minimax-optimal and consistent for sparse linear regression when $n=\Theta(p)$ , but no interpolation method can be. [21, Section 3 ] discuss this type of result in detail, including for non-Gaussian data; see also .

Our next tool measures how much energy in $\Sigma$ is missed by the sample $X$.

The restricted eigenvalue under interpolation for covariance $\Sigma$ and design $X$ is

We now have the tools to show the following result, which holds even more generally than Setting A.

The following results hold deterministically, viewing $L_{\mathcal{D}}(w)$ simply as a quadratic function $L_{\mathcal{D}}(w^{*})+\lVert w-w^{*}\rVert_{\Sigma}$, with no distributional assumptions on $\mathbf{S}$.

Fix a sequence $(B_{n})$ such that $B_{n}\geq\lVert\hat{w}_{\mathit{MN}}\rVert$ for all $n$. Then

where $0\leq R_{n}\leq 2\sqrt{\left[L_{\mathcal{D}}(\hat{w}_{\mathit{MN}})-L_{\mathcal{D}}(w^{*})\right]\kappa_{X}(\Sigma)\left[B_{n}^{2}-\lVert\hat{w}_{\mathit{MN}}\rVert^{2}\right]}$.

The term $\kappa_{X}(\Sigma)[B^{2}-\lVert\hat{w}_{\mathit{MN}}\rVert^{2}]$ appearing in each bound multiplies $\kappa$, essentially “how much” of $\Sigma$ is orthogonal to the data sample, by the amount of excess norm available inside the norm ball. This result makes us expect that ($\star$ ‣ 4) should in fact hold fairly generally with $\xi_{n}=n\,\kappa_{X}(\Sigma)$.

This is a quadratic program with a single quadratic constraint, which enjoys strong duality even though it is a convex maximization [9, Appendix B]. We thus need analyze only the (much simpler) one-dimensional dual problem. For (ii), we take $\hat{w}=\hat{w}_{\mathit{MN}}$ in (13) and obtain the dual as

Given consistency, we can show that the second term’s contribution is negligible, as

and $(\lambda I_{p-n}-F^{\mathsf{T}}\Sigma F)^{-1}$ has controlled eigenvalues so that the Mahalanobis norm is similar to the Euclidean norm. Observing that $\kappa_{X}(\Sigma)=\lVert F^{\mathsf{T}}\Sigma F\rVert$, the conclusion follows by routine calculations.

Case (i) uses a similar strategy, taking $\hat{w}=\hat{w}_{\mathit{MR}}$. The full proof is given in Section C.2. ∎

Now, all that remains is to evaluate the relevant quantities in Setting B.

We apply Theorem 4.5. With probability one,

As the first term inside the inverse converges to $I_{d_{S}}$ and the second term vanishes, we can expect $\kappa_{X}(\Sigma)\approx{\lambda_{n}}/{n}$. We bound the other terms by observing that there exists a sequence $\beta_{n}\to 1$ with

Because $\hat{w}_{\mathit{MR}}$ is consistent via Proposition 4.3, this proves Proposition 4.6. As $\lVert\hat{w}_{\mathit{MN}}\rVert\leq\lVert\hat{w}_{\mathit{MR}}\rVert$, this further implies $\hat{w}_{\mathit{MN}}$ is consistent, so that the $R_{n}$ term of Theorem 4.5 (ii) vanishes. ∎

We can see that $\kappa_{X}(\Sigma)$ tends to 0 while $\lVert\hat{w}_{\mathit{MN}}\rVert$ explodes, and in Setting B their product turns out to converge to exactly the Bayes risk. Because the other terms of Theorem 4.5 (ii) cancel, this gives us precisely the tight result we need for Theorem 4.1, and further suggests that the speculative upper bound $\kappa_{X}(\Sigma)B^{2}$ probably holds in more general settings.

We have at last shown in Theorem 4.1 a uniform convergence bound not only showing consistency of $\hat{w}_{\mathit{MN}}$, but furthermore verifying the predictions of (11). Thus if we obtain an interpolator with norm $1.1\lVert\hat{w}_{\mathit{MN}}\rVert$, we will suffer at most $1.21\sigma^{2}$ asymptotic risk. If we obtain an interpolator with norm no more than a constant amount larger than the minimal norm, we achieve asymptotic consistency.

Discussion

In this work, we shed new light on uniform convergence and its relationship to interpolation learning. We show that uniform control of the generalization gap cannot explain interpolation learning, for almost any interpolator, even in a simple setting. But we argue that when discussing “uniform convergence” in the context of interpolation learning, we should slightly broaden our horizons to include interpolation-specific uniform convergence bounds such as ($\star$ ‣ 4), or more generally “optimistic” (training-error-dependent) bounds . We show that despite recent sentiments to the contrary, such bounds could in principal explain interpolation learning, by demonstrating this in the “junk features” setting. Doing so requires obtaining very tight bounds, include tight constants – perhaps a difficult task, but not impossible. (For example, for linear predictors with a Lipschitz loss in a non-realizable setting, we do know the exact worst-case bound, with a tight numeric constant .)

Our results are also of independent interest in ensuring success with interpolation learning: in settings other than linear regression, where a closed-form solution is available, it is generally unlikely in practice that we find the exact minimum-norm solution. (Even gradient descent for linear regression would find this only when initialized exactly in the span of the data; other forms of implicit bias are likewise suboptimal.) Our results give some reassurance that, at least in this simple setting, approximately minimizing the norm is sufficient. The natural next step in this vein would be to study predictors with small but nonzero loss. This could either be done directly in the style of our Theorem 4.1, or by providing an optimistic rate as in (9) with tight constants. Our specific techniques, as well as the general takeaway of considering interpolation-specific bounds, could also be potentially applicable to settings beyond linear regression, especially the idea of studying the generalization gap via the dual problem: although strong duality may not be available in more general settings, upper bounds are always possible with weak duality.

Broader Impact

Interpolation learning is currently thought to be one of the core mysteries standing between us and a theoretical understanding of modern deep learning. Although there has recently been some key progress, many challenges remain. Our paper, in advancing the study of interpolation learning, makes another step on the path towards understanding the deep learning models that are quickly becoming ubiquitous throughout society, whether we understand them or not. In our view, increased understanding of these models can lead to safer, more reliable, and more controlled deployment, especially in sensitive domains.

In particular, we discuss a key component of statistical learning theory, namely uniform convergence, whose relevance to deep learning in general – and interpolation learning specifically – has recently been questioned. We make an explicit connection between the work on interpolation learning and the recent notion of “algorithmic dependent uniform convergence” . Instead of outright dismissal, we show that a more nuanced view is appropriate. By doing so, we hope to help guide the re-pivoting that statistical learning theory is currently undergoing.

We emphasize that, despite providing some positive theoretical results, we are certainly not advocating for preferring interpolation methods over other approaches. In particular, the increased sensitivity of interpolation methods may have problematic ramifications for robustness or privacy.

Acknowledgments and Disclosure of Funding

Research supported in part by NSF IIS award 1764032 and NSF HDR TRIPODS award 1934843.

References

Appendix A Proofs for Section 2

Therefore, by independence of $X_{S}$ and $E$,

Write the SVD for $X_{S}=UDV^{\mathsf{T}}$. Since $X_{S}$ has rank at most $d_{S}$, we denote its singular values as $\sqrt{\rho_{1}},...,\sqrt{\rho_{d_{S}}}$, and

As $d_{S}$ stays fixed as $n\to\infty$, by the strong law of large numbers we have $\frac{X_{S}^{\mathsf{T}}X_{S}}{n}\to I_{d_{S}}$. Assuming that $\frac{\lambda_{n}}{n}\to\gamma$, then by the continuous mapping and dominated convergence theorems, the first term converges to

Using the first moment of inverse Wishart distribution, the second term can be controlled by

Note that the first term converges to 0 as long as $\gamma=0$, and the desired conclusion follows. ∎

Appendix B Proofs for Section 3

Moreover, there exists a sequence $(\beta_{n})$ such that $\beta_{n}\to 1$ and

By rotational invariance of the standard normal distribution for $Z$, we have

Sending $d_{J}\to\infty$ and recalling $p=d_{S}+d_{J}$, we obtain

With probability one, $X_{S}X_{S}^{\mathsf{T}}$ is a $n\times n$ matrix with rank $d_{S}$, so the eigenvalues of $(X_{S}X_{S}^{\mathsf{T}}+\lambda_{n}I_{n})^{-1}$ consist of the $d_{S}$ eigenvalues of $(X_{S}^{\mathsf{T}}X_{S}+\lambda_{n}I_{d_{S}})^{-1}$ and $(n-d_{S})$ copies of $\frac{1}{0+\lambda_{n}}$. This implies

Moreover, by the rotational invariance of $X_{S}\sim\mathcal{N}(0,I_{d_{S}})$,

Letting the term in brackets be $\beta_{n}$, we have the result. ∎

By Proposition B.1, there exists a sequence $(\beta_{n})$ such that $\beta_{n}\to 1$ and

By assumption, $1/\lambda_{n}\to 0$ and $\lambda_{n}/n\to 0$; thus the dominant term inside the brackets is $\lVert w^{*}\rVert^{2}=\mathcal{O}(1)$. The conclusion follows by

B.2 Divergence of the generalization gap of norm balls (Section 3.1)

Let $\rho(\Sigma-\hat{\Sigma})$ be the algebraically largest eigenvalue of $\Sigma-\hat{\Sigma}$. It holds that

and similarly for two sided uniform convergence, it holds that

Therefore, we can decompose the generalization gap as

The last inequality holds by picking $w$ to be $\pm(\lVert\hat{w}_{\mathit{MN}}\rVert-\lVert w^{*}\rVert)$ times the top eigenvector of $\Sigma-\hat{\Sigma}$ for whichever sign makes the linear term nonnegative. By the same reasoning, we have

We will show that in Setting B as long as $\lambda_{n}=o(n)$,

By Fatou’s lemma and the calculation in Proposition B.1,

Next we want to interchange limit and expectation. Note that

The first two terms do not depend on $d_{J}$. It is easy to verify that

as $\frac{Z_{J}Z_{J}^{\mathsf{T}}}{d_{J}}\stackrel{{\scriptstyle a.s.}}{{\to}}I_{n}$. Therefore, by the dominated convergence theorem

sample-covariance show that, for Gaussian data,

where $C$ is a universal constant. Thus, in our case

It is easy to see that the remaining terms in the lower bound of Proposition B.2 are negligible. ∎

B.3 Uniform convergence on tighter sets (Section 3.2)

using $E\sim\mathcal{N}(0,\sigma^{2}I_{n})$. As $n\to\infty$, because $X_{S}$ is almost surely rank $d_{S}$, $\operatorname{Tr}(I_{n}-\Pi)$ is almost surely $n-d_{S}$. Thus we have

The conclusion follows by the observation that

Then negating junk dimensions simply negates the corresponding dimensions of the predictor:

(If the minimizer is not unique, the equation holds as an operation on sets.)

The KKT conditions for $\mathcal{A}(X,y)$, which are both necessary and sufficient in this case, are

Appendix C Proofs for Section 4

Note that $\left(ZZ^{\mathsf{T}}\right)^{-1}$ follows an inverse-Wishart distribution whose expectation is $\frac{I_{n}}{p-n-1}$. Therefore, we obtain

C.2 Uniform consistency of low norm interpolators (Section 4.1)

Although the second term involves a concave minimization problem, it is a quadratic optimization problem with a single quadratic inequality constraint. This is a classical example where strong duality holds even though the objective is not convex [9, Appendix B]. In order to derive the dual, we write down the Lagrangian:

strong duality tells us that the infimum is equal to $\sup_{\lambda\geq 0}\inf_{u}L(u,\lambda)$. For $\lambda<\lVert F^{\mathsf{T}}\Sigma F\rVert$, $\lambda I_{p-n}-F^{\mathsf{T}}\Sigma F$ has strictly negative eigenvalues, and so then $\inf_{u}L(u,\lambda)=-\infty$. If instead $\lambda>\lVert F^{\mathsf{T}}\Sigma F\rVert$, $\lambda I_{p-n}-F^{\mathsf{T}}\Sigma F$ is strictly positive definite, and setting the $u$ derivative to zero yields that $\inf_{u}L(\lambda,u)$ is

If instead $\lambda=\lVert F^{\mathsf{T}}\Sigma F\rVert$, we again have $\inf_{u}L(u,\lambda)=-\infty$ unless $F^{\mathsf{T}}(\lambda\hat{w}-F^{\mathsf{T}}\Sigma(\hat{w}-w^{*}))=0$ so that the linear term is identically zero; in this case, the quadratic term is minimized by $u=0$, and $\inf_{u}L(u,\lambda)=\lambda(B^{2}-\lVert\hat{w}\rVert^{2})$ agrees with (15), so this case is covered by the strict case as well. Thus the dual problem is to maximize (15) over $\lambda>\lVert F^{\mathsf{T}}\Sigma F\rVert$. The desired result follows by passing the minus sign into the sup of the dual problem. ∎

Thus picking $\hat{w}=\hat{w}_{\mathit{MR}}$ and $B=\lVert\hat{w}_{\mathit{MR}}\rVert$ in Lemma C.1 gives that

we know that $\sup_{\lVert w\rVert\leq\lVert\hat{w}_{\mathit{MR}}\rVert,\,L_{\mathbf{S}}(w)=0}L_{\mathcal{D}}(w)$ is lower bounded by

In order to compute $\lVert F^{\mathsf{T}}\hat{w}_{\mathit{MR}}\rVert^{2}$, we notice that $FF^{\mathsf{T}}$ is the orthogonal projection onto the kernel of $X$. Using the fact that $\text{im}(X^{\mathsf{T}})=\text{ker}(X)^{\bot}$, we get $I-FF^{\mathsf{T}}$ is the orthogonal projection onto the image of $X^{\mathsf{T}}$. Thus,

and left-multiplying both sides by $X^{\mathsf{T}}(XX^{\mathsf{T}})^{-1}$ gives that

which establishes the lower bound with a constant of $1$.

Similarly, we can use $(\lambda I_{p-n}-F^{\mathsf{T}}\Sigma F)^{-1}\preceq\frac{1}{\lambda-\lVert F^{\mathsf{T}}\Sigma F\rVert}I_{p-n}$ to upper bound (16) as

This gives the desired upper bound with a constant of $4$. It follows immediately that (16) converges to $L_{\mathcal{D}}(w^{*})$ if and only if

so that Lemma C.1 with $\hat{w}=\hat{w}_{\mathit{MN}}$ gives

Therefore, $\sup_{\lVert w\rVert\leq B_{n},\,L_{\mathbf{S}}(w)=0}L_{\mathcal{D}}(w)$ is lower bounded by, recalling that $\lVert F^{\mathsf{T}}\Sigma F\rVert=\kappa_{X}(\Sigma)$,

and we have shown that $R_{n}\geq 0$ in the result. On the other hand, $\sup_{\lVert w\rVert\leq B_{n},\,L_{\mathbf{S}}(w)=0}L_{\mathcal{D}}(w)$ is upper bounded by

using the fact that $\lVert AA^{T}\rVert=\lVert A^{T}A\rVert$ with $A=F^{T}\Sigma^{1/2}$. Plugging into the third term of (18) yields our desired upper bound on $R_{n}$,

C.2.2 Special case of Setting B

In Setting B, we are able to compute $\kappa_{X}(\Sigma)$.

With probability 1, it holds in Setting B that

Intuitively, since only the upper-left block does not vanish as $d_{J}\to\infty$, we should expect

However, as the dimensions of $\Sigma^{1/2}FF^{\mathsf{T}}\Sigma^{1/2}$ also increase with $d_{J}$, the analysis of $\kappa_{X}(\Sigma)$ requires more care.

It is clear that $\kappa_{X}(\Sigma)\geq\lVert I_{d_{S}}-X_{S}^{\mathsf{T}}(X_{S}X_{S}^{\mathsf{T}}+X_{J}X_{J}^{\mathsf{T}})^{-1}X_{S}\rVert$, and so

and the second term is upper bounded by $\lambda_{n}/d_{J}$, because

Taking a supremum over $v$ in (19), we get

Sending $\epsilon\to 0$ matches the $\liminf$ and $\limsup$. Finally, because

Notice that $\kappa_{X}(\Sigma)\cdot\lVert\hat{w}_{\mathit{MN}}\rVert^{2}$ can be dominated by $\lVert\Sigma\rVert\cdot\lVert\hat{w}_{\mathit{MR}}\rVert^{2}$ and Proposition B.1 showed that $\lVert\hat{w}_{\mathit{MR}}\rVert^{2}$ is integrable, so by the dominated convergence theorem,

Similarly, $\,\lim_{d_{J}\to\infty}\kappa_{X}(\Sigma)\cdot\lVert\hat{w}_{\mathit{MN}}\rVert^{2}\,$ can be dominated by

As $\left\lVert\left[\frac{X_{S}^{\mathsf{T}}X_{S}}{n}+\frac{\lambda_{n}}{n}I_{d_{S}}\right]^{-1}\right\rVert\stackrel{{\scriptstyle a.s.}}{{\to}}1$ and $\frac{\lVert E\rVert^{2}}{n}\stackrel{{\scriptstyle a.s.}}{{\to}}\sigma^{2}$, we have

Moreover, by independence of $X_{S}$ and $E$

Again, $\left\lVert\left[\frac{X_{S}^{\mathsf{T}}X_{S}}{n}+\frac{\lambda_{n}}{n}I_{d_{S}}\right]^{-1}\right\rVert$ can be dominated by $\operatorname{Tr}\left(\left(\frac{X_{S}^{\mathsf{T}}X_{S}}{n}\right)^{-1}\right)$, so that

and $\lVert\hat{w}_{\mathit{MN}}\rVert^{2}\leq\lVert\hat{w}_{\mathit{MR}}\rVert^{2}$, two final applications of DCT give

by Proposition B.1. Consequently, we have established

We are finally ready to prove Theorems 4.1 and 4.6.

Recall in the proof of Theorem 4.5, it is shown that

Combined with Proposition C.3, we have shown

On the other hand, we have the trivial lower bound

In the proof of Theorem 4.5, it is shown for every $\epsilon\geq 0$ that

Sending $\epsilon\to 0$ yields the upper bound $\alpha^{2}L_{\mathcal{D}}(w^{*})$.

To get the lower bound, in the proof of Theorem 4.5 it is also shown

By Proposition C.3, letting $B_{n}=\alpha_{n}\lVert\hat{w}_{\mathit{MN}}\rVert$ we obtain