Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting
Year: 2021

Abstract:
We consider interpolation learning in high-dimensional linear regression with Gaussian data, and prove a generic uniform convergence guarantee on the generalization error of interpolators in an arbitrary hypothesis class in terms of the class’s Gaussian width. Applying the generic bound to Euclidean norm balls recovers the consistency result of Bartlett et al. (2020) for minimum-norm interpolators, and confirms a prediction of Zhou et al. (2020) for near-minimal-norm interpolators in the special case of Gaussian data. We demonstrate the generality of the bound by applying it to the simplex, obtaining a novel consistency result for minimum `1-norm interpolators (basis pursuit). Our results show how norm-based generalization bounds can explain and be used to analyze benign overfitting, at least in some settings.

heading: 1 Introduction
text: The traditional understanding of machine learning suggests that models with zero training error tend to overfit, and explicit regularization is often necessary to achieve good generalization. Given the empirical success of deep learning models with zero training error (Neyshabur et al. 2015; Zhang et al. 2017) and the (re-)discovery of the “double descent” phenomenon (Belkin et al. 2019), however, it has become clear that the textbook U-shaped learning curve is only part of a larger picture: it is possible for an overparameterized model with zero training loss to achieve low population error in a noisy setting. In an effort to understand how interpolation learning occurs, there has been much recent study of the testbed problem of linear regression with Gaussian features (e.g. Hastie et al. 2019; Bartlett et al. 2020; Belkin et al. 2020; Ju et al. 2020; Muthukumar et al. 2020; Negrea et al. 2020; Tsigler and Bartlett 2020; Zhou et al. 2020). Significant progress has been made in this setting, including nearly-matching necessary and sufficient conditions for consistency of the minimal `2 norm interpolator (Bartlett et al. 2020).
Despite the fundamental role of uniform convergence in statistical learning theory, most of this line of work has used other techniques to analyze the particular minimal-norm interpolator.1 Instead of directly analyzing the population error of a learning algorithm, a uniform convergence-type argument would control the worst-case generalization gap over a class of predictors containing the typical outputs of a learning rule. Typically, this is done because for many algorithms – unlike the minimal Euclidean norm interpolator – it is difficult to exactly characterize the learned predictor, but we may be able to say e.g. that its norm is not too large. Since uniform convergence does not tightly depend on a specific algorithm, the resulting analysis can highlight the key properties that lead to good generalization: it can give bounds not only for, say, the minimal-norm interpolator, but also
⇤These authors contributed equally. 1Negrea et al. (2020) argue that Bartlett et al. (2020)’s proof technique is fundamentally based on uniform convergence of a surrogate predictor; Yang et al. (2021) study a closely related setting with a uniform convergence-type argument, but do not establish consistency. We discuss both papers in more detail in Section 4.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for other interpolators with low norm (e.g. Zhou et al. 2020), increasing our confidence that low norm – and not some other property the particular minimal-norm interpolator happens to have – is key to generalization. In linear regression, practical training algorithms may not always find the exact minimal Euclidean norm solution, so it is also reassuring that all interpolators with sufficiently low Euclidean norm generalize.
Nagarajan and Kolter (2019), however, raised significant questions about the applicability of typical uniform convergence arguments to certain high-dimensional regimes, similar to those seen in interpolation learning. Following their work, Bartlett and Long (2020), Negrea et al. (2020), Zhou et al. (2020), and Yang et al. (2021) all demonstrated the failure of forms of uniform convergence in various interpolation learning setups. To sidestep these negative results, Zhou et al. (2020) suggested considering bounds which are uniform only over predictors with zero training error. This weaker notion of uniform convergence has been standard in analyses of “realizable” (noiseless) learning at least since the work of Vapnik (1982, Chapter 6.4) and Valiant (1984). Zhou et al. demonstrated that at least in one particular noisy setting, such uniform convergence is sufficient for showing consistency of the minimal `2 norm interpolator, even though “non-realizable” uniform convergence arguments (those over predictors regardless of their training error) cannot succeed. It remains unknown, however, whether these types of arguments can apply to more general linear regression problems and more typical asymptotic regimes, particularly showing rates of convergence rather than just consistency.
In this work, we show for the first time that uniform convergence is indeed able to explain benign overfitting in general high-dimensional Gaussian linear regression problems. Similarly to how the standard analysis for learning with Lipschitz losses bounds generalization gaps through Rademacher complexity (e.g. Shalev-Shwartz and Ben-David 2014), our Theorem 1 (Section 3) establishes a finitesample high probability bound on the uniform convergence of the error of interpolating predictors in a hypothesis class, in terms of its Gaussian width. This is done through an application of the Gaussian Minimax Theorem; see the proof sketch in Section 7. Combined with an analysis of the norm of the minimal `2 norm interpolator (Theorem 2 in Section 4), our bound recovers known consistency results (Bartlett et al. 2020), as well as proving a conjectured upper bound for larger-norm interpolators (Zhou et al. 2020).
In addition, since we do not restrict ourselves to Euclidean norm balls but instead consider interpolators in an arbitrary compact set, our results allows for a wide range of other applications. Our analysis leads to a natural extension of the consistency result and notions of effective rank of Bartlett et al. (2020) for arbitrary norms (Theorem 5 in Section 5). As a demonstration of our general theory, in Section 6 we show novel consistency results for the minimal `1 norm interpolator (basis pursuit) in particular settings, which we believe are the first results of their kind.

heading: 2 Problem Formulation
text: Notation. We use k·kp for the `p norm, kxkp = ( P i |xi|p)1/p. We always use maxx2S f(x) to be 1 when S is empty, and similarly minx2S f(x) to be 1. We use standard O(·) notation, and a . b for inequality up to an absolute constant. For a positive semidefinite matrix A, the Mahalanobis (semi-)norm is kxk2
A := hx,Axi. For a matrix A and set S, AS denotes the set {Ax : x 2 S}.
Data model. We assume that data (X,Y ) is generated as
Y = Xw⇤ + ⇠, Xi iid⇠ N(0,⌃), ⇠ ⇠ N(0, 2In), (1)
where X 2 Rn⇥d has i.i.d. Gaussian rows X1, . . . , Xn, d n, w⇤ is arbitrary, and ⇠ is Gaussian and independent of X . Though our proof techniques crucially depend on Xi being Gaussian, we can easily relax the assumption on the noise ⇠ to only being sub-Gaussian; we assume Gaussian noise here for simplicity. The empirical and population loss are defined as, respectively,
L̂(w) = 1
n kY Xwk22, L(w) = E (x,y) (y hw, xi)2 = 2 + kw w⇤k2⌃,
where in the expectation y = hx,w⇤i+ ⇠0 with x ⇠ N(0,⌃) independent of ⇠0 ⇠ N(0, 2). For an arbitrary norm k·k, the minimal norm interpolator is ŵ = argmin
L̂(w)=0 kwk. For Euclidean norm specifically, the minimal norm interpolator can be written explicitly as ŵ = X(XXT ) 1Y . If there is more than one minimal norm interpolator, all of our guarantees will hold for any minimizer ŵ.
Speculative bound. Zhou et al. (2020) studied uniform convergence of low norm interpolators,
sup kwkB, L̂(w)=0 L(w) L̂(w). (2)
Clearly, when B kŵk, this quantity upper-bounds the population risk of ŵ. Zhou et al. evaluated the asymptotic limit of (2) in one particular setting. But they further speculated that a bound of the following form may hold more generally:
sup kwk2B, L̂(w)=0
L(w) L̂(w)  B 2 n n + o(1), (?)
where2 n ⇡ kxk2 . As discussed by Zhou et al., a bound almost of this form is implied by results of Srebro et al. (2010) for general data distributions, except that approach gives a large leading constant and logarithmic factors. To show consistency of benign overfitting, though, we need (?) to hold without even a constant multiplicative factor. Zhou et al. ask whether and when this holds, speculating that it might in broad generality.
The goal of this paper is essentially to prove (?), at least for Gaussian data, and to use it to show consistency of the minimal norm interpolator. Our main result (Theorem 1) can be thought of showing (?) for Gaussian data with n = E kxk2, as well as strengthening and significantly generalizing it. Our result is more general, as it applies to general compact hypothesis sets beyond just the Euclidean ball as in (?). But it also falls short of fully proving the speculative (?) since our results are limited to Gaussian data, while there is no reason we are aware of to believe a tight uniform convergence guarantee of the form (?) does not hold much more broadly. We leave extending our results beyond the Gaussian case open.

