PaperlayerView exact revision on arXiv

Source-linked AI summary

Linearized two-layers neural networks in high dimension

Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari

arXiv:1904.12191v3math.STcs.LG

TL;DR

The paper studies how high-dimensional learning with neural-network linearizations behaves, against a backdrop in which computational aspects of neural-network theory were underrepresented. It analyzes random features and neural tangent models across approximation- and sample-limited regimes, finding degree-limited fitting and a sample threshold for rotationally invariant NT kernels.

  • Problem

    Computational aspects of neural-network theory were underrepresented, although optimization selects among near-minimizers with differing generalization properties.

    Source: §1.1 · p. 3

  • Method

    The analysis studies RF and NT across approximation- and sample-size-limited regimes, relating their fits to polynomial spaces and rotationally invariant kernels.

    Source: §1.4 · p. 8

  • Results

    For rotationally invariant NT kernels, targets with vanishing projection onto degree-ℓ polynomials cannot outperform the trivial predictor unless n ≥ d^(ℓ+1−δ).

    Source: §1.4 · p. 8

  • Takeaways & Limitations

    For d^(ℓ+δ) ≤ n ≤ d^(ℓ+1−δ), KRR's ideal behavior is achieved by near-interpolators with negligible training error.

    Source: §1.4 · p. 9

    The analysis assumes a weakly differentiable activation whose derivative satisfies σ′(u)^2 ≤ c0 exp(c1u^2/2), for constants c0 > 0 and c1 < 1.

    Source: §8.1 · p. 36

Abstract

from arXiv · show

We consider the problem of learning an unknown function $f_{\star}$ on the $d$-dimensional sphere with respect to the square loss, given i.i.d. samples $\{(y_i,{\boldsymbol x}_i)\}_{i\le n}$ where ${\boldsymbol x}_i$ is a feature vector uniformly distributed on the sphere and $y_i=f_{\star}({\boldsymbol x}_i)+\varepsilon_i$. We study two popular classes of models that can be regarded as linearizations of two-layers neural networks around a random initialization: the random features model of Rahimi-Recht (RF); the neural tangent kernel model of Jacot-Gabriel-Hongler (NT). Both these approaches can also be regarded as randomized approximations of kernel ridge regression (with respect to different kernels), and enjoy universal approximation properties when the number of neurons $N$ diverges, for a fixed dimension $d$. We consider two specific regimes: the approximation-limited regime, in which $n=\infty$ while $d$ and $N$ are large but finite; and the sample size-limited regime in which $N=\infty$ while $d$ and $n$ are large but finite. In the first regime we prove that if $d^{\ell + δ} \le N\le d^{\ell+1-δ}$ for small $δ> 0$, then \RF\, effectively fits a degree-$\ell$ polynomial in the raw features, and \NT\, fits a degree-$(\ell+1)$ polynomial. In the second regime, both RF and NT reduce to kernel methods with rotationally invariant kernels. We prove that, if the number of samples is $d^{\ell + δ} \le n \le d^{\ell +1-δ}$, then kernel methods can fit at most a a degree-$\ell$ polynomial in the raw features. This lower bound is achieved by kernel ridge regression. Optimal prediction error is achieved for vanishing ridge regularization.

1 Introduction and main results

The paper studies high-dimensional prediction with random-features (RF) and neural-tangent (NT) models, characterizing their approximation limits at finite width and the generalization limits of kernel methods at finite sample size.

1.1 Background

  • In the overparameterized regime, neural networks are approximated by first-order linearizations: RF varies second-layer weights, while NT varies first-layer weights.The analysis treats these as distinct function classes and studies their behavior in high dimensions.Source: §1.1 · pp. 3–4

1.2 A parenthesis

  • Pointwise, sharp high-dimensional results address limits of earlier worst-case approximation bounds and enable separation statements between neural networks and their linearized counterparts.The paper emphasizes quantitative results for large d and N, with errors vanishing as d grows.Source: §1.1 · p. 4, §1.2 · p. 5

1.3 A numerical experiment

  • RF does not beat the trivial predictor on the quadratic target, and NT does not do so on the third-order target; NT beats it on the quadratic target as n grows.The NT quadratic-target risk appears to decrease to zero; the experiments also show a risk cusp near n≈p, the number of model parameters.Source: Figure 1 · p. 6, Figure 2 · p. 6, §1.3 · p. 7

