Learning curves for Gaussian process regression with power-law priors and targets

Hui Jin, Pradeep Kr. Banerjee, Guido Montúfar

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.

Introduction

In the quest to understand why deep learning works so well, researchers have increasingly turned to "scaling laws"—the empirical observation that model performance improves predictably as a power law of the training set size. While these laws are well-documented in practice, their theoretical foundations remain a work in progress. A recent study by Hui Jin, Pradeep Kr. Banerjee, and Guido Montúfar provides a rigorous mathematical look at these dynamics through the lens of Gaussian Process Regression (GPR).

The central question addressed is: How much data is required to reach a specific performance threshold? This is typically answered by analyzing "learning curves," which plot generalization error against the number of training samples ($n$). In many real-world scenarios, these curves follow a power law ($n^{-\beta}$). However, theoretically predicting the value of $\beta$ is challenging. Previous studies often relied on the "realizable" assumption—that the target function is perfectly contained within the model's hypothesis space. This paper tackles the more realistic "unrealizable" case, where the target function might be smoother or rougher than the model expects, or even contain components the model can never learn.

Theoretical Framework and Methods

The authors employ a spectral analysis approach based on Mercer’s Theorem, which allows for the decomposition of the kernel (the "prior" of the GP) into its eigenvalues and eigenfunctions. The analysis is built upon three key assumptions:

  1. Capacity Condition: The eigenvalues of the kernel decay according to a power law ($\mu_p \sim p^{-\alpha}$). This parameter $\alpha$ represents the model's capacity or the smoothness of the prior.
  2. Source Condition: The coefficients of the target function, when expanded in the kernel's eigenfunctions, also decay as a power law ($c_p^2 \sim p^{-\beta}$). This $\beta$ characterizes the complexity or smoothness of the target task.
  3. Boundedness: The eigenfunctions themselves are assumed to be well-behaved and bounded, ensuring the stability of the spectral decomposition.

By analyzing the "normalized stochastic complexity" (related to the log-marginal likelihood) and the "Bayesian generalization error," the authors derive asymptotic bounds for how these quantities behave as $n \to \infty$. Crucially, they utilize a tight analysis of how empirical eigenfunctions concentrate around their population counterparts, allowing them to cover a wider range of kernels—such as the Neural Tangent Kernel (NTK)—than previous methodologies.

Key Insights

The research highlights several critical aspects of the learning process:

  • The Interplay of $\alpha$ and $\beta$: The learning rate is not determined solely by the model ($\alpha$) or the task ($\beta$); rather, it depends on their interaction. The generalization error scales as $\Theta(n^{\max\{\frac{1}{\alpha}-1, \frac{1-2\beta}{\alpha}\}})$. This formula captures how the model's ability to suppress noise competes with its ability to resolve the target function's details.
  • Spectral Bias: The results provide formal theoretical support for "spectral bias"—the tendency of models to learn low-frequency components (associated with larger eigenvalues) significantly faster than high-frequency components or noise.
  • The Learning Floor: In the "unrealizable" scenario, if the target function contains a component orthogonal to the kernel's eigenfunctions, the generalization error will never reach zero. Instead, it asymptotically approaches a constant floor determined by the magnitude of that unlearnable component.
  • Bridging to Neural Networks: Because infinitely wide neural networks behave like GPs in certain regimes (via the Neural Network Gaussian Process (NNGP) and NTK), these results provide direct theoretical predictions for the scaling exponents observed when training massive deep learning models.

Experimental Validation

The paper validates the theory using toy experiments on a unit circle ($S^1$). The authors tested four specific target functions ($f_1$ to $f_4$) with varying degrees of smoothness (different $\beta$ values) against arc-cosine kernels of orders 0, 1, and 2. These kernels are significant as they represent the infinite-width limits of specific neural network architectures, such as ReLU networks. In these experiments, the slopes of the error curves on log-log plots matched the theoretical predictions with high precision, confirming the accuracy of the derived exponents.

Conclusion and Future Directions

While this work provides a strong theoretical foundation for scaling laws in GPR and KRR, some limitations persist. The theory specifically targets power-law decays and may not directly apply to kernels with exponential decay, such as the Radial Basis Function (RBF) kernel. Furthermore, the connection to neural networks assumes the infinite-width limit; real-world networks are finite, and "finite-width effects" might alter these scaling laws. Future research will need to investigate whether these specific $\alpha$ and $\beta$ values can be accurately estimated and used to predict performance on high-dimensional, real-world datasets.

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 Montúfar},
  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