PaperlayerView exact revision on arXiv

Source-linked AI summary

When Do Neural Networks Outperform Kernel Methods?

Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari

arXiv:2006.13409v2stat.MLcs.LGmath.ST

TL;DR

The paper asks when neural networks genuinely outperform RKHS methods despite wide-network linearizations and mixed empirical evidence. It develops the spiked covariates model to characterize the role of aligned low-dimensional structure, then tests the resulting prediction on perturbed images. The main result is a continuum: RKHS methods are more competitive when covariate and target structure align, but can be highly suboptimal for fully high-dimensional covariates.

  • Problem

    The paper addresses the lack of a unified explanation for empirical cases where RKHS methods match neural networks and theoretical cases where neural networks outperform them.

  • Method

    The paper introduces the spiked covariates model, combining low-dimensional target projections with approximately low-dimensional covariates, and analyzes associated RKHS and neural-network methods.

  • Results

    RKHS methods range from highly suboptimal to competitive with neural networks depending on covariate signal-to-noise ratio, signal dimension, and ambient dimension; image perturbations widen the NN–RKHS gap.

  • Takeaways & Limitations

    Neural networks outperform RKHS methods most strongly when targets depend on low-dimensional projections but covariates remain nearly isotropic.

  • Takeaways & Limitations

    The spiked covariates model is highly stylized, whereas real-image latent structure is expected to be nonlinear, such as wavelet-domain sparsity.

Abstract

from arXiv · show

For a certain scaling of the initialization of stochastic gradient descent (SGD), wide neural networks (NN) have been shown to be well approximated by reproducing kernel Hilbert space (RKHS) methods. Recent empirical work showed that, for some classification tasks, RKHS methods can replace NNs without a large loss in performance. On the other hand, two-layers NNs are known to encode richer smoothness classes than RKHS and we know of special examples for which SGD-trained NN provably outperform RKHS. This is true even in the wide network limit, for a different scaling of the initialization. How can we reconcile the above claims? For which tasks do NNs outperform RKHS? If covariates are nearly isotropic, RKHS methods suffer from the curse of dimensionality, while NNs can overcome it by learning the best low-dimensional representation. Here we show that this curse of dimensionality becomes milder if the covariates display the same low-dimensional structure as the target function, and we precisely characterize this tradeoff. Building on these results, we present the spiked covariates model that can capture in a unified framework both behaviors observed in earlier work. We hypothesize that such a latent low-dimensional structure is present in image classification. We test numerically this hypothesis by showing that specific perturbations of the training distribution degrade the performances of RKHS methods much more significantly than NNs.

1 Introduction

The paper reconciles empirical and theoretical differences between neural networks and RKHS methods through alignment between target and covariate low-dimensional structure. It introduces the spiked covariates model and tests its predictions on perturbed image data.

  • Linearized networks: In the lazy regime, suitably scaled wide-network SGD is approximately described by linear random-feature or neural-tangent classes related to RKHS methods.The approximation follows from a first-order Taylor expansion around the randomly initialized input-layer weights.
  • Prior results: Prior work found both small empirical NN–kernel gaps and theoretical examples where neural networks outperform their associated RKHS methods.A single-neuron target can be learned efficiently by a neural network but remains poorly learned by the corresponding RKHS for polynomial sample sizes.
  • Spiked covariates model: The proposed spiked covariates model combines low-dimensional target dependence with approximately low-dimensional covariates.Targets have the form f∗(x) = ϕ(U Tx), while covariates decompose into signal and noise subspaces.
  • Image experiment: Adding noise to high-frequency image components makes the covariate distribution more isotropic and causes RF, NT, and RKHS methods to deteriorate faster than NNs.The experiment uses Fashion MNIST with d = 784, n = 60000, and 10 classes, comparing matched-parameter finite-width models and infinite-width KRR.
  • Main characterization: RKHS performance improves when covariate structure aligns with the target’s low-dimensional structure, with the tradeoff governed by covariates SNR, signal dimension d0, and ambient dimension d.When covariates are fully d-dimensional, RKHS methods can be highly suboptimal; when they approach d0 dimensions, they become more competitive with NNs.
  • Scope: The spiked covariates model is highly stylized, because real-image latent structure is expected to be nonlinear, such as sparsity in the wavelet domain.The authors present the model as capturing two basic mechanisms and providing qualitative predictions rather than a complete image model.

