The optimal PAC bound for intersection-closed concept classes

•The optimal upper bound for learning intersection-closed concept classes.•Proves an open question by Auer and Ortner and supports a conjecture by Warmuth.•An improved upper bound on the sample complexity in PAC-learning.•Comparison between different variants of disagreement coefficients.•An application of the disagreement coefficient in realizable PAC-learning.

Thirty years after the introduction of Valiant's PAC-learning framework in 1984, proving sharp sample complexity bounds in the standard, realizable framework is still an open problem. This is true for general concept classes but also for most natural families of classes. In this letter we will give sharp bounds on the sample complexity of PAC-learning intersection-closed classes. Our result settles an open problem posed by Auer and Ortner and supports a conjecture by Warmuth about the true sample complexity and the optimal PAC-learning algorithm for general classes.Furthermore this letter demonstrates a useful application of the disagreement coefficient—a complexity measure developed for agnostic learning by Giné and Koltchinskii based on the work of Alexander and, independently, by Hanneke—in the realizable PAC-learning framework.