NOTE: Work in Progress

Outline

• Warm-up: MSE & bias-variance trade-offs.
• Generalization = Simplicity.
  • Solomonoff induction,
  • Complexity measures
    • BIC/MDL, AIC
    • VC dimension & structural risk minimization
    • Rademacher complexity
• Early Stopping
  • NTK
• Problems:
  • Vacuous bounds (Zhang et al. 2017). Always zero training error. Any optimizer (even stupid ones). Crazily convex loss spots. Even with regularization
• From functions to probabilities
  • Gibbs measure
  • PAC-Bayes bounds
    • NNs Dziugaite & Roy 2017
  • Singular learning theory, WAIC
• Mingard-style “Bayesian inference”

Misc:

• SGD & Basin broadness
• Heavy-tailed random matrix theory (implicit self-regularization)
• Double descent & grokking
• Recent Anthropic work It’s non-obvious that (l2) regularization chooses simpler functions in NNs. (Polynomial regression is one thing).

"Regular" learning theory (RLT) predicts that overparametrized deep neural networks (DNNs) should overfit. In practice, the opposite happens: deeper networks perform better and generalize further. What's going on?

The consensus is still out, but different strands of research appear to be converging on a common answer: DNNs don't overfit because they're not actually overparametrized; SGD and NN's symmetries favor "simpler" models whose effective parameter counts are much lower than the externally observed parameter count. Generality comes from a kind of internal model selection where neural networks throw out unnecessary expressivity.

In this post, I'll make that statement more precise. We'll start by reviewing what RLT has to say about generalization and why it fails to explain generalization in DNNs. We'll close with a survey of more recent attempts at the learning theory of DNNs with particular emphasis on "singular" learning theory (SLT).

Intro to Statistical Learning Theory

Before we proceed, we need to establish a few definitions. Statistical learning theory is often sloppy with its notation and assumptions, so we have to start at the basics.

In this post, we'll focus on a (self-)supervised learning task. Given an input $x \in \mathcal X$, we'd like to predict the corresponding output $y \in \mathcal Y$. This relationship is determined by an unknown "true" pdf $q(z) = q(x, y)$ over the joint sample space $\mathcal Z = \mathcal X \times \mathcal Y$.

If we're feeling ambitious, we might directly approximate the true joint distribution with a generative model $p(x, y|w)$ that is parametrized by weights $w \in \mathcal W \subseteq \mathbb R^D$. If it's tractable, we can marginalize this joint distribution to obtain the marginal and conditional distributions. ¹

If we're feeling less ambitious, we might go ahead with a discriminative model of the conditional distribution, $p(y| x, w)$. (In the case of regression and classification, we're interested in inferring target values and labels from future samples, so we may not care all that much about $q(x)$ and $q(x|y)$.)

And if we're feeling unambitious (as most machine learning theorists are), it may be enough to do direct inference with a discriminant function — i.e., to find a deterministic function that maps inputs to outputs, $f_w: \mathcal X \to \mathcal Y$.²

In the case of regression, this is justified on the (only occasionally reasonable) assumption that the error is i.i.d. sampled from a Gaussian distribution. In other words, the discriminative model is defined in terms of $f$ as:

Machine learning usually begins with discriminant functions. Not only is this often easier to implement, but it offers some additional flexibility in the kinds of functions we can model because we optimize arbitrary loss functions that are unmoored from Bayesian-grounded likelihoods or posteriors.³

This flexibility comes at a cost: without the theoretical backing, it's more difficult to reason systematically about what's actually going on. The loss functions and regularizers of machine learning often end up feeling ad hoc and unsupported because they are. Or at least they will be until section 3.

As a result, we'll find it most useful to work at the intermediate level of analysis, in terms of discriminant models.

What Is Learning, Anyway?

The strength of the Bayesian framing is that for some prior over weights, $\phi(w)$, and a dataset $\mathbf d^{(n)} \in \mathcal Z^n$ of samples $\{(x_i, y_i)\}_{i=1}^n$, we can "reverse" the likelihood (assuming each sample is sampled i.i.d. from $p(x, y)$),

to obtain the a posteriori distribution,

where $Z_n$ is the evidence (or partition function),

The aim of "learning" is to make our model $p(y|x, w)$ as "close" as possible to the truth $q(y|x)$.

In the probabilistic formulation, the natural choice of "distance" is the Kullback-Leibler divergence (which is not actually a distance):

where the second equality follows from defining $q(x, y|w) = q(y|x, w) \cdot p(x)$.

Formally, the aim of learning is to solve the following:

We say $p(y|x)$ is realizable iff $K(w^*) = 0$, in which case we call $w^*$ the "true" parameters.

At this point, we run into a bit of a problem: we can't actually compute the expectations $\langle \cdot\rangle_{X, Y}$ since we don't know $p(x, y)$ (and even if we did, the integration would likely be intractable). Instead, we have to resort to empirical averages over a dataset,. ³

Maximum Likelihood Estimation is KL-Divergence Minimization

Example: Regression & Mean-Squared Error

Fortunately, there's a more general and principled way to recover discriminant models from discriminant functions than the assumption of isotropic noise, as long as we're willing to relax Bayes' rule.

First, we introduces a parameter $\beta \geq 0$ that controls the tradeoff between prior and likelihood to obtain the tempered Bayes update [1],⁴

$p_\beta(w|\mathbf d) \propto p(\mathbf d| w)^{\beta}p(w),$

where $\mathbf d$ is a dataset of samples $\{(x_{i},y_{i})\}_{i=1}^n$, and the likelihood is obtained by assuming each sample is distributed i.i.d. according to $p(x_{i}, y_{i}|w)$ s.t. $p(\mathbf d|w) = \prod_{i=1}^{n}p(x_{i}, y_{i}|w)$.

Next, we replace the tempered likelihood with a general loss function

The real-world is noisy, and pure function approximation can't account for this.

To remedy this, it's common to model any departure from our deterministic predictions, $\hat y = f_w(x)$, as isotropic noise, e.g., $q(y|x, w) = \mathcal N(y| f_w(x), \sigma^2)$.

Physically, we may expect the underlying process to be deterministic (given by a "true" function $f^*$) with noise creeping in through some unbiased measurement error $\epsilon \sim \mathcal N(0, \sigma^2)$.

For Gaussian noise, the NLL works out to:

Assuming isotropic Gaussian noise in a regression setting, we see that MLE simplifies to minimizing the mean squared error (up to some overall constant and scaling).

To make MLE more Bayesian, you just multiply the likelihood by some prior over the weights, to obtain maximum a posteriori estimation (MAP): $p(w|\mathbf d) \propto p(\mathbf d|w)\phi(w).$ If we enforce a gaussian prior with precision $\alpha$, the loss gains a regularization term (weight decay), $\frac{\alpha}{2}w^T w$ to the loss function. [2]

Gibbs Generalization Error

Todo

What Is Generalization, Anyway?

Consider the empirical probability distribution,

where $\delta(\cdot)$ is a delta function appropriate to the sample space.

Although this will converge to the true distribution as $N\to\infty$, for any finite $N$, we encounter sampling error. This problem is particularly pronounced for unseen samples: $q_D(z)$ may (and almost always does) assign zero probability to samples that have non-zero probability under the true distribution.

The fundamental challenge of generalization is to make predictions about these unseen samples. Let's make this more precise.

Given some loss function $\ell: Y \times Y \to \mathbb R$, we're interested in how $\ell$ performs on future samples, as measured by the expected risk or generalization error,

However, we can only estimate this performance on on the available dataset via the empirical risk,

where $\overline \cdot$ denotes an empirical average over the dataset, $\mathbf d$.

Our problem is that the true generalization error is unknowable. So, in practice, we split our dataset into a training set, $\mathbf s$, and test set, $\mathbf e$, respectively. We learn our parameters $w$ via the training set, and then estimate the generalization error on the test set. That's where we encounter our first major confusion.³

You see, besides the generalization error, there's the distinct notion of the generalization gap,

