Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification
Not on the map. Why?
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 λ.
Key facts. Cited by 2 papers in the map (data through 13 Oct 2026). Builds on 13 of its 24 references that are in the map. First posted on arXiv 3 Mar 2025.
Builds on
13 of 24 references.
References · 13
- 2019Benign Overfitting in Linear Regressioncited by 545
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 510
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 411
- 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
- 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 43
- 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
- 2019The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regimecited by 27
- 2024How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teacherscited by 18
- 2022Error Scaling Laws for Kernel Classification under Source and Capacity Conditionscited by 17
- 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
- 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
- 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
Built on by
Citing papers per year: 2026: 2.
2 papers.