# Minimum Description Length and Generalization Guarantees for Representation Learning

arXiv: https://arxiv.org/abs/2402.03254 · HTML: https://mlsanity.com/paper/2402.03254/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 71 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Builds on (most cited first, 30 of 37)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [The Conditional Entropy Bottleneck](https://mlsanity.com/paper/2002.05379/) (2020)
- [The Description Length of Deep Learning Models](https://mlsanity.com/paper/1802.07044/) (2018)
- [Nonlinear Information Bottleneck](https://mlsanity.com/paper/1705.02436/) (2017)
- [Learning Representations for Neural Network-Based Classification Using the Information Bottleneck Principle](https://mlsanity.com/paper/1802.09766/) (2018)
- [The Information Bottleneck Problem and Its Applications in Machine Learning](https://mlsanity.com/paper/2004.14941/) (2020)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [Minimum Description Length Revisited](https://mlsanity.com/paper/1908.08484/) (2019)
- [On Information Plane Analyses of Neural Network Classifiers -- A Review](https://mlsanity.com/paper/2003.09671/) (2020)
- [Caveats for information bottleneck in deterministic scenarios](https://mlsanity.com/paper/1808.07593/) (2018)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Learning Optimal Representations with the Decodable Information Bottleneck](https://mlsanity.com/paper/2009.12789/) (2020)
- [Distributed Variational Representation Learning](https://mlsanity.com/paper/1807.04193/) (2018)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views](https://mlsanity.com/paper/2002.00008/) (2020)
- [On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm](https://mlsanity.com/paper/2010.10994/) (2020)

## Built on by (most cited first, 11 of 11)

- [Circuit Stability Characterizes Language Model Generalization](https://mlsanity.com/paper/2505.24731/) (2025)
- [Visual Instruction Bottleneck Tuning](https://mlsanity.com/paper/2505.13946/) (2025)
- [Explaining Grokking and Information Bottleneck through Neural Collapse Emergence](https://mlsanity.com/paper/2509.20829/) (2025)
- [Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priors](https://mlsanity.com/paper/2502.15540/) (2025)
- [Coding for Intelligence from the Perspective of Category](https://mlsanity.com/paper/2407.01017/) (2024)
- [Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective](https://mlsanity.com/paper/2503.01598/) (2025)
- [Multiview Representation Learning via Distributed Joint Latent Space Structuring](https://mlsanity.com/paper/2504.18455/) (2025)
- [On the Rate-Distortion-Complexity Tradeoff for Semantic Communication](https://mlsanity.com/paper/2602.14481/) (2026)
- [Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variables](https://mlsanity.com/paper/2505.19470/) (2025)
- [Information-Theoretic Generalization Bounds for Sequential Decision Making](https://mlsanity.com/paper/2605.12190/) (2026)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## Abstract (arXiv)

A major challenge in designing efficient statistical supervised learning algorithms is finding representations that perform well not only on available training samples but also on unseen data. While the study of representation learning has spurred much interest, most existing such approaches are heuristic; and very little is known about theoretical generalization guarantees. In this paper, we establish a compressibility framework that allows us to derive upper bounds on the generalization error of a representation learning algorithm in terms of the "Minimum Description Length" (MDL) of the labels or the latent variables (representations). Rather than the mutual information between the encoder's input and the representation, which is often believed to reflect the algorithm's generalization capability in the related literature but in fact, falls short of doing so, our new bounds involve the "multi-letter" relative entropy between the distribution of the representations (or labels) of the training and test sets and a fixed prior. In particular, these new bounds reflect the structure of the encoder and are not vacuous for deterministic algorithms. Our compressibility approach, which is information-theoretic in nature, builds upon that of Blum-Langford for PAC-MDL bounds and introduces two essential ingredients: block-coding and lossy-compression. The latter allows our approach to subsume the so-called geometrical compressibility as a special case. To the best knowledge of the authors, the established generalization bounds are the first of their kind for Information Bottleneck (IB) type encoders and representation learning. Finally, we partly exploit the theoretical results by introducing a new data-dependent prior. Numerical simulations illustrate the advantages of well-chosen such priors over classical priors used in IB.