When are epsilon-nets small?

摘要

Given a range space (X,R), where X is a set equipped with probability measure P, R⊂2X is a family of measurable subsets, and ϵ>0, an ϵ-net is a subset of X in the support of P, which intersects each R∈R with P(R)≥ϵ. In many situations the size of ϵ-nets depends on ϵ and on natural complexity measures. The aim of this paper is to give a systematic treatment of such complexity measures arising in Computational Geometry and Statistical Learning. As a byproduct, we obtain several new upper bounds on the sizes of ϵ-nets that improve the best known general guarantees. Some of our results deal with improvements in logarithmic factors, while others consider the regimes where ϵ-nets of size o(1ϵ) exist. Inspired by results in Statistical Learning, we also give a short proof of the Haussler's upper bound on packing numbers.