Overfitting and Generalizing with MDL and (PAC) Bayesian Learning in Supervised Classification

This thesis studies overfitting, regularization, and generalization in information-theoretic learning rules for supervised binary classification, focusing on Minimum Description Length (MDL) and PAC-Bayesian prediction. First, it provides a complete characterization of the regularization path of a modified two-part-code MDL learning rule in the agnostic setting, precisely quantifying the worst-case limiting error as a function of the regularization parameter and noise level, and identifying regimes of tempered overfitting, catastrophic overfitting, and consistency. This quantitatively characterizes the cost of overfitting and shows how it changes along the regularization path. Second, it extends this analysis to the PAC-Bayes learning rule with continuous priors and randomized predictions, showing that these rules admit analogous regularization behavior and establishing explicit connections to empirical Bayes, profile posterior, and Bayesian prediction. In particular, the PAC-Bayes rule with lambda = 1 corresponds to an empirical Bayes procedure. The chapter also suggests several open problems for further work, including whether PAC-Bayes, profile posterior, and full Bayesian prediction yield the same or distinct worst-case limiting errors, and thus a complete comparison between them. Finally, the thesis analyzes the well-specified setting of MDL, where labels are generated by a true predictor with random label noise, and shows that in contrast to the agnostic case, lambda = 1 yields asymptotic per-instance consistency while other regularization regimes still exhibit distinct forms of overfitting or underfitting. This chapter also leaves open the problem of completing the picture of the worst-case limiting error in the well-specified case. Specifically, this includes whether the consistency established in lambda = 1 is "uniform" or only "per-instance". It also stays open to close the remaining gaps and to precisely characterize how the behavior changes across different regularization regimes. More broadly, the thesis suggests a general perspective on learning rules that balance empirical loss and model complexity, and points toward characterizing worst-case limiting error for more general bi-criteria objectives.