Summary

In 2018, Zhang et al. showed that deep neural networks can achieve perfect training loss on randomly labeled data.

This was a Big Deal.

It meant that existing generalization theory couldn't explain why deep neural networks generalize. That's because classical approaches to proving that a given model class (=neural network architecture) would generalize involved showing that it lacks the expressivity to fit noise. If a model class can fit noise arbitrarily well, the resulting bounds break.

So something needed to change.

Evidently, you can't prove tight generalization bounds for entire model classes, so theorists turned to studying generalization bounds for individual models within a model class. If you can empirically show that a model's performance doesn't change substantially when you perturb it (by adding noise to the inputs, weights, training samples, etc.), then you can theoretically prove that that model will generalize to new data.

As a result, the bounds have gotten tighter, but they're still not exactly flattering.

What's really needed is a secret third thing. It's not about either model classes or individual models but about model subclasses. While the model class as a whole may be too complex to obtain tight generalization bounds, individual subclasses can achieve an optimal trade-off between accuracy and complexity. For singular Bayesian learning machines, this trade-off happens automatically.

This more or less answers why models are able to generalize but not how they do it.

Singular learning theory (SLT) provides one possible path towards understanding the how of generalization. This approach is grounded in the geometry of the loss landscape, which in turn is grounded in the symmetries of the model class and data. If this direction pans out, then learning theory is posed for a revolution analogous to the transition between thermodynamics and statistical physics.

Introduction

The central aim of classical learning theory is to bound various kinds of error: in particular, the approximation error, generalization error, and optimization error.

In the previous post in this series, we looked at the approximation error, which measures the performance of a model class's hypothetically optimal model. If your model class isn't expressive enough to do a reasonable job of modeling the data, then it doesn't matter that your model generalizes to new data or that your learning process actually reaches that optimum in practice.

In this post, we'll look at bounding the generalization error, which measures how well a model $f_w\in F$ parametrized by $w\in W$ transfers from a finite training set to additional samples drawn from the same distribution.  We won't cover the related question of out-of-distribution generalization, which asks how a model will perform on data from a different distribution. 

Last time, we started to see that approximation and generalization could not be separated in practice. Here, we'll see the same holds for generalization and optimization. SLT and many other strands of generalization theory point to a deep relation, which views generalization in nearly dynamical terms involving changes to probability distributions. 

In the next post in this sequence, we'll examine the optimization error, which measures how close learning processes get to global optima. Coming at the connection with generalization from the other direction, we'll view optimization in quasistatic terms as a process of selecting among qualitatively distinct generalization strategies. 

This is mainly based on lecture notes by Telgarsky (2021), a recent monograph by Hellström et al. (2023), and Watanabe (2009, 2018).

Outline

This is a self-contained introduction to generalization theory, as developed in three different schools of learning theory: classical learning theory, deep learning theory, and singular learning theory. There's a lot to cover:

• Measuring "generalization" — First, we treat the question of how to quantify generalization, and how this differs between the paradigms of empirical risk minimization and Bayesian inference. 
• Bounding generalization — Next, we look at the different kinds of bounds learning theorists study. This will include classical approaches like uniform convergence and Probably Approximately Correct (PAC) learning, as well as more modern approaches like PAC Bayes.
• Measuring "complexity" — Then, we'll cover the three different types of complexity measures that show up in these bounds: model-class complexity, single-model complexity, and model-subclass complexity. These roughly correspond to the different perspectives of classical learning theory, deep learning theory, and singular learning theory, respectively. 
• Thermodynamics of generalization — Finally, we'll examine the model-subclass complexity measures from a thermodynamic point of view. This raises the natural question: what would a statistical physics of generalization look like and what might we learn about how neural networks generalize?

Measuring "generalization"

The generalization error

To recap, classical learning theory is primarily grounded in the paradigm of Empirical Risk Minimization (ERM). ERM is a story about two kinds of risk. 

The empirical risk $R_n$ is what you might recognize as the "training loss",

where the average is taken over the $n$ samples in your dataset $D_n=\left\{\right(x_i,y_i){\}}_{i=1}^n$.^[1] Learning theorists maintain a sensible distinction between the individual-sample "loss" function $\ell$ and the average-loss "risk" $R_n$.

The population risk (or "true" risk) $R$ is the expectation of the loss over the true distribution $q(x,y)$ from which the dataset is drawn:

In its broadest form, generalization is the question of how a model transfers from a finite dataset to new data. In practice, learning theorists study the generalization error (or generalization gap) $G_n\left(f_w\right)$, 

which addresses a more narrow question: how far apart are the empirical risk and population risk?

Derived generalization metrics

The generalization error, $G_n$, is a function of both the learned model $f_w$ and dataset $D_n$, so by taking expectation values over data, weights, or both, we derive a family of related generalization metrics.

The relevant distributions include:

• $p\left(w|D_n\right)$: the "learning algorithm", some mapping from a dataset to weights. If we're using a deterministic algorithm, this becomes a delta function. In Bayesian learning, this is the posterior. For neural networks, think of the distribution of final weights over initializations and training schedules for a set of fixed optimizer hyperparameters.
• $q\left(D_n\right)={\prod }_{i=1}^{n}q(x_i,y_i)$: the true probability of the dataset. We're assuming samples are i.i.d.
• $p(w,D_n)=p\left(w|D_n\right)q\left(D_n\right)$: the joint distribution over learned weights and datasets.

From these distributions, we obtain:^[2]

• $E_{p(w,D_n)}\left[G_n\right(f_w\left)\right]$: the average generalization error over learned weights and datasets.
• $E_{q\left(D_n\right)}\left[G_n\right(f_w\left)\right]$: the average generalization error over datasets for a fixed model $f_w$.
• $E_{p\left(w|D_n\right)}\left[G_n\right(f_w\left)\right]$: the average generalization error over learned weights for a fixed dataset $D_n$.
• $G_n\left(E_{p\left(w|D_n\right)}\right[f_w\left]\right)$: the generalization error for the average prediction made by the learned models for a fixed dataset.

And so on.

Bayesian generalization metrics

In a Bayesian setting, we replace the deterministic prediction $\hat{y}=f_w\left(x\right)$ with a distribution $p(y|x,w)$, which induces a likelihood $p\left(D_n|w\right)={\prod }_{i=1}^{n}p(y_i|x_i,w)q\left(x_i\right)$. Under certain assumptions, empirical risk minimization maps onto a corresponding Bayesian problem, in which the empirical risk is the negative log likelihood (up to a constant).^[3] 

The Bayesian learning algorithm is the posterior,

But we're not just interested in updating our beliefs over weights — we also want to use our new beliefs to make predictions. Theoretically, the optimal way to do this is to average novel predictions over the ensemble of weights, weighing each machine according to their posterior density. This yields the predictive distribution,

In practice, evaluating these kinds of integrals is intractable. A more tractable alternative is Gibbs estimation, where we draw a particular choice of weights $w^{\prime }\sim p\left(w|D_n\right)$ and make predictions using the corresponding model $p(y|x,w^{\prime })$. This procedure is closer to the kind of paradigm we're in with neural networks: the model we train is a single draw from the distribution of final weights over different initializations and learning schedules. 

Predicting according to either the predictive distribution or Gibbs estimation respectively yields two different kinds of generalization error:

• The Bayes generalization error is the KL divergence between the true distribution and the predictive distribution:

• The Gibbs generalization error is the posterior-averaged KL divergence between the true distribution and the model $p(y|x,w)$: