Limitations of Lazy Training of Two-layers Neural Networks

Introduction

The function class of two-layers neural networks (with $N$ neurons) is defined by:

These facts lead to the following central question in neural network theory:

Here ‘efficiently’ can be formalized in multiple ways: in this paper we will focus on learning via stochastic gradient descent.

Significant amount of work has been devoted to two subclasses of ${\mathcal{F}}_{{\sf NN},N}$ which we will refer to as the random feature model (${\sf RF}$) [RR08], and the neural tangent model (${\sf NT}$) [JGH18]:

We can think of ${\sf RF}$ and ${\sf NT}$ as tractable inner bounds of the class of neural networks ${\sf NN}$:

Tractable. Both ${\mathcal{F}}_{{\sf RF},N}({\boldsymbol{W}})$, ${\mathcal{F}}_{{\sf NT},N}({\boldsymbol{W}})$ are finite-dimensional linear spaces, and minimizing the empirical risk over these classes can be performed efficiently.

Inner bounds. Indeed ${\mathcal{F}}_{{\sf RF},N}({\boldsymbol{W}})\subseteq{\mathcal{F}}_{{\sf NN},N}$: the random feature model is simply obtained by fixing all the first layer weights. Further ${\mathcal{F}}_{{\sf NT}}({\boldsymbol{W}})\subseteq{\rm cl}({\mathcal{F}}_{{\sf NN},2N})$ (the closure of the class of neural networks with $2N$ neurons). This follows from ${\varepsilon}^{-1}[\sigma(\langle{\boldsymbol{w}}_{i}+{\varepsilon}{\boldsymbol{a}}_{i},{\boldsymbol{x}}\rangle)-\sigma(\langle{\boldsymbol{w}}_{i},{\boldsymbol{x}}\rangle)]=\langle{\boldsymbol{a}}_{i},{\boldsymbol{x}}\rangle\sigma^{\prime}(\langle{\boldsymbol{w}}_{i},{\boldsymbol{x}}\rangle)+o(1)$ as ${\varepsilon}\to 0$.

It is possible to show that the class of neural networks ${\sf NN}$ is significantly more expressive than the two linearization ${\sf RF}$, ${\sf NT}$, see e.g. [YS19, GMMM19]. In particular, [GMMM19] shows that, if the feature vectors ${\boldsymbol{x}}_{i}$ are uniformly random over the $d$-dimensional sphere, and $N,d$ are large with $N=O(d)$, then ${\mathcal{F}}_{{\sf RF},N}({\boldsymbol{W}})$ can only capture linear functions, while ${\mathcal{F}}_{{\sf NT},N}({\boldsymbol{W}})$ can only capture quadratic functions.

In this paper we explore systematically the gap between ${\sf RF}$, ${\sf NT}$ and ${\sf NN}$, by considering two specific data distributions:

Quadratic functions: feature vectors are distributed according to ${\boldsymbol{x}}_{i}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d})$ and responses are quadratic functions $y_{i}=f_{*}({\boldsymbol{x}}_{i})\equiv b_{0}+\langle{\boldsymbol{x}}_{i},{\boldsymbol{B}}{\boldsymbol{x}}_{i}\rangle$ with ${\boldsymbol{B}}\succeq 0$.

Mixture of Gaussians: $y_{i}=\pm 1$ with equal probability $1/2$, and ${\boldsymbol{x}}_{i}|y_{i}=+1\sim{\sf N}(0,{\boldsymbol{\Sigma}}^{(1)})$, ${\boldsymbol{x}}_{i}|y_{i}=-1\sim{\sf N}(0,{\boldsymbol{\Sigma}}^{(2)})$.

Let us emphasize that the choice of quadratic functions in model qf is not arbitrary: in a sense, it is the most favorable case for ${\sf NT}$ training. Indeed [GMMM19] proves thatNote that [GMMM19] considers feature vectors ${\boldsymbol{x}}_{i}$ uniformly random over the sphere rather than Gaussian. However, the results of [GMMM19] can be generalized, with certain modifications, to the Gaussian case. Roughly speaking, for Gaussian features, ${\sf NT}$ with $N=O(d)$ neurons can represent quadratic functions, and a low-dimensional subspace of higher order polynomials. (when $N=O(d)$): $(i)$ Third- and higher-order polynomials cannot be approximated nontrivially by ${\mathcal{F}}_{{\sf NT},N}({\boldsymbol{W}})$; $(ii)$ Linear functions are already well approximated within ${\mathcal{F}}_{{\sf RF},N}({\boldsymbol{W}})$.

For clarity, we will first summarize our result for the model qf, and then discuss generalizations to mg. The prediction risk achieved within any of the regimes ${\sf RF}$, ${\sf NT}$, ${\sf NN}$ is defined by

Our results are summarized by Figure 1, which compares the risk achieved by the three approaches above in the population limit $n\to\infty$, using quadratic activations $\sigma(u)=u^{2}+c_{0}$. We consider the large-network, high-dimensional regime $N,d\to\infty$, with $N/d\to\rho\in(0,\infty)$. Figure 1 reports the risk achieved by various approaches in numerical simulations, and compares them with our theoretical predictions for each of three regimes ${\sf RF}$, ${\sf NT}$, and ${\sf NN}$, which are detailed in the next sections.

The agreement between analytical predictions and simulations is excellent but, more importantly, a clear picture emerges. We can highlight a few phenomena that are illustrated in this figure:

Random features do not capture quadratic functions. The random features risk $R_{{\sf RF},N}(f_{*})$ remains generally bounded away from zero for all values of $\rho=N/d$. It is further highly dependent on the distribution of the weight vectors ${\boldsymbol{w}}_{i}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$. Section 2.1 characterizes explicitly this dependence, for general activation functions $\sigma$. For large $\rho=N/d$, the optimal distribution of the weight vectors uses covariance ${\boldsymbol{\Gamma}}^{*}\propto{\boldsymbol{B}}$, but even in this case the risk is bounded away from zero unless $\rho\to\infty$.

Fully trained neural networks achieve vanishing risk on quadratic functions for $N>d$: this is to be expected on the basis of the previous point. For $N/d\to\rho\in(0,1)$ the risk is generally bounded away from , but its value is smaller than for the neural tangent model. Namely, in Section 2.3 we give an explicit expression for the asymptotic risk (holding for ${\boldsymbol{B}}\succeq{\boldsymbol{0}}$) implying that, for some ${\rm GAP}(\rho)>0$ (independent of $N,d$),

The picture emerging from these findings is remarkably simple. The fully trained network learns the most important eigendirections of the quadratic function $f_{*}({\boldsymbol{x}})$ and fits them, hence surpassing the ${\sf NT}$ model which is confined to a random set of directions.

Let us emphasize that the above separation between ${\sf NT}$ and ${\sf NN}$ is established only for $N\leq d$. It is natural to wonder whether this separation generalizes to $N>d$ for more complicated classes of functions, or if instead it always vanishes for wide networks. We expect the separation to generalize to $N>d$ by considering higher order polynomial, instead of quadratic functions. Partial evidence in this direction is provided by [GMMM19]: for third- or higher-order polynomials ${\sf NT}$ does not achieve vanishing risk at any $\rho\in(0,\infty)$. The mechanism unveiled by our analysis of quadratic functions is potentially more general: neural networks are superior to linearized models such as ${\sf RF}$ or ${\sf NT}$, because they can learn a good representation of the data.

