MDL3 — Deep Learning as Program Synthesis

1. \sum_i(y_i-\theta)^2=\sum_i(y_i-\bar y)^2+n(\theta-\bar y)^2, since the cross term contains \sum_i(y_i-\bar y)=0. The first part, with the normalization, is p(D\mid\bar y); the second gives e^{-(\theta-\bar y)^2/2s^2}, maximized at \theta=\bar y.

2. Z=p(D\mid\bar y)\int\mathcal N(\theta;0,\tau^2)\,e^{-(\theta-\bar y)^2/2s^2}d\theta=p(D\mid\bar y)\sqrt{2\pi s^2}\;\mathcal N(\bar y;0,\tau^2+s^2), and \sqrt{2\pi s^2}\,(2\pi(\tau^2+s^2))^{-1/2}=\sqrt{s^2/(\tau^2+s^2)}.

3. -\ln Z=-\ln p(D\mid\hat\theta)+\tfrac12\ln(1+\tau^2/s^2)+\bar y^2/2(\tau^2+s^2). With \tau^2/s^2=n\tau^2/\sigma^2 the middle term is \tfrac12\ln n+\tfrac12\ln(\tau^2/\sigma^2)+O(1/n), and the last tends to \bar y^2/2\tau^2. The Occam factor is \approx\Delta_{\text{post}}/\Delta_\pi with posterior width \Delta_{\text{post}}=\sqrt{2\pi}\,\sigma/\sqrt n and effective prior width \Delta_\pi=1/\pi(\hat\theta). The \tfrac12\ln n is BIC’s \tfrac p2\ln n with p=1: it comes from the posterior shrinking like 1/\sqrt n.

4. The Occam factor behaves like \sigma/(\tau\sqrt n)\to0, so Z\to0 while p(D\mid\hat\theta) is unchanged. The fit is as good as before; the model is penalized because a vague prior put almost all its mass on values the data ruled out. Evidence is sensitive to prior widths in a way that likelihood fits are not.

(a) Let p,q first differ at position j, with p_j=0, q_j=1, and common prefix a=0.p_1\dots p_{j-1}. Then I_p\subset[a,a+2^{-j}) and I_q\subset[a+2^{-j},a+2^{-j+1}), so they are disjoint. The intervals of a prefix-free set are disjoint subintervals of [0,1) with lengths 2^{-|p|}, so their sum is at most 1. Distinct strings have distinct shortest programs, all in the prefix-free domain of U, so \sum_x2^{-K_U(x)}\le1. (Conversely, any lengths satisfying Kraft’s inequality are the lengths of some prefix code, which is why L=-\log_2P converts freely between code lengths and priors.)

(b) If p is a shortest V-program for x, then s_Vp is a U-program for x, so K_U(x)\le K_V(x)+|s_V|; swapping roles gives |K_U-K_V|\le c. For the construction, set V(\texttt{0})=x^\star and V(\texttt{1}p)=U(p). Its domain is prefix-free, it is universal (K_V(y)\le K_U(y)+1), and K_V(x^\star)=1 however large K_U(x^\star) is. So the invariance constant can exceed any single object’s complexity: for one finite object, such as a trained network, K has no machine-independent value.

(c) There are 2^{n-c}-1 binary strings shorter than n-c, each the program for at most one output, so fewer than 2^{n-c} strings have K<n-c: a fraction below 2^{-c} of the 2^n strings. Fewer than one n-bit string in a thousand compresses by 10 bits. Simple strings are rare, so a learner that bets on them is making a strong, falsifiable bet.

1. L(\delta)=\log_2(\Delta_\pi/\delta)-\log_2p(D\mid\hat\theta)+\dfrac{nJ\delta^2}{24\ln2}. Setting dL/d\delta=0 gives \delta^\ast=\sqrt{12/(nJ)}.

2. At \delta^\ast the index costs \log_2\Delta_\pi+\tfrac12\log_2n+\tfrac12\log_2(J/12) bits and the fit penalty is 1/(2\ln2)\approx0.72 bits. The O(1) is \log_2\Delta_\pi+\tfrac12\log_2(J/12)+1/(2\ln2): it depends on the parameter’s range and its Fisher information, and so on the coordinates chosen for \theta. With p parameters (Fisher matrix diagonal) the total is \tfrac p2\log_2n, which is BIC in bits.

3. \delta^\ast\approx3.5/\sqrt{nJ} is a few posterior standard deviations. Stating \theta more precisely than the data can resolve costs bits and buys no fit; stating it less precisely costs fit. The \tfrac12\log_2n is the code-length counterpart of the Occam factor \Delta_{\text{post}}/\Delta_\pi in Exercise 2.1.

• 1. y=\theta x+\varepsilon with \theta\sim\mathrm{Unif}[-10^{100},10^{100}]. One line to state; but with \Delta_{\text{post}}\approx10^{-2} the Occam factor is about 10^{-102}, roughly 340 bits. Volume cares about the prior’s spread, not the model’s description.
• 2. The first 10^6 binary digits of \pi. K is at most a few thousand bits (a short program plus about 20 bits for the length). But i.i.d. and order-k Markov models all see a fair coin, and the best evidence goes to the fair coin at about 10^6 bits. Bayesian comparison only ranks the models you put in; Kolmogorov complexity ranks against every program.
• 3. A singular model with p parameters and learning coefficient \lambda\ll p/2 pays about \lambda\ln n nats in volume, while a code that quantizes every coordinate pays about \tfrac p2\ln n. Degenerate directions cost the evidence nothing. A cleverer code that states only the non-degenerate directions closes some of the gap; the evidence does it automatically.

So when a paper says “networks are biased toward simple functions,” ask which notion it means.

(a) \xi(x) is a sum of non-negative terms, one of which is w_\mu\mu(x).

(b) The product telescopes to \xi(x_{1:n})/\xi(\epsilon), and likewise for \mu with \mu(\epsilon)=1. So the regret is

R_n=\sum_{t\le n}\ln\frac{\mu(x_t\mid x_{<t})}{\xi(x_t\mid x_{<t})}=\ln\frac{\mu(x_{1:n})}{\xi(x_{1:n})}+\ln\xi(\epsilon)\le\ln\frac1{w_\mu},

using \xi(\epsilon)\le1 and (a). With w_\mu=2^{-K(\mu)} the bound is K(\mu)\ln2 nats, on every sequence: a worst-case guarantee, not an average. Taking expectations under \mu, the per-step KL divergences between \mu’s and \xi’s predictions sum to at most K(\mu)\ln2 over all time, so the mixture’s predictions converge to the truth (Rathmanner and Hutter §8.1).

(c) 1000\ln2\approx693 nats, exactly 1000 bits of total excess code length however long the sequence. The mixture pays no more, in total, than it would cost to be told the shortest description of \mu up front. This is the MDL reading of Solomonoff induction. Note that the bound is generic to Bayes mixtures; Solomonoff’s contribution is the class (every computable source) and the weights (which make the price the truth’s description length).

(a) Set \omega_1=1-p(\epsilon) and \omega_{n+1}=1-p(\omega_{1:n}). A program for \omega is a shortest program for p plus a fixed wrapper that runs it and flips its outputs, so K(\omega)\le K(p)+c, and p is wrong at every step (Legg’s Lemma 3.3).

(b) By (a) some \omega' with K(\omega')\le K(p)+c is not learned by p, so K(\omega')>n, hence K(p)>n-c (Legg’s Theorem 4.3).

(c) At each step emit a token other than the model’s argmax. The model is always wrong, and the sequence is computable from the weights plus a constant-size wrapper, so its complexity is at most the model’s plus a constant. Under log-loss, emit the token the model rates least likely: its probability is at most 1/V for vocabulary size V, so the model pays at least \ln V nats per step. A claim that a fixed model is a universal predictor must therefore be distributional (“on the text that actually occurs”) or resource-bounded, not worst-case.

(d) “Always predict 0” learns every sequence x000\ldots, and K(x000\ldots) is as large as you like for incompressible x. No conflict: a simple predictor can learn some complex sequences, but no simple predictor learns all simple ones (Legg’s Lemma 3.2).

(a) For S\ne T, \mathbb E_x[\chi_S\chi_T]=\mathbb E_x[\chi_{S\triangle T}]=0, so they agree on exactly half the inputs, and a fixed wrong parity survives n i.i.d. examples with probability 2^{-n}. A union bound over the N-1 wrong parities gives failure probability at most N2^{-n}\le\delta once n\ge\log_2N+\log_2(1/\delta); and N\le d^k. The sample cost is the number of bits needed to name S: the Occam bound in miniature, and the shape of the slides’ Solomonoff warm-up.

(b) With e_1,\dots,e_r (r\le n) an orthonormal basis of V,

\sum_{|S|=k}\lVert P_V\chi_S\rVert^2=\sum_{j=1}^r\sum_{|S|=k}\langle e_j,\chi_S\rangle^2\le\sum_{j=1}^r\lVert e_j\rVert^2=r\le n

by Bessel. Since \hat f\in V, \lVert\hat f-\chi_S\rVert^2\ge1-\lVert P_V\chi_S\rVert^2; averaging over S gives 1-n/N. The predictor \hat f=0 already has error 1, so any fixed kernel needs n of order \binom dk\approx d^k/k! to do much better. (A posterior sample is the mean plus label-independent noise, which only adds error.)

(c) N=\binom{100}5\approx7.5\times10^7 and \log_2N\approx26.2: about 33 samples for \delta=0.01 versus tens of millions for any fixed kernel. That is the gap between a description-length (or circuit) prior and the NNGP/NTK kernel prior. But both numbers are theory, and neither is SGD: (a) is the information-theoretic count for a learner that enumerates N candidates, (b) the scale for a learner that never moves its features. A network trained by SGD sits empirically in between. Barak et al. (2022) find that online SGD on a small MLP (one fresh sample per step) learns sparse parities after a number of steps polynomial in d with a k-dependent exponent, roughly d^{k-1} in the regime of their analysis; the exponent depends on width, learning rate and k, and is a measured quantity rather than a theorem. Statistical-query lower bounds say any SQ algorithm needs d^{\Omega(k)} queries, so the gap between (a) and SGD is about search, not the prior: Furman’s search problem.

(d) Expect a clean power law with an exponent well below k and well above 0; small runs at k=3 typically land nearer d^{1}–d^{2} than d^3, and the number moves with width, learning rate and the threshold you choose. The point is the bracket, not the slope: SGD is neither the counting learner nor a fixed kernel.

• Description length. L levels, about v symbols each, m rewrites of s symbols at \log_2v bits per symbol: about Lvms\log_2v bits.
• Samples. At most \log_2n_c bits per label, so roughly Lvms\log_2v/\log_2n_c samples: linear in L, whereas P^\ast\simeq n_cm^L is exponential in L (though polynomial in d=s^L).
• Example. v=n_c=8, m=4, s=2: at L=3, about 192 versus 512; at L=6, about 384 versus 32,768.
• Reading. The idealized learner is far more sample-efficient but intractable. The network’s actual cost tracks when correlations become detectable, so P^\ast reflects the search mechanism and the data’s statistics, not a program-length prior. The uncorrelated variant sharpens this: the rules are just as short, so the idealized learner is unaffected, but deep networks become exponential.
• Caveat. A back-of-envelope estimate; unlabelled inputs also carry information about the rules, so the label-only count overstates what the idealized learner needs.