GENERAL BOUNDS FOR PREDICTIVE ERRORS IN SUPERVISED LEARNING
Within a Bayesian framework, 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. This performance measure is equivalent to the mutual information between the data and the parameter that specifies the rule to be learnt. Both bounds match asymptotically, when the number m of observed data grows large. Under mild conditions, we find that the information gain from observing a new example decreases universally like d/m. Here d is a dimension that is defined from the scaling of small volumes with respect to a suitable distance in the space of rules.