PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks

Abdulkadir Canatar, Blake Bordelon, Cengiz Pehlevan

arXiv:2006.13198v6stat.MLcond-mat.dis-nncs.LG

TL;DR

The paper addresses the difficulty of predicting generalization, including why overparameterized neural networks can generalize despite classical expectations. It derives a statistical-mechanics theory for kernel regression and applies it across kernels and datasets. The results identify spectral task-model alignment as a determinant of sample efficiency and show that noise or kernel-inexpressible targets can make generalization non-monotonic.

  • Problem

    Existing theories struggle to predict generalization on real data, while overparameterized neural networks generalize well despite classical overfitting expectations.

  • Method

    The paper uses statistical mechanics to derive an analytical kernel-regression generalization theory applicable to any kernel and dataset, with detailed analysis of rotation-invariant kernels.

  • Results

    Task-model alignment determines sample requirements: targets concentrated in top eigenmodes can be learned sample-efficiently, while noisy or inexpressible targets can yield non-monotonic error.

  • Takeaways & Limitations

    Kernel compatibility with a learning task is important for sample-efficient learning, and regularization can mitigate non-monotonicity.

  • Takeaways & Limitations

    The theory requires costly eigendecomposition, is limited to the kernel regime for neural networks, and relies on Gaussian and replica-symmetry assumptions.

Abstract

from arXiv · show

Generalization beyond a training dataset is a main goal of machine learning, but theoretical understanding of generalization remains an open problem for many models. The need for a new theory is exacerbated by recent observations in deep neural networks where overparameterization leads to better performance, contradicting the conventional wisdom from classical statistics. In this paper, we investigate generalization error for kernel regression, which, besides being a popular machine learning method, also includes infinitely overparameterized neural networks trained with gradient descent. We use techniques from statistical mechanics to derive an analytical expression for generalization error applicable to any kernel or data distribution. We present applications of our theory to real and synthetic datasets, and for many kernels including those that arise from training deep neural networks in the infinite-width limit. We elucidate an inductive bias of kernel regression to explain data with "simple functions", which are identified by solving a kernel eigenfunction problem on the data distribution. This notion of simplicity allows us to characterize whether a kernel is compatible with a learning task, facilitating good generalization performance from a small number of training examples. We show that more data may impair generalization when noisy or not expressible by the kernel, leading to non-monotonic learning curves with possibly many peaks. To further understand these phenomena, we turn to the broad class of rotation invariant kernels, which is relevant to training deep neural networks in the infinite-width limit, and present a detailed mathematical analysis of them when data is drawn from a spherically symmetric distribution and the number of input dimensions is large.

Introduction

The paper develops a general theory of kernel-regression generalization, motivated by shortcomings in existing theories and the surprising success of overparameterized neural networks. It links generalization to spectral simplicity, task-model alignment, noisy or inexpressible targets, and rotation-invariant kernels.

  • Introduction: Existing generalization theories often provide impractical bounds and inaccurate estimates, especially for predicting performance on real data.
  • Introduction: Overparameterized neural networks can fit random noise yet generalize well, contradicting classical expectations that overparameterization worsens generalization.
  • Introduction: The paper presents a kernel-regression theory applicable to any kernel and real datasets, including infinitely wide neural networks as a special case.
  • Introduction: Using statistical mechanics, the theory derives typical generalization error as a function of training-sample count and kernel spectral properties.
  • Introduction: Kernel regression fits successively higher spectral modes as training data grows, so alignment between top kernel eigenfunctions and the target predicts task suitability.
  • Introduction: Noisy labels or target modes absent from the kernel can produce non-monotonic learning curves, while increased regularization can mitigate this behavior.
  • Introduction: The analysis focuses on rotation-invariant kernels, including NNGPK and NTK, under spherically symmetric data distributions to explain inductive bias and non-monotonicity.

Results

