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

Introduction

Despite the fundamental role of uniform convergence in statistical learning theory, most of this line of work has used other techniques to analyze the particular minimal-norm interpolator. argue that ’s proof technique is fundamentally based on uniform convergence of a surrogate predictor; study a closely related setting with a uniform convergence-type argument, but do not establish consistency. We discuss both papers in more detail in Section 4. Instead of directly analyzing the population error of a learning algorithm, a uniform convergence-type argument would control the worst-case generalization gap over a class of predictors containing the typical outputs of a learning rule. Typically, this is done because for many algorithms – unlike the minimal Euclidean norm interpolator – it is difficult to exactly characterize the learned predictor, but we may be able to say e.g. that its norm is not too large. Since uniform convergence does not tightly depend on a specific algorithm, the resulting analysis can highlight the key properties that lead to good generalization: it can give bounds not only for, say, the minimal-norm interpolator, but also for other interpolators with low norm [[, e.g.]]junk-feats, increasing our confidence that low norm – and not some other property the particular minimal-norm interpolator happens to have – is key to generalization. In linear regression, practical training algorithms may not always find the exact minimal Euclidean norm solution, so it is also reassuring that all interpolators with sufficiently low Euclidean norm generalize.

Problem Formulation

We assume that data $(X,Y)$ is generated as

where in the expectation $y=\langle x,w^{*}\rangle+\xi_{0}$ with $x\sim N(0,\Sigma)$ independent of $\xi_{0}\sim N(0,\sigma^{2})$. For an arbitrary norm $\left\lVert\cdot\right\rVert$, the minimal norm interpolator is $\hat{w}=\operatorname*{arg\,min}_{\hat{L}(w)=0}\left\lVert w\right\rVert$. For Euclidean norm specifically, the minimal norm interpolator can be written explicitly as $\hat{w}=X(XX^{T})^{-1}Y$. If there is more than one minimal norm interpolator, all of our guarantees will hold for any minimizer $\hat{w}$.

studied uniform convergence of low norm interpolators,

Clearly, when $B\geq\left\lVert\hat{w}\right\rVert$, this quantity upper-bounds the population risk of $\hat{w}$. evaluated the asymptotic limit of (2) in one particular setting. But they further speculated that a bound of the following form may hold more generally:

Generic Uniform Convergence Guarantee

To state our results, we first need to introduce some key tools.

The radius measures the size of a set in the Euclidean norm. The Gaussian width of a set $S$ can be interpreted as the number of dimensions that a random projection needs to approximately preserve the norms of points in $S$ . These two complexity measures are connected by Gaussian concentration: Gaussian width is the expected value of the supremum of some Gaussian process, and the radius upper bounds the typical deviation of that supremum from its expected value.

Note that $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ effectively splits the eigenvectors of $\Sigma$ into two disjoint parts.

We can now state our generic bound. Section 7 sketches the proof; all full proofs are in the appendix.

There exists an absolute constant $C_{1}\leq 66$ such that the following is true. Under the model assumptions in (1), let $\mathcal{K}$ be an arbitrary compact set, and take any covariance splitting $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$. Fixing $\delta\leq 1/4$, let $\beta=C_{1}\left(\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}\right)$. If $n$ is large enough that $\beta\leq 1$, then the following holds with probability at least $1-\delta$:

Application: Euclidean Norm Ball

Fix any $\delta\leq 1/4$. Under the model assumptions in (1) with $B\geq\|w^{*}\|_{2}$ and $n\gtrsim\log(1/\delta)$, for some $\gamma\lesssim\sqrt{\log(1/\delta)/n}$, it holds with probability at least $1-\delta$ that

The effective ranks of a covariance matrix $\Sigma$ are

There exists an absolute constant $C_{1}\leq 66$ such that the following is true. Under (1), pick any split $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$, fix $\delta\leq 1/4$, and let $\gamma=C_{1}\left(\sqrt{\frac{\log(1/\delta)}{r(\Sigma_{2})}}+\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}\right)$. If $B\geq\|w^{*}\|_{2}$ and $n$ is large enough that $\gamma\leq 1$, the following holds with probability at least $1-\delta$:

In order to use Corollary 1 or 2 to prove consistency, we need a high-probability bound for $\left\lVert\hat{w}\right\rVert_{2}$, the norm of the minimal norm interpolator, so that $B$ will be large enough to contain any interpolators. Theorem 2 gives exactly such a bound, showing that if the effective ranks $R(\Sigma_{2})$ and $r(\Sigma_{2})$ are large, then we can construct an interpolator with Euclidean norm nearly $\|w^{*}\|_{2}+\sigma\sqrt{n/\operatorname{Tr}(\Sigma_{2})}$.

Fix any $\delta\leq 1/4$. Under the model assumptions in (1) with any choice of covariance splitting $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$, there exists some $\epsilon\lesssim\sqrt{\frac{\log(1/\delta)}{r(\Sigma_{2})}}+\sqrt{\frac{\log(1/\delta)}{n}}+\frac{n\log(1/\delta)}{R(\Sigma_{2})}$ such that the following is true. If $n$ and the effective ranks are such that $\epsilon\leq 1$ and $R(\Sigma_{2})\gtrsim\log(1/\delta)^{2}$, then with probability at least $1-\delta$, it holds that

Plugging in estimates of $\|\hat{w}\|$ to our scale-sensitive bound Corollary 2, we obtain a population loss guarantee for $\hat{w}$ in terms of effective ranks.

Fix any $\delta\leq 1/2$. Under the model assumptions in (1) with any covariance splitting $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$, let $\gamma$ and $\epsilon$ be as defined in Corollaries 2 and 2. Suppose that $n$ and the effective ranks are such that $R(\Sigma_{2})\gtrsim\log(1/\delta)^{2}$ and $\gamma,\epsilon\leq 1$. Then, with probability at least $1-\delta$,

From (7), we can see that to ensure consistency, i.e. $L(\hat{w})\to\sigma^{2}$, it is enough that $\gamma\to 0$, $\epsilon\to 0$, and $\|w^{*}\|_{2}\sqrt{\frac{\operatorname{Tr}(\Sigma_{2})}{n}}\to 0$. Recalling the definitions of the various quantities and using that $r(\Sigma_{2})^{2}\geq R(\Sigma_{2})$ [66, Lemma 5], we arrive at the following conditions.

As $n\to\infty$, $L(\hat{w})$ converges in probability to $\sigma^{2}$ if there exists a sequence of covariance splits $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ such that

