2021/10/29 by Jean-Samuel Leboeuf, Leboeuf, Jean-Samuel, Frédéric LeBlanc +3
Computer Science · Engineering · #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Reservoir Engineering and Simulation Methods
paper · pdf · doi:10.48550/arxiv.2111.00062
openalex publication_date 2021/10/29 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We significantly improve the generalization bounds for VC classes by using\ntwo main ideas. First, we consider the hypergeometric tail inversion to obtain\na very tight non-uniform distribution-independent risk upper bound for VC\nclasses. Second, we optimize the ghost sample trick to obtain a further\nnon-negligible gain. These improvements are then used to derive a relative\ndeviation bound, a multiclass margin bound, as well as a lower bound. Numerical\ncomparisons show that the new bound is nearly never vacuous, and is tighter\nthan other VC bounds for all reasonable data set sizes.\n