Journal of Machine Learning Research 1 (2000) 1-48

Submitted 4/00; Published 10/00

Failures of Model-dependent Generalization Bounds
for Least-norm Interpolation
Peter L. Bartlett

peter@berkeley.edu
University of California, Berkeley & Google, 367 Evans Hall #3860 Berkeley, CA 94720-3860.

Philip M. Long

plong@google.com

Google, 1600 Amphitheatre Parkway, Mountain View, CA, 94043.

Editor: Pierre Alquier

Abstract
We consider bounds on the generalization performance of the least-norm linear regressor,
in the over-parameterized regime where it can interpolate the data. We describe a sense inwhich any generalization bound of a type that is commonly proved in statistical learningtheory must sometimes be very loose when applied to analyze the least-norm interpolant.
In particular, for a variety of natural joint distributions on training examples, any valid
generalization bound that depends only on the output of the learning algorithm, the numberof training examples, and the confidence parameter, and that satisfies a mild condition(substantially weaker than monotonicity in sample size), must sometimes be very loose—it
can be bounded below by a constant when the true excess risk goes to zero.
Keywords: generalization bounds, benign overfitting, linear regression, statistical learning theory, lower bounds

1. Introduction
Deep learning methodology has revealed some striking deficiencies of classical statisticallearning theory: large neural networks, trained to zero empirical risk on noisy training data,
have good predictive accuracy on independent test data. These methods are overfitting(that is, fitting to the training data better than the noise should allow), but the overfitting
is benign (that is, prediction performance is good). It is an important open problem tounderstand why this is possible.
The presence of noise is key to why the success of interpolating algorithms is mysterious.
Generalization of algorithms that produce a perfect fit in the absence of noise has beenstudied for decades (see Haussler, 1992, and its references) A number of recent papers haveprovided generalization bounds for interpolating algorithms in the absence of noise, either
for deep networks or in abstract frameworks motivated by deep networks (Li and Liang,
2018; Arora et al., 2019; Cao and Gu, 2019; Feldman, 2020). The generalization bounds
in these papers either do not hold or become vacuous in the presence of noise: Li andLiang (2018) rule out noisy data in Assumption A1; the data-dependent bound of Aroraet al. (2019, Theorem 5.1) becomes vacuous when independent noise is added to the yi ;adding a constant level of independent noise to the yi in the setting of Cao and Gu (2019,
Theorem 3.3) gives an upper bound on excess risk that is at least a constant; and theanalysis of Feldman (2020) concerns the noise-free case.
c 2000 Peter L. Bartlett and Philip M. Long.
License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided
at http://jmlr.org/papers/v1/bartlett21.html.

Bartlett and Long