2 Further related work

The connection (and differences) between two-layers neural networks and random features models has been the object of several papers since the original work of Rahimi and Recht [RR08]. An incomplete list of references includes [Bac13, AM15, Bac17a, Bac17b, RR17]. Our analysis contributes to this line of work by establishing a sharp asymptotic characterization, although in more specific data distributions. Sharp results have recently been proven in [GMMM19], for the special case of random weights ${\boldsymbol{w}}_{i}$ uniformly distributed over a $d$-dimensional sphere. Here we consider the more general case of anisotropic random features with covariance ${\boldsymbol{\Gamma}}\not\propto{\mathbf{I}}$. This clarifies a key reason for suboptimality of random features: the data representation is not adapted to the target function $f_{*}$. We focus on the population limit $n\to\infty$. Complementary results characterizing the variance as a function of $n$ are given in [HMRT19].

The ${\sf NT}$ model (3) is much more recent [JGH18]. Several papers show that SGD optimization within the original neural network is well approximated by optimization within the model ${\sf NT}$ as long as the number of neurons is large compared to a polynomial in the sample size $N\gg n^{c_{0}}$ [DZPS18, DLL+18, AZLS18, ZCZG18]. Empirical evidence in the same direction was presented in [LXS+19, ADH+19].

Chizat and Bach [CB18] clarified that any nonlinear statistical model can be approximated by a linear one in an early (lazy) training regime. The basic argument is quite simple. Given a model ${\boldsymbol{x}}\mapsto f({\boldsymbol{x}};{\boldsymbol{\theta}})$ with parameters ${\boldsymbol{\theta}}$, we can Taylor-expand around a random initialization ${\boldsymbol{\theta}}_{0}$. Setting ${\boldsymbol{\theta}}={\boldsymbol{\theta}}_{0}+{\boldsymbol{\beta}}$, we get

Here the second approximation holds since, for many random initializations, $f({\boldsymbol{x}};{\boldsymbol{\theta}}_{0})\approx 0$ because of random cancellations. The resulting model ${\boldsymbol{\beta}}^{{\mathsf{T}}}\nabla_{{\boldsymbol{\theta}}}f({\boldsymbol{x}};{\boldsymbol{\theta}}_{0})$ is linear, with random features.

Our objective is complementary to this literature: we prove that ${\sf RF}$ and ${\sf NT}$ have limited approximation power, and significant gain can be achieved by full training.

Finally, our analysis of fully trained networks connects to the ample literature on non-convex statistical estimation. For two layers neural networks with quadratic activations, Soltanolkotabi, Javanmard and Lee [SJL19] showed that, as long as the number of neurons satisfies $N\geq 2d$ there are no spurious local minimizers. Du and Lee [DL18] showed that the same holds as long as $N\geq d\wedge\sqrt{2n}$ where $n$ is the sample size. Zhong et. al. [ZSJ+17] established local convexity properties around global optima. Further related landscape results include [GLM17, HYV14, GJZ17].

Main results: quadratic functions

As mentioned in the previous section, our results for quadratic functions (qf) assume ${\boldsymbol{x}}_{i}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d})$ and $y_{i}=f_{*}({\boldsymbol{x}}_{i})$ where

We consider random feature model with first-layer weights $({\boldsymbol{w}}_{i})_{i\leq N}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$. We make the following assumptions:

Then, the following holds as $N,d\to\infty$ with $N/d\to\rho$:

Moreover, assuming $\langle{\boldsymbol{\Gamma}},{\boldsymbol{B}}\rangle^{2}/\|{\boldsymbol{\Gamma}}\|_{F}^{2}\|{\boldsymbol{B}}\|_{F}^{2}$ to have a limit as $d\to\infty$, (10) simplifies as follows for $\rho\rightarrow\infty$:

Notice that $R_{{\sf RF},N}(f_{*})/\|f_{*}\|_{L_{2}}^{2}$ is the ${\sf RF}$ risk normalized by the risk of the trivial predictor $f({\boldsymbol{x}})=0$. The asymptotic result in (11) is remarkably simple. By Cauchy-Schwartz, the normalized risk is bounded away from zero even as the number of neurons per dimension diverges $\rho=N/d\to\infty$, unless ${\boldsymbol{\Gamma}}\propto{\boldsymbol{B}}$, i.e. the random features are perfectly aligned with the function to be learned. For isotropic random features, the right-hand side of Eq. (11) reduces to $1-\text{\rm Tr}({\boldsymbol{B}})^{2}/(d\|{\boldsymbol{B}}\|_{F}^{2})$. In particular, ${\sf RF}$ performs very poorly when $\text{\rm Tr}({\boldsymbol{B}})\ll\sqrt{d}\|{\boldsymbol{B}}\|_{F}$, and no better than the trivial predictor $f({\boldsymbol{x}})=0$ if $\text{\rm Tr}({\boldsymbol{B}})=0$.

Notice that the above result applies to quite general activation functions. The formulas simplify significantly for quadratic activations.

Under the assumptions of Theorem 1, further assume $\sigma(x)=x^{2}-1$. Then we have, as $N,d\to\infty$ with $N/d\to\rho$:

The right-hand side of Eq. (12) is plotted in Fig. 1 for isotropic features ${\boldsymbol{\Gamma}}={\mathbf{I}}/d$, and for optimal features ${\boldsymbol{\Gamma}}={\boldsymbol{\Gamma}}^{*}\propto{\boldsymbol{B}}$.

2 Neural tangent

For the ${\sf NT}$ regime, we focus on quadratic activations and isotropic weights ${\boldsymbol{w}}_{i}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d}/d)$.

where the expectation is taken over ${\boldsymbol{w}}_{i}\sim_{i.i.d}{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d}/d)$.

3 Neural network

For the analysis of SGD-trained neural networks, we assume $f_{*}$ to be a quadratic function as per Eq. (8), but we will now restrict to the positive semidefinite case ${\boldsymbol{B}}\succeq 0$. We consider quadratic activations $\sigma(x)=x^{2}$, and we fix the second layers weights to be $1$:

Notice that we use an explicit offset to account for the mismatch in means between $f_{*}$ and $\hat{f}$. It is useful to introduce the population risk, as a function of the network parameters ${\boldsymbol{W}},c$:

Here expectation is with respect to ${\boldsymbol{x}}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d})$. We will study a one-pass version of SGD, whereby at each iteration $k$ we perform a stochastic gradient step with respect to a fresh sample $({\boldsymbol{x}}_{k},f_{*}({\boldsymbol{x}}_{k}))$

Then we have (probability is over the initialization $({\boldsymbol{W}}_{0},c_{0})$ and the samples)

where $\lambda_{1}({\boldsymbol{B}})\geq\lambda_{2}({\boldsymbol{B}})\geq\dots\geq\lambda_{d}({\boldsymbol{B}})$ are the ordered eigenvalues of ${\boldsymbol{B}}$.

