PAC-Bayesian Generic Chaining

There exist many different generalization error bounds for classification. Each of these bounds contains an improvement over the others for certain situations.Our goal is to combine these different improvements into a single bound. In particular we combine the PAC-Bayes approach introduced byMcAllester [1], which is interesting for averaging classifiers, with the optimal union bound provided by the generic chaining technique developed by Fernique and Talagrand [2]. This combination is quite natural sincethe generic chaining is based on the notion of majorizing measures, whichcan be considered as priors on the set of classifiers, and such priors also arise in the PACbayesian setting.