There has also been progress on bounding the gap between average loss on the training
set and expected loss on independent test data, based on uniform convergence argumentsthat bound the complexity of classes of real-valued functions computed by deep networks.
For instance, the results of Bartlett (1998) for sigmoid nonlinearities rely on `1 -norm bounds
on parameters throughout the network, and those of Bartlett et al. (2017) for ReLUs relyon spectral norm bounds of the weight matrices throughout the network (see also Bartlett
and Mendelson, 2002; Neyshabur et al., 2015; Bartlett et al., 2017; Golowich et al., 2018;
Long and Sedghi, 2019). These bounds involve distribution-dependent function classes,
since they depend on some measure of the complexity of the output model that may be
expected to be small for natural training data. For instance, if some training method gives
weight matrices that all have small spectral norm, the bound of Bartlett et al. (2017) will
imply that the gap between empirical risk and predictive accuracy will be small. But while
it is possible for these bounds to be small for networks that trade off fit to the data withcomplexity in some way, it is not clear that a network that interpolates noisy data could
ever have small values of these complexity measures. This raises the question: are there
any good data-dependent bounds for interpolating networks?
Zhang et al. (2017) claimed, based on empirical evidence, that conventional learningtheoretic tools are useless for deep networks, but they considered the case of a fixed classof functions defined, for example, as the set of functions that can be computed by a neuralnetwork, or that can be reached by stochastic gradient descent with some training data,no matter how unlikely. These observations illustrate the need to consider distributiondependent notions of complexity in understanding the generalization performance of deep
networks. The study of such distribution-dependent complexity notions has a long history
in nonparametric statistics, where it is central to the problem of model selection (see, forexample, Bartlett et al., 2002, and its references); uniform convergence analysis over alevel in a complexity hierarchy is part of a standard outline for analyzing model selection
methods.
Nagarajan and Kolter (2019) provided an example of a scenario where, with high probability, an algorithm generalizes well, but two-sided uniform convergence fails for any hypothesis space that is likely to contain the algorithm’s output. Their analysis takes an important
step in allowing distribution-dependent notions of complexity, but only rules out the application of a specific set of tools: uniform convergence over a model class of the absolutedifferences between expectations and sample averages. Indeed, in their proof, the failure isan under-estimation of the accuracy of a model—a model has good predictive accuracy, but
performs poorly on a sample (one obtained as a transformed but equally likely version of
the sample that was used to train the model). However, in applying uniform convergence
tools to show good performance of an algorithm, uniform bounds are only needed to showthat bad models are unlikely to perform well on the training data. So if one wishes toprovide bounds that guarantee that an algorithm has poor predictive accuracy, Nagarajan
and Kolter (2019) provided an example where uniform convergence tools will not suffice. In
contrast, we are concerned with understanding what tools can provide guarantees of goodpredictive accuracy of interpolating algorithms.
In this paper, motivated by the phenomenon of benign overfitting in deep networks, weconsider a simpler setting where the phenomenon occurs, that of linear regression. Negrea
et al. (2020, Lemma 5.2) adapt the construction of Nagarajan and Kolter (2019) to show
2

Failures of Model-dependent Generalization Bounds

a similar failure of uniform convergence in this context, and similarly cannot shed lighton tools that can or cannot guarantee good predictive accuracy. We study the minimum
norm linear interpolant. Earlier work (Bartlett et al., 2020) provides tight upper and lower
bounds on the excess risk of this interpolating prediction rule under suitable conditions on
the probability distribution generating the data, showing that benign overfitting depends on
the pattern of eigenvalues of the population covariance, and there is already a rich literatureon related questions (Liang and Rakhlin, 2020; Belkin et al., 2019b,a; Hastie et al., 2019a,b;
Negrea et al., 2020; Derezinski et al., 2020; Li et al., 2020; Tsigler and Bartlett, 2020). Theserisk bounds involve fine-grained properties of the distribution. Is this knowledge necessary?
Is it instead possible to obtain data-dependent bounds for interpolating prediction rules?
Already the proof of Bartlett et al. (2020) provides some clues that this might be difficult:when benign overfitting occurs, the eigenvalues of the empirical covariance are a very poor
estimate of the true covariance eigenvalues—all but a small fraction (the largest eigenvalues)
are within a constant factor of each other.
In this paper, we show that in these settings there cannot be good risk bounds based ondata-dependent function classes in a strong sense: For linear regression with the minimum
norm prediction rule, any “bounded-antimonotonic” model-dependent error bound thatis valid for a sufficiently broad set of probability distributions must be loose—too large
by an additive constant—for some (rather innocuous) probability distribution. Here the“model” in “model-dependent” refers to the output of the learning algorithm, which is an
estimate of the regression function. The bounded-antimonotonic condition formalizes themild requirement that the bound does not degrade very rapidly with additional data. Asidefrom this constraint, our result applies for any bound that is determined as a function of
the output of the learning algorithm, the number of training examples, and the confidence
parameter. This function could depend on the level in a hierarchy of models where theoutput of the algorithm lies. Our result applies whether the bound is obtained by uniform
convergence over a level in the hierarchy, or in some other way.
The intuition behind our result is that benign overfitting can only occur when thetest distribution has a vanishing overlap with the training data. Indeed, interpolating thedata in the training sample guarantees that the conditional expectation of the prediction
rule’s loss on the training points that occur once must be at least twice the noise level.
Using a Poissonization method, we show that a situation where the training sample forms asignificant fraction of the support of the distribution is essentially indistinguishable from abenign overfitting situation where the training sample has measure zero. A data-dependent
bound that is valid in both cases must be loose in the second case.

2. Preliminaries and Main Results
We consider prediction problems with patterns x ∈ `2 and labels y ∈ R, where `2 is the spaceof square summable sequences of real numbers. In fact, all probability distributions that we
consider have support restricted to a finite dimensional subspace of `2 , which we identify
with Rd for an appropriate d. For a joint distribution1 P over Rd × R and a (measurable)
1. Throughout the paper, whenever we refer to a probability distribution over R, it is with respect to theBorel σ-field.

3

Bartlett and Long

hypothesis h : Rd → R, define the risk of h to be
RP (h) = E(x,y)∼P [(y − h(x))2 ].
Let RP∗ be the minimum of RP over measurable functions.
For any positive integer k, a distribution D over Rkis sub-Gaussian with parameter σ if,
2 2
for any u ∈ Rk , Ex∼D [exp(u · (x − Ex))] ≤ exp kuk2 σ . A joint distribution P over Rd × R
has unit scale if (X1 , ..., Xd , Y ) ∼ P is sub-Gaussian with parameter 1. It is innocuous if• it is unit scale,• the marginal on (X1 , ..., Xd ) is Gaussian, and• the conditional of Y given (X1 , ..., Xd ) is continuous.
A sample is a finite multiset of elements of Rd × R. A least-norm interpolation algorithm
takes as input a sample (x1 , y1 ), ..., (xn , yn ), and outputs hθ which maps x to θ · x for θ ∈ Rd
that minimizes kθk subject toX(θ · xi − yi )2 =imin(ŷ1 ,...,ŷn )∈Rn

