Bounds for Predictive Errors in the Statistical Mechanics of Supervised Learning

Within a Bayesian framework, by generalizing inequalities known from statistical mechanics, we calculate general upper and lower bounds for a cumulative entropic error, which measures the success in the supervised learning of an unknown rule from examples. Both bounds match asymptotically, when the number $m$ of observed data grows large. We find that the information gain from observing a new example decreases universally like $\frac{d}{m}$. Here $d$ is a dimension that is defined from the scaling of small volumes with respect to a distance in the space of rules.