Y. Li, P. M. Long and A. Srinivasan.
The one-inclusion graph algorithm
is near-optimal for the prediction model of learning.
IEEE Transactions on Information Theory, 47(3):1257-1261, 2001.
Abstract
Haussler, Littlestone and Warmuth described a
general-purpose algorithm for learning according
to the prediction model, and proved an upper
bound on the probability that their algorithm
makes 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 within a factor of
1+o(1) of the best possible such bound for any
algorithm.