Our set of sufficient conditions above subsumes and is slightly more general than the conditions of . There are two differences:

They choose the covariance split specifically to minimize $\operatorname{rank}(\Sigma_{1})$ such that $r(\Sigma_{2})\gtrsim n$.

Their version of the second condition replaces $\operatorname{Tr}(\Sigma_{2})$ by the larger term $\operatorname{Tr}(\Sigma)$.

From the perspective of showing $L(\hat{w})\to\sigma^{2}$, the first difference is immaterial: if there exists a choice of split that satisfies our conditions, it can be shown that there exists a (possibly different) split which will also satisfy $r(\Sigma_{2})\gtrsim n$ (see Section D.2.1). The second point is a genuine improvement over the consistency result of when $\Sigma$ has a few very large eigenvalues; this improvement has also been implicitly obtained by .

Regarding the rate of convergence, our additional $r(\Sigma_{2})^{-1/2}$ term and the dependence on $\sqrt{\operatorname{rank}(\Sigma_{1})/n}$ instead of $\operatorname{rank}(\Sigma_{1})/n$ is slightly worse than that of , but our bound can be applied for a smaller value of $\operatorname{rank}(\Sigma_{1})$ and is better in the $\|w^{*}\|_{2}\sqrt{\operatorname{Tr}(\Sigma_{2})/n}$ term. We believe these differences are minimal in most cases, and not so important for our primary goal to showcase the power of uniform convergence.

The consistency result of can also be recovered with a uniform convergence-based argument . Instead of considering uniform convergence over a norm ball, applied uniform convergence to a surrogate predictor, and separately showed that the minimal-norm interpolator has risk close to the surrogate (and, indeed, argue that this was fundamentally the proof strategy of all along). Their analysis reveals an interesting connection between realizability and interpolation learning, but it does not highlight that low norm is key to good generalization, nor does it predict the worst-case error for other low-norm interpolators.

recently showed that it is impossible to find a tight excess risk bound that only depends on the learned predictor and sample size. This does not, however, contradict our results. A closer look at the construction of their lower bound reveals that the excess risk bounds being ruled out cannot depend on either the training error $\hat{L}$ or the population noise level $\sigma^{2}$. The former is crucial: their considered class of bounds cannot incorporate the knowledge that the training error is small, which is the defining property of uniform convergence of interpolators. The latter point is also important; they consider excess risk ($L-\sigma^{2}$), but ($\star$ ‣ 2) and our bounds are about the generalization gap ($L-\hat{L}$).

give expressions for the asymptotic generalization error of predictors in a norm ball, in a random feature model. Their model is not directly comparable to ours (their labels are effectively a nonlinear function of their non-Gaussian random features), but they similarly showed that uniform convergence of interpolators can lead to a non-vacuous bound. It is unclear, though, whether uniform convergence of low-norm interpolators can yield consistency in their model: they only study sets of the form $\{\left\lVert w\right\rVert\leq\alpha\left\lVert\hat{w}\right\rVert\}$ with $\alpha>1$ a constant, where we would expect a loss of $\alpha^{2}\sigma^{2}$ – i.e. would not expect consistency. They also rely on numerical methods to compare their (quite complicated) analytic expressions. It remains possible that the gap between uniform convergence of interpolators and the Bayes risk vanishes in their setting as $\alpha$ approaches 1.

General Norm Ball

The Euclidean norm’s dual is itself; for it and many other norms, $\partial\left\lVert u\right\rVert_{*}$ is a singleton set. Using these notions, we will now give versions of the effective ranks appropriate for generic norm balls.

The effective $\left\lVert\cdot\right\rVert$-ranks of a covariance matrix $\Sigma$ are given as follows. Let $H\sim N(0,I_{d})$, and define $v^{*}=\operatorname*{arg\,min}_{v\in\partial\|\Sigma^{1/2}H\|_{*}}\left\lVert v\right\rVert_{\Sigma}$. Then

The choice of $R_{\left\lVert\cdot\right\rVert}$ arises naturally from our bound on $\left\lVert\hat{w}\right\rVert$ in Theorem 4 below. Large effective rank of $\Sigma_{2}$ means the sub-gradient $v^{*}$ of $\|\Sigma_{2}^{1/2}H\|_{*}$ is small in the $\lVert\cdot\rVert_{\Sigma_{2}}$ norm. This is, in fact, closely related to the existence of low-norm interpolators. First, note that $\Sigma_{2}^{1/2}H$ corresponds to the small-eigenvalue components of the covariate vector. For $v^{*}$ to be a sub-gradient means that moving the weight vector $w$ in the direction of $v^{*}$ is very effective at changing the prediction $\langle w,X\rangle$; having small $\lVert\cdot\rVert_{\Sigma_{2}}$ norm means that moving in this direction has a very small effect on the population loss $L(w)$. Together, this means the sub-gradient will be a good direction for benignly overfitting the noise.

Using the general notion of effective ranks, we can find an analogue of Corollary 2 for general norms.

