Universality Laws for High-Dimensional Learning with Random Features

I Introduction

The supervised learning process described above has two main performance metrics: the training error

which is simply a scaled version of the optimal value of (1), and the generalization error

where $\theta_{\text{out}}(\cdot)$ is some post-processing function (e.g., the sign function) and the expectation in (4) is taken over a fresh pair of samples $\left\{\boldsymbol{g}_{\text{new}},y_{\text{new}}\right\}$ that are independent of the training data. To carry out theoretical analysis of the training and generalization errors, it is necessary to make some further assumptions on how the training samples $\left\{\boldsymbol{g}_{t},y_{t}\right\}$ are generated. A classical model, which is also the one adopted in this work, is the so-called teacher-student framework. Specifically, we assume that $\boldsymbol{g}_{t}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,\boldsymbol{I}_{d})$ and

In this paper, we study a particular case of the above setting, known in the literature as the random feature model . It corresponds to specializing the general regressors in (2) to

I-B The Gaussian Equivalence Conjecture

Fortunately, it has been observed by many authors (see, e.g., , and also in the context of random kernel matrices) that the random feature model considered above should be asymptotically equivalent to a Gaussian model, where we set the regressors in (2) to

In what follows, we shall refer to the setting where the regressors are $\left\{\boldsymbol{a}_{t}\right\}$ in (6) as the nonlinear feature model, and refer to the one using $\left\{\boldsymbol{b}_{t}\right\}$ in (7) as the linear Gaussian model. Let

The optimal weight vectors, the training and the generalization errors of these two formulations can then be written as $\boldsymbol{w}^{*}_{\boldsymbol{A}},\boldsymbol{w}^{*}_{\boldsymbol{B}}$, $\mathcal{E}_{\text{train}}(\boldsymbol{A}),\mathcal{E}_{\text{train}}(\boldsymbol{B})$, and $\mathcal{E}_{\text{gen}}(\boldsymbol{A}),\mathcal{E}_{\text{gen}}(\boldsymbol{B})$, respectively.

Roughly speaking, the Gaussian equivalence conjecture states that, under certain conditions on the feature matrix $\boldsymbol{F}$, we have

That the nonlinear feature model and the linear Gaussian model can be asymptotically equivalent has a simple intuitive explanation. Under certain conditions on the random feature matrix $\boldsymbol{F}$, one can show that the random vectors $\boldsymbol{a}_{t}$ in (6) and $\boldsymbol{b}_{t}$ in (7) have asymptotically matching first and second moments. (See Appendix -D for details.) Thus, the asymptotic equivalence in (10) points to the emergence of a universality phenomenon that is inherent in many large random systems: The macroscopic behaviors of such systems only depend on a few key parameters (the first two moments of $\boldsymbol{a}_{t}$ and $\boldsymbol{b}_{t}$ in our case), whereas the microscopic structures of the systems (i.e., the exact probability distributions of $\boldsymbol{a}_{t}$ and $\boldsymbol{b}_{t}$) are irrelevant.

Notice that the surrogate Gaussian formulation is much more amenable to theoretical analysis, as it only involves Gaussian vectors $\left\{\boldsymbol{b}_{t}\right\}$. Indeed, based on the Gaussian equivalence conjecture, the authors of provided a precise asymptotic characterization of maximum-margin linear classifiers in the overparameterized regime using Gaussian min-max theorems . The performance of the linear Gaussian model under more general settings, where one uses generic convex loss functions and ridge regularization in (1), was studied in by using the non-rigorous replica method from statistical physics. More recently, these replica predictions have been rigorously proved in .

I-C Main Contributions

The main contribution of this paper is to prove the aforementioned Gaussian equivalence conjecture. Our results are based on the following technical assumptions.

The latent input vectors $\boldsymbol{g}_{t}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,\boldsymbol{I}_{d})$ in (6) and (7).

The dimension of the latent input vectors $\boldsymbol{g}_{t}$ (denoted by $d$), the dimension of the regression vectors (denoted by $p$), and the number of training samples (denoted by $n$) tend to infinity at fixed ratios. Specifically, $n/d\to\alpha>0$ and $p/d\to\eta>0$ as $d\to\infty$.

The unknown teacher vector $\boldsymbol{\xi}$ in (5) is deterministic, with $\lVert\boldsymbol{\xi}\rVert=1$.

where $\theta_{\text{teach}}(\cdot)$ is the function in (5).

The activation function $\sigma(\cdot)$ is an odd function, with bounded first, second, and third derivatives.

The columns of the feature matrix $\boldsymbol{F}=[\boldsymbol{f}_{1},\boldsymbol{f}_{2},\ldots,\boldsymbol{f}_{p}]$ are independent Gaussian random vectors: $\boldsymbol{f}_{i}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(\boldsymbol{0},\tfrac{1}{d}\boldsymbol{I}_{d})$ for $1\leq i\leq p$. Moreover, $\boldsymbol{F}$ is independent of the latent input variables $\left\{\boldsymbol{g}_{t}\right\}$.

We can verify that the conditions in Assumption (A.4) are satisfied by the quadratic loss function, the logistic loss function, and by any $\theta_{\text{teach}}(s)$ that grows no faster than some polynomial of $\left\lvert s\right\rvert$ as $\left\lvert s\right\rvert\to\infty$. Possible ways to generalize our results to non-differentiable loss functions (e.g. the hinge loss) will be discussed in Section IV. To simplify our analysis, we require in Assumption (A.6) that the activation function $\sigma(x)$ be odd, which then implies that $\mu_{0}=0$ in (8). This is merely a limitation of our current results, and the asymptotic equivalence in (10) is expected to hold for more general activation functions [such as the ReLU function as shown in Figure 1(a)]. Yet another limitation of our work is the Gaussian assumption on the feature vectors in Assumption (A.8). With some extra effort (mostly on generalizing the concentration inequalities in Appendix -E2), our proof can be easily extended to cases where the columns of the feature matrix are independent sub-Gaussian random vectors. However, we expect that the majority of our proof technique should work for deterministic feature matrices that satisfy the conditions in (64) and (65). We will elaborate on this point in Section IV and pinpoint the one technical difficulty that prevents us from working with deterministic matrices.

To state the results of our main theorem, we first introduce a perturbed version of the optimization problem in (1):

where $\tau_{1},\tau_{2}$ are two parameters, $\boldsymbol{\xi}$ is the teacher vector in (5), and

Note that $\tfrac{1}{p}\Phi_{\boldsymbol{A}}(0,0)$ and $\tfrac{1}{p}\Phi_{\boldsymbol{B}}(0,0)$ [with the regressor matrix $\boldsymbol{R}$ specialized to $\boldsymbol{A}$ and $\boldsymbol{B}$ in (9)] are exactly the training errors associated with the feature and Gaussian formulations, respectively. The two extra terms $\tau_{1}(\boldsymbol{w}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\Sigma}\boldsymbol{w})$ and $\tau_{2}(\sqrt{p}\mu_{1}\boldsymbol{\xi}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}\boldsymbol{w})$ in (11) will be needed in our analysis of the generalization error. In particular, we shall consider different values of $\tau_{1},\tau_{2}$ such that

The bound $\tau^{\ast}$ requires some explanation. At first glance, the possibility that $\tau_{1}$ can take negative values is worrisome, as $\tau_{1}\boldsymbol{w}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\Sigma}\boldsymbol{w}$ will then be a concave function of $\boldsymbol{w}$. This concave term, however, will (most likely) not change the convexity of the overall objective function in (11). To see this, we recall from Assumption (A.8) that $\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}$ has a Wishart distribution and thus its spectral norm is bounded with high probability. Specifically, it is easy to show (see Appendix -E3) that

where $\eta=p/d$ and $c$ is some positive constant. By Assumption (A.5), the regularizer $h(x)$ is strongly convex with parameter $\lambda>0$. It follows that, with $\tau_{1}\geq-\tau^{\ast}$, the overall objective function of (11) is $\frac{\lambda}{2}$-strongly convex with probability at least $1-2e^{-cp}$,