Whereas generalization error is about absolute performance on the true distribution, the generalization gap is about relative performance between the training and test sets. Generalization error combines both "performance" and "transferability" into one number, while the generalization gap is more independent of "performance" — past a certain threshold, any amount of test-set performance is compatible with both a low and high generalization gap.

For the remainder of this post, I'll focus on the generalization gap. It's not absolute performance we're interested in: universal approximation theorems tell us that we should expect excellent training performance for neural networks. The less obvious claim is why this performance should transfer so well to novel samples.

---

Yes, more data means better generalization, but that's not what we're talking about.

In the limit $N\to \infty$, the empirical risk converges to expected risk, and both generalization error and gap will fade away: $\epsilon_g \to 0,\quad \epsilon_g^2 \to 0 \quad \text{as} \quad N \to \infty.$ So obviously the larger datasets that have accompanied the deep learning boom explain some of the improvement in generalization.

PAC Learning

Established by Valiant (1984) [3], Probably Approximately Correct (PAC) learning establishes upper bounds for the risk $I[f]$. In its simplest form, it states that, for any choice of $\epsilon$ ("probably") a predictor, $f$, will have its risk bounded by some $\delta$ ("approximately correct"):

Originally, PAC learning included the additional assumption that the predictor was polynomial in $N$ and $1/\epsilon$, but this has been relaxed to refer to any bound holding with high probability.

Still, it's not a full explanation as typical networks can easily memorize the entire training set (even under random labelings [4]).

---

MSE & Bias-variance tradeoff

In the case of isotropic noise (where our loss function is the MSE), the generalization error of a model is:

In other words, it is the (l2) distance between our predictions and the truth averaged over the true variables $X \times Y$. The bias-variance decomposition splits the generalization error into a bias term,

which measures the average difference between predictions and true values, a variance term,

which measures the spread of a model's predictions for a given point in the input space, and an irreducible error due to the inherent noise in the data. (For Gaussian noise, the irreducible error is $\sigma^2$.)

In order to achieve good generalization performance, a model must have low bias and low variance. This means that the model must be complex enough to capture the underlying patterns in the data, but not so complex that it overfits the data and becomes sensitive to noise. In practice, these two forces are at odds, hence "tradeoff."

---

Generalization is about simplicity

A common assumption across the entire statistical learning theory literature is that of simple functions generalizing better. It's worth spending a second to understand why we should expect this assumption to hold.

Occam's Razor

"Entities must not be multiplied beyond necessity".

Occam's razor is the principle of using the simplest explanation that fits the available data. If you're reading this, you probably already take it for granted.

Solomonoff Induction

Algorithmic complexity theory lets us define a probability distribution over computable numbers,

$p(x)= \sum_{p}2^{-K(p)},$ where $K(\cdot)$ is the (prefix) Kolmogorov complexity. The probability of any given number is the probability that a uniform random input tape on some Universal Turing Machine outputs that number. Unfortunately, the halting problem makes this just a tad uncomputable. Still, in principle, this allows a hypercomputer to reason from the ground up what the next entry in a given sequence of numbers should be.

Bayesian/Akaike Information Criterion

One of the main strengths of the Bayesian frame is that it lets enforce a prior $\varphi(w)$ over the weights, which you can integrate out to derive a parameter-free model:

One of the main weaknesses is that this integral is often almost always intractable. So Bayesians make a concession to the frequentists with a much more tractable Laplace approximation (i.e., you approximate your model as quadratic/gaussian in the vicinity of the maximum likelihood estimator (MLE), $w^{(0)}$):

where $I(w)$ is the Fisher information matrix:

From this approximation, a bit more math gives us the Bayesian information criterion (BIC):

The BIC (like the related Akaike information criterion) is a criterion for model selection that penalizes complexity. Given two models, the one with the lower BIC tends to overfit less (/"generalize better").

That is, simpler models (with fewer parameters) are more likely in approximate Bayesian inference. We'll see in the section on singular learning theory that the BIC is unsuitable for deep neural networks, but a generalized version, the Widely Applicable Bayesian Information Criterion (WBIC) will pick up the slack.

Minimum Description Length

The BIC is formally equivalent to MDL. TODO

Maximum Entropy Modeling

TODO

Classic Learning Theory

As we've seen in the previous section, the question of how to generalize reduces to the question of how to find simple models that match the data.

In classical learning theory, the answer to this is easy: use fewer parameters, include a regularization term, and enforce early stopping. Unfortunately, none of these straightforwardly help us out with deep neural networks.

For one, double descent tells us that the relation between parameter count and generalization is non-monotonic: past a certain number of parameters, generalization error will start decreasing. Moreover, a large number of the complexity measures we've seen are extensive (they scale with model size). That suggests they're not suited to the task.

As for regularization, it gets more complicated. That regularization on polynomial regression leads to simpler functions is straightforward. That regularization on deep neural networks leads to simpler models is less obvious. Sure, a sparse l1 regularizer that pushes weights to zero seems like it would select for simpler models. But a non-sparse l2 regularizer? Linking small parameters to simple functions will require more work. A deeper problem is that DNNs can memorize randomly labeled data even with regularizers [5]. Why then, do DNNs behave so differently on correctly labeled (/well-structured) data

Other forms of regularization like dropout are more understandable: they explicitly select for redundancy which collapses the effect parameter count.

Finally, early stopping doesn't seem to work with the observation of grokking: in certain models, training loss and test loss may plateau (at a poor generalization gap) for many epochs before training loss suddenly sharply decreasing (towards a much better generalization gap).

SGD Favors Flat Minima

• $P_\beta(f)$ is the probability that $M$ expresses $f$ on $D$ upon a randomly sampled parametrization. This is our "prior"; it's what our network expresses on initialization.
• $V_\beta(f)$ is a volume with Gaussian measure that equals $P_\beta(f)$ under Gaussian sampling of network parameters.
  • This is a bit confusing. We're not talking about a continuous region of parameter space, but a bunch of variously distributed points and lower-dimensional manifolds. Mingard never explicitly points out why we expect a contiguous volume. That or maybe it's not necessary for it to be contiguous
• $\beta$ denotes the "Bayesian prior"
• $P_\text{opt}(f|S)$ is the probability of finding $f$ on $E$ under a stochastic optimizer like SGD trained to 100% accuracy on $S$.
• $P_\beta(f|S) = \frac{P(S|f) P_\beta(f)}{P_\beta(S)},$ is the probability of finding $f$ on $E$ upon randomly sampling parameters from i.i.d. Gaussians to get 100% accuracy on $S$.
  • This is what Mingard et al. call "Bayesian inference"
  • $P(S|f)=1$ if $f$ is consistent with $S$ and $0$ otherwise I.e.: Hessians with small eigenvalues.

Flat minima seem to be linked with generalization:

• Hochreiter and Schmidhuber, 1997a; Keskar et al., 2016; Jastrzebski et al., 2018; Wu et al., 2017; Zhang et al., 2018; Wei and Schwab, 2019; Dinh et al., 2017.

SGD

Problems:

• Suitable reparametrizations can change flatness without changing computation.

Initialization Favors "simple" functions

Mingard 2021

• Levin et al. tell us that many real-world maps satisfy $P(f) \lesssim 2^{-b\tilde K(f)+a}$, where $\hat K$ is a computable approximation of the true Kolmogorov complexity $K(f)$.
• Empirically, maps of the form $f:\{0, 1\}^n \to \{0, 1\}$ satisfy a similar upper bound using a computable complexity measure (CSR).
• This is an upper bound, not more than that!
• The initialization acts as our prior in Bayesian inference.

SGD Performs Hidden Regularization

Mingard 2020

1. **Bayesian inference preserves the "simplicity" of the prior.
2. SGD performs a kind of "Bayesian inference"
   • You can approximate $P_\beta(f)$ with Gaussian Processes.
   • Mingard's main result is that $P_\text{opt}(f|S) \approx P_\beta(f|S)$ appears to hold for many datasets (MNIST, Fashion-MNIST, IMDb movie review, ionosphere), architectures (Fully connected, Convolutional, LSTM),  optimizers (SGD, Adam, etc.), training schemes (including overtraining) and optimizer hyperparameters (e.g. batch size, learning rate).
   • Optimizer hyperparameters matter much less than $P_\beta(f|S)$