There exists an absolute constant $C_{1}\leq 66$ such that the following is true. Under the model assumptions in (1), take any covariance splitting $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ and let $\left\lVert\cdot\right\rVert$ be an arbitrary norm. Fixing $\delta\leq 1/4$, let $\gamma=C_{1}\left(\sqrt{\frac{\log(1/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}+\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}\right)$. If $B\geq\|w^{*}\|$ and $n$ is large enough that $\gamma\leq 1$, then the following holds with probability at least $1-\delta$:

let $\epsilon=C_{2}\left(\sqrt{\frac{\log(1/\delta)}{r_{\left\lVert\cdot\right\rVert}(\Sigma_{2})}}+\sqrt{\frac{\log(1/\delta)}{n}}+(1+\epsilon_{1})^{2}\frac{n}{R_{\left\lVert\cdot\right\rVert}(\Sigma_{2})}+\epsilon_{2}\right)$. Then if $n$ and the effective ranks are large enough that $\epsilon\leq 1$, with probability at least $1-\delta$, it holds that

Straightforwardly combining Corollaries 3 and 4 yields the following theorem, which gives guarantees for minimal-norm interpolators in terms of effective rank conditions. Just as in the Euclidean case, we can extract from this result a simple set of sufficient conditions for consistency of the minimal norm interpolator.

Fix any $\delta\leq 1/2$. Under the model assumptions in (1), let $\left\lVert\cdot\right\rVert$ be an arbitrary norm and pick a covariance split $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$. Suppose that $n$ and the effective ranks are sufficiently large such that $\gamma,\epsilon\leq 1$ with the same choice of $\gamma$ and $\epsilon$ as in Corollary 3 and Theorem 4. Then, with probability at least $1-\delta$,

As $n\to\infty$, $L(\hat{w})$ converges in probability to $\sigma^{2}$ if there exists a sequence of covariance splits $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ such that

and, with the same definition of $P$ and $v^{*}$ as in Theorem 4, it holds for any $\eta>0$ that

As we see, the conditions for a minimal norm interpolator to succeed with a general norm generalize those from the Euclidean setting in a natural way. As discussed above, (14) is always satisfied for the Euclidean norm. The only remaining notable difference from the Euclidean setting is that we have two large effective dimension conditions on $\Sigma_{2}$ instead of a single one; in the Euclidean case, the condition on $R$ implies the condition on $r$.

As $n\to\infty$, $L(\hat{w})$ converges to $\sigma^{2}$ in probability if there exists a sequence of covariance splits $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ such that $\Sigma_{2}$ is diagonal and

We now consider the behavior of basis pursuit in a junk feature model similar to that of . Suppose that $\Sigma=\begin{bmatrix}\Sigma_{s}&0\\ 0&\frac{\lambda_{n}}{\log(d)}I_{d}\end{bmatrix}$, where $\Sigma_{s}$ is a fixed matrix and $\|w^{*}\|_{1}$ is fixed. Quite naturally, we choose the covariance splitting $\Sigma_{1}=\begin{bmatrix}\Sigma_{s}&0\\ 0&0\end{bmatrix}$, which has constant rank so that the first sufficient condition is immediately satisfied.

By standard results on the maximum of independent Gaussian variables [[, e.g.]]vershynin2018high, it is routine to check that

Therefore, basis pursuit will be consistent provided that $\lambda_{n}=o(n)$ and $d=e^{\omega(n)}$. To the best of our knowledge, this is the first time that basis pursuit has been shown to give consistent predictions in any setting with Gaussian covariates and $\sigma>0$. Although we show consistency, the dimension must be quite high, and the rate of convergence depends on ${n}/{\log(d)}$ and $1/\sqrt{\log(d)}$.

As in the Euclidean case, we generally do not expect basis pursuit to be consistent when $\Sigma=I_{d}$ and $w^{*}\neq 0$. However, we can expect its risk to approach the null risk $\sigma^{2}+\|w^{*}\|^{2}$ if $d=e^{\omega(n)}$; we will show this using uniform convergence (without covariance splitting).

Like our work, the results of generalize to arbitrary norms; they also consider a larger class of anti-concentrated covariate distributions than just Gaussians, as in the work of . If $\sigma=0$ and $w^{*}\in\mathcal{K}$ (i.e. the model is well-specified and noiseless), their work as well as that of can recover generalization bounds similar to our Corollary 3, but with a large leading constant.

Proof Sketches

A key ingredient in our analysis is a celebrated result from Gaussian process theory known as the Gaussian Minmax Theorem (GMT) . Since the seminal work of , the GMT has seen numerous applications to problems in statistics, machine learning, and signal processing [[, e.g.]]stojnic2013framework,deng2019model,oymak2010new,oymak2018universality. Most relevant to us is the work of , which introduced the Convex Gaussian Minmax Theorem (CGMT) and developed a framework for the precise analysis of regularized linear regression. Here we apply the GMT/CGMT to study uniform convergence and the norm of the minimal norm interpolator.

For simplicity, assume here there is no covariance splitting: $\Sigma_{2}=\Sigma$. By a change of variable and introducing the Lagrangian, we can rewrite the generalization gap as

where $Z$ is a random matrix with i.i.d. standard normal entries. By GMTWe ignore a compactness issue here, but this is done rigorously by a truncation argument in Section B.1., we can control the upper tail of the max-min problem above (PO) by the auxiliary problem below (AO), with $G,H\sim N(0,I)$:

By standard concentration results, we can expect $\|G\|_{2}^{2}/n\approx 1$ and $\|\xi\|_{2}^{2}/n\approx\sigma^{2}$, so expanding the second constraint in the AO, we obtain $\|w\|_{2}^{2}+\sigma^{2}\leq|\langle H,w\rangle|^{2}/n$. Plugging into (19), we have essentially shown that

Applying concentration on the right hand side concludes the proof sketch. In situations where the supremum does not sharply concentrate around its mean, we can apply GMT only to the small variance directions of $\Sigma$. This requires a slightly more general version of GMT, which we prove in Appendix A. We also show the additional terms contributed by the large variance components of $X$ cancel out due to Wishart concentration. This is reflected in the $\beta$ term of our theorem statement.

Since the minimal norm problem is convex-concave, we can apply the CGMT, which provides a useful direction that GMT cannot. By the same argument as above

To upper bound the infimum, it suffices to construct a feasible $w$. Consider $w$ of the form $\alpha v$ where $v\in\partial\|\Sigma^{1/2}H\|_{*}$. Plugging in the constraint, we can choose $\|w\|=\alpha=\sqrt{\sigma^{2}\left(\frac{\|\Sigma^{1/2}H\|_{*}^{2}}{n}-\|v\|_{\Sigma}^{2}\right)^{-1}}$. Rearranging the terms conclude the proof sketch when there is no covariance splitting. The general proof (in Section C.1) is more technical, but follows the same idea.

Discussion

A future direction of our work is to extend the main results to settings with non-Gaussian features; this has been achieved in other applications of the GMT , and indeed we expect that a version of ($\star$ ‣ 2) likely holds for non-Gaussian data as well. Another interesting problem is to study uniform convergence of low-norm near-interpolators, and characterize the worst-case population error as the norm and training error both grow. This could lead to a more precise understanding of early stopping, by connecting the optimization path with the regularization path. Finally, it is unknown whether our sufficient conditions for consistency in Section 5 are necessary, and it remains a challenge to apply uniform convergence of interpolators to more complex models such as deep neural networks.

Acknowledgments and Disclosure of Funding

Frederic Koehler was supported in part by E. Mossel’s Vannevar Bush Faculty Fellowship ONR-N00014-20-1-2826. Research supported in part by NSF IIS award 1764032, NSF HDR TRIPODS award 1934843, and the Canada CIFAR AI Chairs program. This work was done as part of the Collaboration on the Theoretical Foundations of Deep Learning (deepfoundations.ai).

References

References

Appendices

In the remainder of the paper, we give self-contained proofs of all results from the main text.

In Appendix A, we introduce some technical results that we will use in our analysis.

In Appendix B, we prove the main generalization bound (Theorem 1) and show its specialization to norm balls (Corollaries 1, 2 and 3).

In Appendix C, we prove upper bounds on the norm of the minimal-norm interpolator for a general norm (Theorem 4), and show applications to the Euclidean case (Theorem 2).

In Appendix D, we show how to combine the previous sets of results to give risk guarantees for the minimal norm interpolators (Theorems 3 and 5). In particular, Section D.2.1 shows the equivalence of conditions for consistency in the Euclidean norm setting.

Appendix A Preliminaries

We will first give some general results useful to the rest of the proofs. Most are standard, but a few are variations on existing results.

If $f$ is $L$-Lipschitz with respect to the Euclidean norm and $Z\sim N(0,I_{n})$, then

We also use a similar result for functions of a uniformly spherical vector [[, see]Theorem 5.1.4 and Exercise 5.1.12]vershynin2018high; we cite a result with sharp constant factor from .

The following lemma, which we will use multiple timues, says that a $o(n)$-dimensional subspace cannot align with a random spherically symmetric vector.

with probability at least $1-\delta$. Conditional on this inequality holding, we therefore have uniformly for all $s\in S$ that

with probability at least $1-\delta$. Using $n\geq 4$ gives the result. ∎

The concentration of the Euclidean norm of a Gaussian vector follows from Theorem 6; we state it explicitly below.

First we recall the standard fact [[, see e.g.]]chandrasekaran2012convex that

Because the norm is 1-Lipschitz, it follows from Theorem 6 that

Now using that $(t-1)^{2}\geq t^{2}/2-1$ shows

We recall the notation for the Loewner order on symmetric matrices: $A\preceq B$ means that $B-A$ is positive semidefinite. Let $\sigma_{\min}(A)$ denote the minimum singular value of an arbitrary matrix $A$, and $\sigma_{\max}$ the maximum singular value. Similarly, let $\lambda_{\min}(A)$ denote the minimum eigenvalue. We use $\|A\|_{\mathit{op}}=\sigma_{\max}(A)$ to denote the operator norm of matrix $A$.

Suppose $X_{1},\ldots,X_{n}\sim N(0,\Sigma)$ are independent with $\Sigma:d\times d$ a positive semidefinite matrix, $t>0$ and $n\geq 4(d+t^{2})$. Let $\hat{\Sigma}=\frac{1}{n}\sum_{i}X_{i}X_{i}^{T}$ be the empirical covariance matrix. Then with probability at least $1-\delta$,

with $\epsilon=3\sqrt{d/n}+3\sqrt{2\log(2/\delta)/n}$.

Let $X:n\times d$ be the random matrix with rows $X_{1},\ldots,X_{n}$ so that $\hat{\Sigma}=\frac{1}{n}X^{T}X$. By equality in distribution, we can take $Z:n\times d$ to have $N(0,1)$ independent entries and write $X=Z\Sigma^{1/2}$ and

By definition of singular values, from Theorem 8 the eigenvalues of $Z^{T}Z/n$ are bounded between $(1-\sqrt{d/n}-\sqrt{t^{2}/n})^{2}$ and $(1+\sqrt{d/n}+\sqrt{t^{2}/n})^{2}$. Since $1-(1-x)^{2}\leq(1+x)^{2}-1$, using the inequality $(1+x)^{2}\leq 1+3x$ for $x\in$, we have shown that

Rewriting and taking $t^{2}=2\log(2/\delta)$ gives the result. ∎

The following result is Theorem 3 of , known as the Convex Gaussian Minmax Theorem or CGMT (see also Theorem 1 in the same reference). As explained there, it is a consequence of the main result of , known as Gordon’s Theorem or the Gaussian Minmax Theorem. Despite the name, convexity is only required for one of the theorem’s conclusions.

and the Auxiliary Optimization (AO) problem

Furthermore, if we suppose that $S_{w},S_{u}$ are convex sets and $\psi(w,u)$ is convex in $w$ and concave in $u$, then $\Pr(\Phi(Z)>c)\leq 2\Pr(\phi(G,H)\geq c)$.

In other words, the first conclusion says that high probability lower bounds on the auxiliary optimization $\phi(G,H)$ imply high probability lower bounds on the primary optimization $\Phi(Z)$. Importantly, this direction holds without any convexity assumptions. Under the additional convexity assumptions, the second conclusion gives a similar comparison of high probability upper bounds.

In our analysis, we need a slightly more general statement of the Gaussian Minmax Theorem than Theorem 9: we need the minmax formulation to include additional variables which only affect the deterministic term in the minmax problem. It’s straightforward to prove this result by repeating the argument in ; below we give an alternative proof which reduces to Theorem 9, by introducing extremely small extra dimensions to contain the extra variables. Intuitively, this works because the statement of the GMT allows for arbitrary continuous functions $\psi$, with no dependence on their quantitative smoothness.

and the Auxiliary Optimization (AO) problem

Let $Z^{\prime}:(n+n^{\prime})\times(d+d^{\prime})$ be a matrix with i.i.d. $N(0,1)$ entries such that the top left $n\times d$ matrix is $Z$. Similarly, we define $G^{\prime}$ to be a $(n+n^{\prime})$-dimensional Gaussian vector with independent coordinates such that the first $n$ coordinates are $G$, and $H^{\prime}$ to be a $(d+d^{\prime})$-dimensional Gaussian vector with independent coordinates such that the first $d$ coordinates are $H$. Next, consider the augmented PO and AO:

It is clear that for a small value of $\epsilon$, the augmented problem will be close to the original problem. More precisely, for every $(w,w^{\prime})\in S_{W}$ and $(u,u^{\prime})\in S_{U}$

where $A:=(R(S_{w})+R(S_{w^{\prime}}))(R(S_{u})+R(S_{u^{\prime}}))$ is deterministic and does not depend on $\epsilon$. Similarly, it is routine to check

so by the triangle inequality and Cauchy-Schwarz inequality, we have

Similarly, from (36) and (37), it follows that

where we used (38) in the first inequality, Theorem 9 in the second inequality, and (39) in the last inequality. This holds for arbitrary $\epsilon>0$ and taking the limit $\epsilon\to 0$ shows the result, because the CDF is right continuous and the remaining terms go to zero by standard concentration inequalities (Lemmas 2 and 8). ∎

Appendix B Uniform Convergence Bounds

We will now prove the main generalization bound, as well as its special cases in norm balls and specifically Euclidean norm balls.

For convenience, we restate the definition of covariance splitting here: See 2

It follows from our definition that $\Sigma_{1}\Sigma_{2}=0$. Although our results in Appendix C requires this orthogonality condition (in particular, Lemma 8), we note that all of our results here in Appendix B continue to hold as long as $\Sigma=\Sigma_{1}+\Sigma_{2}$ and both $\Sigma_{1},\Sigma_{2}$ are positive semi-definite. To apply the Gaussian Minimax Theorem, we first formulate the generalization gap as an optimization problem in terms of a random matrix with $N(0,1)$ entries.

Under the model assumptions in (1), let $\mathcal{K}$ be an arbitrary compact set and $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$. Define the primary optimization problem (PO) as

and $Z_{1},Z_{2}$ are both $n\times d$ random matrices with i.i.d. standard normal entries independent of $\xi$ and each other. Then the generalization gap of interpolators is equal in distribution to the sum of the Bayes risk and the PO:

Recall that $L(w)=\sigma^{2}+\|w-w^{*}\|_{\Sigma}^{2}$ and $\hat{L}(w)=0$ is equivalent to $Y=Xw$. Observe that

In the same setting as Lemma 3, let $G\sim N(0,I_{n}),H\sim N(0,I_{d})$ be Gaussian vectors independent of $Z_{1},Z_{2},\xi$ and each other. With the same definition of $\mathcal{S}$, define the auxiliary optimization problem (AO) as

By introducing Lagrange multipliers, we have

By independence, the distribution of $Z_{2}$ remains the same after conditioning on $Z_{1}$ and $\xi$ and the randomness in $\Phi$ comes solely from $Z_{2}$. Since the mapping from $w$ to $(w_{1},w_{2})$ is continuous and $\mathcal{K}$ is compact, $\mathcal{S}$ is compact. To apply Theorem 10, we can take $\psi(w_{1},w_{2},\lambda)=\|w_{1}\|_{2}^{2}+\|w_{2}\|_{2}^{2}-\langle\lambda,\xi-Z_{1}w_{1}\rangle$, which is clearly continuous. The only challenge is that the domain of $\lambda$ is not compact, but we can handle it by a truncation argument. Define

and observe that $\Phi\leq\Phi_{r}$, since the minimum in the definition of $\Phi_{r}$ ranges over a smaller set. The AO associated with $\Phi_{r}$ is

We observe that the untruncated auxiliary problem $\phi$ from (43) has a completely analogous form:

This is because if $\langle H,w_{2}\rangle-\|\xi-Z_{1}w_{1}-G\|w_{2}\|_{2}\|_{2}\geq 0$ then the minimum is achieved at $\lambda=0$, and if $w_{1},w_{2}$ do not satisfy the constraint then taking $\lambda\to\infty$ sends the minimum to $-\infty$. From this formulation, we see that $\phi\leq\phi_{r}\leq\phi_{s}$ for any $r\geq s\geq 0$ since the minimum is taken over a larger set as $r$ grows, and is unconstrained in $\phi$.

The proof that $\lim_{r\to\infty}\phi_{r}=\phi$ is an exercise in real analysis, which splits into two cases:

The auxiliary problem $\phi$ is infeasible. In this case, we know that for all $(w_{1},w_{2})\in\mathcal{S}$

By compactness of $\mathcal{S}$ and continuity of the right hand side, there exists $\mu=\mu(\xi,Z_{1},G,H)<0$ (in particular, independent of $r$) such that

Since the second term is bounded and has no dependence on $r$, taking $r\to\infty$ we have $\phi_{r}\to-\infty$ as desired (since $\phi=-\infty$ by definition).

The auxiliary problem $\phi$ is feasible. In this case, we can let $(w_{1}(r),w_{2}(r))\in\mathcal{S}$ be an arbitrary maximizer achieving the objective $\phi_{r}$ for each $r\geq 0$ by compactness. By compactness again, the sequence $(w_{1}(r),w_{2}(r))_{r=1}^{\infty}$ at positive integer values of $r$ has a subsequential limit $(w_{1}(\infty),w_{2}(\infty))\in\mathcal{S}$, i.e. this point satisfies $(w_{1}(\infty),w_{2}(\infty))=\lim_{n\to\infty}(w_{1}(r_{n}),w_{2}(r_{n}))$ for some sequence $r_{n}$ satisfying $r_{n}\geq n$.

Suppose that $(w_{1}(\infty),w_{2}(\infty))$ does not satisfy the last constraint defining $\phi$, then by continuity, there exists $\mu<0$ and a sufficiently small $\epsilon>0$ such that for all $\|w_{1}-w_{1}(\infty)\|_{2}\leq\epsilon$ and $\|w_{2}-w_{2}(\infty)\|_{2}\leq\epsilon$, we have

This implies that for sufficiently large $n$, we have

so $\phi_{r_{n}}\to-\infty$ – but this is impossible, since considering any feasible element of $\phi$ we can show that $\phi_{r_{n}}\geq 0$. By contradiction, we find that $(w_{1}(\infty),w_{2}(\infty))$ is feasible for $\phi$.

By taking $\lambda=0$ in the definition of $\phi_{r}$ we have

Since $\phi_{r_{n}}\geq\phi$, the limit of $\phi_{r_{n}}$ exists and equals $\phi$. We can conclude that $\lim_{r\to\infty}\phi_{r}=\phi$ because $\phi_{r}$ is a monotone decreasing function of $r$.

By our version of the Gaussian Minmax Theorem, Theorem 10,

We introduce the negative signs here because we have originally a max-min problem instead of a min-max problem. This means the comparison theorem gives an upper bound, instead of a lower bound, on the quantity of interest.

where the last step uses continuity (from above) of probability measure and the fact that $\phi_{r}$ monotonically decreases to $\phi$ almost surely. ∎

Recall the definition of Gaussian width and radius:

It remains to analyze the auxiliary problem, which we do in the following lemma:

Let $\beta=33\sqrt{\frac{\log(32/\delta)}{n}}+18\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}$. If $n$ is sufficiently large such that $\beta\leq 1$, then with probability at least $1-\delta$, it holds that