Suppose Assumptions (A.1)–(A.8) hold. Fix $\tau_{1}\in[-\tau^{\ast},\tau^{\ast}]$ and $\tau_{2}\in$. For every $\varepsilon\in(0,1)$ and every finite constant $c$, we have

for $p\geq 1/\varepsilon^{2}$, where $\operatorname{polylog}p$ denotes some function that grows no faster than a polynomial of $\log p$. Consequently,

where $\overset{\mathcal{P}}{\longrightarrow}$ denotes convergence in probability as $p\to\infty$.

We prove this theorem in Section II-D. A special case, with $\tau_{1}=\tau_{2}=0$, implies that the training errors of the nonlinear feature model and its Gaussian surrogate must necessarily have the same asymptotic limit.

The next result, whose proof can be found in Section II-E, establishes the universality for the generalization error, under one additional assumption:

There exists a limit function $q^{\ast}(\tau_{1},\tau_{2})$ such that $\frac{\Phi_{\boldsymbol{B}}(\tau_{1},\tau_{2})}{n}\overset{\mathcal{P}}{\longrightarrow}q^{\ast}(\tau_{1},\tau_{2})$ for all $\tau_{1}\in[-\tau^{\ast},\tau^{\ast}]$ and $\tau_{2}\in$. In addition, the partial derivatives of $q^{\ast}(\tau_{1},\tau_{2})$ exist at $\tau_{1}=\tau_{2}=0$. Let them be denoted by $\frac{\partial}{\partial\tau_{1}}q^{\ast}(0,0)=\rho^{\ast}$ and $\frac{\partial}{\partial\tau_{2}}q^{\ast}(0,0)=\pi^{\ast}$, respectively. We further assume that $\rho^{\ast}\neq 0$.

and $z_{1},z_{2}$ are two independent standard Gaussian random variables.

I-D Related Work

The Gaussian equivalence phenomenon studied in this paper was stated in , and explicitly exploited in to derive the asymptotic limits of several learning problems. Related phenomena also appear in the context of random kernel matrices , where it is shown that the impact of the nonlinear activation function [on the limiting singular value spectrum of the matrix $\boldsymbol{A}$ in (9)] can be captured by the three parameters in (8). However, these results on the asymptotic spectrum are not sufficient for our purpose. Except for the special case of ridge regression, the training and generalization errors of the learning problem in (1) are not simple functions of the singular values/vectors of $\boldsymbol{A}$.

where $\rho=\boldsymbol{w}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\Sigma}\boldsymbol{w}/p$, with $\boldsymbol{\Sigma}$ defined in (12), and $\pi=\mu_{1}\boldsymbol{\xi}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}\boldsymbol{w}/{\sqrt{p}}$. This result is an important step towards a theoretical justification of the Gaussian equivalence, and indeed a quantitive version of (17) serves as a crucial ingredient of our proof. However, by itself the characterization in (17) does not imply the asymptotic equivalence stated in (10), as the training and generalization errors are all complicated functionals defined implicitly through the optimization problem (1). When calculating the generalization errors $\mathcal{E}_{\text{gen}}(\boldsymbol{A}),\mathcal{E}_{\text{gen}}(\boldsymbol{B})$ using (4), for example, one will be dealing with two different weight vectors $\boldsymbol{w}^{*}_{\boldsymbol{A}}$ and $\boldsymbol{w}^{*}_{\boldsymbol{B}}$, respectively, as opposed to a single shared vector $\boldsymbol{w}$ as in (17). Showing that $\boldsymbol{w}^{\mkern-1.5mu\mathsf{T}}_{\boldsymbol{A}}\boldsymbol{\Sigma}\boldsymbol{w}_{\boldsymbol{A}}/p\approx\boldsymbol{w}_{\boldsymbol{B}}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\Sigma}\boldsymbol{w}_{\boldsymbol{B}}/p$ and $\boldsymbol{\xi}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}\boldsymbol{w}_{\boldsymbol{A}}/{\sqrt{p}}\approx\boldsymbol{\xi}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}\boldsymbol{w}_{\boldsymbol{B}}/{\sqrt{p}}$, which are the second-order statistics of the Gaussian distributions, is exactly among the technical challenges addressed in this work.

Our method for proving universality for the random feature model is based on the classical Lindeberg’s principle and a leave-one-out analysis of the optimization problem in (1). Similar approaches have been used before to establish universality for various estimation problems . As a technical challenge in our problem, the entries of the regression vectors have a particular correlation structure, due to the presence of the random feature matrix $\boldsymbol{F}$ in (6) and (7). Thus, new techniques have to be developed to handle this correlation. Beyond the random feature model considered here, the Gaussian equivalence is a very general universality phenomenon that has been observed in many other models (see, e.g., ).

I-E Paper Outline

The rest of the paper is organized as follows. We prove Theorem 1 and Proposition 1 in Section II. To emphasize readability, we only highlight the central ideas and key intermediate results there. In Section III, we use Stein’s method to provide an alternative proof of the central limit theorem for the nonlinear feature model. Heavier technical details are left to the appendix, where we compile all the auxiliary results. We conclude the paper in Section IV with some additional remarks on how some of the technical assumptions in this work can be further relaxed.

II Proof of the Main Results

Notation: In our proof of Theorem 1, the parameters $\tau_{1},\tau_{2}$ in (11) are always kept fixed. Thus, to streamline the notation, we will write $\Phi_{\boldsymbol{A}}(\tau_{1},\tau_{2})$ and $\Phi_{\boldsymbol{B}}(\tau_{1},\tau_{2})$ simply as $\Phi_{\boldsymbol{A}}$ and $\Phi_{\boldsymbol{B}}$, when no confusion can arise. We will use $C$ and $c$ to denote generic constants that do not depend on the problem dimension $p$. To reduce the burden of bookkeeping, the exact values of $C$ and $c$ can change from one line to the next. In addition, $\operatorname{polylog}p$ stands for any function $B(p)$ that grows no faster than some polynomial of $\log p$, i.e.,

We start by noting that, to prove the inequalities in (14) and (15), it suffices to show that

for every bounded test function $\varphi(x)$ that also has bounded first and second derivatives. The precise connection between (14), (15) and (18) will be made clear in Section II-D, when we prove Theorem 1. For now, we focus on showing (18).

In our analysis, we first show a conditional version of (18). Specifically, we will define a subset $\mathcal{A}$ of all $d\times p$ feature matrices, and show that

II-B The Admissible Set of Feature Matrices

Recall that $\boldsymbol{F}=[\boldsymbol{f}_{1},\boldsymbol{f}_{2},\ldots,\boldsymbol{f}_{p}]$, where $\left\{\boldsymbol{f}_{i}\right\}_{i\in[p]}$ are the feature vectors. For notational simplicity, we add one more vector by letting $\boldsymbol{f}_{0}\overset{\text{def}}{=}\boldsymbol{\xi}$. The admissible set $\mathcal{A}$ is constructed as

where $\eta$ is the constant in Assumption (A.2). Before defining $\mathcal{A}_{3}$, which requires some additional notation, we first note that $\mathcal{A}_{1}\text{ and }\mathcal{A}_{2}$ are all high-probability events under Assumption (A.8). Specifically, standard concentration inequalities for sub-Gaussian random vectors give us

for some $c>0$. (See Lemma 7 in Appendix -E1 for a proof.) Similarly, applying matrix concentration inequalities [(172) in Appendix -E3], we can conclude that

The definition of the last set $\mathcal{A}_{3}$ in (21) is a bit technical. Consider a family of optimization problems

for $0\leq k\leq n$, where $\left\{\boldsymbol{a}_{t}\right\}$ and $\left\{\boldsymbol{b}_{t}\right\}$ are the regressors in (6) and (7), respectively, and

The reason for considering this sequence of problems will become clear in Section II-C. For now, just note that our quantities of interest, namely $\Phi_{\boldsymbol{A}}$ and $\Phi_{\boldsymbol{B}}$, are just the starting and end point of this sequence, i.e., $\Phi_{0}=\Phi_{\boldsymbol{A}}$ and $\Phi_{n}=\Phi_{\boldsymbol{B}}$. We then have

