The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning

Haussler, Littlestone and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved a bound on the probability that their algorithm made a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis dimension of the concept class being learned. We show that their bound is optimal to within a factor of 1 + o(1).