The proof of this theorem depends on the following proposition concerning the landscape of the population risk, which is of independent interest.

Let $f_{*}$ be a quadratic function as per Eq. (8), with ${\boldsymbol{B}}\succeq 0$. For any sub-level set of the risk function $\Omega(B_{0})=\{{\boldsymbol{x}}=({\boldsymbol{W}},c):L({\boldsymbol{W}},c)\leq B_{0}\}$, there exists constants $\varepsilon,\delta>0$ such that $L$ is $(\varepsilon,\delta)$-strict saddle in the region $\Omega(B_{0})$. Namely, for any ${\boldsymbol{x}}\in\Omega(B_{0})$ with $\|\nabla L({\boldsymbol{x}})\|_{2}\leq\varepsilon$, we have $\lambda_{\min}(\nabla^{2}L({\boldsymbol{x}}))<-\delta$.

We can now compare the risk achieved within the regimes ${\sf RF}$, ${\sf NT}$ and ${\sf NN}$. Gathering the results of Corollary 1, and Theorems 2, 3 (using ${\boldsymbol{w}}_{i}\sim{\sf N}(0,{\mathbf{I}}/d)$ for ${\sf RF}$ and ${\sf NT}$), we obtain

As anticipated, ${\sf NN}$ learns the most important directions in $f_{*}$, while ${\sf RF}$, ${\sf NT}$ do not.

Main results: mixture of Gaussians

In this section, we consider the mixture of Gaussian setting (mg): $y_{i}=\pm 1$ with equal probability $1/2$, and ${\boldsymbol{x}}_{i}|y_{i}=+1\sim{\sf N}(0,{\boldsymbol{\Sigma}}^{(1)})$, ${\boldsymbol{x}}_{i}|y_{i}=-1\sim{\sf N}(0,{\boldsymbol{\Sigma}}^{(2)})$. We parametrize the covariances as ${\boldsymbol{\Sigma}}^{(1)}={\boldsymbol{\Sigma}}-{\boldsymbol{\Delta}}$ and ${\boldsymbol{\Sigma}}^{(2)}={\boldsymbol{\Sigma}}+{\boldsymbol{\Delta}}$, and will make the following assumptions:

There exists constants $0<c_{1}<c_{2}$ such that $c_{1}{\mathbf{I}}_{d}\preceq{\boldsymbol{\Sigma}}\preceq c_{2}{\mathbf{I}}_{d}$;

$\|{\boldsymbol{\Delta}}\|_{\rm op}=\Theta_{d}(1/\sqrt{d})$.

The scaling in assumption M2 ensures the signal-to-noise ratio to be of order one. If the eigenvalues of${\boldsymbol{\Delta}}$ are much larger than $1/\sqrt{d}$, then it is easy to distinguish the two classes with high probability (they are asymptotically mutually singular). If $\|{\boldsymbol{\Delta}}\|_{\rm op}=o_{d}(1/sqrt{d})$ then no non-trivial classifier exists.

As mentioned in the introduction, the picture emerging from our analysis of the mg model is aligned with the results obtained in the previous section. We will limit ourselves to stating the results without repeating comments that were made above. Our results are compared with simulations in Figure 2. Notice that, in this case, the Bayes error (MMSE) is not achieved even for very wide networks $N/d\gg 1$ either by ${\sf NT}$ or ${\sf NN}$.

As in the previous section, we generate random first-layer weights $({\boldsymbol{w}}_{i})_{i\leq N}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$. We consider a general activation function satisfying condition ${\bf A1}$. We make the following assumption on ${\boldsymbol{\Gamma}},{\boldsymbol{\Sigma}}$:

Define $\zeta_{1}(d)\equiv d\,\text{\rm Tr}({\boldsymbol{\Sigma}}{\boldsymbol{\Gamma}}{\boldsymbol{\Sigma}}{\boldsymbol{\Gamma}})/2$, $\zeta_{2}(d)\equiv d\,\text{\rm Tr}({\boldsymbol{\Delta}}{\boldsymbol{\Gamma}})^{2}/4$. Then, the following holds as $N,d\to\infty$ with $N/d\to\rho$:

Moreover, assume $\zeta_{1}(d)$ $\zeta_{2}(d)$ to have limits as $d\to\infty$, i.e. we have $\lim_{d\to\infty}\zeta_{j}(d)=\zeta_{j,*}$ for $j=1,2$. Then the following holds as $\rho\rightarrow\infty$:

2 Neural tangent

For the ${\sf NT}$ model, we first state our theorem for general ${\boldsymbol{\Sigma}}$ and ${\boldsymbol{w}}_{i}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$ and then give an explicit concentration result in the case ${\boldsymbol{\Sigma}}={\mathbf{I}}$ and isotropic weights ${\boldsymbol{w}}_{i}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}/d)$.

Assuming further that ${\boldsymbol{\Sigma}}={\mathbf{I}}$ and ${\boldsymbol{w}}_{i}\sim_{i.i.d.}{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d}/d)$, we have as $N,d\to\infty$ with $N/d\to\rho$:

In particular, for $\rho\geq 1$, we have (for almost every ${\boldsymbol{W}}$)

3 Neural network

We consider quadratic activations with general offset and coefficients $\hat{f}({\boldsymbol{x}};{\boldsymbol{W}},{\boldsymbol{a}},c)=\sum_{i=1}^{N}a_{i}\langle{\boldsymbol{w}}_{i},{\boldsymbol{x}}\rangle^{2}+c$. This is optimized over $(a_{i},{\boldsymbol{w}}_{i})_{i\leq N}$ and $c$.

Let us emphasize that, for this setting, we do not have a convergence result for SGD as for the model qf, cf. Theorem 3. However, because of certain analogies between the two models, we expect a similar result to hold for mixtures of Gaussians.

We can now compare the risks achieved within the regimes ${\sf RF}$, ${\sf NT}$ and ${\sf NN}$. Gathering the results of Theorems 4, 5 and 6 for ${\boldsymbol{\Sigma}}={\mathbf{I}}$ and $\sigma(x)=x^{2}-1$ (using ${\boldsymbol{w}}_{i}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}/d)$ for RF and NT), we obtain

We recover a similar behavior as in the case of the (qf) model: ${\sf NN}$ learns the most important directions of ${\boldsymbol{\Delta}}$, while ${\sf RF}$, ${\sf NT}$ do not. Note that the Bayes error is not achieved in this model.

Numerical Experiments

For the experiments illustrated in Figures 1 and 2, we use feature size of $d=450$, and number of hidden units $N\in\{45,\cdots,4500\}$. ${\sf NT}$ and ${\sf NN}$ models are trained with SGD in TensorFlow [ABC+16]. We run a total of $2.0\times 10^{5}$ SGD steps for each (qf) model and $1.4\times 10^{5}$ steps for each (mg) model. The SGD batch size is fixed at $100$ and the step size is chosen from the grid $\{0.001,\cdots,0.03\}$ where the hyper-parameter that achieves the best fit is used for the figures. ${\sf RF}$ models are fitted directly by solving KKT conditions with $5.0\times 10^{5}$ observations. After fitting the model, the test error is evaluated on $1.0\times 10^{4}$ fresh samples. In our figures, each ${\sf RF}$ data point corresponds to the test error averaged over $10$ models with independent realizations of ${\boldsymbol{W}}$.

