Universality of empirical risk minimization

Introduction

Fit the parameters via (regularized) empirical risk minimization (ERM):

As a motivating example, consider a $3$-layer network with two hidden layers of width $p$ and k:

Consider a learning procedure in which the first and last layers ${\bm{a}},{\bm{W}}$ are not learnt from data, and we learn ${\bm{\Theta}}$ by minimizing the logistic loss for binary labels $y_{i}\in\{+1,-1\}$:

(Here we use $f\circ g(\,\cdot\,)$ instead of $f(g(\,\cdot\,))$ to denote composition.) This example fits in the general framework above, with featurization map ${\bm{\phi}}({\bm{z}})=\sigma({\bm{W}}^{{\mathsf{T}}}{\bm{z}})$, function $F({\bm{u}})={\bm{a}}^{{\mathsf{T}}}\sigma({\bm{u}})$, and loss $L(\widehat{y},y)=\log(1+e^{-y\widehat{y}})$.

From the point of view of theoretical analysis, we can replace ${\bm{\phi}}({\bm{z}}_{i})$ by ${\bm{x}}_{i}$ in Eq. (2), and redefine the empirical risk in terms of the feature vectors ${\bm{x}}_{i}$:

A significant line of recent work studies the asymptotic properties of the ERM (5) under the proportional asymptotics $n,p\to\infty$ with $n/p\to{\sgamma}\in(0,\infty)$. A number of phenomena have been elucidated by these studies [BM12, TOH15, TAH18], including the design of optimal loss functions and regularizers [DM16, EK18, CM22, AKLZ20], the analysis of inferential procedures [SCC19, CMW20], and the double descent behavior of the generalization error [HMRT19, DKT19, MRSY19, GLK+20]. However, these works often assume Gaussian feature vectors or feature vectors with independent coordinates, and the generalization to dependent non-Gaussian features is an open challenge.

Needless to say, both the Gaussian assumption and the assumption of independent covariates are highly restrictive. Neither corresponds to an actual nonlinear featurization map ${\bm{\phi}}$.

On the other hand, recent work has unveiled a remarkable phenomenon in the context of random features models, i.e. for ${\bm{\phi}}({\bm{z}})=\sigma({\bm{W}}^{{\mathsf{T}}}{\bm{z}})$. Under simple distributions on the covariates ${\bm{z}}$ (for instances ${\bm{z}}$ with i.i.d. coordinates) and for certain weight matrices ${\bm{W}}$, the asymptotic behavior of the ERM problem (5) appears to be identical to the one of an equivalent Gaussian model. In the equivalent Gaussian model, the feature vectors ${\bm{x}}_{i}$ are replaced by Gaussian features:

(We refer to the next section for formal definitions.)

We stress that —in the proportional asymptotics $n\asymp p$— the test error is typically bounded away from zero as $n,p\to\infty$, and so is possibly the train error. Further, train and test error typically concentrate around different values. Existing proof techniques (for ${\bm{x}}_{i}$ Gaussian) allow to compute the limiting values of these quantities. Insight into the ERM behavior is obtained by studying their dependence on various problem parameters, such as the overparameterization ratio $p/n$ or the noise level. When we say that the the non-Gaussian and Gaussian models have the same asymptotic behavior, we mean that the limits of the test and train errors coincide. This allows transferring rigorous results proven in the Gaussian model to similar statements for more realistic featurization maps.

In each case we fit the data by minimizing the empirical risk:

The agreement between the Gaussian and non-Gaussian models is excellent.

We follow the random matrix theory literature [Tao12] and refer to this as a universality phenomenon. When universality holds, the ERM behavior is roughly independent of the features distribution, provided their covariances are matched.

Universality is a more delicate phenomenon than concentration of the empirical risk around its expectation. Indeed, as emphasized above, it holds in the high-dimensional regime in which test error and train error do not match. Establishing universality requires understanding the dependence of the empirical risk minimizer $\widehat{\bm{\Theta}}_{n}^{\bm{X}}$ on the data ${\bm{X}},{\bm{y}}$, as opposed to just bounding its distance from a population value via concentration.

Universality results for ERM were proven in the past for feature vectors ${\bm{x}}_{i}$ with independent entries [KM11, MN17, PH17, HS22]. Related results for randomized dimension reduction were obtained in [OT18]. The case of general vectors ${\bm{x}}_{i}$ is significantly more challenging. To the best of our knowledge, the first and only proof of universality beyond independent entries was given in the recent paper of Hu and Lu [HL20].

The result of [HL20] is limited to strongly convex ERM problems. Their proof uses a Lindeberg swapping argument, whereby the rows of ${\bm{X}}$ are replaced one-by-one by Gaussian rows with the same mean and covariance. This requires bounding at each step the resulting change in train error $\min_{{\bm{\Theta}}}\widehat{R}_{n}({\bm{\Theta}};{\bm{Z}},{\bm{y}})$, which the authors achieve by bounding the change in the minimizer. Strong convexity is crucial in this type of proof to control the change of minimizer under a perturbation of the cost.

Modern machine learning algorithms often use formulations that are either convex but not strongly convex, or non-convex, as in the example (4). Further, from a mathematical standpoint, there is no reason to believe that strong convexity should be the ‘right’ condition for universality.

In this paper, we present the following contributions:

Universality of test error. We prove that, under additional regularity conditions, the test error is also universal. We emphasized that these regularity conditions concern the asymptotics of the equivalent Gaussian model. Hence, they can be checked using existing techniques.

Applications. We prove that our results can be applied to feature vectors ${\bm{x}}_{i}={\bm{\phi}}({\bm{z}}_{i})$ that are obtained by two interesting classes of featurization maps: random feature models (random one-layer neural networks) and neural tangent models (obtained by the first-order Taylor expansion of two-layer neural networks).

In the next section we state our main results. Then, in Section 3, we discuss our assumptions on the data distribution and prove that they are satisfied for random features and neural tangent models. In Section 4, we demonstrate via a counter-example that universality can fail to hold without this distributional assumption. Finally, in Section 5, we outline the proof of the main result. Most of the technical work is presented in the appendices.

Main results

Throughout, the vectors $\{{\bm{x}}_{i}\}_{i\leq n}$ are i.i.d. and $\{{\bm{g}}_{i}\}_{i\leq n}{\stackrel{{\scriptstyle i.i.d.}}{{\sim}}}\mathcal{N}(\mu_{\bm{g}},\bm{\Sigma}_{\bm{g}})$. As mentioned above, we consider the proportional asymptotics $p,n\to\infty$ whereby, assuming without loss of generality $p:=p(n)$, we have

In fact most of our statements hold under the slightly more general assumption of $p/n\in[C^{-1},C]$

2 Assumptions

We will establish a general universality result under certain assumptions depending on the set ${\mathcal{S}}_{p}$, and then characterize the set ${\mathcal{S}}_{p}$ on a case-by-case basis. In Section 3 we carry out this program by explicitly determining the set ${\mathcal{S}}_{p}$ for models arising from the analysis of two-layer neural networks in the neural tangent regime.

The labels are binary: $y_{i}\in\{+1,-1\}$ with

The set ${\mathcal{C}}_{p}$ appearing in the constraint in (8) is a compact subset of ${\mathcal{S}}_{p}$.

Recall that the random vectors $\{{\bm{x}}_{i}\}_{i\leq n}$ are assumed to be i.i.d. and that $\{{\bm{g}}_{i}\}_{i\leq n}{\stackrel{{\scriptstyle i.i.d.}}{{\sim}}}\mathcal{N}({\bm{\mu}}_{\bm{g}},\bm{\Sigma}_{\bm{g}})$. We assume

