A comparison of tight generalization error bounds

Abstract

We investigate the empirical applicability of several bounds (a number of which are new) on the true error rate of learned classifiers which hold whenever the examples are chosen independently at random from a fixed distribution.The collection of tricks we use includes:1. A technique using unlabeled data for a tight derandomization of randomized bounds.2. A tight form of the progressive validation bound.3. The exact form of the test set bound.The bounds are implemented in the semibound package and are freely available.