PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks

Blake Bordelon, Abdulkadir Canatar, Cengiz Pehlevan

arXiv:2002.02561v7cs.LGstat.ML

TL;DR

The paper addresses how training-set size and learning-machine properties determine average generalization performance. It derives spectral learning curves for kernel regression using Gaussian-process and statistical-physics methods, then applies them to wide neural networks through the NTK correspondence. The results show successive learning of higher target-function spectral modes as sample size grows, with learning stages for dot-product kernels on high-dimensional hyperspheres and agreement with synthetic-data and MNIST experiments.

  • Problem

    Precisely how training-set size, task complexity, and learning-machine properties affect generalization performance remains a theoretical challenge.

  • Method

    The paper derives average-case spectral learning curves for kernel regression using Gaussian-process approximations and replica methods, then applies them to wide neural networks through kernel equivalence.

  • Results

    As sample size grows, kernel machines and neural networks fit successively higher spectral modes; on high-dimensional hyperspheres, dot-product kernels exhibit distinct learning stages across frequency modes.

  • Takeaways & Limitations

    The kernel eigenspectrum encodes a preferential bias in which higher spectral modes are learned only after the sample size is sufficiently large.

  • Takeaways & Limitations

    The modal dependence on a single target coefficient in the approximate expression is an artifact of the approximation scheme and may not hold in a full treatment.

Abstract

from arXiv · show

We derive analytical expressions for the generalization performance of kernel regression as a function of the number of training samples using theoretical methods from Gaussian processes and statistical physics. Our expressions apply to wide neural networks due to an equivalence between training them and kernel regression with the Neural Tangent Kernel (NTK). By computing the decomposition of the total generalization error due to different spectral components of the kernel, we identify a new spectral principle: as the size of the training set grows, kernel machines and neural networks fit successively higher spectral modes of the target function. When data are sampled from a uniform distribution on a high-dimensional hypersphere, dot product kernels, including NTK, exhibit learning stages where different frequency modes of the target function are learned. We verify our theory with simulations on synthetic data and MNIST dataset.

1. Introduction

The paper develops an average-case theory for kernel-regression generalization and applies it to wide neural networks through their kernel correspondence. Its central result is that the kernel spectrum governs how different target-function modes are learned as training data increases.

  • 1. Introduction: The theory applies to wide neural networks through the equivalence between infinite-width gradient-descent training and kernel interpolation.For the Neural Tangent Kernel, the network architecture enters the learning curves through the kernel spectrum.
  • 1. Introduction: The theory derives analytical learning curves for each spectral component of a target function learned through kernel regression.It uses continuous approximations adapted from Gaussian-process learning curves and independently reproduces the expressions with a replica method and saddle-point approximation.
  • 1. Introduction: For dot-product kernels on uniformly sampled hyperspheres, including NTK, increasing dataset size produces stages in which different frequency modes are learned.In high dimensions, for p ∼ O(d^l), modes with k < l are perfectly learned, modes with k = l are being learned, and modes with k > l are not learned.
  • 1. Introduction: The theory fits kernel-regression experiments remarkably well and provides a good approximation to learning curves for wide finite-width neural networks.The paper reports verification on synthetic datasets and MNIST, while its total-error analysis includes power-law scaling with sample size under specified spectral decays.
  • 1. Introduction: The framework decomposes total generalization error into contributions from different kernel eigenmodes.This decomposition separates the target-dependent modal errors and provides a spectral view of generalization performance.
  • 1. Introduction: Modes with larger RKHS eigenvalues receive a greater percent reduction in generalization error from each marginal training point.The result identifies a rate difference across spectral components rather than treating generalization error as a single undifferentiated quantity.

3. Dot Product Kernels on Sd−1 and NTK

On the hypersphere, dot product kernels such as the NTK have spherical-harmonic spectral modes, and their degeneracies determine staged learning as sample size increases.

  • 3. Dot Product Kernels on S^d−1: Dot product kernels on the unit hypersphere use spherical harmonics Y_km as eigenfunctions, with all N(d, k) degree-k modes sharing eigenvalue λ_k.This degeneracy follows from rotation invariance.
  • 3.1. Frequency Dependence of Learning Curves: For dot product kernels with monotonically decaying spectra, each additional training point reduces relative error more for low-frequency modes than for high-frequency modes.Faster spectral decay strengthens the preference for fitting low frequencies first.
  • 3.1. Frequency Dependence of Learning Curves: With p = αd^ℓ samples in the high-dimensional limit, modes with k < ℓ are perfectly learned, k = ℓ decay asymptotically as 1/α^2, and k > ℓ remain constant.Thus, different frequency modes enter distinct learning stages as sample size grows.
  • 3.1. Frequency Dependence of Learning Curves: Lower modes are learned earlier because higher modes remain stationary until the sample size reaches their degeneracy.The relevant degeneracy scales as N(d, k), while λ_k scales inversely with it in the d → ∞ limit.
  • 3.2. Neural Tangent Kernel and its Spectrum: For fully connected networks at infinite width, the NTK becomes deterministic and approximately fixed during gradient descent, linking neural-network training to ridgeless kernel interpolation.The NTK describes prediction evolution under gradient flow in this regime.
  • 3. Dot Product Kernels on S^d−1: Theoretical NTK learning curves require kernel eigenvalues, which are obtained from Gegenbauer-basis projections evaluated numerically with Gauss–Gegenbauer quadrature.The Gegenbauer basis is tied to the spherical-harmonic decomposition used for the hypersphere analysis.

4. Experiments

Experiments test the spectral learning theory across NTK kernel regression, finite-width neural networks, Gaussian kernels, and MNIST. The results show sequential mode fitting, agreement with theory, and regularization- and dimension-dependent shifts in learning stages.

  • 4.1. NTK Regression and Interpolation: Theoretical NTK mode-error curves show perfect agreement with experiments using a 4-layer fully connected ReLU kernel without bias.The target and student kernels were both NTKs, and mode errors were computed exactly for the synthetic construction.
  • 4.1. NTK Regression and Interpolation: NTK kernel-regression mode errors sequentially begin falling when the sample size p is approximately N(d, k).Higher input dimension shifts learning to larger p, while increasing regularization λ also delays learning.
  • 4.2. Learning Curves for Finite Width Neural Networks: Finite-width neural networks learn lower-degree pure modes with less data, while the k = 2 mode is learned only for p > 200 and k = 4 is not learned in the tested range.The 2-layer experiment used width N = 10000 and d = 30; the 4-layer simulation used 500 hidden units per layer.
  • 4.2. Learning Curves for Finite Width Neural Networks: For composite teacher functions containing multiple spherical-harmonic degrees, neural-network generalization errors agree excellently with the theoretical prediction.The student-teacher setup used ReLU activations with d = 25 and N = 8000.
  • 4.4. MNIST: Discrete Data Measure and Kernel PCA: On 8000 MNIST images, larger-eigenvalue eigenmodes are learned more rapidly as the sample size p increases.The discrete-data procedure obtains eigenvalues and eigenvectors, projects target data onto principal components, and computes learning curves for subsamples.

5. Conclusion

The paper develops an approximate theory of average generalization for kernel regression and uses it to explain spectral learning in infinite- and finite-width neural networks. Experiments support sequential spectral fitting, theory–experiment agreement, and applicability to MNIST.

  • 5. Conclusion: The theory shows that the NTK RKHS eigenspectrum preferentially learns high spectral modes only after the sample size p is sufficiently large.The work studies the ridgeless limit and finds that theoretical infinite-width learning curves approximate wide finite-width neural-network curves.
  • 5. Conclusion: Kernel-regression experiments fit the theoretical learning curves remarkably well, and wide finite-width neural networks are well approximated by the infinite-width predictions.The conclusion also reports that the MNIST result suggests applicability to practically valuable datasets.

1. Background on Kernel Machines

This section introduces RKHS kernels, Mercer eigendecompositions, regularized learning, and the spectral representation used to derive kernel-regression generalization errors. The target and learned functions are expanded in kernel eigenfunctions, enabling mode-wise error analysis.

  • RKHS and Mercer decomposition: A reproducing kernel represents function evaluation as a Hilbert-space inner product and uniquely defines the RKHS kernel.For every function g in the Hilbert space and input x, evaluation at x is represented through the kernel section K(·, x).
  • RKHS and Mercer decomposition: Mercer’s theorem provides an eigendecomposition of the kernel, supplying the eigenvalues and eigenfunctions used for spectral analysis.The RKHS eigenvalues are denoted λρ, and the corresponding kernel functions are used to expand the target.
  • Regularized kernel learning: The regularized learning problem can be represented using dataset coefficients through the representer theorem, reducing optimization to finite-dimensional parameters.For least-squares regression, the objective and optimal prediction can be reformulated in terms of p coefficients αi.
  • Spectral formulation: Hilbert-space orthogonality differs from dataset averaging: ⟨ψρ, ψγ⟩H = δρ,γ, whereas averaged feature products equal λρδρ,γ.The distinction is required to interpret the spectral basis and its normalization correctly.
  • Mode-wise generalization error: The derivation substitutes the training-error minimizer into the generalization error and identifies each mode-wise contribution.The mode errors are obtained by matching the resulting terms to the generalization-error expression.
  • Spectral formulation: The target function and student function are expanded in kernel eigenfunctions, with design matrices and diagonal eigenvalue matrices defining the spectral coordinates.The target expansion uses coefficients wρ, while the design matrices encode eigenfunction evaluations on training samples.

