# Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion

arXiv: https://arxiv.org/abs/2111.00062 · HTML: https://mlsanity.com/paper/2111.00062/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 43 references that are in the map.
- First posted on arXiv 29 Oct 2021.

## Builds on (most cited first, 9 of 9)

- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions](https://mlsanity.com/paper/1310.5796/) (2013)
- [Decision trees as partitioning machines to characterize their generalization properties](https://mlsanity.com/paper/2010.07374/) (2020)
- [Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC) Machine Learning Model](https://mlsanity.com/paper/1606.08920/) (2016)
- [Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation](https://mlsanity.com/paper/1306.1433/) (2013)
- [Unlabeled Compression Schemes Exceeding the VC-dimension](https://mlsanity.com/paper/1811.12471/) (2018)
- [An Elementary Analysis of the Probability That a Binomial Random Variable Exceeds Its Expectation](https://mlsanity.com/paper/1712.00519/) (2017)

## Abstract (arXiv)

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.