For (qf) experiments, we choose ${\boldsymbol{B}}$ to be diagonal with diagonal elements chosen i.i.d from standard exponential distribution with parameter $1$. For (mg) experiments, ${\boldsymbol{\Delta}}$ is also diagonal with the diagonal element chosen uniformly from the set $\{\frac{2}{\sqrt{d}},\frac{1.5}{\sqrt{d}},\frac{1}{\sqrt{d}}\}$.

Acknowledgements

This work was partially supported by grants NSF DMS-1613091, CCF-1714305, IIS-1741162, and ONR N00014-18-1-2729, NSF DMS-1418362, NSF DMS-1407813.

References

Appendix A Technical background

A.2 Notations

Appendix B Proofs for quadratic functions

Our results for quadratic functions (qf) assume ${\boldsymbol{x}}_{i}\sim{\sf N}(0,{\mathbf{I}}_{d})$ and $y_{i}=f_{*}({\boldsymbol{x}}_{i})$ where

Note that it is easy to see from the proof that the result stays the same if we add an offset $c$.

where ${\boldsymbol{V}}=[V_{1},\ldots,V_{N}]^{\mathsf{T}}$, and ${\boldsymbol{U}}=(U_{ij})_{i,j\in[N]}$, with

Simply write the KKT conditions. The optimum is achieved at ${\boldsymbol{a}}={\boldsymbol{U}}^{-1}{\boldsymbol{V}}$. ∎

B.1.2 Approximation of kernel matrix 𝑼𝑼{\boldsymbol{U}}

where $({\boldsymbol{w}}_{i})_{i\in[N]}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$ independently. Assume conditions A1 and A2 hold.

Then we have as $N/d=\rho$ and $d\to\infty$,

Step 1. Hermite expansion of $\sigma$ for $\|{\boldsymbol{w}}_{i}\|_{2}\neq 1$. Denote $\sigma_{i}(x)=\sigma(\|{\boldsymbol{w}}_{i}\|_{2}\cdot x)$. First notice that by a change of variables, we get

By Assumption A1, there exists $c_{1}<1$ such that

Denote the Hermite expansion of $\sigma$ to be

By dominated convergence theorem, we have

In addition, by sub-Gaussianity of the norm of a multivariate Gaussian random variable (see [Ver10]), it is easy to show that

Step 2. Expansion of ${\boldsymbol{U}}$. Denote ${\boldsymbol{u}}_{i}={\boldsymbol{w}}_{i}/\|{\boldsymbol{w}}_{i}\|_{2}$, then we have

Step 3. Term ${\boldsymbol{T}}_{0}$. By definition of $\mu_{i}$, we have

Recall the change of variable (22) and do a first order Taylor expansion of the exponential: there exists a function $\xi(G)\in[0,G]$ such that

We see that the integrand goes to zero as $t\to 1$. For $|t-1|$ sufficiently small, we have

Furthermore, for ${\boldsymbol{\mu}}=(\mu_{i})_{i\in[N]}$ with $\mu_{i}=\lambda_{2}(\|{\boldsymbol{w}}_{i}\|_{2}^{2}-1)/2$, we have

where the last equality comes from assumption A2. We get

Step 4. Term ${\boldsymbol{T}}_{1}$. For ${\boldsymbol{T}}_{1}$, we have

By the uniform convergence of $\zeta_{1}(\sigma_{i})$ to $\lambda_{1}(\sigma)$, cf Eq. (24), we have

where we denoted by ${\boldsymbol{G}}$ the matrix with columns ${\boldsymbol{g}}_{i}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d}/d)$. Hence, we have

Step 5. Term ${\boldsymbol{T}}_{2}$. We have

By the uniform convergence of $\zeta_{2}(\sigma_{i})$ to $\lambda_{2}(\sigma)$, we have

Moreover, by the estimates in proof of Theorem 2.1 in [EK+10], we have

Step 6. Term $\sum_{k\geq 3}{\rm ddiag}({\boldsymbol{T}}_{k})$. Denote ${\rm ddiag}({\boldsymbol{T}}_{k})$ the diagonal matrix composed of diagonal entries of ${\boldsymbol{T}}_{k}$. We have

Step 7. Term $\sum_{k\geq 3}[{\boldsymbol{T}}_{k}-{\rm ddiag}({\boldsymbol{T}}_{k})]$. We have

Combining the bounds (27), (28), (29), (30) and (31) into the decomposition (25) proves the lemma. ∎

B.1.3 Approximation of the 𝑽𝑽{\boldsymbol{V}} vector

Under the assumptions of Theorem 1, define ${\boldsymbol{V}}=(V_{1},\ldots,V_{N})^{\mathsf{T}}$ with

where $({\boldsymbol{w}}_{i})_{i\in[N]}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$ independently. Then as $N/d=\rho$ with $d\to\infty$, we have

where ${\boldsymbol{P}}_{\perp{\boldsymbol{w}}_{i}}$ is the projection on the hyperplane orthogonal to ${\boldsymbol{w}}_{i}$, and we recall the definition of $\zeta_{2}(\sigma_{i})$ of Lemma 2:

with $G$ a standard normal random variable.

We define the following interpolating variables:

and the associated vectors ${\boldsymbol{V}}^{(1)}$, ${\boldsymbol{V}}^{(2)}$ and ${\boldsymbol{V}}^{(3)}$. We bound successively the distance between these vectors. We will denote by ${\boldsymbol{P}}_{{\boldsymbol{w}}_{i}}$ the projection onto vector ${\boldsymbol{w}}_{i}$. First, we consider:

One can check, using a similar argument as for Eq. (26) and dominated convergence, that

Let us first show that the sum is bounded with high probability: denoting ${\boldsymbol{g}}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}}_{d})$, classical sub-Gaussian concentration inequalities (see for example Theorem 6.3.2 in [Ver10]) shows that

where $\|\cdot\|_{\psi_{2}}$ denotes the sub-Gaussian Orlicz norm. By assumption, we have $\|{\boldsymbol{\Gamma}}^{1/2}\|_{\text{op}}=\|{\boldsymbol{\Gamma}}\|_{\text{op}}^{1/2}=O_{d}(d^{-1/2})$, and $\|{\boldsymbol{\Gamma}}^{1/2}\|_{F}=\sqrt{\text{\rm Tr}{\boldsymbol{\Gamma}}}=1$. Hence, for ${\boldsymbol{w}}_{i}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$, we have

Furthermore, we readily have (for example from (23))

Noticing that $\text{\rm Tr}({\boldsymbol{w}}_{i}{\boldsymbol{w}}_{i}^{\mathsf{T}}{\boldsymbol{B}})=\|{\boldsymbol{B}}^{1/2}{\boldsymbol{w}}_{i}\|^{2}_{2}$ and by the same argument as for (34), we have:

By assumption A2, we have $\|{\boldsymbol{B}}^{1/2}{\boldsymbol{\Gamma}}^{1/2}\|_{\text{op}}\leq\|{\boldsymbol{B}}^{1/2}\|_{\text{op}}\|{\boldsymbol{\Gamma}}^{1/2}\|_{\text{op}}=O_{d}(d^{-1/2})$ and

Combining the bounds (36), (37) and (39) into (33), we get

which, combined with (39) and (41), yields

where ${\boldsymbol{V}}^{(3)}=\lambda_{2}\text{\rm Tr}({\boldsymbol{\Gamma}}{\boldsymbol{B}}){\mathbf{1}}$. Combining the above three bounds (33), (42) and (43) yields the desired result. ∎

The following proposition is stated in slightly more general terms, in order to be used in both the proofs of Theorem 1 and Theorem 4.

where $\mathcal{D}$ is the empirical distribution of eigenvalues of $d\cdot{\boldsymbol{\Gamma}}$.

The proof of Proposition 2 is a direct combination of Lemma 4, 5, and 6 below.

Let $({\boldsymbol{w}}_{i})_{i\in[N]}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$ independently. Assume condition A2 holds (resp. B2). Let ${\boldsymbol{\mu}}=(\|{\boldsymbol{w}}_{i}\|_{2}^{2}-1)_{i\in[N]}$, and ${\boldsymbol{A}}_{0}=c_{1}{\mathbf{I}}_{N}+c_{2}{\boldsymbol{W}}^{\mathsf{T}}{\boldsymbol{W}}$, where $c_{1}\equiv c_{1}(d)$ and $c_{2}\equiv c_{2}(d)$ are constants that are asymptotically upper and lower bounded by strictly positive constants. Then as $d\rightarrow\infty$ and $N/d\to\rho$, we have

We first prove the lemma under the following extra assumption on the covariance matrix: there exists a (fixed) integer $K$ such that

for some orthogonal matrix ${\boldsymbol{Q}}$ and $d\cdot\gamma_{i}\leq C$. Furthermore, there exists an ${\varepsilon}>0$ such that $d_{k}/d\geq{\varepsilon}$ for $d$ sufficiently large.

Without loss of generality, we assume ${\boldsymbol{\Gamma}}={\rm diag}(\gamma_{1}{\mathbf{I}}_{d_{1}},\ldots,\gamma_{K}{\mathbf{I}}_{d_{K}})$, and we divide ${\boldsymbol{w}}_{i}$ into vectors corresponding to each block

Using the fact that $\|{\boldsymbol{g}}\|_{2}$ is independent of ${\boldsymbol{g}}/\|{\boldsymbol{g}}\|_{2}$ for ${\boldsymbol{g}}\sim{\sf N}({\boldsymbol{0}},{\mathbf{I}})$, the following two sets of random variables have the same distribution:

Since $d_{k}\to\infty$ as $d\to\infty$, we have

Combining (47), (48) and (49) proves the lemma in the case of a covariance of the form (46):

Step 4. From discrete to continuous spectrum.

We consider ${\boldsymbol{\Gamma}}$ a covariance matrix verifying assumption A2. For a given ${\varepsilon}>0$ and $K$ sufficiently large, we consider ${\boldsymbol{\Gamma}}_{{\varepsilon}}$ a matrix obtained from ${\boldsymbol{\Gamma}}$ by binning its eigenvalues to at most $K$ points of $[0,C/d]$, such that we have $\text{\rm Tr}({\boldsymbol{\Gamma}}_{{\varepsilon}})=1$ and $\lim_{d\to\infty}d\cdot\|{\boldsymbol{\Gamma}}-{\boldsymbol{\Gamma}}_{{\varepsilon}}\|_{{\rm op}}\leq{\varepsilon}$ (recall that $\|{\boldsymbol{\Gamma}}\|_{{\rm op}}\leq C/d$ by assumption). Such a matrix always exists from the condition $\text{\rm Tr}({\boldsymbol{\Gamma}})=1$ and the weak convergence of the spectrum of $d\cdot{\boldsymbol{\Gamma}}$.

Furthermore, using $\text{\rm Tr}({\boldsymbol{\Gamma}}-{\boldsymbol{\Gamma}}_{{\varepsilon}})=0$, we have

Noticing that $\|{\boldsymbol{A}}_{0}^{-1}\|_{{\rm op}},\|{\boldsymbol{A}}_{0,{\varepsilon}}^{-1}\|_{{\rm op}}\leq c_{1}^{-1}$, and using (50) applied to ${\boldsymbol{\Gamma}}_{{\varepsilon}}$, we get for $d$ sufficiently large:

Taking a sequence $\delta\to 0$ and ${\varepsilon}$ such that ${\varepsilon}\propto C^{-1}_{\delta}$ shows that this is equivalent to

Taking ${\varepsilon}\propto\sqrt{\delta}$, we deduce that this is equivalent to

Substituting (52) and (53) in (51) concludes the proof. ∎

Under the same setting as Proposition 2, we have

Define ${\boldsymbol{z}}=\sqrt{\kappa}{\mathbf{1}}/\sqrt{d}$. Then we have

By Sherman Morrison Woodbury formula, we have

In the following, we give an asymptotic expression for $\langle{\mathbf{1}},{\boldsymbol{A}}_{0}^{-1}{\mathbf{1}}\rangle/d$.

Let $\rho\in(0,\infty)$. We have almost surely

In addition, assume $\mathcal{D}$ is the limiting spectral distribution of $d\cdot{\boldsymbol{\Gamma}}$. Then, we have almost surely

We know due to fast concentration of $\|z\|^{2}/N$ around one (see e.g. [BLM13]), $P_{1}$ vanish exponentially fast in $N$ (equivalently in $d$ since $N/d$ is fixed to be $\rho$).

Now, let’s consider $P_{2}$. $|{\boldsymbol{z}}^{\mathsf{T}}{\boldsymbol{A}}_{0}^{-1}{\boldsymbol{z}}/N-\text{\rm Tr}({\boldsymbol{A}}_{0}^{-1})/N|$. By Hanson-Wright inequality (see e.g. [BLM13]), we have

B.1.5 Proof of Theorem 1

By Lemma 1, the risk has a representation

B.2 Neural Tangent model: proof of Theorem 2

We can rewrite the neural tangent model with a squared non-linearity $\sigma(x)=x^{2}$ as

where ${\boldsymbol{B}}_{ij}={\boldsymbol{P}}_{i}^{\mathsf{T}}{\boldsymbol{B}}{\boldsymbol{P}}_{j}$ for $i,j=1,2$. We readily deduce that

