nucleation

LIT-245: Minimum Description Length and Generalization Guarantees for Representation Learning

3 min read

Properties6
StatusActive — read 2026-10-14 (NOTE-742) in full; worth reading as the theorem that bounds the generalisation error of an encoder–decoder learner by the encoder alone: 2√((2·MDL + K + 2)/n) + ε, where MDL is the KL divergence of the joint train-and-ghost latents to a prior symmetric under label-preserving permutations (Theorem 4). The bound holds for any decoder and stays finite for deterministic continuous encoders under lossy compression. With a product prior it reduces to sample-wise mutual information, which is why it can be tighter than IB-style bounds. Read it knowing that the bound is never evaluated numerically, that the prior may depend on the unseen ghost data and is only approximated in practice, that a K + 2 term sets a floor, that the proofs other than Theorem 4's were not checked here, and that the experiment is one CIFAR-10 CNN at 62–65% accuracy.
Version4
Tagslearning-theory, representation-learning, information-theory, anthology-candidate
Compared againstLIT-240 — The Role of the Information Bottleneck in Representation Learning
Cited as “paper” byNOTE-207 — MDL generalization guarantees for representation learning, NOTE-742 — Sefidgaran, Zaidi & Krasnowski — MDL and Generalization Guarantees for Representation Learning
Cited as “source” byTHEORY-238 — The expected generalization error of an encoder–decoder learner is bounded by the encoder alone, through the KL divergence of its train-and-ghost latents to a prior symmetric under label-preserving permutations, for any decoder; and under lossy compression the bound can stay finite for deterministic continuous encoders, whose lossless bound is infinite

Graph View

Milad Sefidgaran, Abdellatif Zaidi, Piotr Krasnowski (2023), Advances in Neural Information Processing Systems 36 (NeurIPS 2023), poster — ARXIV-2402.03254

Key takeaways

From the reading, NOTE-742.

  • The main bound (Theorem 4). E[gen(S,W)] ≤ inf 2√((2E D_KL(P(U,U′|X,X′,Ŵe) ‖ Q) + K + 2)/n) + ε for a K-class task. Q is any prior over the 2n latents of a training set and a ghost set that is invariant under permutations preserving the labels. It may depend on both sets’ inputs and labels. The bound depends only on the encoder and “is valid for any choice decoder”. Theorem 7 is the matching tail bound.
  • What it improves on.
    • With a product prior, the KL term becomes n times a sample-wise divergence. With the marginal of Ŷ as Q, that is the empirical mutual information (Eqs. 3–4).
    • For threshold classifiers (VC dimension 1), the bound vanishes as O(√(log n / n)), while the mutual-information term stays of order H(Y).
    • The predicted-label version (Theorem 1) equals I(J; Ŷ^{2n} | Y^{2n}), an f-CMI quantity conditioned on labels only. It recovers the VC bound d log(2en/d).
  • Why I(X;U) is set aside. The paper gives four reasons:
    • existing I(X;U) bounds (Shamir et al., Vera et al., Kawaguchi et al.) are vacuous or restricted to finite alphabets;
    • generalisation tracks geometric compression instead;
    • I(X;U) is invariant to bijections and so blind to the encoder’s structure;
    • it is infinite for deterministic continuous encoders. Lossy compression keeps the new quantity finite. In the paper’s example, I(U;X) = ∞ while a lossy Û within distortion 0.05 has I(Û;X) = 1 (App. C.3).
  • What is not shown.
    • The bound is never computed for a trained network.
    • The prior may depend on the ghost data and is only approximated in practice.
    • The (K + 2) term sets a floor.
    • The experiment, label-dependent learned Gaussian priors in VIB (“CDVIB”), gives 65% against VIB’s 62.5% on one small CIFAR-10 CNN.

Standing in the record

Filed on 2026-09-26 at the owner’s request, from a list they grouped under the heading Relating K-complexity to minimum sufficient statistics. Read on 2026-10-14 in NOTE-742. It is held as the sharpest statement in the record that the IB’s I(X;U) is the wrong complexity for generalisation and a coding rate under a prior is the right one. Its “MDL” is Shannon-style, a KL to a prior, not Kolmogorov complexity, and it says nothing about sufficient statistics. Its Theorem 4 is filed as THEORY-238.

It bears on THEORY-035, which names it among the formal treatments of “the IB term controls generalisation”. It takes that claim up in order to replace it, and supplies a third information quantity that does bound generalisation, beside I(S;W) (LIT-347) and against I(X;T). It is compared_against Vera et al. (LIT-240). The paper’s case against that bound is that it is restricted to finite alphabets and vacuous, citing others, not that it is wrong. The comparison is analytical; a numerical one against Vera et al. is left to future work (App. C.4). It names its label-dependent priors as a link to Fischer’s CEB (LIT-226).

Tagged anthology-candidate (ADR-005). The CDVIB regulariser is a training instruction and belongs in the anthology. The bounds are learning theory. It is kept here by the owner’s decision of 2026-09-26 that new work stays in nucleation until a transfer is judged appropriate (ADR-010).

Bibliographic access when seeded: arXiv abs page (v1 2024-02-05, “accepted and presented at NeurIPS 2023”). The OpenReview record (Ncb0MvVqRV, NeurIPS 2023 poster), made public 2023-11-02, is used as published:. The only DOI found is arXiv’s 10.48550 one.

Backlinks