Summary · Chapter 13

Budgets and description length

Budget: the count K of Gaussians per image. Each stores 390 numbers (6 geometry + 384 features), so 64 Gaussians are 6.3% of the 32×32 grid (393,216 numbers), 256 are 25.4%. The solve is K × K. On the 16×16 target, 256 Gaussians store more than the target and fit it exactly (about 6e-12), so curves there are meaningless above about 96.

Kk-means +16 (100 img)Optimum (100 img)J trained at 64, 32 steps (800 img)
160.0003390.0003150.000332 (+3%)
640.0001170.00009880.0001062 (+5%)
2560.00003670.00002320.0000307 (+32%)

Error curve: each doubling roughly halves the error (slope about −1 on log–log). One model trained at 64 serves 16 to 256 within about 4% of k-means +16 steps, because its Halton start layout is nested by prefix and slot queries matter little. Models trained at each count (one seed): 1 to 2% better at 16 and 32, worse at 128 (+16%) and 256 (+4%); transfer from 64 is the lever.

Ordered representation: prefixes are good at every budget (nested dropout, Matryoshka).

MDL: total length ≈ (N/2) ln E + (P/2) ln N. With N = 393,216, P = 390K, it picks 64 on the optimum curve; a lower price per parameter picks 256. An illustration, not a result (Grünwald).

Per-image count: adaptive computation (ACT, PonderNet) or growth by splitting, scored by residual error or by information gain (code entropy of parent minus children).

A budget-curve claim needs: one model or say otherwise; equal-budget baselines; stored numbers on the x-axis; a non-saturating target; the per-image optimum; a downstream axis; seeds and a sealed test set.

Defence: “64 is a working point. We report the whole curve from one model, within about 4% of per-image k-means at every count, and the gap to the optimum, which grows to 32% at 256.”