where $K_{1}$ is the constant in Assumption (A.4).

Under Assumptions (A.1)–(A.8), there exists some $c>0$ such that

This result, whose proof can be found in Appendix -F5, shows that $\mathcal{A}_{3}$ is still a high-probability event. In light of (24), (25) and (30), there exists $c>0$ such that

II-C The Lindeberg Method

In what follows, we prove (19) by using Lindeberg’s method . The idea is simple: The sequence shown in (26) serves as an interpolation path that allows us to go from $\Phi_{\boldsymbol{A}}$ to $\Phi_{\boldsymbol{B}}$. To prove (19), it suffices to show that the difference between any two neighboring points on the interpolation path is small. Indeed, as there are only $n=\mathcal{O}(p)$ such pairwise comparisons, we just need to show that

uniformly over $\boldsymbol{F}\in\mathcal{A}$ and $1\leq k\leq n$.

By construction, the optimization problems associated with $\Phi_{k}$ and $\Phi_{k-1}$ differ only in their choice of the $k$th regressor. The former uses $\boldsymbol{b}_{k}$, whereas the latter uses $\boldsymbol{a}_{k}$. Consequently, both $\Phi_{k}$ and $\Phi_{k-1}$ can be seen as a perturbation of a common “leave-one-out” problem:

As $\Phi_{k}\approx\Phi_{\backslash k}$, it is natural to apply Taylor’s expansion around $\Phi_{\backslash k}$, which gives us

with $\theta$ denoting some value that lies between $\tfrac{1}{p}\Phi_{k}$ and $\tfrac{1}{p}\Phi_{\backslash k}$. Writing an analogous expansion for $\varphi(\Phi_{k-1})$ around $\Phi_{\backslash k}$, and then subtracting it from (II-C), we can get

To make further progress, we need to introduce a surrogate optimization problem:

where $\boldsymbol{w}_{\backslash k}^{*}$ is the leave-one-out optimal solution of (II-C), and

is the Hessian matrix of the objective function in (II-C) evaluated at $\boldsymbol{w}_{\backslash k}^{*}$. We note that $\Psi_{k}(\boldsymbol{r})$ has a simple interpretation: By setting $\boldsymbol{r}=\boldsymbol{b}_{k}$, we can see that the optimization problem associated with $\Psi_{k}(\boldsymbol{b}_{k})$ is simply a quadratic approximation of the one associated with $\Phi_{k}$ in (26). Similarly, $\Psi_{k}(\boldsymbol{a}_{k})$ is a quadratic approximation of $\Phi_{k-1}$. The following lemma, whose proof can be found in Appendix -F7, quantifies the accuracy of such approximation.

both of which hold uniformly over $\boldsymbol{F}\in\mathcal{A}$ and $k\in[n]$.

Using this lemma, we can now bound the terms on the right-hand side of (33) as follows:

where to reach the last step we have used Hölder’s inequality and (37). Meanwhile, combining (37) and (36) gives us

In light of (II-C), (39), and (40), we just need to show that

to get a useful bound for the left-hand side of (33).

where $\gamma>0$ is some fixed parameter. It is straightforward to show (see Lemma 15 in Appendix -F) that

By construction, both $\boldsymbol{a}_{k}$ and $\boldsymbol{b}_{k}$ are independent of the leave-one-out solution $\boldsymbol{w}_{\backslash k}^{*}$ and the Hessian matrix $\boldsymbol{H}_{\backslash k}$. It is this independent structure that significantly simplifies our analysis.

These last two terms are easy to control, due to the concentrations of $\gamma_{k}(\boldsymbol{b}_{k})$ and $\gamma_{k}(\boldsymbol{a}_{k})$ around $\gamma_{k}$. As shown in Lemma 24 in Appendix -F8, we have

uniformly over $\boldsymbol{F}\in\mathcal{A}$ and $k\in[n]$.

That $\Delta_{\text{CLT}}=o(1)$ is due to the following fact: When conditioned on $\boldsymbol{F}$ and $\boldsymbol{w}_{\backslash k}^{*}$, we have

Making (49) precise is the focus of Theorem 2 in Section III. It is easy to verify that the test function defined in (48) indeed satisfies the assumptions of Theorem 2. (See Lemma 25 in Appendix -F8.) Consequently, for every $\boldsymbol{F}\in\mathcal{A}$, Theorem 2 gives us

Note that the upper bound is uniform over all $\boldsymbol{F}\in\mathcal{A}$ and all $k\in[n]$. Now let us recall the construction of the interpolation sequence in (26). Since $\Phi_{0}=\Phi_{\boldsymbol{A}}$ and $\Phi_{n}=\Phi_{\boldsymbol{B}}$, we obtain (19) from (51) via triangle inequality. Finally, given the decomposition in (20) and the probability bound in (31), we establish the inequality in (18).

Before proceeding to the proof of Theorem 1, we pause and point out a subtle issue regarding the central limit theorem stated informally in (49). It is important that the weight vector in (49) is the leave-one-out solution $\boldsymbol{w}_{\backslash k}^{*}$, which is independent of both $\boldsymbol{a}_{k}$ and $\boldsymbol{b}_{k}$. The situation will be very different if we use the original optimal solution $\boldsymbol{w}^{*}_{k}$ instead. In this case, the asymptotic distribution of $\tfrac{1}{\sqrt{p}}{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}_{k}\boldsymbol{w}^{*}_{k}}$ is not Gaussian (i.e., the central limit theorem is no longer valid), due to the weak yet non-negligible correlation between $\boldsymbol{w}^{*}_{k}$ and $\boldsymbol{a}_{k}$.We illustrate this fact in Fig. 2. The theoretical prediction of the limit distributions shown in the figure can be found by using Lemma 15 and Lemma 16 in Appendix -F.

II-D Proof of Theorem 1

Equipped with (18), we just need to construct a suitable test function in order to complete the proof. For any fixed $\varepsilon>0$ and $c$, let

where $\zeta_{\varepsilon/2}(x)$ is a scaled mollifier defined in (118) in Appendix -A. By properties of $\zeta_{\varepsilon/2}(x)$, it is easy to check that $\lVert\varphi_{\varepsilon}^{\prime}\rVert_{\infty}<{C}/{\varepsilon}$ and $\lVert\varphi_{\varepsilon}^{\prime\prime}\rVert_{\infty}<{C}/{\varepsilon^{2}}$. Moreover,

Letting $x=\Phi_{\boldsymbol{A}}/p$ and taking expectation over the functions in (53), we have

Changing $x$ to $\Phi_{\boldsymbol{B}}/p$ yields

which leads to (14) for $\varepsilon\in(0,1)$ and $p\geq\tfrac{1}{\varepsilon^{2}}$. The proof of (15) is analogous, as the above procedure is completely symmetric with respect to $\Phi_{\boldsymbol{A}}$ and $\Phi_{\boldsymbol{B}}$.

II-E Proof of Proposition 1

Let $\boldsymbol{g}_{\text{new}}\sim\mathcal{N}(0,\boldsymbol{I}_{d})$ be a Gaussian vector independent of the existing training samples and the feature matrix. Substituting (5) into (4), we can then write the generalization errors as

where $\boldsymbol{\Sigma}$ is the matrix in (12). It is also easy to check that $\mathcal{E}_{\text{gen}}(\boldsymbol{B})=G(\rho_{B},\pi_{B})$, where

with $z_{1},z_{2}\overset{\text{i.i.d.}}{\sim}{\mathcal{N}(0,1)}$.