3. Solution of the PDE Using Method of Characteristics

The PDE solution uses characteristics to construct an implicit solution for t(p, v), then evaluates derivatives needed to recover modal generalization errors. The characteristic equations show that t remains constant along the solution curves.

  • Characteristic construction: The PDE is solved by identifying tangent characteristic curves on the solution surface in (t, p, v).The tangent direction is parameterized by s, producing coupled differential equations for t, p, and v.
  • Characteristic equations: Along each characteristic, t is constant while p increases with s and v changes according to λ and t.The characteristic equations are dt/ds = 0, dp/ds = 1, and dv/ds = −1/(λ + t).
  • Solving the PDE: Choosing p0 = 0 identifies s with p and applies the initial condition at s = 0 to obtain an implicit solution for t(p, v).The initial condition is t(0, v) = Tr(Λ^-1 + vI)^-1.
  • Recovering modal errors: The resulting solution establishes Proposition 2, after which the derivation computes modal errors Eρ through differentiation with respect to v at v = 0.The mode errors depend on the relevant diagonal terms because the matrix in the expression is diagonal.
  • Recovering modal errors: Numerically solving for t(p, 0), together with the derived derivative relations, recovers predictions for the modal generalization errors and proves Proposition 3.The result combines equations SI.29, SI.34, and SI.37.

4. Learning Curve for Power Law Spectra

For power-law kernel and target spectra, the total generalization error has sample-size scalings determined by both spectral decay rates and explicit regularization. The analysis identifies distinct asymptotic regimes and notes that slowly decaying kernel spectra produce larger errors.

  • Mode and total errors: Each mode error decays asymptotically as p^-2 for λ > 0, while total error can have nontrivial p-scaling from kernel and target spectra.The total curve therefore need not share the asymptotic scaling of an individual mode.
  • Small-sample regime: For 2b > a − 1, higher-frequency modes dominate at small sample sizes and Eg ∼p^−(a−1).The slow decay of the target power spectrum makes modes k > p the larger error contribution.
  • Small-sample regime: For 2b < a − 1, lower-frequency modes dominate at small sample sizes and Eg ∼p−2b.This regime is controlled by modes k < p.
  • Large-sample regime: At larger sample sizes, the corresponding scalings are Eg ∼p−(a−1)/b when 2b > a − 1 and Eg ∼p−2 when 2b < a − 1.The crossover occurs near p ≈ λ−1/(b−1), separating the small- and large-p regimes.
  • Regularization and kernel choice: Explicit regularization can slow asymptotic error decay, while an RKHS spectrum with exponent b∗ > a−1 is indicated for optimal asymptotics.The analysis concludes that slowly decaying RKHS spectra induce larger errors.
  • Correction: The earlier preprint omitted possible p−2b and p−2 scalings in the ridgeless case before those regimes were corrected.The corrected analysis acknowledges this limitation of the earlier version.

5. Replica Calculation

The replica calculation rederives the continuous-approximation learning-curve expressions using a replica-symmetric saddle-point treatment. Its saddle-point quantity is exactly equivalent to the continuous approximation's t(p, v), and the resulting mode errors agree.

  • Replica formulation: The replica method is used to interpret the continuous approximation as a finite-size saddle-point approximation under a replica-symmetry ansatz.The detailed thermodynamic-limit treatment and replica-symmetric ansatz are reserved for separate work.
  • Replica formulation: The calculation represents the matrix inverse with a Gaussian integral and rewrites it using the replica identity Z−1 = limn→0 Zn−1.The derivation first restricts n to integers before analytically continuing to n → 0.
  • Replica formulation: Averaging over dataset disorder assumes the residual error is a Gaussian process and introduces order parameters Qab = ua·ub.Dirac delta functions enforce the order-parameter definitions before the remaining thermal integrals are evaluated.
  • Saddle point and agreement: At p →∞, the free energy is evaluated at its saddle point, and q∗ is exactly equivalent to t(p, v) from the continuous approximation.The resulting mode-error calculation is consistent with the continuous-approximation result.

6. Spectral Dependence of Learning Curves