Singular Learning theory

Glossary

• $f^*$ is the true function
• $f$ is some implemented function
• $M$ is our neural network
• $D$ is a dataset of pairs $\{(x_i, y_i)\}_{i=1}^N$
• $S, E \subset D$ are the training & test sets, respectively.

Learnability

• PAC in original formulation: simpler functions are easier to learn (polynomial time)

Usually, the true relation is probabilistic. In this case, we're not interested in a deterministic mapping $f^*$ from elements of $\mathcal X$ to elements $\mathcal Y$, but a probability distribution, $q(x, y)$, which relates random variables $X$ and $Y$ (where $\mathcal X$ and $\mathcal Y$ are the associated sample spaces).

We don't have direct access to $q(x, y)$, but we do have access to a dataset of samples, $\mathbf D = \{(X_i, Y_i)\} _ {i=1}^n$, which is itself a random variable. We specify some loss function, $\ell$, $\mathcal Y \times \mathcal Y \to\mathbb R$, which maps a prediction, $\hat y = f_w(x)$, and true value, $y = f^*(x)$, to a "loss". Assuming,

Usually, the true relation is probabilistic. In this case, we're not interested in a deterministic relation $f^*$, but a probabilistic ground truth, given by some distribution, $q(x, y)$.

Formally, we're trying to find the weights, $\widehat w$, that minimize the expected risk ("generalization error") for some choice of loss function, $\ell: \mathcal Y \times \mathcal Y \to \mathbb R$,

We don't have direct access to the probability distribution, $P(X, Y)$, generating our data, so we approximate the expectation with an empirical average over a dataset $\mathbf D = \{(X_i, Y_i)\} _ {i=1}^n$ to get the empirical risk or "test loss". ² More accurately, we optimize $\widehat w$ on a training set, $\mathbf D_\text{train}$, but report performance on a test set, $\mathbf D_\text{test}$, to avoid sampling bias and overfitting, where $\mathbf D = \mathbf D_\mathrm{train} \cup \mathbf D_\mathrm{test}$ and $\mathbf D_\mathrm{train} \cap \mathbf D_\mathrm{test} = \emptyset$. ³

Footnotes

1. Equivalently, we could separately model the likelihood $p(x|y)$ and prior $p(y)$, then multiply to get the joint distribution. P.S. I prefer using $q$ and $p$ to mean the model and truth, respectively, but I'm keeping to the notation of Watanabe in Algebraic Geometry and Singular Learning Theory. ↩

2. Traditionally, statistical learning theory drops the explicit dependence on $w$, and instead looks at model selection at the level of $f \in \mathcal F$, $q \in \mathcal Q$. As we're interested in neural networks, we'll find it useful to fix a particular functional form of our model and look at selection of suitable parameters in $w$. Later, we'll see that the understanding the mapping $w \to f_w$ is at the heart of understanding why deep neural networks work as well as they do. ↩ ↩²

3. From Guedj [1]: "The past few decades have thus seen an increasing gap between the Bayesian statistical literature, and the machine learning community embracing the Bayesian paradigm – for which the Bayesian probabilistic model was too much of a constraint and had to be toned down in its influence over the learning mechanism. This movement gave rise to a series of works which laid down the extensions of Bayesian learning[.]" ↩ ↩² ↩³ ↩⁴

4. . TODO: Something something Safe Bayes ↩

NOTE: Work in Progress

How much do the models we train depend on the path they follow through weight space?

Should we expect to always get the same models for a given choice of hyperparameters and dataset? Or do the outcomes depend highly on quirks of the training process, such as the weight initialization and batch schedule?

If models are highly path-dependent, it could make alignment harder: we'd have to keep a closer eye on our models during training for chance forays into deception. Or it could make alignment easier: if alignment is unlikely by default, then increasing the variance in outcomes increases our odds of success.

Vivek Hebbar and Evan Hubinger have already explored the implications of path-dependence for alignment here. In this post, I want to take a step back and survey the literature on path-dependence in current models. I'll also share the results of a few experiments on simple datasets like MNIST.

Formalizing Path-dependence

Hebbar and Hubinger define path-dependence "as the sensitivity of a model's behavior to the details of the training process and training dynamics." Let's make that definition more precise. To start, let us formalize the learning process as a dynamical system over weight space.

In the context of machine learning, our goal is (usually) to model some "true" function $f^* : \mathcal X \to \mathcal Y$¹. To do this, we construct a neural network, $\mathcal F \ni f: \mathcal X \times \mathcal W \to \mathcal Y$, which induces a model of $f^*$ upon fixing a choice of weights, $w \in \mathcal W \subset \mathbb R^D$. For convenience, we'll denote the resulting model with a subscript, i.e., $f_{w}(x):= f(x, w)$.²

To find the weights, $w_\mathrm{opt}$, such that $f_\text{opt} := f_{w_\text{opt}}$ is as "close" as possible to $f^*$, we specify a loss function $L_n$, which maps a choice of parameters and a set of training examples, $\mathbf d_\text{train} = \{(x_{i},y_i)\}_{i=1}^n \in \mathcal Z^n$, to a scalar "loss"³:

For a fixed choice of dataset, we denote the empirical loss, $L_\text{train}(w) =L(w, \mathbf d_\text{train})$. Analogously, we can define a test loss, $L_\text{test}$ over a corresponding test set, and batch loss, $L^{(t)}(w)$, for a batch $\mathbf b^{(t)} \subset \mathbf d_\text{train}$. Next, we choose an optimizer, $\Phi$, which iteratively updates the weights (according to some variant of SGD),

The optimizer depends on hyperparameters, $h \in \mathcal H$, as well as some learning schedule $\mathbf b = \{\mathbf b^{(t)}\}_{t=1}^T$ of $T$ batches, $\mathbf b^{(t)} \in \boldsymbol{\mathcal B}$. There are $N_\text{epochs}$ epochs consisting of $T_\text{epochs}$ batches (i.e., $T/ T_\text{epochs} = N_\text{epochs}$). The learning schedule for epoch $\tau$ is the subset $\mathbf b = \{\mathbf b^{(t)}\}_{t=\tau T_\text{epochs}}^{\tau (T_\text{epochs} + 1) - 1}$. Within any given epoch, the batches are disjoint, but across epochs, repetition is allowed (though typically no batch will be repeated sample for sample).

Example: for Adam, $h=(\beta_1, \beta_2, \epsilon, \eta)$. These are, respectively, the momenta for the first moment and second moment of the gradients, a small term to ensure numerical stability, and the learning rate.

If we take the learning schedule and hyperparameters as constant, we obtain a discrete-time dynamical system over parameter space, which we denote $\Phi_{\mathbf b, h}: \mathcal W \to \mathcal W$.

Two Kinds of Path Dependence

Given this dynamical system over weight space, let us contrast two kind of path dependence:

1. Global path dependence. Given some distribution over starting weights, $p(w^{(0)})$, hyperparameters, $p(h)$, or batches, $p(\mathbf b)$, what is the resulting distribution over final weights, $p(w^{(T)})$?
2. Local path dependence. For some choice of initial weights, $w^0$, hyperparameters, $h$, or batches, $\mathbf b$, and a small perturbation to one of these values, how different (e.g., in terms of the l2 norm) are the final weights of the perturbed model from the baseline unperturbed model?

The former enquiry is concerned with finding (semi-)stable distributions while the latter is concerned with chaos (macroscopic sensitivity to microscopic perturbations in deterministic systems is the definition of chaos). Though we ultimately want to form global statements of path dependence, the distributions involved are generally intractable (thus require us to resort to empirical approximations).

In the local view, we rarely care about specific perturbations, so we end up studying the relation between a distribution over perturbations $p(\delta)$ and $p(w^{(T)})$, which is similarly intractable. Still, this is a much smaller space to explore, which makes it friendlier to investigation.

From Weight Space to Function Space

The problem with studying dynamics over $\mathcal W$ is that we don't actually care about $w \in \mathcal W$. Instead, we care about the evolution in function space, $\mathcal F$, resulting from the mapping $m: \mathcal W \ni w \mapsto f_{w}\in \mathcal F$.