Kernel regression learns high-eigenvalue modes first, so task-model alignment predicts which tasks generalize efficiently. Noise, unexpressible target components, and regularization shape non-monotonic learning curves and double descent.

  • The bias decreases monotonically with more samples, but estimator variance can be non-monotonic and create local maxima in total generalization error.
  • MNIST 0–1 discrimination generalizes faster than 8–9 discrimination because its cumulative power distribution rises more rapidly despite similar NTK eigenspectra.
  • Kernel regression estimates eigenfunctions with larger eigenvalues using fewer samples, establishing a spectral bias toward high-eigenvalue modes.
  • Target functions concentrated in top kernel eigenfunctions are learned efficiently, and cumulative power distribution C(ρ) measures task-model alignment.
  • Non-monotonic generalization can arise from noisy labels or target modes outside the kernel's expressible space, whose effects act as effective noise.
  • The white band-limited model reduces rotation-invariant kernel analysis to a tractable learning-stage model, while its behavior depends on regularization and parameterization.
  • In the white band-limited model, noisy interpolation produces a singular peak at α = 1, after which averaging over noise reduces error asymptotically as Eg ∼ σ2/α.
  • For noisy targets, λ∗ = σ2 minimizes Eg(α) at every α, while larger regularization mitigates peaks but slows learning.

Discussion

The discussion connects generalization to the interaction between data structure and model inductive bias, emphasizing spectral bias, task-model alignment, and non-monotonic learning curves. It also states the theory’s applicability and limitations.

  • Theory and scope: The theory provides an analytical generalization-error expression applicable to any kernel and dataset, including kernel descriptions of infinite-width neural networks.Applications include rotation-invariant kernels and real datasets.
  • Spectral bias: Spectral bias makes modes with larger kernel eigenvalues easier to estimate, so their errors decrease faster as sample size grows.The kernel eigendecomposition orders functions by estimation difficulty.
  • Task-model alignment: Task-model alignment measures how target-function power is distributed across kernel eigenmodes, with greater power in top modes supporting sample-efficient learning.The paper introduces cumulative power distribution as an alignment metric and proves that higher values yield lower normalized error under fixed kernel and data distribution.
  • Non-monotonicity: Non-monotonic generalization can arise from noisy labels or target modes that the kernel cannot express, and regularization can mitigate it.The paper identifies variance as the cause in its decomposition and reports an optimal regularizer in its theoretical settings.
  • Non-monotonicity: The discussion relates multiple observed peaks to overfitting noise and compares them with peaks in random-features models.The comparison distinguishes peaks associated with interpolation thresholds from those observed in the paper’s analytically solvable models.
  • Limitations: The theory requires costly eigendecomposition on the full dataset, is limited to kernel-regime neural networks, and relies on Gaussian and replica-symmetric approximations.The authors note that relaxing these assumptions could reveal further insights.

Methods

The methods derive typical kernel-regression generalization error with statistical mechanics, then analyze it through kernel eigenmodes, target alignment, and data-distribution-dependent spectra.

  • Statistical-mechanics derivation: The calculation uses a Gibbs distribution whose zero-temperature limit is dominated by the kernel-regression solution.A source term in the partition function connects the free energy to dataset-level generalization error.
  • Statistical-mechanics derivation: Typical behavior is obtained by averaging the dataset-dependent free energy over datasets, using self-averaging in the large-sample limit.The replica trick, Gaussian feature-space approximation, replica-symmetric ansatz, saddle-point equations, and β →∞ limit complete the calculation.
  • Spectral analysis: Generalization error decomposes into modal errors for coefficients of kernel eigenfunctions, with larger-eigenvalue modes exhibiting faster error decay.The ordering is established through the mode-error derivatives and holds for all sample sizes in the stated noiseless setting.
  • Spectral analysis: For fixed kernel eigenvalues, reallocating target power toward higher-index-ranked top modes lowers generalization error through the cumulative power distribution.Comparing kernels for a fixed target requires tracking both spectrum changes and changes in the target’s cumulative-power curve.
  • Data and multiclass implementation: The calculation requires kernel eigenvalues and teacher weights derived from the underlying data distribution, approximated by Monte Carlo when that distribution is unknown.For finite datasets, the empirical Gram matrix supplies eigenvalues and eigenvectors, becoming exact as dataset size grows.
  • Data and multiclass implementation: Multiclass targets are represented as separate one-hot output channels, whose channel-wise learning curves are summed into total generalization error.Each channel is expanded in the kernel eigenbasis using its teacher weights.