This section analyzes how mode errors change as additional samples are added, using spectral structure associated with spherical harmonics on the hypersphere. The calculation connects mode-specific errors to the underlying eigenfunctions and degeneracies.

  • Mode-wise learning: The analysis asks how different mode errors Eρ change when one more training sample is added.The mode error is differentiated with respect to sample size p.
  • Mode-wise learning: The derivative calculation uses γ after identifying the relevant sum, then solves for ∂t/∂p and obtains a negative derivative under the stated ordering.The passage specifies the assumption λγ > λρ without loss of generality.
  • Spherical-harmonic basis: Spherical harmonics are harmonic, homogeneous polynomials that are orthonormal under the uniform measure on Sd−1.Their degree k indexes the spectral frequency, while m indexes members of the degree-k family.
  • Spherical-harmonic basis: The Laplace-Beltrami operator decomposes into radial and angular parts, and spherical harmonics are eigenfunctions of the surface Laplacian.This supplies the geometric spectral basis used for the hypersphere analysis.
  • Spherical-harmonic basis: Spherical harmonics are related to Gegenbauer polynomials, which are orthogonal under the inner-product measure for uniformly sampled pairs on the sphere.The relevant inner product is z = x⊤x′.

8. Decomposition of Dot Product Kernels on Sd−1

For uniformly sampled points on Sd−1, dot-product kernels are decomposed using Gegenbauer polynomials and spherical-harmonic modes. In high dimensions, the resulting learning curves depend on mode degeneracy and the ratio of sample size to degeneracy.

  • Kernel decomposition: Dot-product kernels on uniformly sampled Sd−1 inputs can be decomposed into Gegenbauer polynomials.The polynomial basis is the kernel decomposition used for numerical eigenvalue calculations.
  • Kernel decomposition: Kernel eigenvalues are numerically computed with Gauss-Gegenbauer quadrature using roots zi of Qr(z) and associated weights wi.The calculations use quadrature order r = 1000.
  • High-dimensional limit: In the d →∞ limit, the degeneracy of degree-k modes scales as N(d, k) ∼O(dk), while dot-product kernel eigenvalues scale as λk ∼d−k.The rescaled quantity λ̄k = dkλk is introduced to remain O(1).
  • Learning stages: The relevant sample-to-degeneracy ratio is gk = p/dk, and the analysis probes learning through the ratio Ekm(p)/Ekm(0).An integer l is selected so that the sample-size scaling P = αdl can be studied asymptotically.
  • Learning stages: The asymptotic behavior separates into three regimes for gk, with mode errors obtained after summing over degenerate indices.The mode-error expressions use the rescaled eigenvalues and the auxiliary terms defined in the section.

10. Neural Tangent Kernel

The paper defines the NTK recursively for zero-bias networks and uses its eigenspectrum to analyze mode-dependent generalization and derivative regularity.

  • Neural Tangent Kernel: The NTK is computed recursively from the NNGP kernel for zero-bias networks with nonlinear activation σ.For ReLU activation, the recursion simplifies analytically and is evaluated as a function of z = x⊤x′.
  • Spectra of Fully Connected ReLU NTK: Increasing network depth whitens the fully connected ReLU NTK spectrum, eventually causing λkN(d, k) to diverge.In the infinite-depth limit, the spectrum approaches λkN(d, k) ∼1, and the kernel becomes nonanalytic at the origin.
  • Spectra of Fully Connected ReLU NTK: The condition λkN(d, k) ∼O(k−n−1/2) implies finite variance for the n-th gradient.This links eigenspectrum decay to the regularity of functions in the associated RKHS.
  • Spectral analysis: The kernel eigenspectrum determines the spectral components used to calculate generalization error and mode errors.The teacher function is expanded in kernel eigenfunctions, whose coefficients enter the mode-error calculation.
  • Spectral analysis: The student function is represented by kernel basis functions, with coefficients obtained by fitting α = (K + λI)−1y to training data.These coefficients are then used to obtain empirical mode errors.

13. Neural Network Experiments

The experiments test theoretical learning curves on pure-mode and composite neural-network targets, comparing finite-width networks with NTK and theory predictions.

  • Neural Network Experiments: Pure-mode experiments use neural-network targets, while composite experiments use a randomly sampled two-layer ReLU teacher network.The composite target is a special case of the teacher-function form used to derive theoretical learning curves.
  • Neural Network Experiments: The experiments compute theoretical curves by expanding the teacher network in Gegenbauer polynomials and determining its spectral weights.The required expansion is computed with equation (SI.37).
  • Neural Network Experiments: The reported experiments include training and generalization errors from pure-mode targets, with learning curves also evaluated on student-teacher experiments.Figures SI.3 and SI.4 provide representative training-error and learning-curve results.
  • Neural Network Experiments: 500 hidden units per layer and p = 500 are used for the pure-mode training-error experiment.The figure compares training dynamics across different pure frequency modes.
  • Neural Network Experiments: Higher frequencies k ≥4 train more slowly than low-frequency modes, which show an initial rapid reduction in training error.This is the qualitative pattern reported for the pure-mode experiment.
  • Neural Network Experiments: Figure SI.4 compares theory curves with finite-width neural-network and NTK test errors, using solid lines, dots, and triangles respectively.Logarithms in the figure are evaluated with base 10.
Loading 2002.02561v7…