RIGOROUS LEARNING-CURVE BOUNDS FROM STATISTICAL-MECHANICS

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 also more reflective of t he true behavior of learning curves. This behavior can often exhibit d ramatic properties such as phase transitions, as well as power law asy mptotics not explained by the VC theory. The disadvantages of our theo ry are that its application requires knowledge of the input distributi on, and it is limited so far to finite cardinality function classes. W e illustrate our results with many concrete examples of learning curve bounds derived from our theory.