X(ŷi − yi )2 .

i

We will refer both to the parameter vector θ output by the least-norm interpolation algorithm and the function x → θ · x parameterized by θ as the least-norm interpolant.
A function (h, n, δ) mapping a hypothesis h, a sample size n and a confidence δ toa positive real number is a uniform model-dependent bound for unit-scale distributions if,
for all unit-scale joint distributions P , all sample sizes n, and any least-norm interpolation
algorithm A, with probability at least 1 − δ over the random choice of S ∼ P n ,RP (A(S)) − RP∗ ≤ (A(S), n, δ).
Here h may be any measurable function from Rd to R for any d, and n and δ may be any
positive integer and positive real number. The bound  is c-bounded antimonotonic for c ≥ 1
if for all h, δ, n1 and n2 , if n2 /2 ≤ n1 ≤ n2 then (h, n2 , δ) ≤ c(h, n1 , δ). This formalizes
the requirement that the bound cannot get too much worse too quickly with more data;
doubling the sample size can degrade the bound by at most a factor of c. If (h, ·, δ) ismonotone-decreasing for all h and δ, then it is 1-bounded antimonotonic.
}|≥ β. Say that B ⊆ N is strongly β-dense
A set B ⊆ N is β-dense if liminf N →∞ |B∩{1,...,NN
2
beyond n0 if, for all s ∈ N such that s ≥ n0 ,|B ∩ {s2 , ..., (s + 1)2 − 1}|≥ β.
2s + 1The β-dense notion is standard; it roughly corresponds to the informal idea that at least a
fraction β of the natural numbers are in B. Notice that if a set is strongly β-dense beyond
n0 , then it is β-dense, but also is, in a sense, “locally” β-dense as well.
The following is our main result.
4

Failures of Model-dependent Generalization Bounds

Theorem 1 If  is a bounded-antimonotonic, uniform model-dependent bound for unit-scale
distributions, then there are constants c0 , c1 , c2 , c3 , c4 > 0 and innocuous distributions P1
over Rd1 × R, P2 over Rd2 × R, ... such that for, for any least-norm interpolation algorithm
A, for all 0 < δ < c1 , for all large enough n,√ PrS∼Pnn RPn (A(S)) − RP∗ n ≤ c0 / n ≥ 1 − δ
but nonetheless, the set of n such that
PrS∼Pnn [(A(S), n, δ) > c2 ] ≥12c3)-dense beyond c4 log(1/δ).
is strongly (1 − log(1/δ)

The distributions Pn in the theorem are slight variations on a joint gaussian distribution:
the marginal distribution of x is gaussian with a covariance matrix chosen to satisfy theconditions in (Bartlett et al., 2020) that ensure the benign overfitting property, and theconditional distribution of y given x is a linear function of x plus noise, where the noise isa mixture of mean-zero gaussians with different variances.

3. Proof of Theorem 1
Our proof uses the following lemma (Birch, 1963; Feller, 1968; Batu et al., 2000, 2013),
which has become known as the “Poissonization lemma”. We use Poi(λ) to denote the
Poisson distribution with mean λ: For t ∼ Poi(λ) and k ≥ 0,
Pr[t = k] =λk e−λ.
k!

Lemma 2 If, for t ∼ Poi(n), you throw t balls independently uniformly at random into mbins,• the numbers of balls falling into the bins are mutually independent, and• the number of balls falling in each bin is distributed as Poi(n/m).
For each n, our proof uses three distributions: Dn , Qn and Pn . The first, Dn , is used todefine Qn and Pn ; it is chosen so that the least-norm interpolant performs well on Dn . The
distribution Qn is defined so that the least-norm interpolant performs poorly on Qn . The
distribution Pn is defined so that, when the least-norm interpolant performs well on Dn , italso performs well on Pn . Crucially, the least norm interpolants that arise from Qn and Pn
are closely related.
√
For each n, the joint distribution Dn on (x, y)-pairs is defined as follows. Let s = b nc,
N = s2 , d = N 2 . Let θ∗ be an arbitrary unit-length vector. Let Σs be an arbitrary
covariance matrix with eigenvalues λ1 = 1/81, λ2 = · · · = λd = 1/d2 . The marginal of Dn
1
on x is then N (0, Σs ). For each x ∈ Rd , the distribution of y given x is N θ∗ · x, 81. For
d ≥ 9, since (x, y) is Gaussian, kΣs k ≤ 1/81, and the variance of y is 1/81, each Dn is
innocuous.
For an absolute constant positive integer b, we get Qn from Dn through the following
steps.
5

Bartlett and Long

1. Sample (x1 , y1 ), . . . , (xbn , ybn ) ∼ Dnbn .
2. Define Qn on Rd × R so that its marginal on Rd is uniform on U = {x1 , . . . , xbn } andits conditional distribution of Y |X is the same as Dn .
Definition 3 For a sample S, the compression of S, denoted by C(S), is defined to be
C(S) = ((u1 , v1 ), . . . , (uk , vk )) ,where u1 , . . . , uk are the unique elements of {x1 , . . . , xn }, and, for each i, vi is the averageof {yj : 1 ≤ j ≤ n, xj = ui }.
For the least-norm interpolation algorithm A, for any pair S and S 0 of samples such that
C(S) = C(S 0 ), we have A(S) = A(S 0 ). (This is true because the least-norm interpolant
A(S) is uniquely defined by the equality constraints specified by the compression C(S).)
So that a generalization bound often must apply to Qn , we need to show that it is likely
to be unit scale. The proof of this lemma is in Appendix A.
Lemma 4 There is a positive constant c5 such that, for all large enough n, with probability
at least 1 − cn5 , Qn has unit scale.
We can show that the least-norm interpolant is bad for Qn by only considering thepoints in the support of Qn that the algorithm sees exactly once.
Lemma 5 For any constant c > 0, there are constants c6 , c7 > 0 such that, for all sufficiently large n, almost surely for Qn chosen randomly as described above, if t is chosenrandomly according to Poi(cn) and S consists of t random draws from Qn , then with probability at least 1 − e−c6 n over t and S,E(x,y)∼Qn (A(C(S))(x) − y)2 − E(x,y)∼Qn (f ∗ (X) − Y )2 ≥ c7
where f ∗ is the regression function for Dn (and hence also for Qn ).
Proof Recall that U = {x1 , . . . , xbn } is the support of the marginal of Qn on the independent variables. With probability 1, U has cardinality bn. Define h = A(C(S)). If somex ∈ U appears exactly once in S, then h(x) is a sample from the distribution of y given x
under Dn . Thus, for such an x, the expected quadratic loss of h(x) on a test point is thesquared difference between two independent samples from this distribution. This is twice
the variance of this distribution, that is, twice the expected loss of f ∗ , hence 2/81. On any
x ∈ U , whether or not it was seen exactly once in S, by definition, f ∗ (x) minimizes the
expected loss given x.
Lemma 2 shows that, conditioned on the random choice of Qn , the numbers of times thevarious x in U in S are mutually independent and, the probability that x ∈ U is seen exactly−conce in S is cb exp − cb ≥ ceb . Applying a Chernoff bound (see, for example Mitzenmacherand Upfal, 2005, Theorem 4.5), the probability that fewer than ce−c n/2 members of U
6

Failures of Model-dependent Generalization Bounds

are seen exactly once in S is at most e−c6 n for an absolute constant c6 . Thus if U1 is the(random) subset of points in U that were seen exactly once, we haveQn (h(X) − Y )2 − Qn (f ∗ (X) − Y )2X=
Qn ((h(X) − Y )2 − (f ∗ (X) − Y )2 )1X=x
x∈U

≥

X

E[(f ∗ (X) − Y )2 1X=x ]

x∈U1

=

|U1 |
.
81bn

Since, with probability 1 − e−c6 n , |U1 | ≥ ce−c n/2, this completes the proof.

Definition 6 Define Pn as follows.
1. Set the marginal distribution of Pn on Rd the same as that of Dn .
2. To generate Y given X = x for (X, Y ) ∼ Pn , first sample a random variable Z
whose distribution is obtained by conditioning a draw from a Poisson with mean cb on
the event that it is at least 1, then sampleP
Z values V1 , . . . , VZ from the conditional
1
distribution Dn (Y |X = x), and set Y = Z Z
i=1 Vj .
Note that, since Dn has a density, x1 , ..., xr are almost surely distinct and hence S drawn
from Pnr has C(S) = S a.s.
The following lemma implies that the bounds for Pn tend to be as big as those for Qn .
Lemma 7 Define Qn as above and let Qn be the resulting distribution over the random
choice of Qn . Suppose Pn is defined as in Definition 6. Let c > 0 be an arbitrary constant.
Choose S randomly by choosing t ∼ Poi(cn), Qn ∼ Qn and S ∼ Qtn . Choose T by choosingcr ∼ B bn, 1 − exp − b and T ∼ Pnr . Then C(S) and T have the same distribution. In
particular, for all δ > 0, for any function ψ of the least norm interpolant h, a sample sizer, and a confidence parameter δ, we have
Et∼Poi(cn),Qn ∼Qn [ES∼Qtn [ψ(h(S), |C(S)|, δ)]] = Er∼B (bn,1−exp(− c )) [ET ∼Pnr [ψ(h(T ), r, δ)].
b

Proof Let C be the probability distribution over training sets obtained by picking Qn from
Qn , picking t from Poi(cn), picking S from Qtn and compressing it. Let C = C(S) be arandom draw from C. Let nC be the number of examples in C.
c
We claim that nC is distributed as B bn, 1 − exp − b . Conditioned on Qn , andrecalling that U is the support of Qn , for any x ∈ U , Lemma 2 implies that for each x ∈ U ,cthe probability that x is not seen is the probability, under a Poisson with mean b , of drawingca 0. Thus, the probability that x is seen is 1−exp − b . Since the numbers of times differentx are seen in S are independent, the number seen is distributed as B bn, 1 − exp − cb .
Now, for each x ∈ U , the event that it is in C(S) is the same as the event that at appears
at least once in S. Thus, conditioned on the event that x appears in S, the number of y7

Bartlett and Long

values that are used to compute the y value in C(S) is distributed as a Poisson with meancb , conditioned on having a value at least 1.
Let Dn,X be the marginal distribution of Dn on the x’s. If we make n independentdraws from Dn,X , and then independently reject some of these examples, to get nC draws,
the resulting nC examples are independent. (We could first randomly decide the number
nC of examples to keep, and then draw those independently from Dn , and we would havethe same distribution.)
The last two paragraphs together, along with the definition of Qn , imply that the distribution over T obtained by sampling r from B(bn, 1 − e−c/b ) and T from Pnr is the same as
the distribution over C obtained by sampling Qn from Qn , t from Poi(cn), then sampling S
from Qtn and compressing it. Thus, the distributions of T and C(S) are the same, and hence
the distributions of (h(T ), |T |) and (h(S), |C(S)|) are the same, because h(S) = h(C(S)).

We will use the following bound on a tail of the Poisson distribution, due to Canonne(2017).

α2Lemma 8 For any λ, α > 0, Prr∼Poi(λ) (r ≥ (1 + α)λ) ≤ exp − 2(1+α)λ .
Armed with these tools, we now show that  must often have a large value.
Lemma 9 Then there are positive constants c1 , c2 , c3 , c4 such that, for all 0 < δ < c1 , theset of n such that
1
PrS∼Pnn [(h, n, δ) > c2 ] ≥2
c3
is strongly (1 − log(1/δ))-dense beyond c4 log(1/δ).
Proof We will think of the natural numbers as being divided into bins [1, 2), [2, 4), [4, 7), ...
Let us focus our attention on one bin: {s2 , ..., (s + 1)2 − 1}. Let n denote the center of the√bin, n = s2 + s, so that s ∼ n.
For a constant c8 > 0 and any δ > 0, Lemma 7 implies
Er∼B(bn,1−e−c/b ) [PrT ∼Pnr [(h(T ), r, δ) ≤ c8 ]] = Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [(h(S), |C(S)|, δ) ≤ c8 ]].
(1)
Suppose that  is B 0 -bounded-antimonotonic. Fix B > 0 such that B > B 0 . Then
Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [(h, |C(S)|, δ) ≤ c8 ]]= Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [B(h, |C(S)|, δ) ≤ c8 B]]∗> B(h, |C(S)|, δ)]]≤ Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [RQn (h) − RQn∗≤ c8 B]].
+ Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [RQn (h) − RQnFor each sample size t and any Qn that has unit scale∗
PrS∼Qtn [RQn (h) − RQ
> B(h, |C(S)|, δ)]n∗≤ PrS∼Qtn RQn (h) − RQ
> (h, t, δ) + PrS∼Qtn [B(h, |C(S)|, δ) ≤ (h, t, δ)]n≤ δ + PrS∼Qtn [|C(S)| < t/2]
8(2)

Failures of Model-dependent Generalization Bounds

where the second inequality follows from the fact that  is a valid B 0 -bounded-antimonotonic
uniform model-dependent bound for unit-scale distributions and B > B 0 . Combining thiswith Lemma 4, we have∗
> B(h, |C(S)|, δ)]] ≤ δ+
Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [RQn (h)−RQnc5+PrS∼Qtn [|C(S)| < t/2].
n

Now by a union bound, for some constant c9 > 0,
Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [|C(S)| < t/2]]≤ Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [|C(S)| < c9 n]] + Prt∼Poi(cn) [t/2 ≥ c9 n]= PrZ∼B(bn,1−e−c/b ) [Z < c9 n] + Prt∼Poi(cn) [t/2 ≥ c9 n]
≤ δ,