Universality of the training error amounts to saying that $\widehat{R}^{\star}_{n}({\bm{X}},{\bm{y}}({\bm{X}}))$ is asymptotically distributed as $\widehat{R}^{\star}_{n}({\bm{G}},{\bm{y}}({\bm{G}}))$. Namely, the two risks are similarly distributed at their respective, random, minimizers $\widehat{\bm{\Theta}}_{n}^{\bm{X}}$ and $\widehat{\bm{\Theta}}_{n}^{\bm{G}}$ in ${\mathcal{C}}_{p}^{\textsf{k}}\subseteq{\mathcal{S}}_{p}^{\textsf{k}}$.

It is intuitively clear that for this to happen, their expectations must be close at a fixed, non-random point ${\bm{\Theta}}$ namely

Obviously, universality of the minimum of a random function is much stronger than universality of the the function evaluated at a single point, and therefore our main results require substantial technical work.

We will further discuss this assumption in Section 3. In particular, we will provide a counterexample showing that this or a similar assumption is necessary for universality to hold.

Also note that Eq. (11) states that the projections of ${\bm{x}}$ and ${\bm{g}}$ in the direction of ${\mathcal{S}}_{p}$ are K-subgaussian, which is implied if ${\bm{x}}$ and ${\bm{g}}$ are K-subgaussian.

We additionally provide an alternative for Assumption 1 which is sufficient for our results to hold, but not as straightforward to check.

for some $C(\beta,\textsf{R},\textsf{K})$ dependent only on $\beta,\textsf{R},\textsf{K}$.

3 Universality of the training error

Theorem 1 is the key technical result of this paper. While the training error is not as interesting as the test error, which is treated next, universality of the training error is more robust and we will build on it to establish universality of the test error.

The mathematical reason for the greater robustness of the training error is easy to understand. A small data perturbation, changing $\widehat{R}_{n}({\bm{\Theta}},{\bm{X}},{\bm{y}})$ to $\widehat{R}_{n}({\bm{\Theta}},{\bm{X}}^{\prime},{\bm{y}}^{\prime})$, changes the value of the minimum by at most $\sup_{{\bm{\Theta}}}|\widehat{R}_{n}({\bm{\Theta}},{\bm{X}},{\bm{y}})-\widehat{R}_{n}({\bm{\Theta}},{\bm{X}}^{\prime},{\bm{y}}^{\prime})|$, but can change the minimizer by a large amount. The situation is of course significantly simpler if the cost is strongly convex, since in that case the change of the minimizer is controlled as well.

By Assumption 2, the ERM problem is subject to the constraint ${\bm{\Theta}}\in{\mathcal{C}}_{p}^{\textsf{k}}\subseteq{\mathcal{S}}_{p}$. In order to apply this theorem to unconstrained ERM problems, or to an ERM problem in which the constraint set is not a subset of ${\mathcal{S}}_{p}$, one can proceed in three steps: $(i)$ Prove that the unconstrained minimizer belongs, with high probability, to such a set ${\mathcal{C}}_{p}^{\textsf{k}}$; $(ii)$ Deduce that the unconstrained ERM problem is equivalent to the constrained one; $(iii)$ Apply Theorem 1.

Proof technique. We outline the proof of Theorem 1 in Section 5. The proof is based on an interpolation method. Namely we consider an ERM problem with feature matrix ${\bm{U}}_{t}=\sin(t){\bm{X}}+\cos(t){\bm{G}}$ that continuously interpolates between the two cases as $t$ goes from to $\pi/2$. We then bound the change in the training error (minimum empirical risk) along this path.

This approach is analogous to the Lindeberg method [Lin22, Cha06], which was used in the context of statistical learning in [KM11] and subsequently in [MN17, OT18, HL20]. A direct application of the Lindeberg procedure would require to swap an entire row of ${\bm{X}}$ with the corresponding row of ${\bm{G}}$ and bound the effect on the minimum empirical risk (we cannot replace one entry at a time since these are dependent). We find the use of a continuous path more effective.

In [HL20], the effect of a swapping step is controlled by first bounding the change in the minimizer $\widehat{\bm{\Theta}}$. This is achieved by assuming strong convexity of the empirical risk. The bound in the change of the minimizer immediately implies a bound in the change of the minimum value.

In the non-convex setting, we face the challenge of bounding the change of the minimum without bounding the change of the minimizer. We achieve this by using a differentiable approximation of the minimum. Even after this sequence of approximations, unlike in other universality proofs, the expectation one needs to bound is not obviously small. The key technical innovation is a polynomial approximation method which we believe can be of more general applicability.

4 Universality of the test error

We will state two theorems that provide sufficient conditions for universality of the test error. The first of these theorems concerns a scenario in which near interpolators (models achieving very small training error) exist. We are interested in this scenario because of its relevance to deep learning [BMR21], and because it is very different from the strongly convex one.

It is useful to denote the set of near empirical risk minimizers:

In other words, the minimum test error over all near-interpolators is universal (provided it does not change discontinuously with the accuracy of ‘near interpolation’). The same theorem holds (with identical proof) for the maximum test error over near interpolators, and if the level is replaced with any deterministic constant.

(In the first line $\operatorname*{p-lim}$ denotes limit in probability.)

The next theorem provides alternative sufficient conditions that guarantee the universality of the test error. We emphasize that these are conditions on the Gaussian features only and it is therefore possible to check them on concrete models using existing techniques.

there exists a function $\rho(s)$ differentiable at $s=0$ such that for all $s$ in a neighborhood of ,

for any minimizers $\widehat{\bm{\Theta}}_{n}^{\bm{X}},\widehat{\bm{\Theta}}_{n}^{\bm{G}}$ of $\widehat{R}_{n}({\bm{\Theta}};{\bm{X}},{\bm{y}}({\bm{X}}))$, $\widehat{R}_{n}({\bm{\Theta}};{\bm{G}},{\bm{y}}({\bm{G}}))$, respectively.

Proof technique. The proofs of Theorems 2 and 3 are given in Appendix B and C. The basic technique can be gleaned from condition (23). We perturb the train error by a term proportional to the test error (this is only a proof device, not an actual algorithm). The test error can be related to the derivative with respect to $s$ of the resulting minimum value. The minimum value is universal by our results in the previous section. The technical challenge is therefore to control its derivative.

Checking pointwise normality

In this section we study some concrete examples for the distribution of the feature vectors ${\bm{x}}_{i}$. In each case, we characterize the set of parameter vectors ${\mathcal{S}}_{p}$ for which the pointwise normality condition of Eq. (12) holds. For simplicity of exposition, we use $\textsf{k}=\textsf{k}^{\star}=1$ throughout this section.

We first consider examples of featurization maps from the deep learning literature. Section 3.1 analyzes the featurization map that is obtained by linearizing a two-layer neural network around a random initialization. This is also known as the ‘neural tangent model.’ We establish asymptotic equivalence (in distributional sense) of ERM under the neural tangent model, to ERM under the Gaussian model with matching covariance structure. Comparable universality results were not known in this model, even in the case of convex losses. Indeed, checking the pointwise normality condition of Eq. (12) is challenging in this case.

Next, in Section 3.2, we consider the featurization map that is obtained by applying a one-layer network with random weights. This is equivalent to the ‘random features’ model of [RR07]. Pointwise normality (along the lines of Eq. (12)) and universality of the expected risk at a fixed ${\bm{\Theta}}$ for this model was first shown in [GRM+20]. Universality of test and train error for ridge regression was established in [MM19], while [HL20] proved universality of the ERM for strongly convex losses. Finally, [LGC+21] presented empirical evidence and conjectured that universality holds for a wide class of such featurization maps and loss functions.

In the setting of Section 3.2, our main contribution is the generalization of the results of [HL20] to non-convex losses.

Finally, in Section 3.3, we consider the case in which $\bm{\Sigma}^{-1/2}{\bm{x}}_{i}$ has i.i.d. entries: this is a standard model in random matrix theory. This data distribution was studied in the past mostly for convex or strongly convex losses [MN17, PH17, OT18]. The only exceptionAfter a first posting of the present manuscript, [HS22] also analyzed non-convex losses with ${\bm{x}}_{i}$ having i.i.d. entries. is provided by [KM11] which studies certain non-convex losses when $\bm{\Sigma}={\bm{I}}$.

