Singular Learning Theory: Basics

Notation

The Learning Problem

Setup. A learning problem is a triple $(p,q,\varphi)$:

• $p$: a model, a distribution on $\X$ for each parameter setting;
• $q$: what we want to learn;
• $\varphi$: a prior, our best guess as to which $w\in W$ gives us the lowest loss.

A Bayesian learning machine outputs a distribution on $W$, having seen a dataset $\Dn$:

The numerator is the likelihood function on $W$. Note that here we vary $w$ and not $x$.

We are interested in the loss landscape, i.e. what happens when we vary $w$? What does the geometry look like?

The loss landscape factorizes

Now note that $K(w)=\KL(q\,\|\,\pw)$ trivially factorizes as

$\Psi$ takes $w$ and gives a distribution. $\eta$ measures how far this distribution is from $q$.

• $\eta$ is a “nice map”: no degeneracies, convex, a unique zero at $q$. It knows nothing about the model.
• $\Psi$ is where the weird geometry lives, but it has nothing to do with $q$.

The posterior in terms of $K_n$

A Bayesian learning machine averages over the posterior:

The Log-Likelihood and First Geometry

The score (the $w$-derivative of $\ell$)

Mean zero property. We have

Population loss and $K$

Recall

so

Hence

and

Relating empirical and population quantities

Recall :

$K(w)$ vanishes up to second order

Let $W\subset\R^d$ be the parameter space. Consider

Taylor expand in $\delta$ at $\delta=0$. Denote $p_w=\pw$ and $p_{w+\delta}=p(\,\cdot\,|w+\delta)$:

Therefore

We call

the Fisher information matrix. If $p=q$, i.e. $w=\ws$, then $-\E_q[\gr^2_w\log p(x|\ws)]=\gr^2_w K(\ws)$ (see ).

Fisher Information

Geometry of Fisher

Consider the setting $\ws\in\Wz$, so that $p(x|\ws)=q(x)$. Then recall

On $\Wz$, $I(w)$ is the curvature of $K$. Consequently (recall from that the first two terms vanish)

Geometrically, consider $\{w\in W\mid K(w)<\eps\}$. This is an ellipsoid

whose semi-axes have lengths $\sqrt{2\eps/\kappa_j}$, determined by the eigenvalues $\kappa_j$ of $I$. ($I(w)$ is positive semi-definite, so all eigenvalues are $\ge 0$.) See .

• $\kappa_1$, the largest eigenvalue: travel along the corresponding eigenvector and the loss quickly grows, so the distributions become distinguishable.
• $\kappa_2$, a small eigenvalue: travel along the corresponding eigenvector and you can do so for a long time before the loss exceeds $\eps$.

Singular and Regular Models

Note that $I(w)\ge 0$ for all $w$; (2) is a strictness claim. When $I(w)=0$, it indicates flatness in $K$.

Moving $w$ in the direction $v$ does not change the log-likelihood, i.e. it is a degenerate direction in the loss landscape.

Three simple examples of different kinds of degeneracies ().

1. Redundant parameterization. Let $W=[-1,1]^2$, $w\mapsto p(\,\cdot\,|a,b)=\N(a+b,1)$, $q=\N(0,1)$. Then the direction $v=\binom{1}{-1}$ has $v\cdot s\equiv 0$. Indeed
   $$\Wz=\{w\mid K(w)=0\}=\{a+b=0\},$$
   so moving along $\binom{1}{-1}$ has no effect. This degeneracy is fixed by just quotienting out the redundant parameter, though.
2. Reparameterization. Consider $W=[-1,1]$, $p(x|w)=\N(w^3,1)$, $q\sim\N(0,1)$. Again
   $$\Wz=\{w\in W\mid K(w)=0\}=\{w^3=0\}.$$
   But $\frac{\partial}{\partial w}w^3=3w^2$, which is $0$ at $w=0$, so $I(0)=0$. Simply setting $u=w^3$ removes this degeneracy, though.
3. Genuine singularities. A degenerate fibre structure with no rescue via smooth transformations. This is where we want to focus!

Examples of singularities

Setup. Throughout, $q\sim\N(0,1)$, $W=[-1,1]^2$, $\varphi$ uniform, and

The parameter–function map just takes $w$, computes $\mu(w)$, some function of $w$, and uses it as the mean of $\N(\mu,1)$. Therefore

RLCT and LLC

We saw in that $I(w)$ fails to estimate $K$ near $\ws$ when there are degeneracies (flat directions that grow slower than quadratically). Instead we consider the volume of the sublevel set

Some intuition

Recall that the posterior mass is ()

In what follows we replace $K_n$ by $K$. In general $n(K_n-K)=O_p(\sqrt n)$, but relative finite variance makes it $O_p(1)$ on the set $\{K\lesssim 1/n\}$, which is the only region that matters below.

Now observe that if $K(w)>1/n$, then $e^{-nK(w)}<e^{-n\cdot\frac1n}=e^{-1}$. Indeed, as $K(w)$ increases, $e^{-nK(w)}\to 0$. Conversely, as $K(w)\to 0$, $e^{-nK(w)}\to 1$.

Now let $\ws\in\Wz$ and consider a unit vector $u\in\R^d$ and $t<\delta$ small. The question we've been asking over and over again is: what does $K(\ws+tu)$ look like? When $I(\ws)$ is non-degenerate we can use it to estimate this up to order 2, but as we saw, this fails if $K$ vanishes up to order 2 but still contains quartic or higher terms. Now from above,

