machine-learning learning-theory statistics
Definition
Generalisation Bound
A generalisation bound is a theoretical inequality that provides a probabilistic upper limit on the true risk of a hypothesis based on its empirical risk and a measure of model complexity. Formally, with probability at least , for all :
Complexity Measures
The “Complexity” term in the bound quantifies the capacity of the hypothesis class to fit random noise.
Vapnik-Chervonenkis Dimension: In the PAC learning framework, the bound is typically expressed in terms of the VC dimension, where the complexity term scales as .
Rademacher Complexity: A more modern and data-dependent measure that evaluates the expectation of the maximum correlation between the hypotheses and random noise.