As we will see, the set ${\mathcal{S}}_{p}$ typically excludes parameters ${\bm{\Theta}}$ that are too aligned with an element of the canonical basis. In other words, the parameters ${\bm{\Theta}}$ needs to be ‘incoherent’ with respect to the canonical basis.

In specific applications, if the constraint set ${\mathcal{C}}_{p}$ is not a subset of ${\mathcal{S}}_{p}$, in order to apply our general theorems, it will be necessary to prove that a minimizer actually belongs to ${\mathcal{S}}_{p}$. In general, this will require a case-by-case analysis. However, Section 3.4 shows that a minimizer satisfies this condition for a broad class of overparametrized models. In these cases, no further analysis is required.

where ${\bm{w}}_{i}$ are the first layer weights at initializations ${\bm{u}}_{i}^{0}={\bm{w}}_{i}$, and $p=md$. As in the rest of the paper, we assume to be given training samples $\{(y_{i},{\bm{z}}_{i})\}_{i\leq n}$ and to compute feature vectors ${\bm{x}}_{i}={\bm{\phi}}_{\textrm{NT}}({\bm{z}}_{i})$.

Here we are not concerned with the connection between the original neural network and its neural tangent model, for which we refer to the literature [JGH18, DLL+19, LXS+19, BMR21, MZ20]. We will instead focus on the neural tangent model, and show that it can be approximated by an equivalent Gaussian model. Let us emphasize once more that –despite the neural tangent approximation– the loss function which we assume for the neural tangent model is not necessarily convex.

We have the following universality result for the neural tangent model (24).

Under the additional conditions of Theorem 2, Corollary 1 or Theorem 3, the universality results for the test error stated there hold.

Theorem 4 does not hold if we relax the set ${\mathcal{S}}_{p}$ to ${\mathcal{S}}_{p}:=B_{2}^{p}(\textsf{R})$. Indeed, for ${\bm{T}}_{\bm{\theta}}=\textsf{R}/\sqrt{d}\left(\mathbf{1}_{d},0,\dots,0\right)$, the random variable ${\bm{\theta}}^{\mathsf{T}}{\bm{x}}={\bm{z}}^{\mathsf{T}}{\bm{T}}_{\bm{\theta}}\sigma^{\prime}({\bm{W}}^{\mathsf{T}}{\bm{z}})$ is not asymptotically Gaussian. Clearly, this choice of ${\bm{\theta}}$ is not in the set defined in (25).

Proof technique. We prove Theorem 4 in Appendix E by using Theorem 1. The key technical challenge is to establish that Assumption (5) for the distribution of the feature vectors ${\bm{x}}_{i}={\bm{\phi}}_{\textrm{NT}}({\bm{z}}_{i})$, cf. Eq. (24). We Stein’s method as done in [HL20] for the random features model. However, treating the neural tangent features of Eq. (24) requires extra care due to the more complex covariance structure.

2 Random features

Let ${\bm{W}}$ be the matrix whose columns are the weights ${\bm{w}}_{j}$. We have the following corollary of Theorem 1.

In Appendix F, we derive this corollary as a consequence of Theorem 1. To do so, we use a result established by [HL20] implying that the feature vectors ${\bm{x}}_{i}$ satisfy Assumption 5, for every ${\bm{W}}$ in a high probability set.

3 Linear functions of vectors with independent entries

We have therefore the following corollary of Theorem 1.

4 Controlling a minimizer in the overparametrized setting

The general universality results of Theorem 1 to Theorem 3 are stated for the ERM problem of Eq. (8), where we constrain ${\bm{\Theta}}\in{\mathcal{C}}_{p}^{\textsf{k}}\subseteq{\mathcal{S}}_{p}$, with ${\mathcal{S}}_{p}$ satisfying Assumption 5. As discussed in Remark 2.4, these theorems can be applied to unconstrained ERM problems, or to ERM problems in which the constraint set is not a subset of ${\mathcal{S}}_{p}$, by separately proving that the minimizer belongs, with high probability, to a suitable compact set ${\mathcal{C}}_{p}^{\textsf{k}}\subseteq{\mathcal{S}}_{p}$.

Assume $p/n\geq(1+\delta)$ for some $\delta>0$, $\bm{\Sigma}^{-1/2}{\bm{x}}_{i}$ have i.i.d., mean , unit variance and subgaussian entries. Further assume that there exist constants $k,K>0$ such that

Then for any $\alpha<1/8$, there exists $C>0$ depending only on $\sOmega$ such that

That is, condition (12) of Assumption 5 holds in this case. In particular, under Assumptions 1 to 4 and the subgaussian condition of Eq. (11), we have

where $\widehat{R}_{n}^{\star}$ is the optimum of the unconstrained ERM problem.

The proof of this result is deferred to Appendix D.

Necessity of pointwise normality

Let us now give a counterexample demonstrating that universality does not hold for general ERM problems, unless we restrict the optimization to subsets of ${\mathcal{S}}_{p}$ where the latter satisfies the pointwise normality condition (12).

The pointwise normality condition (12) is not satisfied for this distribution of the feature vectors ${\bm{x}}_{i}$ and this choice of ${\mathcal{S}}_{p}$. Indeed ${\bm{e}}_{1}=(1,0,\dots,0)^{{\mathsf{T}}}\in{\mathcal{S}}_{p}$. However ${\bm{e}}_{1}^{\mathsf{T}}{\bm{x}}\sim\textrm{Unif}(\{+1,-1\})$, while under the Gaussian model with the same covariance —namely, for ${\bm{g}}\sim\mathcal{N}(0,{\bm{I}}_{p})$— we have ${\bm{e}}_{1}^{\mathsf{T}}{\bm{g}}\sim\mathcal{N}(0,1)$, for all $p$. In other words, Assumption 5 does not hold in this case.

We next construct an ERM problem whose minimum value under this features distribution is different from the value under the Gaussian model. Consider the non-negative, Lipschitz continuous loss function

We then have the following minima of the two empirical risk problems:

In the non-Gaussian case, we clearly have $\widehat{R}_{n}^{\star}({\bm{X}})=0$ for all $n$, since $\widehat{R}_{n}^{\star}({\bm{X}})\geq 0$ by construction, while $\widehat{R}_{n}^{\star}({\bm{X}})\leq 0$ follows by evaluating the cost at $\widehat{\bm{\theta}}_{n}^{\bm{X}}={\bm{e}}_{1}$. Hence, ${\bm{e}}_{1}$ will be a minimizer which achieves a training loss of for all $n$. However, in the Gaussian model (defined by ${\bm{g}}_{i}\sim\mathcal{N}(0,{\bm{I}}_{p})$), there exist $c>0$, $\sgamma_{0}>0$ such that if $\sgamma\geq\sgamma_{0}$,

This can shown by a uniform convergence argument as we detail in Appendix G.1.

Proof outline for Theorem 1

We redefine the vector $\sOmega$ from our assumptions to include $\smu$ and $\widetilde{\sgamma}$: $\sOmega:=\left(\textsf{k},\textsf{k}^{\star},\sgamma,\textsf{R},\textsf{K},\textsf{K}_{r}(\cdot),\smu,\widetilde{\sgamma}\right)$. We will use $C,\widetilde{C},C^{\prime},c,C_{0},C_{1},$ …etc, to denote constants that depend only on $\sOmega$, often without explicit definition. If a constant $C$ depends additionally on some variable, say $\beta$, we write $C(\beta)$.

Under Assumption 1’ along with Assumptions 2-5, for any fixed $\alpha>0$ and any bounded differentiable function $\psi$ with bounded Lipschitz derivative we have

Here, we outline the proof of this lemma deferring several technical details to Appendix A.3 where we present the complete proof. A standard estimate bounds the difference between the free energy and the minimum empirical risk (see Appendix): For $\beta>0$.

