# Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 24 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Builds on (most cited first, 13 of 13)

- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime](https://mlsanity.com/paper/1911.01544/) (2019)
- [How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers](https://mlsanity.com/paper/2402.06323/) (2024)
- [Error Scaling Laws for Kernel Classification under Source and Capacity Conditions](https://mlsanity.com/paper/2201.12655/) (2022)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [Tight Bounds on the Binomial CDF, and the Minimum of i.i.d Binomials, in terms of KL-Divergence](https://mlsanity.com/paper/2502.18611/) (2025)

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

- [Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classification](https://mlsanity.com/paper/2603.22644/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

We provide a complete characterization of the entire regularization curve of a modified two-part-code Minimum Description Length (MDL) learning rule for binary classification, based on an arbitrary prior or description language. Grunwald and Langford [2004] previously established the lack of asymptotic consistency, from an agnostic PAC (frequentist worst case) perspective, of the MDL rule with a penalty parameter of λ=1, suggesting that it underegularizes. Driven by interest in understanding how benign or catastrophic under-regularization and overfitting might be, we obtain a precise quantitative description of the worst case limiting error as a function of the regularization parameter λ and noise level (or approximation error), significantly tightening the analysis of Grunwald and Langford for λ=1 and extending it to all other choices of λ.