When training a machine learning model, we constantly balance two competing forces: goodness-of-fit and model complexity. Fit the training data too closely, and the model overfits to noise; penalize complexity too harshly, and it underfits. Traditionally, we balance these forces using ad-hoc regularization coefficients or computationally expensive cross-validation.
The Minimum Description Length (MDL) principle offers an elegant alternative by framing learning entirely as a data compression problem. The core intuition is simple: any regularity in data can be used to compress it. Therefore, the model that best captures the underlying structure of the data is the one that enables the shortest total description of that data.
The Intuition of the Two-Part Code
To understand why MDL works, imagine a sender who wants to transmit a dataset to a receiver over a limited-bandwidth channel. To minimize the number of bits sent, the sender can transmit a model of the data, followed by the data encoded using that model.
The total message length $L(\text{Total})$ is the sum of two components:
$$L(\text{Total}) = L(M) + L(D|M)$$
Where:
- $L(M)$ is the length of the model description (the complexity cost).
- $L(D|M)$ is the length of the data given the model (the error cost).
A highly complex model can fit the data perfectly, driving the error cost $L(D|M)$ to zero, but it requires a massive number of bits to describe the model parameters, making $L(M)$ very large. Conversely, an overly simple model has a tiny $L(M)$ but fails to compress the data, resulting in a large $L(D|M)$. Minimizing the sum of these two costs naturally finds the optimal balance—Occam's Razor formalized in bits.
Escaping the Hyperparameter Trap
One of the most compelling reasons to use MDL is that it eliminates the need for manual hyperparameter tuning. In many statistical frameworks, researchers must choose arbitrary penalty weights or tune hyper-priors.
For instance, Ralf Eggeling et al. demonstrate this advantage in Robust learning of inhomogeneous PMMs, showing that MDL-based structure learning removes the need to fine-tune equivalent sample sizes in Markov models. By treating architecture selection purely as a compression task, the data itself determines the optimal model complexity.
Similarly, in sparse coding and dictionary learning, choosing the right dictionary size or sparsity threshold usually requires extensive grid searches. Ignacio Ramírez addresses this in An MDL Framework for Sparse Coding and Dictionary Learning, showing that treating the dictionary and sparse coefficients as communication costs allows the data's own regularities to dictate the optimal stopping point without manual intervention.
Determining Latent Structure and Rank
The power of MDL becomes clear when deciding the granularity or dimensionality of a model. Consider Non-negative Matrix Factorization (NMF), where selecting the inner rank (the number of latent features) is notoriously difficult.
Steven Squires et al. in Rank Selection in Nonnegative Matrix Factorization using Minimum Description Length and Adam Prugel-Bennett et al. in Minimum description length as an objective function for non-negative matrix factorization frame rank selection as a compression problem. By minimizing the total message length required to encode both the factorized matrices and the reconstruction error, the algorithm automatically discovers the true latent dimensionality of the data.
This principle applies equally well to discrete problems like density estimation via histograms. Instead of relying on arbitrary equal-width bins, Petri Kontkanen et al. in MDL Histogram Density Estimation and Lincen Yang et al. in Unsupervised discretization by two-dimensional MDL-based histogram use MDL to optimize the number and placement of bin boundaries. The optimal histogram is simply the one that compresses the data distribution most efficiently.
Application to Deep Learning and Language Models
While MDL originated in classical information theory, its foundational insights scale to modern deep learning and large language models (LLMs).
In neural networks, Alex Graves in Practical Variational Inference for Neural Networks bridges the gap between Bayesian neural networks and MDL. By framing the loss function as a combination of prediction error and the information cost of the weights, the learning process naturally regularizes complex neural network architectures.
MDL also provides a robust evaluation metric when data is scarce. In few-shot learning with LLMs, standard cross-validation often overestimates performance because validation sets are too small to be reliable. Ethan Perez et al. in True Few-Shot Learning with Language Models utilize description length as a selection criterion, showing that how efficiently a model compresses training labels serves as a reliable proxy for true generalization.
Furthermore, the principle can guide high-level architectural decisions in complex planning tasks. Zirui Zhao et al. in Large Language Models as Commonsense Knowledge for Large-Scale Task Planning demonstrate that MDL can determine whether to use a direct policy or a model-based planner: if the environment's transition rules are more concise to describe than the optimal policy itself, a model-based approach is theoretically superior and more generalizable.
Theoretical Foundations and Variations
The theoretical validity of this approach is backed by rigorous risk bounds. For instance, Masanori Kawakita et al. in Barron and Cover's Theory in Supervised Learning and its Application to Lasso extended foundational MDL theory to high-dimensional supervised learning, proving that selecting models based on compression efficiency mathematically guarantees tighter risk and predictive error bounds.
A closely related framework is the Minimum Message Length (MML) criterion. While MDL focuses on choosing a model class based on minimax code length, MML operates from a subjective Bayesian perspective to simultaneously estimate parameters and select models. As shown by Enes Makalic in Minimum Message Length Ridge Regression for Generalized Linear Models, MML allows for simultaneous feature selection, parameter estimation, and hyperparameter tuning within generalized linear models, demonstrating that the core philosophy—learning is compression—holds true across both frequentist and Bayesian formulations.