Hence, Theorem 1 follows from Lemma 1 via an approximation argument detailed in Appendix A.

We assume, without loss of generality, that ${\bm{X}}$ and ${\bm{G}}$ are defined on the same probability space and are independent, and define the interpolating paths

for $t\in[0,\pi/2]$ and $i\in[n]$. We use ${\bm{U}}_{t}$ to denote the matrix whose $i$th row is ${\bm{u}}_{t,i}$; note that these rows are i.i.d. since the rows of ${\bm{X}}$ and ${\bm{G}}$ are so. Noting that for all ${\bm{\theta}}\in{\mathcal{S}}_{p}$, ${\bm{x}}^{\mathsf{T}}{\bm{\theta}}$ and ${\bm{g}}^{\mathsf{T}}{\bm{\theta}}$ are subgaussian with subgaussian norms bounded by RK uniformly over ${\bm{\theta}}\in{\mathcal{S}}_{p}$, it is easy to see that $\sup_{t\in[0,\pi/2],{\bm{\theta}}\in{\mathcal{S}}_{p}}\left\lVert{\bm{u}}_{t}^{\mathsf{T}}{\bm{\theta}}\right\rVert_{\psi_{2}}\leq 2\textsf{R}\textsf{K}.$

It is convenient to define the probability mass function over ${\bm{\Theta}}_{0}\in\mathcal{N}_{\alpha}^{\textsf{k}}$:

for $i\in[n]$. With this notation, we can write

Via a leave-one-out argument detailed in Appendix A.3, we show that this form allows us to control

where $\left\langle\;\cdot\;\right\rangle_{{\bm{\Theta}}_{1}^{j}}$ is the expectation respect $\{{\bm{\Theta}}_{l}\}_{l\leq[j]}$ seen as independent samples from $p^{(1)}({\bm{\Theta}};t)$. The next lemma then states that the right-hand side in (40) can be controlled via its Gaussian equivalent.

from which the statement of Lemma 1 can be deduced.

Acknowledgements

This work was supported by the NSF through award DMS-2031883, the Simons Foundation through Award 814639 for the Collaboration on the Theoretical Foundations of Deep Learning, the NSF grant CCF-2006489, the ONR grant N00014-18-1-2729, and an NSF GRFP award.

References

Appendix A Proof of Theorem 1

In this section, we complete the proof of Theorem 1 by deducing it from Lemma 1 and give a complete proof of this lemma.

Recall that for $\alpha>0$, in Section 5 we let $\mathcal{N}_{\alpha}$ be a minimal $\alpha-$net of ${\mathcal{C}}_{p}\subseteq B_{2}^{p}(\textsf{R})$, so that $|\mathcal{N}_{\alpha}|\leq C(\alpha)^{p}$ for some $C(\alpha)$ depending only on $\alpha$ and $\sOmega$. Let us define the discretized minimization over ${\bm{\Theta}}\in\mathcal{N}_{\alpha}^{\textsf{k}}$

We have the following consequence of Lemma 1.

Under Assumption 1’ along with Assumptions 2-5, we have for any bounded differntiable function $\psi$ with bounded Lipschitz derivative

The proof of this result is deferred to Section A.2. Here, we show that Theorem 1, under the alternative Assumption 1’ is a direct consequence of this lemma. First, we need a few technical lemmas. Let us define the restricted operator norm

For ${\bm{X}},{\bm{G}}$ as in Assumption 5, we have for some $C\in(0,\infty)$ depending only on $\sOmega$,

Under Assumptions 1’, 3, 4 and 5, we have for all ${\bm{\Theta}},\widetilde{\bm{\Theta}}\in{\mathcal{S}}_{p}^{\textsf{k}}$

for some $C>0$ depending only on $\sOmega$. A similar bound also holds for the Gaussian model.

The proofs are deferred to Sections G.2 and G.3 respectively. Here, we derive Theorem 1.

where in $(a)$ we used Lemma 5 and in $(b)$ the subgaussianity conditions in Assumptions 1 and 5 along with the condition on $\eta$. An analogous argument then shows that

where the last equality is by Lemma 4. Now using that $\left\lVert\psi^{\prime}\right\rVert_{\infty}<\infty$ and sending $\alpha\to 0$ concludes the proof of Eq. (16) for $\psi$ bounded differentiable with bounded Lipschitz derivative. To extend it to $\psi$ bounded Lipschitz, it is sufficient to find a sequence of bounded differentiable functions with bounded Lipschitz derivative approximating $\psi$ uniformly (see for example the following section for a similar argument).

A.1.2 Proof of Eq. (16) of Theorem 1 under Assumption 1

The proof under Assumption $1$ $(a)$ and $(b)$ is via an approximation argument. The proof under $(a)$ is a straightforward modification of that under $(b)$, hence, we omit the former and only prove the latter.

is infinitely differentiable (see [Eva10], Appendix C.4.). Additionally, we have the following properties of $f_{\delta}$.

for some $C>0$. Then for $\delta\in(0,1)$, we have

for some $\bar{C},\widetilde{C}>0$. Furthermore, if for some positive integer $l<m$, $f$ satisfies

Optimizing over ${\bm{s}}$ gives the claim. Meanwhile, the bound in (46) is obtained as

Finally, the last property is obtained via a similar argument, namely,

Now for the labels $y_{i}({\bm{x}}_{i})$, note that we can write $y_{i}({\bm{x}}_{i})\stackrel{{\scriptstyle d}}{{=}}\chi(g({\bm{\Theta}}^{\star{\mathsf{T}}}{\bm{x}}_{i})-\epsilon_{i})$ where $\epsilon_{i}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}\textrm{Unif}()$ for $i\in[n]$ and

Once again, $\eta_{\delta}$ is locally Lipschitz, differentiable and has

where in $(a)$ we used that $\chi^{\prime}_{\delta}$ is continuous and supported on a bounded interval, along with Lemma 7 applied to $(g,g_{\delta})$. This implies that $\eta_{\delta}$ satisfies the conditions on the labeling function in Assumption 1’. Furthermore, $\epsilon_{i}$ are i.i.d. subgaussian, and finally, we have for all $\beta>0$, and random variables ${\bm{v}},{\bm{v}}^{\star},V$ as in Eq. (14),

For any $\delta\in(0,1)$ and bounded Lipschitz test functions $\varphi$, there exists a constant $C>0$ depending only on $\sOmega$ such that

where ${\bm{\eta}}_{\delta}({\bm{X}};{\bm{\epsilon}})=\left(\eta_{\delta}({\bm{\Theta}}^{\star{\mathsf{T}}}{\bm{x}}_{i},\epsilon_{i})\right)_{i\in[n]}.$

Let $\widehat{\bm{\Theta}}$ and $\widehat{\bm{\Theta}}_{\delta}$ denote the minimizers of $\widehat{R}_{n}({\bm{\Theta}};{\bm{X}},{\bm{y}}({\bm{X}}))$ and $\widehat{R}_{n}^{\delta}({\bm{\Theta}};{\bm{X}},{\bm{\eta}}_{\delta}({\bm{X}}))$ respectively. Since $\varphi$ is Lipschitz, it is sufficient to bound

for $C>0$ depending only on $\sOmega$. First, let us obtain an upper bound on

For the term in (53), letting $\{\widehat{\bm{\theta}}_{\delta,j}\}_{j\in[\textsf{k}]}$ be the columns of $\widehat{\bm{\Theta}}_{\delta}$,

By symmetry, we can obtain a similar lower bound on the left-hand side of (54) (by replacing $\widehat{\bm{\Theta}}_{\delta}$ throughout with $\widehat{\bm{\Theta}}$), which allows us to write

for large enough $n$ and $C_{2},C_{3}>0$ depending only on $\sOmega$ . Here, in $(a)$ we used Lemma 5.

To conclude the proof, we show that the expectation on line (55) is bounded by a positive constant times $\delta$. This follows via the following computation:

for some $C_{4},C_{5}>0$ depending only on $\sOmega$. Here, in $(a)$ we used $\chi_{\delta}(t)=1$ for all $t\geq\delta$ and $-1$ for all $t\leq\delta$, in $(b)$ we used Lemma 7 with $(g,g_{\delta})$, and in $(c)$ we used subgaussianity of ${\bm{x}}_{i}$.

A.1.3 Proof of the bounds in Eq. (17) of Theorem 1

and that$\left\lVert\chi_{\delta,\rho}\right\rVert_{\mbox{\tiny\rm Lip}}=C(\delta)$ for some constant depending only on $\delta$. Hence, we can apply (16) with $\psi(t)=\chi_{\delta}(t-\rho)$ to conclude

which establishes the first bound in (17). The second bound follows via a similar argument. ∎

A.2 Universality of the minimum over the discretized space: Proof of Lemma 4

Recall the minimization problem over the set $\mathcal{N}_{\alpha}^{\textsf{k}}$ defined in (42). We show in this section that Lemma 4 is a direct consequence of Lemma 1.

Fix $\alpha>0$. Let us first bound the derivative of the free energy. Define the probability mass function for ${\bm{\Theta}}\in\mathcal{N}_{\alpha}^{\textsf{k}}$,

and define similalry $p({\bm{\Theta}};{\bm{G}},t)$ for the Gaussian model. Recall that the Shannon entropy of a distribution $H(p(\,\cdot\,;{\bm{X}},t)):=-\sum_{{\bm{\Theta}}\in\mathcal{N}_{\alpha}^{\textsf{k}}}p({\bm{\Theta}};{\bm{X}},t)\log p({\bm{\Theta}};{\bm{X}},t)$ satisfies

where $C_{0}$ depends only on $\alpha,\textsf{R}$ and $\sOmega$. Therefore, the derivative of the free energy with respect to $t$ can be bounded as

Clearly, a similar bound holds with ${\bm{G}}$ replacing ${\bm{X}}$. Hence, we have

where $(a)$ follows from Lemma 1 along with the assumption that $p(n)/n\to\sgamma$. Sending $\beta\to\infty$ completes the proof. ∎

A.3 Complete proof of universality of the free energy: Proof of Lemma 1

Let us recall the interpolating paths ${\bm{u}}_{t,i}:=\sin(t)\left({\bm{x}}_{i}-{\bm{\mu}}_{\bm{g}}\right)+\cos(t)\left({\bm{g}}_{i}-{\bm{\mu}}_{\bm{g}}\right)+{\bm{\mu}}_{\bm{g}}$ and $\widetilde{\bm{u}}_{t,i}:=\cos(t)\left({\bm{x}}_{i}-{\bm{\mu}}_{\bm{g}}\right)-\sin(t)\left({\bm{g}}_{i}-{\bm{\mu}}_{\bm{g}}\right)$ defined in (35) for $t\in[0,\pi/2]$ and $i\in[n]$, and the associated matrix ${\bm{U}}_{t}$ whose $i$th row is ${\bm{u}}_{t,i}$. Further, recall the gradient notation introduced in Section 5:

Finally, recall the probability mass function and its associated expectation defined in (37)

where all sums are implicitly over $\mathcal{N}_{\alpha}$; the minimal $\alpha-$net of ${\mathcal{C}}_{p}$ introduced in Section 5.

where $f_{\alpha}(\beta,\cdot)$ is the free energy defined in (34).

Using the interpolator ${\bm{U}}_{t}$, we can write

where $(a)$ follows via an application of the dominated convergence theorem along with Lemma 9. So it is sufficient to show that for all $t\in[0,\pi/2]$,

With the notation previously defined, we can compute the deriative of the free energy as

Since our goal is to establish (59), let us fix some $t\in[0,\pi/2]$ and suppress it in the notation. We use the previous display to bound the expectation of the derivative as

The term in (60) can be controlled via a simple leave-one-out argument. Indeed, since the samples are i.i.d, it is sufficient to control the term $i=1$ in the sum:

Meanwhile, to control the term (61), it is sufficient to establish that

To see that this is sufficient, note that with (62), we can control (61) as

where $(a)$ follows by the i.i.d assumption on the samples and $(b)$ follows by reverse Fatou’s and Lemma 9.

In order to prove (59), fix $\delta>0$ and let $P(s):=\sum_{j=0}^{M}b_{j}s^{j}$ be the polynomial from Lemma 2, where $b_{j}$ and $M>0$ depend only on $\beta,\delta$ and $\sOmega$. Then the this lemma yields the bound

where $(a)$ is the statement of Lemma 2 and in $(b)$ we defined the expectation $\left\langle\;\cdot\;\right\rangle_{{\bm{\Theta}}_{1}^{j}}$ with respect to $j$ independent samples from $p^{(1)}({\bm{\Theta}};t)$. Now recall the definitions of $\widetilde{\bm{g}}_{1},\widetilde{\epsilon}_{1},{\bm{w}}_{1},\widetilde{\bm{w}}_{1}$ and $\widehat{\bm{q}}_{1}({\bm{\Theta}}_{0})$ from Lemma 3. Note that ${\bm{w}}_{1}$ and $\widetilde{\bm{w}}_{1}$ are jointly Gaussian with means

for all $t\in[0,\pi/2]$, and hence they are independent. And since $\widetilde{\bm{w}}_{1}$ is independent of $\widetilde{\epsilon}_{1}$ by definition, the assertion of Lemma 3 implies that the summands in (63) converge to . Indeed, for $j\in[M]$:

where in $(a)$ we applied Lemma 3, in $(b)$ we used the independence of $\widetilde{\bm{w}}_{1}$ and ${\bm{w}}_{1}$ and in $(c)$ we used that the mean of $\widetilde{\bm{w}}_{1}$ is . Combining this with the bound in (63) yields, for all $\delta>0$,

Taking $\delta\to 0$ then establishes (62) for any $t\in[0,\pi/2]$ and concludes the proof. ∎

Appendix B Proof of Theorem 2

for all $t\geq 0$, where we set the value of the minimum to $\infty$ whenever the constraints are not feasible. First we give the following lemma.

For all $t\geq s>0$ and any $\delta>0$, we have

Fix $t\geq s>0$. On ${\mathcal{G}}_{n,s}$, let

be any minimizers of the respective functions so that $F_{n}^{\bm{x}}(t,{\bm{X}})=R_{n}^{\bm{x}}(\widehat{\bm{\theta}}_{\bm{x}})$ and $F_{n}^{\bm{g}}(t,{\bm{X}})=R_{n}^{\bm{g}}(\widehat{\bm{\theta}}_{\bm{g}})$. Then note that we can upper bound

where in $(a)$ we used that $R_{n}^{\bm{g}}(\widehat{\bm{\theta}}_{\bm{g}})\leq R_{n}^{\bm{g}}(\widehat{\bm{\theta}}_{\bm{x}})$ on ${\mathcal{G}}_{n,s}$. An analogous argument with the roles of ${\bm{x}}$ and ${\bm{g}}$ exchanged shows that we also have

where $(a)$ follows from the subgaussianity in Assumption 5 and the assumption on the labels and noise in Assumption 1, and hence a similar bound holds for $F_{n}^{\bm{x}}(t,{\bm{X}})\mathbf{1}_{{\mathcal{G}}_{n,\alpha_{0}}}$ and $F_{n}^{\bm{g}}(t,{\bm{G}})\mathbf{1}_{{\mathcal{G}}_{n,\alpha_{0}}}$. Now define

on ${\mathcal{G}}_{n,\alpha_{0}}$. Letting $\widehat{\bm{\theta}}^{\bm{X}}_{s}$ denote a minimizer of this problem we write

where in $(a)$ we used that $F_{n}^{\bm{g}}(t,{\bm{X}})$ is nonincreasing in $t$ and the definition of $s$, and in $(b)$ that $C^{\prime}\geq F_{n}^{\bm{g}}(\alpha,{\bm{X}})$ by (67). Meanwhile we can obtain an upper bound for

Hence, for $s=C^{\prime}/\alpha$ and $\alpha_{0}\leq\alpha$, we have

Using a similar argument with the roles of ${\bm{X}}$ and ${\bm{G}}$ exchanged gives the second statement.

Appendix C Proof of Theorem 3

We prove the statement under each condition separately in the subsections that follow. We will use $\textsf{k}=1$ for simplicity, and without losing generality, since the arguments that follow can be directly extended to the setting where $\textsf{k}>0$ as long as it is a fixed constant.

(note the asymmetry), and use $\widehat{\bm{\theta}}_{s}^{\bm{X}},\widehat{\bm{\theta}}_{s}^{\bm{G}}$ to denote their unique minimizers respectively. Furthermore, we write $\widehat{R}_{n,s}^{\star}({\bm{X}},{\bm{y}}({\bm{X}}))$ and $\widehat{R}_{n,s}^{\star}({\bm{G}},{\bm{y}}({\bm{G}}))$ for the minima.

First, we show that the convexity assumptions imply the following lemma.

for some $C>0$ depending only on $\sOmega$. A similar inequality also holds for $\widehat{\bm{\theta}}_{s}^{\bm{G}}$.

where $(a)$ follows from the KKT conditions for $\widehat{R}_{n}$; namely, for some $\lambda\geq 0$, we have

where $(a)$ follows by noting that $\widehat{\bm{\theta}}_{s}^{\bm{X}}$ minimizes $\widehat{R}_{n,s}({\bm{\theta}};{\bm{X}},{\bm{y}}({\bm{X}}))$, and $(b)$ follows since $R^{\bm{g}}_{n}({\bm{\theta}})$ is Lipschitz with bounded Lipschitz modulus under Assumption 1: Indeed we have

Combining the upper and lower bounds and rearranging gives

This proves the lemma for ${\bm{X}}$. A similar argument clearly holds for the Gaussian model. ∎

Now let us define, for $s\neq 0$, the differences

where in $(a)$ we used $\widehat{R}_{n}(\widehat{\bm{\theta}}^{\bm{X}}_{-s};{\bm{X}},{\bm{y}}({\bm{X}}))\geq\widehat{R}_{n}(\widehat{\bm{\theta}}^{\bm{X}}_{0};{\bm{X}},{\bm{y}}({\bm{X}}))$ and $\widehat{R}_{n}(\widehat{\bm{\theta}}^{\bm{X}}_{s},{\bm{X}})\geq\widehat{R}_{n}(\widehat{\bm{\theta}}^{\bm{X}}_{0},{\bm{X}})$, in $(b)$ we used that that $R_{n}^{\bm{g}}({\bm{\theta}})$ is Lipschitz with bounded Lipschitz modulus and in $(c)$ we used Lemma 11. A similar argument then shows the same property for $D^{\bm{G}}(s)$.

First, note that that for $s>0$, $R_{n}^{\bm{g}}(\widehat{\bm{\theta}}_{0}^{\bm{X}})$ is sandwhiched between $D^{\bm{X}}(s)$ and $D^{\bm{X}}(-s)$. Indeed, we have

For any $\delta>0$, take $s_{\delta}\in(0,\delta/C))$ where $C$ is the constant appearing in Eq. (73) of Lemma 12 and write

To conclude the proof, note that Lemma 30 implies that

C.2 Proof of Theorem 3 under the condition b

Let $\mathcal{A}_{n,\delta,\alpha}$ be the event in condition b, namely,

and take $\widehat{\bm{\theta}}_{n}^{\bm{G}}$ and $\widehat{\bm{\theta}}_{n}^{\bm{X}}$ to be any minimizers of $\widehat{R}_{n}({\bm{\theta}};{\bm{G}},{\bm{y}}({\bm{G}}))$ and $\widehat{R}_{n}({\bm{\theta}};{\bm{X}},{\bm{y}}({\bm{X}}))$ respectively.

C.3 Proof of Theorem 3 under the condition c

shown in (76) hold generally without the convexity assumption. Hence, using

we can write, for any $\delta>0$ and $s>0$,

for $s$ in some neighborhood of . Combining this with the previous display gives

where $(a)$ follows by differentiability of $\rho(s)$ at $s=0$. By exchanging the roles of ${\bm{X}}$ and ${\bm{G}}$ in this argument we additionally obtain

Appendix D Proof of Theorem 5

The claim of the theorem is a direct corollary of the following lemma.

Assume $p/n\geq(1+\delta)$ and that the feature vectors ${\bm{x}}_{i}$ have i.i.d. mean , unit variance and subgaussian entries. Fix $\alpha<1/8$. Then the following holds with probability at least $1-c_{1}\exp(-p^{c_{2}})$ for some constants $c_{1}$, $c_{2}>0$: For any ${\bm{\theta}}$, there exists ${\bm{u}}={\bm{u}}({\bm{\theta}})$ such that ${\bm{X}}{\bm{u}}={\bm{X}}{\bm{\theta}}$ satisfying

for some $C>0$ depending only on $\sOmega$.

Let $m=\lceil p^{2\alpha}\rceil$ and denote by $L=L({\bm{\theta}})\subseteq[p]$ the set of indices corresponding to the $m$ entries in ${\bm{\theta}}$ with largest absolute value. Namely if $|\theta_{i(1)}|\geq|\theta_{i(2)}|\geq\cdots\geq|\theta_{i(p)}|$, then we let $L:=\{i(1),\dots,i(m)\}$ (ties are broken arbitrarily). We also let $S=S({\bm{\theta}}):=[p]\setminus L({\bm{\theta}})$ denote the set of indices of ‘small’ entries.

Note that $m\,|\theta_{i(m)}|^{2}\leq\|{\bm{\theta}}\|_{2}^{2}$, whence

Postponing the proof of this claim, we define ${\bm{u}}={\bm{u}}({\bm{\theta}})$ by

Further $\left\lVert{\bm{u}}\right\rVert_{\infty}\leq(\left\lVert{\bm{\theta}}\right\rVert_{2}+\left\lVert{\bm{\theta}}\right\rVert_{\infty})p^{-\alpha}$, and $\left\lVert{\bm{u}}\right\rVert_{2}\leq(1+C)\left\lVert{\bm{\theta}}\right\rVert_{2}$, thus proving the lemma.

We are left with the task of proving the existence of ${\bm{\eta}}={\bm{\eta}}({\bm{\theta}})$ with the properties stated above. We construct ${\bm{\eta}}$ by setting ${\bm{\eta}}_{L}={\bm{0}}$ and

This vector satisfies the condition (80) by construction, and we are therefore left with the task of proving that it satisfies the norm constraints, with the claimed probability.

Recalling that $m=\lceil p^{2\alpha}\rceil$, we define the

Here $C_{1}$ is a constant that will be specified below. On the intersection of these events, we have

where ${\bm{X}}_{s}={\bm{X}}_{\{s\}}$ is the $s$-th column of ${\bm{X}}$. We therefore have, on the event $\mathcal{A}\cap\mathcal{B}\cap\mathcal{B}_{*}\cap{\mathcal{D}}$,

In order to conclude the proof of the lemma, we need to prove that each of events $\mathcal{A}$, $\mathcal{B}$, $\mathcal{B}_{*}$, ${\mathcal{D}}$ holds with probability at least $1-c_{1}\exp(-p^{c_{2}})$, for a suitable choice of $C_{1}$.

For event $\mathcal{B}$, by Theorem 1.1 of [RV09], for any set $R$, $|R|=p-m$, we have

for $C_{3},c_{3}>0$ and any $\epsilon>0$, where $\sigma_{n}$ is the $n$-th largest singular value. Hence, for a suitable choice of $C_{1}$, $\sigma_{\min}({\bm{X}}_{R}{\bm{X}}_{R}^{{\mathsf{T}}})\geq 2p/C_{1}$ with probability at least $1-c_{0}\exp(-c_{0}^{\prime}p)$. The claim follows by taking a union bound over the $\binom{p}{m}=\exp(O(p^{2\alpha}\log p))$ choices of set $R$.