The rest of the proof falls naturally into three parts: (a) We will first show that $\rho_{B}\to\rho^{\ast}=\frac{\partial}{\partial\tau_{1}}q^{\ast}(0,0)$ and $\pi_{B}\to\pi^{\ast}=\frac{\partial}{\partial\tau_{2}}q^{\ast}(0,0)$, where $q^{\ast}(\tau_{1},\tau_{2})$ is the limit function in Assumption (A.9); (b) By replacing $\boldsymbol{w}^{*}_{\boldsymbol{B}}$ in (54) with $\boldsymbol{w}^{*}_{\boldsymbol{A}}$, we introduce the analogous quantities $\rho_{A}$ and $\pi_{A}$. We will show that $\rho_{A},\pi_{A}$ have the same limits as $\rho_{B},\pi_{B}$; (c) Finally, we will show that $\mathcal{E}_{\text{gen}}(\boldsymbol{A})\approx G(\rho_{A},\pi_{A})$ with high probability, where $G(\cdot,\cdot)$ is the function in (55).

We start with part (a). By the definition of the optimization problem in (11), we have

for any $\tau_{1},\tau_{2}$. It follows that, for any $\tau>0$,

Fix $\varepsilon>0$. By Assumption (A.9), the limit function $q^{\ast}(\tau_{1},\tau_{2})$ is differentiable at the origin. Thus, there is some $\delta>0$ such that

The first inequality in (56), with $\tau$ substituted by $\delta$, then gives us

Next, we move on to part (b) and establish the limits for $\rho_{A}$ and $\pi_{A}$. This is easy, in light of the universality laws given by Theorem 1. Specifically, (16) gives us $\Phi_{\boldsymbol{A}}(\tau_{1},\tau_{2})/p\overset{\mathcal{P}}{\longrightarrow}q^{\ast}(\tau_{1},\tau_{2})$. Replicating the same steps in part (a), with $B$ replaced by $A$, allows us to conclude that

By Assumption (A.7), $\varphi(x;s)$ is differentiable with respect to $x$ except at a finite number of points. Moreover, it is easy to check that

where $K_{1}$ is the constant in Assumption (A.4) and

Also recall the admissible set $\mathcal{A}$ defined in Section II-B. We can verify that the assumptions of Proposition 3 (as stated and shown in Section III-D) hold for any $\boldsymbol{F}\in\mathcal{A}$ and $\boldsymbol{\beta}=\boldsymbol{w}^{*}_{\boldsymbol{A}}\in\mathcal{B}\cap\mathcal{C}$. Thus, conditioned on $\mathcal{A}\cap\mathcal{B}\cap\mathcal{C}$, we can apply Proposition 3 to get

III A Central Limit Theorem for the Feature Model

In this section, we prove a central limit theorem (CLT) related to the nonlinear feature model. Let

as $p\to\infty$. Here, we consider the setting where $\boldsymbol{\beta},\boldsymbol{\xi}$ and the feature vectors are all deterministic, and the only sources of randomness come from $\boldsymbol{g}$ and $\boldsymbol{z}$. Thus, the right-hand side of (63) are just two jointly Gaussian random variables. CLT in the form of (63) was first studied and proved in (see our discussions in Section I-D and Remark 4 below). It will be useful in bounding the term $\Delta_{\text{CLT}}$ in (44), a critical step in our application of the Lindeberg method. It also plays an important role in our proof of Proposition 1, where we establish the universality of the generalization error.

To state the theorem, we first need to put some restrictions on the feature vectors and the teacher vector $\boldsymbol{\xi}$. Let $\boldsymbol{f}_{0}\overset{\text{def}}{=}\boldsymbol{\xi}$, and let $\delta_{ij}$ denote the Kronecker delta function. We assume that

for some $\kappa_{p}=\mathcal{O}(p^{1/8-\gamma})$ and $\gamma>0$. Moreover,

Note that, for the random feature vectors considered in this paper [see Assumption (A.8) and the admissible condition in (22)], the upper bound $\kappa_{p}$ can actually be as small as $\operatorname{polylog}p$, and the spectral norm $\lVert\boldsymbol{F}\rVert$ can be set to be of $\mathcal{O}(1)$. However, since we believe that the central limit theorem could be of independent interest in other problems beyond this paper, we are going to prove it under the more relaxed assumption in (64).

Suppose that the feature vectors satisfy (64) and (65), and the activation function $\sigma(x)$ satisfies the conditions in Assumption (A.6). Let $\left\{\varphi_{p}(x;s)\right\}$ be a sequence of two-dimensional test functions that are differentiable with respect to $x$. Moreover, for each $p$,

where $z\sim\mathcal{N}(0,1)$ and $P({\boldsymbol{\beta}},\kappa_{p})=[1+\lVert\boldsymbol{\beta}\rVert_{\infty}(1+\kappa^{4}_{p})][1+(\tfrac{1}{\sqrt{p}}\lVert\boldsymbol{\beta}\rVert)^{2K+1}]/\mu_{2}^{2}$.

The settings of the CLT shown in are also somewhat different from ours. On the one hand, the one in is more general in that it does not require the nonlinear activation function $\sigma(x)$ to be an odd function. On the other hand, Theorem 2 is more relaxed in terms of the test function $\varphi(x;s)$, which only needs to be differentiable with respect to the first variable $x$. In addition, we further relax this restriction in Section III-D, where a characterization similar to (67) is given for piecewise differentiable test functions, at the cost of a slower decay rate than the right-hand side of (67). This extension will be needed when we study the universality of the generalization error in (4). Finally, the new proof technique here, based on Stein’s method , might be of interest in its own right.

Consider a sequence of activation functions $\left\{\sigma_{p}(x)\right\}$ and differentiable test functions $\left\{\varphi_{p}(x)\right\}$ such that, for every $p$,

$\max\left\{\lVert\sigma^{\prime}_{p}(x)\rVert_{\infty},\lVert\sigma^{\prime\prime}_{p}(x)\rVert_{\infty},\lVert\sigma^{\prime\prime\prime}_{p}(x)\rVert_{\infty}\right\}\leq\operatorname{polylog}p$;

$\sigma_{p}(x)$ is compactly supported. Specifically, there is some threshold $\tau_{p}\leq\operatorname{polylog}p$ such that $\sigma_{p}(x)=0$ for all $\left\lvert x\right\rvert\geq\tau_{p}$;

$\max\left\{\lVert\varphi_{p}(x)\rVert_{\infty},\lVert\varphi^{\prime}_{p}(x)\rVert_{\infty}\right\}\leq B_{p}$ for some $B_{p}<\infty$.

Here, $\boldsymbol{a}=\sigma(\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{g})$ and $\boldsymbol{b}=\mu_{1,p}\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{g}+\mu_{2,p}\boldsymbol{z}$, where $\boldsymbol{g}\sim\mathcal{N}(0,\boldsymbol{I}_{d})$ and $\boldsymbol{z}\sim\mathcal{N}(0,\boldsymbol{I}_{p})$ are two independent Gaussian vectors, $\boldsymbol{F}=[\boldsymbol{f}_{1},\boldsymbol{f}_{2},\ldots,\boldsymbol{f}_{p}]$ is a collection of feature vectors satisfying (64) and (65), and

Lemma 2 is essentially a reduced form of Theorem 2. The characterization in (68) guarantees that $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\sqrt{p}}$ has an asymptotical Gaussian law, whereas (67) needs to consider the joint distribution of $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\sqrt{p}}$ and $\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\xi}$. Moreover, Lemma 2 puts some further constraints on $\sigma_{p}(x)$ and $\varphi_{p}(x)$, requiring the former to have compact supports and the latter to be bounded and to have bounded derivatives.

Our proof is based on Stein’s method . We start by observing that $\frac{\boldsymbol{b}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\sqrt{p}}$ is a Gaussian random variable with zero mean and variance

It follows that we can rewrite the left-hand side of (68) as

for $z\sim\mathcal{N}(0,1)$. Next, we introduce the following “Stein transform”:

Key to Stein’s method is the following identity

which can be directly verified from the definition of $\psi(x)$. Moreover, since $\lVert\varphi^{\prime}(x)\rVert_{\infty}\leq B_{p}$, we have from [45, Lemma 2.4] that