Competing Interests

The paper declares no competing interests and identifies the supplementary information by the paper title and author list.

  • Declaration: The authors declare no competing interests.
  • Supplementary information: The supplementary information is titled “Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks.”
  • Authorship: The listed authors are Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan.

Supplementary Note 1 - Problem Setup

The supplementary setup formulates kernel regression in an RKHS, decomposes targets into kernel and null modes, and defines generalization error including irreducible null-space error.

  • RKHS and spectral setup: The RKHS is a function space with an inner product and reproducing kernel, defined over square-integrable functions under the data measure.The kernel satisfies the reproducing property and determines the associated Hilbert space.
  • RKHS and spectral setup: Mercer decomposition diagonalizes the kernel integral operator into orthonormal eigenfunctions with nonnegative eigenvalues called the RKHS spectrum.The number of nonzero eigenvalues determines the RKHS dimension.
  • Regression problem: Kernel regression minimizes an energy over RKHS functions, with ridge regularization controlling function complexity and λ →0 giving exact interpolation.The target may be square-integrable without belonging to the RKHS.
  • Regression problem: The target is modeled as a square-integrable function plus zero-mean additive noise, while kernel null modes are defined by zero eigenvalues.The learned function cannot place power in null modes and therefore optimizes only over non-null eigenfunctions.
  • Error decomposition: Generalization error includes the squared target power in kernel null modes as an irreducible error that remains even with infinitely many samples.The theory averages generalization and training errors over datasets of fixed size.

Supplementary Note 2 - Replica Calculation

The replica method converts kernel regression’s dataset-averaged partition function into saddle-point expressions for estimator statistics and generalization error. The resulting decomposition identifies bias, estimator variance, and irreducible error from target components outside the RKHS.

  • Replica setup: Replica averaging treats training samples and label noise as quenched disorder before evaluating the replicated partition function.The calculation uses β →∞ to recover kernel regression quantities and replica symmetry based on convexity.
  • Generalization error: Target modes in the kernel null space act as label noise and add an irreducible component to generalization error.Their contribution can be incorporated by shifting σ2 to σ2 + ∥ā∥2.
  • Replica setup: The calculation approximates the joint distribution of mode-related variables as multivariate Gaussian using their mean and covariance.This approximation is supported by an excellent match between theory and simulations.
  • Generalization error: Non-monotonic learning curves can arise from noise or out-of-RKHS target components, while increasing regularization can mitigate the non-monotonicity.In the noisy interpolation limit, generalization error can diverge, whereas finite regularization smooths the learning curve.
  • Generalization error: The generalization error decomposes into a monotonically decreasing bias and a variance term that is solely responsible for non-monotonicity.The learned function can express only components spanning the RKHS; out-of-RKHS components are never learned.

Supplementary Note 3 - White Band-limited RKHS Spectrum