For event $\mathcal{B}_{*}$, the bound follows in the same way (the only difference being that the union bound is over $m\binom{p}{m}$ terms).

Next note that, defining ${\bm{v}}_{R,s}:=\left({\bm{X}}_{R\setminus s}{\bm{X}}_{R\setminus s}^{\mathsf{T}}\right)^{-1}{\bm{x}}_{s}$, we have

Appendix E The neural tangent model: Proof of Corollary 4

Note that ${\mathcal{S}}_{p}$ is symmetric, convex, and ${\mathcal{S}}_{p}\subseteq B_{2}^{p}(\textsf{R})$. Furthermore, for all ${\bm{\theta}}\in{\mathcal{S}}_{p}$ we have $\left\lVert{\bm{\theta}}_{(j)}\right\rVert_{2}\leq\textsf{R}/\sqrt{d}$ for all $j\in[m]$.

The key to proving Corollary 4 is showing that the distribution of the feature vectors $\{{\bm{x}}_{i}\}_{i\leq[n]}$ satisfy, on a high probability set, Assumption 5. Our proof here is analogous to that of [HL20] for the random features model. Let us begin our treatment by defining the event

For a given $\delta>0$, let us define the set

Our goal in this subsection is to prove the following lemma.

Define, for ${\bm{\theta}}\in{\mathcal{S}}_{p,\delta}$ the notation

For a fixed bounded Lipschitz function $\varphi$, let $\chi=\chi_{\varphi}$ be the solution to Stein’s equation for $\varphi$, namely, the function $\chi$ satisfying

(see [CGS11] for more on Stein’s method and properties of the solution $\chi$.). In order to prove Lemma 14, it is sufficient to show that

In Section E.1.3, we upper bound the quantity (84) as

So first, let us control the terms on the right hand side: We do this in Sections E.1.1 and E.1.2, respectively. Before doing this, we make the following definitions which will be used throughout. Define $\widetilde{\bm{\theta}}_{j,i}:={\bm{P}}_{i}^{\perp}{\bm{\theta}}_{(j)},$ along with the matrix notation

For ${\bm{W}}\in\mathcal{B}$, we have for any fixed integers $k>0$ and $l\leq 4$

for some constants $C_{i}$ depending only on $\sOmega$.

Using Lemma 21, the first five inequalities are direct. Indeed, recalling that $m/d\to\widetilde{\sgamma}$, we have

where the last equality holds because ${\bm{M}}$ is a diagonal matrix. Now recall that for the two square matrices ${\bm{W}}^{\mathsf{T}}{\bm{T}}_{\bm{\theta}}$ and ${\bm{M}}{\bm{B}}$, we have (see for example [Joh90], (3.7.9))

where $(a)$ follows using the same bound we applied to (88). This establishes the seventh bound in the lemma.

For the ninth bound, we first note that by definition of ${\bm{A}}$ and ${\bm{R}}$, ${\bm{A}}\odot{\bm{R}}={\bm{W}}^{\mathsf{T}}{\bm{T}}_{\bm{\theta}}\odot{\bm{R}}$ so that

Fix $\delta>0$ throughout. Define for convenience

Let us compute the expectation of $U$ and control its variance.

Now, we control $\text{Var}(U)$. First, note that we can write $\Delta_{i}$ as

Taylor expanding $\sigma^{\prime}$ to the third order gives

for some $v_{ij}({\bm{z}})$ between ${\bm{w}}_{j}^{\mathsf{T}}{\bm{z}}-\rho_{ij}{\bm{w}}_{i}^{\mathsf{T}}{\bm{z}}$ and ${\bm{w}}_{j}^{\mathsf{T}}{\bm{z}}$. Using this expansion and the notation $\widetilde{\bm{\theta}}_{j,i}$ defined earlier, $\Delta_{i}$ can be re-written as

Using the expansion (92) in the expression for $U$ gives

Let us write $u_{1}({\bm{z}}),u_{2}({\bm{z}}),u_{3}({\bm{z}}),u_{4}({\bm{z}})$ for the terms on the right-hand on lines (93), (94), (95), (96) respectively. Observe that

where $(a)$ follows from the Gaussian Poincaré inequality. We control each summand directly. In doing so, we will make heavy use of the bounds in Lemma 15 and hence we will often do so without reference. First let us bound the expected norm of the gradients in the above display.

Now, the gradient of $u_{2}({\bm{z}})$ can be computed as

where we recall that ${\bm{\sigma}}({\bm{v}})$ denotes the vector whose $i$th entry is $\sigma(v_{i})$. We have the following bounds on the expected norm squared of each term in (99): for the first of these terms,

for all ${\bm{\theta}}\in{\mathcal{S}}_{p,\delta}$, where $C_{4}>0$ depends only on $\sOmega$, and $C_{5}>0$ depends only on $\sOmega$ and $\delta$. Note that in $(a)$ we used $\left\lVert\sigma^{\prime}\right\rVert_{\infty}$ is finite.

Moving on to bound the norm squared of the second term in (99), we have

Similarly, the expected norm squared of the third term in (99) is bounded as

and finally, for the fourth term in (99) we have

Now moving on to $u_{3}({\bm{z}})$, we can write

Let us again bound the expected norm squared of each of the terms in the previous display.

For the terms on lines (101) and (102) we have

where in $(a)$ we used that $\left\lVert\sigma^{(l)}\right\rVert_{\infty}<\infty$. A similar calculation shows that

For the term on line (104), an analogous calculation shows that

and then similarly for (105), and (106) we have

What remains is the term $\text{Var}(u_{4}({\bm{z}}))^{1/2}$. However, this can be bounded naively as

where $(a)$ follows from an application of Hölder’s and Lemma 15. Hence we have

Combining this with (98), (100), and (107) gives

E.1.2 Bounding the second term in Eq. (86)

Using that for $v_{i}$, not necessarily independent, subgaussian with subgaussian norm $1$

for some universal constant $c_{0}\in(0,\infty)$. Hence, it is sufficient to establish the desired bound on the set $\mathcal{A}$. Indeed, suppose

where $(a)$ follows by a naive bound on $\Delta_{i}$ and $(b)$ follows by an application of Hölder’s. Hence, throughout we work on the event $\mathcal{A}$.

By Lemma 2.4 of [CGS11], $\chi^{\prime}=\chi^{\prime}_{\varphi}$ is differentiable and $\left\lVert\chi^{\prime\prime}\right\rVert_{\infty}\leq C_{0}$ since $\varphi$ is assumed to be differntiable with bounded derivative. Hence,

where $(a)$ follows from (111), $(b)$ follows from boundedness of $\left\lVert\sigma^{\prime}\right\rVert_{\infty}$, and $(c)$ follows from $\left\lVert{\bm{\theta}}_{(i)}\right\rVert_{2}\leq\textsf{R}/\sqrt{d}$ and the definition of $\mathcal{A}$. Now recall the form of $\Delta_{i}$ introduced in Eq. (91) and let us again Taylor expand $\sigma^{\prime}$ to write

for some $v_{j,i}({\bm{z}})$ between ${\bm{w}}_{j}^{\mathsf{T}}{\bm{z}}$ and ${\bm{w}}_{j}^{\mathsf{T}}{\bm{z}}-\rho_{ij}{\bm{w}}_{i}^{\mathsf{T}}{\bm{z}}$. We show that for each $k\in$,

For the contributions of $d_{1,i}$, we have

uniformly over ${\bm{\theta}}\in{\mathcal{S}}_{p,\delta}$. Taking supremum over ${\bm{\theta}}\in{\mathcal{S}}_{p,\delta}$ and sending $n\to\infty$ proves (114) for $k=1$.