(3)

where the last inequality follows from a Chernoff bound and from Lemma 8 with α =1 − 2c9 /c, provided n = Ω(log(1/δ)) and provided we can choose c9 to satisfy c/2 < c9 <b(1 − e−c/b ). Our choice of b and c, specified below, will ensure this. In that case, we have
that
Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [(h, |C(S)|, δ) ≤ c8 ]]c5∗≤ 2δ ++ Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [RQn (h) − RQ
≤ c8 B]].
nn
Applying Lemma 5 to bound the RHS, if n is large enough and c8 B < c7 , then
Et∼Poi(cn),Qn ∼Qn [PrS∼Qtn [(h, |C(S)|, δ) ≤ c8 ]] ≤ 3δ +c5.
nReturning to (1), we get
Er∼B(bn,1−e−c/b ) [PrT ∼Pnr [(h, r, δ)) ≤ c8 ]] ≤ 3δ +

c5
.
n

(4)

Let us now focus on the case that b = 2 and c = 2 ln 2, so that
Er∼B(bn,1−e−c/b ) [r] = (1 − e−c/b )bn = n.
(And note that c/2 = ln 2 < 1 = b(1 − e−c/b ), as required for (3).) Chebyshev’s inequality
implies
Prr∼B(bn,1−e−c/b ) [r 6∈ [n − s, n + s]] ≤ c10
for an absolute positive constant c10 . Returning now to (4), Markov’s inequality implies

