LIT-542: The Local Learning Coefficient: A Singularity-Aware Complexity Measure

Lau, Furman, Wang, Murfet and Wei (2023) — ARXIV-2308.12108. Read as NOTE-285.

Key takeaways

• Definition 1. There is a unique rational λ(w*), a positive integer multiplicity m(w*) and c > 0 with V(ε) = c ε^{λ(w*)} (−log ε)^{m(w*)−1} + o(…) as ε → 0; when m = 1, V(ε) ∝ ε^{λ(w*)}. So λ(w*) is the volume scaling exponent of the set of near-optimal parameters around w*: raise the error tolerance by a and the volume grows by a^λ. Its rationality follows from Hironaka’s resolution of singularities.
• The information reading. λ(w*) is the number of additional bits needed to halve an already small error: −log₂[V(ε/2)/V(ε)] ≈ λ(w*).
• What it replaces. In the regular case V(ε) ≈ c ε^{d/2}, which is why d/2 is the classical complexity — and the curvature constant c is, in the paper’s words, “less significant than the scaling exponent”.
• The estimator. λ̂(w*) := n β* [E_{w|w*,β*,γ} L_n(w) − L_n(w*)] with β* = 1/log n, the expectation taken over a localized tempered posterior and computed by SGLD. If the loss barely moves under perturbation near w*, the estimate is small.
• Validated against ground truth. On deep linear networks up to 100M parameters, the estimates track Aoyagi (2024)‘s theoretical learning coefficients — and keep doing so when evaluated at an SGD-found minimum rather than at a minimum of the population loss, which was the authors’ stated worry about using the data twice.
• The result that makes it a practice. ResNet18 on CIFAR10, sweeping learning rate, batch size and momentum one at a time: stronger implicit regularization (higher LR, lower batch size, higher momentum) gives lower LLC and higher test accuracy. “Even though most training losses collapse to zero, the LLC can discern the implicit regularization pressure.”
• Invariance. Proved invariant to local diffeomorphism, so it is not confounded by a reparameterization of the same function.

Standing in the anthology

Active. This is the paper LIT-476 was comparing itself against, and the one that makes the school’s central quantity something a practitioner can compute rather than a theorem about an object nobody can reach.

The gap between theory and instrument is real and the record states it. The theorems concern the Bayesian posterior and are asymptotic in n; what is computed is an SGLD sample at β* = 1/log n with a localizing γ. The paper is careful about the engineering steps between the two, and the deep-linear validation is the strongest evidence that the gap is small — in the one realistic setting where the true value is known.