"Rigorous Learning Curve Bounds from Statistical Mechanics," Machine Learning , Vol. 25, (1997) pp. 195-236. (with Michael Kearns, H. Sebastian Seung and Naftali Tishby)
Abstract:
In this paper we introduce and investigate a mathematically rigorous theory of learning curves
that is based on ideas from statistical mechanics. The advantage of our theory over the
well-established Vapnik-Chervonenkis theory is that our bounds can be considerably tighter in many
cases, and are more reflectve of the true behavior (functional form) of learning curves. This behavior
can often exhibit dramatic properties such as phase transitions, as well as power law asymptotics not
explained by the VC theory. The disadvantages of our theory are that its application requires
knowledge of the input distribution, and it is limited so far to finite cardinality function classes. We
illustrate our results with many concrete examples of learning curve bounds derived from our theory.