1r
Prr∼B(bn,1−e−c/b ) [PrT ∼Pn [(h, r, δ)) ≤ c8 ] > 1/2] ≤ c11 δ +.
(5)nFurther, it is known (Slud, 1977; Box et al., 1978) that there is an absolute constant c12
such that, for all large enough n and all r0 ∈ [n − s, n + s],
c12
Prr∼B(bn,1−e−c/b ) [r = r0 ] ≥ √ .
n9Bartlett and Long√
Combining this with (5) and recalling that s and s0 are Θ( n), we get|{r ∈ [n − s, n + s] : PrT ∼Pnr [(h, r, δ)) ≤ c8 ] > 1/2}|
1
c14≤≤ c13 δ +,2s + 1nlog(1/δ)for n ≥ c4 log(1/δ) and small enough δ. Since, for all r ∈ [n − s, n + s], we have Pr = Pn ,this completes the proof.
The following bound can be obtained through direction application of the results ofBartlett et al. (2020). The details are given in Appendix B.
Lemma 10 There is a constant c such that, for all large enough n, with probability
at leastq
1 − δ, for S ∼ Pnn , the least-norm interpolant h satisfies RPn (h) − RP∗ n ≤ clog(1/δ).
n

Combining this with Lemma 9 proves Theorem 1.