The last term of the sum (65) is also derived by first conditioning on ${\boldsymbol{v}}_{1}$. Let us denote ${\boldsymbol{z}}_{1}={\boldsymbol{P}}_{\perp{\boldsymbol{v}}_{1}}{\boldsymbol{e}}_{1}$ and ${\boldsymbol{z}}_{2}={\boldsymbol{P}}_{\perp{\boldsymbol{v}}_{1}}{\boldsymbol{e}}_{2}$ the projections of $({\boldsymbol{e}}_{1},{\boldsymbol{e}}_{2})$ on the hyperplane perpendicular to ${\boldsymbol{v}}_{1}$, on which ${\boldsymbol{v}}_{2}$ is uniformly distributed over the unit sphere. We decompose ${\boldsymbol{z}}_{2}$ into two components: one along ${\boldsymbol{z}}_{1}$ that we denote ${\boldsymbol{z}}_{2}^{(1)}={\boldsymbol{P}}_{\parallel{\boldsymbol{z}}_{1}}{\boldsymbol{z}}_{2}$ and one perpendicular to ${\boldsymbol{z}}_{1}$, denoted ${\boldsymbol{z}}_{2}^{(2)}={\boldsymbol{P}}_{\perp{\boldsymbol{z}}_{1}}{\boldsymbol{z}}_{2}$. Then we have:

where we used the same argument as for (66). Plugging the above limits (66), (67) and (68) in the expansion (65), we get

The above formula for the ${\sf RF}$ risk Eq. (69) has two terms that corresponds to the two limits $\text{\rm Tr}({\boldsymbol{B}})/\|{\boldsymbol{B}}\|_{F}=o_{d}(\sqrt{d})$ (e.g. spiked matrix)

and $\text{\rm Tr}({\boldsymbol{B}})^{2}=d\|{\boldsymbol{B}}\|_{F}^{2}$ (i.e. ${\boldsymbol{B}}\propto{\mathbf{I}}$)

B.3 Neural Network model: proof of Theorem 3

We consider two-layers neural networks with quadratic activation function $\sigma(x)=x^{2}$ and we fix the second layer weights to $1$,

We consider the ground truth function $f_{*}$ to be a quadratic function as per Eq. (20), and the risk function defined by

We consider running SGD dynamics upon the risk function for a fresh sample $({\boldsymbol{x}}_{k},f_{*}({\boldsymbol{x}}_{k}))$ for each iteration

The infimum of $L$ over ${\boldsymbol{W}}$ is equivalent to the low-rank approximation problem of matrix ${\boldsymbol{B}}$ in Frobenius norm, with rank less or equal to $\max(d,N)$, and is given by the Eckart-Young-Mirsky theorem (see [EY36]). ∎

B.3.2 Landscape: proof of Proposition 1

Without loss of generality, throughout the proof, we assume that ${\boldsymbol{B}}$ is diagonal and $b_{0}=0$. Our first proposition characterizes the critical points of $L({\boldsymbol{W}},c)$.

Then for any critical point $({\boldsymbol{W}}_{0},c_{0})$ of $L({\boldsymbol{W}},c)$, there exists a projection matrix ${\boldsymbol{P}}=\sum_{i=1}^{k}{\boldsymbol{e}}_{\tau(i)}{\boldsymbol{e}}_{\tau(i)}^{\mathsf{T}}$ for some injection $\tau:[k]\to[d]$, such that ${\boldsymbol{\Gamma}}_{0}={\boldsymbol{W}}_{0}{\boldsymbol{W}}_{0}^{\mathsf{T}}$ is diagonal and satisfy

We consider the gradient of this function. We get:

By the stationary condition, at a critical point $({\boldsymbol{W}}_{0},c_{0})$, we must have:

This is of the form of the eigenvalue equation of matrix ${\boldsymbol{B}}$. Hence we must have the columns of ${\boldsymbol{U}}_{1}$ to be a set of eigenvectors and ${\boldsymbol{S}}_{1}^{2}$ to be positive eigenvalues of ${\boldsymbol{B}}$. This proves the proposition. ∎

Note the global minimizers are attained for ${\boldsymbol{\Gamma}}_{0}={\boldsymbol{W}}_{0}{\boldsymbol{W}}_{0}^{\mathsf{T}}$ corresponding to the $\min(N,d)$ directions of ${\boldsymbol{B}}$ with the largest eigenvalues. We prove in the following proposition that stationary points that are not global minimizers are strict saddle points.

Define the spectral separation of ${\boldsymbol{B}}$ as

and $\delta^{\textup{eig}}$ the minimum strictly positive eigenvalue of ${\boldsymbol{B}}$.

Consider $({\boldsymbol{W}}_{0},c_{0})$ a stationary point of $L({\boldsymbol{W}},c)$ but not a global minimizer. Then, we have

Let us first compute the Hessian of the risk with respect to the ${\boldsymbol{W}}$ variable. We have

Plugging the value of $c_{0}$ at a critical point (cf Eq. (70)), we get

Case 1: Consider the case $\text{rank}({\boldsymbol{W}}_{0})<\min\{\text{rank}({\boldsymbol{B}}),N\}$. Then there exists an $i\in[d]$ such that ${\boldsymbol{B}}_{ii}>0$ (recall that we assumed ${\boldsymbol{B}}$ diagonal , with diagonal elements given by the positive eigenvalues of ${\boldsymbol{B}}$) and $({\boldsymbol{W}}_{0}{\boldsymbol{W}}_{0}^{\mathsf{T}})_{ii}=0$. For simplicity, let us permute the coordinates so that $i=1$. The singular value decomposition of ${\boldsymbol{W}}_{0}$ verifies

We have $\|{\boldsymbol{Z}}\|_{F}=1$ and ${\boldsymbol{W}}_{0}{\boldsymbol{Z}}^{\mathsf{T}}=0$. Plugging these matrices in the above expression of the Hessian, see Eq. (73), we get

Case 2: Consider the case when $\text{rank}({\boldsymbol{W}}_{0}{\boldsymbol{W}}_{0}^{\mathsf{T}})=N<\text{rank}({\boldsymbol{B}})$ and ${\boldsymbol{W}}_{0}{\boldsymbol{W}}_{0}^{\mathsf{T}}$ does not correspond to the $N$ largest eigenvalues of ${\boldsymbol{B}}$. Then there exists $i\neq j\in[n]$, such that ${\boldsymbol{B}}_{ii}>{\boldsymbol{B}}_{jj}$, $({\boldsymbol{W}}_{0}{\boldsymbol{W}}_{0}^{\mathsf{T}})_{ii}=0$ and $({\boldsymbol{W}}_{0}{\boldsymbol{W}}_{0}^{\mathsf{T}})_{jj}={\boldsymbol{B}}_{jj}$. For simplicity, let us permute the coordinates such that $i=1$ and $j=2$. The SVD decomposition of ${\boldsymbol{W}}_{0}$ now verifies:

We have $\|{\boldsymbol{Z}}\|_{F}=1$. Plugging these matrices in the above expression of the Hessian (73), note

First, remark that $L({\boldsymbol{W}},c)$ has compact sub-level sets. The proposition then follows from Proposition 4 and the continuity of the gradient $\nabla L({\boldsymbol{x}})$ and of the minimum eigenvalue of the Hessian $\lambda_{\min}(\nabla^{2}L({\boldsymbol{x}}))$. ∎

B.3.3 Dynamics

The following lemma is a standard combination of Lojasiewicz inequality and center and stable manifold theorem. We prove it for completeness.

Then for (Lebesgue) almost all initialization ${\boldsymbol{x}}_{0}$, there exists a second order local minimizer ${\boldsymbol{x}}_{*}$, such that