This is become the mapping to function space is non-injective; the internal symmetries of $m$ ensure that different choices of $w\in \mathcal W$ can map to the same function $f \in \mathcal F$.[1] As a result, notions of similarity and distance in $\mathcal W$ can be misleading.

The difficulty with function space is that it is infinite-dimensional, which makes it that much more intractable than weight space. Though we have full knowledge of $\mathcal W$, we can't resolve exactly where we are in $\mathcal F$ with a finite set of samples. At best, we can resolve the level set in $\mathcal F$ with a certain empirical performance (like training/test loss). Without a better understanding of the mapping $m$, this leaves room for uncertainty between models that can perform wildly differently out-of-training or off-distribution.

On optimizer state: If we want to be exhaustive, let us recall that optimizers might have some internal state, $s \in \mathcal S$. E.g., for Adam, $s_{t}= (m_t, v_t)$, a running average of the first moment and second moment of the gradients, respectively. Then, the dynamical system over $\mathcal W$ is more appropriately a dynamical system over the joint space $\mathcal W \times \mathcal S$. Completing this extension will have to wait for another day; we'll ignore it for now for the sake of simplicity and because, in any case, $s_t$, tends to be a deterministic function of $\mathbf b$ and $h$.

Before, we run a few experiments, let's recap what the literature has to say on path-dependence so far.

Review

Evidence of Low Path Dependence

Internal Symmetries

Ainsworth, Hayase, and Srinivasa [2] find that, after correcting for permutation symmetries, different weights are connected by a close-to-zero loss barrier linear mode connection. In other words, you can linearly interpolate between the permutation-corrected weights, and every point in the linearly interpolation has essentially the same loss. They conjecture that there is only global basin after correcting for these symmetries.

In general, correcting for these symmetries is NP-hard, so the argument of these authors depends on several approximate schemes to correct for the permutations [2].

![400](/media/pasted-image-20221220152152.png)

Universal Circuits

Some of the most compelling evidence for the low path-dependence world comes from the circuits-style research of Olah and collaborators. Across a range of computer vision models (AlexNet, InceptionV1, VGG19, ResnetV2-50), the circuits thread [3] finds features common to all of them such as curve and high-low frequency detectors [4], branch specialization [5], and weight banding [6]. More recently, the transformer circuits thread [7] has found universal features in language models, such as induction heads and bumps [8]. This is path independence at the highest level: regardless of architecture, hyperparameters, and initial weights different models learn the same things. In fact, low path-dependence ("universality") is often taken as a starting point for research on transparency and interpretability [4].

Universal circuits of computer vision models [4].

ML as Bayesian Inference

• $P_\beta(f)$ is the probability that $M$ expresses $f$ on $D$ upon a randomly sampled parametrization. This is our "prior"; it's what our network expresses on initialization.

• $V_\beta(f)$ is a volume with Gaussian measure that equals $P_\beta(f)$ under Gaussian sampling of network parameters.

  • This is a bit confusing. We're not talking about a continuous region of parameter space, but a bunch of variously distributed points and lower-dimensional manifolds. Mingard never explicitly points out why we expect a contiguous volume. That or maybe it's not necessary for it to be contiguous

• $\beta$ denotes the "Bayesian prior"

• $P_\text{opt}(f|S)$ is the probability of finding $f$ on $E$ under a stochastic optimizer like SGD trained to 100% accuracy on $S$.

• $P_\beta(f|S) = \frac{P(S|f) P_\beta(f)}{P_\beta(S)},$ is the probability of finding $f$ on $E$ upon randomly sampling parameters from i.i.d. Gaussians to get 100% accuracy on $S$.

  • This is what Mingard et al. call "Bayesian inference"
  • $P(S|f)=1$ if $f$ is consistent with $S$ and $0$ otherwise

• Double descent & Grokking

• Mingard et al.'s work on NNs as Bayesian.

Evidence of High Path Dependence

• Why Comparing Single Performance Scores Does Not Allow to Conclusions About Machine Learning Approaches (Reimers et al., 2018)
• Deep Reinforcement Laming Doesn’t Work Yet (Irpan, 2018)
• BERTS of a feather do not flock together

Experiments

In section XX, we defined path dependence as about understanding the relation between $(P(B_t), P(W_0), P(H))$ and $(P(W_{T}), P(F_{T}))$. As mentioned, there are two major challenges:

1. In general, we have to estimate these distributions empirically, and training neural networks is already computationally expensive, so we're restricted to studying smaller networks and datasets.
2. The mapping $m:\mathcal W\to \mathcal F$ is non-straightforward because of the symmetries of $m$.

To make it easier for ourselves, let us restrict our attention to the narrower case of studying local path-dependence.

a (small) perturbation, $\epsilon$, to one of $(b_{t}, w_{0}, h)$. E.g., we'll study probability densities of the kind $p(\mathbf w_0)=\mathcal N(\mathbf w_{0}|\mathbf w_\text{baseline}, \epsilon \mathbf 1)$. For discrete variables (like the number of layers, network width, and batch schedule), there's a minimum size we can make $\epsilon$,

Within dynamical systems theory, there are two main ways to view dynamical systems:

1. The trajectory view studies the evolution of points like $(w_0, w_1, \dots, w_T)$ and $(f_1, f_2, \dots, f_T)$.
2. The probability view studies the evolution of densities like $(p_0(w), p_1(w), \dots, p_T(w))$ and $(p_1(f), p_2(f), \dots, p_T(f))$.

Both have something to tell us about path dependence:

1. In the trajectory view, sensitivity of outcomes becomes a question of calculating Lyapunov exponents, the rate at which nearby trajectories diverge/converge.
2. In the probability view, sensitivity of outcomes becomes a question of measuring autocorrelations, $\langle w_{i} w_{i+\tau}\rangle$ and $\langle f_{i} f_{i+\tau} \rangle$.

Tracking Trajectories

The experimental set-up involves taking some baseline model, $m_0$, then applying a Gaussian perturbation to the initial weights with norm $\epsilon$, to obtain a set of perturbed models $\{m_i\} _{i=1}^{n _\text{models}}$. We train these models on MNIST (using identical batch schedules for each model).

Over the course of training, we track how these models diverge via several metrics (see next subsection). For each of these, we study how the rate of divergence varies for different choices of hyperparameters: momentum $\beta$, weight decay $\lambda$, learning rate $\eta$, hidden layer width (for one-hidden-layer models), and number of hidden layers. Moving on from vanilla SGD, we compare adaptive variants like Adam and RMSProp.

TODO: Non-FC models. Actually calculate the rate of divergence (for the short exponential period at the start). Perform these experiments for several different batch schedules. Perturbations in batch schedule. Other optimizers besides vanilla SGD.

Measuring distance

• $d_\mathbf{w}^{(p)}(m_i, m_0)$: the $p$-norm between the weight vectors of each perturbed model and the baseline model. We'll ignore the $p$ throughout and restrict to the case $p=2$. This is the most straightforward notion of distance, but it's flawed in that it can be a weak proxy for distance in $\mathcal F$ because of the internal symmetries of the model.
• $\frac{d_{\mathbf w}(m_{i}, m_0)}{|\mathbf w_{0}|}$: the relative $p$-norm between weight vectors of each perturbed model.
• $L_\text{train,test}(m_i)$: the training/test losses
• $\delta L_\text{train, test}(m_{i}, m_0)$: the training/test loss relative (difference) to the baseline model $m_0$
• $f_\text{train, test}(m_i)$, $\delta f_\text{train, test}(m_i, m_0)$: the training/test set classification accuracy and relative classification accuracy.
• $L_\text{train cf., test cf.}$ and $f_\text{train cf., test cf.}$: same as above, but we take the predictions of the baseline model as the ground truth (rather than the actual labels in the test set).

A few more metrics to include:

• $d^\text{perm.}_{\mathbf w}$: the l2 norm after adjusting for permutation differences (as described in Ainsworth et al.)
• $\int_{\mathbf w_0}^{\mathbf w_{i}^\text{perm.}} L_\text{train (cf.), test (cf.)}(\mathbf w) d\mathbf w$. The loss integrated over the linear interpolation between two models' weights after correcting for permutations (as described in Ainsworth et al.)