The white band-limited spectrum provides an analytically solvable model linking kernel expressivity, effective noise, regularization, and sample-size-dependent generalization. Its analysis explains peaks and double descent through separate bias and variance contributions.

  • White band-limited spectrum: A band-limited kernel with ηρ = 0 for ρ > N separates target components representable by the kernel from components outside its RKHS.The target coefficients for modes beyond N contribute to the asymptotic generalization error.
  • White band-limited spectrum: The effective noise is ˜σ2 = σ2 + Eg(∞), combining explicit label noise with target power in the kernel null space.Thus non-monotonic learning curves can occur even when explicit label noise is absent.
  • Learning curves: The noiseless contribution to generalization error decreases with α, whereas the noise contribution peaks at α = 1 + λ.The peak corresponds to the interpolation-related non-monotonicity in the white band-limited model.
  • Learning curves: In noisy settings, generalization error diverges as λ → 0, while finite λ smooths the learning curve and avoids the sharp interpolation peak.Without noise there is no phase transition; with noise, a sharp discontinuity and divergence occur at λ = 0.
  • Rotation-invariant kernels: Rotation-invariant kernels decompose into learning episodes associated with eigenvalues of different degeneracies, each described by the same special-case formula.The framework applies to kernels including Gaussian, Exponential, Matern, NNGPK, and NTK families.

Supplementary Note 4 - Rotation Invariant Kernels

For rotation-invariant kernels, spherical symmetry and high-dimensional limits expose how spectral degeneracy, mode learning, effective regularization, and noise shape generalization curves.

  • Spectral scaling: Kernel eigenvalues scale inversely with rotational degeneracy, ηz,k ∼ O(D^-k), to keep the Mercer decomposition O(1).The relevant scaling also considers P/N(D,k) ∼ O(1), producing a non-trivial large-P, large-D limit.
  • Spectral scaling: Different spherical-harmonic degrees decouple in the large-dimensional limit when sample size scales with their degeneracy.For fixed degree k, eigenvalues may differ across radial modes while sharing the same degeneracy N(D,k).
  • Mode-wise learning: Learning proceeds by kernel modes: lower modes are learned first, while higher modes remain unlearned during earlier learning stages.The mode-l learning term is separated from higher-mode and noise contributions, and modes k > l are not learned at stage l.
  • Effective regularization: Effective regularization is fixed by the full eigenspectrum and ridge parameter, controlling the decay of the self-consistent quantity κ.Larger effective regularization slows κ’s decay; with zero effective regularization, the decay is fastest and its second derivative diverges at α = 1.
  • Non-monotonicity: Noise and weak regularization can produce peaks or double descent, while larger effective regularization reduces peak effects.The peak mechanism follows from the 1/(1 − γ) factor, with γ approaching 1 as effective regularization vanishes.
  • Non-monotonicity: Faster-decaying spectra yield smaller effective regularization and are therefore more likely to produce non-monotonic learning curves with larger peaks.For power-law spectra, effective regularization grows with learning stage and acts like a mode-dependent ridge parameter that keeps higher modes smoother.
  • Kernel bandwidth: Increasing kernel bandwidth lowers effective regularization, whereas smaller bandwidth increases regularization and mitigates learning-curve peaks under noise.For fixed distribution variance, effective regularization increases monotonically with r^2/ω^2.
  • Neural-network correspondence: The infinite-width neural-network correspondence is exact for ridgeless NTK regression, while finite-width networks approach the theory as width increases.At low sample counts, neural-network generalization error is systematically higher than its NTK-regression counterpart; ensembling removes this discrepancy empirically.

Supplementary Note 5 - Details of Numerical Experiments

