Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion

Code

• github.com/jsleb333/hypergeometric_tail_inversion
  OfficialIn papernone★ 2

Abstract

We significantly improve the generalization bounds for VC classes by using two main ideas. First, we consider the hypergeometric tail inversion to obtain a very tight non-uniform distribution-independent risk upper bound for VC classes. Second, we optimize the ghost sample trick to obtain a further non-negligible gain. These improvements are then used to derive a relative deviation bound, a multiclass margin bound, as well as a lower bound. Numerical comparisons show that the new bound is nearly never vacuous, and is tighter than other VC bounds for all reasonable data set sizes.

Tasks

Reproductions