Step 1. Show convergence to a critical point. Since $f$ is an analytic function, by Lojasiewicz inequality [Loj82], and the fact that the level set of $f$ is compact, we have

for ${\boldsymbol{x}}_{*}$ some critical point of $f$.

Step 2. Show convergence to a local minimizer. In this step, we proceed similarly to the proof of Theorem 3 in [PP16]. First, consider a sublevel set

Then we have $\Omega(K)$ compact. Since $f$ is an analytic function, $\nabla f$ is Lipschitz in the compact set $\Omega(K)$. We define the map $\phi_{t}:\Omega(K)\to\phi_{t}(\Omega(K))$, ${\boldsymbol{x}}\mapsto{\boldsymbol{x}}_{t}$ where ${\boldsymbol{x}}_{t}$ is defined as the solution of

By Picard’s existence and uniqueness theorem, we have $\phi_{t}$ is a diffeomorphism from $\Omega(K)$ to $\phi(\Omega(K))$ for any $t>0$. Fix an $\varepsilon_{0}>0$, and we define $g=\phi_{\varepsilon_{0}}:\Omega(K)\to\Omega(K)$.

Let ${\boldsymbol{r}}$ be a strict saddle point of $f$, then ${\boldsymbol{r}}$ must be an unstable fixed point of the diffeomorphism $g=\phi_{{\varepsilon}_{0}}$. By center and stable manifold theorem (such as Theorem 9 in [PP16]), there exists a manifold $W_{{\rm loc}}^{{\rm sc}}({\boldsymbol{r}})$ of dimension at most $d-1$, and a ball ${\mathsf{B}}({\boldsymbol{r}},\varepsilon({\boldsymbol{r}}))$ centered at ${\boldsymbol{r}}$ with radius $\varepsilon({\boldsymbol{r}})$, such that we have the following facts:

$g\left(W_{{\rm loc}}^{{\rm sc}}({\boldsymbol{r}})\cap{\mathsf{B}}({\boldsymbol{r}},\varepsilon({\boldsymbol{r}}))\right)\subseteq W_{{\rm loc}}^{{\rm sc}}({\boldsymbol{r}})$;

If $g^{n}({\boldsymbol{x}})\in{\mathsf{B}}({\boldsymbol{r}},\varepsilon({\boldsymbol{r}}))$ for all $n\geq 0$, we have ${\boldsymbol{x}}\in W_{{\rm loc}}^{{\rm sc}}({\boldsymbol{r}})$ (here $g^{n}$ means composition of $g$ for $n$ times).

We consider the union of the balls associated to all the strict saddle points of $f$ in $\Omega(K)$

Due to Lindelof’s lemma, we can find a countable subcover for $A$, i.e., there exists fixed-points ${\boldsymbol{r}}_{1},{\boldsymbol{r}}_{2},\ldots$ such that $A=\cup_{m=1}^{\infty}{\mathsf{B}}({\boldsymbol{r}}_{m},\varepsilon({\boldsymbol{r}}_{m}))$. If gradient descent converges to a strict saddle point, starting from a point ${\boldsymbol{v}}\in\Omega(K)$, there must exist a $t_{0}$ and $m$ such that $\phi_{t}({\boldsymbol{v}})\in{\mathsf{B}}({\boldsymbol{r}}_{m},\varepsilon({\boldsymbol{r}}_{m}))$ for all $t\geq t_{0}$. By center and stable manifold theorem, we get that $\phi_{t}({\boldsymbol{v}})\in W_{{\rm loc}}^{{\rm sc}}({\boldsymbol{r}}_{m})\cap\Omega(K)$. By setting $D_{1}({\boldsymbol{r}}_{m})=g^{-1}(W_{{\rm loc}}^{{\rm sc}}({\boldsymbol{r}}_{m})\cap\Omega(K))$ and $D_{i+1}({\boldsymbol{r}}_{m})=g^{-1}(D_{i}({\boldsymbol{r}}_{m})\cap\Omega(K))$ we get that ${\boldsymbol{v}}\in D_{k}({\boldsymbol{r}}_{m})$ for all $k\varepsilon_{0}\geq t_{0}$. Hence the set of initial points in $\Omega(K)$ such that gradient descent converges to a strict saddle point is a subset of

The following lemma is standard, and a corollary of Theorem 2.11 in [Kur70].

Let ${\boldsymbol{x}}_{t}$ be the trajectory of

with initialization ${\boldsymbol{x}}_{0}\in\Omega$. Further assume that there exists $\eta>0$, such that $\cup_{t\geq 0}{\mathsf{B}}({\boldsymbol{x}}_{t},\eta)\subseteq\Omega$.

Consider the following Markov jump process ${\boldsymbol{x}}_{t,\varepsilon}$ starting from ${\boldsymbol{x}}_{0}$, with jump time to be an exponential random variable with fixed mean $\varepsilon$, and jump direction $-\varepsilon\nabla f({\boldsymbol{x}};{\boldsymbol{z}})$ where ${\boldsymbol{x}}$ is the current state, and ${\boldsymbol{z}}$ an independent sample. Then we have for any fixed $T>0$ and $\delta>0$,

B.3.4 Proof of Theorem 3

By Proposition 4, we know that for $L({\boldsymbol{W}},c)$, any critical point that is not a global minimizer is a strict saddle point. Consider the gradient flow

with random initialization $({\boldsymbol{W}}_{0},c_{0})\sim\nu_{0}$ where $\nu_{0}$ is a distribution that is absolutely continuous with respect to Lebesgue measure. Since $L({\boldsymbol{W}},c)$ is an analytic function, by Lemma 8, we have $({\boldsymbol{W}}_{t},c_{t})$ converges to a global minimizer of $L({\boldsymbol{W}},c)$. That is, we have almost surely (over $\nu_{0}$)

where $\inf_{{\boldsymbol{W}},c}L({\boldsymbol{W}},c)$ is calculated in Lemma 7.

Consider the following Markov jump process $({\boldsymbol{W}}_{t,\varepsilon},c_{t,\varepsilon})$ starting from $({\boldsymbol{W}}_{0},c_{t})\sim\nu_{0}$, with jump time to be an exponential random variable with fixed mean $\varepsilon$, and jump direction to be $-\varepsilon\nabla L({\boldsymbol{W}},c;{\boldsymbol{z}})$ where

with $({\boldsymbol{W}},c)$ the current state, and ${\boldsymbol{z}}$ an independent sample. By Lemma 9, we have for any fixed $T>0$ and $\delta>0$,

Note the sequence of Markov jump process at jump time is exactly the SGD iterates. Hence the SGD iterates with properly scaled number of iterations is uniformly close to $({\boldsymbol{W}}_{t},c_{t})$ over finite horizon as ${\varepsilon}\to 0$. This proves the Theorem.

Appendix C Proofs for Mixture of Gaussians

