  The one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth
achieves an optimal in-expectation risk bound in the standard PAC
classification setup. In one of the first COLT open problems, Warmuth
conjectured that this prediction strategy always implies an optimal high
probability bound on the risk, and hence is also an optimal PAC algorithm. We
refute this conjecture in the strongest sense: for any practically interesting
Vapnik-Chervonenkis class, we provide an in-expectation optimal one-inclusion
graph algorithm whose high probability risk bound cannot go beyond that implied
by Markov's inequality. Our construction of these poorly performing
one-inclusion graph algorithms uses Varshamov-Tenengolts error correcting
codes.
  Our negative result has several implications. First, it shows that the same
poor high-probability performance is inherited by several recent prediction
strategies based on generalizations of the one-inclusion graph algorithm.
Second, our analysis shows yet another statistical problem that enjoys an
estimator that is provably optimal in expectation via a leave-one-out argument,
but fails in the high-probability regime. This discrepancy occurs despite the
boundedness of the binary loss for which arguments based on concentration
inequalities often provide sharp high probability risk bounds.