Tracking Densities

TODO

Results

One-hidden-layer Models

What's remarkable about one-hidden-layer models is how little the model depends on weight initialization: almost all of the variance seems to be explained by the batch schedule. Even for initial perturbations of size $\epsilon=10$¹, the models appear to become almost entirely equivalent in function space across the entire training process. In the figure below, you can see that the differences in $L_\text{train}$ are imperceptible (both for a fixed $\epsilon$ and across averages over different $\epsilon$).

TODO: I haven't checked $\epsilon/|\mathbf w|$. I'm assuming this is >1 for $\epsilon=10$ (which is why I find this surprising), but I might be confused about PyTorch's default weight initialization scheme. So take this all with some caution.

The rate of growth for $d_\mathbf{w}$ has a very short exponential period (shorter than a single epoch), followed by a long linear period (up to 25 epochs, long past when the error has stabilized). In some cases, you'll see a slight bend upwards or downwards. I need more time to test over more perturbations (right now it's 10 perturbed models) to clean this up. Maybe these trends change over longer periods, and with a bit more time I'll test longer training runs and over more perturbations.

Hyperparameters

• Momentum: ($\beta=0.1, 0.5, 0.9$) The $d_\textbf w$ curves look slightly more curved upwards/exponential but maybe that's confirmation bias (I expect momentum to make divergence more exponential back when I expected exponential divergence). Small amounts of momentum appear to increase convergence (relative to other models equivalent up to momentum), while large amounts increase divergence (towards . For very small amounts, the effect appears to be negligible. Prediction: the $d_w$ curves curve down because in flat basins, momentum slows you down.
• Learning rate: Same for $\eta=10^{-3}, 10^{-2}, 10^{-1}$. (Not too surprising) TODO: Compare directly between different learning rates. Can we see $\eta$ back in the slope of divergence? Prediction: This should not make much of a difference. I expect that correcting for the learning rate should give nearly identical separation slopes.
• Weight Decay: TODO for $\lambda=10^{-3}, 10^{-2}, 10^{-1}$. Prediction: $d_w$ will shrink (because $|w|$ will shrink). The normalized $d_w/|w|$ will curve downwards because we break the ReLU-scaling symmetry which means the volume of our basins will shrink
• Width: TODO. Both this and depth require care. With different sizes of $\mathbf w$, we can't naively compare norms. Is it enough to divide by $\dim \mathbf w$? Prediction: I expect the slope of divergence to increase linearly with the width of a one-layer network (from modeling each connection as separating of its own linear accord).
• Depth: TODO. Prediction: I expect the shape of $d_w$ for each individual layer to become more and more exponential with depth (because the change will be the product of layers that diverge linearly independently). I expect this to dominate the overall divergence of the networks.
• Architecture: Prediction: I expect convolutional architectures to decrease the rate of separation (after correcting for the number of parameters).
• Optimizer:
  • Prediction: I expect adaptive techniques to make the rate of divergence exponential.

Datasets

• Computer Vision
  • MNIST
  • Fashion-MNIST
  • Imagenet: Prediction: I expect Imagenet to lead to the same observations as MNIST (after correcting for model parameter count).
• Natural Language
  • IMDb movie review database

Why Linear?

I'm not sure. My hunch going in was that I'd see either exponential divergence (indicating chaos) or square root divergence (i.e., Brownian noise). Linear surprises me, and I don't yet know what to make of it.

Maybe all of this is just a fact about one-hidden-layer networks. If each hidden layer evolves independently linearly, maybe this combines additively into something Brownian. Or maybe it's multiplicative (so exponential).

Deep Models

TODO

Appendix

Weight Initialization

For ReLU-based networks, we use a modified version of Kaiming (normal) initialization, which is based on the intuition of Kaiming initialization as sampling weights from a hyperspherical shell of vanishing thickness.

Kaiming initialization is sampling from a hyperspherical shell

Consider a matrix, $\mathbf w^{(l)}$, representing the weights of a particular layer $l$ with shape $(D_\mathrm{in}^{(l)}, D_\mathrm{out}^{(l+1)})$. $D_\mathrm{in}^{(l)}$ is also called the fan-in of the layer, and $D_\mathrm{in}^{(l+1)}$ the fan-out. For ease of presentation, we'll ignore the bias, though the following reasoning applies equally well to the bias.

We're interested in the vectorized form of this matrix, $\vec w^{(l)} \in \mathbb R^{D^{(l)}}$, where $D^{(l)} =D_\mathrm{in}^{(l)} \times D_\mathrm{out}^{(l+1)}$.

In Kaiming initialization, we sample the components, $w_i^{(l)}$, of this vector, i.i.d. from a normal distribution with mean 0 and variance $\sigma^2$ (where $\sigma^2 = \frac{2}{D_\mathrm{in}^{(l)}}$).

Geometrically, this is equivalent to sampling from a hyperspherical shell, $S^{D-1}$ with radius $\sqrt{D}\sigma$ and (fuzzy) thickness, $\delta$.

This follows from some straightforward algebra (dropping the superscript $l$ for simplicity):

and

So the thickness as a fraction of the radius is

where the last equality follows from the choice of $\sigma$ for Kaiming initialization.

This means that for suitably wide networks ($D_\mathrm{in}^{(l)} \to \infty$), the thickness of this shell goes to $0$.

Taking the thickness to 0

This suggests an alternative initialization strategy: sample directly from the boundary of a hypersphere with radius $\sqrt{D}\sigma$, i.e., modify the shell thickness to be $0$.

This can easily be done by sampling each component from a normal distribution with mean 0 and variance $1$ and then normalizing the resulting vector to have length $\sqrt{D}\sigma$ (this is known as the Muller method).

Perturbing Weight initialization

Naïvely, if we're interested in a perturbation analysis of the choice of weight initialization, we prepare some baseline initialization, $\mathbf w_0$, and then apply i.i.d. Gaussian noise, $\boldsymbol \delta$, to each of its elements, $\delta_i \sim \mathcal N(0, \epsilon^2)$.

The problem with this is that the perturbed weights $\mathbf w = \mathbf w_0 + \boldsymbol\delta$ are no longer sampled from the same distribution as the baseline weights. In terms of the geometric picture from the previous section, we're increasing the thickness of the hyperspherical shell in the vicinity of the baseline weights.

There is nothing wrong with this per se, but it introduces a possible confounder (the thickness).

The modification we made to Kaiming initialization was to sample directly from the boundary of a hypersphere, rather than from a hyperspherical shell. This is a more natural choice when conducting a perturbation analysis, because it makes it easier to ensure that the perturbed weights are sampled from the same distribution as the baseline weights.

Geometrically, the intersection of a hypersphere $S^D$ of radius $w_0=|\mathbf w_0|$ with a hypersphere $S^D$ of radius $\epsilon$ that is centered at some point on the boundary of the first hypersphere, is a lower-dimensional hypersphere $S^{D-1}$ of a modified radius $\epsilon'$. If we sample uniformly from this lower-dimensional hypersphere, then the resulting points will follow the same distribution over the original hypersphere.

This suggests a procedure to sample from the intersection of the weight initialization hypersphere and the perturbation hypersphere.

First, we sample from a hypersphere of dimension $D-1$ and radius $\epsilon'$ (using the same technique we used to sample the baseline weights). From a bit of trigonometry, see figure below, we know that the radius of this hypersphere will be $\epsilon' = w_0\cos \theta$, where $\theta = \cos^{-1}\left(1-\frac{\epsilon^2}{2w_0^2}\right)$.

Next, we rotate the vector so it is orthogonal to the baseline vector $\mathbf w_0$. This is done with a Householder reflection, $H$, that maps the current normal vector $\hat{\mathbf n} = (0, \dots, 0, 1)$ onto $\mathbf w_0$:

where

and $\hat{\mathbf w}_0 = \frac{\mathbf w_0}{|w_0|}$ is the unit vector in the direction of the baseline weights.

Implementation note: For the sake of tractability, we directly apply the reflection via:

Finally, we translate the rotated intersection sphere along the baseline vector, so that its boundary goes through the intersection of the two hyperspheres. From the figure above, we find that the translation has the magnitude $w_0' = w_0 \cos \theta$.

By the uniform sampling of the intersection sphere and the uniform sampling of the baseline vector, we know that the resulting perturbed vector will have the same distribution as the baseline vector, when restricted to the intersection sphere.

Dynamical Systems

Formally, a dynamical system is a tuple $(\mathcal T, \mathcal M, \Phi)$, where $\mathcal T$ is the "time domain" (some monoid), $\mathcal M$ is the phase space over which the evolution takes place (some manifold), and $\Phi$ is the evolution function, a map,

that satisfies, $\forall x \in \mathcal M, \forall t_{1}, t_{2}\in \mathcal T$,

⁴

Informally, we're usually interested in one of two perspectives:

1. Trajectories of individual points in $\mathcal M$, or
2. Evolution of probability densities over $\mathcal M$.

The former is described in terms of differential equations (for continuous systems) or difference equations (for discrete systems), i.e.,

or

The latter is described in terms of a transfer operator:

Both treatments have their advantages: the particle view admits easier empirical analysis (we just simulate a trajectory), while the latter

In terms of the former, path-sensitivity becomes the question of chaos: do nearby

Lyapunov spectrum

The Lyapunov exponent $\lambda$ quantifies the rate of separation of infinitesimally close trajectories:

If the exponent is positive, then nearby trajectories will diverge, and the dynamics are chaotic. If the exponent is negative, then nearby trajectories will converge

For a $D$-dimensional system, there are $D$ Lyapunov exponents. We often focus exclusively on the maximal Lyapunov exponent because it dominates the overall rate of separation between two neighboring trajectories. However, the full spectrum contains valuable additional information like the rate of entropy production, the fractal dimension, the Hausdorff dimension, and the Lyapunov dimension.

The first major limitation is that the full Lyapunov spectrum is intractable for large $D$. The other major limitation is that the Lyapunov spectrum requires a suitable norm. We can use the l2 norm in $\mathcal W$, but as we already saws what we really care about is measuring distance in $\mathcal F$ with some metric $d : \mathcal F \times \mathcal F \to \mathbb R$.

One option would be to repurpose the loss function $\ell$:

Here, we treat $f_2(x_i)$ as the truth, and use the empirical risk as our distance metric. We could define an analogous distance over either the train or test set. As long as $\ell$ is a suitable metric (or easily converted into a metric through, e.g., symmetrization), $d$ will be too.

This suffers a major downside that two functions will be seen as identical as long as they have the same performance on the dataset in question. They can have totally different performance on unseen examples. Devising suitable distance metrics for neural networks requires more work.

Autocorrelations

The autocorrelation of a random process $\{X_t\}$ is the correlation between two values of that process at different times,

For stationary processes (where $\langle X_t\rangle$ is independent of $t$), this becomes a function of one variable, $\tau=t_2-t_1$,

In the case of training, the dynamics aren't stationary: learning rate schedules and the the "descent" of gradient descent ensures that these correlations will depend on our choice of starting time. However, we're not typically interested in correlations between later time steps. We care about autocorrelations relative to the starting point $t_1=0$.

In practice, the probabilistic and point-wise views are intimately connected: the relevant autocorrelation timescales can often be directly related to the maximal Lyapunov component. These two formulas are only a small sample of the available tooling.

$\mathcal F$ is the space of $p$-integrable functions, $f_w \in \mathcal F$ iff

which is equipped with a metric,

So we exchange evolution over a finite-dimensional $\mathcal W$ with an infinite-dimensional

Footnotes

1. For regression, $\mathcal Y = \mathbb R^N$, for classification, $\mathcal Y \subset \mathbb N$, for self-supervised tasks, we're often interested in $\mathcal Y = \mathcal X$, etc. ↩ ↩²

2. For convenience, we'll start by ignoring model hyperparameters. You can view this as either subsuming the hyperparameters into the weights, into the optimizer, or into our choice of $f$. Later, it'll be useful to separate out hyperparameters (i.e., $f: \mathcal X \times \mathcal Y \times \mathcal H \to \mathcal Y$). ↩

3. A quick note on notation: Often, you'll see the dataset denoted with a capital $D$. Here, we're using a lowercase because it'll be useful to treat $\mathbf d$ as an instance of a random variable $\mathbf D$. Similarly for $x$, $y$, and $w$ ($X$, $Y$, and $W$). Even though $x$, $y$, and $w$ are (typically) all vectors, we'll reserve boldface for sets. TODO: Maybe just bite the bullet and bold all of them. ↩

4. It's possible to generalize this further so that $\Phi : U \subseteq (\mathcal T \times \mathcal M) \to \mathcal M$, but this won't be necessary for us. ↩

NOTE: Work in Progress

Outline

• Warm-up: MSE & bias-variance trade-offs.
• Generalization = Simplicity.
  • Solomonoff induction,
  • Complexity measures
    • BIC/MDL, AIC
    • VC dimension & structural risk minimization
    • Rademacher complexity
• Early Stopping
  • NTK
• Problems:
  • Vacuous bounds (Zhang et al. 2017). Always zero training error. Any optimizer (even stupid ones). Crazily convex loss spots. Even with regularization
• From functions to probabilities
  • Gibbs measure
  • PAC-Bayes bounds
    • NNs Dziugaite & Roy 2017
  • Singular learning theory, WAIC
• Mingard-style “Bayesian inference”

Misc:

• SGD & Basin broadness
• Heavy-tailed random matrix theory (implicit self-regularization)
• Double descent & grokking
• Recent Anthropic work It’s non-obvious that (l2) regularization chooses simpler functions in NNs. (Polynomial regression is one thing).

"Regular" learning theory (RLT) predicts that overparametrized deep neural networks (DNNs) should overfit. In practice, the opposite happens: deeper networks perform better and generalize further. What's going on?

The consensus is still out, but different strands of research appear to be converging on a common answer: DNNs don't overfit because they're not actually overparametrized; SGD and NN's symmetries favor "simpler" models whose effective parameter counts are much lower than the externally observed parameter count. Generality comes from a kind of internal model selection where neural networks throw out unnecessary expressivity.

In this post, I'll make that statement more precise. We'll start by reviewing what RLT has to say about generalization and why it fails to explain generalization in DNNs. We'll close with a survey of more recent attempts at the learning theory of DNNs with particular emphasis on "singular" learning theory (SLT).

Intro to Statistical Learning Theory

Before we proceed, we need to establish a few definitions. Statistical learning theory is often sloppy with its notation and assumptions, so we have to start at the basics.

In this post, we'll focus on a (self-)supervised learning task. Given an input $x \in \mathcal X$, we'd like to predict the corresponding output $y \in \mathcal Y$. This relationship is determined by an unknown "true" pdf $q(z) = q(x, y)$ over the joint sample space $\mathcal Z = \mathcal X \times \mathcal Y$.

If we're feeling ambitious, we might directly approximate the true joint distribution with a generative model $p(x, y|w)$ that is parametrized by weights $w \in \mathcal W \subseteq \mathbb R^D$. If it's tractable, we can marginalize this joint distribution to obtain the marginal and conditional distributions. ¹

If we're feeling less ambitious, we might go ahead with a discriminative model of the conditional distribution, $p(y| x, w)$. (In the case of regression and classification, we're interested in inferring target values and labels from future samples, so we may not care all that much about $q(x)$ and $q(x|y)$.)

And if we're feeling unambitious (as most machine learning theorists are), it may be enough to do direct inference with a discriminant function — i.e., to find a deterministic function that maps inputs to outputs, $f_w: \mathcal X \to \mathcal Y$.²

In the case of regression, this is justified on the (only occasionally reasonable) assumption that the error is i.i.d. sampled from a Gaussian distribution. In other words, the discriminative model is defined in terms of $f$ as:

Machine learning usually begins with discriminant functions. Not only is this often easier to implement, but it offers some additional flexibility in the kinds of functions we can model because we optimize arbitrary loss functions that are unmoored from Bayesian-grounded likelihoods or posteriors.³