2 Rigorous results for kernel methods and NT, RF NN expansions

The paper analyzes how a shared low-dimensional structure in covariates and targets changes RKHS, RF, NT, and NN performance. An effective dimension governs kernel sample complexity and finite-width approximation, while NN approximation can remain independent of covariate anisotropy.

  • Spiked covariates model: The spiked-covariates model separates a low-dimensional signal subspace of dimension d0=d^η from a noise subspace, with signal-to-noise ratio r=d^κ/2.Targets depend only on the signal projection, and the analysis uses rotationally invariant kernels with uniformly spherical input weights.
  • RKHS methods: The effective dimension deff=d^max(1−κ,η) characterizes how covariate structure affects KRR sample complexity.For κ≈0, deff≈d and the setting is nearly isotropic; for κ>1−η, deff=d^η=d0 and KRR behaves as if the signal subspace were known.
  • Finite-width RF and NT: For RF and NT, the same effective dimension controls the number of neurons needed to approximate degree-ℓ polynomials, with RF requiring N≫d^ℓ.The finite-width analysis treats approximation error in the infinite-sample setting and extends the kernel characterization to these linearizations.
  • Finite-width RF and NT: NT has greater approximation power than RF per neuron but lower power per parameter because NT contains Nd rather than N parameters.The comparison reflects the different parameterizations of the two linearized models.
  • Neural network models: NNs separate from uniformly sampled NT models when deff≠d0, and the gap shrinks as κ increases until κ=1−η.The NN approximation error is independent of κ≥0, while its bound is related to approximation on the low-dimensional signal sphere.

3 Further numerical experiments

Numerical experiments compare NN, RF, NT, and KRR across synthetic and image data. They find that NN approximations are stronger on synthetic targets, while frequency perturbations separate neural networks from corresponding kernel methods.

  • Synthetic data: NN provides much better approximations than RF and NT, while RF is superior to NT at the same parameter count.The synthetic experiment uses d=1024, latent dimension d0=16, and degree-4 polynomial targets.
  • Synthetic data: As κ increases, RF and NT approximation errors decrease, whereas NN error is smaller in absolute terms and much less sensitive to κ.The RF and NT curves approximately collapse after rescaling by effective dimension.
  • Synthetic data: KRR test error is substantially larger than NN error and deteriorates rapidly as κ decreases, when effective dimension increases.Rescaling observations by effective dimension approximately collapses the KRR curves across κ.
  • Image data: Removing low-frequency structure from images tests whether kernel methods are more sensitive than neural networks to perturbations of the covariate distribution.The perturbation adds noise to the high-frequency image component in one experiment and removes low-frequency structure in the complementary experiment.
  • Image data: In image experiments, progressively perturbing Fourier modes produces the same qualitative separation between neural networks and corresponding NT kernel methods.The comparison includes fully connected networks on FMNIST and a convolutional network versus CNTK KRR on CIFAR-10.

4 Discussion

The discussion places the results in high-dimensional nonparametric estimation and introduces a spiked-covariate perspective. Kernel performance depends on how closely low-dimensional structure in covariates aligns with low-dimensional structure in the target.

  • High-dimensional estimation: Classical Sobolev estimation results require roughly ε^(-2-d/α) samples for mean square error ε, illustrating the curse of dimensionality for kernel methods.These results concern fixed d with sample size n diverging and need not describe specific functions.
  • High-dimensional estimation: The paper characterizes test error when both d and n diverge polynomially, for arbitrary target functions, using their polynomial decomposition.Analogous results are also given for finite-width RF and NT models.
  • Spiked covariates: The spiked covariates model assumes covariates concentrate near a d0-dimensional signal subspace, with the target depending on that same subspace.It generalizes analyses based on uniformly spherical covariates.
  • Spiked covariates: RKHS methods are highly suboptimal when covariates are fully d-dimensional, but become more competitive when covariates are close to d0-dimensional.The continuum depends on signal dimension d0, ambient dimension d, and covariate signal-to-noise ratio r.

