Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting
Authors: Frederic Koehler
Lijia Zhou
Danica J. Sutherland
Nathan Srebro
Venue: NeurIPS 2021 Oral (2021)
Keywords: interpolation learning
uniform convergence
double descent
statistical learning theory

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 $\ell_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.


Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting
Frederic Koehler" MIT fkochler@iit. edu Collaboration the Theoretical Foundations of Deep Learning (deepfoundations. ai)
Lijia Zhou" University of Chicago zij@uchicago edu
Danica J. Sutherland UBC and Amii dsuth0cs ubc. ca
Nathan Srebro TTI-Chicago nati @ttic. edu
Abstract
We consider interpolation learning in high-dimensional linear regression with Gaussian data, and prove generic uniform convergence guarantee on the general- ization error of interpolators in 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- noomm interpolators, and confirms a prediction of Zhou et al. (2020) for near-minn mouu-minimal--a norm interpolators in the special case of Gaussian data. We demonstrate the generality of the bound by applying it to the simplex, obtaining novel consistency result for minimum fi-nrrm interpolators (basis pursuit). Our results show how norm-based general- ization bounds can explain and be used to analyze benign overfitting, at least in some settings.
Introduction
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 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 only part larger picture: 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 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 al. 2020). Significant progress has been made in this setting, including nearly-matching necessary and sufficient conditions for consistency of the minimal fz 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. Instead of directly analyzing the population error of a learning algorithm, a uniform convergence-lype argument would control the worst-case generalization gap outputs of a learning rule. Typically, this is done because for many algorithms unlike the minimal Euclidean norm interpolator
class of predictors containing the typical
is difficult to exactly characterize the learned predictor, but may be able to say e.g. that its norm is not too large. Since uniform convergence does not tightly depend specific algorithm, the resulting analysis highlight the key properties that lead to good generalization: can give bounds not only for, say, the minimal-norm interpolator, but also
'These authors contributed equally.
NNggrea et al. (2020) argue that Bartlett et al. (2020)'s proof technique is fundamentally based on uni- form convergence of surrogate predictor; Yang al. (2021) study closely related setting with uniform convergence-tye type argument, but do not establish consistency. We discuss both papers more detail in Section
35th Conference on Neural Information Processing Systems (NcurIPS 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 Fuclidean 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 typi- cal 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 fg 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- sigh-dimnsioonal 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 (Section 3) establishes a finite- sample 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 & norm interpolator (Theorem 2 in Section 4), our bound recovers known consistency results (Bartlett et al. 2020), as well proving 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 inter- polators 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 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 l norm interpolator (basis pursuit) in particular settings, which we believe are the first results of their kind.
Problem Formulation
Notation. We use I1-IIp for the Ep norm, |0>1|p - (E, ///po)//p. We always use maxzes fxx to be -00 when S is empty, and similarly minzes fxx be We use standard O(-) notation, and a S b for incquality up to an absolute constant, For a positive semidefinite matrix A, the Mahalanobis (semi-jnorm is || == (x, Ax). For a matrix A and set S, AS denotes the set {Ax I E S}.
Data model. We assume that data (X, Y) is generated as
Y Xwo + X, itd NO, E),
N~N 02,)),
where X E Raxd has i..dd Gaussian rows ,,...., X,, d n, w" is arbitrary, and & is Gaussian and independent of X. Though our proof techniques crucially depend on X, being Gaussian, we can easily relax the assumption the noise & to only being sub-Gaussian; here for simplicity. The empirical and population loss are defined as, respectively,
assume Gaussian noise
L(w)= = n || - -xwl L(w)= = E (y (w, x))² 0² + || - w" 13. (x,9)
where in the expectation y = (I, w*) + Eo with x ~ (O, Σ) independent of Eo NO, o²). For an arbitrary norm |I- the minimal norm interpolator is v = arg L(r)= ||l|] For Euclidean norm specifically, the minimal norm interpolator can be written explicitly as = X(XXT)-X 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
L(w) - L(w).
(2)
|| L(w)=0
Clearly, when 2 ||0]],, 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 bound of the following form may hold more generally:
Bar n + +(1),
L(w) L(w)
sup 10 LB, l(w)=0
where? the Re |0:1| 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 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 vin, = IE |a=|| as well as strengthening and significantly generalizing 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 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
Our result is more general,
the Gaussian case open.
3 Generic Uniform Convergence Guarantee
To state our results, we first need to introduce some key tools.
Definition 1. The Gaussian width and the radius of a set S C R2d are
W(S):= == E sup (s, HY| and (a) = sup |||||2-
H-N(0.1a) sES
sES
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 Σ E Rdxd we write Σ Σ Dg if > Σ + Dg, each matrix is positive semidefinite, and their spans are orthogonal.
Note that Σ Σn e Σg 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 (Main generalization bound). There exists an absolute constant C1 I 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 Σ = Σ₁ $ Σz. Fixing < 144, let B =C, (V
(og(1/8)
rank(E1)
If
is large enough that 3 < 1, then the following holds with probability least 1:
2
1 1 B [(w)= <
322
W(E)/2 K.) + (rad(=//2/)) KC) + 1|0" l12.) 22log
sup W(K,
n
In our applications, we consider XC = {w E Rdd || < B}} for an arbitrary norm, with B based on probabibbyyylityy upper bound for || Depending on the application, the rank of En will be
Whee ||=|| concentrates, we need v.. to match typical value. That is, the might a high probability bound on |-|| 2 or for (subJGaussian data, in case, thn = E 1|
3

---

1.75
bound bayes
1.75
bound bayes
1,25
1.25
0.75
0.15
0.25
0.25
2
8
10
12
14
10
d/n
(a) = 1 (isotropic)
(b) À = 0.1
Figure 1: Illustration of our generalization bound when >
n2 = 200, 0² = 1/2. X La--11
w = (1/v2,0..... .). and is varied (x-axis). Averages (curve) and standard deviations (cr- ror bars) are estimated from 400 trials for each value of d. Here the curve marked "loss" cor- responds to L(w) for the minimum Euclidean norm interpolator t, "bound" to | Tr //n = E | + (d 1))/n which an asymptotic bound on L(w)) due to Corollary 1, "null" the loss L(0) = of the zero estimator, and "bayes" is the Bayes-optime error L(w") = o² = 1/2. The
vertical line is d/n 1, the location of the double-descent peak; for d/n n 1 there are almost surely no interpolators.
either constant or o(n), so that -> O. The term ||=|||, generally does not scale with n and hence 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 a /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. 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 W<=2/2x))² X.)² /n, which can be viewed the ratio between the (probabilistic) dimension of our hypothesis class and sample size. We will also analyze how large K must be contain any interpolators, allowing to find consistency results.
part of the analysis in the following sections,
4 Application: Euclidean Norm Ball
It can be easily that the Gaussian width of Euclidean norm ball reduces nicely to the product of the norm of our predictor with the typical norm of x: if I {w E Rd ||l||2 S B}. then
W B
E (O,
11/2 H S
B² |
(3)
Therefore, it is plausible that (+) holds with v. = E generalization bound in two simple examples, motivated by Hastie al. (2019) and Zhou et (2020). Indeed, an application of our main theorem proves that this is exactly the case for Gaussian data.
Tr(2). Figure illustrates this
Corollary (Proof of the speculative bound (+) for Gaussian data). Fix any 8 < 1/4. Under the model assumptions in (1) with B 2 ||w*||2 and Z log(1/5), some S /log(1/8)/m, it holds with probability at least that
B Tr(E) L(w) S (1+7)
sup ((
7
The above bound is clean and simple, but only proves sub-optimal rate of n -1/4, This is because the choice of covariance split used the proof of Corollary 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(E) can be replaced by 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 covariance matrix Σ are
Tr(2) D>llop
Tr( and REE) Tr(E2)
r(2)
The r(E) 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 l2 norm of a Gaussian vector with covariance E. In fact, both definitions of effective ranks can be derived by applying Bernstein's 's inequality to || /E ||=] We will only need r(Σ) in the generalization bound below, but we will show in Theorem that R(E) can be used to control the norm of the minimal norm interpolator wb
Corollary 2. There exists absolute constant C1 66 such that the following is true. Under (1), pick any split E = En @ En, fix 8 & 1/4, and let = =
log(1/8)
log(1/8)
rank(Ea)
x(222
If 2 1 ||2 and n is large enough that 7 S 1, the following holds with probability at least
B² TT(E2)
sup [
L(w) S (1 11++7
(5)
71
In order use Corollary or 2 to prove consistency, we need a seghhprobabilityy bound for ||0]]] 2. the norm of the minimal norm interpolator, so that B will be large enough to contain any interpolators. Theorem gives exactly such bound, showing that if the effective ranks R(E²) and r(E2) are large, then we can construct an interpolator with Euclidean norm nearly || ||2 + a Vovn n/ Tr({2).
Theorem (Euclidean norm bound; special case of Theorem 4). Fix any ó < 1/4. Under the model assumptions in (1) with any choice of covariance splitting Σ = Σσ $ Σ,, there exists some
S
Tog(L/8) r(E2) + 10g(1/6) + n log((188 such that the following is true. If and the effective ranks
[((2aa)
are such that S 1 and R(E2) z 1og(1/5)² then with probability at least 1 5, it holds that
||0l122 S I| ll2 + +11 (1+ 11/2
72
(6)
Tr(E2)
Plugging in estimates of || to our scale-sensitive bound Corollary 2, we obtain a population loss guarantee for in terms of effective ranks.
Theorem 3 (Benign overfitting). Fix any 8 < 1/2. Under the model assumptions in (1) with any covariance splitting Σ Σn @ Ez, let y and be as defined Corollary 2 and Theorem Suppose that n and the effective ranks are such that R(Ez) Z log(1/5) and 7 S 1. Then, with probability least 5,
L(w) S (1 (1+ +7) ( ||w0
Tr(22)
2
12
From (7), we can see that to ensure consistency, i.e. L(w) 0², it is enough that y - 0, + and [| 1ee" Tr(Ea)) - 0. Recalling the definitions the various quantities and using that r(Er) > R(E,) (Bartlett et al. 2020, Lemma 5), arrive the following conditions.
Sufficient conditions for consistency of w. As m + oc, L(w) converges in probability to o² there exists sequence of covariance splits Σ = Σ₁ E, such that
rank(E,) + O, ||"" ll
(r(E2)
72
O,
+ 0.
(8)
71
R{E2)
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 minimize rank(E;) such that r(22) 2
5

---

2. Their version of the second condition replaces Tr(E2) by the larger term Tr(E).
From the perspective of showing L(i) > o², the first difference is immaterial: if there exists choice of split that satisfies our conditions, it can be shown that there exists a (possibly different) split which will also satisfy r(Ez) 2 (see Appendix D.2.1). ).. The second point is genuine improvement over the consistency result of Bartlett et al. (2020) when 2 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(E2)=1/2 term and the dependence on /rank(Z1)/n instead of rank(21)/n is slightly worse than that of Bartlett et al. (2020), but our bound can be applied for smaller value of rank(E1) and is better the ||w* / (T2))))) / 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 norm ball, Negrea al. applied uniform convergence predictor, and separately showed that the minimal-norm interpolator has risk close to the surrogate (and, indeed, argue that this fundamentally the proof strategy of Bartlett al. (2020) all along). Their analysis reveals an interesting connection between realizability and interpolation learning, but it does not highlight that low norm key to good generalization, nor does it predict the worst-case error for other low-norm interpolators.
surrogate
Relationship to Bartlett and Long (2020). Bartlett and Long recently showed that is impossible to find 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 either the training error L the population noise level o². 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 σ²), but (x) and our bounds are about the generalization gap (I. f.).
Relationship to Yang et al. (2021). Yang et al. give expressions for the asymptotic generalization error of predictors in norm ball, in 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 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 [||w| would expect loss of a²o"" -i... 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 a approaches 1.
|| with > 1 constant, where
-i.e.
5 General Norm Ball
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 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 ||-I| on IR is ||a][| == max 1 u). and the set of all its sub-gradients with respect to u is @|[u|]|+ = {v ||u||| = 1, (c. u) = [|u][.].
The Fuclidean norm's dual is itself; for it and many other norms, Ø [| is singleton set. Using these notions, we will now give versions of the effective ranks appropriate for generic norm balls.
Definition 5. The effective I-rnks of a covariance matrix Σ are given as follows. Let H N (0, Ia), and define 8* = arg min sea || Then
E | ||||
LE /E| 2
(E) = sup | 1 ||20|
and (E) =
E
|
l|x

---

The first effective ||-l|-aakk is the squared ratio of Gaussian width to the radius of the set / where I' is norm ball (w : || I B}: the importance of this ratio should be clear from Theorem The Gaussian width is given by W( = B E l.., while the radius can be written w ||||] so that the factors of B cancel.
The choice of RiI-11 arises naturally from our bound on ||=||| in Theorem 4 below. Large effective rank of Σg means the sub gradient v² of || H|| is small in the I1-1Ix, norm. This is, in fact, closely related to the existence of low-norm interpolators. First, note that E H corresponds to the -mallleigenvalue components of the covariate vector. For e" to be a sub- uub-gradient means that moving the weight vector in the direction of v" is very effective at changing the prediction (w, X); having small ||1/ 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 I1-112 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 ||x]| in their numerators, while 11-112 and R1-11, use (E ||=]])) The denominators of r and Ill-ll, agree; Lemma 9, in Appendix C.2, shows that r(E) 1 S TH (E) S r(E). The the denominator is R(E). Equation (75), in Appendix C.2, shows that Ri (E) 2 cR(E) for some that converges to 1 as r(E) 00, as is required by the consistency conditions. The other direction, R(E) 2 é R1-11 (E), also holds with d' + 1 as r(E?) co. It would be possible (and probably even more natural with our analysis) to state the consistency conditions in Section 4 in terms of r11-11, and R1i-11: we used r and R mainly to allow direct comparison Bartlett et al. (2020).
denominator of Ril-11 uses the sole sub- sub-gradient v* ///2//EE
then | / ///////////// ~ Tr(=²)/ Tr()), giving that (II11(22) ~ (r)) /T<(3
Using the general notion of effective ranks, we can find an analogue of Corollary 2 for general norms.
Corollary 3. There exists absolute constans C1 66 such that the following is true. Under the model assumptions in (1), take any covariance spliting Σ = Li + Dg and let ||-Il be an arbitrary
norm. Fixing 8 S 1/4, let = -C
Tog(1/8)
+ +V [To((188) + rank(E.) "
If B 2 || || and is
n
large enough that y $ 1, then the following holds with probability at least - 5:
BB E
12/2 H1I.
sup [ ((w))(
L(w)= S (1+
(9)
n
As in the Euclidean special case, we still need a bound on the norm of ih arg min || to use this result to study the consistency of ú. This leads us the second main technical result of this paper, which essentially says that if the effective ranks R (E2) and ri-1 (E2) are sufficiently large,
then there exists an interpolator with norm || + of BIE 1/2 gll..
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 Σ = Eσ @ Σz, let ||-Il be an arbitrary norm, and fix d < 1/4. Denote the &a orthogonal projection matrix onto the space spanned by Ee as P. Let H ~ N (0, Ia), and let v² = arg min eEalls [ H|I | Suppose that there exist
E1, 62 2 such that with probability at least 1 - 8/4
| (1 + +c)+ |100 Ir,
and
|| <1+
(10)
let c = C2 (V 1OR(11S)
/ /oo((1/0) + +1++ ()-)(>;)) + tc2) Then if n and the effective ranks
are large enough that S 1, with probubility at least 1 - 8, it holds that
Vn
| < ||00|| + (1 61/2)
(11)
E
|
H|.
For a specific choice of norm ||-I|, we can verify that ||, is small. In the Fuclidean case, for example, this is done by (78) in Appendix C.2; in our basis pursuit application to come, this is done
7

---

by (92). The term 22 measures the cost of using projected version of the subgradient; in most of our applications, we can take 62 O. Recalling that ||o*||
this is obviously true with the Euclidean norm for any Eg. More generally, if Σ is diagonal, then it is natural to only consider covariance splits E E ① Σg such that Σg is diagonal. Then, when ||-I| is the & norm (or lp norms more generally), it can be easily seen that Pv v* and so ||Pu*|| - ||0*||
Straightforwardly combining Corollary and Theorem 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 (Benign overfitting with general norm), Fix any å < 1/2. Under the model assumptions in (1), let II-Il be an arbitrary norm and pick covariance split Σ = Σ1 @ Σz. Suppose that and the effective ranks are sufficiently large such that 7,e S 1 with the same choice of y and as in Corollary 3 and Theorem 4. Then, with probability at least 8,
L(w) s (1+
a
||'"
E
1/ 2
H
1|
2
(12)
vn
Sufficient conditions for consistency of Φ. As n + oc, L(w) converges in probability to o² if there exists sequence of covariance splits Σ Σ₁ Eg such that
rank(E) (2)) O,
||
| HII-
1
71
0,
- 0, (13)
72
Vn
(1-1((22)
R (E2)
and, with the same definition of and v- as in Theorem 4, it holds for any n > that
Pr[[|Pu 1 1) + 0.
(14)
As see, the conditions for minimal norm interpolator to succeed with 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 Mا instead of a single one; in the Euclidean case, the condition on R implies the condition on
6 Application: l Norm Balls for Basis Pursuit
The theory for the minimal & norm interpolator, ørr E arg min [(w)= [|l]] - also known as basis pursuit (Chen et al. 2001) is much less developed than that of the minimal E2 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 & norm is the foo norm ||/|| (sgg e E arg max |u,]). From the definition of sub-gradient, we observe that
max; jull, and a||u]|oo is the convex hull of
min e -
||u||x
S max ||e/|i> = y /max En. xE|d]
(15)
/0 =1
Furthermore, by convexity we have
max Ne 11
max (ei, Eee) = max Ei
(16)
(E //1 < Rig-11 (E). Therefore, we can use a single notion of effective max,; Vi. rank. For simplicity, we denote ri (Σ) = T][-| (E). Combining this with (13) and the previous discussion of (14), we obtain the following sufficient conditions for consistency of basis pursuit.
and so T1- (Σ)-
Sufficient conditions for consistency of wp. As n + 00, L(w) converges to o² in probability if there exists sequence of covariance splits E Σn Eg such that Eg is diagonal and
rank (E,) + O,
Iw"
B E 1/2 ooo 0,
- O. r (Σ2)
(17)
8

---

Application: Junk features. We now consider the behavior of basis pursuit in junk feature model similar to that of Zhou et al. (2020). Suppose that 2
Σ
where Mg is a fixed matrix do
D 0
and ||=||| is fixed. Quite naturally, we choose the covariance splitting Σ1
which has
0
0
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 check that
H 10
(V An
+
and ri = = (log(d))
(18)
Therefore, basis pursuit will be consistent provided that An o(n) and ea(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 > O. Although we show consistency, the dimension must be quite high, and the rate of convergence depends on n/log(d) (d) and 1/ llo(d)
Application: Isotropic features. As in the Euclidean case, we generally do not expect basis pursuit to consistent when Σ = La and w" + O. However, we can expect its risk to approach the null risk o² + ||u if d e'(m)); we will show this using uniform convergence (without covariance splitting).
direct application of Theorem is not enough because the || (io///lg())) (d) /n term diverges, but we can remove the dependence on / /log(d)/n with a better norm bound. Let S be the support of w* and denote Xg as the matrix formed by selecting the columns of X in S. The key observation is that we can rewrite our model as Y = ss 0+ (X +)), which corresponds to the case when w" = 0 and the Bayes risk is o² + | [2. If we interpolate using only the features in S the minimal norm will be approximately upper bounded by / +
as long d - |S| ea("), by Theorem 4. This implies the original model |B can also be upper bounded by the same quantity with high probability. Plugging the norm estimate in to Corollary 3 yields risk bound of o² + ||
11 /n
Relationship to previous works. Both Ju et al. (2020) and Chinot et al. (2021) study the minimal l 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 (() S o2(2 + 32 /5) where s is the ground truth sparsity. Note that even when w" O, this bound does not show consistency. Similarly, Chinot et al. (2021) establish sufficient conditions for BP = O ), which is nontrivial but also does not show consistency for any a > O; 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(WBP) + σ² in the isotropic setting when w' = and in the junk feature setting when |w"' || is bounded.
Like our work, the results of Chinot al. (2021) generalize to arbitrary norms; they also consider larger class of anti-concentrated covariate distributions than just Gaussians, as in the work of Mendelson (2014). If a = 0 and w" E 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.
7 Proof Sketches
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 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, assumee here there is no covariance splitting: Σg = E. By a change of variable and introducing the Lagrangian. we can rewrite the generalization gap as
sup [(w)= = 0²
sup (K-)""
2r EE
WEE'A
00
Zw=
(19)
0²
sup (
inf (A, Zw E) + 1w0
where Z is a random matrix with i..dd standard normal entries. By GMT", we can control the upper tail of the max-min problem above (PO) by the auxiliary problem below (AO), with G, H ~ (N 1):
sup inf (H, w) + (A, Gl|wll2 - E) + ||wll = w =EIV/((K=>)
sup WEE!/2 (K- w²)
| |
(20)
|| -1
By standard concentration results, we can expect ||G| R and |KElB/n R o², so expanding the second constraint in the AO, we obtain | + o² KH, w) /n. Plugging into (19), have essentially shown that
(H. w)1? (SuPwexx/aX KH, w) + EH, WEEVA((--)))
sup
S sup
(21)
WEK [[w]=0
n
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
||o||| - ||w'|| || S inf |w||| inf sup | 1/2w|| + (A, Zw E
Xwr=
(22)
inf || (F/
|| 1/2
| + inf
|l||-
(
To upper bound the infimum, it suffices to construct a feasible w. Consider w of the form ov where v e
/||E//2H| ||.. Plugging in the constraint, we can choose |||||| = a 02 |
||0|
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.
Discussion
In this work, we prove generic generalization bound in terms of the Gaussian width and radius of a hypothesis class. We also provide 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 lg case, confirm the conjecture of Zhou et al. (2020) for Gaussian data, and obtain novel consistency results in the & case. Our results provide concrete evidence that uniform convergence is indeed sufficient to explain interpolation learning, at least 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 version of (x) 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 eтror 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, is unknown whether our sufficient conditions for consistency in Section 5 are necessary, and it remains a challenge apply uniform convergence of interpolators to more complex models such as deep neural networks.
We ignore compactness issue here, but this is done rigorously by truncation argument in Appendix B.I.
10

---

Acknowledgments and Disclosure of Funding
Frederic Koehler was supported in part by E. Mossel's Vannevar Bush Faculty Fellowship ONR- 100014-20-1-2822 Research supported in part by NSF IIS award 1764032, NSF HDR TRIPODS award 1934843, and the Canada CIFAR Al Chairs program. This work was done as part of the Collaboration on the Theoretical Foundations of Deep Learning (deepfoundations.. ai).
References
Bandeira, Afonso S. (2016). "Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science." Lecture notes, MIT. URL: https / /eoppee math. ethz htt/cchaadeeeeeeeeeeeeeee abandeira/ pdf.
Bartlett, Peter L. and Philip M. Long (2020). "Failures of model-dependent generalization bounds for least-norm interpolation." arXiv: 2010. 2010.08479. 08479.
Bartlett, Peter I.., Philip M. Long, Gábor Lugosi, and Alexander Tsigler (2020). "Benign overfitting
in linear regression." Proceedings of the National Academy of Sciences 117.48, pp. 30063-30070.
arXiv: 1906. 11300.
Belkin, Mikhail, Daniel Hsu, Siyuan Ma, and Soumik Mandal (2019). "Reconciling modern machine learning practice and the bias-variance trade-off." Proceedings of the National Academy of Sciences
116.32, pp. 15849-15854, arXiv: 1812. 11118.
Belkin, Mikhail, Daniel Hsu, and Xu (2020). "Two models of double descent for weak features."
SIAM Journal on Mathematics of Data Science 2.4, pp. 1167-1180. arXiv: 00571.. Chandrasckaran, Venkat, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky (2012). "The convex geometry of linear inverse problems." Foundations of Computational Mathematics 12.6, pp. 805- 849.
Chen, Scott Shaobing, David L.. Donoho, and Michael A. Saunders (2001). "Atomic decomposition by basis pursuit." SIAM Review 1, pp. 129-159.
Chinot, Geoffrey and Matthieu Lerasle (2020). "On the robustness of the minimum & interpolator." arXiv: 05838.
Chinot, Geoffrey, Matthias Löffler, and Sara van de Geer (2021). "On the robustness of minimum-
norm interpolators." arXiv: 2012. 00807.
Deng. Zeyu, Abla Kammoun, and Christos Thrampoulidis (2021). "A model of double descent for high-dimensional binary linear classification." Information and Inference: A Journal of the IMA.
arXiv: 1911. 05822.
Durrett, Rick (2019). Probability: theory and examples. Cambridge University Press.
Gordon, Yehoram (1985). "Some inequalities for Gaussian processes and applications." Israel Journal
of Mathematics 50.4, pp. 265-289.
Gordon, Yehoram (1988). "On Milman's inequality and random subspaces which escape through a mesh in _ Geometric Aspects of Functional Analysis. Vol. 1317. Lecture Notes in Mathematics. Springer, pp. 84-106.
Hastie, Trevor, Andrea Montanari. Saharon Rosset, and Ryan J. Tibshirani (2019). "Surprises in High-Dimensionn Ridgeless Least Squares Interpolation." arXiv: 1903.08560.
Ju. Peizhong, Xiaojun Lin, and Jia Liu (2020). "Overfitting Can Be Harmless for Basis Pursuit: Only to a Degree." " Advances in Neural Information Processing Systems. arXiv: 2002. 2002.00492. 00492.
Kamath, Gautam (2013). "Bounds on the Expectation of the Maximum of Samples from Gaussian." URL: htttp://wstt gaut amkamath. com/ /r tings/ www.ttigggggtutn//seeeeeeereeeee gaussian. __axx, pdf (visited in 2021). Ledoux, Michel (1992). "A heat semigroup approach to concentration the sphere and compact Riemannian manifold." Geometric & Functional Analysis GAFA 2.2, pp. 221-224.
Mendelson, Shahar (2014). "Learning without concentration." " Conference on Learning Theory.
PMLR, pp. 25-39.
Muthukumar, Vidya, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai (2020). "Harmless interpolation of noisy data in regression." IEEE Journal on Selected Areas in Information Theory. arXiv: 1903. 09139.
Nagarajan, Vaishnavh and J. Zico Kolter (2019). "Uniform convergence may be unable to explain generalization in deep learning." Advances in Neural Information Processing Systems. arXiv: 1902. 04742.
Negrea, Jeffrey, Gintare Karolina Dziugaite, and Daniel M. Roy (2020). "In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors." International Conference on Machine Learning, arXiv: 1912. 04265.

---

Neyshabur, Behnam. Ryota Tomioka, and Nathan Srebro (2015). "In Search of the Real Inductive Bias: On the Role of Implicit Regularization Deep Learning." International Conference on Learning Representations Workshop. arXiv: 1412.6614.
Oymak, Samet and Babak Hassibi (2010). "New null space results and recovery thresholds for matrix
rank minimization." arXiv: 2011.6326.
Oymak, Samet and Joel A Tropp (2018). "Universality laws for randomized dimension reduction, with applications." Information and Inference; A Journal of the IMA 7.3, pp. 337-446.
Rudelson, Mark and Roman Vershynin (2008). "On sparse reconstruction from Fourier and Gaussian
Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 61.8. pp. 1025-1045.
measurements." Communicatiion
Shalev-Shwart Shai and Shai Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.
Srebro, Nathan, Karthik Sridharan, and Ambuj Tewari (2010). "Optimistic Rates for Learning with
Smooth Loss." arviv: 1
Stojnic, Mihailo (2013). "A framework characterize performance of LASSO algorithms." arXiv:
1303. 7291.
Thrampoulidis, Christos, Samet Oymak, and Babak Hassibi (2015). "Regularized linear regression: A precise analysis of the estimation error." Conference on Learning Theory. PMLR, pp. 1683-1709. Tsigler, Alexander and Peter L. Bartlett (2020). "Benign overfitting in ridge regression." arXiv: 2009. 14286.
Valiant, Leslie G. (1984). "A theory of the learnable." " Communications of the ACM 27.11, pp. 1134- 1142.
Van Handel, Ramon (2014). "Probability High Dimension." " Lecture notes, Princeton University.
URL: https::////e //web: math. pricc.prnnetoo.... felu/"rvaa////e rran APC550. pdf.
Vapnik, Vladimir (1982). Estimation of Dependences Based on Empirical Data. Springer Series in Statistics. Springer- Verlag.
Vershynin, Roman (2010). "Introduction to the non-asymptotic analysis random matrices." arXiv:
1011.3027.
Vershynin. Roman (2018). High--dimensioal probability: An introduction with applications in data science. Cambridge University Press.
Yang, Zitong, Yu Bai, and Song Mei (2021). "Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models." International Conference Machine Learning. arXiv: 1.03.00554.
Zhang, Chiyuan, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals (2017). "Under- standing deep learning requires rethinking generalization." " International Conference on Learning Representations, arXiv: 1611. 03530.
Zhou, Lijia, Danica J. Sutherland, and Nathan Srebro (2020). "On Uniform Convergence and Low- Norm Interpolation Learning." Advances in Neural Information Processing Systems, arXiv: 2006.
05942.
12


Reviews:
[{"review_id": "UUdWJKokMbl", "reviewer": "Reviewer_Gkhk", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- the authors provide a novel and (to the best of my knowledge) innovative and elegant way to use uniform bounds for low-norm linear interpolators for regression (proven separately before for the min-l1 and min-l2) by appealing to the (C)GMT. \n- the manuscript is very clearly and nicely written\n- the proof sketch contains the key ideas of the proof so it’s very informative\n\nConstructive comments:\n- The proof technique is the key novelty and one certainly wonders about the impact of the exercise of unifying proof framework for l1 and l2 generalized to norms in general -> is there any gain going forward for non-Gaussian distributions, neural networks etc. - the impact of the new technique is not quite clear to me since the (C)GMT crucially rely on Gaussianity. On the other hand, the l1-discussion about w* = 0 - relatively speaking, it’s not that big of a result IMO. Hence in my view, given the limited space, it would be much more enlightening to shorten that section and instead discuss the impact of the new proof technique. Also a discussion about more insights from the proof would be very helpful / useful - what is the intuition behind why consistency for min-l1 can be achieved for spiked covariances with d = e^{omega(n)}? \n- The proof would benefit from significant modularization. Navigating through the proofs is unnecessarily cumbersome since there is a lot of nesting, lemmas are often proved along the way\n\nOn  another note: \nRegarding the story that makes a case for/in defense of uniform convergence min-norm-ball: I guess somewhat concurrently, Chinot et al. ‘21 (AdaBoost ...) have also used uniform convergence techniques for min-l1-norm classifiers although they study a different setting … \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "AhIhcudoWAB", "reviewer": "Reviewer_CCVZ", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper was a pleasure to read, and the authors provide an interesting set of results that help improve our understanding of the behavior of interpolating models. Their results also indicate that the fact that techniques from uniform convergence may indeed be useful in understanding the generalization behavior of interpolating models by skirting past recent lower bounds (e.g. Bartlett and Long).  Some questions for the authors that hopefully shall help improve this draft:\n\n1. In ln 107 the authors say that we expect the Gaussian width to scale like sigma sqrt{n}. I dont see where the dependence on sigma comes in here if the set K is just the norm ball of radius B.\n\n2. In equation 12 is it clear if the sufficient conditions for the l_1 minimizer to be consistent close to necessary? Is there any evidence, theoretical or otherwise to suggest this or not?\n\n3. On ln 266 the authors say ||w^*||_1 sqrt{log(d)/n} diverges, but it is not clear to me why this is the case.\n\n4. I would appreciate a more detailed comparison between the techniques used in this paper and the techniques employed by Ju et al. and Chinot et al. who also study the minimum ell_1 norm interpolant using uniform convergence techniques.\n\n\n5. On ln 297, both equation (PO) and equation (AO) are not defined.\n\n\n========== Post rebuttal comments ========== \n\nI thank the authors for their responses. I would like to continue to vote for acceptance, and would be happy to see this paper being published at NeurIPS.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential impacts of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "4ID2_qV47wk", "reviewer": "Reviewer_GGnj", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although heavily technical, the article is well written and the proven results were widely discussed and compared to the existing results in the literature. However, some aspects of this work need to be clarified: \n- the theoretical results proven in this article are relevant and single out from existing work in the regime  $n$ goes to infinity. Yet, in practice, the dimension d  is finite. Taking both n and d to infinity makes sense in the context of kernel-based interpolation: the effective dimension increases with n and goes to infinity as the regularisation parameter goes to $0$. But, it seems to be unnatural to take d to infinity in the context of linear regression. How can we conciliate the two seemingly contradictory regimes (n goes to infinity and d is finite) in the context of linear regression? \n- It would be interesting to give the intuition behind the conditions for consistency in equation (7), especially for the two quantities $\\sqrt{\\frac{Tr \\Sigma_2}{n}}$ and $\\frac{n}{R(\\Sigma_2)}$. (Or at least the order of magnitude of these quantities when $\\Sigma$ is a sequence of decreasing exponentially or polynomially to 0.) \n-The same goes with the conditions of Theorem 2: intuitively, what does it mean to have $R(\\Sigma_2) \\geq n \\log(2/\\delta) ...$?\n\nMinor comments:\n- Line 122: I can’t understand why the rate is only $\\mathcal{O}(N^{-1/4})$ since $1+\\beta^{,}$ converges to 1.\n- Equation (7) is misleading: we may think that the three terms are equals...\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies uniform convergence for linear predictors in the high-dimensional setting with gaussian assumptions on the data. This setting has been adopted by the learning theory community to tractably study generalization phenomena arising in deep learning. In this setting, the paper gives new bounds on the generalization error of interpolating solutions, where the bound depends on the gaussian width of the function class and the norm of the predictor. This recovers some existing bounds derived in special cases, and adds a counterpoint to recent work suggesting uniform convergence cannot explain generalization in high dimensional settings.

All reviewers agreed that the results are novel and interesting, the paper is clearly written, and the proofs are easy to follow and illuminating. As such, we believe this will make a strong contribution to the program. 
Decision: Accept (Oral)