heading: 3 Generic Uniform Convergence Guarantee
text: To state our results, we first need to introduce some key tools. Definition 1. The Gaussian width and the radius of a set S ⇢ Rd are
W (S) := E H⇠N(0,Id) sup s2S |hs,Hi| and rad(S) := sup s2S ksk2.
The radius measures the size of a set in the Euclidean norm. The Gaussian width of a set S can be interpreted as the number of dimensions that a random projection needs to approximately preserve the norms of points in S (Gordon 1988; Bandeira 2016). These two complexity measures are connected by Gaussian concentration: Gaussian width is the expected value of the supremum of some Gaussian process, and the radius upper bounds the typical deviation of that supremum from its expected value. Definition 2 (Covariance splitting). Given a positive semidefinite matrix ⌃ 2 Rd⇥d, we write ⌃ = ⌃1 ⌃2 if ⌃ = ⌃1 + ⌃2, each matrix is positive semidefinite, and their spans are orthogonal.
Note that ⌃ = ⌃1 ⌃2 effectively splits the eigenvectors of ⌃ into two disjoint parts. We can now state our generic bound. Section 7 sketches the proof; all full proofs are in the appendix. Theorem 1 (Main generalization bound). There exists an absolute constant C1  66 such that the following is true. Under the model assumptions in (1), let K be an arbitrary compact set, and take any covariance splitting ⌃ = ⌃1 ⌃2. Fixing  1/4, let = C1 ✓q log(1/ ) n + q rank(⌃1) n ◆ . If
n is large enough that  1, then the following holds with probability at least 1 :
sup w2K,L̂(w)=0
L(w)  1 + n
" W (⌃1/22 K) + ⇣ rad(⌃1/22 K) + kw⇤k⌃2 ⌘ s 2 log ✓ 32 ◆#2 .
In our applications, we consider K = {w 2 Rd : kwk  B} for an arbitrary norm, with B based on a high-probability upper bound for kŵk. Depending on the application, the rank of ⌃1 will be
2When kxk2 concentrates, we need n to match its typical value. That is, n might be a high probability bound on kxk2, or for (sub)Gaussian data, as in our case, n = E kxk2.
either constant or o(n), so that ! 0. The term kw⇤k⌃2 generally does not scale with n and hence is often negligible. As hinted earlier, we can think of the Gaussian width term and the radius term as bias and variance, respectively. To achieve consistency, we can expect that the Gaussian width should scale as p n. This agrees with the intuition that we need increasing norm to memorize noise when the model is not realizable. The radius term requires some care in our applications, but can be handled by the covariance splitting technique. As part of the analysis in the following sections, we will rigorously show in many settings that the dominant term in the upper bound is the Gaussian width. In these cases, our upper bound is roughly W (⌃1/22 K)2/n, which can be viewed as the ratio between the (probabilistic) dimension of our hypothesis class and sample size. We will also analyze how large K must be to contain any interpolators, allowing us to find consistency results.