A.2 Synthetic data experiments

The experiments compare NN, NT, and RF models on synthetic and image data, testing how covariate anisotropy and frequency-target alignment affect relative performance. Adding high-frequency noise makes covariates more isotropic and widens the NN advantage over RKHS methods, especially on CIFAR-2.

  • Noise construction: High-frequency noise is added to training and test images to make covariate distributions more isotropic while preserving low-frequency components.Images are transformed with DCT, noise is applied through a binary frequency filter, and inverse DCT produces the perturbed images.
  • FMNIST covariance: As high-frequency noise increases, empirical covariance eigenvalues become more isotropic, although conservative filtering leaves some low-variance directions unperturbed.This experiment directly measures how the perturbation changes the covariance spectrum.
  • Evaluation: The experiments report normalized test squared error and test accuracy for models trained and evaluated under high-frequency image noise.The stated normalization for FMNIST uses the risk of a trivial predictor as reference.
  • CIFAR-2 results: On CIFAR-2, the NN–NT KRR accuracy gap grows from 0.6% at τ = 0 to 4.5% at τ = 3.All models perform comparably without noise, but the gap widens as the perturbation increases; CIFAR-2 uses grayscale images with d = 1024.
  • Noise construction: The FMNIST filter retains over 95% of the training-data variation in the selected low-frequency region.The filter excludes low-frequency noise and targets high-frequency directions associated with smaller-variance components.

C.5 Approximation error of the random features model

The random-features analysis characterizes which polynomial subspaces are fit at width N = d^γ under activation-function assumptions. It identifies effective dimensions that determine how latent structure affects approximation and separates RF and NT behavior from unsupported components.

  • Assumptions: The theorem assumes activation derivatives have controlled Gaussian growth and nonzero relevant coefficients, with separate conditions for lower- and higher-width regimes.These assumptions constrain the activation function used in the approximation guarantees.
  • Functional-space decomposition: At width N = d^γ, RF fits a low-degree polynomial subspace F(β, κ, γ) but cannot fit its complementary subspace F_c(β, κ, γ).The decomposition is stated for γ outside the specified exceptional set.
  • Functional-space decomposition: The corresponding NT model also fits F(β, κ, γ) and cannot fit the complementary subspace at N = d^γ.This establishes the analogous representational split for the neural-tangent model.
  • Effective dimension: Each sphere component has effective dimension d_q,eff = d^(ξ−κ_q), reflecting the extra width required to capture weaker dependencies.For components with η_q + κ_q < ξ, the analysis derives the effective dimension from reduced signal strength.

C.6 Approximation error of the neural tangent model

The neural tangent model approximates functions through degree-indexed polynomial subspaces whose accessible components depend on width scaling and covariate structure. In the two-spheres setting, the approximated degree ranges differ across KRR, random features, and NT models.

  • General approximation structure: For N=d^γ, the NT model fits the low-degree polynomial subspace F(β, κ, γ) but cannot fit its complement F^c(β, κ, γ).The functional space decomposes into an approximable component and a component excluded by the width-dependent regime.
  • General approximation structure: The accessible NT degrees satisfy a width-dependent condition involving β = ξ − min_{q∈S(k)} κ_q.Here S(k) indexes spheres with positive degree components.
  • Two-spheres specialization: In the two-spheres model, KRR approximates first-sphere polynomials with d_eff^k ≤ d^γ, where d_eff = d^max(η,1−κ) for targets depending only on the first sphere.The result applies when the sample size lies in the stated width-dependent range.
  • Two-spheres specialization: In the same specialization, random features approximate first-sphere polynomials satisfying d_eff^k ≤ d^γ.The cited theorem identifies the accessible polynomial subspace for finite-width random features.

D.2 Proof of Theorem 5

