Information-Theoretic Generalization Bounds

Classic generalization theory bounds test error using properties of the hypothesis class alone — how many functions a model could represent, roughly. Information-theoretic bounds take a different angle: they bound the generalization gap using how much information the trained model actually depends on the specific training data it was fit to, measured with mutual information between the dataset and the learned parameters.

The intuition: if a training procedure is so sensitive that swapping a single training example noticeably changes the output model, the algorithm has effectively memorized details specific to that dataset rather than learning something that generalizes — and mutual information quantifies exactly this kind of dependence. A learning algorithm whose output barely changes as you resample the training set (low mutual information between data and output) is bounded to generalize well, almost by definition of what "depends less on the specific sample" means; one that changes drastically (high mutual information) is flagged as prone to overfitting, consistent with the everyday finding that heavily-tuned models on small datasets generalize worse.

The practical upshot for a quant is less a formula to compute and more a lens: since these bounds tie generalization directly to how much a fitting procedure "listens to" idiosyncratic noise in a specific sample, techniques that literally add noise during training — like adding a small perturbation to gradients, or randomly holding out subsets of features — provably shrink this dependence and tighten the bound, which is one formal reason regularization and noise injection curb overfitting on a small backtest sample.