This flexibility comes at a cost: without the theoretical backing, it's more difficult to reason systematically about what's actually going on. The loss functions and regularizers of machine learning often end up feeling ad hoc and unsupported because they are. Or at least they will be until section 3.

As a result, we'll find it most useful to work at the intermediate level of analysis, in terms of discriminant models.

What Is Learning, Anyway?

The strength of the Bayesian framing is that for some prior over weights, $\phi(w)$, and a dataset $\mathbf d^{(n)} \in \mathcal Z^n$ of samples $\{(x_i, y_i)\}_{i=1}^n$, we can "reverse" the likelihood (assuming each sample is sampled i.i.d. from $p(x, y)$),

to obtain the a posteriori distribution,

where $Z_n$ is the evidence (or partition function),

The aim of "learning" is to make our model $p(y|x, w)$ as "close" as possible to the truth $q(y|x)$.

In the probabilistic formulation, the natural choice of "distance" is the Kullback-Leibler divergence (which is not actually a distance):

where the second equality follows from defining $q(x, y|w) = q(y|x, w) \cdot p(x)$.

Formally, the aim of learning is to solve the following:

We say $p(y|x)$ is realizable iff $K(w^*) = 0$, in which case we call $w^*$ the "true" parameters.

At this point, we run into a bit of a problem: we can't actually compute the expectations $\langle \cdot\rangle_{X, Y}$ since we don't know $p(x, y)$ (and even if we did, the integration would likely be intractable). Instead, we have to resort to empirical averages over a dataset,. ³

Maximum Likelihood Estimation is KL-Divergence Minimization

Example: Regression & Mean-Squared Error

Fortunately, there's a more general and principled way to recover discriminant models from discriminant functions than the assumption of isotropic noise, as long as we're willing to relax Bayes' rule.

First, we introduces a parameter $\beta \geq 0$ that controls the tradeoff between prior and likelihood to obtain the tempered Bayes update [1],⁴

$p_\beta(w|\mathbf d) \propto p(\mathbf d| w)^{\beta}p(w),$

where $\mathbf d$ is a dataset of samples $\{(x_{i},y_{i})\}_{i=1}^n$, and the likelihood is obtained by assuming each sample is distributed i.i.d. according to $p(x_{i}, y_{i}|w)$ s.t. $p(\mathbf d|w) = \prod_{i=1}^{n}p(x_{i}, y_{i}|w)$.

Next, we replace the tempered likelihood with a general loss function

The real-world is noisy, and pure function approximation can't account for this.

To remedy this, it's common to model any departure from our deterministic predictions, $\hat y = f_w(x)$, as isotropic noise, e.g., $q(y|x, w) = \mathcal N(y| f_w(x), \sigma^2)$.

Physically, we may expect the underlying process to be deterministic (given by a "true" function $f^*$) with noise creeping in through some unbiased measurement error $\epsilon \sim \mathcal N(0, \sigma^2)$.

For Gaussian noise, the NLL works out to:

Assuming isotropic Gaussian noise in a regression setting, we see that MLE simplifies to minimizing the mean squared error (up to some overall constant and scaling).

To make MLE more Bayesian, you just multiply the likelihood by some prior over the weights, to obtain maximum a posteriori estimation (MAP): $p(w|\mathbf d) \propto p(\mathbf d|w)\phi(w).$ If we enforce a gaussian prior with precision $\alpha$, the loss gains a regularization term (weight decay), $\frac{\alpha}{2}w^T w$ to the loss function. [2]

Gibbs Generalization Error

Todo

What Is Generalization, Anyway?

Consider the empirical probability distribution,

where $\delta(\cdot)$ is a delta function appropriate to the sample space.

Although this will converge to the true distribution as $N\to\infty$, for any finite $N$, we encounter sampling error. This problem is particularly pronounced for unseen samples: $q_D(z)$ may (and almost always does) assign zero probability to samples that have non-zero probability under the true distribution.

The fundamental challenge of generalization is to make predictions about these unseen samples. Let's make this more precise.

Given some loss function $\ell: Y \times Y \to \mathbb R$, we're interested in how $\ell$ performs on future samples, as measured by the expected risk or generalization error,

However, we can only estimate this performance on on the available dataset via the empirical risk,

where $\overline \cdot$ denotes an empirical average over the dataset, $\mathbf d$.

Our problem is that the true generalization error is unknowable. So, in practice, we split our dataset into a training set, $\mathbf s$, and test set, $\mathbf e$, respectively. We learn our parameters $w$ via the training set, and then estimate the generalization error on the test set. That's where we encounter our first major confusion.³

You see, besides the generalization error, there's the distinct notion of the generalization gap,

Whereas generalization error is about absolute performance on the true distribution, the generalization gap is about relative performance between the training and test sets. Generalization error combines both "performance" and "transferability" into one number, while the generalization gap is more independent of "performance" — past a certain threshold, any amount of test-set performance is compatible with both a low and high generalization gap.

For the remainder of this post, I'll focus on the generalization gap. It's not absolute performance we're interested in: universal approximation theorems tell us that we should expect excellent training performance for neural networks. The less obvious claim is why this performance should transfer so well to novel samples.

---

Yes, more data means better generalization, but that's not what we're talking about.

In the limit $N\to \infty$, the empirical risk converges to expected risk, and both generalization error and gap will fade away: $\epsilon_g \to 0,\quad \epsilon_g^2 \to 0 \quad \text{as} \quad N \to \infty.$ So obviously the larger datasets that have accompanied the deep learning boom explain some of the improvement in generalization.

PAC Learning

Established by Valiant (1984) [3], Probably Approximately Correct (PAC) learning establishes upper bounds for the risk $I[f]$. In its simplest form, it states that, for any choice of $\epsilon$ ("probably") a predictor, $f$, will have its risk bounded by some $\delta$ ("approximately correct"):

Originally, PAC learning included the additional assumption that the predictor was polynomial in $N$ and $1/\epsilon$, but this has been relaxed to refer to any bound holding with high probability.

Still, it's not a full explanation as typical networks can easily memorize the entire training set (even under random labelings [4]).

---

MSE & Bias-variance tradeoff

In the case of isotropic noise (where our loss function is the MSE), the generalization error of a model is:

In other words, it is the (l2) distance between our predictions and the truth averaged over the true variables $X \times Y$. The bias-variance decomposition splits the generalization error into a bias term,

which measures the average difference between predictions and true values, a variance term,

which measures the spread of a model's predictions for a given point in the input space, and an irreducible error due to the inherent noise in the data. (For Gaussian noise, the irreducible error is $\sigma^2$.)

In order to achieve good generalization performance, a model must have low bias and low variance. This means that the model must be complex enough to capture the underlying patterns in the data, but not so complex that it overfits the data and becomes sensitive to noise. In practice, these two forces are at odds, hence "tradeoff."

---

Generalization is about simplicity

A common assumption across the entire statistical learning theory literature is that of simple functions generalizing better. It's worth spending a second to understand why we should expect this assumption to hold.

Occam's Razor

"Entities must not be multiplied beyond necessity".

Occam's razor is the principle of using the simplest explanation that fits the available data. If you're reading this, you probably already take it for granted.

Solomonoff Induction

Algorithmic complexity theory lets us define a probability distribution over computable numbers,

$p(x)= \sum_{p}2^{-K(p)},$ where $K(\cdot)$ is the (prefix) Kolmogorov complexity. The probability of any given number is the probability that a uniform random input tape on some Universal Turing Machine outputs that number. Unfortunately, the halting problem makes this just a tad uncomputable. Still, in principle, this allows a hypercomputer to reason from the ground up what the next entry in a given sequence of numbers should be.

Bayesian/Akaike Information Criterion

One of the main strengths of the Bayesian frame is that it lets enforce a prior $\varphi(w)$ over the weights, which you can integrate out to derive a parameter-free model:

One of the main weaknesses is that this integral is often almost always intractable. So Bayesians make a concession to the frequentists with a much more tractable Laplace approximation (i.e., you approximate your model as quadratic/gaussian in the vicinity of the maximum likelihood estimator (MLE), $w^{(0)}$):