The proof of Theorem 5 decomposes functions and kernel matrices into tensor-product spherical-harmonic components, then controls the resulting risk terms using spectral bounds and concentration.

  • Proof organization: The proof rewrites the target, error, kernel, and auxiliary matrices in harmonic components before decomposing the risk.The spherical-harmonic and Gegenbauer decompositions organize the analysis by multi-degree.
  • Spectral decomposition: The kernel analysis uses tensor-product Gegenbauer expansions and the associated orthogonal basis on the product of normalized spheres.These expansions identify the degree-indexed blocks used throughout the proof.
  • Risk bounds: The resulting test-error control includes a term T5 that is o_d,P(1) times τ(∥P_Q f_d∥_L2 + ∥P_Qc f_d∥_L2).This term appears in the final aggregation of the risk decomposition.
  • Risk bounds: The proof bounds individual risk terms using matrix concentration, operator-norm estimates, Cauchy–Schwarz, and Markov’s inequality.The argument combines these bounds across terms T1 through T5 to finish the theorem.
  • Spectral control: Lemma 4 supplies high- and low-component spectral scales, with κ_h = Θ_d(1), κ_m = O_d(d^-m(γ)), and controlled perturbation operators.These bounds support the later risk estimates.

E.2 Proof of Theorem 6.(a): Outline

The proof outline for Theorem 6(a) constructs activation and kernel decompositions to isolate the random-features subspace and control the complementary component.

  • High-probability control: The proof establishes high-probability bounds for the random matrix and associated vectors before combining them with the risk decomposition.The intermediate propositions provide expected-norm and kernel-matrix controls.
  • Risk decomposition: The random-features risk is rewritten using a decomposition into the subspaces Q and Q^c.The notation suppresses the dependence on the random weights while separating approximable and non-approximable components.
  • Conclusion: The outline concludes by combining the constructed activation, kernel comparison, and concentration bounds to obtain the theorem.The final step is explicitly stated after the preceding estimates.
  • Activation construction: The proof expands the activation in tensor-product Gegenbauer polynomials and uses these coefficients to construct specialized activation functions.The constructed functions isolate selected polynomial degrees and coordinates.
  • Kernel comparison: The kernels u_d, û_d, and ū_d are positive semidefinite, and U ⪰ ūU provides a lower bound for the kernel matrix.The comparison reduces the analysis to lower-bounding the simpler component ūU.

F Proof of Theorem 6.(b): upper bound for RF model

The RF upper-bound proof defines operator representations for feature maps, analyzes their limiting kernel, and controls the resulting harmonic components to bound approximation error.

  • Degree-wise control: For degrees in Q, the operator bounds control the feature contribution uniformly over the restricted τ parameters.The argument uses the activation assumptions and degree-dependent coefficient bounds.
  • Operator formulation: The proof defines T_τ and its adjoint, then represents the limiting kernel as K_{τ,τ′} = T_τ T*_{τ′}.The operator formulation connects feature representations to the limiting kernel.
  • Harmonic representation: The limiting-kernel analysis uses the Gegenbauer decomposition of the activation and an orthonormal basis indexed by multi-degrees and basis elements.This makes the kernel action blockwise in the harmonic representation.
  • Risk expansion: The proof expands the squared loss around a selected coefficient vector and separately bounds diagonal, off-diagonal, and remaining terms.The expansion is applied to the RF risk under the restricted parameter event.
  • Conclusion: The proof combines these estimates with concentration and the assumption N = ω_d(d^γ) to conclude the upper bound.The final conclusion invokes the high-probability event established earlier.

G.2 Proof of Theorem 7.(a): Outline

The proof treats the NT model like the RF case, decomposing its kernel matrix into structured blocks and controlling diagonal and perturbation terms.

  • The NT-model proof follows the RF proof structure but requires additional work.
  • The proof defines block-structured random vectors and kernel matrices for the NT model.
  • Two propositions provide expected-norm and kernel-matrix lower-bound controls used in the argument.
  • The kernel matrix is decomposed as a block-diagonal matrix plus a perturbation.
  • With high probability, the diagonal blocks remain well conditioned while the perturbation has smaller operator norm.
  • Combining these bounds yields the target equation and completes the theorem’s proof.