By a union bound, the following collection of events, which together we call $\mathcal{E}$, occurs with probability at least $1-\delta$:

(Approximate isometry.) By Corollary 4, uniformly over all $w_{1}\in\Sigma_{1}^{1/2}(\mathcal{K}-w^{*})$, it holds that

(Typical norm of $G$ and $\xi$.) By Lemma 2, it holds that

(Typical size of $\langle\Sigma_{2}^{1/2}w^{*},H\rangle$.) By the standard Gaussian tail bound $\Pr(|Z|\geq t)\leq 2e^{-t^{2}/2}$, it holds that

because the marginal law of $\langle\Sigma_{2}^{1/2}w^{*},H\rangle$ is $N(0,\|w^{*}\|_{\Sigma_{2}}^{2})$.

(Gaussian process concentration.) By Theorem 6, it holds that

because $\max_{w_{2}\in\Sigma_{2}^{1/2}\mathcal{K}}|\langle u_{2},H\rangle|$ is a $\operatorname{rad}(\Sigma_{2}^{1/2}\mathcal{K})$-Lipschitz function of $H$.

From now on, the argument is conditional on the event $\mathcal{E}$ defined above. By squaring the last constraint in the definition of $\phi$ we see that

where in the last line we used (49) and the AM-GM inequality ($ab\leq a^{2}/2+b^{2}/2$). Rearranging gives the inequality

where in the second inequality we used (50) and the AM-GM inequality again, in the third inequality we used (52) and in the last inequality we used (51). This shows

Dividing through by the first two factors on the left hand side and plugging in (53) gives

We can simplify the first term by defining $\beta=(1-\gamma)^{-1}(1-\alpha)^{-2}(1-\rho)^{-2}-1$ and the second term by observing $-\frac{\sigma^{2}}{1-\gamma}\leq-\sigma^{2}$. Finally, plugging into (43) gives

by the triangle inequality, and (48) follows by (54) and (55). To deduce the explicit bound for $\beta$, first use that

and similarly $(1-\rho)^{2}\geq 1-2\rho$ to show

Provided that $2\gamma+2\alpha+2\rho<1/2$ (which implies that $\gamma,\rho<1/2$), we can use the inequality $(1-x)^{-1}\leq 1+2x$ for $x\in[0,1/2]$ to show that

We are finally ready to prove our main generalization bound:

By Lemmas 3 and 4, we show that for any $t$

By Lemma 5, the above is upper bounded by $\delta$ if we set $t-\sigma^{2}$ according to (48) with $\delta$ replaced by $\delta/2$. Observe that the $\sigma^{2}$ term cancels, and the proof is complete. ∎

We also note that in Theorem 1, there is no requirement that $w^{*}\in\mathcal{K}$, so the true function may not necessarily lie in the class even if there is no noise ($\sigma=0$).