uniformly over ${\mathcal{S}}_{p,\delta}$, where $(a)$ holds by the definition of $\mathcal{A}$. Sending $n\to\infty$ shows (114) for $k=2$.

uniformly over ${\bm{\theta}}\in{\mathcal{S}}_{p,\delta}$, establishing (114) for $k=3$.

Finally, $d_{4,i}$ can be bounded almost surely on $\mathcal{A}$:

uniformly over ${\mathcal{S}}_{p,\delta}$, where $(a)$ follows from the definition of the event $\mathcal{A}$ and $(b)$ follows because ${\bm{P}}_{i}^{\perp}$ is a projection matrix for all $i$ and that $\left\lVert{\bm{\theta}}_{(j)}\right\rVert_{2}\leq\textsf{R}/\sqrt{d}$. Therefore, we have

where $(a)$ follows from (112), $(b)$ follows from (113) and $(c)$ follows from (114) holding for $k\in$. Hence, we have shown (110) and completed the proof. ∎

E.1.3 Proof of Lemma 14

Recall the definition of $\Delta_{i}$ in (85) and note that for all $i\in[m]$,

Since ${\bm{z}}$ is Gaussian, ${\bm{w}}_{i}^{\mathsf{T}}{\bm{z}}$ is independent of any function of ${\bm{w}}_{j}^{\mathsf{T}}{\bm{z}}-\rho_{i,j}{\bm{w}}_{i}^{\mathsf{T}}{\bm{z}}$ and hence is independent of ${\bm{\theta}}^{\mathsf{T}}{\bm{x}}/\nu-\Delta_{i}$. Therefore, we have

where $(a)$ follows by Eq. (83) and $(b)$ follows by Eq. (116). Taking the supremum over ${\bm{\theta}}\in{\mathcal{S}}_{p,\delta}$ then $n\to\infty$ and applying Lemmas 16 and 17 completes the proof. ∎

We give the following consequence of Lemma 14.

and take $\varphi$ to be bounded differentiable with bounded derivative. Then for $\delta>0$ we have

where $(a)$ follows from Lemma 14 and $(b)$ follows from the definition of ${\mathcal{S}}_{p,\delta}^{c}$. Now sending $\delta\to 0$ proves the lemma for differentiable Lipschitz functions, which can then be extended to Lipschitz functions via a standard uniform approximation argument.

E.3 Truncation

Let us define ${\mathcal{G}}:=\left\{\left\lVert{\bm{z}}\right\rVert_{2}\leq 2\sqrt{d}\right\}$ and the random variable $\bar{\bm{x}}:={\bm{x}}\mathbf{1}_{\mathcal{G}}.$ The following Lemma establishes the subgaussianity condition of Assumption 5 for $\bar{\bm{x}}$.

Conditional on ${\bm{W}}\in\mathcal{B}$ we have

for some constant $C$ depending only on $\sOmega$.

Take arbitrary ${\bm{\theta}}\in{\mathcal{S}}_{p}$. Let

then consider the function $f({\bm{z}}):={\bm{z}}^{\mathsf{T}}{\bm{T}}_{\bm{\theta}}{\bm{\sigma}}^{\prime}({\bm{W}}^{\mathsf{T}}{\bm{z}})u\left(\left\lVert{\bm{z}}\right\rVert_{2}/\sqrt{d}\right)$. Note that $f$ is continuous and differentiable almost everywhere with gradient

almost everywhere. Noting that $u^{\prime}(t)=u^{\prime}(t)\mathbf{1}_{t\leq 3}$ and $u(t)\leq\mathbf{1}_{t\leq 3}$ we can bound

where $(a)$ follows by nothing that $\mathbf{1}_{t\leq 2}\leq u(t)$. This shows that $\bar{\bm{x}}^{\mathsf{T}}{\bm{\theta}}$ is subgaussian with subgaussian norm constant in $n$ and ${\bm{\theta}}$. Since ${\bm{\theta}}\in{\mathcal{S}}_{p}$ was arbitrary, this proves the claim.

Now, let us show that the condition of Eq. (12) holds for the truncated variables $\bar{\bm{x}}$.

E.4 Proof of Corollary 4

Now, note that we have for some $C_{0},c_{0}>0$,

Combining the displays (121), (123) and (E.4) gives

where $(a)$ follows by dominated convergence. ∎

E.5 Auxiliary lemmas

We include the following auxiliary lemmas for the sake of completeness.

Let $V_{i}$ be mean zero subgaussian random variables with $\sup_{i\in[m]}\left\lVert V_{i}\right\rVert_{\psi_{2}}\leq\textsf{K}$. We have for all integer $k\geq 1$,

There exist constants $C,C^{\prime}\in(0,\infty)$ depending only on $\widetilde{\sgamma}$ such that

where we used that ${\bm{w}}_{i}$ and ${\bm{w}}_{j}$ are independent for $i\neq j$, $\left\lVert{\bm{w}}_{i}\right\rVert=1$ and that ${\bm{w}}_{j}$ is subgaussian with subgaussian norm $C_{0}/\sqrt{d}$. Hence, we have

This proves the existence of the constant $C$ in the statement of the lemma. Meanwhile the existence of $C^{\prime}$ is a consequence of Theorem 4.6.1 in [Ver18]. ∎

Appendix F The random features model: Proof of Corollary 2

The following lemma is a direct consequence of Theorem 2 and Lemma 8 from [HL20].

Furthermore, conditional on ${\bm{W}}\in\mathcal{B}$, ${\bm{x}}$ is subgaussian with subgaussian norm constant in $n$.

We remark that the setting of [HL20] differs slightly from the one considered above. Indeed, they take

the activation function to be odd and the weight vectors to be $\{{\bm{w}}_{j}\}_{j\leq[p]}{\stackrel{{\scriptstyle i.i.d.}}{{\sim}}}\mathcal{N}(0,{\bm{I}}_{d}/d)$, and

the “asymptotically equivalent” Gaussian vectors to be $\widetilde{\bm{g}}:=c_{1}{\bm{W}}^{\mathsf{T}}{\bm{z}}+c_{2}{\bm{h}}$ for ${\bm{h}}\sim\mathcal{N}(0,{\bm{I}}_{p})$ instead of ${\bm{g}}$, where $c_{1}$ and $c_{2}$ are defined so that

Theorem 2 of [HL20] prove a more general result than the one stated here for their setting. Additionally, they give bounds for the rate of convergence for a fixed ${\bm{\theta}}$ in terms of $\left\lVert{\bm{\theta}}\right\rVert_{2},\left\lVert{\bm{\theta}}\right\rVert_{\infty}$ and $\left\lVert\varphi\right\rVert_{\mbox{\tiny\rm Lip}}$ (and other parameters irrelevant to our setting.). However, here we are only interested in the consequence given above.

First note that via a standard argument uniformly approximating Lipschitz functions wtih differentiable Lipschitz functions, Lemma 23 can be extended to hold for $\varphi$ that are bounded Lipschitz.

where $(a)$ follows by the dominated convergence theorem and $(b)$ follows from Eq. (127).

Appendix G Deferred proofs

Let $\mathcal{N}_{\alpha}$ be a minimal $\alpha-$net of $B_{2}^{p}(1)$ so that $|\mathcal{N}_{\alpha}|\leq C(\alpha)^{p}$. It is easy to show that for ${\bm{g}}$ centered isotropic Gaussian,

for some constants $C_{1},C_{2}>0$, where the last inequality holds on $\mathcal{B}$. (A similar argument was carried out in the proof of Lemma 6.)

Choose $\alpha\leq\Delta/C_{2}$. By union bound over $\mathcal{N}_{\alpha}$, for sufficiently large $n$, the following holds with probability at least $1-\delta$:

Let $\mathcal{A}_{\delta}$ be the event that this inequality holds. Having chosen $\alpha$, choose $\sgamma>0$ to satisfy $(C_{1}(\alpha)/\sgamma)^{1/2}<\Delta$ and $\delta=e^{-2\Delta^{2}}<1$ so that we have