By Stein’s identity, when $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\nu\sqrt{p}}$ follows the standard Gaussian distribution, the left-hand side of (76) exactly equals to zero. Intuitively, this quantity should be approximately equal to zero when $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\nu\sqrt{p}}$ is approximately standard Gaussian. This is what we are going to prove next. In what follows, we derive bounds for the two parts on the right-hand side of (76), separately.

We start with part (a). To simplify the notation, we let $\chi=\frac{1}{\nu\sqrt{p}}\sum_{i=1}^{p}\beta_{i}a_{i}\delta_{i}$. Applying the bound on $\left\|\psi^{\prime}(x)\right\|_{\infty}$ in (73) gives us

with the second inequality due to (65). Recall the definition of $\nu$ in (70). We then have

where in the last step we use a simple inequality ($\lVert\boldsymbol{\beta}\rVert^{2}\leq\lVert\boldsymbol{\beta}\rVert_{\infty}\lVert\boldsymbol{\beta}\rVert\sqrt{p}$) to bring the final bound to a convenient form.

Next, we consider the variance term in (78). Introducing the shorthand notation $u_{k}=\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{f}_{k},1\leq k\leq p$, we rewrite $\delta_{i}$ in (77) as

where to reach the second equality we have used Taylor’s expansion, with $\theta_{ij}$ denoting a point between $u_{j}-\rho_{ij}u_{i}$ and $u_{j}$. Substituting (80) into the expression for $\chi$ leads to

The term involving $\Delta$ on the right-hand side of (84) is easy to bound, even deterministically. Using our assumptions about the function $\sigma_{p}(x)$ stated in the lemma, namely it has a compact support and bounded third derivatives, we have $\left\lvert\sigma(u_{i})u_{i}^{3}\right\rvert\leq\operatorname{polylog}p$ and $\left\lvert\sigma^{\prime\prime\prime}(\theta_{ij})\right\rvert\leq\operatorname{polylog}p$. In addition, since the feature vectors satisfy (64), we can verify from the definition (74) that $\max_{i\neq j}\left\lvert\rho_{ij}\right\rvert\leq\frac{c\kappa_{p}}{\sqrt{p}}$ for some constant $c$. It follows that

where the second inequality is due to the simple bound that $\sum_{i\neq j}\left\lvert\beta_{i}\beta_{j}\right\rvert\leq p\lVert\boldsymbol{\beta}\rVert_{\infty}\sum_{i}\left\lvert\beta_{i}\right\rvert\leq p^{3/2}\lVert\boldsymbol{\beta}\rVert_{\infty}\lVert\boldsymbol{\beta}\rVert$.

Now we tackle the more challenging task of bounding $\text{var}(\Gamma)$ in (84). We first note that, since $u_{i}=\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{f}_{i}$ and $u_{j}=\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{f}_{j}$, we can view $\Gamma$ as a differentiable function of $\boldsymbol{g}$, denoted by $\Gamma(\boldsymbol{g})$, with $\boldsymbol{g}\sim\mathcal{N}(0,\boldsymbol{I}_{d})$. The Gaussian Poincaré inequality (see, e.g., [46, Theorem 3.20]) then gives us

where the gradient $\nabla\Gamma(\boldsymbol{g})$ can be computed, with some diligence, as

where $q_{1}(u)=2\sigma(u)\sigma^{\prime}(u)$, $q_{2}(u)=\sigma(u)u$, $q_{3}(u)=\sigma^{\prime}(u)$, $q_{4}(u)=-\tfrac{1}{2}\sigma(u)u^{2}$, and $q_{5}(u)=\sigma^{\prime\prime}(u)$. In light of (86), we just need to show that $\lVert\nabla\Gamma(\boldsymbol{g})\rVert$ is properly bounded. We do so by controlling the norm of each term on the right-hand side of (87).

Note that our assumptions about the function $\sigma_{p}(x)$ implies that $\lVert q_{i}(u)\rVert_{\infty}\leq\operatorname{polylog}p$ and $\lVert q^{\prime}_{i}(u)\rVert_{\infty}\leq\operatorname{polylog}p$ for $1\leq i\leq 5$. Moreover, $\lVert\boldsymbol{F}\rVert\leq\operatorname{polylog}p$ by assumption. Thus, the first term on the right-hand side of (87) can be bounded as

For the second term, we first rewrite it in the form of a matrix-vector multiplication as

where $\boldsymbol{D}_{1}=\text{diag}\left\{\beta_{i}q^{\prime}_{2}(u_{i})\right\}$, $\boldsymbol{M}=\text{diag}\left\{\|\boldsymbol{f}_{i}\|^{-2}\right\}\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}-\boldsymbol{I}$, and $\boldsymbol{D}_{2}=\text{diag}\left\{q_{3}(u_{j})\right\}$. Clearly, $\lVert\boldsymbol{D}_{1}\rVert\leq\lVert\boldsymbol{\beta}\rVert_{\infty}\operatorname{polylog}p$ and $\lVert\boldsymbol{D}_{2}\rVert\leq\operatorname{polylog}p$. We can also verify that

Similarly, the fourth term on the right-hand side of (87) can be rewritten as $\frac{1}{\nu^{2}p}\boldsymbol{F}\widetilde{\boldsymbol{D}}_{1}\widetilde{\boldsymbol{M}}\widetilde{\boldsymbol{D}}_{2}\boldsymbol{\beta}$, where $\widetilde{\boldsymbol{D}}_{1}=\text{diag}\left\{\beta_{i}q^{\prime}_{4}(u_{i})\right\}$, $\widetilde{\boldsymbol{D}}_{2}=\text{diag}\left\{q_{5}(u_{j})\right\}$, and $\widetilde{\boldsymbol{M}}=\boldsymbol{M}\circ\boldsymbol{M}$, with $\circ$ denoting the Hadamard product of two matrices. The spectral norm of $\widetilde{\boldsymbol{M}}$ can be bounded as

for some constant $c$, where the last inequality is due to (64). This then allows us to bound the norm of the fourth term of the gradient expression as

The situations for the third and fifth term on the right-hand side of (87) are completely analogous, and thus we avoid the repetitions. With the bounds in (88), (90) and (92), we can now apply (86) to get

Combining this bound with those in (85), (84), (79), we can retrace our steps back to (78) and conclude

where the last inequality also uses the fact that $\boldsymbol{\Sigma}_{b}\succeq\mu_{2,p}^{2}\boldsymbol{I}$ and thus

Now the remaining task is to bound the part (b) in (76) before we can complete the proof. Using Taylor’s expansion, we have

where $\theta_{i}$ is some point between $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\nu\sqrt{p}}-\delta_{i}$ and $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\nu\sqrt{p}}$. By assumption, the function $\sigma(x)$ considered in this lemma is supported on $[-\tau_{p},\tau_{p}]$ for some $\tau_{p}\leq\operatorname{polylog}p$. We can then write $a_{i}=\sigma(u_{i})=\sigma(u_{i})\mathds{1}_{[-\tau_{p},\tau_{p}]}(u_{i})$. This step of introducing an indicator function is not strictly necessary, but it helps to simplify some of our later arguments. We now have

where to reach the last inequality we have also used (73) and the boundedness of $a_{i}=\sigma(u_{i})$. Using a similar Taylor’s expansion as in (80) but only to the second order, we have

where $\boldsymbol{M},\widetilde{\boldsymbol{M}}$ are the matrices considered in (89) and (91), respectively, and $\widetilde{\boldsymbol{\beta}}=[\left\lvert\beta_{1}\right\rvert,\ldots,\left\lvert\beta_{p}\right\rvert]^{\mkern-1.5mu\mathsf{T}}$. Using the spectral bounds given in (89) and (91), and the inequality (94), we get

Substituting this inequality and (93) into (76), and using the fact that $\mu_{2,p}\leq\operatorname{polylog}p$, we are done. ∎

III-B Joint Distributions

Lemma 2 shows that $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\sqrt{p}}$ has an asymptotically Gaussian distribution. Using this result, we can easily show that the asymptotic distribution of $\frac{\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}}{\sqrt{p}}$ and $\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\xi}$ is jointly Gaussian, via a conditioning technique.