where $I(w)$ is the Fisher information matrix:

From this approximation, a bit more math gives us the Bayesian information criterion (BIC):

The BIC (like the related Akaike information criterion) is a criterion for model selection that penalizes complexity. Given two models, the one with the lower BIC tends to overfit less (/"generalize better").

That is, simpler models (with fewer parameters) are more likely in approximate Bayesian inference. We'll see in the section on singular learning theory that the BIC is unsuitable for deep neural networks, but a generalized version, the Widely Applicable Bayesian Information Criterion (WBIC) will pick up the slack.

Minimum Description Length

The BIC is formally equivalent to MDL. TODO

Maximum Entropy Modeling

TODO

Classic Learning Theory

As we've seen in the previous section, the question of how to generalize reduces to the question of how to find simple models that match the data.

In classical learning theory, the answer to this is easy: use fewer parameters, include a regularization term, and enforce early stopping. Unfortunately, none of these straightforwardly help us out with deep neural networks.

For one, double descent tells us that the relation between parameter count and generalization is non-monotonic: past a certain number of parameters, generalization error will start decreasing. Moreover, a large number of the complexity measures we've seen are extensive (they scale with model size). That suggests they're not suited to the task.

As for regularization, it gets more complicated. That regularization on polynomial regression leads to simpler functions is straightforward. That regularization on deep neural networks leads to simpler models is less obvious. Sure, a sparse l1 regularizer that pushes weights to zero seems like it would select for simpler models. But a non-sparse l2 regularizer? Linking small parameters to simple functions will require more work. A deeper problem is that DNNs can memorize randomly labeled data even with regularizers [5]. Why then, do DNNs behave so differently on correctly labeled (/well-structured) data

Other forms of regularization like dropout are more understandable: they explicitly select for redundancy which collapses the effect parameter count.

Finally, early stopping doesn't seem to work with the observation of grokking: in certain models, training loss and test loss may plateau (at a poor generalization gap) for many epochs before training loss suddenly sharply decreasing (towards a much better generalization gap).

SGD Favors Flat Minima

• $P_\beta(f)$ is the probability that $M$ expresses $f$ on $D$ upon a randomly sampled parametrization. This is our "prior"; it's what our network expresses on initialization.
• $V_\beta(f)$ is a volume with Gaussian measure that equals $P_\beta(f)$ under Gaussian sampling of network parameters.
  • This is a bit confusing. We're not talking about a continuous region of parameter space, but a bunch of variously distributed points and lower-dimensional manifolds. Mingard never explicitly points out why we expect a contiguous volume. That or maybe it's not necessary for it to be contiguous
• $\beta$ denotes the "Bayesian prior"
• $P_\text{opt}(f|S)$ is the probability of finding $f$ on $E$ under a stochastic optimizer like SGD trained to 100% accuracy on $S$.
• $P_\beta(f|S) = \frac{P(S|f) P_\beta(f)}{P_\beta(S)},$ is the probability of finding $f$ on $E$ upon randomly sampling parameters from i.i.d. Gaussians to get 100% accuracy on $S$.
  • This is what Mingard et al. call "Bayesian inference"
  • $P(S|f)=1$ if $f$ is consistent with $S$ and $0$ otherwise I.e.: Hessians with small eigenvalues.

Flat minima seem to be linked with generalization:

• Hochreiter and Schmidhuber, 1997a; Keskar et al., 2016; Jastrzebski et al., 2018; Wu et al., 2017; Zhang et al., 2018; Wei and Schwab, 2019; Dinh et al., 2017.

SGD

Problems:

• Suitable reparametrizations can change flatness without changing computation.

Initialization Favors "simple" functions

Mingard 2021

• Levin et al. tell us that many real-world maps satisfy $P(f) \lesssim 2^{-b\tilde K(f)+a}$, where $\hat K$ is a computable approximation of the true Kolmogorov complexity $K(f)$.
• Empirically, maps of the form $f:\{0, 1\}^n \to \{0, 1\}$ satisfy a similar upper bound using a computable complexity measure (CSR).
• This is an upper bound, not more than that!
• The initialization acts as our prior in Bayesian inference.

SGD Performs Hidden Regularization

Mingard 2020

1. **Bayesian inference preserves the "simplicity" of the prior.
2. SGD performs a kind of "Bayesian inference"
   • You can approximate $P_\beta(f)$ with Gaussian Processes.
   • Mingard's main result is that $P_\text{opt}(f|S) \approx P_\beta(f|S)$ appears to hold for many datasets (MNIST, Fashion-MNIST, IMDb movie review, ionosphere), architectures (Fully connected, Convolutional, LSTM),  optimizers (SGD, Adam, etc.), training schemes (including overtraining) and optimizer hyperparameters (e.g. batch size, learning rate).
   • Optimizer hyperparameters matter much less than $P_\beta(f|S)$

Singular Learning theory

Glossary

• $f^*$ is the true function
• $f$ is some implemented function
• $M$ is our neural network
• $D$ is a dataset of pairs $\{(x_i, y_i)\}_{i=1}^N$
• $S, E \subset D$ are the training & test sets, respectively.

Learnability

• PAC in original formulation: simpler functions are easier to learn (polynomial time)

Usually, the true relation is probabilistic. In this case, we're not interested in a deterministic mapping $f^*$ from elements of $\mathcal X$ to elements $\mathcal Y$, but a probability distribution, $q(x, y)$, which relates random variables $X$ and $Y$ (where $\mathcal X$ and $\mathcal Y$ are the associated sample spaces).

We don't have direct access to $q(x, y)$, but we do have access to a dataset of samples, $\mathbf D = \{(X_i, Y_i)\} _ {i=1}^n$, which is itself a random variable. We specify some loss function, $\ell$, $\mathcal Y \times \mathcal Y \to\mathbb R$, which maps a prediction, $\hat y = f_w(x)$, and true value, $y = f^*(x)$, to a "loss". Assuming,

Usually, the true relation is probabilistic. In this case, we're not interested in a deterministic relation $f^*$, but a probabilistic ground truth, given by some distribution, $q(x, y)$.

Formally, we're trying to find the weights, $\widehat w$, that minimize the expected risk ("generalization error") for some choice of loss function, $\ell: \mathcal Y \times \mathcal Y \to \mathbb R$,

We don't have direct access to the probability distribution, $P(X, Y)$, generating our data, so we approximate the expectation with an empirical average over a dataset $\mathbf D = \{(X_i, Y_i)\} _ {i=1}^n$ to get the empirical risk or "test loss". ² More accurately, we optimize $\widehat w$ on a training set, $\mathbf D_\text{train}$, but report performance on a test set, $\mathbf D_\text{test}$, to avoid sampling bias and overfitting, where $\mathbf D = \mathbf D_\mathrm{train} \cup \mathbf D_\mathrm{test}$ and $\mathbf D_\mathrm{train} \cap \mathbf D_\mathrm{test} = \emptyset$. ³

Footnotes

1. Equivalently, we could separately model the likelihood $p(x|y)$ and prior $p(y)$, then multiply to get the joint distribution. P.S. I prefer using $q$ and $p$ to mean the model and truth, respectively, but I'm keeping to the notation of Watanabe in Algebraic Geometry and Singular Learning Theory. ↩

2. Traditionally, statistical learning theory drops the explicit dependence on $w$, and instead looks at model selection at the level of $f \in \mathcal F$, $q \in \mathcal Q$. As we're interested in neural networks, we'll find it useful to fix a particular functional form of our model and look at selection of suitable parameters in $w$. Later, we'll see that the understanding the mapping $w \to f_w$ is at the heart of understanding why deep neural networks work as well as they do. ↩ ↩²

3. From Guedj [1]: "The past few decades have thus seen an increasing gap between the Bayesian statistical literature, and the machine learning community embracing the Bayesian paradigm – for which the Bayesian probabilistic model was too much of a constraint and had to be toned down in its influence over the learning mechanism. This movement gave rise to a series of works which laid down the extensions of Bayesian learning[.]" ↩ ↩² ↩³ ↩⁴

4. . TODO: Something something Safe Bayes ↩