H.2 Proof of Theorem 7.(b): outline

The proof of Theorem 7(b) analyzes NT risk through sphere-restricted submodels, limiting kernels, and Gegenbauer-based decompositions.

  • The NT model is partitioned into Q sphere-restricted subclasses, and each restricted risk is defined by an infimum over its function class.
  • The full NT risk is bounded using the risks of these restricted submodels.
  • A limiting kernel serves as a proxy for upper-bounding the restricted NT risk.
  • The associated operators are constructed as Tτ and Kτ,τ′ = TτTτ′* on the relevant function spaces.
  • The proof uses orthogonal Gegenbauer bases to diagonalize the relevant kernel operator.
  • Expanding the risk around its optimizer separates diagonal and nondiagonal terms before concentration bounds complete the argument.

I Proof of Theorem 4 in the main text

The theorem proof compares neural-network and neural-tangent representations for low-dimensional target functions and establishes risk invariance under covariate scale changes.

  • For targets of the form f*(x) = ϕ(U^T x), the proof restricts neuron weights to the target’s d0-dimensional representation.
  • A Taylor expansion relates neural-network functions to neural-tangent models, allowing the NN class to control an NT approximation error.
  • The NT model on the representation space Rd0 is used as a comparison class.
  • The NN risk is independent of the covariate scale parameter κ.
  • The high-dimensional spherical coordinates are coupled to Gaussian variables to obtain asymptotic coefficient and norm controls.
  • Gegenbauer expansions and their coefficient asymptotics provide the spectral ingredients for the proof.

J.2 Proof of convergence in probability of the Gegenbauer coefficients

This section establishes convergence of Gegenbauer coefficients and controls the associated Gram matrices under smoothness and growth assumptions on the activation.

  • The coefficient results assume weak differentiability of the activation and sub-Gaussian-type exponential growth bounds on its derivatives.
  • Under these assumptions, the Gegenbauer coefficients converge with high-dimensional scaling for τ near the unit vector.
  • The proof derives coefficient formulas using Rodrigues’ formula and the Gegenbauer–Hermite correspondence.
  • The dominant coordinate is selected by maximizing ηq + κq, with the first sphere chosen as the unique maximizer without loss of generality.
  • The Gram-matrix argument combines blockwise estimates, Hadamard-product bounds, and asymptotic scaling relations.
  • Uniform Gram-matrix control is obtained for sample sizes satisfying n ≤ d^γ/e^A_d.

K.1 Proof of Proposition 5

The proof bounds an operator norm by organizing index sequences into graph-based equivalence classes and reducing them through skeletonization. It separately controls type 1 and type 2 sequences before selecting parameters that make the expected operator-norm error vanish.

  • Proof setup: The proof begins by bounding the operator norm through moments and grouping index sequences according to isomorphic associated multigraphs.Equivalent sequences receive the same corresponding value, while sequences outside T⋆(p) contribute zero.
  • Proof setup: The graph lemmas ensure that contributing sequences have even vertex degrees, at most (2p)2p equivalence classes, and bounded class sizes.The class-size bound depends on the number of distinct vertices v(i).
  • Skeletonization: Skeletonization repeatedly removes degree-2 vertices, producing an order-independent skeleton whose nontrivial vertices all have degree at least 4.Sequences are classified as type 1 when the skeleton has one index and type 2 otherwise.
  • Type 1 sequences: For type 1 sequences, every graph edge has multiplicity at most two, implying the lower bound min_i∈T1 v(i) = p + 1.The proof then combines this structural bound with equivalence-class counting and lower bounds on B(dq, kq).
  • Conclusion: Setting n = d^K e^-2A√log d and p = (K/A)√log d yields E[∥∆∥op] → 0 as A → ∞.The chosen p also satisfies p = o(d) and the required condition for sufficiently large d.
Loading 2006.13409v2…