1.4 Summary of main results

  • For d^ℓ+δ ≤ N ≤ d^(ℓ+1−δ), RF approximation is pointwise equivalent to least-squares fitting all raw-feature monomials of degree at most ℓ.This includes linear regression when d^(1+δ) < N ≤ d^(2−δ).Source: §1.4 · p. 8
  • For d^ℓ+δ ≤ N ≤ d^(ℓ+1−δ), NT approximation is pointwise equivalent to fitting raw-feature monomials through degree ℓ+1.In particular, when d^(1+δ) ≤ N ≤ d^(2−δ), the equivalent model includes monomials through degree two.Source: §1.4 · p. 8
  • With n ≤ d^(ℓ+1−δ), any rotationally invariant kernel method has generalization error at least the degree-ℓ polynomial-regression approximation error; KRR attains it when d^ℓ+δ ≤ n ≤ d^(ℓ+1−δ).This applies to the rotationally invariant NT kernel of infinitely wide fully connected networks under i.i.d. Gaussian weight initialization.Source: §1.4 · p. 8
  • For d^ℓ+δ ≤ n ≤ d^(ℓ+1−δ), KRR's ideal behavior holds for regularization λ ≤ λ*, including near interpolators with negligible training error.The threshold λ* depends on N, d, and the activation function.Source: §1.4 · p. 9

2 Approximation error of linearized neural networks

The approximation error of RF and NT models changes in polynomial-degree steps as their size grows, while certain target functions remain learnable by neural networks but not by their linearizations. The results also compare RF and NT at equal parameter counts and identify a prediction-time advantage for NT.

2.1 Approximation error of random features models

  • With ω(d^ℓ) neurons and at most O(d^(ℓ+1−δ)) neurons, RF approximately fits polynomials through degree ℓ, leaving the higher-degree component’s squared norm as its error.Under the stated activation assumptions, the risk decomposes into the RF risk on the degree-at-most-ℓ projection and the squared norm of the remaining component; the first term vanishes asymptotically.Source: §2.1 · p. 10

2.2 Approximation error of neural tangent models

  • The NT results require activation conditions: assumptions (a) and (b) hold for commonly used activations, while assumption (c) excludes ReLU but holds for generically shifted ReLU.The cited examples establish the applicable activation conditions for the respective NT results.Source: §2.2 · p. 11
  • At fixed parameter count p, RF and NT have the same approximation error, with staircase-like drops as log(p)/log(d) reaches integer values.NT uses p = Nd parameters and RF uses p = N; the drops correspond to projection onto homogeneous polynomials of successive degrees.Source: §2.2 · p. 12
  • At constant p, NT prediction costs O(p), compared with O(pd) for RF.The stated prediction-time complexities are O(Nd) = O(p) for NT and O(Nd) = O(pd) for RF.Source: §2.2 · p. 12
  • For typical targets, fewer than o(d^(ℓ+1)) orthogonal monomial basis elements yield approximation error ∥P>ℓf⋆∥², and RF or NT behave similarly.“Typical” targets are formed by applying a Haar-distributed rotation to a fixed function.Source: §2.2 · p. 12
  • When a target depends mainly on d1 ≪ d directions, choosing random features in that subspace may offer an advantage; sensitivity to the subspace dimension remains a proposed direction.The paper presents this as a possible improvement, not an established result.Source: §2.2 · pp. 12–13

2.3 Separation between NN and RF, NT

  • For f⋆(x) = σ(⟨w⋆, x⟩), one-neuron networks represent the target exactly, while RF and NT retain non-vanishing error in the stated intermediate-width regime.Gradient descent over single-neuron networks can efficiently learn this target [MBM16], separating the linearized models from neural networks trained by gradient descent.Source: §2.3 · p. 13

3 Generalization error of kernel methods

For rotationally invariant kernel methods, the sample-size scale limits the polynomial degrees they can fit, and kernel ridge regression attains the corresponding prediction-error bound. The section contrasts this limitation with gradient descent and discusses near-interpolating KRR and a conjecture for finite random features.

3 Generalization error of kernel methods

  • As N → ∞, RF and NT ridge regression converge to KRR with rotationally invariant kernels, a framework that also covers multilayer NT kernels under layerwise Gaussian initialization.The unit ball of the RF RKHS is well approximated by the finite-feature unit ball for sufficiently large N [Bac17b].Source: §3 · pp. 13–14

3.1 Lower bound for general kernel methods

  • For general kernel methods, the prediction-risk decomposition is controlled by sample size n rather than neuron count N, yielding a degree-ℓ fitting limit in the stated sample-size regime.The lower-bound theorem assumes n ≤ d^(ℓ+1−δ) up to its stated asymptotic condition; the paper’s overall regime is d^ℓ+δ ≤ n ≤ d^(ℓ+1−δ).Source: §3.1 · p. 15