In this section, we consider the mixture of Gaussian setting (mg): $y_{i}=\pm 1$ with equal probability $1/2$, and ${\boldsymbol{x}}_{i}|y_{i}=+1\sim{\sf N}(0,{\boldsymbol{\Sigma}}^{(1)})$, ${\boldsymbol{x}}_{i}|y_{i}=-1\sim{\sf N}(0,{\boldsymbol{\Sigma}}^{(2)})$ where ${\boldsymbol{\Sigma}}^{(1)}={\boldsymbol{\Sigma}}-{\boldsymbol{\Delta}}$ and ${\boldsymbol{\Sigma}}^{(2)}={\boldsymbol{\Sigma}}+{\boldsymbol{\Delta}}$. With these notations,

Throughout this section, we will make the following assumptions:

There exists constants $0<c_{1}<c_{2}$ such that $c_{1}{\mathbf{I}}_{d}\preceq{\boldsymbol{\Sigma}}\preceq c_{2}{\mathbf{I}}_{d}$;

$\|{\boldsymbol{\Delta}}\|_{\rm op}=\Theta_{d}(1/\sqrt{d})$.

Note that it is easy to see from the proof that the result stays the same if we add an offset $c$.

Consider the RF model introduced above. We have

where ${\boldsymbol{V}}=[V_{1},\ldots,V_{N}]^{\mathsf{T}}$, and ${\boldsymbol{U}}=(U_{ij})_{i,j\in[N]}$, with

Simply write the KKT conditions. The optimum is achieved at ${\boldsymbol{a}}={\boldsymbol{U}}^{-1}{\boldsymbol{V}}$. ∎

C.1.2 Approximation of kernel matrix 𝑼𝑼{\boldsymbol{U}}

where $({\boldsymbol{w}}_{i})_{i\in[N]}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$ independently. Assume conditions A1 and B2 hold.

Then we have as $N/d=\rho$ and $d\to\infty$, we have

Recalling that in the (${\sf mg}$) model, we have ${\boldsymbol{x}}\sim(1/2)\cdot{\sf N}({\boldsymbol{0}},{\mathbf{I}}-{\boldsymbol{\Delta}})+(1/2)\cdot{\sf N}({\boldsymbol{0}},{\mathbf{I}}+{\boldsymbol{\Delta}})$, we have

We also have $\text{\rm Tr}({\boldsymbol{\Delta}}{\boldsymbol{\Gamma}}{\boldsymbol{\Delta}}{\boldsymbol{\Gamma}})^{2}=o_{d}(d^{-1})$ by assumptions M2 and B2, hence

Therefore, combining (76) and (77), we get:

Combining (75) and (78) concludes the proof. ∎

C.1.3 Approximation of the 𝑽𝑽{\boldsymbol{V}} vector

Under the assumption of Theorem 4, define ${\boldsymbol{V}}=(V_{1},\ldots,V_{N})^{\mathsf{T}}$ with

where $({\boldsymbol{w}}_{i})_{i\in[N]}\sim{\sf N}({\boldsymbol{0}},{\boldsymbol{\Gamma}})$ independently. Then as $N/d=\rho$ with $d\to\infty$, we have

Using dominated convergence theorem and arguments similar to those used to prove (26), one can check that

The same arguments as in the proofs of Lemma 2 and Lemma 3 show

Combining (80) with (81) in (79), we get:

Bounding similarly the term depending on $({\mathbf{I}}+{\boldsymbol{\Delta}})^{1/2}{\boldsymbol{w}}_{i}$ in $V_{i}^{(1)}$, we get

Now, consider the difference between ${\boldsymbol{V}}^{(1)}$ and ${\boldsymbol{V}}^{(2)}$. We use the fact for $x$ on a neighborhood of , there exists $c$ such that

where the last equality is due to assumptions M2 and B2. We conclude that

For the last comparison between ${\boldsymbol{V}}^{(2)}$ and ${\boldsymbol{V}}^{(3)}$, we take the expectation:

Combining the above three bounds (82), (83) and (84) yields the desired result. ∎

C.1.4 Proof of Theorem 4

By Lemma 10, the risk has a representation

C.2 Neural Tangent model: proof of Theorem 5

Assume conditions M1 and M2 hold. Consider the function

Define the risk function optimized over $a,c$ while ${\boldsymbol{\Gamma}}$ is fixed

Minimizing successively over $c$ and $a$, we get the following formula:

By Assumptions M1 and M2, we have ${\boldsymbol{\Sigma}}\succeq c{\mathbf{I}}_{d}$ and $\|{\boldsymbol{\Delta}}\|_{{\rm op}}\leq C/\sqrt{d}$ for some constants $c$ and $C$. We get

C.2.2 Proof of Theorem 5

where the minimizer ${\boldsymbol{G}}={\boldsymbol{\Delta}}$ is obtained by Cauchy-Schwarz inequality.

Case $N/d\to\rho<1$. Consider now the case when $N<d$. From (88), the optimal ${\boldsymbol{G}}$ is the one maximizing

which we rewrite as the following convex problem

which yields, using ${\boldsymbol{P}}_{1}^{\mathsf{T}}{\boldsymbol{P}}_{1}={\mathbf{I}}_{N}$,

where ${\boldsymbol{\Delta}}_{ij}={\boldsymbol{P}}_{i}^{\mathsf{T}}{\boldsymbol{\Delta}}{\boldsymbol{P}}_{j}$ for $i,j=1,2$. The constraint reads in the ${\boldsymbol{P}}$ basis

Considering the (unique) symmetric optimizer ${\boldsymbol{G}}_{1}$ and substituting (92) in (90), we get the minimizer

Substituting (94) in (88), we then obtain

where ${\boldsymbol{\Delta}}_{22}={\boldsymbol{P}}_{{\boldsymbol{W}}^{\perp}}{\boldsymbol{\Delta}}{\boldsymbol{P}}_{{\boldsymbol{W}}^{\perp}}$ with ${\boldsymbol{P}}_{{\boldsymbol{W}}^{\perp}}={\mathbf{I}}_{d}-{\boldsymbol{W}}({\boldsymbol{W}}^{\mathsf{T}}{\boldsymbol{W}})^{-1}{\boldsymbol{W}}^{\mathsf{T}}$ is the random projection along the orthogonal subspace to the columns of ${\boldsymbol{W}}$. From Theorem 2, we know that

by assumption M2 on ${\boldsymbol{\Delta}}$. We deduce that there exists a constant $c$ (that depends on $\rho$ and $C$) such that:

Using (97) and (95), we deduce the final high probability formula for the risk of the NT model:

C.3 Neural Network model: proof of Theorem 6

where we consider the function class of two-layers neural networks (with $N$ neurons) with quadratic activation function and general offset and coefficients

We define the risk function for a given set of parameters as

The risk is optimized over $(a_{i},{\boldsymbol{w}}_{i})_{i\leq N}$ and $c$.

where ${\boldsymbol{A}}={\rm diag}({\boldsymbol{a}})$. Define ${\boldsymbol{\Gamma}}={\boldsymbol{W}}{\boldsymbol{A}}{\boldsymbol{W}}^{\mathsf{T}}$ and using Eq. (87) in Lemma 13, the minimizer ${\boldsymbol{\Gamma}}^{*}$ is the solution of

where the $\lambda_{i}$’s are the singular values of ${\boldsymbol{\Delta}}$ in descending order. Plugging this expression in Eq. (87) concludes the proof. ∎