The Size of Teachers as a Measure of Data Complexity: PAC-Bayes Excess Risk Bounds and Scaling Laws

Gintare Karolina Dziugaite, Daniel M. RoyAISTATS 2025 · OpenReview

Introduction

Deep learning presents a persistent theoretical paradox: models with billions of parameters are trained on datasets that are often orders of magnitude smaller, yet they generalize remarkably well instead of merely memorizing noise. While practitioners have identified empirical "neural scaling laws"—mathematical rules predicting that model performance improves predictably as data and parameters increase—theoretical frameworks have struggled to explain why these specific power laws emerge.

A core challenge in bridging this gap is the lack of a formal, quantitative measure for "data complexity." It is difficult to determine if a specific task is "harder" due to noisy inputs or an inherently more intricate decision boundary. This paper addresses this by defining data complexity through the lens of "teacher" networks, providing a theoretical foundation for the scaling laws observed in large-scale models like GPT-3 and Chinchilla.

The Teacher-Student Framework and Gated Architectures

The authors propose that the performance of a massive "student" network is not limited by its own total parameter count, but by the existence of a much smaller "teacher" network capable of solving the task to a specific level of accuracy. To formalize this, they introduce a "gated" neural network architecture. In this model, a large student network can effectively "turn off" unnecessary neurons, allowing it to functionally mimic the behavior of a smaller, simpler teacher.

The gated architecture allows a large student network (right) to functionally mimic a smaller teacher network (left) by deactivating redundant neurons.

By defining data complexity $C(\epsilon)$ as the minimum number of parameters a teacher needs to achieve an excess risk of $\epsilon$, the researchers create a metric that links the inherent difficulty of a dataset to the architectural requirements of a model that can generalize from it.

Theoretical Foundations: PAC-Bayes and Gibbs Posteriors

To derive rigorous guarantees, the paper employs PAC-Bayes theory, specifically utilizing "single-sample" bounds. Because analyzing Stochastic Gradient Descent (SGD) directly is mathematically complex, the authors model the training process as sampling from a Gibbs posterior—a distribution that naturally favors models with low training error.

This approach allows for the derivation of an "oracle inequality" that remains valid even in "agnostic" learning scenarios, where the data may be noisy or a perfect teacher might not exist. This is a significant advancement over previous theories that required the "realizable" assumption (i.e., that a perfect fit is always possible).

Deriving and Validating Scaling Laws

The most striking result of this framework is its ability to mathematically derive the power-law decay in risk observed in empirical studies. By assuming that data complexity $C(\epsilon)$ follows a power law (e.g., $C(\epsilon) \approx \epsilon^{-p}$), the theory predicts that excess risk should decay at a rate of $O(n^{-1/(p+1)})$, where $n$ is the sample size.

Theoretical simulation showing the optimal excess risk (ε) decaying as a power law of the sample size (n), with a slope of -0.100 matching empirical LLM observations.

When the authors plugged in values to match the scaling rates reported in DeepMind’s Chinchilla report (Hoffmann et al., 2022), they found remarkable consistency. For instance, to achieve the observed -0.1 scaling rate, the underlying data complexity of human language must be approximately $C(\epsilon) \in O(\epsilon^{-9})$. This provides a concrete, quantitative way to describe the complexity of the distributions used to train modern Large Language Models (LLMs).

Limitations and Future Directions

While the theory offers a powerful new perspective, several hurdles remain:

  • Quantization: The current proofs rely on weights being discrete (quantized), which is common in deployment (e.g., 4-bit weights) but does not yet fully capture the continuous weight space of standard floating-point training.
  • Symmetry: The bounds do not yet account for permutation symmetry (the ability to swap neurons without changing function), meaning the actual probability of finding a suitable teacher is likely higher than the current math suggests.
  • Overparameterization Limits: The bounds become "vacuous" if the student network grows faster than the square of the number of data points ($n^2$), suggesting the theory is currently best suited for the "moderate overparameterization" regime.

By framing generalization as the search for an existing simple explanation within a complex model, this work moves the field closer to a unified theory of why scaling works.

Summary updated

Abstract

We study the generalization properties of neural networks through the lens of data complexity. Recent work by Buzaglo et al. (2024) shows that random (nearly) interpolating networks generalize, provided there is a small "teacher" network that achieves small excess risk. We give a short single-sample PAC-Bayes proof of this result and an analogous "fast-rate" result for random samples from Gibbs posteriors. The resulting oracle inequality motivates a new notion of data complexity, based on the minimal size of a teacher network required to achieve any given level of excess risk. We show that polynomial data complexity gives rise to power laws connecting risk to the number of training samples, like in empirical neural scaling laws. By comparing the "scaling laws" resulting from our bounds to those observed in empirical studies, we provide evidence for lower bounds on the data complexity of standard benchmarks.
BibTeX
@inproceedings{dziugaite2025size,
  author = {Gintare Karolina Dziugaite and Daniel M. Roy},
  title = {{The Size of Teachers as a Measure of Data Complexity: PAC-Bayes Excess Risk Bounds and Scaling Laws}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=FDUfAcAVjO},
}
Figure