3.2 Upper bound for kernel ridge regression

  • Theorem 4 considers n in the range ω_d(d^ℓ log d) ≤ n ≤ O_d(d^(ℓ+1−δ)); for ε > 0 and λ ∈ (0, λ*), its conclusion holds with high probability.For d-independent σ ∈ L2(R, γ), Assumption 3 holds if µ_k(σ) ≠ 0 for every k ≤ ℓ.Source: §3.2 · p. 16

3.3 Separation between kernel methods and neural networks

  • O(d log d/n) prediction error is attainable by gradient descent, while kernel methods have test error bounded away from zero when d^ℓ+δ ≤ n ≤ d^(ℓ+1−δ).The gradient-descent result assumes n ≥ C d log d samples and technical conditions on σ; KRR achieves the kernel error bound.Source: §3.3 · p. 17

3.4 Near-optimality of interpolators

  • For λ < λ*, KRR’s predictor is close in ℓ2 to the target’s degree-ℓ approximation, and taking λ → 0 yields an interpolator with optimal test error.Theorem 5 quantifies the empirical risk under the same sample-size and kernel assumptions as Theorem 4.Source: §3.4 · p. 17

3.5 A conjecture for generalization error of random features model

  • When d^ℓ+δ ≤ min(n, N) ≤ d^(ℓ+1−δ), the authors conjecture that RF prediction error matches that of fitting a degree-ℓ polynomial.They leave this finite-sample, finite-neuron conjecture for future work.Source: §3.5 · p. 18

4 Further related work

The section situates the paper’s kernel and random-features results among related work, emphasizing differences in asymptotic regimes, prediction-error analysis, and model scope. It also contrasts prior approximation and wide-network analyses with the paper’s setting.

4 Further related work

  • Donoho and Johnstone study approximation on the two-dimensional unit circle using equally spaced directions, with worst-case lower bounds over differentiable functions.Spherical harmonic expansions also appear in related contexts [VW18].Source: §4 · pp. 18–19
  • El Karoui (also) shows that kernel random matrices approximate a raw-feature Gram matrix plus a diagonal term when n is proportional to d.That work analyzes the spectrum, whereas this paper treats polynomial sample-size scalings and prediction error, and also studies RF and NT models.Source: §4 · p. 18
  • Related wide-limit analyses include RF learning degree-ℓ polynomials with n and N of order d^O(ℓ) [VW18] and mean-field training beyond NT’s linear regime [RVE18] [SS18] [MMM19].The paper states its RF tradeoff is sharper because it gives precise exponents of d; [VW18] also establishes a statistical-query lower bound of d^Ω(ℓ) queries.Source: §4 · p. 19
  • Liang, Rakhlin, and Zhai [LRZ19] bound kernel ridge regression’s generalization error for bounded-RKHS-norm targets, while this paper derives precise non-vanishing-error asymptotics without that assumption.The paper also uses spherical harmonic analysis, which appears in related contexts [VW18].Source: §4 · p. 19

5 Technical background

The section establishes the spherical-harmonic and orthogonal-polynomial tools used in later proofs, along with asymptotic notation.

5.1 Functional spaces over the sphere

  • On the sphere, restrictions of homogeneous harmonic polynomials define orthogonal subspaces that decompose the function space, with projections onto each degree.The framework takes functions in L2 of the sphere under its uniform probability measure.Source: §5.1 · pp. 19–20

5.2 Gegenbauer polynomials

  • For each degree, a Gegenbauer polynomial of the inner product represents the spherical-harmonic projector; rotationally invariant operators act diagonally on these subspaces.The operator’s eigenvalue on degree k is denoted ξd,k(hd).Source: §5.2 · p. 21

5.3 Hermite polynomials

  • Hermite polynomials form an orthogonal basis of Gaussian L2 and arise as fixed-degree, high-dimensional limits of suitably scaled Gegenbauer polynomials.Both polynomial families are obtained by Gram–Schmidt orthogonalization, with the Gegenbauer construction using the sphere-induced measure and Hermite using the standard Gaussian measure.Source: §5.3 · pp. 21–22

5.4 Notations

  • The notation section defines big-O and little-o asymptotics, their in-probability versions, and variants that hide logarithmic factors.The subscript d identifies the asymptotic variable; a tilde permits a fixed power of log d.Source: §5.4 · p. 22

6 Proof of Theorem 1.(a): RF model lower bound

This section proves the RF model lower bound by controlling degree-separated random-feature components and the kernel matrix, including bounds on Gegenbauer Gram-matrix norms. It also shows that the expected operator norm of Δ vanishes as A grows under a specified choice of N and p, using expected-norm estimates and moment bounds organized through multigraphs and skeletonization.

6.1 Proof of Theorem 1.(a): Outline

  • The outline splits random-feature vectors into degrees ≤ell and >ell, uses orthogonality and norm and kernel-matrix bounds, and concludes the theorem when N=o(d^(ell+1)).The outline invokes Propositions 1 and 2 and uses B(d,ell+1)=Theta(d^(ell+1)).Source: §6.1 · pp. 23–24

6.2 Proof of Proposition 1

  • Proposition 1 provides an expected-norm bound for V under the stated activation assumptions.The supplied passages identify the proposition’s expected-norm result but do not show its bound’s formula.Source: §6.1 · p. 24, §6.2 · p. 26

6.3 Proof of Proposition 2

  • The Proposition 2 proof decomposes kernel matrix U into Gegenbauer-degree components and establishes its lower bound with high probability.The proof uses a bound involving B(d,2ell+3) and N=o(d^(ell+1)).Source: §6.3 · pp. 26–27

6.4 Proof of Proposition 3

  • Proposition 3 bounds Gegenbauer Gram-matrix operator norms by moments, organizing terms as multigraphs and skeletonizing degree-2 vertices into type-1 and type-2 sequences.The skeletonization process removes redundant degree-2 vertices; type-2 skeletons have vertices of degree at least 4.Source: §6.4 · pp. 27–30
  • E[||Δ||op] → 0 as A → ∞ with N = d^k e^(-2A√log d) and p = (k/A)√log d; this p satisfies p = o(d) and Eq. (68) for large d.Source: §6.4 · p. 33

7 Proof of Theorem 1.(b): RF model upper bound

The proof shows that, for degree-at-most-ℓ targets, a suitable random-features coefficient construction yields risk converging to zero when the stated width condition holds. It relies on the kernel operator being invertible on polynomials of degree at most ℓ.

7 Proof of Theorem 1.(b): RF model upper bound

  • On the degree-at-most-ℓ polynomial subspace, the spherical-harmonic basis diagonalizes K, and Assumption 1.(b) makes K bijective for sufficiently large d.Thus the restricted inverse K^-1 is well defined.Source: §7 · p. 34
  • Choosing α(θ) = (K^-1 T f_d)(θ) and a_i = N^-1 α(θ_i) provides the coefficients used in the RF risk bound.The inverse is taken on the subspace of polynomials of degree at most ℓ.Source: §7 · p. 34
  • Under Assumption 1.(b) and N = ω_d(d^ell), the constructed RF risk converges to zero in L1 over Θ, and therefore in probability.The targets are assumed to be polynomials of degree at most ℓ.Source: §7 · pp. 34–35

8 Proof of Theorem 2.(a): NT model lower bound

The proof of the NT lower bound uses an expected-norm estimate, a high-probability kernel-matrix lower bound, and a perturbation argument to complete Proposition 5 under Assumption 5. It also establishes two limits and an o₍d,P₎(1) bound on the operator norm of Δ when k₁ ≥ 2ℓ + 7, under stated activation and Hermite-component conditions.

8.1 Preliminaries

  • Assumption 4 requires a weakly differentiable activation whose derivative has squared growth bounded by c0 exp(c1u^2/2), with c0>0 and c1<1.Assumption 5 requires two nonzero Hermite coefficients of the activation derivative at indices at least 2ℓ+7.Source: §8.1 · p. 36

8.2 Proof of Theorem 2.(a): Outline

  • Under Assumption 4, Proposition 4 bounds the expected norm of V by a constant for ℓ≥1 and d≥6.The constant depends only on the constants in Assumption 4.Source: §8.2 · p. 37
  • For N=o(d^(ℓ+1)), Proposition 5 gives a high-probability lower bound on the NT kernel matrix under Assumptions 4 and 5.The activation must satisfy the integrability condition, and have two nonzero Hermite coefficients at indices k1,k2≥2ℓ+7.Source: §8.1 · p. 36, §8.2 · p. 37

8.4.2 Proof of Proposition 5

  • The Proposition 5 proof decomposes U as U=Û+Ū, with Û positive semidefinite, so U ⪰ Ū; it then seeks a lower bound for Ū.The proof also aims to show that the perturbation matrix Δ has operator norm o_d,P(1) and that D ⪰ εI_Nd with high probability.Source: §8.4.2 · p. 44
  • When k1 ≥ 2ℓ + 7, the proof obtains ∥Δ∥op = o_d,P(1) and proceeds to prove D ⪰ εI_Nd.The passage identifies this as the start of Step 5.Source: §8.4.2 · p. 46
  • Using Eq. (110), the proof establishes that the limits in Eqs. (118) and (119) exist.The passage then sets μk ≡ μk(σ′).Source: §8.4.2 · p. 47
  • Under Assumption 5, ∇F1(0) and ∇F2(0) are nonzero and have nonzero determinant, completing the proof of Proposition 5.These gradient conditions permit a direction v with positive inner products against both gradients, so a sufficiently small δ = δ0v makes F1(δ) and F2(δ) positive.Source: §8.4.2 · pp. 47–48

