The One-Inclusion Graph Algorithm is not Always Optimal
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- A Characterization of List Learnability2023
- A Characterization of Multiclass Learnability2022
- When are epsilon-nets small?Journal of Computer and System Sciences, 2020
- Localization of VC classes: Beyond local Rademacher complexitiesTheoretical Computer Science, 2018
- The optimal PAC bound for intersection-closed concept classesInformation Processing Letters, 2015
- Shifting: One-inclusion mistake bounds and sample compressionJournal of Computer and System Sciences, 2009
- Relative Expected Instantaneous Loss BoundsJournal of Computer and System Sciences, 2002
- The one-inclusion graph algorithm is near-optimal for the prediction model of learningIEEE Transactions on Information Theory, 2001
- Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimensionJournal of Combinatorial Theory, Series A, 1995
- Predicting {0, 1}-Functions on Randomly Drawn PointsInformation and Computation, 1994