B.2 Specialization to General Norm Balls

For convenience, we restate the general definition of effective rank.

Applying Theorem 1 to an arbitrary norm ball yield the following:

Let $\mathcal{K}=\{w:\|w\|\leq B\}$ in Theorem 1. It is easy to see that

Under our assumptions that $\gamma\leq 1$ and $\delta\leq 1/4$, using the inequality $(1+x)(1+y)\leq 1+x+2y$ for $x\leq 1$, it is routine to check that

Plugging into Theorem 1 concludes the proof. ∎

B.3 Special Case: Euclidean Norm

In the Euclidean setting, the effective ranks are defined as follows:

Due to the small difference between $r(\Sigma)$ and $r_{\left\lVert\cdot\right\rVert_{2}}(\Sigma)$, our generalization bound below requires a slightly different proof (see discussion in Section 5), but the proof strategies are exactly the same.

By the same argument, we can show that $\|w^{*}\|_{\Sigma_{2}}\leq R(\Sigma_{2}^{1/2}\mathcal{K})$ and

Plugging into Theorem 1 concludes the proof. ∎

Next, by choosing a particular covariance split, we prove the speculative bound from when the features are Gaussian:

By Theorem 1 and the same argument in proof of Corollary 2, we obtain

Let $\Sigma_{1}$ contain the largest eigenvalues, then we have

Therefore, we can pick $\gamma=(1+\beta)\left(1+6\sqrt{\frac{\log(1/\delta)}{\operatorname{rank}(\Sigma_{1})}}\right)^{2}-1$ and it is clear that

for sufficiently large $n$ and $\operatorname{rank}(\Sigma_{1})$. To balance the last two terms, we can pick a covariance split such that $\operatorname{rank}(\Sigma_{1})$ is of order $[n\log(1/\delta)]^{1/2}$, which proves the $\sqrt{\log(1/\delta)/n}$ rate. ∎

Appendix C Bounds on the Norm of the Minimal-Norm Interpolator

In this section, we will give bounds – again based on the Gaussian Minimax Theorem – for the norm of the minimal norm interpolator, first in general and then in the Euclidean case.

Similar to the analysis in the previous section, we first formulate the minimal norm as an optimization problem in terms of a random matrix with $N(0,1)$ entries. Next, we apply the Convex Gaussian Minimax Theorem.

Under the model assumptions in (1), let $\lVert\cdot\rVert$ be an arbitrary norm and $Z:n\times d$ be a matrix with i.i.d. $N(0,1)$ entries independent of $\xi$. Define the primary optimization problem (PO) as

By equality in distribution, we can write $X=Z\Sigma^{1/2}$. By the triangle inequality and two changes of variables, we have

In the same setting as Lemma 6, let $G\sim N(0,I_{n}),H\sim N(0,I_{d})$ be Gaussian vectors independent of $\xi$ and each other. Define the auxiliary optimization problem (AO) as

By introducing Lagrange multipliers, we have

By independence, the distribution of $Z$ remains the same after conditioning on $\xi$ and the randomness in $\Phi$ comes solely from $Z$. Therefore, we can apply CGMT in Theorem 9 with $\psi(w,\lambda)=\|\Sigma^{-1/2}w\|-\langle\lambda,\xi\rangle$ because $\psi$ is convex-concave, but we again have the technical difficulty that the domains of $w$ and $\lambda$ are not compact. To overcome this, we will use a double truncation argument. For any $r,t>0$, we define

Note that the optimization in $\Phi_{r}(t)$ and $\phi_{r}(t)$ now ranges over compact sets. We will also use an intermediate problem between $\Phi$ and $\Phi_{r}(t)$, defined as

We similarly define the intermediate AO as

Compared to the definition of $\phi$, we have $\langle-H,w\rangle$ instead of $\langle H,w\rangle$, but this difference is negligible because $H$ is Gaussian. It can be easily seen that the event $\Phi>t$ is the same as $\Phi(t)>t$, and the same holds for $\phi$ and $\phi(t)$. It is also clear that $\phi(t)\geq\phi_{r}(t)$ and we can connect $\phi_{r}(t)$ with $\Phi_{r}(t)$ by CGMT. It remains to show that $\Phi_{r}(t)\to\Phi(t)$ as $r\to\infty$.

