Margin-Based Generalization Lower Bounds for Boosted Classifiers

Despite the numerous generalization upper bounds that have been proved over the last two decades, nothing is known about the tightness of these bounds.