Learning non-linear features-or representations-from data is thought to be one of the fundamental reasons for the success of deep neural networks (see e.g., [BCV13, DKD16, YH21, SWL22, RBPB22], etc.). This has been observed in a wide range of domains, including computer vision and natural language processing. At the same time, the current theoretical understanding of feature learning is incomplete. In particular, among many theoretical approaches to study neural networks, much work has focused on two-layer fully-connected neural networks with a randomly generated, untrained first layer weights and a trained second layer-or random features models [RR07]. Despite their simplicity, random features models can capture various empirical properties of deep neural networks, and have been used to study generalization, overparametrization and "double descent", adversarial robustness, transfer learning, estimation of out-of-distribution performance, and uncertainty quantification (see e.g., [MM22, HJ22, TAP21, LMH + 23, BM23, CLKZ23, LD21, ALP22], etc.).
Nevertheless, feature learning is absent in random features models, because the first layer weights are assumed to be randomly generated, and then fixed. Although these models can represent non-linear functions of the data, in the commonly studied setting where the sample size, dimension, Figure 1: Spectrum of the updated feature matrix for di!erent regimes of the gradient step size ω. Spikes corresponding to monomial features are added to the spectrum of the initial matrix. The number of spikes depends on the range of ε. See Theorems 3.1 and 3.2 for details. and hidden layer size are proportional, under certain reasonable conditions they can only learn the linear component of the true model-or, teacher function-and other components of the teacher function e!ectively behave as Gaussian noise. Thus, in this setting, learning in a random features model is equivalent to learning in a noisy linear model with Gaussian features and Gaussian noise. This property is known as the Gaussian equivalence property (see e.g., [GLR + 22, ALP22, AP20a, MM22, MS22, HL23]). While other models such as the neural tangent kernel [JGH18,DZPS19] can be more expressive, they also lack feature learning.
To bridge the gap between random features models and feature learning, several recent approaches have shown provable feature learning for neural networks under certain conditions; see Section 1.1 for details. In particular, the recent pioneering work of [BES + 22] analyzed two-layer neural networks, trained with one gradient step on the first layer. They showed that when the step size is small, after one gradient step, the resulting two-layer neural network can learn linear features. However, it still behaves as a noisy linear model and does not capture non-linear components of a teacher function. Moreover, they showed that for a su"ciently large step size, under certain conditions, the one-step updated random features model can outperform linear and kernel predictors. However, the e!ects of a large gradient step size on the features is unknown. Moreover, what happens in the intermediate step size regime also remains unexplored. In this paper, we focus on the following key questions in this area:
What nonlinear features are learned by a two-layer neural network after one gradient update? How are these features reflected in the singular values and vectors of the feature matrix, and how does this depend on the scaling of the step size? What is the improvement in the training and test errors due to the nonlinear features learned? Main Contributions. Toward answering the above questions, we make the following contributions:
• We study feature learning in two-layer neural networks. Specifically, we follow the training procedure introduced in [DLS22, BES + 22] where one step of gradient descent with step size ω is applied to the first layer weights, and the second layer weights are found by solving ridge regression on the updated features. We consider a step size ω → n ω , ε ↑ (0, 1 2 ) that grows with the sample size n and examine how the learned features change with ε (Section 2.1).
• In Section 3, we present a spectral analysis of the updated feature matrix. We first show that the spectrum of the feature matrix undergoes phase transitions depending on the range of ε.
In particular, we find that if ε ↑ ( ε→1 2ε , ε 2ε+2 ) for some ϑ ↑ {1, 2, . . .}, then ϑ separated singular values-spikes-will be added to the spectrum of the initial feature matrix (Theorem 3.1). Figure 1 illustrates this finding.
• Building on perturbation theory for singular vectors, we argue that the left singular vectors (principal components) associated with the ϑ spikes are asymptotically aligned with polynomial features of di!erent degrees (Theorem 3.2). In other words, the updated feature matrix will contain information about the degree-ϑ polynomial component of the target function.
• The Gaussian equivalence property [HL23,MM22], an essential tool to analyze random features models, fails after a gradient update with a large step size ω. To overcome this di"culty, we establish equivalence theorems (Theorem 4.1 and 4.2) stating that the trained features F can be replaced by sum of the untrained features F 0 and ϑ spikes without changing the training and test errors. Then, by applying the Gaussian equivalence to the untrained component F 0 , we provide a precise characterization of the training and test errors in the high-dimensional proportional regime (Theorem 4.3 and 4.5).
• From the derived results, we show that in the simple case where ϑ = 1, the neural network does not learn non-linear functions. However, in the ϑ = 2 regime, the neural network in fact learns quadratic components of the target function.
Theory of shallow neural networks. Random features models [RR07] have been used to study various aspects of deep learning, such as generalization [MM22, ALP22, LD21, MP21], adversarial robustness [HJ22,BKM23], transfer learning [TAP21], out-of-distribution performance estimation [LMH + 23], uncertainty quantification [CLKZ23], stability, and privacy [BM23]. This line of work builds upon nonlinear random matrix theory (see e.g., [PW17, LLC18, FW20, BP21], etc.) studying the spectrum of the feature matrix of two-layer neural networks at initialization. Two-layer neural networks have been studied extensively in the mean-field regime (see e.g., [CB18, MMN18, MMM19, SS20, RVE22], etc.), and the neural tangent kernel (NTK) regime (see e.g., [JGH18, LXS + 19, HY20], etc.). However, these results often require the neural net to have an extremely large width. In particular, in the NTK regime, this large width will result in features not evolving over the course of training and the model behaves similar to classic kernel methods. [GMMM21] show that for NTKs and other kernel methods, with a sample size linear in size of the input, non-linear functions cannot be learned. See also [Mis22, XHM + 22, LY22]. Perturbative corrections to the large-width regime to capture feature learning have also been studied in the literature (see e.g., [Yai20, HN19, SNR23, NR21], etc.). See Section A for more discussion on related work in deep learning theory.
Feature learning. The problem of feature learning has been gaining a lot of attention recently. [DLS22] study the problem of learning polynomials with only a few relevant directions and show a sample complexity improvement over kernel methods. [CHS + 23] extend these results and analyze multi-task feature learning in two-layer ReLU networks. [WES + 22] empirically show that if learning rate is su"ciently large, an outlier in the spectrum of the weight and feature matrix emerges with the corresponding singular vector aligned to the structure of the training data. [NDL23,WNL23] provide theoretical evidence that three-layer neural networks have provably richer feature learning capabilities than their two-layer counterparts.
Recently, [BES + 22] show that in two-layer neural networks, when the dimension, sample size and hidden layer size are proportional, one gradient step with a constant step size on the first layer weights can lead to feature learning. However, non-linear components of a single-index target function are still not learned. They further show that with a su"ciently large step size, when the teacher function has a non-zero first Hermite coe"cient, and under certain conditions, the updated neural networks can outperform linear and kernel methods. However, the precise e!ects of large gradient step sizes on learning nonlinear features, and their precise e!ects on the loss remain unexplored. [DKL + 23] show that with a sample size proportional to the input dimension d, it is only possible to learn a single direction of multi-index teacher function using gradient updates on the first layer of a two-layer neural network. They also show that for single index models with information exponent (the index of the first non-zero Hermite coe"cient) ϖ, there are hard directions whose learning requires a sample size of order #(d ϑ ). See also [BAGJ21].
High-dimensional asymptotics. We use tools developed in work on high-dimensional asymptotics, which dates back at least to the 1960s [Rau67,Dee70,Rau72]. Recently, these tools have been used in a wide range of areas such as wireless communications (e.g., [TV04,CD11], etc.), high-dimensional statistics (e.g., [RY04, Ser07, PA14, YBZ15, DW18], etc.), and machine learning (e.g., [GT90, Opp95, OK96, CL22, EVdB01], etc.). In particular, the spectrum of so-called information plus noise random matrices that arise in Gaussian equivalence results has been studied in [DS07,Péc19] and its spikes in [Cap14].
Notation. We let N = {1, 2, . . .} be the set of positive integers. For a positive integer d ↓ 1, we denote [d] = {1, . . . , d}. We use O(•) and o(•) for the standard big-O and little-o notation. For a matrix A and a non-negative integer k, A ↑k = A ↔ A ↔ . . . ↔ A is the matrix of the k-th powers of the elements of A. For positive sequences (A n ) n↓1 , (B n ) n↓1 , we write A n = #(B n ) or A n → B n or A n ↗ B n if there is C, C ↔ > 0 such that CB n ↓ A n ↓ C ↔ B n for all n. We use O P (•), o P (•), and # P (•) for the same notions holding in probability. The symbol ↘ P denotes convergence in probability.
In this paper, we study a supervised learning problem with training data (x i , y i ) ↑ R d ≃ R, for i ↑ [2n], where d is the feature dimension and n ↓ 2 is the sample size. We assume that the data is generated according to
⇐ N(0, I d ), and
in which f ϖ is the ground truth or teacher function, and ϱ i i.i.d.
⇐ N(0, ς 2 ϱ ) is additive noise. We fit a model to the data in order to predict outcomes for unlabeled examples at test time; using a two-layer neural network. We let the width of the internal layer be N ↑ N. For a weight matrix W NN ↑ R N ↗d , an activation function ς : R ↘ R applied element-wise, and the weights a NN ↑ R N of a linear layer, we define the two-layer neural network as
Following [DLS22, BES + 22], for the convenience of the theoretical analysis, we split the training data into two parts:
We train the two layer neural network as follows. First, we initialize a NN with N →1/2 a where a = (a 1 , . . . , a N ) ↘ in which a i i.i.d.
⇐ N (0, 1/N ), and initialize
⇐ Unif(S d→1 ) where S d→1 is the unit sphere in R d and Unif(S d→1 ) is the uniform measure over it. Although we choose this initialization for a simpler analysis, many arguments can be shown to hold if we switch from the uniform distribution over the sphere to a Gaussian; for example, see Section N.5. Fixing a NN at initialization, we perform one step of gradient descent on W NN with respect to the squared loss computed on (X, y). Recalling that ↔ denotes element-wise multiplication, the (rescaled) negative gradient can be written as
and the one-step update is W = w 1 , . . . , w N ↘ = W 0 + ω G for a learning rate or step size ω.
After the update on W NN , we perform ridge regression on a NN using ( X, ỹ). Let F = ς( XW ↘ ) ↑ R n↗N be the feature matrix after the one-step update. For a regularization parameter ↼ > 0, we set â = â(F) = arg min
Then, for a test datapoint with features x, we predict the outcome ŷ = f W,â (x) = â↘ ς (Wx).
Our theoretical analysis applies under the following conditions:
Condition 2.1 (Asymptotic setting). We assume that the sample size n, dimension d, and width of hidden layer N all tend to infinity with
We further consider the following model for the teacher function, leading to a single-index model.
Condition 2.2. We let
This condition is in line with prior work (see e.g., [BES + 22, HL23, GLR + 22], etc.). Recently, [DKL + 23] showed that under Condition 2.1, two-layer neural networks trained with one gradient descent step can only learn a single-index approximation of a multi-index model. This shows that when studying a single-step update, 2.2 is not restrictive.
We let H k , k ↓ 1 be the (probabilist's) Hermite polynomials on R defined by
for any x ↑ R. These polynomials form an orthogonal basis in the Hilbert space L 2 of measurable functions f : R ↘ R such that f 2 (x) exp(⇒x 2 /2)dx < ⇔ with inner product ↖f, g↙ = f (x)g(x) exp(⇒x 2 /2)dx. The first few Hermite polynomials are H 0 (x) = 1, H 1 (x) = x, and
Condition 2.3. The activation function ς : R ↘ R has the following Hermite expansion in L 2 :
The coe!cients satisfy
for some C, ⇁ > 0 and for all k ↓ 1. Moreover, the first three derivatives of ς exist almost surely, and are bounded.
Note that in this paper, unlike [HL23], we do not require the activation function to be odd. The reason is that here, unlike [HL23], we do not analyze the problem for a general loss function and use a proof technique specialized for squared loss. We remark that the above condition requires c 0 = 0, i.e., that Eς(Z) = 0 for Z ⇐ N(0, 1). This condition is in line with prior work in the area (e.g., [AP20a, BES + 22], etc.), and could be removed at the expense of more complicated formulas and theoretical analysis. The smoothness assumption on ς is also in line with prior work in the area (see e.g., [HL23, BES + 22], etc.). Note that the above condition is satisfied by many popular activation functions (after shifting) such as the ReLU ς(x) = max{x, 0} ⇒ 1 ⇑ 2φ , hyperbolic tangent ς(x) = e x →e →x e x +e →x , and sigmoid ς(x) = 1 1+e →x ⇒ 1 2 , for all x. We also make similar assumptions on the teacher activation:
Condition 2.4. The teacher activation ς ϖ : R ↘ R has the following Hermite expansion in L 2 :
with Z ⇐ N(0, 1). Also, we define
The first step in analyzing the spectrum of the feature matrix F is to study the matrix rescaled negative gradient
, where the Hermite coe"cient c 1 of the activation ς is defined in Condition 2.3, and ω = 1 n X ↘ y ↑ R d ; i.e., the matrix G can be approximated (in operator norm) by the rank-one matrix c 1 aω ↘ with high probability. Moreover, under Conditions 2.1-2.4, [BES + 22] show that ω can be understood as a noisy estimate of ω ϖ , namely
.
(3) See also Lemma J.1. In particular, if the sample size used for the gradient update is very large; i.e., ↽ ↘ 0, ω will converge to being completely aligned to ω ϖ .
Building on this result, we show the spectrum of the feature matrix F = ς( X(W 0 + ωG) ↘ ) will consist of a bulk of singular values that stick close together-given by the spectrum of the initial feature matrix F 0 = ς( XW ↘ 0 )-and ϑ separated spikesfoot_0 , where ϑ is an integer that depends on the step size used in the gradient update. Specifically, when the step size is ω → n ω with ε→1 2ε < ε < ε 2ε+2 for some ϑ ↑ N, the feature matrix F can be approximated in operator norm by the untrained features F 0 = ς( XW ↘ 0 ) plus ϑ rank-one terms, where the left singular vectors of the rank-one terms are aligned with the non-linear features X ∞ ↘ ( Xω) ↑k , for k ↑ [ϑ]. See Figure 2. Theorem 3.1 (Spectrum of feature matrix). Let ω → n ω with ε→1 2ε < ε < ε 2ε+2 for some ϑ ↑ N. If Conditions 2.1-2.4 hold, then for c k from Condition 2.3 and F 0 = ς( XW ↘ 0 ),
where
To understand ( Xω) ↑k (a ↑k ) ↘ , notice that for a datapoint with features xi , the activation of each neuron is proportional to the polynomial feature ( x↘ i ω) k , with coe"cients given by a ↑k for the neurons. The spectrum of the initial feature matrix F 0 is fully characterized in [PW17, BP21, BP22, LLC18, FW20], and its operator norm is known to be # P ( ⇑ n). Moreover, it follows from the proof that the operator norm of each of the terms
is with high probability of order larger than ⇑ n. Thus, Theorem 3.1 identifies the spikes in the spectrum of the feature matrix.
Proof Idea. We approximate the feature matrix F = ς( XW ↘ 0 + XG ↘ ) by a polynomial using its Hermite expansion. Next, recalling that G ∈ c 1 ωa ↘ , we set ( XG ↘ ) ↑k to c k 1 ( Xω) ↑k (a ↑k ) ↘ . We show that the spike terms with k ↓ ϑ + 1 are negligible since we can show that their norm is
The special case where ε = 0 is discussed in [BES + 22, Section 3], which focuses on the spectrum of the updated weight matrix W = W 0 + ωG. However, here we study the updated feature matrix F = ς( X(W 0 + ωG) ↘ ) because that is more directly related to the learning problem-as we will discuss in the consequences for the training and test errors below.
In the following theorem, we argue that the subspace spanned by the non-linear features {ς( Xw i )} i≃[N ] can be approximated by the subspace spanned by the monomials
where the minimum is over ϑ ≃ ϑ orthogonal matrices [SS90]. This definition is invariant to the choice of U 1 , U 2 . Theorem 3.2. Let F ε be the ϑ-dimensional subspace of R n spanned by top-ϑ left singular vectors (principal components) of F. Under the conditions of Theorem 3.1, we have
This result shows that after one step of gradient descent with step size ω → n ω with ε→1 2ε < ε < ε 2ε+2 , the subspace of the top-ϑ left singular vectors carries information from the polynomials {( Xω) ↑k } k≃ [ε] . Also, recall that by equation 3, the vector ω is aligned with ω ϖ . Hence, it is shown that F ε carries information from the first ϑ polynomial components of the teacher function.
Proof Idea. We use Wedin's theorem [Wed72] to characterize the distance between the left singular vector space of ε k=1 c k 1 c k ω k ( Xω) ↑k (a ↑k ) ↘ and that of F. Here, we consider the matrix F 0 + ! as the perturbation term.
In the previous section, we studied the feature matrix F and showed that when ω → n ω with ε→1 2ε < ε < ε 2ε+2 , it can be approximated by F 0 = ς( XW ↘ 0 ) plus ϑ rank-one or spike terms. We also saw that the left singular vectors of the spike terms are aligned with the non-linear functions X ∞ ↘ ( Xω) ↑k . Intuitively, this result suggests that after the gradient update, the trained weights are becoming aligned with the teacher model and we should expect the ridge regression estimator on the learned features to achieve better performance. In particular, when ε > 0, we expect the ridge regression estimator to capture the non-linear part of the teacher function. This is impossible for ω = O(1) [BES + 22] or ω = 0 [HL23,MM22].
In this section, we aim to make this intuition rigorous and show that the spikes in the feature matrix lead to a decrease in the error achieved by the estimator. Moreover, for large enough step sizes, the model can learn non-linear components of the teacher function. For this, we first need to prove equivalence theorems showing that instead of the true feature matrix F, the approximations from Theorem 3.1 can be used to compute error terms (i.e., the e!ect of ! on the error is negligible).
The Gaussian equivalence property ([GLR + 22, HL23, MS22], etc.) implies that the training and test errors of a random features model are asymptotically the same as that of a noisy linear model. In other words, the limiting behavior of these quantities is unchanged if we replace the untrained feature matrix F 0 = ς( XW ↘ 0 ) with F 0 = c 1 XW ↘ 0 + c >1 Z, where Z ↑ R n↗N is an independent random matrix with i.i.d. N(0, 1) entries. This property has been used extensively in work on random features models (see e.g., [AP20b, AP20a, TAP21, MP21], etc.) as it provides a powerful tool to analyze non-linear random matrices. However, the Gaussian equivalence property fails when the weight matrix W is updated with a large gradient descent step [BES + 22], posing a significant challenge to the analysis.
In this section, we first prove that we can replace the trained features F with their approximation F ε from Theorem 3.1 in terms of F 0 and spikes, without changing the limiting training and test errors. Then, in the next sections we will see that the training and test errors can be derived by applying the Gaussian equivalence property to the untrained features F 0 only. Given a regularization parameter ↼ > 0, recalling the ridge estimator â(F) from equation 2, we define the training loss
In the next theorem, we show that when ω → n ω with ε→1 2ε < ε < ε 2ε+2 , the training loss L tr (F) can be approximated with negligible error by L tr (F ε ). In other words, the approximation of the feature matrix from Theorem 3.1 can be used to derive the asymptotics of the training loss.
Theorem 4.1 (Training loss equivalence). Let ω → n ω with ε→1 2ε < ε < ε 2ε+2 for some ϑ ↑ N and recall F ε from equation 4. If Conditions 2.1-2.4 hold, then for any fixed ↼ > 0, with probability
Similar equivalence results can also be proved for the test error, i.e., the average test loss. For any a ↑ R N , we define the test error of a as L te (a) = E f ,y (y ⇒ f ↘ a) 2 , in which the expectation is taken over (x, y) where f = ς(Wx) with x ⇐ N(0, I d ) and y = f ϖ (x) + ϱ with ϱ ⇐ N(0, ς 2 ϱ ). The next theorem shows that one can also use the approximation of the feature matrix from Theorem 3.1 to derive the asymptotics of the test error.
Theorem 4.2 (Test error equivalence). Let ω → n ω with ε→1 2ε < ε < ε 2ε+2 for some ϑ ↑ N, and F ε be defined as in equation 4. If Conditions 2.1-2.4 hold, then for any
Proof Idea. To prove Theorem 4.2, we show first show that the norm of the trained second layer weight â, is O P (1). Then, we use Theorem 3.1 to conclude the proof. To prove Theorem 4.2, we will use a free-energy trick [ASH19, HL23, HJ22]. We first extend Theorem 4.1 and show that for any ↼, ζ > 0, the minima over a of
for F = F and F = F ε are close. Then, we use this to argue that the limiting test errors are also close.
With Theorem 4.1 and 4.2 in hand, for ω → n ω , we can use the approximation F ε -with the appropriate ϑ-of the feature matrix F to analyze the training and test error.
In this section, we quantify the discrepancy between the training loss of the ridge estimator trained on the new-learned-feature matrix F and the same ridge estimator trained on the untrained feature matrix F 0 . We will do this for the step size ω → n ω with ε→1 2ε < ε < ε 2ε+2 for various ϑ ↑ N.
Our results depend on the limits of traces of the matrices (F 0 F ↘ 0 + ↼nI n ) →1 and X↘ (F 0 F ↘ 0 + ↼nI n ) →1 X. These limits have been determined in [ALP22,AP20a], see also [PW17,Péc19], and depend on the values m 1 , m 2 > 0, which are the unique solutions of the following system of coupled equations, for ↼ > 0:
where
Here, m 1 is the limiting Stieltjes transform of the matrix 1 n F 0 F ↘ 0 and m 2 is an auxiliary transform. For instance, we leverage that under Condition 2.1, we have
See Lemma J.4 and its proof for more details. For instance, as argued in [PW17, ALP22], these can be reduced to a quartic equation for m 1 and are convenient to solve numerically. However, the existence of these limits does not imply our results; on the contrary, the proofs of our results require extensive additional calculations and several novel ideas.
Theorem 4.3. If Conditions 2.1-2.4 are satisfied, and we have c 1 , • • • , c ε ∝ = 0, as well as ω → n ω with ε→1 2ε < ε < ε 2ε+2 , then for the learned feature map F and the untrained feature map F 0 , we have
where % ε can be found in Section K.
The expression for % ε is complex and given in Section K due to space limitations. For a better understanding of Theorem 4.3, we consider two specific cases, ϑ = 1 and ϑ = 2.
Corollary 4.4. Under the assumptions of Theorem 4.3, for ϑ = 1, we have L tr (F 0 ) ⇒ L tr (F) ↘ P % 1 with
For ϑ = 2, we have L tr (F 0 ) ⇒ L tr (F) ↘ P % 2 with
The above result shows that after one gradient step with su"ciently large step size, the model can fit nonlinear components of the teacher function. This is impossible with a small step size. For example, when ϑ = 1, the improvement in the loss is increasing in the strength of the linear component c ϖ,1 , keeping the signal strength c ϖ fixed. This is not the case for the strength of the non-linear component c 2 ϖ,>1 = c 2 ϖ ⇒ c 2 ϖ,1 . When we further increase the step size to the ϑ = 2 regime, the loss of the trained model will drop by an additional positive value, depending on the strength c ϖ,2 of the quadratic signal, which shows that the quadratic component of the target function is being fit. Also, note that if c ϖ,1 = 0; i.e., if the information exponent (the index of the first non-zero Hermite coe"cient) of ς ϖ is greater than one, the gradient step does not change the limiting loss. In this case, according to equation 3, the alignment between the learned direction ω and the true direction ω ϖ will converge to zero. It is known that learning single-index functions with information exponent greater than one requires a sample size of order larger than d [DKL + 23].
The limiting value of the test error can be analyzed similarly.
Theorem 4.5. Let Conditions 2.1-2.4 and the assumptions of Theorem 4.2 hold. If c 1 ∝ = 0, then
where ' 1 does not depend on the target function.
If further c 2 ∝ = 0, then for ϑ = 2, we have
where ' 2 does not depend on the target function. The complete expressions for ' 1 and ' 2 can be found in equation 64 and equation 87, respectively.
Similar to the training loss result, when ϑ = 1, the improvement in the test error is increasing in c ϖ,1 ; keeping the signal strength c ϖ fixed. Moreover, the improvement in the test error for ϑ = 2 depends on the strength c ϖ,2 of the quadratic signal, showing that the nonlinear component is being learned.
Proof Idea. Using Theorem 4.1 and 4.2, in the expression for the training and test error, we replace the trained features matrix F with its approximation F ε from Theorem 3.1. Then, by applying the Woodbury formula, we express the training and test errors in terms of R0 = (F 0 F ↘ 0 + ↼nI n ) →1 and the non-linear spikes from Theorem 3.1. Using the Gaussian equivalence property (Appendix I) for the untrained features F 0 , we show that the interaction between the first ϑ Hermite components of ỹ and the spike terms will result in non-vanishing terms corresponding to learning di!erent components of the target function. Finally, we compute the limiting value of these terms in terms of m 1 , m 2 and their derivatives using tools from random matrix theory.
Recently, [ABAB + 21, AAM22] show that when learning Boolean functions, under certain conditions on the teacher function, a two-layer trained by SGD in the mean-field regime will learn the target function incrementally; i.e., Fourier coe"cients of higher order are sequentially learned over time. [BMZ23] study the problem of learning a single-index function using a wide two-layer neural network trained using gradient flow, and show that in a specific training setting where the stepsizes for the first layer are much smaller than those of the second layer, the decrease rate of training error is non-monotone; there are long plateaus where there is barely any progress, and there are intervals of rapid decrease.
In the one-step updated two layer neural network, we observe a similar phenomenon. Theorems 4.5 and Theorem K.1 show that given ϑ ↑ N, the errors of the trained model is asymptotically constant for all ω = cn ω with ε→1 2ε < ε < ε 2ε+2 and c ↑ R. There are sharp jumps at the edges between regimes of ε, whose size is precisely characterized above. This shows that a non-monotone rate of decrease in training and test error can also be seen after one step of gradient descent, as a function of step size. For an illustration of this phenomenon, see Figure 3 (Right).
To support and illustrate our theoretical results, we present some numerical simulations. We use the shifted ReLU activation ς(x) = max(x, 0) ⇒ 1/ ⇑ 2π, n = 1000, N = 500, d = 300, and the regularization parameter ↼ = 0.01.
Singular Value Spectrum of F. We let the the teacher function be
), set the noise variance ς 2 ϱ = 0.5, and the step size to ω = n 0.29 , so ϑ = 2. We plot the histogram of singular values of the updated feature matrix F. In Figure 2, we see two spikes corresponding to Xω, ( Xω) ↑2 as suggested by Theorem 3.1 and 3.2. Since f ϖ has a linear component H 1 and a quadratic component H 2 , these spikes will lead to feature learning.
Quadratic Feature Learning. To support the findings of Corollary 4.4 and Theorem 4.5 for ϑ = 2, we consider the following two settings:
Note that c ϖ,1 and c ϖ + ς 2 ϱ are same in these two settings. This ensures that the improvement due to learning the linear component is the same. We plot the training and test errors of the two-layer neural networks trained with the procedure described in Section 2.1 as functions of log(ω)/ log(n). In Figure 3 (Left), we see that the errors decrease in the range log(ω)/ log(n) ↑ (0, 1 4 ) as the model learns the linear component H 1 (ω ↘ ϖ x). In the range log(ω)/ log(n) ↑ ( 1 4 , 1 3 ), the model starts to learn the quadratic feature. However since the quadratic feature is not present in Setting 1, the errors under the two settings diverge. Although the proofs reveal that the convergence rates of the training/test errors after one step can be slow, these results are consistent with Corollary 4.4 and Theorem 4.5.
We have studied feature learning in two-layer neural networks under one-step gradient descent with step size ω → n ω , ε ↑ (0, 1 2 ). We showed that if ε ↑ ((ϑ ⇒ 1)/(2ϑ), ϑ/(2ϑ + 2)), the gradient update will add ϑ separated singular values to the initial feature matrix spectrum corresponding to di!erent nonlinear features. We then proved equivalence theorems and used them to derive a precise characterization of the training and test errors in the high-dimensional proportional limit. Using this, we showed that in certain examples, non-linear components of the teacher function are learned.
Future Work. In this paper, we only study the problem when ω → n ω with ε ↑ ((ϑ⇒1)/(2ϑ), ϑ/(2ϑ+ 2)). The boundary case where ω → n (ε→1)/(2ε) is an interesting problem and is left as future work. Also, following prior work in the area (see e.g., [DLS22, BES + 22, DKL + 23, NDL23, WNL23], etc.), we use sample splitting in our two-step training procedure. Although this setting is natural for the analysis of pretrained models, it does not cover the case where feature learning and ridge regression use the same data. We leave this setting as a future direction.
In this paper, we focused on the case where ε < 1/2. The behaviour of the feature matrix can be significantly di!erent when ε = 1/2. When ε < 1/2, as proved in this paper, the spectrum of the feature matrix will consist of a finite number of spikes added to the spectrum of the untrained feature matrix. However, when ε = 1/2, the behaviour can deviate from the spectrum of the untrained model in other ways. Note that according to Theorem 3.1, the number of spikes in the spectrum of F will increase as we increase ε from 0 to 1/2 and will diverge as we approach 1/2. The limiting empirical singular-value distribution of the feature matrix and the training and test errors of the network when ε = 1/2 is an open problem and we leave it as future work.
[GK19] provide a polynomial time algorithm that learns neural networks with two non-linear layers. Our setting is di!erent because we do not apply a non-linear activation after the second layer. [CGKM22] show that learning two-hidden-layer neural networks from noise-free Gaussian data requires superpolynomially many statistical queries. [ZWL22] show that neural networks trained by gradient descent can succeed on problems where the labels are determined by a set of class-relevant patterns and if these patterns are removed, no polynomial algorithm in the Statistical Query model can learn even weakly.
In the appendix, we use the following additional notations. We let N 0 = {0, 1, 2, . . .} be the set of non-negative integers. For a set X and x 1 , x 2 ↑ X, ▷ x 1 ,x 2 is the Kronecker delta, which equals unity if x 1 = x 2 , and is zero otherwise. We use Õ(•) for the standard big-O notation up to logarithmic factors in n. For a positive integer k, k!! is the product of all the positive integers up to n with the same parity as n. For two random quantities X, Y , X △ △ Y denotes that X is independent of Y . By orderwise analysis, we mean bounding a term by the triangle inequality and the inequality ⇓Ab⇓ 2 ′ ⇓A⇓ op ⇓b⇓ 2 for a conformable matrix-vector pair A, b, to reduce it to operator norms of matrices and Euclidean norms of vectors, and then use simple bounds for those quantities. Constants such as C, c ↔ , etc., can change from line to line unless specified otherwise. For two random quantities A, B, A = d B denotes that A and B have the same distribution. Limits of random variables are understood in probability. For two matrices A, B with equal shape, we write A ↔ B to denote their entry-wise (Hadamard) product.
We denote Xω = ε, Xω = ε, Xω ϖ = ε ϖ , and Xω ϖ = εϖ . We also define R0 = (F 0
Lemma C.1 (Orthogonality of Hermite polynomials). Let (Z 1 , Z 2 ) be jointly Gaussian with
In particular, if for some positive integer d, Z ⇐ N(0, I d ), and if a, b ↑ S d→1 , then
Lemma C.2 (Taylor expansion of Hermite polynomials). For any k ↑ N 0 and x, y ↑ R,
. By Taylor expanding H k (x + y) at y, we find
x j H k→j (y).
The following Lemma, proved in Section N.1, provides several bounds used in the proofs.
Lemma C.3. Under Conditions 2.1-2.4, there exists C > 0 such that the following holds with
By Lemma J.1 with v = ω ϖ and D = I d , we have
. By the continuous mapping theorem, we conclude
The feature matrix is given by
Note that we have
. With these, it can easily be verified that the e!ect of ! in the following arguments is negligible (see [DKL + 23, Lemma 12] for more details).
We consider any fixed W 0 such that the event
whose operator norm is O(j!) on (. Thus by [Ver12, Theorem 5.48] and Markov's inequality, for any j ↑ [L], for t ↓ (Cnj!) 1/2 , and with
Next, we observe that since H j is a j-th degree polynomial and the normal absolute moments increase with
by simply expanding the norms. Thus, on the event (, one can verify that for all x, ⇓(W 0 x) ↑j ⇓ 2 ′ C ↔ j ⇓x⇓ 2j for some C ↔ j > 0. Also, we have that
are sub-Weibull random variables with tail parameter 1/(2j), (see e.g., [VGNA20,ZC21]). Thus, by the maximal inequality for sub-Weibull random variables [KC22, Proposition A.6 and Remark A.1], it follows that for all j ↓ 1, there is
with probability 1 ⇒ o(1).
with probability 1 ⇒ o(1). Since ω = o( ⇑ n), the rows of have W norm of O P (1). Thus, we can repeat the same argument to show that with probability 1 ⇒ o(1), we have
. We can write
By Lemma C.2, using W = W 0 + ω G so that XW ↘ = XW ↘ 0 + ω XG ↘ , and using that H 0 (z) = 1 for all z ↑ R,
Therefore, setting G = c 1 aω ↘ , we have
with probability 1 ⇒ o(1). Also, since
we also have
This proves that with probability 1 ⇒ o(1), we have
. This, alongside equation 11 and equation 12, concludes the proof.
) ↘ has rank ϑ almost surely and its left singular vector space is span{( Xω) ↑k } k≃ [ε] . Also, the subspace spanned by the top-ϑ left singular vectors of F is F ε . By Wedin's theorem [Wed72], [CCFM21, Theorem 2.9], and as ε > ε→1 2ε , we have
which concludes the proof.
By the definition of â(F), we have max
Thus,
A similar argument gives
Also, by the triangle inequality, and using equation 14 and Theorem 3.1, which states
Similarly, we can prove that
For a = â(F) or a = â(F ε ),
by equation 13, equation 14, equation 15, equation 16, and Theorem 3.1. Therefore, using the definition of â(F ε ),
and using the definition of â(F),
These together prove the theorem.
First, we will prove a general lemma regarding the equivalence of an augmented training loss. We will later use this result to prove the equivalence of the test error.
Lemma H.1. Let ω → n ω with ε→1 2ε < ε < ε 2ε+2 for some ϑ ↑ N and F ε be defined as in equation 4. For the test error L te from Section 4.1, define
Then, for any
with probability 1 ⇒ o(1).
Proof of Lemma H.1. Letting â↼ (F) = arg min a R ↼ (a, F), we can write max
Thus,
A similar argument gives
Also by the triangle inequality, equation 19 and Theorem 3.1, which states
Similarly, we can show that
For a = â↼ (F) or a = â↼ (F ε ),
by equation 18, equation 19, equation 20, equation 21, and Theorem 3.1. Therefore, using the definition of â↼ (F ε ),
and using the definition of â↼ (F),
Putting these together, we have
which concludes the proof. Now, we use this lemma to prove the equivalence of the test error.
Proof of Theorem 4.2. We will argue by contradiction. Assume that
. Now, consider the following two optimization problems:
Without loss of generality, assume that L F < L F ω . The solution of the first optimization problem will still converge to L tr (F) because L F < L. However, the solution of the second optimization problem will converge to a value greater than L tr (F ε ), because L F ω > L and the objective is ↼-strongly convex. Note that by Theorem 4.1, we asymptotically have L tr (F ε ) = L tr (F). Thus L 1 and L 2 converge to di!erent quantities as n ↘ ⇔. However, using the minimax theorem and since the objectives are ↼-strongly convex, we can write
According to Lemma H.1, the two minima above converge to the same value for any fixed ζ. Note that, as functions of ζ, both maxima are concave as they are minima of linear functions of ζ. Hence, by using the concave version of [ASH19, Lemma 1], we have that L 1 and L 2 converge to the same value, which is a contradiction.
Gaussian equivalence results for non-linear random matrices were introduced in [EK10, CS13
, FM19]. They have been repeatedly used in recent studies of random feature models [MM22, MRSY19, AP20a, AP20b, TAP21, GLR + 22, MP21, dGSB21, LGC + 21, LMH + 23, HJ22, HL23, MS22]. Also, there has been progress on proving the Gaussian equivalence property for a multi-layer network with only the final layer trained [BPH23, CKZ23].
In more distantly related work in random matrix theory literature, the phenomenon that eigenvalue statistics in the bulk spectrum of a random matrix do not depend on the specific law of the matrix entries is referred to as "bulk universality" [Wig55, Gau61, Meh04, Dys62, EPR + 10, EYY12, EK10, TV11]. [Erd19] shows that local spectral laws of correlated random Hermitian matrices can be fully determined by their first and second moments, through the matrix Dyson equation. Also, [BMP15,BNY20] show that spectral distributions of correlated symmetric random matrices can be characterized by Gaussian matrices with matching correlation structures.
In our case, we apply the Gaussian equivalence property to the following quantities for p, q ↑ N 0 and ω 1 , ω 2 ↑ {ω, ω ϖ }: H p ( Xω 1 ) ↘ R0 H q ( Xω 2 ).
In this section, we describe the proof idea of the Gaussian equivalence property. We use the Lindeberg exchange method [Lin22] in which we replace each column
⇐ N(0, I n ). Hereafter, we condition on all random variables except W 0 . Then, H p ( Xω 1 ) and H q ( Xω 2 ) become deterministic vectors with O(1) entries. We write v = H p ( Xω 1 ), w = H q ( Xω 2 ), and for all i
. By the triangle inequality,
Defining
, we have by the Sherman-Morrison formula that
, and
Plugging into equation 23,
where the first and second inequalities follow from the definition of the operator norm, and the last one follows from the Cauchy-Schwarz inequality.
By [EK10, Theorem 2.1], ⇓" g ⇒ " g⇓ op ↘ P 0. Therefore,
J Proofs of Results from Section 4.2
Here, we will prove the results in Section 4.2. First, we will provide several lemmas, which will be used in our proofs. The first lemma allows us to approximate linear and quadratic forms of ω in terms of ω ϖ ; the quadratic form result is from [BES + 22]. Its proof is in Section N.2.
Lemma J.1. For any d ↑ N, let v ↑ R d and D ↑ R d↗d be vectors and matrices, fixed or independent of X, ω ϖ , ϱ 1 , . . . , ϱ n , and satisfy ⇓v⇓ 2 , ⇓D⇓ op ′ C almost surely, uniformly for some constant C > 0. Under Condition 2.1, we have
We will use the expression derived for the training loss in the following lemma; see Section N.3 for the proof.
Lemma J.2. The training loss L tr (F) can be written as
The following lemma will be used in proving concentration of certain quadratic forms appearing in the proofs; see Section N.4 for the proof.
Lemma J.3. Let g : R ↘ R be a polynomial, D ↑ R n↗n be a matrix with ⇓D⇓ op = O P (1/n), and Z ↑ R n be a vector of i.i.d. Gaussian random variables with bounded variance independent of D. We have
in which g is applied elementwise.
The limiting values of two key quadratic forms appearing in the proof are derived in the following lemma, whose proof is deferred to Section N.5.
Lemma J.4. Let m 1 and m 2 be the solutions to the system of fixed point equations from equation 5.
Then, the following holds:
In particular, ⇀(c
The following lemmas will be used in the computations. We defer the proofs of these lemmas to Sections N.6, N.7, N.8, and N.9 respectively. Lemma J.5. For any p, q ↑ N 0 , p ∝ = q and any vector u ↑ R n , with ⇓u⇓ 2 = 1 independent of R0 , we have H q ( Xu) ↘ R0 H p ( Xu) = o P (1).
Lemma J.6. For any p ↑ N, we have
Lemma J.7. For s ↑ {1, 2}, p ↑ N, and p ∝ = s, we have H p ( Xω ϖ ) ↘ R0 ( Xω) ↑s = o P (1). Further,
Lemma J.8. We have
Now, we will first provide a proof of Theorem 4.3 in the case of ϑ = 1 and ϑ = 2 for a better insight into the proof techniques. We will then prove the general form in Section K.
In the ϑ = 1 regime, due to Theorem 4.1, we can replace F by F 1 (defined in equation 4) to compute the training loss. Hence, from now on we let F = F 1 . We can write
Based on Lemma J.2, the training loss depends on R = (FF ↘ + ↼nI n ) →1 . Using the Woodbury formula, this matrix can be written in terms of R0 = (F 0
Defining T = (K →1 + U ↘ R0 U) →1 ↑ R 2↗2 and substituting R = R0 ⇒ R0 UTU ↘ R0 in the formula for training loss in Lemma J.2, we find
Using equation 25 and U = [ F 0 a | Xω ], the loss di!erence can be written as
in which T ij are the elements of the matrix T. Using
we will compute the limit of each term appearing in equation 26 separately:
Term 1. The first term can be written as
Based on Lemma J.4, we know that ω ↘ X↘ R0 Xω and a ↘ F ↘ 0 R0 F 0 a ⇒ ⇓a⇓ 2 2 are # P (1). Also, it can easily be seen that
where in the last inequality, we used that ỹ↘ R0 ỹ ′ 1 λn ⇓ ỹ⇓ 2 2 = O P (1) and ỹ↘ R2 0 ỹ ′ 1 (λn) 2 ⇓ ỹ⇓ 2 2 = o P (1). Putting everything together, it follows that ▷ 1 = o P (1) in probability.
Term 2 and Term 3. The second and third terms can be written as
Recall from the above argument that the denominator is # P (1) and that 1
. Therefore, we find ▷ 2 = ▷ 3 = o P (1).
Term 4. This term can be written as Further by Lemma J.1,
where the final limit follows from the proof of Lemma J.4. By summing up the fours terms computed above and using Lemma J.4, we find
which concludes the proof for ϑ = 1.
In the ϑ = 2 regime, based on Theorem 4.1, we can replace F with F 2 (defined in equation 4) to compute the training loss. Hence, from now on we let F = F 2 . We can write
, we have the following analogue to equation 25:
Denoting in what follows Q = F ↘ 0 R0 F 0 , the inverse T →1 can be written as follows:
J.2.1 Analysis of Terms in T →1 and T
In the following section, we will first analyze the elements of T →1 :
(1,1): The term a ↘ Qa ⇒ ⇓a⇓ 2 2 has already been analyzed in Lemma J.4 and is # P (1).
(1,2) and (2,1):
Introducing ã = ⇑ N a ⇐ N(0, I N ), and as H 2 (x) = x 2 ⇒ 1 for all x, we find
The second term converges to zero as n ↘ ⇔ because a ⇐ N(0, 1 N I N ) is independent of R 0 , and
. Moreover, the first term also converges to zero; indeed,
Lemma J.3 can be used with D = R to prove the concentration of both term around their expectation. Note that the expectation of ã↘ R 0 H 2 (ã) is zero because of the orthogonality property of Hermite polynomials and the independence of ã and R 0 . Putting everything together, we conclude that
(1,3) and (3,1): Recalling that ε = Xω, it follows from equation 28 that this term is o P (1).
(1,4) and (4,1): To bound a ↘ F ↘ 0 R0 ε↑2 , note that
Hence, because a ⇐ N(0,
(2,2): This term is O P (1), because a ⇐ N(0,
(2,3) and (3,2):
Also, by Lemma J.1, we have
X, which has bounded norm in probability.
(2,4) and (4,2): First note that in the regime where ϑ = 2, we have
By Lemma J.6, the first term converges in probability to zero. Moreover, a ⇐ N(0,
. Thus, we have that
. Based on the Gaussian equivalence from Appendix I, we can replace F 0 with F 0 = c 1 XW ↘ 0 + c >1 Z, where Z ↑ R n↗d is an independent random matrix with N(0, 1) entries, without changing the limit. Now, the linearized F 0 is left-orthogonally invariant, hence F 0 has the same distribution as OF 0 , where O is uniformly distributed over the Haar measure of d-dimensional orthogonal matrices, independently of all other randomness. Hence,
(3,4) and (4,3): First, note that defining ω = ω ↖ω↖ 2 , and as H 2 (x) = x 2 ⇒ 1 for all x, we can write
Now, by Lemma J.1, we have ε↘ R0 1 N = c ϖ,1 ε↘ ϖ R0 1 N + o P (1). Now, note that ⇓ X R0 1 N ⇓ 2 = O P (1) and ω ϖ ⇐ N(0, 1 d I d ) is independent of X R0 1 N , which implies that the second term converges to zero. By using Lemma J.5 for u = ω, the first term also converges to zero. Putting these together, we have [T →1 ] 3,4 = [T →1 ] 4,3 = o P (1). Now, putting everything together, the matrix T →1 can be written as
where the all elements of ! 1 are o P (1). Thus the matrix T is equal to
where the all elements of ! 2 are o P (1).
Having computed the limit of the matrix T →1 and T, we are now ready to put everything together and compute the limiting train loss. One can write the outcome vector ỹ as ỹ = ς ϖ ( Xω ϖ ) + ϑ, where ϑ ↑ R n is the noise term. Thus, using equation 31, we find
We will first argue the second and third term will go to zero in probability. To do this, we note that ⇓T⇓ op = O P (1) and also
We have ϑ ⇐ N(0, ς 2 ϱ I n ) and it is independent of R0 , U, T, X, and ω ϖ . Also note that ⇓ς ϖ ( Xω ϖ ) ↘ R0 U⇓ 2 = O P (1). Thus, the second and third term in equation 35 go to zero and we have
If we expand ς ϖ ( Xω ϖ ) in the Hermite basis as ς ϖ ( Xω ϖ ) = ⇐ p=1 c ϖ,p H p ( εϖ ), we can write
We define % p,q = H p ( εϖ ) ↘ R0 UTU ↘ R0 H q ( εϖ ) = ▷ p,q 1 + ▷ p,q 2 + ▷ p,q 3 + ▷ p,q 4 in which, with T i,j being the (i, j)-th elements of the matrix T,
and
We will now look at each ▷ p,q i for i ↑ {1, 2, 3, 4}.
Term ▷ p,q 1 : To prove that the term in equation 36 are asymptotically negligible, note that a ⇐ N(0, 1 N I N ) is independent of H p ( εϖ ) R0 F 0 and we have ⇓H p ( εϖ ) R0 F 0 ⇓ 2 = O P (1). Thus, H p ( εϖ ) R0 F 0 a = o P (1) and all other terms multiplying this are O P (1). This implies that for any p, q ↑ N, we have ▷ p,q 1 = o P (1).
Term ▷ p,q 2 : All four terms in equation 37 converge to zero. To prove this, we will use the Lemma J.6. In equation 37, all terms multiplied by ⇑ NH p ( εϖ ) R0 F 0 a ↑2 are O P (1). Thus, ▷ p,q 2 = o P (1) for any p, q ↑ N.
Term ▷ p,q 3 : The first term in equation 38 converges to zero in probability due to an argument similar to the arguments used for ▷ p,q 1 ; and the same holds for the second term in equation 38, by arguing similarly as for ▷ p,q 2 . We have shown that T 3,4 = o P (1), and by a norm argument, we can see that H p ( εϖ ) ↘ R0 ε and ε↑2↘ R0 H q ( εϖ ) are O P (1). Hence,
Term ▷ p,q 4 : The first two terms in equation 39 converge to zero by the same reasoning used for ▷ p,q 1 and ▷ p,q 2 , respectively. The third term can also be shown to converge to zero by recalling that T 4,3 = o P (1). Hence, we can write
Putting everything together, we find
Using Lemma J.7, we know that in the sums above, the terms corresponding to (p, q) = (1, 1) and (p, q) = (2, 2) are the only non-negligible terms in the first and second sum respectively.
Hence, as T 3,3 = 1/( ε↘ R0 ε) + o P (1) and T 4,4 = 1/( ε↑2↘ R0 ε↑2 ) + o P (1), from Lemmas J.1, J.4, J.7 and J.8, we can write,
We define the values 0 i,j for all i, j ↑ {0, 1, . . .} such that for any p ↑ N and x ↑ R, we have x p = p i=0 0 p,i H i (x). Theorem K.1. Let ϑ ↑ N. If Conditions 2.1-2.4 hold, while we also have c 1 , • • • , c ε ∝ = 0, and ω → n ω with ε→1 2ε < ε < ε 2ε+2 , then for the learned feature map F and the untrained feature map F 0 , we have L tr (F 0 ) ⇒ L tr (F) ↘ P % ε > 0, where
(i+j)/2 0 i,p 0 j,q + o P (1), in which # is an invertible matrix with
and for p ↑ N,
Proof of Theorem K.1. In the regime where ω → n ω with ε→1 2ε < ε < ε 2ε+2 , according to the equivalence theorem 4.1, we can replace F with F ε when computing the limiting training loss. To compute the limiting training loss di!erence according to lemma J.2, we study the matrix R = (FF ↘ + ↼nI n ) →1 . Due to equation 4, we can write
Defining the matrix U as
we can write
where
Using the Woodbury formula, the matrix R can be written in terms of R0 = (F 0
and [ K] i,j = ⇒N (i→1)/2 N (j→1)/2 ↖a ↑i , a ↑j ↙, for all i, j ↑ [ϑ]. We define M 1 , M 2 , M o ↑ R ε↗ε as the following blocks of T →1 :
Hence, we have
We can expand the monomials in terms of the Hermite polynomials, for scalars 0 i,k , k ↑ [i], as follows:
Using these, we will analyze each matrix M 1 , M 2 , M o separately.
Analysis of M 1 . It is easily seen that the elements of this matrix are O P (1).
Analysis of M 2 . To analyze these terms, we need the following lemma, whose proof is deferred to Section N.10.
Lemma K.2. For any i, j ↑ N 0 , we have
Defining the matrix M2 ↑ R ε↗ε with entries
Recalling that for all i, j ↑ {0, 1, . . .}, 0 i,j are such that such that for any p ↑ N and x ↑ R, we have x p = p i=0 0 p,i H i (x), it follows that the matrix Z is lower-triangular with unit diagonal; hence invertible. Thus, since B, M are diagonal with positive entries, the matrix BZMZ ↘ B is positive definite. This implies that M2 is invertible. We will denote # = M→1 2 .
Analysis of M o . We analyze [M o ] i,j by writing N (i→1)/foot_1 a ↑i in the Hermite basis, finding
The terms with k > 0 are all o P (1) because
⇑ N is a norm O P (1) vector with mean zero, independent from the vector F ↘ 0 R0 ε↑j with norm O P (1). Thus, [M o ] i,j = o P (1). The term with k = 0 can also be shown to be o P (1) by using that the linearized F 0 is left-orthogonally invariant, via an argument identical to the one used to analyze equation 33.
Hence, putting these together, the matrix T can be written as
Using lemma J.2, we can write the training loss di!erence as L tr (F 0 )⇒L tr (F) = ↼y ↘ R0 UTU ↘ R0 y. Plugging in the teacher function f ϖ , we find
Note that the second term can be shown to be o P (1) because ϑ ⇐ N(0, ς 2 ϱ I n ) and it is independent from H p ( εϖ ) ↘ R0 UTU ↘ R0 , and ⇓H p ( εϖ ) ↘ R0 UTU ↘ R0 ⇓ op = O P (1/ ⇑ N ) with a simple orderwise analysis. The third can also be shown to be o P (1) by noting that ϑ is independent from R0 U, ⇓ R0 U⇓ op = O P (1/ ⇑ n) and that the elements of T are O P (1).
To analyze the first term, we define ▷ p,q = H p ( εϖ ) ↘ R0 UTU ↘ R0 H q ( εϖ ) for all non-negative integers p, q. To analyze such terms, we first expand UTU ↘ as
Thus, for any p, q ↑ N 0 , the terms ▷ p,q can be written as
By an argument identical to the argument for the terms in M o , the first sum goes to zero in probability. Denoting ω/⇓ω⇓ 2 := ω, we can expand ( Xω) ↑i = ⇓ω⇓ i Lemma K.3. For any p, q ↑ N 0 , we have
We can now use Lemma K.3 and that ⇓ω⇓ 2
(i+j)/2 0 i,p 0 j,q r p r q + o P (1), for p, q ↑ [ϑ], which concludes the proof.
In the infinite sample limit, where n ̸ N, d, we have ↽ ↘ 0. In this extreme case, the expressions for m 1 , m 2 will further simplify as m 1 , m 2 ↘ ↽/↼⇀. Note that in this limit, we have
(see e.g., [MM22, Section 6]. Using Corollary 4.4, we see that for example when ϑ = 2, we have
3 + c 2 ϖ,>2 . In particular, the term corresponding to the linear component of the teacher function in L(F 0 ) cancels out with the corresponding term in % 2 .
Let (x te , y te ) follow the model from (1). Recall that the test error can be written as
where
. First, we will show that in the definition of " f and µ f , we can replace the test feature ς(Wx te ) with the spiked approximation from Theorem 3.1
without changing the test error. To do this, consider an independent test set {x te,i , y te,i } nte i=1 with n te test samples following the data generation distribution in equation 1 and we define X = [x te,1 , . . . , x te,n ] ↘ ↑ R nte↗d . Let F te = ς(X te W ↘ ) ↑ R nte↗N be the test feature matrix. We can write the test error as
Now, consider the spiked approximation of the test feature matrix F te,ε ↑ R nte,N where each row of F te,ε follows the approximation in equation 41. Using Theorem 3.1, we have ⇓F te ⇒ F te,ε ⇓ op = o P ( ⇑ n te ). Thus,
where the last line is due to the fact that under the assumption of Theorem 4.2, we have ⇓y te ⇒ F te â(F)⇓ 2 2 = O P ( ⇑ n te ), and that ⇓â(F)⇓ 2 = O P (1) from the proof of Theorem 4.1. Thus in the test error, we can replace the test features with their spiked approximation without changing the limiting test error. With this, we can write
where
and
where µ 0 f = E xte,yte [ y te ς(W 0 x te ) ], and
Without loss of generality, assume that c 1 = 1. First, note that
where the convergence follows from equation 3 and the computations are in its proof.
Thus, using equation 42, we have
From Section J.1, we have R = R0 ⇒ R0 UTU ↘ R0 , where T is defined in equation 27 and
. In Section J.1 it was shown that
where T 11 , T 22 = # P (1), and T 21 , T 12 = O P (1/ω). Now, we are ready to study the terms E 1 = E xte,yte (y 2 te ), E 2 = â↘ " f â, and E 3 = ⇒2â ↘ µ f that appear in the test error in equation 40.
This term can be readily computed as
. Using these, we can write
We have ỹ = f ϖ + ϑ, thus
We will now analyze the terms in equation 47. First note that ϑ ↘ RF" f F ↘ Rf ϖ = o P (1) using a simple order-wise argument. To analyze the third term in equation 47, we write
Using a simple order-wise analysis, we have
Thus, the third term can be written as
The term q 1 can be computed as
where in the last line we have used that R = R0 ⇒ R0 UTU ↘ R0 and an order-wise analysis for various terms. To analyze q 2 , note that
using a simple order-wise analysis, thus q 2 = o P (1). Similarly, for q 3 , we have
Hence, summing everything up
Next, we will study the term
In the following sections, we will analyze each term in this sum separately.
Preliminary Computations. Before starting the computation, we define K as
Recalling that T 12 = T 21 = O(1/ω) and ω ↘ X↘ R0 F 0 a = O(1/ ⇑ n), the variable K can be simplified as follows:
Also, from the definition of the matrix T in equation 44, we have
Hence, putting everything together, and using Lemma J.4, we can write
Next, we will study the limit of ωT 12 . For this, we can use equation 44 to write
Analysis of E 11 2 . Noting that ω = o(n 1/4 ) and a ↘ F ↘ 0 R0 f ϖ = O P (1/ ⇑ n), we can simplify this term as follows:
Analysis of E 12 2 and E 21 2 . By expanding " f and UTU ↘ , we have
These terms can be simplified as follows. By expanding UTU ↘ , we have
where the last line uses that f ↘ ϖ R0 F 0 a = o P (1) and
Using a similar argument, we have
Putting all together, we arrive at
Analysis of E 22 2 . Once again, by expanding " f and UTU ↘ , we have
Hence,
Analysis of E 13 2 and E 31 2 . Recalling the definition of K in equation 50, this term can be written as
where the last line uses equation 51 and that ω f ↘ ϖ R0 F 0 a = o P (1).
Analysis of E 23 2 and E 32 2 . Again, recalling the definition of K in equation 50, we have
, in which each term can be written as follows:
where we have used that
with a very similar argument to that for E 23(1) 2
. Next,
in which we have used the fact that T 21 = # P (1/ω), and K = #(1/ω 2 ). Finally, with a similar argument
Putting everything together, we have
Analysis of E 33 2 . This term can be analyzed by expanding " f as follows:
where we have used that K = # P (1/ω 2 ) and ω a ↘ W 0 ω = o P (1).
Putting Everything Together. Now, we can put together the results from previous sections to derive the limiting value of E 2 . First, we will explicitly derive the limit of each component. To do so, recall that using equation 3 and Lemma J.4, we have
Also, using Lemma J.1, we have
This limit has been computed in [AP20a]. Using the diagram in the proof of Lemma J.4 that shows how the notations of [AP20a] match ours, we find that E 32 in [AP20a, S148] equals our M . Thus, we find
where m ↔ 2 is the derivative of m 2 with respect to ↼. Also, again using J.1, we have
in which M := lim n,N,d⇓⇐ ω ↘ ϖ X↘ R0 F 0 W 0 ω ϖ . This limit has been computed in [BES + 22]. Specifically, using T 0 9 in (C.16), and noting that their $ 0 translates to F 0 / ⇑ N , their W 0 translates to W ↘ 0 , and their ↼ translates to λn N in our notation, using [BES + 22, Proposition 29] we find
Now, we can use equation 54, equation 55, equation 57, equation 58, and equation 59, respectively, to derive the following expressions:
Thus, summing these terms up, we conclude that
wrapping up the derivation of the limiting value of E 2 .
To analyze this term, first note that
With a simple order-wise analysis, the second term can be shown to be o P (1). To analyze the first term, we will again use the decomposition from equation 49. We can write ⇒2f
We will analyze these terms separately. For the first term, we have
where we have used that ω f ↘ ϖ R0 F 0 a = o P (1). Similarly, the second term can be written as
Also, for the third term we can write
Summing up, the limiting value for E 3 is
Putting equations 45, 62, 63 together, we have
The test error of the untrained random features model can be written as
Hence, the improvement over the untrained random features model in terms of test error is equal to
Hence, using equation 61 and equation 60, we find
where ▷m 1 ▷λ ′ 0 using that tr( X↘ (F 0 F ↘ 0 + ↼nI n ) →1 X)/d = ⇀m 2 /↽. This concludes the proof for ϑ = 1.
First, similar to the proof for ϑ = 1, we have
te ω) 3 = 0, and
, in which we have used Lemma C.1. Thus, using equation 42 and equation 43, we have
), and
. Also, from Section J.2, we have R = R0 ⇒ R0 UTU ↘ R0 , where the matrix T →1 is defined in equation 32 and
Using the analysis in Section J.2.1, we note that
in which the elements of ! are O P (1/ ⇑ n). Hence, the matrix T = [T i,j ] has entries
and its other elements are O P (1/ ⇑ n).
Next, we will study the terms E 1 = E xte,yte (y 2 te ), E 2 = â↘ " f â, and E 3 = ⇒2â ↘ µ f that appear in the decomposition of the test error in equation 40.
Similar to the ϑ = 1 case, we have
M.2.2 Analysis of E 2
Recall that using equation 47, we have
First, note that ϑ ↘ RF" f F ↘ Rf ϖ = o P (1) using a simple order-wise argument. Using an argument similar to the one for ϑ = 1, the third term can be written as
Next, we will study the term f ↘ ϖ RF" f F ↘ Rf ϖ . We can write
in which K 1 and K 2 are defined as
Usign this notation, we have
In the following sections, we will compute each term separately.
Preliminary Computations. First, we will analyze K 1 and K 2 . Recall that
Thus, we have
which gives
Similarly, for K 2 we have
which gives
Analysis of E 11 2 . For this term, by expanding " f , we can write
This holds because ωf ↘ ϖ R0 F 0 a = o P (1), and
Analysis of E 12 2 and E 21 2 . We have
Using the expression for T, we can write
On the other hand, by expanding U and " f , we similarly have
This gives
Analysis of E 13 2 and E 31 2 . Recalling equation 67, by expanding " f we have
in which we have used that
Analysis of E 14 2 and E 41 2 . Recalling equation 68, by expanding " f we have
in which we have used that ω 4 K 2 /N = O P (1).
Analysis of E 22 2 . This term is equal to
Using equation 70, we can write
(75) Further, by expanding " f , we have
in which
Analysis of E 23 2 and E 32 2 . We have
Recall that the vector F ↘ 0 R0 UTU ↘ R0 f ϖ has been computed in equation 75. With this, we have
in which we used that ω 2 K 1 = O P (1) and ωT 13 = O P (1).
Analysis of E 24 2 and E 42 2 . This term can be written as
The vector F ↘ 0 R0 UTU ↘ R0 f ϖ has been computed in equation 75. By expanding " f , we have
Now, noting that K 2 = O P (N/ω 4 ) from equation 68 and ⇓(W 0 ω) ↑2 ⇓ 2 = O P (1/ ⇑ N ), we find that the first term is o P (1) and we have
Analysis of E 33 2 . Similar to the ϑ = 1 case, this term can be written as
noting that
Analysis of E 34 2 and E 43 2 . By expanding " f , we readily arrive at
Analysis of E 44 2 . This term can be written as E 44 2 = c 2 2 ω 4 K 2 2 a ↑2↘ " f a ↑2 . By expanding " f and noting that K 2 = O P (N/ω 4 ), we can write
Putting Everything Together. Now, we can use the results derived above to compute the limiting value of E 2 . Recall that from Lemma J.7 and Lemma J.8 we have
Also using an argument similar to the argument in the proof of Lemma J.7 and Lemma J.8, we have
in which M = lim n,N,d⇓⇐
. This term has been computed in [AP20a]. Using the diagram in the proof of Lemma J.4 that shows how the notations of [AP20a] match ours, we find that we can use (S142) with ς ϱ = 0 in [AP20a], to find
where m ↔ 1 is the derivative of m 1 with respect to ↼.
For brevity, we will define à := lim n,N,d⇓⇐ (
) . With this, equations 72, 73, 74, 76, 77, 78, 79, 80, and 81 give
as well as
and also
respectively. Putting these together, the component E 2 can be written as
(83)
To analyze this component, first note that
Using a simple order-wise analysis, it can be shown that the second term is o P (1). Now, recalling equation 66 we write
, where
. By expanding µ f and recalling that µ 0 f = c ϖ,1 W 0 ω, we have
Next, recall that the matrix F ↘ 0 R0 UTU ↘ R0 f ϖ is analyzed in equation 75. Using this, and by expanding µ f , we get
Similarly, by expanding µ f , we arrive at
, and
Similar to the computation for E 2 , we can derive the limiting values of the components in E 3 as
.
Putting these together, we have
(86)
Putting equations 65, 83, and 86, we have
, where L te (â(F 0 )) is the test error of the untrained random feature model. Further, using equation 60, equation 61, and equation 82, we get
Note that ▷m 1 ▷λ , ▷m 2 ▷λ ′ 0, concluding the proof.
N Proofs of Supplementary Lemmas
N.1 Proof of Lemma C.3 Recalling a i i.i.d. ⇐ N(0, 1/N ) and ↖ xi , ω↙|ω i.i.d.
⇐ N(0, ⇓ω⇓ 2 2 ), claims (a) and (b) follow from standard Gaussian maximal inequalities [vdVW13, Section 2.2] and from ⇓ω⇓ 2 2 = O P (1); the latter follows by writing ω = n →1 X ↘ (ς ϖ (Xω ϖ ) + ϱ), where ϱ = (ϱ 1 , . . . , ϱ n ) ↘ and using our distributional assumptions on X, ϱ, as well as Condition 2.2. By [Ver12, Theorem 5.39] and [BS10, Corollary A.21], we have ⇓W 0 W ↘ 0 ⇓ op , ⇓(W 0 W ↘ 0 ) ↑2 ⇓ op = O P (1). Also, by [Ver18, Theorem 3.4.6] and Gaussian maximal inequalities [vdVW13, Section 2.2], we have max 1⇔i↙ =⇔j⇔N ↖w 0,i , w 0 N.2 Proof of Lemma J.1
We can write
, where conditional on ω ϖ , (P >1 ς ϖ )(x ↘ i ω ϖ ) is orthogonal in L 2 to the constant function and to x ↘ i ω ϖ . Hence the first sum above equals
For the first term,
2 ) ↘ P 0. The second term is c ϖ,1 times a sample mean of i.i.d. random variables of the form v ↘ (x i x ↘ i ⇒ 1)ω ϖ , which have zero mean by the Gaussianity of x i , and for which all moments are finite. Hence, by the weak law of large numbers, this term converges to zero in probability.
Similarly, the third term is a sample mean of i.i.d. random variables of the form v ↘ x i (P >1 ς ϖ )(x ↘ i ω ϖ ), which have zero mean by the Gaussianity of x i and Lemma C.1, and whose second moments are finite since ς ϖ is Lipschitz. Hence, by the weak law of large numbers, this term also converges to zero in probability. This finishes the proof of the first claim.
Next, the second statement follows from [BES + 22, Lemma 18]. While that work has slightly di!erent assumptions on the teacher function f ϖ , it is straightforward to check that their proof goes through unchanged under our assumptions. Specifically, their proof requires that x ∞ ↘ f ϖ (x) = ς ϖ (x ↘ ω ϖ ) is O(1)-Lipschitz, which holds in our case because ς ϖ is O(1)-Lipschitz, and ⇓ω ϖ ⇓ 2 = O P (1).
By plugging in â into the training loss, we find
which proves the lemma.
To prove the concentration of this term around its mean, we will use the generalized Hanson-Wright inequality [Sam23, Theorem 2.1] for ε-subexponential random variables. Note that, by definition, if Z is a Gaussian random variable, H p (Z) is 2/p-subexponential (see the definition in equation (1.1) of [Sam23] and for these variables the Orlicz norm of order 2/p is bounded (see equation (1.3) of [Sam23]). Also note that ⇓D⇓ Fr ′ ⇑ n⇓D⇓ op = O P (1/ ⇑ n). Thus, using [Sam23, Theorem 2.1] and setting t = log(n) ⇑ n , we find
where C > 0 is some constant. This concludes the proof.
N.5 Proof of Lemma J.4
First, we show that switching from w 0,i i.i.d.
⇐ Unif(S d→1 ) to ŵ0,i i.i.d.
⇐ N(0, 1 d I d ) will not change the limit of the terms 1 d Etr( X↘ R0 X) and Etr( R0 ) which will appear later in the proof. First, we define Ŵ0
Now, using the Gaussian equivalence from Appendix I, we can replace F 0 and F0 with F 0 = c 1 XW ↘ 0 + c >1 Z and F0 = c 1 X Ŵ↘ 0 + c >1 Z, respectively, without changing the limit. With this, we have
1), ⇓D⇓ op = O P (1), and ⇓I N ⇒ D⇓ op = o P (1). Thus ⇓W 0 W ↘ 0 ⇒ Ŵ0 Ŵ↘ 0 ⇓ op = o P (1). Also, similarly, ⇓W 0 ⇒ Ŵ0 ⇓ op = o P (1). Hence, noting that ⇓ X⇓ op and ⇓Z⇓ op are both O P ( ⇑ N ), we have 1 n
Finally, we can prove the required claims as follows: ⇐ N(0, 1 d I d ) without changing the limiting trace. Further, from [AP20a, Proposition 1], see also [ALP22], we have 1 d Etr( X↘ R0 X) ↘ ↽ ⇀ m 2 ; see the discussion at the end of this proof for the detailed explanation. Now, we arrive at the conclusion by applying Lemma J.1.
1) by the Hanson-Wright inequality. Moreover,
. From the argument above, we can assume that ŵ0,i i.i.d.
⇐ N(0, 1 d I d ) without changing the limiting trace. It follows from [AP20a, Proposition 1] that E tr R0 ↘ ↽ ⇀ m 1 ; again see the discussion at the end of this proof for the detailed explanation. Note that lim E tr R0 is the limiting Stieltjes transform of F 0 F ↘ 0 . Hence, m1 = lim E tr(F ↘ 0 F 0 + ↼nI N ) →1 is the limiting companion Stieltjes transform of m 1 which is given by m1
This concludes the proof.
For the reader's convenience, we provide the following diagram that shows how the notations of [AP20a] (left) match (∀) ours (right):
N.6 Proof of Lemma J.5
Define X = X ⇒ Xuu ↘ , which implies X △ △ Xu due to the Gaussianity of X. Based on the Gaussian equivalence from Appendix I, we can replace F 0 with c 1 XW ↘ 0 + c >1 Z, where Z ↑ R n↗d is an independent random matrix with N(0, 1) entries, without changing the conclusion. Hence, from now on, we write
Thus, by the definition of X, F0 = F 0 ⇒ c 1 Xu(W 0 u) ↘ . As a consequence, we also have
Noting that D is invertible, and using the Woodbury formula, with R0 = ( F0 F↘
Now, we can write
Next, we can analyze each term in the above sum separately.
The first term on the right hand side converges to zero by using Lemma J.3 to prove the concentration of this term around its mean and noting that the mean is zero using the orthogonality property of Hermite polynomials (Lemma C.1).
To analyze the second term, we first study the matrix K = (D →1 + V ↘ R0 V) →1 , writing
It can readily verified that all elements in this matrix are O P (1) checking the order of the operator and Euclidean norms. Next, we analyze the terms in the expression
Without loss of generality, we can assume that p ∝ = 1.
• First Term. Note that H q ( Xu) ↘ and H p ( Xu) are orthogonal in L 2 by the properties of the Hermite polynomials, and conditional on u, they are independent of R0 ( F0 W 0 u)( F0 W 0 u) ↘ R0 . Moreover, ⇓ R0 ( F0 W 0 u)( F0 W 0 u) ↘ R0 ⇓ op = O P (1/n). Thus, by using Lemma J.3, this term converges to zero.
• Second Term. Similar to the argument above, we can show that ( Xu) ↘ R0 H p ( Xu) converges to zero. Also, by analyzing the operator norms, we have H q ( Xu) ↘ R0 ( F0 W 0 u) = O(1). This implies that the second term converges to zero.
• Third Term. First, note that by a simple order-wise analysis, H q ( Xu) ↘ R0 ( Xu) = O P (1). Now, we have H p ( Xu) is independent of ( F0 W 0 u) ↘ R0 and ⇓( F0 W 0 u) ↘ R0 ⇓ 2 = O P (1/ ⇑ n). The term ( F0 W 0 u) ↘ R0 H p ( Xu) converges to zero in probability by noting that H p ( Xu) is mean zero for p ∝ = 0. For the p = 0 case, we can use an orthogonality invariance argument identical to the one used to analyze equation 33.
• Fourth Term. This term also converges to zero because ( Xu) ↘ R0 H p ( Xu) converges to zero, as argued above.
Putting everything together, the proof is completed.
We will prove part (a) first. To do this, we will first handle the cases where p = 0 and p = 1.
For p = 0, we have ⇑ NH 0 ( εϖ ) R0 F 0 a ↑2 = ⇑ N. This is identical to the second term in equation 33 and it is shown to be o P (1) For p = 1, we need to analyze
Thus, we can conclude that ⇑ NH 1 ( εϖ ) R0 F 0 a ↑2 ↘ 0 in probability.
To analyze the case where p > 1, we first define X = X ⇒ εϖ ω ↘ ϖ . By construction, we have X △ △ εϖ . As in the proof of Lemma J.5, Based on the Gaussian equivalence from Appendix I, we can replace F 0 with c 1 XW ↘ 0 + c >1 Z in our computations without changing the limiting result, where Z ↑ R n↗d is an independent random matrix with N(0, 1) entries. Thus, from now on, we denote F 0 = c 1 XW ↘ 0 + c >1 Z. We define F0 as in equation 89. Thus, F0 = F 0 ⇒ c 1 εϖ (W 0 ω ϖ ) ↘ . As a consequence, we can write F 0 F ↘ 0 = F0 F↘ 0 + VDV ↘ , where V = F0 W 0 ω ϖ εϖ ↑ R n↗2 and
Using the Woodbury formula, we find that equation 90 still holds. Now, we can write
. Now, we can analyze each term in the above sum separately.
Term 1. Note that by a simple orderwise analysis,
We have ⇓H p ( εϖ )⇓ 2 = O P ( ⇑ N ), E[H p ( εϖ )] = 0, and H p ( εϖ ) has independent entries. Also H p ( εϖ ) △ △ R0 F0 a ↑2 . Thus, ⇑ NH p ( εϖ ) ↘ R0 F0 a ↑2 ↘ P 0.
We now need to analyze ⇑ NH p ( εϖ ) ↘ R0 εϖ ω ↘ ϖ W ↘ 0 a ↑2 . Note that H p ( εϖ ) ↘ R0 εϖ = O P (1) by a simple order analysis of the norms. We also have ⇑ N ω ↘ ϖ W ↘ 0 a ↑2 ↘ P 0, because ω ϖ ⇐ N(0, 1 d I d ) is independent of the norm bounded vector ⇑ N W ↘ 0 a ↑2 .
Term 2. To analyze the second term, we first study the matrix K = (D →1 + V ↘ R0 V) →1 :
By orderwise analysis, all elements in this matrix converge to deterministic O P (1) values in probability. We write the second term in equation 91 as follows:
In the sum above, we will show that each term converges to zero.
• First term: By orderwise analysis, we have ⇓ R0 ( F0 W 0 ω ϖ )⇓ op = O P (1/ ⇑ N ). Further, H p ( εϖ ) is independent of it (only considering the randomness in X) with mean zero and ⇓H p ( εϖ )⇓ 2 = O P ( ⇑ N ). This implies that
We can use a simple order argument to show that ⇑ N ( F0 W 0 ω ϖ ) ↘ R0 F 0 a ↑2 = O P (1). Thus, the first term converges to zero.
• Second term: For this term, we use that H p ( εϖ ) ↘ R0 ( F0 W 0 ω ϖ ) ↘ P 0. We can also use an orderwise analysis to prove that ⇑ N ( εϖ ) ↘ R0 F 0 a ↑2 = O P (1). This proves that the second term also converges to zero.
• Third term: By a simple orderwise analysis, we have ⇑ N ( F0 W 0 ω ϖ ) ↘ R0 F 0 a ↑2 = O P (1). To show that the third term converges to zero, it is enough to show that H p ( εϖ ) ↘ R0 ( εϖ ) ↘ P 0, which is true for p ∝ = 1 by using Lemma J.3 and the orthogonality property of Hermite polynomials (Lemma C.1).
• Fourth term: By a simple orderwise analysis, we have ⇑ N ε↘ ϖ R0 F 0 a ↑2 = O P (1). Again, to show that the fourth term converges to zero, it is enough to show that H p ( εϖ ) ↘ R0 ( εϖ ) ↘ P 0, which is true for p ∝ = 1 as argued above.
Putting everything together, part (a) follows. The proof for part (b) is identical and omitted.
N.8 Proof of Lemma J.7
We will study the cases where s = 1 and s = 2 separately. For s = 1, we can use Lemma J.1 to show that H p ( εϖ ) R0 ε = c ϖ,1 H p ( εϖ ) R0 εϖ + o P (1). Also, by Lemma J.5, we have H p ( εϖ ) R0 ( εϖ ) = o(1) in probability if p ∝ = 1, which proves the lemma. .
Next, we consider H 2 ( εϖ ) ↘ R0 V with V = Xω Xω ∝ F0 W 0 ω F0 W 0 ω ∝ . For the first two entries of the vector H 2 ( εϖ ) ↘ R0 V, an analysis very similar to the one above for H 2 ( εϖ ) ↘ R0 H 2 ( Xω ) shows that they converge to zero in probability. For the last two entries, since H 2 ( εϖ ) is independent of R0 [ F0 W 0 ω F0 W 0 ω ∝ ], and has zero-mean i.i.d. entries, it also follows that these entries converge to zero in probability. Moreover, the limiting entries of (D →1 + V ↘ R0 V) →1 have been shown to be bounded in our above analysis. Hence, the second term to zero in probability. Now, note that ω = ω/⇓ω⇓ 2 . From Lemma J.1, ⇓ω⇓ 2 ↘ P ↽(c 2 ϖ + ς 2 ϱ ) + c 2 ϖ,1 . Hence,
+ o P (1) ↘ P 2c 2 ϖ,1 ⇀m 1 ↽ , which concludes the proof.
N.9 Proof of Lemma J.8
As in the proof of Lemma J.6, we define X = X ⇒ εω ↘ . By construction, we have X △ △ ε. As in the proof of Lemma J.5, based on the Gaussian equivalence from Appendix I, we can replace F 0 with c 1 XW ↘ 0 + c >1 Z in our computations without changing the limiting result, where Z ↑ R n↗d is an independent random matrix with N(0, 1) entries. Thus, from now on, we denote F 0 = c 1 XW ↘ 0 +c >1 Z. We define F0 as in equation 89; thus, F0 = F 0 ⇒ c 1 ε(W 0 ω) ↘ . As a consequence, we can write F 0 F ↘ 0 = F0 F↘ 0 + VDV ↘ , where V = F0 W 0 ω ε ↑ R n↗2 and
Using the Woodbury formula, we find that equation 90 still holds. Now, we can write
We can analyze each term in the above sum separately.
By Lemma J.3, ε↑2↘ R0 ε↑2 ⇒ E ε↑2↘ R0 ε↑2 ↘ P 0. Further, conditional on ω, E ε↑2↘ R0 ε↑2 = 3⇓ω⇓ 4 2 E tr R0 ; and as in the proof of Lemma J.7, E tr R0 ⇒ E tr R0 ↘ 0. Moreover, we have already argued in the proof of Lemma J.4 that E tr R0 ↘ ⇀m 1 /↽. In addition, from Lemma J.1, ⇓ω⇓ 2 ↘ P ↽(c 2 ϖ + ς 2 ϱ ) + c 2 ϖ,1 . Hence, ε↑2↘ R0 ε↑2 ↘ P 3⇀m 1 [↽(c 2 ϖ + ς 2 ϱ ) + c 2 ϖ,1 ] 2 /↽. To analyze the second term in equation 94, we first study ε↑2↘ R0 F0 W 0 ω. By an argument similar to the ones above, we can show that it concentrates around 1 ↘ n R0 F0 W 0 ω = 1 ↘ n F0 R0 W 0 ω. Since F0 is left-orthogonally invariant, 1 ↘ n F0 R0 W 0 ω = d 1 ↘ n O F0 R0 W 0 ω, where O is uniformly distributed over the Haar measure of n-dimensional orthogonal matrices, independently of all other randomness. Then, it follows as in the analysis of term (1,2) from Section J.2 that 1 ↘ n O F0 R0 W 0 ω ↘ P 0; and hence ε↑2↘ R0 F0 W 0 ω ↘ P 0.
Moreover, the limiting entries of (D →1 + V ↘ R0 V) →1 can be shown to be bounded by a simple orderwise analysis. Hence, the second term in equation 94 is o P (1).
For H p ( εϖ ) ↘ R0 H p ( Xω ), since H p ( εϖ ), H p ( Xω ) are independent of R0 , it follows from Lemma J.3, as in the analysis of term (1, 2) in the Section J.2, that H p ( εϖ ) ↘ R0 H p ( Xω ) ⇒ E R0 • EH p ( εϖ ) ↘ H p ( Xω ) ↘ P 0. Now notice that F0 is left-orthogonally invariant in distribution, and thus R0 = d O R0 O ↘ , where O is uniformly distributed over the Haar measure of n-dimensional orthogonal matrices, independently of all other randomness. Hence, E R0 = E tr R0 I n /n. Also, similar to the proof of Lemma J.7, we have | tr R0 ⇒ tr R0 | = o P (1). Moreover, we have already argued in the proof of Lemma J.4 that E tr R0 ↘ ⇀m 1 /↽. Further, by Lemmas C.1 and J.1, H p ( εϖ ) ↘ R0 H p ( Xω ) ↘ P p! ⇀m 1 ↽ c ϖ,1
Next, we consider H 2 ( εϖ ) ↘ R0 V with V = Xω Xω ∝ F0 W 0 ω F0 W 0 ω ∝ . For the first two entries of the vector H p ( εϖ ) ↘ R0 V, an analysis very similar to the one above for H p ( εϖ ) ↘ R0 H p ( Xω ) shows that they converge to zero in probability. For the last two entries, since H p ( εϖ ) is independent of R0 [ F0 W 0 ω F0 W 0 ω ∝ ], and has zero-mean i.i.d. entries, it also follows that these entries converge to zero in probability. Moreover, the limiting entries of (D →1 + V ↘ R0 V) →1 have been shown to be bounded in our above analysis. Hence, the second term converges to zero in probability.
The case when p = q = 1: In this case, we have + o P (1), using Lemma J.1 and by arguments similar to the ones in the proof of Lemma J.4.
Putting everything together concludes the proof.
i k=0 0 i,k H k ( Xω/⇓ω⇓ 2 ), To analyze ▷ p,q , we need the following result, whose proof is deferred to Section N.11.