By definition, $\Phi_{r}(t)\leq\Phi_{s}(t)$ for $r\leq s$. We consider two cases:

$\Phi(t)=\infty$, i.e. the minimization problem defining $\Phi(t)$ is infeasible. In this case, we know that for all $\|\Sigma^{-1/2}w\|\leq 2t$

By compactness, there exists $\mu=\mu(Z,\xi)>0$ (in particular, independent of $r$) such that

Therefore, considering $\lambda$ along the direction of $Zw-\xi$ shows that

so $\Phi_{r}(t)\to\infty$ as $r\to\infty$.

Otherwise $\Phi(t)<\infty$, i.e. the minimization problem defining $\Phi(t)$ is feasible. In this case, we can let $w(r)$ be an arbitrary minimizer achieving the objective $\Phi_{r}(t)$ for each $r\geq 0$ by compactness. By compactness again, the sequence $\{w(r)\}_{r=1}^{\infty}$ at positive integer values of $r$ has a subsequential limit $w(\infty)$ such that $\|\Sigma^{-1/2}w(\infty)\|\leq 2t$. Equivalently, there exists an increasing sequence $r_{n}$ such that $\lim_{n\to\infty}w(r_{n})=w(\infty)$.

Suppose for the sake of contradiction that $Zw(\infty)\neq\xi$, then by continuity, there exists $\mu>0$ and a sufficiently small $\epsilon>0$ such that for all $\|w-w(\infty)\|_{2}\leq\epsilon$

This implies that for sufficiently large $n$, we have

and by the same argument as in the previous case

so $\Phi_{r_{n}}\to\infty$, but this is impossible since $\Phi_{r}(t)\leq\Phi(t)<\infty$. By contradiction, it must be the case that $Zw(\infty)=\xi$. By taking $\lambda=0$ in the definition of $\Phi_{r}(t)$, we have

Since $\Phi_{r_{n}}(t)\leq\Phi(t)$, the limit of $\Phi_{r_{n}}(t)$ exists and equals $\Phi(t)$. We can conclude that $\lim_{r\to\infty}\Phi_{r}(t)=\Phi(t)$ because $\Phi_{r}(t)$ is an increasing function of $r$.

By the last part of Theorem 9 (the CGMT),

By continuity (from below) of the probability measure, and the fact that $\Phi_{r}(t)$ monotonically increases to $\Phi(t)$ almost surely, we can conclude

It remains to analyze the auxiliary problem, which we do in the following lemma:

For any covariance splitting $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$, denote $P$ as the orthogonal projection matrix onto the space spanned by $\Sigma_{2}$, and let $v^{*}=\operatorname*{arg\,min}_{v\in\partial\|\Sigma^{1/2}_{2}H\|_{*}}\left\lVert v\right\rVert_{\Sigma_{2}}$. Assume that there exists $\epsilon_{1},\epsilon_{2}\geq 0$ such that with probability at least $1-\delta/2$,

If $n$ and the effective ranks are sufficiently large such that $\epsilon\leq 1$, then with probability at least $1-\delta$, it holds that

By a union bound, the following collection of events occurs with probability at least $1-\delta/2$:

(Approximate Orthogonality.) By Lemma 1, it holds that

(Typical Norm of $G$ and $\xi$.) By Lemma 2, it holds that

(Typical Norm of $\Sigma_{2}^{1/2}H$.) By Theorem 6, it holds that

because $\|\Sigma_{2}^{1/2}H\|_{*}$ is a $\sup_{\|u\|\leq 1}\|u\|_{\Sigma_{2}}$-Lipschitz function of $H$.

To upper bound $\phi$, it suffices to construct a $w$ that satisfies the constraint. Consider $w$ of the form $s(Pv^{*})$, then $\Sigma^{1/2}w=s\Sigma^{1/2}_{2}v^{*}$. Plugging in, it suffices to choose $s$ such that

given that it is positive. By (65) and (71), we have

and using the inequality $(1+x)^{-1}\geq 1-x$, we show

Provided that $\epsilon^{\prime}\leq 1/2$ (which also guarantees that $\alpha<1$ and our definition of $s^{2}$ is sensible), we can use the inequality $(1-x)^{-1}\leq 1+2x$ for $x\in[0,1/2]$ to show that

with $\epsilon=2\epsilon^{\prime}+2\epsilon_{2}$. ∎

Finally, we are ready to prove our general norm bound.

By Lemmas 6 and 7, we show that for any $t$

By Lemma 8, the above is upper bounded by $\delta$ if we set $t-\left\lVert w^{*}\right\rVert$ according to (67) with $\delta$ replaced by $\delta/2$. Moving $\left\lVert w^{*}\right\rVert$ to the other side concludes the proof. ∎

C.2 Special Case: Euclidean Norm

For any covariance matrix $\Sigma$, it holds that

Observe that if $f(H)=\|\Sigma^{1/2}H\|_{2}$, then it can easily be checked that

and so by the Gaussian Poincaré inequality [54, Corollary 2.27], we have

Rearranging the terms proves (72). To prove (73), without loss of generality assume that $\Sigma$ is diagonal, with diagonal entries $\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{d}$. Observe that for any integer $\nu>2$, we can pad $\Sigma$ with 0’s such that $\nu$ divides $d$, and we have

In the last equality, we use the fact that for each $i$ the random variable $\left(H_{\nu(i-1)+1}^{2}+...+H_{\nu i}^{2}\right)^{-1}$ follows an inverse Chi-square distribution with $\nu$ degrees of freedom; its expectation is $(\nu-2)^{-1}$. In addition, notice that

Plugging the above estimate into our upper bound shows for any integer $\nu>2$, it holds that

We can show (73) by choosing $\nu=\lceil(2r(\Sigma))^{1/2}\rceil$:

It remains to verify (74) and (75). By (72), we can check

For any covariance matrix $\Sigma$, it holds that with probability at least $1-\delta$,

Therefore, provided that $R(\Sigma)\gtrsim\log(4/\delta)^{2}$, it holds that

where the last inequality uses that $R(\Sigma)\leq r(\Sigma)^{2}$, shown in Lemma 5 of . Using the sub-exponential Bernstein inequality again, we show with probability at least $1-\delta/2$

From Lemma 5 of , we know that the effective ranks are at least 1. This implies

Provided that $R(\Sigma)\gtrsim\log(4/\delta)^{2}$, we have