4. Conclusion
We have shown that valid bounds that depend only on the output of the learning algorithm
must be too loose to establish benign overfitting of linear regressors in the sense of Bartlett
et al. (2020); Tsigler and Bartlett (2020); additional information, such as properties of thecovariance, is necessary.
There are several interesting directions for further work. The construction presented
in this paper uses a different probability distribution for each sample size. It is not clear
whether this is necessary. It seems likely that a wider variety of generalization bounds thanthe class analyzed in this paper must sometimes be loose. Our theoretical understanding of
benign overfitting in the context of deep learning, where it was originally observed, is muchless developed than in the linear regression setting considered here.

Acknowledgments
We thank Andrea Montanari for alerting us to a flaw in an earlier version of this paper, andthe JMLR reviewers for their helpful comments and suggestions. We also thank Vaishnavh
Nagarajan and Zico Kolter for helpful comments on an earlier draft of this paper, and Dan
Roy for calling our attention to (Negrea et al., 2020, Lemma 5.2).

Appendix A. Proof of Lemma 4
To prove Lemma 4, we will need some lemmas. The first is due to Buldygin and Kozachenko(1980) (see Rivasplata, 2012).
Lemma 11 If X1 is a sub-Gaussian random variable with parameter σ1 , and X2 is a (notnecessarily independent) sub-Gaussian random variable with parameter σ2 , then X1 + X2 is
sub-Gaussian with parameter σ1 + σ2 .
This immediately implies the following.
10

Failures of Model-dependent Generalization Bounds

Lemma 12 If X1 is a sub-Gaussian random vector with parameter σ1 , and X2 is a (notnecessarily independent) sub-Gaussian random vector with parameter σ2 , then X1 + X2 is
sub-Gaussian with parameter σ1 + σ2 .
Proof Any projection of X1 + X2 is the sum of the projections of X1 and X2 , so thisfollows from Lemma 11.

Lemma 13 For a random vector X = (X1 , ..., Xk ), if X1 is sub-Gaussian with parameter 1/3, X2 is sub-Gaussian with parameter 1/3, and (X3 , ..., Xk ) is sub-Gaussian withparameter 1/3, then X is sub-Gaussian with parameter 1.
Proof Embedding a random vector into a higher-dimensional space by adding componentsthat always evaluate to zero does not affect whether it is sub-Gaussian, or its sub-Gaussian
parameter. Since
X = (X1 , 0, ..., 0) + (0, X2 , 0, ..., 0) + (0, 0, X3 , ..., Xk ),applying Lemma 12 above completes the proof.
Now, for U ∼ Dnm , the uniform distribution Q over U , and (X1 , ..., Xd , Y ) ∼ Q, we now
would like to show that X1 is sub-Gaussian with parameter 1/3. We will use the following
known sufficient condition, which can be recovered by tracing through the constants in the
proof of (Vershynin, 2018, Proposition 2.5.2).
hi2
Lemma 14 If a random variable X satisfies E exp 18X≤ 2, then X is sub-Gaussianewith parameter 1/3.
Now we are ready to analyze the marginal distribution of the first component.
Lemma 15 For U obtained from m independent samples from N (0, σ 2 ) for σ ≤ 1/9 if Q
3is the uniform distribution over U , then, with probability at least 1 − m, Q is sub-Gaussianwith parameter 1/3.
Proof Define a = 18/e and let Z = Ex∼Q [exp(ax2 )].
We have
ES∼N (0,σ)m [Z] = ES∼N (0,σ)m [Ex∼Q [exp(ax2 )]]= Ex∼N (0,σ) [exp(ax2 )]