Consider a sequence of activation functions $\left\{\sigma_{p}(x)\right\}$ and two-dimensional test functions $\left\{\varphi_{p}(x;s)\right\}$ such that, for every $p$,

$\max\left\{\lVert\sigma^{\prime}_{p}(x)\rVert_{\infty},\lVert\sigma^{\prime\prime}_{p}(x)\rVert_{\infty},\lVert\sigma^{\prime\prime\prime}_{p}(x)\rVert_{\infty}\right\}\leq\operatorname{polylog}p$;

$\sigma_{p}(x)$ is compactly supported. Specifically, there is some threshold $\tau_{p}\leq\operatorname{polylog}p$ such that $\sigma_{p}(x)=0$ for all $\left\lvert x\right\rvert\geq\tau_{p}$;

$\varphi_{p}(x;s)$ is differentiable with respect to $x$. Moreover, there is a function $B_{p}(s)$ such that

Here, $\boldsymbol{z}\sim\mathcal{N}(0,1)$, $\boldsymbol{a},\boldsymbol{b}$ are defined the same way as in Lemma 2, and $\boldsymbol{F}=[\boldsymbol{f}_{1},\boldsymbol{f}_{2},\ldots,\boldsymbol{f}_{p}]$ is a collection of feature vectors satisfying (64) and (65).

where $s\sim\mathcal{N}(0,1)$ and $\widetilde{g}\sim\mathcal{N}(0,\boldsymbol{I}_{d})$ are two independent sets of Gaussian random variables. Let

We can then redefine the entries of $\boldsymbol{a}$ and $\boldsymbol{b}$ as

without changing their probability distributions. The reason we do such decomposition is that $\widetilde{\boldsymbol{g}}^{\mkern-1.5mu\mathsf{T}}\widetilde{\boldsymbol{f}}_{i}$ is independent of $s$. This convenient independence structure allows us to calculate the expectations in (3) by first conditioning on $s$.

Applying Taylor’s expansion to the expression for $a_{i}$ in (99), we get

where $\theta_{i}$ is some point between $\widetilde{u}_{i}$ and $\widetilde{u}_{i}+s\rho_{i}$. This expansion then leads to

Using the bounded derivative assumption in (97), we have

Next, we show that the terms involving $\Delta_{1}$ and $\Delta_{2}$ in (III-B) are small.

with the last step being the Gaussian Poincaré inequality. Recall the definition of $\rho_{i}$ and $\widetilde{\boldsymbol{f}}_{i}$ in (98). One can verify that

where to reach (102) we have used the bound $\max_{i}\left\lvert\rho_{i}\right\rvert\leq\kappa_{p}/\sqrt{p}$ due to (64). Substituting (102) into (101) then gives us

In light of (103) and (104), the left-hand side of (III-B) is well under control.

Using the equivalent representation for $\boldsymbol{b}$ in (99), we have

where $\varphi_{\text{shift}}(x;s)\overset{\text{def}}{=}\varphi(x+\frac{s\mu_{1,p}\sum_{i}\beta_{i}\rho_{i}}{\sqrt{p}};s)$ is simply a shifted version of $\varphi(x;s)$. Combining this with (III-B), (103) and (104), we can now bound the left-hand side (LHS) of (3) as

Note that, for any fixed $s$, we can use Lemma 2 to control the conditional expectation in the first term on the right-hand side of (105). Indeed, with $s$ fixed, $\varphi_{\text{shift}}(x;s)$ can be viewed as a one-dimensional test function and it satisfies all the assumptions stated in Lemma 2. The only thing that is different here is that we are now using $\{\widetilde{\boldsymbol{f}}_{i}\}$ as the feature vectors. Thus, to apply Lemma 2, we need to check that this modified set of feature vectors still satisfy the condition in (64). But this is easy to do. Recall that $\widetilde{\boldsymbol{f}}_{i}=(\boldsymbol{I}-\boldsymbol{\xi}\boldsymbol{\xi}^{\mkern-1.5mu\mathsf{T}})\boldsymbol{f}_{i}$, with $\{\boldsymbol{f}_{i}\}$ satisfying (64) for some $\kappa_{p}=\mathcal{O}(p^{1/8})$. Thus, for all $i,j$,

for some positive constant $c$. Finally, by substituting the bounds (68) [with $B_{p}$ there replaced by $B_{p}(s)$] and (106) into (105), we reach the target inequality in (3). ∎

III-C Proof of Theorem 2

To go from Lemma 3 to Theorem 2, we just need to remove the following two restrictions in the assumptions of Lemma 3: (1) $\sigma(x)$ is compactly supported on $[-\tau_{p},\tau_{p}]$ for some $\tau_{p}=\operatorname{polylog}p$; and (2) $\varphi(x;s)$ and its derivatives are bounded [see (97)]. The main ingredient of our proof is to show, via a standard truncation technique, that the central limit theorem characterization still holds even if we relax these two assumptions.

Let $\varphi(x;s)$ be a test function satisfying (66). We can construct a smoothly truncated version of this function via

where $\Omega_{T_{p},1}(x)$ is the smooth window function defined in (119) in Appendix -A and

for some positive constant $C_{T}$. The threshold $T_{p}$ in (107) is chosen strategically. With this choice, we can show

The detailed proof of (108) and (109) are provided in Appendix -B Together, (108) and (109) show that replacing the original test function $\varphi(x;s)$ with its smoothly truncated approximation $\widehat{\varphi}_{p}(x;s)$ only incurs a small price of $\mathcal{O}(\operatorname{polylog}p/\sqrt{p})$.

Next, we consider the activation function $\sigma(x)$. Using the smooth window function in (119) again, we can build a truncated approximation

for some positive constant $C_{\tau}$. It is easy to verify that $\widehat{\sigma}_{p}(x)$ satisfies all the assumptions stated in Lemma 3 concerning the activation functions. With this truncated activation function, define

as the counterparts of $\boldsymbol{a}$ and $\boldsymbol{b}$ in (62). Here, $\mu_{1,p},\mu_{2,p}$ are the constants defined in (69). Our goal is to show that $\tfrac{1}{\sqrt{p}}\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}\approx\tfrac{1}{\sqrt{p}}\widehat{\boldsymbol{a}}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}$ and $\tfrac{1}{\sqrt{p}}\boldsymbol{b}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}\approx\tfrac{1}{\sqrt{p}}\widehat{\boldsymbol{b}}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}$. Specifically, we can get (details are relegated to Appendix -B)

Given the inequalities in (108), (109), (112) and (113), we have

We can use Lemma 3 to bound the second term on the right-hand side, since its test function $\widehat{\varphi}_{p}(x;s)$ and the activation function $\widehat{\sigma}_{p}(x)$ satisfy the assumptions stated in that lemma. Using (3) and the property that $\left\lvert\mu_{2}-\mu_{2,p}\right\rvert\leq\operatorname{polylog}p/\sqrt{p}$, we reach the main result (67) of the theorem.

III-D Extension to Piecewise Smooth Test Functions

In what follows, we generalize Theorem 2 to test functions that are only piecewise differentiable. This auxiliary result will be needed in our proof of Proposition 1 for the case where the “output function” $\theta_{\text{out}}(y)$ in the generalization error (4) lacks smoothness [e.g., $\theta_{\text{out}}(y)=\operatorname{sign}(y)]$.

Consider the same assumptions of Theorem 2 with “$\varphi_{p}(x;s)$ is differentiable with respect to $x$” replaced by “$\varphi_{p}(x;s)$ differentiable with respect to $x$ except at a finite number of points $\left\{x_{1},x_{2},\ldots,x_{L}\right\}$”. Additionally, we also assume that

The upper bound $\kappa_{p}\leq\operatorname{polylog}p$ in (64).

$\lVert\boldsymbol{\beta}\rVert_{\infty}\leq\operatorname{polylog}p$.

