AI summaryⓘ
The authors study a way to choose models for making predictions by balancing the simplicity of the model and how well it fits the data, known as the Minimum Description Length (MDL) principle. They explore what happens when this balance is only approximated rather than perfectly optimized, which is common in real-world machine learning. They prove that if the approximation error is small and the model simplicity is weighted enough (with a parameter λ≥1), the prediction errors remain controlled over time. However, if the weight for simplicity is too low (λ<1), the model can overfit and produce very poor predictions. Their work clarifies how much approximation and regularization are needed to keep MDL-based predictions reliable.
Minimum Description Length (MDL)Occam's razorSequential predictionModel selectionRegularizationApproximate optimizationAdditive approximationOverfittingCumulative expected error
Authors
Qian Li, Xinyu Mao, Shang-Hua Teng, Guangxu Yang
Abstract
Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: $L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$. For sequential prediction, the MDL method repeatedly selects a model with a minimum objective score of the observed prefix for the next step prediction. Classical MDL prediction theory shows that exact optimization of the MDL objective indeed provides a strong compression guarantee that supports reliable prediction. However, practical machine learning usually can only find models by approximately optimizing the objective function. To bridge this gap, this paper addresses the following fundamental question: Under what forms of approximation and regularization does approximate MDL still guarantee reliable sequential prediction? This work offers a principled characterization. We prove that for any approximation with additive slack $C$ of the more general form of the balanced MDL objective: $λ\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$, the cumulative expected squared prediction error is finite for all $λ\ge1$. The case $λ>1$ is proved by an affinity-telescoping argument, while the boundary case $λ=1$ is proved by a likelihood-ratio stopping argument based on exact static MDL bounds. Our results establish that classical MDL regularization remains robust to any fixed additive optimization error. Furthermore, we establish that our characterization of the approximate MDL framework is sharp: When $0<λ<1$, overfits can happen to incur infinite cumulative expected error in the universal class of estimable measures, and hence a strong form of model-complexity regularization is necessary. In addition, model selection may fail in every regularized regime $λ>0$, under multiplicative approximation, and thus, additive approximation is both sufficient and essential.