9 Proof of Theorem 2.(b): NT model upper bound

For targets of degree at most ℓ+1, the proof establishes an NT upper bound by constructing coefficients from an inverse operator on the target’s polynomial subspace. Under the stated neuron-count condition, the NT risk converges to zero in probability.

9 Proof of Theorem 2.(b): NT model upper bound

  • The operator K is diagonalized on the image of the degree-at-most-ℓ+1 polynomial subspace, and Assumption 2.(b) makes its restricted inverse well defined.The proof uses the nonzero Γ_d,k condition for k≤ℓ+1 at sufficiently large d.Source: §9 · p. 49
  • The construction sets α(θ)=K⁻¹T f_d(θ) and a_i=N⁻¹α(θ_i); bounded operator norm and harmonic-polynomial estimates control the resulting NT risk.The diagonal-kernel operator norm is O_d(1), and for fixed k≤ℓ+1 the proof gives Γ_d,k=Ω_d(d).Source: §9 · pp. 49–50
  • For degree-at-most-ℓ+1 targets, the NT risk converges to zero in L1 and therefore in probability when N=ω_d(d^ℓ).The proof assumes the target polynomial degree is at most ℓ+1.Source: §9 · pp. 48, 50

10 Proof of Theorem 4: risk for KR

The proof expresses the empirical kernel ridge regression test error through spherical-harmonic components, then decomposes and bounds its risk terms using auxiliary concentration and perturbation results.

10.1 Proof of Theorem 4

  • The proof rewrites the test error and decomposes the function and kernel matrices using spherical harmonics and Gegenbauer coefficients.It then uses Proposition 3 and Eq. (56) to rewrite the kernels.Source: §10.1 · pp. 50–51

Step 2. Decompose the risk

  • The risk decomposition bounds terms T1–T5 and combines the resulting estimates to finish the proof.The argument uses lemmas and high-probability bounds under the sample-size range ω_d(d^ℓ log d) ≤ n ≤ O_d(d^(ℓ+1−δ)) and Assumption 3.Source: Step 2. Decompose the risk · pp. 53–55

10.2 Auxiliary results

  • When n/(B log B) → ∞, the spherical-harmonic Gram matrix Ψ = Y^T Y/n is close to the identity in operator norm.The proof gives a tail bound for ∥Ψ−I_B∥op and concludes E[∥Δ∥op] = o_d(1).Source: §10.2 · pp. 55–56
  • For a sequence of functions satisfying Assumption 3 and ωd(dℓlog d) ≤ n ≤ Od(dℓ+1−δ), the results establish ∥∆y∥op = od,P(1) and λmin(D1) = ωd(1).Source: §10.2 · pp. 57, 59

A Numerical results with ridge regression

Ridge-regression experiments are consistent with the earlier results: regularization reduces the peak near n≈p but does not change large-n behavior. The paper’s main results predict that RF and NT remain limited by their ability to approximate the target, regardless of how coefficients are estimated.

A Numerical results with ridge regression

  • RF and NT remain limited in approximating f⋆ unless it is a low-degree polynomial, regardless of the coefficient-estimation method.This is the qualitative prediction of Theorem 1 and Theorem 2.(a).Source: A Numerical results with ridge… · p. 64
  • The ridge-regression experiments estimate coefficients from p covariates, with p = N for RF and p = Nd for NT.The design matrix uses σ(⟨w_j, x_i⟩) for RF and (x_i)_j2 σ(⟨w_j1, x_i⟩) for NT.Source: A Numerical results with ridge… · p. 64
  • Regularization reduces the peak at n≈p but does not change the large-n behavior.Figure 8 reports neural tangent model risk for a third-order polynomial target; its settings are d = 30, N = 240 and d = 50, N = 400.Source: A Numerical results with ridge… · pp. 64–65, Figure 8 · p. 65
  • For RF, the d = 100 results are omitted because risk is slightly below baseline R0, an effect that vanishes for d ≳ 100.Source: A Numerical results with ridge… · p. 65

Related papers

Loading 1904.12191v3…