Say $K(t)\approx\tfrac12\kappa t^2$. (This is a direction that would work with $I(w)$, since it is quadratic, and $\kappa$ would be the eigenvalue.) Then

In , at a point $(a_0,0)$ on the $b=0$ axis, moving off the axis in the $b$ direction,

How big can $\|t\|$ be so that $K(t)\le\eps$?

Some remarks.

1. Column 1 measures the following. Consider a unit vector $u$ and $K(\ws+tu)$. Then we're interested in the set $\{t : K(\ws+tu)<\eps\}$. Now say
   $$K(\ws+tu)\approx\tfrac12\kappa t^{2k}<\eps\iff |t|<\underbrace{\Big(\frac{2\eps}{\kappa}\Big)^{1/2k}}_{\text{width}},$$
   the width of the interval that $t$ can move along before $K(\ws+tu)$ exceeds $\eps$. Now if you multiply the widths across all directions you get the volume $V(\eps)$. At a point where $K$ decouples into a sum over directions, $K\approx\sum_j c_j t_j^{2k_j}$,
   $$\mathrm{width}_j\propto\eps^{1/2k_j}\ \Longrightarrow\ \Vol(\eps)\propto\prod_{j=1}^d\eps^{1/2k_j}\propto\eps^{\sum_j 1/2k_j} ,$$
   and $\lambda=\sum_j\frac{1}{2k_j}$ is just this exponent. Note that the unit vectors are the eigenbasis in the regular case.
2. Regular means $K(\ws+tu)\approx\tfrac12\kappa t^2$ for all $u$. Note that you might have regular and degenerate directions, e.g. (asymmetry), where at $\ws=(0,b_0)$ the direction $\binom10$ is regular but $\binom01$ is degenerate.
3. If a model is regular, then every direction $u$ contributes $\tfrac12$ to $\lambda$. There are $\dim W=d$ directions, so
   $$\lambda=d\cdot\tfrac12=\frac d2 .$$
   A singular model has at least one direction where the contribution to $\lambda$ is $<\tfrac12$. So for singular models
   $$\lambda<\frac d2 .$$

RLCT

Summary.

Free Energy

The free energy formula

Recall

$\Dn$ is the training data, e.g. pairs $x$ and $y$; $p(\Dn)$ has the $w$-dependence integrated out. $\Fn$ measures how surprised $p$ is by $\Dn$.

Core result.

Here $nS_n$ is model independent, $S_n=-\frac1n\sum_{i=1}^n\log q(x_i)$ being the entropy of the data; $\lambda$ is the RLCT and $m$ its multiplicity. This is Watanabe's Main Theorem 6.2 [Wat09, Ch. 6] (in the realizable case). The statement in exactly this form, $F=nL_n(w_0)+\lambda\log n-(m-1)\log\log n+R_n$ with $R_n$ converging in law, is Theorem 2 of [Wat13]; there $L_n(w_0)$ is Watanabe's average negative log-likelihood, which equals $S_n$ when the truth is realizable.

Local RLCT

In all of the above we worked globally on $W$. Now we go local. Take $U\subset W$.

The first term measures how well you fit the data, something like a measure of accuracy on the training data. Low $\lambda_U$ means more posterior volume near the optimum (more degenerate or flat directions). See [LLC23] for the local learning coefficient.

Phase transitions

One of the payoffs of building this machinery is that it may offer an explanation for phenomena we see in deep learning, like phase transitions (which are not explained by regular models).

Consider $U_1$ and $U_2$, basins of separated local minima, so that each region's minimum is interior and $\lambda_U$ is well-defined (cutting $W$ arbitrarily would put the minimum on a boundary). Then by

A transition requires the two terms to have opposite signs: one region fits worse but is flatter, the other fits better but is stiffer. Then the $\log n$ term dominates at small $n$ and the linear term overtakes it, with the crossover at

See . Note that $\hat K_n$ is random, so $n^*$ is a random variable, not a fixed threshold. Note also that different components of $\Wz$ always have $\Delta\hat K=0$, so they give a drift, not a transition; the two axes in are exactly this case.

Next time: Estimating $\lambda_U$, the local learning coefficients. Developmental interpretability: using $\hat\lambda_U$ as observables.

References

1. [Wat09]S. Watanabe. Algebraic Geometry and Statistical Learning Theory. Cambridge Monographs on Applied and Computational Mathematics 25, Cambridge University Press, 2009. RLCT and multiplicity via the zeta function, Chapter 6; the free energy asymptotics, Main Theorem 6.2.
2. [Wat13]S. Watanabe. A widely applicable Bayesian information criterion. Journal of Machine Learning Research 14 (2013), 867–897. jmlr.org Theorem 2: $F=nL_n(w_0)+\lambda\log n-(m-1)\log\log n+R_n$.
3. [LLC23]E. Lau, Z. Furman, G. Wang, D. Murfet, S. Wei. The Local Learning Coefficient: A Singularity-Aware Complexity Measure. arXiv:2308.12108, 2023. Local RLCT $\lambda(\ws)$ as a volume-scaling exponent; the local free energy $F_n(B)=nL_n(\ws)+\lambda(\ws)\log n+o_p(\log\log n)$.
4. [Car23]L. Carroll. Distilling Singular Learning Theory (DSLT), sequence of posts, LessWrong / AI Alignment Forum, 2023. lesswrong.com
5. [Fur24]Z. Furman. Singular learning theory: exercises. Timaeus blog / LessWrong, 30 August 2024. timaeus.co