Source-linked AI summary
Linearized two-layers neural networks in high dimension
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari
TL;DR
The paper studies prediction with neural-network linearizations and asks how finite width and sample size constrain learnable functions in high dimensions. It shows that these models effectively fit low-degree polynomials, while kernel ridge regression attains the sample-limited optimum with vanishing regularization.
Problem
The canonical learning problem is to construct a predictor from i.i.d. feature-response pairs and evaluate it by square prediction error.
Method
The analysis characterizes random features and neural tangent models through their effective polynomial degree and examines kernel ridge regression with rotationally invariant kernels.
Results
For d^ℓ+δ ≤ n ≤ d^ℓ+1−δ, kernel methods cannot fit beyond degree ℓ, while ideal kernel ridge regression behavior is achieved for λ ≤ λ* and near-zero regularization.
Takeaways & Limitations
In the sample-limited regime, near-interpolating kernel ridge regression achieves the ideal prediction behavior despite negligible training error.
Takeaways & Limitations
The analysis includes polynomial targets of degree at most ℓ and suggests improvements when the target or data concentrate in a low-dimensional subspace.
Abstract
from arXiv · showhide
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 analyzes high-dimensional random-features and neural-tangent models as linearized two-layer networks, focusing on their approximation and generalization limits. It shows that finite-width models behave like low-degree polynomial regression, while finite-sample rotationally invariant kernel methods face analogous degree limits.
- Models: RF and NT are first-order Taylor-linearized two-layer neural-network models around random initialization.RF fixes the first layer and optimizes second-layer coefficients; NT expands with respect to first-layer weights.
- Contributions: The analysis provides sharp asymptotic results with polynomial dependence on d and pointwise characterization of approximation and generalization error.This regime is intended to capture behavior when both dimension and model size are large.
- Separation from neural networks: Finite-width RF and NT can fail on simple targets, while neural networks with O(d) neurons can achieve small approximation error for quadratic and third-order polynomials.The numerical study reports cases where RF or NT do not beat the trivial predictor, whereas tailored neural-network weights yield substantially lower risk.
- Approximation error: For d^(ℓ+δ) ≤ N ≤ d^(ℓ+1−δ), RF is equivalent to fitting monomials of degree at most ℓ, whereas NT reaches degree at most ℓ+1.These approximation equivalences hold pointwise for the target function f⋆.
- Generalization error: For n ≤ d^(ℓ+1−δ), any kernel method has generalization error at least the approximation error of degree-ℓ polynomial regression.This establishes a pointwise lower bound for rotationally invariant kernel methods in the sample-limited regime.
- Generalization error: For d^(ℓ+δ) ≤ n ≤ d^(ℓ+1−δ), kernel ridge regression achieves the degree-ℓ polynomial approximation error.The ideal behavior is attained for all regularization values λ ≤ λ∗, including near-interpolating choices with λ ≈ 0.
2 Approximation error of linearized neural networks
The results characterize RF and NT approximation error in high dimension through polynomial projections, under explicit scaling and activation assumptions. They also establish separation from neural networks and identify computational and structural implications.
- RF approximation error: RF is equivalent to fitting monomials up to degree ℓ when d^ℓ ≪ N ≪ d^(ℓ+1−δ).Its approximation error decomposes into low-degree RF risk and the residual beyond degree ℓ.
- Assumptions: The conclusions require activation-function conditions, including weak differentiability and growth or Hermite-coefficient assumptions for the RF and NT analyses.The RF result also requires nonzero relevant Hermite coefficients and excludes activations that are polynomials of degree below ℓ.
- Statistical insights: RF and NT approximation error follows a staircase in log(number of parameters)/log d, with drops corresponding to polynomial degrees.The models behave similarly to expansions into orthogonal monomial bases when fewer than d^(ℓ+1) basis elements are included.
- Statistical insights: At fixed parameter count, RF and NT have no approximation-error difference, but NT has prediction complexity O(p) versus O(pd) for RF.The parameter relations are p=N for RF and p=Nd for NT.
- Statistical insights: The results suggest gains from sampling random features in a low-dimensional relevant subspace when the target or data concentrates there.The proposed low-dimensional sensitivity is identified as a direction for future work.
- Separation from NN: A single-neuron target can be represented exactly by a neural network but has non-vanishing RF and NT error in intermediate neuron regimes.This yields a separation between linearized networks and neural networks trained by gradient descent.
3 Generalization error of kernel methods
In the wide-network limit, RF and NT become kernel ridge regression with rotationally invariant kernels. When samples scale between adjacent powers of d, kernel methods are limited to low-degree polynomial structure, while KRR attains the corresponding lower bound.
- Wide-network limit: N →∞ before n, d →∞ makes RF ridge regression converge to kernel ridge regression, and NT ridge regression converges analogously to KRR.The corresponding RKHSs are denoted HRF and HNT.
- Rotationally invariant kernels: Both RF and NT kernels are rotationally invariant on the sphere.Rotational invariance means the kernel is unchanged under orthogonal transformations of its inputs.
- Lower bound: Theorem 3 decomposes kernel-method generalization error with the sample size n, rather than the neuron count N, as the controlling factor.The result assumes n is below approximately d^(ℓ+1), subject to the stated asymptotic condition.
- Lower bound: n between approximately d^ℓ and d^(ℓ+1) leaves every kernel method with test error bounded away from zero.This establishes a pointwise lower bound in the high-dimensional sample-size-limited regime.
- Kernel ridge regression: Any λ < λ∗ achieves optimal test error, including the λ →0 interpolating limit.Thus interpolation can attain the same optimal prediction error under the theorem’s assumptions.
- Kernel conditions: For kernels whose first ℓ derivatives at zero are positive, the required eigenvalue condition holds and λ∗ remains bounded away from zero.For dimension-independent activations, a sufficient condition is nonzero Hermite coefficients through degree ℓ.
- Motivation: Classical minimax rates would require n exponential in d for fixed small error, motivating the polynomial-sample regime studied here.The paper frames the question as the minimum prediction error achievable when n ≍ d^α.
- Kernel ridge regression: Kernel ridge regression achieves the lower-bound test error and is therefore near-optimal pointwise for each target function.Its predictor is close in L2 to the target’s low-degree approximation P≤ℓfd.
4 Further related work
Related work studies high-dimensional kernel limitations, RF polynomial learning, and mean-field alternatives, but differs in asymptotic regime, target assumptions, or model dynamics.
- Kernel methods: El Karoui’s proportional-asymptotic analysis approximates kernel matrices by a raw-feature Gram matrix plus a diagonal term.The present theorems address broader polynomial sample-size regimes beyond n ∝ d.
- Random features: Vempala and Wilmes show RF can learn degree-ℓ polynomials with d^O(ℓ) samples and neurons, while this paper gives sharper exponents.Their statistical-query lower bound requires at least d^Ω(ℓ) queries, but the settings are not directly comparable.
- Kernel ridge regression: Liang, Rakhlin, and Zhai study KRR with polynomially many samples under bounded RKHS-norm targets, whereas this paper proves pointwise lower bounds.The distinction concerns the target-function assumption and the form of the guarantee.
- Mean-field theory: Mean-field analyses describe weight evolution beyond the linear regime, unlike the neural tangent approach.The cited works provide an alternative framework for analyzing wide two-layer neural networks.
5 Technical background
The paper develops spherical-harmonic and orthogonal-polynomial tools for analyzing rotationally invariant kernels and high-dimensional neural-network limits.
- Spherical harmonics: Functions on the sphere are decomposed into orthogonal spaces of spherical harmonics indexed by polynomial degree.The spaces Vd,ℓ consist of restrictions of homogeneous harmonic polynomials of degree ℓ.
- Spherical harmonics: The projection Pk extracts the degree-k spherical-harmonic component of a function.The Gegenbauer polynomial Q^(d)_k represents the corresponding projector kernel.
- Rotationally invariant kernels: Rotational invariance makes each degree-k polynomial space an eigenspace of the kernel operator, with eigenvalue ξd,k(hd).This spectral structure is the basis for degree-wise generalization analysis.
- Polynomial limits: Gegenbauer polynomials converge to Hermite polynomials in the high-dimensional limit after the appropriate domain scaling.Both arise by orthogonalizing monomials under their respective limiting measures.
- Asymptotic notation: The notation O_d,P and o_d,P denotes big-O and little-o convergence in probability, with tildes hiding logarithmic factors.These conventions track the high-dimensional asymptotics used throughout the proofs.
6 Proof of Theorem 1.(a): RF model lower bound
The RF lower-bound proof decomposes random features by spherical-harmonic degree and controls the higher-degree component through random Gram-matrix operator norms.
- Feature decomposition: The random feature vector is decomposed into degree-at-most-ℓ and degree-greater-than-ℓ components.The risk analysis then uses orthogonality between these components.
- Feature decomposition: Proposition 1 controls the expected norm of the degree components of the random-feature representation.The activation is expanded in the Gegenbauer basis, whose coefficients determine the contribution of each degree.
- Kernel-matrix control: Proposition 2 lower-bounds the random-feature kernel matrix when N is below the next harmonic-dimension scale.The proof expands the matrix into Gegenbauer-degree components and bounds the higher-degree remainder.
- Harmonic dimensions: The number B(d,k) of independent degree-k spherical harmonics is non-decreasing in k.This monotonicity supports the comparison B(d,ℓ+1)=Θ_d(d^(ℓ+1)) used in the proof.
- Kernel-matrix control: The operator-norm remainder vanishes with high probability under the chosen moment order and asymptotic scaling.The proof concludes from the moment estimates that E[||Δ||op] tends to zero.
- Moment method: Moment bounds organize index sequences by isomorphic induced multigraphs and eliminate sequences whose graph contains incompatible structures.Equivalent sequences share moments, while noncontributing sequences have zero moment or even-degree graph constraints.
- Moment method: Skeletonization removes redundant degree-2 vertices from index-sequence graphs while preserving the relevant equivalence structure.The resulting skeleton is either a singleton or has all vertex degrees at least four.
7 Proof of Theorem 1.(b): RF model upper bound
The proof analyzes random features through operators diagonalized by spherical harmonics and constructs coefficients that yield vanishing risk for degree-ℓ polynomial targets when N grows faster than d^ℓ.
- The target sequence is assumed to consist of polynomials of degree at most ℓ.
- The operator K=TT* preserves the degree-≤ℓ polynomial subspace and is invertible there for sufficiently large d.
- Choosing coefficients from α(θ)=K^-1T f_d provides the random-features parameters used in the risk analysis.
- When N=ω_d(d^ℓ), the RF risk converges to zero in L1 and therefore in probability.
8 Proof of Theorem 2.(a): NT model lower bound
The NT lower-bound proof decomposes the model into harmonic components and controls the associated random block kernel matrix under activation-function assumptions.
- The proof assumes integrability of σ and nonzero Hermite components of σ′ at two levels k1,k2≥2ℓ+7.
- The NT construction introduces vector-valued features and a block kernel matrix U indexed by the random initialization directions.
- Proposition 4 bounds the expected norm of the feature vector under the activation integrability condition.
- For N=o_d(d^(ℓ+1)), Proposition 5 establishes a high-probability lower bound on the NT kernel matrix.
- The proof constructs a truncated activation and decomposes U into a positive-semidefinite component plus a residual matrix for lower bounding.
9 Proof of Theorem 2.(b): NT model upper bound
The NT upper-bound proof restricts the kernel to the image of low-degree polynomials, establishes invertibility of its harmonic components, and uses this structure to show vanishing risk.
- The proof assumes targets are polynomials of degree at most ℓ+1 and studies T(V_d,≤ℓ+1).
- A spherical-harmonic basis diagonalizes K on T(V_d,≤ℓ+1).
- Under Assumption 2.(b), Γ_d,k is nonzero for every k≤ℓ+1 at sufficiently large d, so the restricted inverse is well defined.
- The NT coefficients are chosen using α(θ)=K^-1T f_d, and the risk is analyzed in expectation over the initialization.
- When N=ω_d(d^ℓ), the NT risk converges to zero in L1 and hence in probability.
10 Proof of Theorem 4: risk for KR
The kernel-ridge proof decomposes empirical quantities into spherical-harmonic components and controls their deviations in the sample-size range used for the risk analysis.
- The proof rewrites the test error of empirical kernel ridge regression using harmonic decompositions of the target and kernel-related matrices.
- The feature matrix Y collects spherical harmonics through degree ℓ, with B columns representing the corresponding basis dimension.
- If n/(B log B)→∞, the harmonic-feature Gram matrix concentrates sufficiently for the subsequent bounds.
- Matrix Bernstein concentration controls the empirical Gram matrix Ψ=Y^T Y/n around the identity.
- For ω_d(d^ℓ log d)≤n≤O_d(d^(ℓ+1−δ)), the perturbation terms are controlled, including operator-norm errors that are o_d,P(1).
A Numerical results with ridge regression
Ridge-regression experiments reproduce the earlier qualitative behavior of RF and NT models. Regularization reduces the peak near n ≈ p but does not improve their large-sample behavior, consistent with the models' approximation limitations.
- Ridge-regression experiments: Changing coefficient estimation to ridge regression does not qualitatively alter the RF and NT results.The experiments use p = N covariates for RF and p = Nd covariates for NT.
- Ridge-regression experiments: Regularization reduces the risk peak near n ≈ p but does not improve large-n behavior.The reported results are consistent with the earlier experiments.
- Numerical settings: Figure 8 evaluates neural tangent risk when learning a third-order polynomial, using d = 30, N = 240 and d = 50, N = 400.The left and right frames use these two dimension-width settings, respectively.
- Numerical settings: For RF, results at d = 100 are omitted because the risk is slightly below the baseline R0, an effect that vanishes for d ≳ 100.This omission applies to Figure 6.