heading: 4 Application: Euclidean Norm Ball
text: It can be easily seen that the Gaussian width of a Euclidean norm ball reduces nicely to the product of the norm of our predictor with the typical norm of x: if K = {w 2 Rd : kwk2  B}, then
W (⌃1/2K) = B · E H⇠N(0,Id)
k⌃1/2Hk2  q B2 E kxk22. (3)
Therefore, it is plausible that (?) holds with n = E kxk22 = Tr(⌃). Figure 1 illustrates this generalization bound in two simple examples, motivated by Hastie et al. (2019) and Zhou et al. (2020). Indeed, an application of our main theorem proves that this is exactly the case for Gaussian data. Corollary 1 (Proof of the speculative bound (?) for Gaussian data). Fix any  1/4. Under the model assumptions in (1) with B kw⇤k2 and n & log(1/ ), for some . 4 p log(1/ )/n, it holds with probability at least 1 that
sup kwk2B,L̂(w)=0
L(w)  (1 + )B 2 Tr(⌃)
n . (4)
The above bound is clean and simple, but only proves a sub-optimal rate of n 1/4. This is because the choice of covariance split used in the proof of Corollary 1 uses no information about the particular structure of ⌃. This bound can also be slightly loose in situations where the eigenvalues of ⌃ decay
rapidly, in which case Tr(⌃) can be replaced by a smaller quantity. We next state a more precise bound on the generalization error, which requires introducing the following notions of effective rank. Definition 3 (Bartlett et al. 2020). The effective ranks of a covariance matrix ⌃ are
r(⌃) = Tr(⌃)
k⌃kop and R(⌃) =
Tr(⌃)2 Tr(⌃2) .
The r(⌃) rank can roughly be understood as the squared ratio between the Gaussian width and radius in our previous bound. It is related to the concentration of the `2 norm of a Gaussian vector with covariance ⌃. In fact, both definitions of effective ranks can be derived by applying Bernstein’s inequality to kxk2/E kxk2. We will only need r(⌃) in the generalization bound below, but we will show in Theorem 2 that R(⌃) can be used to control the norm of the minimal norm interpolator ŵ. Corollary 2. There exists an absolute constant C1  66 such that the following is true. Under (1),
pick any split ⌃ = ⌃1 ⌃2, fix  1/4, and let = C1 ✓q
log(1/ ) r(⌃2)
+ q
log(1/ ) n
+ q
rank(⌃1) n
◆ .

heading: If B kw⇤k2 and n is large enough that  1, the following holds with probability at least 1 :
text: sup kwk2B,L̂(w)=0
L(w)  (1 + )B 2 Tr(⌃2)
n . (5)
In order to use Corollary 1 or 2 to prove consistency, we need a high-probability bound for kŵk2, the norm of the minimal norm interpolator, so that B will be large enough to contain any interpolators. Theorem 2 gives exactly such a bound, showing that if the effective ranks R(⌃2) and r(⌃2) are large, then we can construct an interpolator with Euclidean norm nearly kw⇤k2 + p n/Tr(⌃2).
Theorem 2 (Euclidean norm bound; special case of Theorem 4). Fix any  1/4. Under the model assumptions in (1) with any choice of covariance splitting ⌃ = ⌃1 ⌃2, there exists some ✏ . q log(1/ ) r(⌃2) + q log(1/ ) n + n log(1/ ) R(⌃2)
such that the following is true. If n and the effective ranks are such that ✏  1 and R(⌃2) & log(1/ )2, then with probability at least 1 , it holds that
kŵk2  kw⇤k2 + (1 + ✏)1/2 r n
Tr(⌃2) . (6)
Plugging in estimates of kŵk to our scale-sensitive bound Corollary 2, we obtain a population loss guarantee for ŵ in terms of effective ranks. Theorem 3 (Benign overfitting). Fix any  1/2. Under the model assumptions in (1) with any covariance splitting ⌃ = ⌃1 ⌃2, let and ✏ be as defined in Corollary 2 and Theorem 2. Suppose that n and the effective ranks are such that R(⌃2) & log(1/ )2 and , ✏  1. Then, with probability at least 1 ,
L(ŵ)  (1 + )(1 + ✏) + kw⇤k2
r Tr(⌃2)
n
!2 . (7)
From (7), we can see that to ensure consistency, i.e. L(ŵ) ! 2, it is enough that ! 0, ✏ ! 0, and kw⇤k2 q Tr(⌃2) n ! 0. Recalling the definitions of the various quantities and using that r(⌃2)2 R(⌃2) (Bartlett et al. 2020, Lemma 5), we arrive at the following conditions.
Sufficient conditions for consistency of ŵ. As n ! 1, L(ŵ) converges in probability to 2 if there exists a sequence of covariance splits ⌃ = ⌃1 ⌃2 such that
rank(⌃1)
n ! 0, kw⇤k2
r Tr(⌃2)
n ! 0, n R(⌃2) ! 0. (8)
Relationship to Bartlett et al. (2020). Our set of sufficient conditions above subsumes and is slightly more general than the conditions of Bartlett et al. (2020). There are two differences:
1. They choose the covariance split specifically to minimize rank(⌃1) such that r(⌃2) & n.
2. Their version of the second condition replaces Tr(⌃2) by the larger term Tr(⌃).
From the perspective of showing L(ŵ) ! 2, the first difference is immaterial: if there exists a choice of split that satisfies our conditions, it can be shown that there exists a (possibly different) split which will also satisfy r(⌃2) & n (see Appendix D.2.1). The second point is a genuine improvement over the consistency result of Bartlett et al. (2020) when ⌃ has a few very large eigenvalues; this improvement has also been implicitly obtained by Tsigler and Bartlett (2020).
Regarding the rate of convergence, our additional r(⌃2) 1/2 term and the dependence onp rank(⌃1)/n instead of rank(⌃1)/n is slightly worse than that of Bartlett et al. (2020), but our bound can be applied for a smaller value of rank(⌃1) and is better in the kw⇤k2 p
Tr(⌃2)/n term. We believe these differences are minimal in most cases, and not so important for our primary goal to showcase the power of uniform convergence.
Relationship to Negrea et al. (2020). The consistency result of Bartlett et al. (2020) can also be recovered with a uniform convergence-based argument (Negrea et al. 2020). Instead of considering uniform convergence over a norm ball, Negrea et al. applied uniform convergence to a surrogate predictor, and separately showed that the minimal-norm interpolator has risk close to the surrogate (and, indeed, argue that this was fundamentally the proof strategy of Bartlett et al. (2020) all along). Their analysis reveals an interesting connection between realizability and interpolation learning, but it does not highlight that low norm is key to good generalization, nor does it predict the worst-case error for other low-norm interpolators.
Relationship to Bartlett and Long (2020). Bartlett and Long recently showed that it is impossible to find a tight excess risk bound that only depends on the learned predictor and sample size. This does not, however, contradict our results. A closer look at the construction of their lower bound reveals that the excess risk bounds being ruled out cannot depend on either the training error L̂ or the population noise level 2. The former is crucial: their considered class of bounds cannot incorporate the knowledge that the training error is small, which is the defining property of uniform convergence of interpolators. The latter point is also important; they consider excess risk (L 2), but (?) and our bounds are about the generalization gap (L L̂).
Relationship to Yang et al. (2021). Yang et al. give expressions for the asymptotic generalization error of predictors in a norm ball, in a random feature model. Their model is not directly comparable to ours (their labels are effectively a nonlinear function of their non-Gaussian random features), but they similarly showed that uniform convergence of interpolators can lead to a non-vacuous bound. It is unclear, though, whether uniform convergence of low-norm interpolators can yield consistency in their model: they only study sets of the form {kwk  ↵ kŵk} with ↵ > 1 a constant, where we would expect a loss of ↵2 2 – i.e. would not expect consistency. They also rely on numerical methods to compare their (quite complicated) analytic expressions. It remains possible that the gap between uniform convergence of interpolators and the Bayes risk vanishes in their setting as ↵ approaches 1.

heading: 5 General Norm Ball
text: All the results on the Euclidean setting are special cases of the following results for arbitrary norms. It is worth keeping in mind that the Euclidean norm will still play a role in these analyses, via the Gaussian width and radius appearing in Theorem 1 and the `2 projection P appearing in Theorem 4. Definition 4. The dual norm of a norm k·k on Rd is kuk⇤ := maxkvk=1hv, ui, and the set of all its sub-gradients with respect to u is @kuk⇤ = {v : kvk = 1, hv, ui = kuk⇤}.
The Euclidean norm’s dual is itself; for it and many other norms, @ kuk⇤ is a singleton set. Using these notions, we will now give versions of the effective ranks appropriate for generic norm balls. Definition 5. The effective k·k-ranks of a covariance matrix ⌃ are given as follows. Let H ⇠ N(0, Id), and define v⇤ = argminv2@k⌃1/2Hk⇤ kvk⌃. Then
rk·k(⌃) =
E ⌃1/2H
⇤
supkwk1 kwk⌃
!2 and Rk·k(⌃) = E ⌃1/2H ⇤
E kv⇤k⌃
!2 .
The first effective k·k-rank is the squared ratio of Gaussian width to the radius of the set ⌃1/2K, where K is a norm ball {w : kwk  B}; the importance of this ratio should be clear from Theorem 1. The Gaussian width is given by W (⌃ 12K) = B E kxk⇤, while the radius can be written supkwkB kwk⌃ so that the factors of B cancel.
The choice of Rk·k arises naturally from our bound on kŵk in Theorem 4 below. Large effective rank of ⌃2 means the sub-gradient v⇤ of k⌃1/22 Hk⇤ is small in the k·k⌃2 norm. This is, in fact, closely related to the existence of low-norm interpolators. First, note that ⌃1/22 H corresponds to the small-eigenvalue components of the covariate vector. For v⇤ to be a sub-gradient means that moving the weight vector w in the direction of v⇤ is very effective at changing the prediction hw,Xi; having small k·k⌃2 norm means that moving in this direction has a very small effect on the population loss L(w). Together, this means the sub-gradient will be a good direction for benignly overfitting the noise. Remark 1 (Definitions of effective ranks). Using k·k2 in Definition 5 yields slightly different effective ranks than those of Definition 3, but the difference is small and asymptotically negligible. Both r and R use E kxk2 in their numerators, while rk·k2 and Rk·k2 use (E kxk)
2. The denominators of r and rk·k2 agree; Lemma 9, in Appendix C.2, shows that r(⌃) 1  rk·k2(⌃)  r(⌃). The denominator of Rk·k2 uses the sole sub-gradient v
⇤ = ⌃1/2H/k⌃1/2Hk2; the denominator is then k⌃1/2Hk2⌃/k⌃1/2Hk22 ⇡ Tr(⌃2)/Tr(⌃), giving that Rk·k2(⌃) ⇡ Tr(⌃)
2/Tr(⌃2) = R(⌃). Equation (75), in Appendix C.2, shows that Rk·k2(⌃) cR(⌃) for some c that converges to 1 as r(⌃) ! 1, as is required by the consistency conditions. The other direction, R(⌃) c0Rk·k2(⌃), also holds with c0 ! 1 as r(⌃2) ! 1. It would be possible (and probably even more natural with our analysis) to state the consistency conditions in Section 4 in terms of rk·k2 and Rk·k2 ; we used r and R mainly to allow direct comparison to Bartlett et al. (2020).
Using the general notion of effective ranks, we can find an analogue of Corollary 2 for general norms. Corollary 3. There exists an absolute constant C1  66 such that the following is true. Under the model assumptions in (1), take any covariance splitting ⌃ = ⌃1 ⌃2 and let k·k be an arbitrary
norm. Fixing  1/4, let = C1 ✓q
log(1/ ) rk·k(⌃2)
+ q
log(1/ ) n
+ q
rank(⌃1) n
◆ . If B kw⇤k and n is
large enough that  1, then the following holds with probability at least 1 :
sup kwkB,L̂(w)=0
L(w)  (1 + )
⇣ B · Ek⌃1/22 Hk⇤ ⌘2
n . (9)
As in the Euclidean special case, we still need a bound on the norm of ŵ = argmin L̂(w)=0 kwk to use this result to study the consistency of ŵ. This leads us to the second main technical result of this paper, which essentially says that if the effective ranks Rk·k(⌃2) and rk·k(⌃2) are sufficiently large, then there exists an interpolator with norm kw⇤k+ p n/Ek⌃1/22 gk⇤. Theorem 4 (General norm bound). There exists an absolute constant C2  64 such that the following is true. Under the model assumptions in (1) with any covariance split ⌃ = ⌃1 ⌃2, let k·k be an arbitrary norm, and fix  1/4. Denote the `2 orthogonal projection matrix onto the space spanned by ⌃2 as P . Let H ⇠ N(0, Id), and let v⇤ = argmin
v2@k⌃1/22 Hk⇤ kvk⌃2 . Suppose that there exist
✏1, ✏2 0 such that with probability at least 1 /4
kv⇤k⌃2  (1 + ✏1)E kv ⇤k⌃2 and kPv ⇤k2  1 + ✏2; (10)
let ✏ = C2 ✓q
log(1/ ) rk·k(⌃2)
+ q
log(1/ ) n + (1 + ✏1)2 n Rk·k(⌃2) + ✏2
◆ . Then if n and the effective ranks
are large enough that ✏  1, with probability at least 1 , it holds that
kŵk  kw⇤k+ (1 + ✏)1/2 p n
E k⌃1/22 Hk⇤ . (11)
For a specific choice of norm k·k, we can verify that kv⇤k⌃2 is small. In the Euclidean case, for example, this is done by (78) in Appendix C.2; in our basis pursuit application to come, this is done
by (92). The term ✏2 measures the cost of using a projected version of the subgradient; in most of our applications, we can take ✏2 = 0. Recalling that kv⇤k = 1, this is obviously true with the Euclidean norm for any ⌃2. More generally, if ⌃ is diagonal, then it is natural to only consider covariance splits ⌃ = ⌃1 ⌃2 such that ⌃2 is diagonal. Then, when k·k is the `1 norm (or `p norms more generally), it can be easily seen that Pv⇤ = v⇤ and so kPv⇤k = kv⇤k = 1. Straightforwardly combining Corollary 3 and Theorem 4 yields the following theorem, which gives guarantees for minimal-norm interpolators in terms of effective rank conditions. Just as in the Euclidean case, we can extract from this result a simple set of sufficient conditions for consistency of the minimal norm interpolator. Theorem 5 (Benign overfitting with general norm). Fix any  1/2. Under the model assumptions in (1), let k·k be an arbitrary norm and pick a covariance split ⌃ = ⌃1 ⌃2. Suppose that n and the effective ranks are sufficiently large such that , ✏  1 with the same choice of and ✏ as in Corollary 3 and Theorem 4. Then, with probability at least 1 ,
L(ŵ)  (1 + )(1 + ✏) + kw⇤kE k⌃ 1/2 2 Hk⇤p n
!2 . (12)
Sufficient conditions for consistency of ŵ. As n ! 1, L(ŵ) converges in probability to 2 if there exists a sequence of covariance splits ⌃ = ⌃1 ⌃2 such that
rank(⌃1) n ! 0, kw ⇤kE k⌃1/22 Hk⇤p n ! 0, 1 rk·k(⌃2) ! 0, n Rk·k(⌃2) ! 0, (13)
and, with the same definition of P and v⇤ as in Theorem 4, it holds for any ⌘ > 0 that
Pr(kPv⇤k2 > 1 + ⌘) ! 0. (14)
As we see, the conditions for a minimal norm interpolator to succeed with a general norm generalize those from the Euclidean setting in a natural way. As discussed above, (14) is always satisfied for the Euclidean norm. The only remaining notable difference from the Euclidean setting is that we have two large effective dimension conditions on ⌃2 instead of a single one; in the Euclidean case, the condition on R implies the condition on r.

heading: 6 Application: `1 Norm Balls for Basis Pursuit
text: The theory for the minimal `1 norm interpolator, ŵBP 2 argminL̂(w)=0 kwk1 – also known as basis pursuit (Chen et al. 2001) – is much less developed than that of the minimal `2 norm interpolator. In this section, we illustrate the consequences of our general theory for basis pursuit. Full statements and proofs of results in this section are given in Appendix E.
The dual of the `1 norm is the `1 norm kuk1 = maxi|ui|, and @kuk1 is the convex hull of {sign(ui) ei : i 2 argmax |ui|}. From the definition of sub-gradient, we observe that
min v2@k⌃1/2gk1 kvk⌃  max i2[d]
keik⌃ = q max
i
⌃ii. (15)
Furthermore, by convexity we have
max kwk11
kwk⌃ = q
max i
hei,⌃eii = q max
i
⌃ii (16)
and so rk·k1(⌃) = (E k⌃1/2gk1)2 maxi ⌃ii  Rk·k1(⌃). Therefore, we can use a single notion of effective rank. For simplicity, we denote r1(⌃) = rk·k1(⌃). Combining this with (13) and the previous discussion of (14), we obtain the following sufficient conditions for consistency of basis pursuit.
Sufficient conditions for consistency of ŵBP . As n ! 1, L(ŵ) converges to 2 in probability if there exists a sequence of covariance splits ⌃ = ⌃1 ⌃2 such that ⌃2 is diagonal and
rank(⌃1)
n ! 0,
kw⇤k1 Ek⌃ 1/2 2 Hk1p n ! 0, n r1(⌃2) ! 0. (17)
Application: Junk features. We now consider the behavior of basis pursuit in a junk feature model similar to that of Zhou et al. (2020). Suppose that ⌃ =  ⌃s 0 0 nlog(d)Id , where ⌃s is a fixed matrix and kw⇤k1 is fixed. Quite naturally, we choose the covariance splitting ⌃1 =  ⌃s 0 0 0 , which has
constant rank so that the first sufficient condition is immediately satisfied.
By standard results on the maximum of independent Gaussian variables (e.g. Vershynin 2018), it is routine to check that
E k⌃1/22 Hk1p n = ⇥ r n n ! and r1(⌃2) = ⇥ (log(d)) . (18)
Therefore, basis pursuit will be consistent provided that n = o(n) and d = e!(n). To the best of our knowledge, this is the first time that basis pursuit has been shown to give consistent predictions in any setting with Gaussian covariates and > 0. Although we show consistency, the dimension must be quite high, and the rate of convergence depends on n/log(d) and 1/ p log(d).
Application: Isotropic features. As in the Euclidean case, we generally do not expect basis pursuit to be consistent when ⌃ = Id and w⇤ 6= 0. However, we can expect its risk to approach the null risk 2 + kw⇤k2 if d = e!(n); we will show this using uniform convergence (without covariance splitting). A direct application of Theorem 5 is not enough because the kw⇤k1 p log(d)/n term diverges, but we can remove the dependence on p log(d)/n with a better norm bound. Let S be the support of w⇤ and denote XS as the matrix formed by selecting the columns of X in S. The key observation is that we can rewrite our model as Y = XSc 0+(XSw⇤S +⇠), which corresponds to the case when w
⇤ = 0 and the Bayes risk is 2 + kw⇤k22. If we interpolate using only the features in Sc, the minimal norm will be approximately upper bounded by p 2 + kw⇤k22 p n E kHk⇤ as long as d |S| = e !(n), by Theorem 4. This implies the original model kŵBPk1 can also be upper bounded by the same quantity with high probability. Plugging the norm estimate in to Corollary 3 yields a risk bound of 2 + kw⇤k22.
Relationship to previous works. Both Ju et al. (2020) and Chinot et al. (2021) study the minimal `1 norm interpolator in the isotropic setting. They consider a more realistic scaling where log(d)/n is not large and the target is not the null risk. The best bound of Ju et al. (2020), their Corollary 3, is L(ŵBP )  2(2 + 32 p 14 p s)2, where s is the ground truth sparsity. Note that even when w⇤ = 0, this bound does not show consistency. Similarly, Chinot et al. (2021) establish sufficient conditions for L(ŵBP ) = O( 2), which is nontrivial but also does not show consistency for any > 0; see also the work of Chinot and Lerasle (2020) for a similar result in the Euclidean setting. In contrast, the constants in our result are tight enough to show L(ŵBP ) ! 2 in the isotropic setting when w⇤ = 0 and in the junk feature setting when kw⇤k1 is bounded. Like our work, the results of Chinot et al. (2021) generalize to arbitrary norms; they also consider a larger class of anti-concentrated covariate distributions than just Gaussians, as in the work of Mendelson (2014). If = 0 and w⇤ 2 K (i.e. the model is well-specified and noiseless), their work as well as that of Mendelson (2014) can recover generalization bounds similar to our Corollary 3, but with a large leading constant.

heading: 7 Proof Sketches
text: A key ingredient in our analysis is a celebrated result from Gaussian process theory known as the Gaussian Minmax Theorem (GMT) (Gordon 1985; Thrampoulidis et al. 2015). Since the seminal work of Rudelson and Vershynin (2008), the GMT has seen numerous applications to problems in statistics, machine learning, and signal processing (e.g. Oymak and Hassibi 2010; Stojnic 2013; Oymak and Tropp 2018; Deng et al. 2021). Most relevant to us is the work of Thrampoulidis et al. (2015), which introduced the Convex Gaussian Minmax Theorem (CGMT) and developed a framework for the precise analysis of regularized linear regression. Here we apply the GMT/CGMT to study uniform convergence and the norm of the minimal norm interpolator.
Proof sketch of Theorem 1. For simplicity, assume here there is no covariance splitting: ⌃2 = ⌃. By a change of variable and introducing the Lagrangian, we can rewrite the generalization gap as
sup w2K
Xw=Y
L(w) = 2 + sup w2⌃1/2(K w⇤)
Zw=⇠
kwk22
= 2 + sup w2⌃1/2(K w⇤) inf
h , Zw ⇠i+ kwk22 (19)
where Z is a random matrix with i.i.d. standard normal entries. By GMT3, we can control the upper tail of the max-min problem above (PO) by the auxiliary problem below (AO), with G,H ⇠ N(0, I):
sup w2⌃1/2(K w⇤) inf k k2hH,wi+ h , Gkwk2 ⇠i+ kwk22 = sup w2⌃1/2(K w⇤)
kGkwk2 ⇠k2hH,wi
kwk22 . (20)
By standard concentration results, we can expect kGk22/n ⇡ 1 and k⇠k22/n ⇡ 2, so expanding the second constraint in the AO, we obtain kwk22 + 2  |hH,wi|2/n. Plugging into (19), we have essentially shown that
sup w2K
L̂(w)=0
L(w)  sup w2⌃1/2(K w⇤)
|hH,wi|2 n  sup
w2⌃1/2K |hH,wi|+ |hH,⌃1/2w⇤i| 2
n . (21)
Applying concentration on the right hand side concludes the proof sketch. In situations where the supremum does not sharply concentrate around its mean, we can apply GMT only to the small variance directions of ⌃. This requires a slightly more general version of GMT, which we prove in Appendix A. We also show the additional terms contributed by the large variance components of X cancel out due to Wishart concentration. This is reflected in the term of our theorem statement.
Proof sketch of Theorem 4. Since the minimal norm problem is convex-concave, we can apply the CGMT, which provides a useful direction that GMT cannot. By the same argument as above
inf Xw=Y kwk kw⇤k  inf Xw=⇠ kwk = inf w sup k⌃ 1/2wk+ h , Zw ⇠i
⇡ inf kwk22+ 2|hH,wi|2/n k⌃ 1/2wk = inf kwk2⌃+ 2|h⌃1/2H,wi|2/n
kwk. (22)
To upper bound the infimum, it suffices to construct a feasible w. Consider w of the form ↵v where v 2 @k⌃1/2Hk⇤. Plugging in the constraint, we can choose kwk = ↵ = r 2 ⇣ k⌃1/2Hk2⇤ n kvk2⌃ ⌘ 1
. Rearranging the terms conclude the proof sketch when there is no covariance splitting. The general proof (in Appendix C.1) is more technical, but follows the same idea.

heading: 8 Discussion
text: In this work, we prove a generic generalization bound in terms of the Gaussian width and radius of a hypothesis class. We also provide a general high probability upper bound for the norm of the minimal norm interpolator. Combining these results, we recover the sufficient conditions from Bartlett et al. (2020) in the `2 case, confirm the conjecture of Zhou et al. (2020) for Gaussian data, and obtain novel consistency results in the `1 case. Our results provide concrete evidence that uniform convergence is indeed sufficient to explain interpolation learning, at least in some settings.
A future direction of our work is to extend the main results to settings with non-Gaussian features; this has been achieved in other applications of the GMT (Oymak and Tropp 2018), and indeed we expect that a version of (?) likely holds for non-Gaussian data as well. Another interesting problem is to study uniform convergence of low-norm near-interpolators, and characterize the worst-case population error as the norm and training error both grow. This could lead to a more precise understanding of early stopping, by connecting the optimization path with the regularization path. Finally, it is unknown whether our sufficient conditions for consistency in Section 5 are necessary, and it remains a challenge to apply uniform convergence of interpolators to more complex models such as deep neural networks.
3We ignore a compactness issue here, but this is done rigorously by a truncation argument in Appendix B.1.
Acknowledgments and Disclosure of Funding
Frederic Koehler was supported in part by E. Mossel’s Vannevar Bush Faculty Fellowship ONRN00014-20-1-2826. Research supported in part by NSF IIS award 1764032, NSF HDR TRIPODS award 1934843, and the Canada CIFAR AI Chairs program. This work was done as part of the Collaboration on the Theoretical Foundations of Deep Learning (deepfoundations.ai).

Review summaries:
The authors study generalization bounds for minimum norm linear interpolants. They use techniques from uniform convergence to derive a general bound that applies to minimum norm linear interpolant, that depends on both the norm of the optimal linear predictor as well as the Gaussian width and radius of the corresponding norm ball. In the case of the Euclidean norm the authors re-derive the sufficient conditions previously obtained by Bartlett et al. (2020) by deriving an upper bound on the norm of the predictor. In the case of the l_1 norm, the authors provide a set of sufficient conditions for the minimum norm interpolant to be consistent and discuss the implications in two special cases.

This article deals with excess risk guarantees, under Gaussian noise, of linear regression with interpolators: estimators with zero training error. In particular, it highlights the role played by the norm of an interpolator in the generalization bounds. The proposed analysis covers a wide range of problems since it is valid for a large class of norms. In particular, the analysis covers the case of  $\ell_1$ norm interpolator and the  $\ell_2$ norm interpolator. These upper bounds were used to prove the consistency of the respective interpolators. 

This paper uses (a small modification of) the CGMT for a uniform bound and the GMT for bounding the norm of the min-norm linear interpolators for general norms. Using this technique they recover generalization bounds for l2 and l1 and consistency conditions such as in Tsigler, Bartlett et al. or Zhou et al. In contrast to these works their bound does not only apply to the exact min-norm interpolator but for all linear interpolators that have a norm as small as an high probability upper bound of the min-norm interpolator. By doing this they provide a counterpoint to some recent works that question uniform convergence to explain the generalization capabilities of overparameterized interpolating models.