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 #cs.LG
paper · pdf · doi:10.48550/arxiv.2111.00062
15 pages (body), 36 pages (appendices), 54 pages (total), 13 figures
arxiv created 2021/10/29 · openalex publication_date 2021/10/29 · arxiv updated 2021/11/02 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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.