The numerical experiments construct target functions in kernel eigenbases, compute spectra and theoretical errors, and compare predictions with synthetic, neural-network, and kernel-regression experiments.

  • Spectrum computation: Kernel eigenvalues for spherical-harmonic and Gegenbauer bases are obtained from integral formulas and numerical Gauss–Gegenbauer quadrature.The computed NTK spectrum is used to calculate NTK learning curves.
  • Target construction: Target functions are expanded in normalized kernel features, allowing theoretical generalization error to be computed from mode weights and eigenvalues.The framework supports a wide range of targets, including mixed target functions.
  • Target construction: Pure target functions use a single mode, simplifying numerical evaluation; the synthetic neural-network experiments use a linear target with k = 1.The target is generated using a random projection vector and coefficients selected relative to the kernel spectrum.
  • Experimental targets: Representer-theorem constructions generate alternative targets from sphere samples, while Gaussian label noise is added to study corrupted-sample settings.Kernel-regression coefficients are obtained from training samples, and total error is decomposed into mode-wise errors.
  • Error evaluation: Theoretical mode errors replace target-mode weights with corresponding kernel eigenvalues, and Gaussian RBF experiments use the same procedure.This provides a direct route from the theoretical expression to experimental generalization errors.
  • Neural-network experiments: Neural-network experiments vary hidden-layer widths from 4,000 to 50,000, train two-layer ReLU networks with ADAM, and average five trials.The corresponding NTK experiments use zero regularization and numerically computed NTK spectra.
  • Linear-kernel experiment: For the linear-kernel experiment, Gaussian inputs use a linear target and input dimension N = 500.The linear kernel’s Mercer eigenfunctions are individual input coordinates.
  • S1 experiment: On S1, the experiment evaluates a centered von Mises target in a finite-dimensional RKHS by fitting and comparing functions over [−π, π].The RKHS has dimension 2N, with weights obtained by projection onto cosine features.

Supplementary Note 6 - Notes on Spherical Harmonics

Spherical harmonics provide an orthonormal basis for functions on the sphere, with degree-dependent polynomial structure and degeneracy that supports the kernel spectral analysis.

  • Spherical-harmonic basis: Spherical harmonics are homogeneous harmonic polynomials restricted to the sphere and are orthonormal under the uniform spherical measure.They form a basis for functions on S^(D−1) within the construction used here.
  • Dimension and degeneracy: The degree-k harmonic space is a subspace of homogeneous polynomials of degree k and has a dimension determined by k and D.Its dimension determines the multiplicity of kernel modes in rotationally symmetric settings.
  • Gegenbauer representation: Gegenbauer polynomials relate to sums over degree-k spherical harmonics and are written as Q_k^(D−1)(x · y) on the sphere.This relation connects rotationally invariant kernels to the spherical-harmonic basis.

Supplementary Discussion

The discussion situates the theory among kernel generalization approaches, defines task-model alignment, and emphasizes extensions covering noise, multiple descent, real datasets, and broader observables.

  • Relation to KARE: The theory differs from KARE because ridgeless learning curves retain dependence on kernel and task spectra, whereas KARE’s scaling does not.Both approaches share related quantities, but the paper states they are not equivalent.
  • Relation to KARE: KARE may be easier to implement, but both methods scale as O(M^3) on a sampled dataset of size M.The paper contrasts KARE’s matrix operations with the full eigendecomposition required by its theory.
  • Task-model alignment: Task-model alignment evaluates compatibility through how target power is distributed across kernel eigenmodes, rather than only through an aggregate alignment score.A target with larger cumulative mode-wise power is learned with less training data than another target under the stated comparison.
  • Task-model alignment: For the kernel K(x, x′) = f̄(x)f̄(x′), the target is perfectly aligned and all target power lies in the sole nonzero eigenfunction.The theory predicts the target’s generalization error falls fastest under this kernel.
  • Statistical-physics relations: The paper’s white band-limited analysis extends prior replica-based linear-regression results with a phase diagram for effective noise and regularization.The phase diagram describes how these quantities alter non-monotonic learning curves.
  • Statistical-physics relations: The replica-derived learning curves are related to prior Gaussian-process results while retaining estimator variance that is important for non-monotonicity.The paper’s expression remains valid in the ridgeless limit, where the compared expressions break down.
  • Extensions over prior work: Compared with the earlier conference paper, this work adds label-noise analysis, a multiple-descent phase diagram, CIFAR-10 comparisons, and white band-limited analysis.It also develops task-model alignment and a more general field-theory formalism supporting additional observables.
Loading 2006.13198v6…