Learning Curves for Gaussian Process Regression with Power-Law Priors and Targets

Hui Jin, Pradeep Kr. Banerjee, Guido Montufar

Gaussian Process Regression (GPR) and Kernel Ridge Regression (KRR) are foundational tools in machine learning. This paper provides a rigorous theoretical framework for understanding how GPR improves as it processes more data. By focusing on "power-law" settings—where the properties of the model and the task decay at specific polynomial rates—the authors derive precise asymptotics for generalization error. This work bridges classical kernel methods and the generalization behavior of infinitely wide neural networks, offering significant implications for modern deep learning theory.

Background and Motivation

In machine learning, a "learning curve" describes how the generalization error decreases as the training set size $n$ increases. Understanding these curves is vital for predicting data requirements and model scaling.

While learning curves have been studied extensively, existing theoretical bounds often assume the target function resides within the model's Reproducing Kernel Hilbert Space (RKHS). In practice, particularly in Bayesian non-parametrics, target functions often fall outside this space. Furthermore, the discovery that infinitely wide neural networks behave like Gaussian Processes (via the Neural Tangent Kernel or NNGP kernel) has renewed the need for tight, asymptotic results that can explain the empirical "scaling laws" observed in deep learning.

Methodology

The researchers analyze GPR and KRR by making two primary structural assumptions:

  1. Prior Power Law ($\alpha$): The eigenvalues of the GP kernel decay as $\lambda_p \propto p^{-\alpha}$. The parameter $\alpha$ represents the "smoothness" of the prior.
  2. Target Power Law ($\beta$): The coefficients of the target function, when expanded in the kernel's eigenbasis, decay as $\mu_p \propto p^{-\beta}$. The parameter $\beta$ represents the regularity or complexity of the task.

Using sophisticated concentration analysis, specifically matrix Bernstein inequalities, the authors demonstrate how the empirical kernel matrix concentrates around its population mean. This enables the derivation of tight asymptotic rates for Bayesian Generalization Error (measured via Kullback-Leibler divergence) and Excess Mean Squared Error (MSE).

Key Insights and Results

  • The Interplay of $\alpha$ and $\beta$: The learning rate depends fundamentally on the alignment between the model and the data. The generalization error is shown to behave as $\Theta(n^{\max\{\frac{1}{\alpha}-1, \frac{1-2\beta}{\alpha}\}})$.
  • Beyond the RKHS: The paper successfully characterizes the "unrealizable" case. If a target function is "rougher" than the prior expects, the learning rate slows down, and the paper provides the exact mathematics to predict this deceleration.
  • Spectral Bias: The results offer a theoretical basis for "spectral bias"—the phenomenon where low-frequency components of a function are learned much faster than high-frequency ones.
  • Neural Network Scaling: Because the Neural Tangent Kernel (NTK) of ReLU networks often exhibits a power-law spectrum, this work helps explain the power-law "scaling laws" observed in large language models and other deep learning systems.
  • Tight Asymptotics: The authors prove that the negative log-marginal likelihood and the generalization error follow specific power-law decays, recovering and extending classical results (such as those by Sollich & Halees, 2002) to more realistic, misspecified settings.

Experimental Validation

To validate their theorems, the authors utilize synthetic toy experiments rather than large-scale real-world datasets. They sample data points uniformly on a unit circle ($S^1$) and apply arc-cosine kernels of various orders (0, 1, and 2), which correspond to infinitely wide ReLU neural networks.

By selecting specific target functions (e.g., $\cos(2\theta)$, $\theta^2$, or $\text{sign}(\theta)$) with known power-law eigen-coefficients, they directly test the $\alpha$ and $\beta$ theory. In all tests, the slope of the error on a log-log plot perfectly matched the theoretical predictions derived from the chosen kernels and targets.

Limitations and Future Work

  • Power-Law Assumption: The theory strictly relies on power-law decay and does not directly cover kernels with exponential eigenvalue decay, such as the Radial Basis Function (RBF) kernel.
  • Infinite Width Limit: The connection to neural networks assumes the "infinite width" regime, which does not account for finite-width effects or feature learning present in practical neural networks.
  • Real-World Complexity: Future research is necessary to estimate actual $\alpha$ and $\beta$ values for real-world datasets (like ImageNet) and complex architectures (like Transformers) to verify these theoretical scaling laws in practical scenarios.

Summary updated

Abstract

We characterize the power-law asymptotics of learning curves for Gaussian process regression (GPR) under the assumption that the eigenspectrum of the prior and the eigenexpansion coefficients of the target function follow a power law. Under similar assumptions, we leverage the equivalence between GPR and kernel ridge regression (KRR) to show the generalization error of KRR. Infinitely wide neural networks can be related to GPR with respect to the neural network GP kernel and the neural tangent kernel, which in several cases is known to have a power-law spectrum. Hence our methods can be applied to study the generalization error of infinitely wide neural networks. We present toy experiments demonstrating the theory.
BibTeX
@inproceedings{jin2022learning,
  author = {Hui Jin and Pradeep Kr. Banerjee and Guido Montufar},
  title = {{Learning Curves for Gaussian Process Regression with Power-Law Priors and Targets}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=KeI9E-gsoB},
}
Figure