Let $\nu^{2}=\boldsymbol{\beta}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\Sigma}\boldsymbol{\beta}/p$, where $\boldsymbol{\Sigma}$ is the covariance matrix in (12). Then $\nu^{2}\geq c>0$ for some constant $c$.

It is possible to improve the convergence rate on the right-hand side of (114) from $\mathcal{O}(p^{-1/8}\operatorname{polylog}p)$ to $\mathcal{O}(p^{-1/4}\operatorname{polylog}p)$, by requiring higher moments of $B_{p}(z)$ to be bounded. We do not pursue this optimization as the current form is sufficient for our proof of Proposition 1.

IV Conclusion and Final Remarks

In this paper, we have proved the asymptotic equivalence of a nonlinear random feature model and a surrogate linear Gaussian models in terms of their training and generalization errors. As a consequence of this universality theorem, the learning performance of high-dimensional random feature models can be precisely characterized by studying their linear Gaussian counterparts, which are much more amenable to theoretical analysis. Our proof, which builds on the classical Lindeberg approach, makes several technical assumptions on the loss function, the nonlinear activation function, and the feature matrix. We close the paper by discussing how some of these assumptions can be further relaxed.

In our proofs, we often need to apply smoothing and truncation to certain functions. This appendix collects the background and auxiliary results associated with such operations. First, we recall the construction of a standard mollifier

for some numerical constant $C$. For each $\delta>0$, we can rescale the mollifier as

so that the resulting function is supported on $[-\delta,\delta]$. For any piecewise-smooth function $h(x)$, we can obtain a smooth approximation by convolving it with a mollifier, i.e.,

A special case, frequently used in our proofs, is when $h(x)$ is the indicator function defined on certain intervals. In particular, for $T>0,\delta>0$, we define

as a smooth “window function”. It is easy to check that $\Omega_{T,\delta}(x)=1$ for $\left\lvert x\right\rvert\leq T$, $\Omega_{T,\delta}(x)=0$ for $\left\lvert x\right\rvert\geq T+\delta$, and $0\leq\Omega_{T,\delta}(x)\leq 1$ for $x$ in the smooth “transition bands”. Moreover, it follows from (117) that $\lVert\Omega^{\prime}_{T,\delta}(x)\rVert_{\infty}\leq C/\delta$.

Let $h(x)$ be a function that is differentiable everywhere except at a finite number of points $\left\{x_{1},x_{2},\ldots,x_{L}\right\}$. If there is a function $B(x)$ such that

where $B_{\delta}(x)\overset{\text{def}}{=}\sup_{\left\lvert c\right\rvert\leq\delta}B(x+c)$ and $\Omega_{2\delta,\delta}(\cdot)$ is a smoothed window function as defined in (119). Moreover,

Let $\mathcal{D}=\cup_{1\leq i\leq L}[x_{i}-2\delta,x_{i}+2\delta]$. For any $x\not\in\mathcal{D}$, the function $h(x)$ is differentiable on the interval $[x-\delta,x+\delta]$. For such $x$, we have

The desired inequality in (121) then follows from the simple observation that $\mathds{1}_{[x_{i}-2\delta,x_{i}+2\delta]}(x)\leq\Omega_{2\delta,\delta}(x-x_{i})$, which can be easily verified from the definition in (119).

The first inequality in (122) is obvious. To get the second inequality, we have

-B Auxiliary Results for the Proof of Theorem 2

The standard trick in a truncation method is to introduce two indicator functions defined on $\mathcal{B}$ and $\mathcal{B}^{c}$, respectively. Since \big{|}\varphi\big{(}\tfrac{1}{\sqrt{p}}\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta};\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\xi}\big{)}-\widehat{\varphi}_{p}\big{(}\tfrac{1}{\sqrt{p}}\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta};\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\xi}\big{)}\big{|}\mathds{1}_{\mathcal{B}}\equiv 0,

where to reach (126) we have used Hölder’s inequality and the fact that $\left\lvert\varphi(x;s)\right\rvert\geq\left\lvert\widehat{\varphi}_{p}(x;s)\right\rvert$. To bound the first term on the right-hand side of (126), we can use (66) and get

where the last inequality is obtained by using the moment estimate (157) in Lemma 8. Substituting (125) and (127) into (126), we can get (108). The steps leading to (109) are completely analogous to what we did to reach (108), so we omit the details here.

for all sufficiently large $C_{\tau}$. [Without loss of generality, we should also assume that $C_{\tau}\geq 2$, as this is needed in the proof of an auxiliary result in Appendix -D.] On the other hand, by the construction of $\Omega_{T_{p},1}(x)$ and the assumption in (66), we can easily verify that

where $K$ is the constant in (66). Then using the boundedness of $\widehat{\varphi}^{\prime}_{p}(x;s)$ given in (130) and defining $\mathds{1}_{\mathcal{D}^{c}}$ as the indicator function supported on $\mathcal{D}^{c}$, we have

Next we prove (113). It follows from the definition in (111) that

where the last inequality uses the estimate given in Lemma 6 in Appendix -D. We now have

-C Proof of Proposition 3

be a smoothed version of the test function, where $\zeta_{\delta_{p}}(x)$ is the mollifier introduced in Appendix -A. The main idea of the proof is choosing a diminishing sequence of ${\delta_{p}}$ so that the left-hand side of (114) is well-approximated by a similar term involving the smooth function $\varphi_{\delta_{p}}(x;s)$. To shorten notation, in what follows, we abbreviate \varphi_{p}\big{(}\tfrac{1}{\sqrt{p}}\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta};\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\xi}\big{)} and \varphi_{\delta_{p}}\big{(}\tfrac{1}{\sqrt{p}}\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta};\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\xi}\big{)} to $\varphi(\boldsymbol{a})$ and $\varphi_{\delta_{p}}(\boldsymbol{a})$, respectively. The meaning of the notation $\varphi(\boldsymbol{b})$ and $\varphi_{\delta_{p}}(\boldsymbol{b})$ should also be clear. Since

we just need to bound the three terms on the right-hand side.

The first term can be controlled by Theorem 2, as $\varphi_{\delta_{p}}(x;s)$ is differentiable. By assumption, $\left\lvert\varphi(x;s)\right\rvert\leq B_{p}(s)(1+\left\lvert x\right\rvert^{K})$ for some $K\geq 1$. Using the simple bound (122) in Lemma 4 (see Appendix -A), we can check that, for any ${\delta_{p}}<1$,

where $C$ is some numerical constant and $C^{\prime}=(2^{K-1}+1)C$. Theorem 2 then gives us

where we have simplified the term $P(\boldsymbol{\beta},\kappa_{p})$ in (67) by using the additional assumption that $\kappa_{p}\leq\operatorname{polylog}p$ and $\lVert\boldsymbol{\beta}\rVert_{\infty}\leq\operatorname{polylog}p$.

To control the second term on the right-hand side of (133), we apply Lemma 4 again. Using a shorthand notation \widehat{B}_{p}(\boldsymbol{a})=C^{\prime}B_{p}(s)(1+\big{\lvert}\tfrac{1}{\sqrt{p}}\boldsymbol{a}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}\big{\rvert}^{K}), we have, from (121),

where in reaching the last step we have used the moment bound obtained in (127). The same reasoning also yields

Note that $\tfrac{1}{\sqrt{p}}\boldsymbol{b}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}$ is a Gaussian random variable with zero mean and variance $\nu^{2}$. (Recall the definition of $\nu^{2}$ in the statement of the proposition.) As the function $\Omega_{2{\delta_{p}},{\delta_{p}}}^{2}(x-x_{i})\leq 1$ with a compact support of width $6{\delta_{p}}$, we have

Substituting (138), (137), (135), (136), (134) into (133), and after some simplifications, we get

The convergence rate of the right-hand side can be optimized by setting $\delta_{p}=p^{-1/4}$. This then leads to the claim in (114).

-D Asymptotic Equivalence of the Covariance Matrices

Consider a sequence of activation functions $\left\{\sigma_{p}(x)\right\}$ such that, for every $p$, $\sigma_{p}(x)$ is an odd function and