To apply Theorem 4, it is clear that $v^{*}=\frac{\Sigma_{2}^{1/2}H}{\|\Sigma_{2}^{1/2}H\|_{2}}$ and so $\|v^{*}\|_{\Sigma_{2}}=\frac{\|\Sigma_{2}H\|_{2}}{\|\Sigma_{2}^{1/2}H\|_{2}}$. By (78), it suffices to pick $\epsilon_{1}$ such that for some constant $c>0$

Finally, using the inequality $(1-x)^{-1}\leq 1+2x$ for $x\in[0,1/2]$ and (72) of Lemma 9 again, we can conclude

Appendix D Benign Overfitting

In this section, we will combine results from the previous two sections to study when interpolators are consistent.

then with large probability, $\{w:\|w\|\leq B\}$ has non-empty intersection with $\{w:Xw=Y\}$, which contains the minimal norm interpolator $\hat{w}$. Also, it is clear that $B>\|w^{*}\|$ and so by Corollary 3, it holds that

Under the model assumptions in (1), let $\left\lVert\cdot\right\rVert$ be an arbitrary norm. Suppose that as $n$ goes to $\infty$, there exists a sequence of covariance splits $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ such that the following properties hold:

Then $L(\hat{w})$ converges to $\sigma^{2}$ in probability. In other words, minimum norm interpolation is consistent.

converges to 0 by assumption. Then by Markov’s inequality, for any $\eta^{\prime}>0$, it holds that for all sufficiently large $n$

As a result, we show $\lim_{n\to\infty}\Pr(\,|L(\hat{w})-\sigma^{2}|>\eta\,)\leq\delta$ for any $\delta>0$. To summarize, for any fixed $\eta>0$, we have

and so $L(\hat{w})$ converges to $\sigma^{2}$ in probability. ∎

D.2 Euclidean Norm

The proof follows the same strategy as Theorem 5. By Theorem 2, if we choose

then with large probability, $\{w:\|w\|_{2}\leq B\}$ has non-empty intersection with $\{w:Xw=Y\}$. This intersection necessarily contains the minimal norm interpolator $\hat{w}$.

Also, it is clear that $B>\|w^{*}\|$ and so by Corollary 2, it holds that

Fix any $\eta>0$, for sufficiently small $\gamma,\epsilon$ and $\|w^{*}\|_{2}\sqrt{\frac{\operatorname{Tr}(\Sigma_{2})}{n}}$, it is clear that

From Lemma 5 of , it holds that $R(\Sigma_{2})\leq r(\Sigma_{2})^{2}$, and so the condition $R(\Sigma_{2})=\omega(n)$ implies that $r(\Sigma_{2})=\omega(\sqrt{n})=\omega(1)$. For any $\delta>0$, by the definition of $\gamma,\epsilon$ in Corollary 2 and Theorem 2 and our assumptions, the terms $\gamma,\epsilon$ and $\|w^{*}\|_{2}\sqrt{\frac{\operatorname{Tr}(\Sigma_{2})}{n}}$ can be made small enough for Equation 87 to hold with a sufficiently large $n$. By Theorem 3, we show that

Since the choice of $\delta>0$ is arbitrary, we have shown that $L(\hat{w})$ converges to $\sigma^{2}$ in probability. ∎

We compare the above conditions to the following conditions:

Obviously, the conditions in (89) imply (88), but we show in Theorem 13 that the existence of a splitting that satisfies (88) also implies the existence of a (potentially different) splitting that satisfies (89). This is one way to see that the particular choice of $k^{*}$ from can be made without loss of generality, at least if we only consider the consistency conditions.

Suppose that there exists $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ that satisfies the conditions in (88). Then there exists a $\Sigma=\Sigma^{{}^{\prime}}_{1}\oplus\Sigma^{{}^{\prime}}_{2}$ that satisfies the conditions in (89).

Denote $v$ as the vector of eigenvalues of $\Sigma$, and $v_{k}$ as the vector obtained by setting the $k$ coordinates of $v$ corresponding to $\Sigma_{1}$ to be 0. By our assumptions in (88), there exists $k=o(n)$ such that

For any $\tau\geq 0$, we let $S_{\tau}=\{i\in[d]:|v_{k,i}|\geq\tau\|v_{k}\|_{\infty}\}$ and define $v_{k,\tau}$ by setting the coordinates of $v_{k}$ in $S_{\tau}$ to be 0. For simplicity of notation, define $a=\|v_{k}\|_{1}^{2}/\|v_{k}\|_{2}^{2}$ and $b=\|v_{k}\|_{1}/\|v_{k}\|_{\infty}$. Observe that

Finally, we pick $\tau$ by setting $b/(\tau a)=(n/a)^{3/4}$. By our assumption that $a=\omega(n)$, we can check

It is clear that $\|v_{k,\tau}\|_{1}\leq\|v_{k}\|_{1}=o(n)$ and $k+|S_{\tau}|=o(n)$, so picking the covariance splitting that corresponds to $v_{k,\tau}$ concludes the proof. ∎

In this section, we illustrate the consequences of our general theory for basis pursuit. The following generalization bound for basis pursuit follows immediately from Corollary 3:

There exists an absolute constant $C_{1}\leq 66$ such that the following is true. Under the model assumptions in (1) with $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$, fix $\delta\leq 1/4$ and let $\gamma=C_{1}\left(\sqrt{\frac{\log(1/\delta)}{r_{1}(\Sigma_{2})}}+\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}\right)$. If $B\geq\|w^{*}\|_{1}$ and $n$ is large enough that $\gamma\leq 1$, then the following holds with probability at least $1-\delta$:

The following norm bound for basis pursuit follows from Theorem 4:

There exists an absolute constant $C_{2}\leq 64$ such that the following is true. Under the model assumptions in (1), let $\Sigma=\Sigma_{1}\oplus\Sigma_{2}$ such that $\Sigma_{2}$ is diagonal. Fix $\delta\leq 1/4$ and let $\epsilon=C_{2}\left(\sqrt{\frac{\log(1/\delta)}{r_{1}(\Sigma_{2})}}+\sqrt{\frac{\log(1/\delta)}{n}}+\frac{n}{r_{1}(\Sigma_{2})}\right)$. Then if $n$ and the effective rank $r_{1}(\Sigma_{2})$ are large enough that $\epsilon\leq 1$, with probability at least $1-\delta$, it holds that

Recall that $\partial\|u\|_{*}=\text{conv}\{\operatorname{sign}(u_{i})\,e_{i}:i\in\arg\max|u_{i}|\}$, where $\text{conv}(S)$ denotes the convex hull of $S$. By definition, it holds almost surely that