Z ∞
1
x2
ax2
=√
e exp − 2 dx
2σ2πσ −∞
 
 
Z ∞
1
1
=√
exp −
− a x2 dx
2σ 22πσ −∞
√
1
π
=√
×q
1
2πσ
−a
2σ 2
=√

1
.
1 − 2aσ 2

11Bartlett and Long

Similarly
VarS [Z] = VarS [Ex∼Q [exp(ax2 )]]1= Varx∼N (0,σ) [exp(ax2 )]m1≤ Ex∼N (0,σ) [exp(2ax2 )]
m
1
= √
.
m 1 − 4aσ 2
By Chebyshev’s inequality,
Pr Z ≥ √


3
1
1
≤ .
+√
1/4
2
2
m
3(1 − 4aσ )1 − 2aσ3
and applying Lemma 14
For σ ≤ 1/9, recalling that a = 18/e shows that Pr [Z ≥ 2] ≤ mcompletes the proof.

Armed with these lemmas, we are now ready to prove Lemma 4. For S ∼ Dnm , let Q
be the uniform distribution over S. For (X1 , ..., Xd , Y ) ∼ Q, Lemma 15 implies that, withprobability 1 − 6/m, X1 and Y are both sub-Gaussian with parameter 1/3. It remains toanalyze (X2 , ..., Xd ). Let S 0 be the projections of the elements of S onto
√ these coordinates.
With probability at least 1 − 3/m, for all s0 ∈ S 0 , ||s0 || ≤ log(em2 /3)/ d; see (Lovász andVempala, 2007, Lemma 5.17). Recalling that d = Θ(n2 ), if m = bn, then, for all large
enough n, with probability 1 − 3/m, maxs0 ∈S 0 ||s|| ≤ 1/6, which implies that (X2 , ..., Xd )is sub-Gaussian with parameter 1/3. Putting this together with the analysis of X1 and Y ,and applying Lemma 13, completes the proof.

Appendix B. Proof of Lemma 10
The lemma follows from (Bartlett et al., 2020, Theorem 1); before showing how to apply it,
let us first restate a special case of the theorem for easy reference.
B.1 A useful upper boundThe special case concerns the least-norm interpolant applied to training data (x1 , y1 ), ..., (xn , yn )drawn from a joint distribution P over (x, y) pairs. The marginal distribution of x is Gaussian with covariance Σ. There is a unit length θ∗ such that, for all x, the conditional
distribution of y given x has mean θ∗ · x is sub-gaussian with parameter 1 and variance at
most 1.
We will apply an upper bound in terms of the eigenvalues λ1 ≥ λ2 ≥ ... of Σ. The boundis in terms of two notions of the effective rank of the tail of this spectrum:
2PPi>k λii>k λirk (Σ) =, Rk (Σ) = P
2 .
λk+1
i>k λiThe rank of Σ is assumed to be greater than n.
12Failures of Model-dependent Generalization Bounds

Lemma 16 () There are b, c, c1 > 1 for which the following holds. For all n, P andΣ defined as above, write k ∗ = min{k ≥ 0 : rk (Σ) ≥ bn}. Suppose that δ < 1 withlog(1/δ) < n/c. If k ∗ < n/c1 , then, with probability at least 1 − δ, the least-norm interpolant
h satisfies
(r
)
r
 ∗
!
r0 (Σ) r0 (Σ) log(1/δ)
kn∗
RP (h) − RP ≤ c max+ log(1/δ)
.
.
.
+
n
n
n
n
Rk∗ (Σ)Lemma 16 was sharpened and generalized by Tsigler and Bartlett (2020). Both Bartlett
et al. (2020) and Tsigler and Bartlett (2020) provide examples of concrete instantiations of
their bounds.
B.2 The proof
To prove Lemma 10, we need to show that Pn satisfies the requirements on P in Lemma 16,
and evaluate the effective ranks rk and Rk of Pn ’s covariance Σs . Define α = 1/d2 . We
have
1/81 + (d − 1)αr0 == 1 + 81(d − 1)α1/81(which is bounded by a constant) andR0 =(1/81 + (d − 1)α)2.
1/812 + (d − 1)α2