Suppose that the feature vectors satisfy (64) with some $\kappa_{p}$. We have

For the case of $i=j$, we define $R_{ii}=0$.

Using (141), we can verify the following decomposition of $\boldsymbol{\Sigma}_{a}$:

Since $\boldsymbol{\Sigma}_{b}=\mu_{1,p}^{2}\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}+\mu_{2,p}^{2}\boldsymbol{I}$, we must have

Recall the assumptions about the feature vectors in (64). It then follows from (139) that $\lVert\boldsymbol{D}_{1}\rVert\leq\kappa_{p}\operatorname{polylog}p/\sqrt{p}$. Similarly, we also have $\lVert\boldsymbol{D}_{2}\rVert\leq\kappa_{p}\operatorname{polylog}p/\sqrt{p}$. Controlling $\lVert\boldsymbol{D}_{3}\rVert$ requires a few more steps. Let $z\sim\mathcal{N}(0,1)$ and $T=\sqrt{2\log p}$.

It follows that $\lVert\boldsymbol{R}\rVert\leq\lVert\boldsymbol{R}\rVert_{\text{F}}=\sqrt{\sum_{i,j}R^{2}_{ij}}\leq\kappa^{3}_{p}\operatorname{polylog}p/\sqrt{p}$. Substituting our bounds for $\lVert\boldsymbol{D}_{1}\rVert,\lVert\boldsymbol{D}_{2}\rVert,\lVert\boldsymbol{D}_{3}\rVert$ and $\lVert\boldsymbol{R}\rVert$ into (143), we then reach the bound (140) in the statement of the lemma. ∎

Next, we prove an auxiliary result that will be used in the proof of Theorem 2. Here, we consider a particular sequence of activation functions $\left\{\widehat{\sigma}_{p}(x)\right\}$ as defined in (110). They form a family of smoothly truncated versions of a fixed activation function $\sigma(x)$.

Let $\mu_{1},\mu_{2}$ and $\mu_{1,p},\mu_{2,p}$ be the constants associated with $\sigma(x)$ and $\widehat{\sigma}_{p}(x)$, respectively. If the threshold $\tau_{p}=\sqrt{2C_{\tau}\log p}$ in (110) is chosen with a constant $C_{\tau}\geq 2$, then

By construction, $\sigma(x)=\widehat{\sigma}_{p}(x)$ and $\sigma^{\prime}(x)=\widehat{\sigma}^{\prime}_{p}(x)$ for $\left\lvert x\right\rvert<\tau_{p}$. Let $z\sim\mathcal{N}(0,1)$. We then have

Combining this bound with (146) and recall the definitions of $\mu_{2}$ and $\mu_{2,p}$, we have $\left\lvert\mu_{2}^{2}-\mu_{2,p}^{2}\right\rvert\leq({\operatorname{polylog}p})/{p}$. Finally, the second bound in (145) can be obtained from the following inequality: $\left\lvert\sqrt{x}-\sqrt{y}\right\rvert\leq\sqrt{\left\lvert x-y\right\rvert}$ for any two nonnegative numbers $x$ and $y$. ∎

-E Some Concentration Results

Let $\mathcal{A}_{1}$ be the event defined in (22). There exists a constant $c>0$ such that

We start by stating the following simple result: for \boldsymbol{f}_{1},\boldsymbol{f}_{2}\overset{i.i.d.}{\sim}\mathcal{N}\Big{(}0,\tfrac{1}{d}\boldsymbol{I}_{d}\Big{)}, there exists positive constants $c$ and $K$ such that for any $\varepsilon\geq 0$

Indeed, for any $i\in[d]$, $f_{1,i}$ and $f_{2,i}$ are both sub-Gaussian random variables with sub-Gaussian norm bounded by $\frac{C}{\sqrt{d}}$, for some $C>0$ [47, Example 2.5.8], so $f_{1,i}f_{2,i}$ is a sub-exponential random variable with sub-exponential norm $\frac{C^{2}}{{d}}$ [47, Lemma 2.7.7]. Then we can apply Bernstein’s inequality [47, Corollary 2.8.3] to get (147). Also, (148) can be proved in the same way. Then we can let $\varepsilon=\tfrac{(\log p)^{2}}{\sqrt{p}}$ in (147) and (148) and use union bound to get for any $p$,

For any $i\in[p]$, we have $\boldsymbol{f}_{i}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\xi}\sim\mathcal{N}(0,\tfrac{1}{d})$. Thus, for any $\varepsilon\geq 0$, the standard Gaussian tail bound gives us

By setting $\varepsilon=\tfrac{(\log p)^{2}}{\sqrt{p}}$ and applying union bound, we can obtain (151). Recall the definition of $\mathcal{A}_{1}$ in (22). Combining (149), (150) and (151), we complete the proof. ∎

-E2 Concentration of Lipschitz Functions of Gaussian Vectors

The results presented in this section are all consequences of the following well-known theorem about the concentration of Lipschitz functions of independent Gaussian random variables. See e.g., [48, Theorem 1.3.4] for a proof.

It follows that the function $f(\boldsymbol{g})=\frac{1}{\sqrt{p}}\sigma\left(\boldsymbol{g}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{F}\right)\boldsymbol{\beta}$ is $\frac{\lVert\sigma^{\prime}\rVert_{\infty}\|\boldsymbol{\beta}\|\|\boldsymbol{F}\|}{\sqrt{p}}$-Lipschitz continuous. Therefore, using (152) we have

To establish (156), we observe that $\boldsymbol{b}_{t}$ can be represented as $\boldsymbol{b}_{t}=\boldsymbol{\Sigma}^{1/2}\widetilde{\boldsymbol{b}}$, where $\widetilde{\boldsymbol{b}}\sim\mathcal{N}\left(\boldsymbol{0},\boldsymbol{I}_{p}\right)$. It follows that $\tfrac{1}{\sqrt{p}}\boldsymbol{b}_{t}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{\beta}$ can also be seen as a Lipschitz function of a standard normal vector, with a Lipschitz constant equal to $\frac{\|\boldsymbol{\beta}\|\|\boldsymbol{\Sigma}^{1/2}\|}{\sqrt{p}}$. Therefore (156) is again a consequence of (152). Finally, the moment bounds in (157) and (158) can be obtained by applying (154). ∎

There exists $c>0$ such that for any $t\in[n]$ and $s\geq\sqrt{\tfrac{4d}{p}}\lVert\sigma^{\prime}\rVert_{\infty}\|\boldsymbol{F}\|$,

Similarly, for any $s\geq 2\sqrt{\|\boldsymbol{\Sigma}\|}$, we have

Correspondingly, there exists $C>0$ such that

Recall that $\boldsymbol{a}_{t}=\sigma(\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{g}_{t})$ and $\boldsymbol{g}\mapsto\sigma(\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{g})$ is a $(\lVert\sigma^{\prime}\rVert_{\infty}\|\boldsymbol{F}\|)$-Lipschitz continuous mapping. It follows that $\boldsymbol{g}\mapsto\|\sigma(\boldsymbol{F}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{g})\|~{}(=\|\boldsymbol{a}\|)$ is a $(\lVert\sigma^{\prime}\rVert_{\infty}\|\boldsymbol{F}\|)$-Lipschitz continuous function. From (152), there exists $c>0$ such that for any $s>0$,

For any $s\geq\sqrt{\tfrac{4d}{p}}\lVert\sigma^{\prime}\rVert_{\infty}\|\boldsymbol{F}\|$, we can use (165) and (164) to deduce that

The proof of (161) is analogous. We write $\boldsymbol{b}_{t}=\boldsymbol{\Sigma}^{\frac{1}{2}}\widetilde{\boldsymbol{b}}_{t}$, where $\widetilde{\boldsymbol{b}}_{t}\sim\mathcal{N}\left(\boldsymbol{0},\boldsymbol{I}_{p}\right)$. Therefore, similar to what we did to reach (164), we can show there exists $c>0$ such that for any $s\geq 0$,