Noname manuscript No. (will be inserted by the editor) A New PAC Bound for Intersection-Closed Concept Classes ⋆

The bound is established using the closure algorithm, that generates as its hypothesis the intersection of all concepts that are consistent with the positive training examples, and it is shown that many intersection-closed concept classes satisfy an additional combinatorial property that allows a proof of the optimal bound of O(\frac{1}{\varepsilon}(d+\log \frac{ 1}{\delta})).