Cover-based combinatorial bounds on probability of overfitting
A. I. Frey, I. O. Tolstikhin · Doklady Mathematics · 2014
The paper improves existing combinatorial bounds on probability of overfitting. A new bound is based on partitioning of a set of classifiers into non-overlapping clusters, and then embedding each cluster into a superset with known exact formula for the probability of overfitting. Such approach makes the bound sharper because it accounts for similarities between classifiers within each cluster.