Benign Overfitting in Linear Regression
Peter L. Bartlett Philip M. Long Gábor Lugosi Alexander Tsigler







a,b]Peter L. Bartlett
c]Philip M. Long
d]Gábor Lugosi
a]Alexander Tsigler

[a]Department of Statistics, UC Berkeley, 367 Evans Hall,
Berkeley CA 94720-3860
[b]Computer Science Division, UC Berkeley, 387 Soda Hall,
Berkeley CA 94720-1776
[c]Google
[d]Economics and Business,
Pompeu Fabra University;
ICREA, Pg. Lluís Companys 23, 08010 Barcelona, Spain;
Barcelona Graduate School of Economics






Benign Overfitting in Linear Regression
    [
    
=======================================




The phenomenon of benign overfitting is one of the key
mysteries uncovered by deep learning methodology: deep
neural networks seem to predict well, even with a perfect
fit to noisy training data. Motivated by this phenomenon,
we consider when a perfect fit to training data in
linear regression is compatible with accurate prediction.
We give a characterization of linear regression
problems for which the minimum norm interpolating prediction rule
has near-optimal prediction accuracy. The characterization is in
terms of two notions of the effective rank of the data covariance.
It shows that overparameterization is essential for
benign overfitting in this setting: the number of directions
in parameter space 
that are unimportant for prediction must
significantly exceed the sample size.  By studying examples of data
covariance properties that this characterization shows are required
for benign overfitting, we find an important role for
finite-dimensional data: the accuracy of the minimum norm
interpolating prediction rule approaches the best possible accuracy
for a much narrower range of properties of the data distribution
when the data lies in an infinite dimensional space versus when the
data lies in a finite dimensional space whose dimension grows faster
than the sample size.









§ INTRODUCTION

Deep
learning methodology has revealed a surprising statistical
phenomenon: overfitting can perform well.
The classical perspective in statistical learning theory is that
there should be a tradeoff between the fit to the training data
and the complexity of the prediction rule. Whether complexity
is measured in terms of the number of parameters, the number of
non-zero parameters in a high-dimensional setting, the number of
neighbors averaged in a nearest-neighbor estimator, the scale of an
estimate in a reproducing kernel Hilbert space, or the bandwidth of
a kernel smoother, this tradeoff has been ubiquitous
in statistical learning theory.  Deep learning
seems to operate outside the regime where results of this kind are
informative, since deep neural networks can perform well even with
a perfect fit to the training data.

As one example of this phenomenon, consider the experiment
illustrated in Figure 1(c) in <cit.>: standard deep
network architectures and stochastic gradient algorithms, run until
they perfectly fit a standard image classification training set,
give respectable prediction performance, even when significant
levels of label noise are introduced.  The deep networks in the
experiments reported in <cit.> achieved essentially
zero cross-entropy loss on the training data.  In statistics
and machine learning textbooks, an estimate that fits every
training example perfectly is often presented as an illustration
of overfitting (“... interpolating fits... [are] unlikely to
predict future data well at all.” <cit.>). Thus,
to arrive at a scientific understanding of the success of deep
learning methods, it is a central challenge to understand the
performance of prediction rules that fit the training data perfectly.

In this paper, we consider perhaps the simplest setting where we
might hope to witness this phenomenon: linear regression.
That is, we consider quadratic loss and linear prediction rules, and
we assume that the dimension of the parameter space is large enough
that a perfect fit is guaranteed. We consider data in an infinite
dimensional space (a separable Hilbert space), but our results
apply to a finite-dimensional subspace as a special case. There
is an ideal value of the parameters, θ^*, corresponding to
the linear prediction rule that minimizes the expected quadratic loss.
We ask when it is possible to fit the data exactly
and still compete with the prediction accuracy of θ^*.
Since we require more parameters than the sample size in order to
fit exactly, the solution might be underdetermined, so there might
be many interpolating solutions. We consider the most natural: 
choose the parameter vector θ̂ with the smallest norm
among all vectors that give perfect predictions on the training
sample. (This corresponds to using the pseudoinverse to solve
the normal equations; see Section <ref>.)
We ask when it is possible to overfit in this
way—and embed all of the noise of the labels into the parameter
estimate θ̂—without harming prediction accuracy.

Our main result is a finite sample characterization of when
overfitting is benign in this setting. The linear regression
problem depends on the optimal parameters θ^* and the
covariance Σ of the covariates x. The properties of Σ
turn out to be crucial, since the magnitude of the variance in
different directions determines both how the label noise gets
distributed across the parameter space and how errors in
parameter estimation in different directions in parameter space
affect prediction accuracy. There is a classical decomposition of
the excess prediction error into two terms. The
first is rather standard: provided that the scale of the problem
(that is, the sum of the eigenvalues of Σ) is small compared
to the sample size n, the contribution to θ̂ that we can
view as coming from θ^* is not too distorted. The second
term is more interesting, since it reflects the impact of the noise
in the labels on prediction accuracy.
We show that this part is small if and only if the
effective rank of Σ in the subspace corresponding to low
variance directions is large compared to n.  This necessary
and sufficient condition of a large effective rank can be viewed
as a property of significant overparameterization: fitting the
training data exactly but with near-optimal prediction accuracy
occurs if and only if there are many low variance (and hence
unimportant) directions in parameter space where the label
noise can be hidden.

The details are more complicated. The characterization
depends in a specific way on two notions of effective rank,
r and R; the smaller one, r, determines a split of Σ
into large and small eigenvalues, and the excess prediction error
depends on the effective rank, as measured by the larger notion R, of
the subspace corresponding to the smallest eigenvalues. For the excess
prediction error to be small, the smallest eigenvalues of Σ
must decay slowly.

Studying the patterns of eigenvalues that allow benign overfitting
reveals an interesting role for large but finite dimensions: in an
infinite-dimensional setting, benign overfitting occurs only for a
narrow range of decay rates of the eigenvalues. On the other
hand, it occurs with any suitably slowly decaying eigenvalue sequence
in a finite dimensional space whose dimension grows
faster than the sample size. Thus, for linear regression,
data that lies in a large but finite dimensional space exhibits the
benign overfitting phenomenon with a much wider range of covariance
properties than data that lies in an infinite dimensional space.

The phenomenon of interpolating prediction rules has been an
object of study by several authors over the last two years, since
it emerged as an intriguing mystery at the Simons Institute program
on Foundations of Machine Learning in Spring 2017.  Belkin, Ma and
Mandal <cit.> 
described an experimental study
demonstrating that this phenomenon of accurate prediction for
functions that interpolate noisy data also occurs for prediction
rules chosen from reproducing kernel Hilbert spaces, and explained
the mismatch between this phenomenon and classical generalization
bounds.  Belkin, Hsu and Mitra <cit.> gave
an example of an interpolating decision rule—simplicial
interpolation—with an asymptotic consistency property as the input dimension
gets large. That work, and subsequent work of Belkin, Rakhlin, and
Tsybakov <cit.>, studied
kernel smoothing methods based on singular kernels that
both interpolate and, with suitable bandwidth choice, give optimal
rates for nonparametric estimation (building on earlier consistency
results <cit.> for these unusual kernels).  Liang and
Rakhlin <cit.> considered minimum norm interpolating
kernel regression with kernels defined as nonlinear functions of the
Euclidean inner product and showed that, with certain properties
of the training sample (expressed in terms of the empirical kernel
matrix), these methods can have good prediction accuracy.
Belkin, Hsu, Ma and Mandal <cit.> studied
experimentally the excess risk as a function of the dimension of a
sequence of parameter spaces for linear and non-linear classes.

Subsequent
to our work, <cit.> considered the properties of the
interpolating linear prediction rule with minimal expected squared
error. After this work was presented at the NAS Colloquium on
the Science of Deep Learning <cit.>, we became
aware of the concurrent work of Belkin, Hsu and
Xu <cit.> and of Hastie, Montanari, Rosset and
Tibshirani <cit.>.
Belkin et al <cit.> calculated the excess risk for
certain linear models (a regression problem with identity covariance,
sparse optimal parameters, both with and without noise, and a
problem with random Fourier features with no noise), and
Hastie et al considered linear regression
in an asymptotic regime, where sample size n and input dimension
p go to infinity together with asymptotic ratio p/n→γ.
They assumed that, as p gets large, the empirical spectral distribution
of Σ (the discrete measure on its set of eigenvalues)
converges to a fixed measure, and they applied random matrix theory
to explore the range of behaviors of the asymptotics of the
excess prediction error as γ, the noise variance, and the
eigenvalue distribution vary. They also studied the asymptotics of a
model involving random nonlinear features.  In contrast,
we give upper and lower bounds on the excess prediction error
for arbitrary finite sample size, for arbitrary covariance matrices,
and for data of arbitrary dimension.

The next section introduces notation and definitions used
throughout the paper, including definitions of the problem of
linear regression and of various notions
of effective rank of the covariance operator.
Section <ref> gives the characterization of benign
overfitting, illustrates why the effective rank condition
corresponds to significant overparameterization, and presents several
examples of patterns of eigenvalues that allow benign overfitting,
suggesting that slowly decaying covariance eigenvalues
in input spaces of growing but finite dimension are the generic
example of benign overfitting.
Section <ref> discusses the connections between these
results and the benign overfitting phenomenon in deep neural networks.
Section <ref> outlines the proofs of the results.



§ DEFINITIONS AND NOTATION


We consider linear regression problems, where a linear function of
covariates x from a (potentially infinite dimensional) Hilbert
space  is used to predict a real-valued response variable y.
We use vector notation, so that x^⊤θ denotes the inner
product between x and θ
and xz^⊤ denotes the tensor product of x,z∈.


  A linear regression problem in a separable Hilbert space 
  is defined by a random covariate vector x∈ and outcome
  y∈. We define
    
      
  * the covariance operator Σ=[x x^⊤],
      and
      
  * the optimal parameter vector
      θ^*∈, satisfying
      (y-x^⊤θ^*)^2=min_θ(y-x^⊤θ)^2.
    
   We assume
   
   	
  * 
    x and y are mean zero;
    
  * 
    x = VΛ^1/2 z, where Σ=VΛ V^⊤
    is the spectral decomposition of Σ and z has components
    that are independent σ_x^2-subgaussian with σ_x a
    positive constant; that is, for all λ∈, 
      
    [exp(λ^⊤ z)] ≤exp(σ_x^2λ^2/2),

   	where · is the norm in the Hilbert space ;
   	
  * 
    the conditional noise variance is bounded below by some constant σ^2,
   	
    [(y-x^⊤θ^*)^2|x] ≥σ^2;

   	
  * 
    y - x^⊤θ^∗ is σ_y^2-subgaussian, conditionally on x, that is for all λ∈
   	
    [exp(λ(y - x^⊤θ^∗))|x] ≤exp(σ_y^2λ^2/2)

   	(note that this implies [y|x] = x^⊤θ^*);
    
  * 
  almost surely, the projection of the
  data X on the space orthogonal to any eigenvector of Σ
  spans a space of dimension n.
   	
  Given a training sample (x_1,y_1),…,(x_n,y_n)
  of n i.i.d. pairs with the same distribution as (x,y),
  an estimator returns a parameter estimate θ∈.
  The excess risk of the estimator is defined as
    
    R(θ):=
            _x,y[
            (y-x^⊤θ)^2
            - (y-x^⊤θ^*)^2],

  where _x,y denotes the conditional expectation given
  all random quantities other than x,y (in this case, given the
  estimate θ).
  Define the vectors y∈^n with entries y_i and
  ∈^n with entries _i=y_i-
  x_i^⊤θ^*.  We use infinite matrix notation: X
  denotes the linear map from  to ^n corresponding to
  x_1,…,x_n∈, so that Xθ∈^n has ith component
  x_i^⊤θ. We use similar notation for the
  linear map X^⊤ from ^n to .

Notice that Assumptions <ref>
to <ref> are satisfied when x and y are
jointly gaussian with zero mean and (Σ)>n.

We shall be concerned with situations where an estimator θ
can fit the data perfectly, that is, Xθ=y.
Typically this implies that there are many such vectors. We consider the
interpolating estimator with minimal norm in .
We use · to denote both the
Euclidean norm of a vector in ^n and the Hilbert space norm.


  Given data X∈^n and y∈^n,
  the minimum norm estimator θ̂ solves the optimization problem
    
    min_θ∈       θ^2 
    such that        Xθ-y^2
            = min_βXβ-y^2.


By the projection theorem, parameter vectors that solve the least squares
problem min_βXβ-y^2 solve the normal
equations, so we can equivalently write θ̂ as the minimum norm
solution to the normal equations,
  
    θ̂    =min_θ{θ^2:
            X^⊤ Xθ = X^⊤y}
        = (X^⊤ X)^† X^⊤y
        = X^⊤(XX^⊤)^†y,

where (X^⊤ X)^† denotes the pseudoinverse of the
bounded linear operator X^⊤ X (for infinite dimensional ,
the existence of the pseudoinverse is guaranteed because X^⊤ X is
bounded and has a closed range; see <cit.>). When  has dimension p with p<n and X has rank p, there is a unique
solution to the normal equations. 
On the contrary,
Assumption <ref> in Definition <ref>
implies that we can find many solutions θ∈ to the normal
equations that achieve Xθ=y.  
The minimum norm solution is given by
  
    θ̂    = X^⊤(XX^⊤)^-1y.


Our main result gives tight bounds on the excess risk of this minimum
norm estimator in terms of certain notions of effective rank of the
covariance that are defined in terms of its eigenvalues.

We use μ_1(Σ)≥μ_2(Σ)≥⋯ to denote the
eigenvalues of Σ in descending order, and we denote the
operator norm of Σ by Σ. We use I to denote
the identity operator on  and I_n to denote the n× n
identity matrix.


For the covariance operator Σ,
define λ_i=μ_i(Σ) for i=1,2,….
If ∑_i=1^∞λ_i<∞ and λ_k+1>0
for k≥ 0, define
  
    r_k(Σ)     = ∑_i>kλ_i/λ_k+1,    
        R_k(Σ)     = (∑_i>kλ_i)^2/∑_i>kλ_i^2.





§ MAIN RESULTS


The following theorem establishes nearly matching upper and lower
bounds for the risk of the minimum-norm interpolating estimator.


 For any σ_x there are  b,c, c_1>1 for which the following
 holds. Consider a linear regression problem from
 Definition <ref>. Define
   
    k^* = min{k≥ 0: r_k(Σ)≥ bn},

 where the minimum of the empty set is defined as ∞.
 Suppose δ<1 with log(1/δ)<n/c.
 If k^* ≥ n/c_1, then
 R(θ̂)≥σ^2/c.
 Otherwise,
   
    R(θ̂)
              ≤ c(
             θ^∗^2Σmax{√(r_0(Σ)/n),
             r_0(Σ)/n, √(log(1/δ)/n)}) 
    
    
              + clog(1/δ)σ^2_y(k^*/n
             + n/R_k^*(Σ))

 with probability at least 1-δ, and
   
    R(θ̂)≥σ^2/c(k^*/n + n/R_k^*(Σ)).


Moreover, there are universal constants a_1,a_2,n_0
such that
for all n ≥ n_0, for all Σ, 
for all t ≥ 0, there is
a θ^* with 
θ^*  = t such that for x∼ N(0,Σ) and
y|x∼ N(x^⊤θ^*,θ^* ^2 Σ), with probability at least 1/4,
  
    R(θ̂)
             ≥1/a_1θ^∗^2Σ[r_0(Σ)/n
            log(1+r_0(Σ))≥ a_2].





 §.§ Effective Ranks and Overparameterization


In order to understand the implications of Theorem <ref>, 
we now study relationships between the two notions of effective rank,
r_k and R_k, and establish sufficient and necessary conditions for
the sequence {λ_i} of eigenvalues to lead to small excess risk.

The following lemma shows that the two notions of effective rank are closely
related. See Appendix <ref> for its proof, and for
other properties of r_k and R_k.  (All appendices may be found in 
the supporting material.)


  r_k(Σ)≥ 1, r^2_k(Σ)=r_k(Σ^2)R_k(Σ), and
    
    r_k(Σ^2) ≤ r_k(Σ) ≤ R_k(Σ) ≤ r_k^2(Σ).



Notice that r_0(I_p)=R_0(I_p)=p. More generally, if all the non-zero
eigenvalues of Σ are identical, then
r_0(Σ)=R_0(Σ)=(Σ).
For Σ with finite rank, we can express both r_0(Σ)
and R_0(Σ) as a product of the rank and a notion of symmetry.
In particular, for (Σ)=p we can write
  
    r_0(Σ)    = (Σ) s(Σ),    
        R_0(Σ)    = (Σ) S(Σ), 
    with  
        s(Σ)    = 1/p∑_i=1^pλ_i/λ_1,    
        S(Σ)    = (1/p∑_i=1^pλ_i)^2/1/p∑_i=1^pλ_i^2.

Both notions of symmetry s and S lie between 1/p (when
λ_2→ 0) and 1 (when the λ_i are all equal).

Theorem <ref> shows that, for the minimum norm estimator
to have near-optimal prediction accuracy, r_0(Σ) should be
small compared to the sample size n (from the first term) and
r_k^*(Σ) and R_k^*(Σ) should be large compared to
n. Together, these conditions imply that overparameterization is
essential for benign overfitting in this setting: the number of
non-zero eigenvalues should be large compared to n, they should
have a small sum
compared to n, and there should be many eigenvalues no larger
than λ_k^*.  If the number of these small eigenvalues
is not much larger than n, then they should be roughly equal,
but they can be more assymmetric if there are many more of them.

The following theorem shows that the kind of overparameterization that
is essential for benign overfitting requires Σ to have a heavy
tail. (The proof—and some other examples illustrating the boundary of
benign overfitting—are in Appendix <ref>.) In
particular, if we fix Σ in an infinite-dimensional Hilbert
space and ask when does the excess risk of the minimum norm estimator
approach zero as n→∞, it imposes tight restrictions on the
eigenvalues of Σ.  But there are many other possibilities for
these asymptotics if Σ can change with n.
Since rescaling X affects the accuracy of the least-norm
interpolant in an obvious
way, we may assume without loss of generality that
Σ = 1.  If we restrict our attention to
this case, then, informally, 
Theorem <ref> implies that,
when the covariance operator for data with n examples
is Σ_n,
the least-norm interpolant converges if r_0(Σ_n)/n→ 0,
k_n^*/n→ 0, 
and n/R_k_n^*(Σ_n)→ 0,
and only if 
r_0(Σ_n)/n log (1 + r_0(Σ_n))→ 0,
k_n^*/n→ 0, 
and n/R_k_n^*(Σ_n)→ 0,
where k^*_n= min{k≥ 0: r_k(Σ_n)≥ bn} for the
universal constant b in Theorem <ref>.
For this reason, we say that a sequence of covariance operators Σ_n is
benign if
  
    lim_n →∞r_0(Σ_n)/n
     = lim_n →∞k_n^*/n
     = lim_n →∞n/R_k_n^*(Σ_n)
     = 0.

  
    
    
      
  * 
        If μ_k(Σ) = k^-αln^-β (k+1), then
        Σ is benign iff α=1 and β > 1.
      
  * 
        If
          
    μ_k(Σ_n) = γ_k + ϵ_n    if k≤ p_n,
    
                  0      otherwise,

        and γ_k=Θ(exp(-k/τ)),
        then Σ_n is benign iff p_n=ω(n) and
        ne^-o(n)=ϵ_np_n=o(n).
        Furthermore, for p_n=Ω(n) and
        ϵ_np_n=ne^-o(n),
          
    R(θ̂)
                  = O(ϵ_np_n+1/n
                  + ln(n/(ϵ_np_n))/n
                  + max{1/n,n/p_n}).

    
  

Many popular learning algorithms may be viewed as the combination
of a feature transformation with a linear method applied to the
transformed features.  In practice, hyperparameter choices 
such as kernel parameters and deep network architectures can be made
with the knowledge of n, and of course these affect the spectrum of
the covariance of the transformed features.

It is informative to compare the situations described by
Parts <ref> and <ref>
of Theorem <ref>. 
Part <ref> shows that
if the data has finite dimension and a small amount
of isotropic noise is added to the covariates, even
if the eigenvalues of the original covariance operator (before the
addition of isotropic noise) decay very rapidly, benign overfitting
occurs iff both the dimension is large compared to the sample size,
and the isotropic component of the covariance is sufficiently
small—but not exponentially small—compared to the sample size.


Compare the situations described by
Parts <ref> and <ref>
of Theorem <ref>.
Part <ref> shows that
for infinite-dimensional data with a fixed covariance, benign
overfitting occurs iff the eigenvalues of the covariance operator
decay just slowly enough for their sum to remain finite.
Part <ref> shows that the situation is
very different if the data has finite dimension and a small amount
of isotropic noise is added to the covariates.  In that case, even
if the eigenvalues of the original covariance operator (before the
addition of isotropic noise) decay very rapidly, benign overfitting
occurs iff both the dimension is large compared to the sample size,
and the isotropic component of the covariance is sufficiently
small—but not exponentially small—compared to the sample size.

These examples illustrate the tension between the slow decay
of eigenvalues that is needed for k/n+n/R_k to be
small, and the summability of eigenvalues that is needed for
r_0(Σ)/n to be small. There are two ways to resolve this tension. 
First, in the infinite dimensional setting, slow decay of the
eigenvalues suffices—decay just fast enough to ensure
summability—as shown by Part <ref> of
Theorem <ref>.
(Appendix <ref>
gives another example, where the eigenvalue decay is allowed
to vary with n; in that case, Σ_n is benign iff the decay
rate gets close—but not too close—to 1/k as n increases.)
The other way to resolve the tension is to consider
a finite dimensional setting (which ensures that the eigenvalues
are summable), and in this case arbitrarily slow decay is possible.
Part <ref> of
Theorem <ref> gives an example of this:
eigenvalues that are all at least as large as a small constant.
Appendix <ref>
gives another example, with a truncated infinite
series that decays sufficiently slowly that their sum
does not converge.
Theorem <ref>(<ref>)
shows that a very specific decay rate is required in infinite
dimensions, which suggests that this is an unusual phenomenon in that
case. The more generic scenario where benign overfitting will occur is
demonstrated by
Theorem <ref>(<ref>),
with eigenvalues that are either constant or slowly decaying in a very
high—but finite dimensional—space.



§ DEEP NEURAL NETWORKS


How relevant are Theorems <ref>
and <ref> to the phenomenon of benign
overfitting in deep neural networks?  One connection appears by
considering regimes where deep neural networks are well-approximated
by linear functions of their parameters. This so-called neural tangent kernel (NTK) viewpoint has been vigorously pursued
recently in an attempt to understand the optimization properties
of deep learning methods.  Very wide neural networks, trained
with gradient descent from a suitable random initialization,
can be accurately approximated by linear functions in an
appropriate Hilbert space, and in this case gradient descent
finds an interpolating solution quickly; see <cit.>.
(Note that these papers do not consider prediction
accuracy, except when there is no noise; for
example, <cit.> implies that the
network can compute a suitable real-valued response exactly, and
the data-dependent bound of <cit.>
becomes vacuous when independent noise is added to the y_is.) The
eigenvalues of the covariance operator in this case can have a
heavy tail under reasonable assumptions on the data distribution
(see <cit.>, where this kernel was introduced,
and <cit.>),
and the dimension is very large but
finite, as required for benign overfitting. 
However, the assumptions
of Theorem <ref> do not apply in this case. In particular,
the assumption that the random elements of the Hilbert space are
a linearly transformed vector with independent components is not
satisfied. Thus, our results are not directly applicable in
this—somewhat unrealistic—setting.
Note that the slow decay of the eigenvalues of the NTK is in contrast
to the case of the gaussian and other smooth kernels, where the
eigenvalues decay nearly exponentially
quickly <cit.>.

The phenomenon of benign overfitting was first observed
in deep neural networks.
Theorems <ref> and <ref>
are steps towards understanding this phenomenon by
characterizing when it occurs in the simple setting of linear
regression. Those results suggest that covariance eigenvalues that are
constant or slowly decaying in a high (but finite)
dimensional space might be important in the deep network setting also.
Some authors have suggested viewing neural networks as
finite-dimensional approximations to infinite dimensional objects <cit.>, and there are
generalization bounds—although not for the overfitting regime—that
are applicable to infinite width deep networks with parameter norm
constraints <cit.>.
However, the intuition from the linear setting suggests
that truncating to a finite dimensional space might be important
for good statistical performance in the overfitting regime.
Confirming this conjecture by extending our results to the setting
of prediction in deep neural networks is an important open problem.



§ PROOF


Throughout the proofs, we treat σ_x (the subgaussian norm of
the covariates) as a constant. Therefore, we use the symbols
b,c,c_1,c_2,… to refer to constants that only depend on
σ_x. Their values are suitably large (and always at
least 1) but do not depend on any parameters of the problems we
consider, besides σ_x. For universal constants that do not depend on any parameters of the problem at all we use the symbol a. Also, whenever we sum over eigenvectors of 
Σ, the sum is restricted to eigenvectors with non-zero
eigenvalues.



 §.§ Outline


The first step is a standard decomposition of the excess risk into
two pieces, a term that corresponds to the distortion
that is introduced by viewing θ^* through the lens of the
finite sample and a term that corresponds to the
distortion introduced by the noise =y-Xθ.
The impact of both sources of error in θ̂ on
the excess risk is modulated by the covariance Σ, which
gives different weight to different directions in parameter space.


  The excess risk of the minimum norm estimator satisfies
    
    R(θ̂)
            ≤ 2θ^∗^⊤ B θ^∗
            + cσ^2log1/δ(C)

  with probability at least 1-δ over ϵ,
  and
    
    _ R(θ̂)
               ≥θ^∗^⊤ B θ^∗ + σ^2 (C),

  where
    
    B     = (I - X^⊤(X X^⊤)^-1X)
              Σ(I - X^⊤(X X^⊤)^-1X), 
    
          C     = (X X^⊤)^-1XΣ X^⊤(X X^⊤)^-1.



The proof of this lemma is in Appendix <ref>.
Appendices <ref> and <ref> give bounds on the term
θ^∗^⊤ B θ^∗.
The heart of the proof is controlling (C).

Before continuing with the proof, let us make a quick digression to
note that Lemma <ref> already begins to give an idea that
many low-variance directions are necessary for the least-norm
interpolator to succeed.  Let us consider the extreme case that p =
n and Σ = I.  In this case, C = (X X^⊤)^-1.
For gaussian data, for instance, standard random matrix theory implies
that, with high probability, the eigenvalues of X X^⊤ will
all be within a constant factor of n,
which implies (C) is bounded below by a constant,
and then Lemma <ref> implies that the least-norm interpolant's
excess risk is at least a constant.

To prove that
(C) can be controlled for suitable
Σ, the first step is to express it in terms of
sums of outer products of unit covariance independent subgaussian
random vectors.
We show that when there is a k^* with k^*/n small and
r_k^*(Σ)/n large, all of the
smallest eigenvalues of these matrices are suitably concentrated,
and this implies that (C) is bounded above by
  
    min_l≤ k^*(l/n + 
           n∑_i>lλ_i^2/(λ_k^*+1r_k^*(Σ))^2).

(Later, we show that the minimizer is l=k^*.)
Next, we show that this expression is also a lower bound on (C),
provided that there is such a k^*.
Conversely, we show that for any
k for which r_k(Σ) is not large compared to n,
(C) is at least as big as a constant times min(1,k/n).
Combining shows that when k^*/n is small,
(C) is upper and lower bounded by constant factors times
  
    k^*/n + n/R_k^*(Σ).




 §.§ Unit variance subgaussians


Our assumptions allow the trace of C to be expressed
as a function of many independent subgaussian vectors.


  Consider a covariance operator Σ with
  λ_i=μ_i(Σ) and λ_n>0. Write its spectral
  decomposition Σ=∑_jλ_j v_jv_j^⊤,
  where the orthonormal v_j∈ are the eigenvectors
  corresponding to the λ_j. 
  For i with λ_i > 0, define
  z_i=Xv_i/√(λ_i). Then 
    
    (C)
               = ∑_i[ λ_i^2 z_i^⊤(∑_jλ_j z_j z_j^⊤)^-2z_i],

  and these z_i∈^n are independent σ_x^2-subgaussian.
  Furthermore, for any i with λ_i > 0, we have
  
    λ_i^2 z_i^⊤(∑_jλ_j z_j z_j^⊤)^-2z_i
          = λ_i^2 z_i^⊤  A_-i^-2z_i/(1 + λ_i z_i^⊤ A_-i^-1z_i)^2,

  where A_-i = ∑_j ≠ iλ_j z_j z_j^⊤.



  By Assumption <ref> in
  Definition <ref>, the random
  variables x^⊤ v_i/√(λ_i) are independent
  σ_x^2-subgaussian. We consider X in the basis of
  eigenvectors of Σ, Xv_i=√(λ_i)z_i, to see that
  
    XX^⊤ = ∑_iλ_i z_i z_i^⊤,    
        XΣ X^⊤ = ∑_iλ_i^2 z_i z_i^⊤,

  so we can write
    
    (C)
                = ((X X^⊤)^-1XΣ X^⊤(X
              X^⊤)^-1) 
        = ∑_i[ λ_i^2 z_i^⊤(∑_jλ_j z_j z_j^⊤)^-2z_i].

  For the second part, we use
  Lemma <ref>, which is
  a consequence of the Sherman-Woodbury-Morrison formula; see
  Appendix <ref>.
    
    λ_i^2 z_i^⊤(∑_jλ_j z_j z_j^⊤)^-2z_i
             = λ_i^2 z_i^⊤(λ_i z_i z_i^⊤ 
            +A_-i)^-2z_i 
       = λ_i^2 z_i^⊤  A_-i^-2z_i/(1 + λ_i z_i^⊤ A_-i^-1z_i)^2,

  by Lemma <ref>, for the case k=1 and
  Z=√(λ_i)z_i. Note that A_-i is invertible by
  Assumption <ref> in Definition <ref>.


The weighted sum of outer products of these subgaussian vectors plays a
central role in the rest of the proof. Define
  
    A     = ∑_iλ_i z_i z_i^⊤,    
        A_-i    = ∑_j ≠ iλ_j z_j z_j^⊤,    
        A_k    = ∑_i>kλ_i z_i z_i^⊤,

where the z_i∈^n are independent vectors with independent σ_x^2-subgaussian  coordinates with unit variance, defined in Lemma <ref>.
Note that the vector z_i is independent of the matrix A_-i, so
in the last part of Lemma <ref>,
all the random quadratic forms are independent of the points where
those forms are evaluated.



 §.§ Concentration of A


The next step is to show that eigenvalues of A, A_-i and A_k are
concentrated. The proof of the following inequality is in
Appendix <ref>. Recall that μ_1(A) and μ_n(A)
denote the largest and the smallest eigenvalues of the n× n matrix A.


 There is a constant c such that for any k ≥ 0 
with probability at least 1 - 2e^-n/c,
    
    1/c∑_i > kλ_i - cλ_k+1 n
            ≤μ_n(A_k) ≤μ_1(A_k)
            ≤ c(∑_i> kλ_i + λ_k+1 n).



The following lemma uses this result to give bounds on the eigenvalues
of A_k, which in turn give bounds on some eigenvalues of A_-i
and A. For these upper and lower bounds to match up to a constant
factor, the sum of the eigenvalues of A_k should dominate the term
involving its leading eigenvalue, which is a condition on the
effective rank r_k(Σ).
The lemma shows that once r_k(Σ) is
sufficiently large, all of the eigenvalues of A_k are identical up
to a constant factor.


  There are constants b,c≥ 1 such that for any
k≥ 0, 
with probability at least 1 - 2e^-n/c,
    
      
  * for all i≥ 1,
        
    μ_k+1(A_-i) ≤μ_k+1(A) ≤μ_1(A_k)
               ≤ c(∑_j>kλ_j + λ_k+1n),

      
  * for all 1≤ i≤ k,
        
    μ_n(A) ≥μ_n(A_-i) ≥μ_n(A_k)
              ≥1/c∑_j>kλ_j - cλ_k+1 n,

      
  * if r_k(Σ)≥ bn, then
        
    1/cλ_k+1 r_k(Σ)
                ≤μ_n(A_k)
                ≤μ_1(A_k) ≤ cλ_k+1 r_k(Σ).

    


  By Lemma <ref>, we know that with probability at
  least 
1-2e^-n/c_1,
    
    1/c_1∑_j>kλ_j - c_1λ_k+1 n
               ≤μ_n(A_k) 
       ≤μ_1(A_k) 
            ≤ c_1(∑_j>kλ_j + λ_k+1 n).

  First, the matrix A - A_k has rank at most k
  (as a sum of k matrices of rank 1).
  Thus, there is a linear space  of dimension n-k such that 
  for all v∈, v^⊤ Av = v^⊤ A_k v ≤μ_1(A_k)v^2,
  and so μ_k+1(A) ≤μ_1(A_k).
  
  Second, by the Courant-Fischer-Weyl Theorem, for all i and j,
  μ_j(A_-i)≤μ_j(A) (see Lemma <ref>).
  On the other hand, for i ≤ k, A_k ≼ A_-i, so all
  the eigenvalues of A_-i are lower bounded by μ_n(A_k).

  Finally, if r_k(Σ)≥ b n,
    
    ∑_j>kλ_j + λ_k+1n
                = λ_k+1 r_k(Σ) + λ_k+1n 
       ≤(1+1/b)λ_k+1 r_k(Σ), 
    1/c_1∑_j>kλ_j - c_1λ_k+1n
                = 1/c_1λ_k+1 r_k(Σ) - c_1λ_k+1n
            
       ≥(1/c_1-c_1/b)
              λ_k+1 r_k(Σ).

  Choosing b > c_1^2 and c > max{c_1+1/c_1,
  (1/c_1-c_1/b)^-1}  gives the
  third
  claim of the lemma.




 §.§ Upper bound on the trace term



  There are constants b,c≥ 1 such that 
  if 0≤ k≤ n/c, r_k(Σ)≥ bn, and l≤ k 
then  with probability at least 
1 - 7e^-n/c,
    
    (C)
               ≤ c (l/n + n ∑_i>lλ_i^2/(∑_i>kλ_i)^2).


The proof uses the following lemma and its corollary. Their proofs are in
Appendix <ref>.

  	Suppose {λ_i}_i^∞ is a non-increasing sequence of non-negative numbers such that ∑_i=1^∞λ_i < ∞, and {ξ_i}_i = 1^∞ are independent centered σ-subexponential random variables. Then for some universal constant a for any t > 0 with probability at least 1-2e^-t
  	
    |∑_iλ_i ξ_i| ≤ aσmax(tλ_1, √(t ∑_iλ_i^2)).



	
	Suppose z∈^n is a centered random vector with independent
    σ^2-subgaussian coordinates with unit variances,
     is a random subspace of ^n of codimension
    k, and  is independent of z. Then for some universal
    constant a and any t > 0, with probability at least
    1-3e^-t,
	
    z^2    ≤ n + aσ^2(t + √(nt)),
    Π_ z^2    ≥ n - aσ^2(k + t + √(nt)),

	where Π_ is the orthogonal projection on .


(of Lemma <ref>)
    Fix b to its value in Lemma <ref>.
    By Lemma <ref>,
    
    (C)
                 = ∑_iλ_i^2 z_i^⊤ A^-2z_i 
       = ∑_i = 1^lλ_i^2 z_i^⊤  A_-i^-2z_i/(1 + λ_i z_i^⊤ A_-i^-1z_i)^2 +
                ∑_i >lλ_i^2 z_i^⊤ A^-2z_i.

    First, consider the sum up to l.
    If r_k(Σ)≥ bn,
    Lemma <ref> shows
    that with probability at least 
1-2e^-n/c_1,
    for all i≤ k, μ_n(A_-i)≥λ_k+1r_k(Σ)/c_1,
    and, for all i, μ_k+1(A_-i)≤ c_1λ_k+1r_k(Σ).
    The lower bounds on the μ_n(A_-i)'s imply that,
    for all z ∈^n and 1≤ i ≤ l,
      
    z^⊤ A_-i^-2 z
                 ≤c_1^2z^2/(λ_k+1r_k(Σ))^2,

    and the upper bounds on the μ_k+1(A_-i)'s give
      
    z^⊤ A_-i^-1 z
                 ≥(Π__i z)^⊤
                A_-i^-1Π__i z 
              ≥Π__i z^2/c_1λ_k+1r_k(Σ),

    where 
    _i is the span of the
    n-k eigenvectors of A_-i corresponding to its smallest n-k
    eigenvalues. So for i≤ l,
      
    λ_i^2 z_i^⊤  A_-i^-2z_i/(1 + λ_i z_i^⊤ A_-i^-1z_i)^2   ≤z_i^⊤  A_-i^-2z_i/(z_i^⊤ A_-i^-1z_i)^2≤ c_1^4z_i^2/Π__iz_i^4.

    Next, we apply Corollary <ref> l times, together with a union bound,
    to show that with probability at least 1-3e^-t, for all 1≤ i≤ l,
      
    z_i^2
                 ≤ n + aσ_x^2(t + ln k + √(n(t + ln k)))≤ c_2n, 
    Π__iz_i^2
                 ≥ n-aσ_x^2(k + t + ln k + √(n(t + ln k))) ≥ n/c_3,

    provided that  t < n/c_0 and c > c_0 for some sufficiently
    large c_0 (note that c_2 and c_3 only depend on c_0, a
    and σ_x, and we can still take c large enough in the end
    without changing c_2 and c_3).
    Combining (<ref>), (<ref>),
    and (<ref>), with probability at least
   1-5e^-n/c_0,
      
    ∑_i=1^lλ_i^2 z_i^⊤
                A_-i^-2z_i/(1 + λ_i z_i^⊤ A_-i^-1z_i)^2≤ c_4l/n.

    Second, consider the second sum in (<ref>).
    Lemma <ref> shows that, on the same high
    probability event that we considered in bounding the first half of the sum,
    μ_n(A)≥λ_k+1r_k(Σ)/c_1. Hence,
      
    ∑_i>lλ_i^2 z_i^⊤ A^-2z_i
                 ≤c_1^2∑_i>lλ_i^2z_i^2/(λ_k+1r_k(Σ))^2.

    Notice that ∑_i>lλ_i^2z_i^2 is a weighted sum of σ_x^2-subexponential random
    variables, with the weights given by the λ_i^2 in blocks of size n.
    Lemma <ref> implies that, with probability at least 1-2e^-t,
      
    ∑_i>lλ_i^2z_i^2
                 ≤ n∑_i>lλ_i^2
                + aσ_x^2max(λ_l+1^2t,
                √(tn∑_i>lλ_i^4)) 
       ≤ n∑_i>lλ_i^2
                + aσ_x^2max(t∑_i>lλ_i^2,
                √(tn)∑_i>lλ_i^2) 
       ≤ c_5n∑_i>lλ_i^2,

    because t < n/c_0. Combining the above gives
      
    ∑_i>lλ_i^2 z_i^⊤ A^-2z_i
                 ≤ c_6n∑_i>lλ_i^2/(λ_k+1r_k(Σ))^2.

     Finally, putting both parts together and taking c > max{c_0,
     c_4, c_6} gives the lemma.




 §.§ Lower bound on the trace term


We first give a bound on a single term in the expression for (C)
in Lemma <ref>
that holds regardless of r_k(Σ). The proof is in
Appendix <ref>.


  There is a constant c such that for any  i≥ 1 with λ_i > 0, and any 0≤ k≤ n/c, 
 with probability  at least 
1-5e^-n/c,
    
    λ_i^2 z_i^⊤ A_-i^-2z_i/(1 + λ_i z_i^⊤ A_-i^-1z_i)^2≥1/cn(1+∑_j >kλ_j
              + nλ_k+1/nλ_i)^-2.



We can extend these bounds to a lower bound on (C)
using the following lemma. The proof is in Appendix <ref>.


  Suppose n≤∞ and {η_i}_i = 1^n is a sequence
  of non-negative random variables, {t_i}_i=1^n is a sequence
  of non-negative real numbers (at least one of which is strictly
  positive) such that for some δ∈ (0,1) and any
  i ≤ n, (η_i > t_i) ≥ 1 - δ. Then
    
    (∑_i=1^nη_i ≥1/2∑_i=1^n t_i)
            ≥ 1 - 2δ.



These two lemmas imply the following lower bound.

  There are constants c such that for any 0≤ k≤ n/c and any b > 1
  with probability at least 
1-10e^-n/c,
  
    
  * If r_k(Σ)<bn, then (C)≥k+1/c b^2n.
    
  * If r_k(Σ)≥ bn, then
        
    (C)≥1/cb^2min_l≤ k(
              l/n + b^2n ∑_i>lλ_i^2/(λ_k+1r_k(Σ))^2).

  
  In particular, if all choices of k≤ n/c give r_k(Σ)<bn, then
  r_n/c(Σ)<bn implies that with probability at least 
1-10e^-n/c,
  (C)= Ω_σ_x( 1 ).

 
From Lemmas <ref>, <ref> and <ref>,
with probability at least 
1-10e^-n/c_1,
  
    (C)
             ≥1/c_1n∑_i (1+∑_j >kλ_j
            + nλ_k+1/nλ_i)^-2
       ≥1/c_2n∑_i min{
            1, n^2λ_i^2/(∑_j >kλ_j)^2,
            λ_i^2/λ_k+1^2}
       ≥1/c_2b^2n∑_i min{
            1, (bn/r_k(Σ))^2
            λ_i^2/λ_k+1^2,
            λ_i^2/λ_k+1^2}.

Now, if r_k(Σ)<bn, then the second term in the minimum
is always bigger than the third term, and in that case,
  
    (C)
             ≥1/c_2b^2n∑_i min{
            1, λ_i^2/λ_k+1^2}≥k+1/c_2b^2n.

On the other hand, if r_k(λ)≥ bn,
  
    (C)
             ≥1/c_2b^2∑_i min{1/n,
            b^2nλ_i^2/(λ_k+1r_k(Σ))^2}
       = 1/c_2b^2min_l≤ k(
            l/n + b^2n ∑_i>lλ_i^2/(λ_k+1r_k(Σ))^2),

where the equality follows from the fact that the λ_is are
non-increasing.




 §.§ A simple choice of l


Recall that σ_x is a constant. 
If no k≤ n/c has r_k(Σ)≥ bn,
then Lemmas <ref> and <ref>
imply that the expected excess risk is Ω(σ^2),
which proves the first paragraph of Theorem <ref> for large
k^*.
If some k≤ n/c does have r_k(Σ)≥ bn, then the upper and lower
bounds of Lemmas <ref> and <ref> are
constant multiples of
  
    min_l≤ k(
          l/n + n∑_i>lλ_i^2/(λ_k+1r_k(Σ))^2).

It might seem surprising that any suitable choice of k suffices
to give upper and lower bounds: what prevents one choice of k
from giving an upper bound that falls below the lower bound that
arises from another choice of k? However, the freedom to choose
k is somewhat illusory: Lemma <ref>
shows that, for any qualifying value of k, the smallest eigenvalue
of A is within a constant factor of λ_k+1r_k(Σ).
Thus, any two choices of k satisfying k≤ n/c and r_k(Σ)≥
bn must have values of λ_k+1r_k(Σ) within constant
factors.  The smallest such k simplifies the bound on (C), as
the following lemma shows. The proof is in Appendix <ref>.


For any b≥ 1 and k^* := min{k: r_k(Σ)≥ bn},
if k^* < ∞, we have
  
    min_l≤ k^*(
          l/bn + bn∑_i>lλ_i^2/(λ_k^*+1r_k^*(Σ))^2)
    
    
        = k^*/bn + bn∑_i>k^*λ_i^2/(λ_k^*+1r_k^*(Σ))^2
        = k^*/bn + bn/R_k^*(Σ).



Finally, we can finish the proof of Theorem <ref>. 
Set b in Lemma <ref> and Theorem <ref> to the constant b from  Lemma <ref>. Take c_1 to be the maximum of the constants c from  Lemmas <ref> and <ref>.

By Lemma <ref>, if k^* ≥ n/c_1, then
w.h.p. (C)≥ 1/c_2.
However, by the second part of Lemma <ref> and
by Lemma <ref>, if k^* < n/c_1, then w.h.p. (C)
is within a constant factor of min_l≤ k^*(
      l/n + n∑_i>lλ_i^2/(λ_k^*+1r_k^*(Σ))^2),
which, by Lemma <ref>, is 
within a constant factor of k^*/n + n/R_k^*(Σ).
Taking c sufficiently large, and combining
these results with Lemma <ref> and with the upper bound on the
term θ^∗^⊤ B θ^∗ in Appendix <ref>
completes the proof of the first paragraph of Theorem <ref>.

The proof of the second paragraph is in Appendix <ref>.



§ CONCLUSIONS AND FURTHER WORK


Our results characterize when the phenomenon of benign overfitting
occurs in high dimensional linear regression, with gaussian data
and more generally. We
give finite sample excess risk bounds that reveal the covariance
structure that ensures that the minimum norm interpolating prediction
rule has near-optimal prediction accuracy. The characterization
depends on two notions of the effective rank of the data covariance
operator. It shows that overparameterization, that is, the existence
of many low-variance and hence unimportant directions in parameter
space, is essential for benign overfitting, and that
data that lies in a large but finite dimensional space exhibits the
benign overfitting phenomenon with a much wider range of covariance
properties than data that lies in an infinite dimensional space.

There are several natural future directions. Our main theorem
requires the conditional expectation [y|x] to be a linear
function of x, and it is important to understand whether the results
are also true in the misspecified setting, where this assumption is
not true. Our main result also assumes
that the covariates are distributed as a linear function of a vector
of independent random variables. We would like to understand the
extent to which this assumption can be relaxed, since it rules out
some important examples, such as infinite-dimensional reproducing
kernel Hilbert spaces with continuous kernels defined on
finite-dimensional spaces.
We would also like to
understand how our results extend to other loss functions besides
squared error and what we can say about overfitting estimators
beyond the minimum norm interpolating estimator. The most interesting
future direction is understanding how these ideas could apply to
nonlinearly parameterized function classes such as neural networks,
the methodology that uncovered the phenomenon of benign overfitting.



§ ACKNOWLEDGEMENTS


We gratefully acknowledge the support of the NSF through grant
IIS-1619362 and of Google through a Google Research Award.  Part of
this work was done as part the Fall 2018 program on Foundations of
Data Science at the Simons Institute for the Theory of Computing.
Gábor Lugosi was supported by the Spanish Ministry of Economy and
Competitiveness, Grant MTM2015-67304-P and FEDER, EU;
“High-dimensional problems in structured probabilistic models -
Ayudas Fundación BBVA a Equipos de Investigación Cientifica
2017”; and Google Focused Award “Algorithms and Learning for AI”.


plain






§ PROOF OF LEMMA <REF>


We first give the decomposition of the excess risk.



  The excess risk of the minimum norm estimator satisfies
    
    R(θ̂)
                = _x(x^⊤(θ^*-θ̂))^2
            ≤ 2θ^∗^⊤ B θ^∗ +2^⊤
            C,

  and
    
    _x, R(θ̂)
               ≥θ^∗^⊤ B θ^∗ + σ^2 (C),

  where
    
    B     = (I - X^⊤(X X^⊤)^-1X)
              Σ(I - X^⊤(X X^⊤)^-1X), 
    
          C     = (X X^⊤)^-1XΣ X^⊤(X X^⊤)^-1.




  Since =y-x^⊤θ^* has mean zero conditionally on x,
    
    R(θ̂)
                = _x,y(y-x^⊤θ̂)^2
              - (y-x^⊤θ^*)^2 
        = _x,y(y-x^⊤θ^*
              + x^⊤(θ^*-θ̂))^2
              - (y-x^⊤θ^*)^2 
        = _x(x^⊤(θ^*-θ̂))^2.

  Using (<ref>), the definition of Σ, and the
  fact that y=Xθ^*+,
    
    R(θ̂)
                = _x(x^⊤(I - X^⊤(X X^⊤)^-1
              X)θ^∗ - x^⊤ X^⊤(X X^⊤)^-1)^2 
       ≤ 2 _x(x^⊤(I - X^⊤(X X^⊤)^-1
              X)θ^∗)^2 
              + 2 _x(x^⊤ X^⊤(X X^⊤)^-1)^2
        = 2θ^∗^⊤(I - X^⊤(X X^⊤)^-1X)
              Σ(I - X^⊤(X X^⊤)^-1X) θ^∗
       
              +2^⊤(X X^⊤)^-1XΣ X^⊤(X X^⊤)^-1
        = 2θ^∗^⊤ B θ^∗ +2^⊤
            C.

Also, since  has zero mean conditionally on X, and is independent of x, we have
    
    _x, R(θ̂)
                = _x,[
              (x^⊤(I - X^⊤(X X^⊤)^-1
              X)θ^∗)^2 
              + (x^⊤ X^⊤(X X^⊤)^-1)^2]
        = θ^∗^⊤(I - X^⊤(X X^⊤)^-1X)
              Σ(I - X^⊤(X X^⊤)^-1X) θ^∗
       
              +((X X^⊤)^-1XΣ X^⊤(X X^⊤)^-1[^⊤|X]) 
       ≥θ^∗^⊤ B θ^∗ + σ^2 (C).



The following lemma shows that we can obtain a high-probability upper
bound on the term ^⊤ C in terms
of the trace of C. It is Lemma 36 in <cit.>.

	
  Consider random variables _1,…,_n, conditionally
  independent given X and conditionally σ^2-subgaussian, that
  is, for all λ∈,
    
    [exp(λ_i)|X] ≤exp(σ^2λ^2/2).

  Suppose that, given X, M∈^n× n is a.s. positive
  semidefinite. Then a.s. on X, with conditional probability at
  least 1-e^-t,
    
    ^⊤ M ≤σ^2(M) + 2σ^2 Mt
              + 2σ^2√(M^2 t^2 +
              (M^2)t).


Since C≤(C) and (C^2) ≤(C)^2,
with probability at least 1-e^-t,
  
    ^⊤ C   ≤σ^2(C)(2t+1) + 2σ^2√((C)^2(t^2 + t))≤ (4t+2)σ^2(C).

Combining this with Lemma <ref>
implies Lemma <ref>.



§ AN ALGEBRAIC PROPERTY
.


  Suppose k < n, A ∈^n× n is an invertible matrix,
  and Z ∈^n× k is such that ZZ^⊤ + A is invertible.
  Then
    
    Z^⊤ (ZZ^⊤ + A)^-2 Z
          = (I +  Z^⊤ A^-1Z)^-1Z^⊤ A^-2Z
            (I +  Z^⊤ A^-1Z)^-1.




  We use the Sherman–Morrison–Woodbury formula to write
  
    (ZZ^⊤ + A)^-1
        = A^-1 - A^-1Z(I + Z^⊤ A^-1Z)^-1Z^⊤ A^-1.

  Denote M_1:= Z^⊤ A^-1Z and M_2:= Z^⊤ A^-2Z.
  Applying (<ref>), we get
	
    Z^⊤(ZZ^⊤ + A)^-2 Z 
    	    = Z^⊤(A^-1 - A^-1Z(I + Z^⊤ A^-1Z)^-1Z^⊤ A^-1)^2Z 
        = Z^⊤(A^-1 - A^-1Z(I + M_1)^-1Z^⊤ A^-1)^2Z 
        = Z^⊤(
                     A^-2
                     - A^-2Z(I + M_1)^-1Z^⊤ A^-1 
                     - A^-1Z(I + M_1)^-1Z^⊤ A^-2
       
              + A^-1Z(I + M_1)^-1Z^⊤ A^-2Z(I + M_1)^-1Z^⊤ A^-1)Z 
        = M_2 - M_2(I + M_1)^-1M_1 
          - M_1(I + M_1)^-1M_2 
       
              + M_1(I + M_1)^-1M_2(I + M_1)^-1M_1
        = M_2 - M_2(I + M_1)^-1M_1 
          - M_1(I + M_1)^-1M_2 (I - (I + M_1)^-1M_1) 
        = M_2(I + M_1)^-1 -  M_1(I + M_1)^-1M_2(I + M_1)^-1
        = (I + M_1)^-1M_2(I + M_1)^-1,

  where we used the identity I - (I + M_1)^-1M_1 = (I + M_1)^-1
  twice in the second last equality and the identity
  I - M_1(I + M_1)^-1 = (I + M_1)^-1 in the last equality.




§ PROOF OF CONCENTRATION INEQUALITIES


We use some standard results about subgaussian and
subexponential random variables.

First of all, we need the following direct consequence of
Propositions 2.5.2 and 2.7.1 and Lemma 2.7.6
from <cit.>:

    There is a universal constant c such that for any
    random variable ξ that is centered, σ^2-subgaussian,
    and unit variance, ξ^2 - 1 is a centered
    cσ^2-subexponential random variable, that is,
	  
    exp(λ(ξ^2 - 1)) ≤exp(c^2σ^4λ^2) for all such λ that 
            |λ| ≤1/cσ^2.



Second, we are going to use the following form of Bernstein's inequality, which is Theorem 2.8.2 in <cit.>:

    There is a universal constant c such that, for any
	independent, mean zero, σ-subexponential random variables
	ξ_1, …, ξ_N, any a = (a_1, …, a_N)∈^n, and
    any t ≥ 0,
	  
    (|∑_i=1^N a_i ξ_i| > t)
                ≤ 2exp[-cmin(t^2/σ^2 ∑_i=1^N
            a_i^2, t/σmax_1 ≤ i ≤ n
            a_i)].



    There is a universal constant c such that for any
	non-increasing sequence {λ_i}_i =1^∞
    of non-negative numbers such that
    ∑_i=1^∞λ_i < ∞, and any
    independent, centered, σ-subexponential random variables
    {ξ_i}_i = 1^∞, and any x > 0, with probability
    at least 1-2e^-x
	  
    |∑_iλ_i ξ_i| ≤
            cσmax(xλ_1, √(x ∑_iλ_i^2)).



    There is a universal constant c such that for any
	centered random vector z∈^n with independent
    σ^2-subgaussian coordinates with unit variances, any
    random subspace  of ^n of codimension k that is
    independent of z, and any t > 0, with probability at
    least 1-3e^-t,
	  
    z^2 ≤    n + cσ^2(t + √(nt)),
    Π_ z^2 ≥    n - cσ^2(k + t + √(nt)),

	where Π_ is the orthogonal projection on .


	First of all, since z^2 = ∑_i=1^n z_i^2 — a sum of
    n σ^2-subexponential random variables, by
    Corollary <ref>, for some absolute constant c
    and for any t > 0, with probability at least 1 - 2e^-t,
	
    |z^2 - n| ≤ cσ^2max(t, √(nt)).

	
	Second, we can write
	
    Π_ z^2 = z^2 - Π_^⊥ z^2.

	
	Denote M = Π_^⊥^⊤Π_^⊥. 	Since M =
    1 and (M) = (M^2) = k, by
    Lemma <ref>,
    with probability at least 1 - e^-t,
	
    Π_^⊥ z^2 =    z^⊤ M z
    ≤   σ^2 k + 2σ^2 t + 2σ^2√(t^2 + kt)
    ≤   σ^2(2k+4t).

	
	Thus, with probability at least 1-3e^-t
	
    z^2 ≤    n + cσ^2max(t, √(nt)),
    Π_ z^2 ≥   z -  σ^2(2k+4t)
    ≥    n -  σ^2(2k + 4t + cmax(t, √(nt))).





  Suppose A ∈^n× n is a symmetric matrix, and
  _ϵ is an ϵ-net on the unit sphere ^n-1 in
  the Euclidean norm, where ϵ < 1/2. Then
    
    A≤ (1 - ϵ)^-2max_x ∈_ϵ |x^⊤ Ax|.



  Denote the eigenvalues of A as λ_1, …, λ_n
  and assume |λ_1| ≥ |λ_2| ≥…≥ |λ_n|.
  Denote the first eigenvector of A as v ∈^n-1, and take
  Δ v ∈^n such that v + Δ v ∈_ϵ and
  Δ v≤ϵ. 
  Denote the coordinates of Δ v in
  the eigenbasis of A as Δ v_1, …, Δ v_n.
  Now we can write
    
    |(v + Δ v)^⊤  A (v + Δ v)|
               = |λ_1 + 2λ_1Δ v_1
              + ∑_i=1^n λ_i Δ v_i^2|
       = |λ_1|·|1 + 2Δ v_1 + Δ v_1^2
              + ∑_i=2^n λ_i/λ_1Δ v_i^2|
       ≥|λ_1|·|1 + 2Δ v_1 + Δ v_1^2
              - ∑_i=2^n Δ v_i^2|
       = |λ_1|·|1 + 2Δ v_1 + Δ v_1^2 - Δ v^2 + Δ v_1^2|
       = |λ_1|·|1 + 2(Δ v_1 + Δ v_1^2) - Δ v^2 |
       ≥ |λ_1|·|1 + 2(-Δ v + (-Δ v)^2) - Δ v^2 |
       =|λ_1|·|1 - 2Δ v + Δ v^2 |
       ≥ |λ_1| · |1 - 2ϵ + ϵ^2|
       = A(1-ϵ)^2,

  where the first inequality holds because the λ_is are
  decreasing in magnitude, and the last two inequalities hold since
  the functions x + x^2 and 2x + x^2 are both increasing on
  (-1/2, ∞) and Δ v_1 ≥ -Δ v≥
  -ϵ≥ -1/2.


We restate Lemma <ref>.


  There is a universal constant c such that with probability at least 1 - 2e^-n/c,
    
    1/c∑_iλ_i - cλ_1 n
            ≤μ_n(A) ≤μ_1(A)
            ≤ c(∑_iλ_i + λ_1 n).



  For a fixed vector v ∈^n, Proposition 2.6.1 from
  <cit.> implies that for some constant c_1 and any
  i the random variable v^⊤ z_i is
  c_1v^2σ_x^2-subgaussian. Thus, for any fixed unit vector
  v, as v^⊤ A v = ∑_iλ_i(v^⊤ z_i)^2,
  Lemma <ref> and
  Corollary <ref> imply that for some constant c_2 with
  probability at least 1 - 2e^-t,
    
    |v^⊤ A v - ∑λ_i|
            ≤ c_2σ_x^2max(λ_1 t, √(t∑λ_i^2)).

  Let  be a 1/4-net on the sphere ^n-1 with respect to the
  Euclidean distance such that ||≤ 9^n.
  Applying the union bound over the elements of , we see that
  with probability 1 - 2e^-t, every v ∈ satisfies
   
    |v^⊤ A v - ∑λ_i| 
            ≤ c_2σ_x^2max(λ_1 (t + nln 9), √((t + nln 9)∑_iλ_i^2)).

  Since  is a 1/4-net, by Lemma <ref>,
  we need to multiply the quantity above by (1 - 1/4)^-2 to
  get the bound on the norm of the A - I_n∑_iλ_i. Denote
  
    = (λ_1 (t + nln 9)
      + √((t + nln 9)∑_iλ_i^2)).

  Thus, with probability at least 1 - 2e^-t,
  
    A - I_n∑_i λ_i≤ c_3σ_x^2.

  When t<n/c_4 we can write t+nln 9≤ c_5n, and we have
    
    ≤ c_5(λ_1 n + √(n∑_i λ_i^2)) 
       ≤ c_5λ_1 n
              + √((c_5^2λ_1 n)
              ∑_i λ_i)
       ≤ c_6σ_x^2λ_1 n + 1/2c_3σ_x^2∑_i λ_i,

  by the AMGM inequality. (Recall that c_1,c_2,… denote universal
  constants with value at least 1, and σ_x ≥ 1/c_7 is the
  subgaussian constant of a random variable with unit variance.)




§ PROOF OF LEMMA <REF>



  Fix i≥ 1 with λ_i > 0
  and 0≤ k≤ n/c. By Lemma <ref>,
  with probability at least 
1-2e^-n/c_1,
    
    μ_k+1(A_-i)
          ≤ c_1(∑_j>kλ_j + λ_k+1n),

  and hence
    
    z_i^⊤ A_-i^-1z_i
               ≥Π__i z_i^2/c_1( ∑_j >kλ_j + λ_k+1n).

  By Corollary <ref>,
  with probability at least 1-3e^-t,
    
    Π__i z_i^2 ≥ n-aσ_x^2(k + t + √(tn))≥ n/c_2,

    provided that t < n/c_0 and c > c_0 for some sufficiently large c_0.
  Thus, with probability at least 
1-5e^-n/c_3,
    
    z_i^⊤ A_-i^-1z_i
          ≥ n/ c_3(∑_j >kλ_j + λ_k+1n),

  hence
    
    1 + λ_i z_i^⊤ A_-i^-1z_i 
      ≤(c_3(∑_j >kλ_j + λ_k+1n)/λ_in + 1)
              λ_i z_i^⊤ A_-i^-1z_i.

  Dividing λ_i^2z_i^⊤  A_-i^-2z_i by the square of both
  sides, we have
    
    λ_i^2 z_i^⊤  A_-i^-2z_i/(1 + λ_i z_i^⊤ A_-i^-1z_i)^2   ≥(c_3(∑_j >kλ_j + λ_k+1n)/λ_in + 1)^-2z_i^⊤ A_-i^-2z_i/(z_i^⊤ A_-i^-1z_i)^2.

  Also, from the Cauchy-Schwarz inequality 
  and Corollary <ref> again,
  we have that 
  on the same event,
    
    z_i^⊤  A_-i^-2z_i/( z_i^⊤ A_-i^-1z_i)^2   ≥ z_i^⊤
            A_-i^-2z_i/A_-i^-1z_i^2z_i^2
        = 1/z_i^2≥1/n + aσ_x^2(t + √(nt))≥1/c_4 n.

  Choosing c suitably large gives the lemma.



§ PROOF OF LEMMA <REF>


  We know that, for all i≤ n,
    (η_i > t_i) ≥ 1 - δ.
  Consider the following event: 
    
    E = {∑_i=1^n η_i < 1/2∑_i=1^n
          t_i},

  and denote its probability as cδ for some c ∈ (0,δ^-1). 
  On the one hand, by the definition of the event, we have
    
    1/(E)[_E ∑_i=1^n η_i] ≤1/2∑_i=1^n t_i.

  On the other hand, note that for any i,
    
    [η_i _E] ≥   [ t_i_{η_i≥ t_i}∩ E ]
       = t_i ({η_i≥ t_i}∩ E)
       ≥ t_i( {η_i≥ t_i} +(E) -1)
       ≥ t_i(c-1)δ.

  So
    
    [_E ∑_i=1^n η_i]
               ≥ (c-1)δ∑_i=1^n t_i, 
    1/(E)[_E ∑_i=1^n η_i]
               ≥ (1-c^-1)∑_i=1^n t_i.

  Thus, we obtain
    
    1/2∑_i=1^n t_i ≥ (1-c^-1)∑_i=1^n t_i, 
    
          c ≤ 2, 
    (∑_i=1^nη_i < 1/2∑_i=1^n t_i) = cδ≤ 2δ.




§ PROOF OF LEMMA <REF>



  We can write the function of l being minimized as
    
    l/bn + bn∑_i>lλ_i^2/(λ_k^*+1r_k^*(Σ))^2    = ∑_i=1^l 1/bn +∑_i>lbnλ_i^2/(λ_k^*+1r_k^*(Σ))^2
       ≥∑_i=1^k^*min{1/bn,
              bnλ_i^2/(λ_k^*+1r_k^*(Σ))^2}
           
              + ∑_i>k^*bnλ_i^2/(λ_k^*+1r_k^*(Σ))^2
        = ∑_i=1^l^*1/bn +∑_i>l^*bnλ_i^2/(λ_k^*+1r_k^*(Σ))^2,

  where l^* is the largest value of i≤ k^* for which 
    
    1/bn≤bnλ_i^2/(λ_k^*+1r_k^*(Σ))^2,

  since the λ_i^2 are non-increasing.
  This condition 
  holds iff
    
    λ_i
            ≥λ_k^*+1r_k^*(Σ)/bn.

  The definition of k^* implies r_k^*-1(Σ)<bn. So we can write
    
    r_k^*(Σ)
                = ∑_i>k^*λ_i/λ_k^*+1
        = ∑_i>k^*-1λ_i-λ_k^*/λ_k^*+1
        = λ_k^*/λ_k^*+1 (r_k^*-1(Σ) -1) 
        < λ_k^*/λ_k^*+1(bn-1),

  and so
  the minimizing l is k^*. Also,
    
    ∑_i>k^*λ_i^2/(λ_k^*+1r_k^*(Σ))^2    = ∑_i>k^*λ_i^2/(∑_i>k^*λ_i)^2
            = 1/R_k^*(Σ).




§ EIGENVALUE MONOTONICITY


Recall (half of) the Courant-Fischer-Weyl theorem.


For any symmetric n × n matrix A, and any i ∈ [n], 
μ_i(A) is 
the minimum, over all subspaces U of ^n
of dimension n - i, of the maximum, over all unit-length
u ∈ U, of u^⊤ A u.



If symmetric matrices A and B
satisfy A≼ B, then, for any i ∈ [n], we have
μ_i(A)≤μ_i(B).


Let U be the subspace of ^n of dimension n-i
that minimizes the maximum
over all unit-length u ∈ U, of u^⊤ A u, and
let V be the analogous subspace for B.
We have

    μ_i(A) 
         = max_u ∈ U: || u || = 1 u^⊤ A u 
                 
       ≤max_v ∈ V: || v || = 1 v^⊤ A v 
              
       ≤max_v ∈ V: || v || = 1 v^⊤ B v 
              
        = μ_i(B),

by Lemma <ref>, completing the proof.




§ RANK FACTS


The quantity r_0(Σ) is an important complexity parameter
for covariance estimation problems, where it has been called the
`effective rank' <cit.>.  Earlier,
r_0(Σ^2) was called the `stable rank' <cit.>
and the `numerical rank' <cit.>, although that
term has a different meaning in computational linear
algebra <cit.>.

We restate Lemma <ref>.

  r_k(Σ)≥ 1, r^2_k(Σ)=r_k(Σ^2)R_k(Σ), and
  r_k(Σ^2) ≤ r_k(Σ) ≤ R_k(Σ) ≤ r_k^2(Σ).


  The first inequality and the equality are immediate from the
  definitions. Together they imply R_k(Σ) ≤ r_k^2(Σ).
  For the second inequality,
  
    r_k(Σ^2)
            = ∑_i>kλ_i^2/λ_k+1^2≤λ_k+1∑_i>kλ_i/λ_k+1^2
        = r_k(Σ).

  Substituting this in the equality implies
  r_k(Σ) ≤ R_k(Σ).



Writing r_k and R_k for r_k(Σ) and R_k(Σ),
  
    1/R_k+1 = 1/R_k-1/r_k^2/1-(2-1/r_k)1/r_k.

  Thus, the function ϕ(k)= k/(b^2n) + n/R_k
  satisfies the monotonicity property ϕ(k+1)>ϕ(k) whenever
  r_k>bn≥ 1.



Writing
  
    q = ∑_i>k+1λ_i^2,   s = ∑_i>k+1λ_i,

so that R_k+1=s^2/q, we have
  
    1/R_k - 1/R_k+1    = λ_k+1^2 +q/(λ_k+1+s)^2
              - q/s^2
        = (λ_k+1^2 +q)s^2 - q(λ_k+1+s)^2/s^2(λ_k+1+s)^2
        = 1/r_k^2 - qλ_k+1(λ_k+1+2s)/s^2(λ_k+1+s)^2
        = 1/r_k^2 - 2(λ_k+1+s)-λ_k+1/R_k+1r_k (λ_k+1+s)
        = 1/r_k^2 - 2-1/r_k/R_k+1r_k.

Hence
  
    1/R_k+1    = 1/R_k - 1/r_k^2/1-(2-1/r_k)1/r_k.

Since
r_k>1, 0<1-(2-1/r_k)/r_k<1, so
  
    n/R_k+1    > n/R_k - n/r^2_k,

and if r_k>bn,
  
    ϕ(k+1)-ϕ(k)
              = k+1/b^2n + n/R_k+1
            - (k/b^2n + n/R_k) 
        > 1/b^2n - n/r^2_k
        >0.





§ CONDITIONS ON EIGENVALUES


In this section, we prove the following expanded version of
Theorem <ref>.
  
    Define
     λ_k,n:= μ_k(Σ_n) for all k,n.
    
      
  * 
        If λ_k,n = k^-αln^-β (k+1), then
        Σ_n is benign iff α=1 and
        β > 1.
      
  * 
        If λ_k,n = k^-(1+α_n), then
        Σ_n is benign iff ω(1/n)=α_n=o(1).
        Furthermore,
          
    R(θ̂)
                  = Θ(min{1/α_nn
                  +α_n,1}).

      
  * 
        If
          
    λ_k,n = 
                  k^-α   if k≤ p_n,
    
                  0      otherwise,

        then Σ_n is benign iff either 0<α<1,
        p_n=ω(n) and p_n=o(n^1/(1-α)) or
        α=1, p_n = e^ω(√(n)) and  p_n = e^o(n).
      
  * 
        If
          
    λ_k,n = γ_k + ϵ_n    if k≤ p_n,
    
                  0      otherwise,

        and γ_k=Θ(exp(-k/τ)),
        then Σ_n is benign iff p_n=ω(n) and
        ne^-o(n)=ϵ_np_n=o(n).
        Furthermore, for p_n=Ω(n) and
        ϵ_np_n=ne^-o(n),
          
    R(θ̂)
                  = O(ϵ_np_n+1/n
                  + ln(n/(ϵ_np_n))/n
                  + max{1/n,n/p_n}).

    
  

We build up the proof in stages.  First, we characterize those
sequences of effective ranks that can arise.

	
		Consider some positive summable sequence {λ_i}_i=1^∞, and for any non-negative integer i denote 
		
    r_i := λ_i+1^-1∑_j > iλ_j.

		Then r_i > 1 and
		∑_i r_i^-1 = ∞.
		Moreover, for any positive sequence {u_i} such
                that  ∑_i = 0^∞ u_i^-1 = ∞ and for
                every i u_i > 1, there exists a positive sequence {λ_i} (unique up to
                constant multiplier) such that  r_i ≡ u_i.  The sequence is (a constant rescaling of)
			 
    λ_k = u_k-1^-1∏_i=0^k-2(1 - u_i^-1).

	
	
			
    ∑_i ≥ k+1λ_i =   ∑_i ≥ kλ_i - λ_k
    			= (1 - r_k-1^-1)∑_i ≥ kλ_i.

			Thus, 
			
    ∑_i ≥ k+1λ_i = ∏_i =
                0^k-1(1 - r_i^-1) ·∑_iλ_i,

			which goes to zero if and only if ∑_i r_i^-1 = ∞.
			 On the other hand, we may rewrite the first equality in the proof as
			
    λ_k+1r_k = λ_kr_k-1(1 - r_k-1^-1),

            and hence
			
    λ_kr_k-1 =
                    ∏_i=0^k-2(1-r_i^-1)
                    λ_1r_0.

			So for any sequence {u_i} we can uniquely (up to a
            constant multiplier) recover the sequence {λ_i} such that  r_i = u_i — the only candidate is 
			 
    λ_k = u_k-1^-1∏_i=0^k-2(1 - u_i^-1).

			 However, for such {λ_i} one can compute
			 
    ∑_i=1^k λ_i = 1 - ∏_i=0^k-1(1 - u_i^-1),

			 so the resulting sequence {λ_i}  sums to 1, and 
			 
    r_k = λ_k+1^-1∑_i > kλ_i = λ_k+1^-1∏_i=0^k-1(1 - u_i^-1) = u_k.

 			 
 	

	
      
		Suppose b is some constant, and k^∗(n) =
                min{k: r_k ≥ bn}. Suppose also that the
                sequence {r_n} is increasing. Then, as n goes to
                infinity,  k^∗(n)/n goes to zero  if and only if
                r_n/n goes to infinity.
		
	
		We prove the “if” part separately from the “only if” part.
		
			
  * If  k^∗(n)/n → 0 then r_n/n →∞.
			
			Fix some C > 1.  Since k^∗(n)/n → 0, there exists some N_C such that  for any n ≥ N_C, k^∗(n) < n/C. Thus,  for all n > N_C, 
			
    k^∗(⌊ Cn⌋) ≤ n,
    
    			 r_n ≥  r_k^∗(⌊ Cn⌋)≥ b⌊ Cn⌋.

			 
			 Since the constant C is arbitrary, r_n/n goes to infinity.
		 
		 	
  * If r_n/n →∞ then  k^∗(n)/n → 0 .
		 	
		 	Fix some constant C > 1. Since r_n/n →∞  there exists some N_C such that  for any n ≥ N_C, r_n > Cn. Thus,  for any n > CN_C/b 
		 	
    r_⌈ nb/C⌉≥ bn,
    
    			 	k^∗(n) ≤⌈ nb/C⌉.
 
		 	 Since the constant C is arbitrary, k^∗(n)/n goes to zero.
		 
	

	
          
		Suppose the sequence {r_i} is increasing and r_n/n →∞ as n →∞. Then a sufficient condition for n/R_k^∗(n)→ 0 is 
		
    r_k^-2 = o(r_k^-1 - r_k+1^-1)  as  k →∞.

		For example, this condition holds for r_n = nlog n.
	
	
		We need to show that 
		
    n/R_k^∗(n) = n∑_i > k^∗(n)λ_i^2/(∑_i > k^∗(n)λ_i)^2 = n∑_i > k^∗(n)λ_i^2/λ_k^∗(n)+1^2r_k^∗(n)^2→ 0.

		Since r_k^∗(n)≥ bn
                and lim_n →∞ k^*(n) = ∞, 
                it is enough to prove
                that ∑_i >
                    kλ_i^2/λ_k+1^2r_k→ 0 as k
                goes to infinity.
                Since 
		
    λ_k+2 r_k+1 =  λ_k+1r_k(1 - r_k^-1),

		we can write that
                
    λ_k+1+lr_k+l    =  λ_k+1r_k∏_i = k^k+l-1 (1-r_i^-1) 
       ≤λ_k+1r_k exp(-∑_i=k^k+l-1r_i^-1)

                which yields
		
    λ_k+1+l/λ_k+1r_k≤ r_k+l^-1exp(-∑_i=k^k+l-1r_i^-1).

		Thus, we obtain
		
    ∑_i > kλ_i^2/λ_k+1^2r_k≤
    		r_k∑_i ≥ k r_i^-2exp(-2∑_j=k^i-1r_j^-1),

		and it is sufficient to prove that the latter quantity goes to zero. We write
		
    r_k∑_i ≥ k r_i^-2exp(-2∑_j=k^i-1r_j^-1) =   ∑_i ≥ k r_i^-2exp(-2∑_j=k^i-1r_j^-1)/r_k^-1
    
    		 =   ∑_i ≥ k r_i^-2exp(-2∑_j=0^i-1r_j^-1)/r_k^-1exp(-2∑_j=0^k-1r_j^-1).

		 Since both numerator and denominator are decreasing in k and go to zero as k →∞, we can apply the Stolz–Cesáro theorem (an analog of L'Hôpital's rule for discrete sequences):
		
    lim_k →∞∑_i ≥ k
                    r_i^-2exp(-2∑_j=0^i-1r_j^-1)/r_k^-1exp(-2∑_j=0^k-1r_j^-1)    =  lim_k →∞r_k^-2exp(-2∑_j=0^k-1r_j^-1)/(r_k^-1 - e^-2r_k^-1r_k+1^-1)exp(-2∑_j=0^k-1r_j^-1) 
        =  lim_k →∞r_k^-2/(r_k^-1 - e^-2r_k^-1r_k+1^-1)
           (since, for large enough k,
                      e^-2r_k^-1≤ 1-r_k^-1)
       ≤lim_k →∞r_k^-2/r_k^-1 - r_k+1^-1 + r_k^-1r_k+1^-1
        = 0,

		where the last line is due to our sufficient condition.
	

Now we are ready to prove
Theorem <ref>.

Part <ref>, if direction, first term:  We have

    || Σ_n || √(r_0(Σ_n)) 
      = √(λ_1 ∑_i=1^∞λ_i)
          = O( √(∑_i=1^∞1/i log^β (1 +
          i))),

which is O(1) for β > 1.

Part <ref>, if direction, second term:  
By Theorem <ref>, it suffices to prove
that lim_n→∞r_n/n = ∞.  This holds because

    r_n 
         = ∑_i > n1/i log^β (1 + i)/1/(n+1) log^β (2 + n) 
      = Θ(n log n),

since β > 1.

Part <ref>, if direction, third term:  By Theorem <ref>, it suffices to
prove that r_k^-2 = o(r_k^-1 - r_k+1^-1), that is

    lim_k →∞r_k^-2/r_k^-1 - r_k+1^-1 = 0

or, equivalently,

    lim_k →∞r_k+1/r_k (r_k+1 - r_k) = 0.

As argued above, when α = 1 and β > 1, r_k = Θ(k
log k), so it suffices to show that lim_k →∞
(r_k+1 - r_k) = ∞.  We have

    r_k+1 - r_k 
         = ∑_i > k+1λ_i/λ_k+2
          - ∑_i > kλ_i/λ_k+1
        = ( ( λ_k+1 - λ_k+2) ∑_i > k+1λ_i )
               - λ_k+1λ_k+2/λ_k+1λ_k+2
        = ( ( 1/λ_k+2 - 1/λ_k+1)
             ∑_i > k+1λ_i )
          - 1

so it suffices to show that

    lim_k →∞( 1/λ_k+2 - 1/λ_k+1)
             ∑_i > k+1λ_i = ∞.

Since λ_i is non-increasing, we have

    ( 1/λ_k+2 - 1/λ_k+1)
             ∑_i > k+1λ_i 
       ≥( 1/λ_k+2 - 1/λ_k+1)
             ∫_k+1^∞1/x log^β x  dx 
        = ( 1/λ_k+2 - 1/λ_k+1)
             1/(β - 1) log^β - 1 (k+1)
        = (k+2) log^β (k+3) - (k+1) log^β (k+2)/(β - 1) log^β - 1 (k+1).

If we define f on the positive reals by
f(x) = x log^β (x+1), then f is 
convex, and, since 
f'(x) = β x log^β - 1 (x+1)/x+1 + log^β (x+1),
we have

    (k+2) log^β (k+3) - (k+1) log^β (k+2)/(β - 1) log^β - 1 (k+1)   ≥β (k+1) log^β - 1 (k+2)/k+2 
              + log^β (k+2)/(β - 1) log^β - 1 (k+1),

which goes to infinity for large k, completing the proof of the
“if” direction of the third term of Part <ref>.

Part <ref>, only if direction, α > 1:  
If α > 1, then 

    r_n 
         = ∑_i > n1/i^a log^β (1 + i)/1/n^a log^β (1 + n)
       ≤ n^α∑_i > nlog^β (1 + n)/i^a log^β (1 + i)
       ≤ n^α∑_i > n1/i^a
        = n^α O(n^1 - α),

which does not grow faster than n.  Thus, by
Theorem <ref>, k^∗(n)/n does not go to zero.

Part <ref>, only if direction, 
   α < 1, or α = 1 and β≤ 1:  
In this case, since, as above

    || Σ_n || √(r_0(Σ_n))≥√(∑_i=1^∞λ_i),

and ∑_i=1^∞1/i^αlog^β (1 + i)
diverges in this case, 
|| Σ_n || √(r_0(Σ_n))/n does not go to zero.

Before starting on Part <ref>,
let us define r_k,n = r_k(Σ_n) and R_k,n = R_k(Σ_n).

Part <ref>, if direction, first term:  We have

    || Σ_n || √(r_0,n) 
      = √(λ_1,n∑_i=1^∞λ_i.n)
          = √(∑_i=1^∞1/i^1+α_n)≤√(1 + 1/α_n),

so || Σ_n || √( r_0,n/n)≤√(1 +
    1/α_n/n) which goes to zero with n if α_n
= ω(1/n).

Part <ref>, if direction, second term:  
First, 

    r_k,n    = (k+1)^1 + α_n∑_i > k i^-(1 + α_n)
       ≥ (k+1)^1 + α_n∫_k+1^∞ x^-(1 + α_n) dx 
        = k+1/α_n.

Thus, k^*(n) = O(α_n n), so that 
k^*(n)/n = O(α_n) = o(1).

Part <ref>, if direction, third term:  
We bound R_k,n from below by separately bounding
its numerator and denominator:

    ∑_i > k i^-(1 + α_n)   ≥∫_k+1^∞ x^-(1 + α_n) dx 
        = 1/α_n (k+1)^α_n,

and

    ∑_i > k i^-2 (1 + α_n)   ≤∫_k^∞ x^-2 (1 + α_n) dx 
        = 1/ k^1 + 2 α_n (2 α_n + 1),

so that

    R_k,n≥k^1 + 2 α_n (2 α_n + 1)/α_n^2 (k+1)^2 α_n≥k/α_n^2×( 1 - 1/k+1)^2 α_n.

So now we want a lower bound on k^*(n).  For that, we need
an upper bound on r_k,n, and

    r_k,n   ≤ (k+1)^1 + α_n∫_k^∞ x^-(1 + α_n) dx 
        = 
     (k+1)/α_n×(1 + 1/k)^α_n
       ≤2 k/α_n e^α_n/k.

This implies 2 k^*(n)/α_n e^α_n/k^*(n)≥ b n.  
This, together with the fact
that,
for u > 1, u e^1/u is an increasing function
of u, implies that, for large enough n,
k^*(n) ≥α_n b n/3.  
Since α_n = ω(1/n), this implies
that k^*(n) = ω(1).  
Combining this with (<ref>),
for large enough n

    R_k^*(n),n   ≥k^*(n)/α_n^2 e^-α_n/k^*(n)≥k^*(n)/2 α_n^2≥b n/6 α_n.

Thus n/R_k^*(n),n = O(α_n) = o(1).

Part <ref>, only if direction, α_n = O(1/n):  
We have

    || Σ_n || √(r_0,n)   = √(∑_i=1^∞1/i^1+α_n)≥√(1/α_n),

so || Σ_n || √(r_0,n/n)≥√(1/α_n n), which is 
bounded below by a constant for large n if 
α_n = O(1/n).

Part <ref>, only if direction, α_n = Ω(1):  
Recall that, in the proof of the “if” direction of
the third term, we showed that k^*(n) ≥α_n b n/3.
This implies that k^*(n)/n = Ω(α_n).

Part <ref>:
Suppose that Σ_n is benign. Then because
R_k(Σ_n)≤ p_n-k, we must have p_n=ω(n). Thus, we can restrict our attention to the sequences for which p_n = ω(n) and find the necessary and sufficient conditions for that class.

Next, for any positive α and any natural number
k ∈ [1, p_n), we can write 


    ∫_k^p_nx^-α dx ≥∑_i = k+1^p_n i^-α≥∫_k+1^p_nx^-α dx,


    F(p_n) - F(k) ≥∑_i = k+1^p_n i^-α≥ F(p_n) - F(k+1),

where 

    F(x) = 1/1-αx^1-α,   for α≠ 1,
    ln(x),   for α = 1.


As the sequence can only be benign if k^∗ = o(n), we can only consider values of k that do not exceed some constant fraction of n, e.g. n/2. 
 Since p_n = ω(n),  
 noting that, for x > 0, the
 sign of 1/1 - α x^1-α flips
 when α crosses 1,
 we can write, uniformly for all
 k ∈ [1, n/2],
 
    ∑_i = k+1^p_n i^-α = Θ_α(p_n^1-α),   for α∈ (0,1),
    Θ_α(ln(p_n/k)),    for α = 1,
    Θ_α(k^1-α),   for α > 1.
 
 Recall that we consider λ_i,n = i^-α for i ≤ p_n. 
Using the formula above, we get uniformly
for all k ∈ [1, n/2]

    r_k(Σ_n) =  Θ_α(k^α p_n^1-α),   for α∈ (0,1),
    Θ_α(kln(p_n/k)),    for α = 1,
    Θ_α(k),   for α > 1.


Recall that k^∗ = min{k: r_k(Σ_n) ≥ bn}.  We compute

    k^∗ =  Θ_α( p_n^1-1/α  n^1/α),   for α∈ (0,1),
    Θ_α(n/ln(p_n/n)),    for α = 1,
    Θ_α(n),   for α > 1.

One can see that for α > 1, k^∗ = Ω_α(n), so the sequence is not benign for  α > 1. On the other hand, k^∗ = o(n) for α≤ 1.

Next, analogously to the asymptotics for r_k(Σ), we have

    r_k(Σ_n^2) =  Θ_α(k^2α p_n^1-2α),   for α∈ (0,0.5),
    Θ_α(kln(p_n/k)),    for α = 0.5,
    Θ_α(k),   for α∈ (0.5, 1].


Since R_k = r_k(Σ)^2/r_k(Σ^2), we can write uniformly for all k ∈ [1, n/2]

    R_k =  Θ_α(p_n),   for α∈ (0,0.5),
    Θ_α(p_n/ln(p_n/k)),    for α = 0.5,
    Θ_α(k^2α - 1p_n^2 - 2α),   for α∈  (0.5, 1),
    Θ_α(ln(p_n/k)^2),   for α=1.


Now we plug in k^∗ instead of k. Recall that p_n/k^∗ = Θ_α((p_n/n)^1/α) for α∈ (0,1), and p_n/k^∗ = Θ_α(p_n/n ln(p_n/n)) for α = 1. We get


    R_k^∗ =  Θ_α(p_n),   for α∈ (0,0.5),
    Θ_α(np_n/n/ln(p_n/n)) ,    for α = 0.5,
    Θ_α(n(p_n/n)^1/α - 1),   for α∈  (0.5, 1),
    Θ_α(ln(p_n/n)^2),   for α=1.


Since p_n = ω(n), for any α∈ (0,1), R_k^∗ = ω(n). For α = 1 the necessary and sufficient for R_k^∗ = ω(n) is ln(p_n/n) = ω(√(n)). 

So far, we obtained the necessary and sufficient conditions for the
last terms to go to zero.
Now let's look at the upper bound for the
first term: since λ_1,n≡ 1, we just need r_0/n → 0. We
write, for α∈ (0,1],

    r_0 = ∑_i = 1^p_n i^-α
    =Θ_α(p_n^1-α),   for α∈ (0,1),
    Θ_α(ln p_n),   for α =1.


Thus, for α < 1, r_0(Σ_n)/n goes to zero if and only if
p_n = o(n^1/(1-α)), and for α = 1, r_0(Σ_n)/n goes to zero if and only if ln(p_n) = o(n).

Part <ref>:
Suppose that Σ_n is benign. Then because
R_k(Σ_n)≤ p_n-k, we must have p_n=ω(n). Also,
  
    (Σ_n)
              = Θ(1-e^-p_n/τ + p_nϵ_n) 
        = Θ(1 + p_nϵ_n),

and so p_nϵ_n=o(n).
Since Σ_n benign implies k^*=o(n), and hence k^*=o(p_n), we
consider k=o(p_n). In this regime,
  
    ∑_i>kλ_i
              = Θ(e^-k/τ-e^-p_n/τ
            + (p_n-k)ϵ_n) 
       ≤Θ(e^-k/τ + p_nϵ_n).

Thus, whenever k≤ p_n,
  
    r_k(Σ_n)
             ≤Θ(
            e^-k/τ+p_nϵ_n/e^-k/τ+ϵ_n).

Notice that
  
    d/dxx+p_nϵ_n/x+ϵ_n
          = ϵ_n-p_nϵ_n/(x+ϵ_n)^2
          <0,

so k^* must be large enough to make
  
    e^-k/τ+p_nϵ_n/e^-k/τ+ϵ_n=Ω(n).

Substituting k=τln(n/(p_nϵ_n))-a gives
  
    r_k(Σ_n)
             ≤Θ(
            p_nϵ_n/n + p_nϵ_n/p_nϵ_n/n + ϵ_n) 
        = Θ(
            p_nϵ_n/p_nϵ_n/n) 
        = Θ(n),

which shows that
k^*≥τln(n/(p_nϵ_n))-O(1).
Thus, if Σ_n is benign, we must have k^*=o(n), that is,
ϵ_np_n=ne^-o(n).

Conversely, assume p_n=Ω(n) and
ϵ_np_n=ne^-o(n) (that is, ln(n/(p_nϵ_n))=o(n)).
Set k=τln(n/(p_nϵ_n))-a,
for some a, which we shall see is Θ(1). Notice that
k=o(n), so p_n-k=Ω(p_n) and e^-p_n=o(e^-k). Thus,
  
    ∑_i>kλ_i
              = Θ(e^-k/τ-e^-p_n/τ
            + (p_n-k)ϵ_n) 
        = Θ(e^-k/τ + p_nϵ_n), 
    ∑_i>kλ_i^2
              = Θ(e^-2k/τ-e^-2p_n
            + (p_n-k)ϵ_n^2) 
        = Θ(e^-2k/τ + p_nϵ_n^2).

These imply
  
    (Σ_n)
              = Θ(1+p_nϵ_n), 
    
        r_k(Σ_n)
              = Θ(
            e^-k/τ+p_nϵ_n/e^-k/τ+ϵ_n) 
        = Θ(
            ap_nϵ_n/n + p_nϵ_n/ap_nϵ_n/n + ϵ_n) 
        = Θ(
            p_nϵ_n/ap_nϵ_n/n) 
        = Θ(n/a),

which shows that k^*=τln(n/(p_nϵ_n))+O(1).
Also, we have
  
    R_k(Σ_n)
              = Θ(
            (e^-k/τ+p_nϵ_n)^2/e^-2k/τ+p_nϵ_n^2) 
        = Θ(
            (p_nϵ_n/n+p_nϵ_n)^2/p_n^2ϵ_n^2/n^2+p_nϵ_n^2) 
        = Θ(p_n^2ϵ_n^2/p_n^2ϵ_n^2/n^2+p_nϵ_n^2) 
        = Θ(min{n^2,p_n }).

Combining gives
  
    R(θ̂)
          = O(ϵ_np_n+1/n
          + ln(n/(ϵ_np_n))/n
          + max{1/n,n/p_n}).

Now, it is clear that p_n=ω(n), ϵ_np_n=o(n), and
ϵ_np_n=ne^-o(n) imply that Σ_n is benign.



§ UPPER BOUND ON THE B TERM


We can control the term θ^∗^⊤ B θ^∗ in
Lemma <ref> using a standard argument.


There is a constant c, that depends only on σ_x, such that for any 1<t<n, with
probability at least 1-e^-t,
  
    θ^∗^⊤ B θ^∗≤ cθ^∗^2Σmax{√(r_0(Σ)/n),
            r_0(Σ)/n, √(t/n)}.




Note that
  
    (I - X^⊤(X X^⊤)^-1X)X^⊤   = X^⊤  - X^⊤(X X^⊤)^-1(XX^⊤ ) =0.

Moreover, for any v in the orthogonal complement to the span of
the columns of X^⊤,
  
    (I - X^⊤(X X^⊤)^-1X)v = v.

Thus, 
  
    I - X^⊤(X X^⊤)^-1X≤ 1.

Now we can apply (<ref>) to write
  
    θ^∗^⊤ B θ^∗    
         = θ^∗^⊤(I - X^⊤(X X^⊤)^-1X)Σ(I - X^⊤(X X^⊤)^-1X)θ^∗
       = θ^∗^⊤(I
          - X^⊤(X X^⊤)^-1X)(Σ -
          1/n X^⊤ X) 
            (I - X^⊤(X X^⊤)^-1X)θ^∗.

Combining with (<ref>) shows that
  
    θ^∗^⊤ B θ^∗≤Σ - 1/n X^⊤ Xθ^∗^2.

Thus, due to Theorem 9 in <cit.>,
there is an absolute constant c such that for any t > 1  with
probability at least 1-e^-t,
  
    θ^∗^⊤ B θ^∗≤ cθ^∗^2Σmax{√(r(Σ)/n),
          r(Σ)/n, √(t/n), t/n},

where 
  
    r(Σ) := (x)^2/Σ≤(Σ)/Σ
        = 1/λ_1∑_i λ_i = r_0(Σ).





§ ANOTHER LOWER BOUND


In this section, we prove 
the second paragraph of Theorem <ref>.

First, note that, without loss of generality,
|| Σ ||_2 = 1 and || θ^* || = 1,
since scaling these scales the excess risk by 
|| Σ ||_2 and || θ^* ||^2 respectively.
This implies λ_1 = 1, and we may further
assume without loss of generality that
Σ = (λ_1, λ_2,…).  Define
s = ∑_i=1^∞λ_i.  
We may also assume that

    r_0(Σ)/n
            log(1+r_0(Σ))≥ c_2

since, otherwise, the lower bound is vacuously satisfied.

Define a metric ρ over  by

    ρ(u,v) = √( (u - v)^⊤Σ (u - v) ),

so that, informally, a successful learning algorithm
achieves ρ(,θ) < √(τ_0).



Define sets S_1, S_2,... of indices as follows.  
Let S_1 = { 1 };  let S_2 = { 2,..., i_2 }, for
the least i_2 such that ∑_i=2^i_2λ_i ≥ 1.
Continue the same way as long as possible; for all j > 2, let
S_j = { i_j-1,...,i_j }, where i_j is the least index
such that ∑_i=i_j-1^i_jλ_i ≥ 1.



Definition <ref> produces Ω(n log n) sets.


For all j, ∑_i ∈ S_jλ_i < 2.  
Thus, for all k, 
∑_i ≤ i_kλ_i = ∑_j ≤ k∑_i ∈ S_jλ_i < 2 k.  
Assume for contradiction that, for k < c_2 n ln n/4, 
after S_k,
it is not possible to add any more sets.  Then
∑_i ≤ i_kλ_i < c_2 n ln n/2,
and, since no more sets can be added,
∑_i = 1^∞λ_i < 1 + c_2 n ln n/2.
We claim that, for large enough n, this contradicts the assumption that
∑_i = 1^∞λ_i/ln(1 + ∑_i = 1^∞λ_i )≥ c_2 n.
To see why, consider the function ϕ : ^+ →^+ defined
by ϕ(s) = s/ln (1 + s).  The function ϕ is
increasing for s ≥ 1, so it suffices to show that
ϕ( 1 + c_2 n ln n/2) < c_2 n,
and 

    ϕ( 1 + c_2 n ln n/2) 
           = 1 + c_2 n ln n/2/ln(2 + c_2 n ln n/2)
         = ( c_2/2 + o(1) ) n,

yielding the contradiction and completing the proof.



If the number of sets produced by the process
of Definition <ref> is finite, let d be this
finite number.  Otherwise, let d = ⌈ n ln n ⌉.


Now, informally, we, in our role as an adversary, commit to
assigning all covariates in S_j the same weight.  The
following definition formalizes this idea.

Define a mapping ϕ from ^d to  as follows.
For w ∈^d, ϕ(w) = θ where, for all
j in [d], for all i in S_j, θ_i = w_j.
For all i > i_d, θ_i = 0.


We would like to show that applying ϕ to an
L_2 packing yields a ρ-packing, which is done
in the following lemma.


For all u,v ∈^n, ρ(ϕ(u), ϕ(v)) ≥ || u - v ||.



    ρ(ϕ(u), ϕ(v))^2 
        = ∑_i λ_i (ϕ(u)_i - ϕ(v)_i)^2 
        = ∑_j ( ∑_i ∈ S_jλ_i ) (u_j - v_j)^2 
       ≥∑_j (u_j - v_j)^2.



Let A be the least-norm interpolation algorithm.  
We will bound the accuracy of A by bounding its
performance in terms of an algorithm C built using
A as a subroutine, as was done in a related context
in <cit.>.  The definition of Algorithm
C is illustrated in Figure <ref>, which is reproduced
from <cit.>.  

The definition uses the
function Q_α that rounds its input to the nearest
multiple of α.  Algorithm C applies algorithm
A to training data whose response variables have been
modified.  For each example (x,y), and
simulated artificial noise  distributed as
N(0,1), and artificial noise ζ distributed uniformly
on (-α/2,α/2), 
Algorithm C gives (x, y + Q_α() + ζ) to
A.  
The following lemma is similar to Lemma 5
of <cit.>.  One important difference is that
we show that Algorithm C approximates the linear
function parameterized by θ^*, not its discretization.


If the linear interpolant algorithm A 
has error τ from n examples 
drawn from N(0,Σ) with independent N(0,1) noise with probability
1 - δ, and

    α≤min{δ/2 n, 2 τ}

then, in the absence of noise, Algorithm C, given
n examples of the form (x,Q_α(θ^⊤ x)), 
with probability 1 - 2 δ,
achieves ρ(, θ^*)^2 ≤τ.


The proof of Lemma <ref> will be
deferred until we have proved some more lemmas.

Recall the definition of total
variation distance, d_TV(P,Q) = sup_E | P(E) - Q(E) |.
The following lemma is implicit in the proof
of Lemma 6 of <cit.>.


Let η, ν be random variables that are distributed
according to N(0,1) and let ζ be uniform over
[-α/2,α/2].  


  (a) For any y ∈, if
P_1 is the distribution of y+η
and P_2 is the distribution of 
Q_α (y + η) + ζ, we have 
d_TV(P_1, P_2) ≤α.

  (b) For any y ∈, if
P_3 is the distribution of Q_α (y + η)
and P_4 is the distribution of 
Q_α (y) + Q_α(η), 
d_TV (P_3, P_4) ≤α.



We will use the following, which is implicit
in the proof of Lemma 8 of <cit.>.


If P_1,...,P_n, Q_1,...,Q_n are probability distributions over
a domain U, and χ is a [0,1]-valued random variable
defined on U^n then

    | _∏_t P_t (χ) - _∏_t Q_t (χ) |
     ≤∑_t=1^n d_TV(P_t,Q_t).





Now, we are ready to prove Lemma <ref>.  The
proof closely follows the proof of Lemma 5 in <cit.>.

Proof (of Lemma <ref>).
Let A(X, , θ^*) be the output  of
the least-norm interpolant when the covariates are X,
the noise is , and the target is θ^*.  
Let A(X, y) be the output  of
the least-norm interpolant when the covariates are X,
and the response variables are y, and 
let (X,,θ^*) = (X, X θ^* + ) be
the input arising from covariates X, regressor θ^* and
noise .  

By assumption

    N(0,Σ)^n × N(0,1)^n
     { (X, ) 
           :
         ρ( A((X, , θ^*)), θ^*)^2 ≥τ} < δ.

Let ζ_t be a random variable with distribution U_α,
where U_α is the uniform distribution over (-α/2, α/2).
Let B be the randomized algorithm that adds noise 
ζ_t to each y_t value it receives, passes the result to
Algorithm A, and returns A's output.

Fix X, and define

    E     = {∈^n: 
          ρ( A((X, , θ^*)), θ^*)^2 ≥τ}
    
    E_1     = {y∈^n: 
          ρ( A(X,y), θ^*)^2 ≥τ}.

We have

    N(0,1)^n (E) = ( ∏_t=1^n P_1|x_t) (E_1),

where P_1|x_t is the distribution of (θ^*)^⊤ x_t + _t.

Define P_2|x_t as the distribution of
Q_α ((θ^*)^⊤ x_t + _t) + ζ_t.
From Lemma <ref>,
d_TV(P_1|x_t, P_2|x_t) ≤α.
Applying Lemma <ref> with χ as
the indicator function for E_1,

    | 
    ( ∏_t P_2|x_t) (E_1) - ( ∏_t P_1|x_t) (E_1) 
    |
     ≤α n.

Since α≤δ/2 n, this implies

    ( ∏_t P_2|x_t) (E_1)
       ≤( ∏_t P_1|x_t) (E_1)
          + δ/2 
    = N(0,1)^n (E) + δ/2.

Let P_3|x_t be the distribution of Q_α ((θ^*)^⊤ x_t + _t),
and let

    E_3 =  { (y, ζ) ∈^n ×^n:
          ρ( A(X,y + ζ), θ^*)^2 > τ}

so that

    ( ∏_t P_2|x_t) (E_1)
     = ( ∏_t ( P_3|x_t× U_α^n) ) (E_3).

Let P_4|x_t be the distribution of 
Q_α ((θ^*)^⊤ x_t) + Q_α (_t).
Applying Lemma <ref>, we get

    |
    ( ∏_t ( P_3|x_t× U_α^n) ) (E_3)
     - ( ∏_t ( P_4|x_t× U_α^n) ) (E_3)
    | 
    ≤∑_t=1^m d_TV(P_3|x_t, P_4|x_t).

From Lemma <ref>, d_TV(P_3|x_t, P_4|x_t) ≤α,
so

    ( ∏_t ( P_4|x_t× U_α^n) ) (E_3)
        ≤( ∏_t ( P_3|x_t× U_α^n) ) (E_3)
          + δ/2 
        = ( ∏_t P_2|x_t) (E_1)
          + δ/2 
       ≤ N(0,1)^n (E)
          + δ.

Averaging over the random choice of X,
the probability, for 
(X, ζ, )
distributed as N(0,Σ)^n × U_α^n × N(0,1)^n,
that
ρ(A (X, Q_α (X θ^*)
                    + Q_α ()
                    + ζ)),
         θ^*)^2 > τ, is at most

    (N(0,Σ)^n × N(0,1)^n)
     { (X, ) :
        ρ(A ((X, , θ^*), θ^*)^2 > τ}  + δ ≤  2 δ.

But A (X, Q_α (X θ^*)
                    + Q_α ()
                    + ζ) is the output of
the randomized algorithm C, so this completes the proof. 

So, informally, we have shown that if the least norm interpolant
can learn unit length weight vectors with noise and N(0,Σ)
data, then there is an algorithm C than can learn
from quantized data without noise.  The next step is to lower
bound the error of C.

Recall that we have fixed an n, that
s ∑_i=1^∞λ_i ≥ c n, and that
Σ = (λ_1, λ_2,...).  

We will use the following, which is
an immediate consequence
of Corollary <ref>.


For each row x_t of X, and each q > 1,

    (|| x_t || > q √(s)) ≤exp(-q^2/c).



The proof of the following lemma borrows heavily
from <cit.>.


If 1/α = O(n), there is a constant τ such that,
for any regression algorithm C, 
for all large enough n, if C is given
n examples of the form (X, Q_α (X θ^*)),
if the rows of X are n independent draws from N(0,Σ), 
with probability at least 1/2, its output 
 satisfies ρ(, θ^*)^2 > τ.


For τ > 0 to be chosen later,
assume for contradiction that, with probability
1/2, ρ(, θ^*)^2 ≤τ.
For an absolute constant c_3, let G be a set
of (1/τ)^ c_3 d members of the unit ball in  that
are pairwise separated by 3 √(τ) w.r.t. ρ
so that, for distinct members g,h of G,
ρ(g,h)^2 > 9 τ.  

For each X ∈^n ×∞, and each 
θ∈, define

    ϕ(X, θ)
     = 
     {[ 1  ; 0   ].

and define

    S = _X [
          ∑_θ∈ Gϕ(X, θ)
        ].

Our assumption about the learning ability of C implies that

    S ≥ |G|/2 = (1/τ)^c_3 d/2.

For any g,h ∈ G
for which Q_α (X g) = Q_α (X h),
since ρ(g,h) > 3 √(τ), it cannot be the
case that both ϕ(X, g) and ϕ(X,h) are both
1.  Thus, recalling that x_1,...,x_n are the
rows of X, and that all elements of G have length
at most 1, we have

    S     ≤_X (| { Q_α (X g): g ∈ G }|) 
        = _X (| { Q_α (X g): g ∈ G }| 
                   _max_t || x_t || < √(s))  
               + ∑_i = 1^∞_X (| { Q_α (X g): g ∈ G }| 
                     _max_t || x_t ||/s = i) 
       ≤( c_4 √(s)/α)^n
               + ∑_i = 1^∞
             (i√(s)/α)^n ×(max_t || x_t || ≥ i √(s)) 
       ≤( c_4 √(s)/α)^n
               + ∑_i = 1^∞
             (i√(s)/α)^n × 
           n e^-i^2/c_5   
       ≤ c_6 n ( c_4 √(s)/α)^n.

Since 1/α = O(n)

    |{ Q_α (X g): g ∈ G }|
     ≤exp( O(n log (n s)) )
     = exp( O(n log (n d)) )

since d = Θ(s).  Since d = Ω(n log n),
for large enough n and small enough τ, this
contradicts (<ref>), completing the proof.


Now we are ready to put everything together to prove
the second paragraph of Theorem <ref>.
By Lemma <ref>, it suffices to
prove that, for a small enough constant τ_0,
if 1/α = O(n), with probability
1/2, Algorithm C, given examples 
(x,Q_α(θ^⊤ x)), 
with probability 1/2, fails to
achieves ρ(, θ^*)^2 ≤τ_0.
By Lemma <ref>, this is the case, completing the
proof.

