Ensemble Validation: Selectivity has a Price, but Variety is Free

If classifiers are selected from a hypothesis class to form an ensemble, bounds on average error rate over the selected classifiers include a component for selectivity, which grows as the fraction of hypothesis classifiers selected for the ensemble shrinks, and a component for variety, which grows with the size of the hypothesis class or in-sample data set. We show that the component for selectivity asymptotically dominates the component for variety, meaning that variety is essentially free.