For k > 0,
rk = Rk = d − k.
Since d grows faster than n, for large enough n, k ∗ := min {k : rk ≥ bn} = 1. So
Rk∗ = d − 1 = Ω(n2 ).
Each sample from the distribution of Y given X = x has a mean of θ∗ · x, and is subGaussian with parameter at most 19 , and with variance at most 1/81 (because increasing Z
only decreases the variance of Y ).
Evaluating Lemma 16 on Pn then gives Lemma 10.

References
S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization andgeneralization for overparameterized two-layer neural networks. In ICML, volume 97,
pages 322–332, 2019.
P. L. Bartlett. The sample complexity of pattern classification with neural networks: thesize of the weights is more important than the size of the network. IEEE Transactions
on Information Theory, 44(2):525–536, 1998.
P. L. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds andstructural results. Journal of Machine Learning Research, 3:463–482, 2002.
13

Bartlett and Long

P. L. Bartlett, S. Boucheron, and G. Lugosi. Model selection and error estimation. Machine
Learning, 48(1-3):85–113, 2002.
P. L. Bartlett, D. Foster, and M. Telgarsky. Spectrally-normalized margin bounds for neuralnetworks. In NIPS, pages 6240–6249, 2017.
P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linear regression.
PNAS, 2020.
T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions
are close. In Proceedings 41st Annual Symposium on Foundations of Computer Science,
pages 259–269. IEEE, 2000.
T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing closeness of
discrete distributions. J. ACM, 60(1):4:1–4:25, 2013. doi: 10.1145/2432622.2432626.
URL https://doi.org/10.1145/2432622.2432626.
M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practiceand the classical biasvariance trade-off. PNAS, 116(32):15849–15854, 2019a.
M. Belkin, A. Rakhlin, and A. B. Tsybakov. Does data interpolation contradict statisticaloptimality? AISTATS, pages 1611–1619, 2019b.
MW Birch. Maximum likelihood in three-way contingency tables. Journal of the Royal
Statistical Society: Series B (Methodological), 25(1):220–233, 1963.
GEP Box, WH Hunter, S Hunter, et al. Statistics for experimenters, volume 664. John
Wiley and sons New York, 1978.
V. V. Buldygin and Y. V. Kozachenko. Sub-gaussian random variables. Ukrainian Mathematical Journal, 32(6):483–489, 1980.
C. L. Canonne. A short note on Poisson tail bounds, 2017.
Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide anddeep neural networks. In Advances in Neural Information Processing Systems, pages
10835–10845, 2019.
M. Derezinski, F. T. Liang, and M. W. Mahoney. Exact expressions for double descent andimplicit regularization via surrogate random design. In NeurIPS, 2020.
V. Feldman. Does learning require memorization? a short tale about a long tail. In
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,pages 954–959, 2020.
W. Feller. An introduction to probability theory and its applications, volume 1. John Wiley& Sons, 1968.
N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neuralnetworks. In COLT, volume 75, pages 297–299, 2018.
14

Failures of Model-dependent Generalization Bounds

T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensionalridgeless least squares interpolation. arXiv preprint arXiv:1903.08560, 2019a.
T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensionalridgeless least squares interpolation. Technical Report 1903.08560 [math.ST], arXiv,
2019b. URL https://arxiv.org/abs/1903.08560.
D. Haussler. Decision theoretic generalizations of the PAC model for neural net and otherlearning applications. Information and Computation, 100(1):78–150, 1992.
Y. Li and Y. Liang. Learning overparameterized neural networks via stochastic gradientdescent on structured data. In NeurIPS, pages 8157–8166. 2018.
Z. Li, W. Su, and D. Sejdinovic. Benign overfitting and noisy features. arXiv preprint
arXiv:2008.02901, 2020.
T. Liang and A. Rakhlin. Just interpolate: Kernel “Ridgeless” regression can generalize.
The Annals of Statistics, 48(3):1329–1347, 2020.
P. M. Long and H. Sedghi. Generalization bounds for deep convolutional neural networks.
ICLR, 2019.
L. Lovász and S. S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Struct. Algorithms, 30(3):307–358, 2007.
M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms andProbabilistic Analysis. Cambridge University Press, 2005.
V. Nagarajan and J. Z. Kolter. Uniform convergence may be unable to explain generalizationin deep learning. In NeurIPS, pages 11611–11622, 2019.
J. Negrea, G. K. Dziugaite, and D. M. Roy. In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors. ICML,
2020.
B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks.
In COLT, pages 1376–1401, 2015.
O. Rivasplata.
Subgaussian random variables: An expository note.
https://
sites.ualberta.ca/~omarr/publications/subgaussians.pdf, 2012.
Downloaded
1/12/2021.
E. V. Slud. Distribution inequalities for the binomial law. The Annals of Probability, pages
404–412, 1977.
A. Tsigler and P. L. Bartlett.
2009.14286.

Benign overfitting in ridge regression, 2020.

ArXiv,

R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning
requires rethinking generalization. In ICLR, 2017.
15