Extending the scope of the small-ball method
This work addresses a theoretical limitation in statistical learning for researchers, offering a more general and stable framework, though it appears incremental.
The paper extends the small-ball method to obtain a high probability, almost-isometric lower bound on the quadratic empirical process, eliminating the need for a uniform small-ball condition and adding stability under majority vote.
The small-ball method was introduced as a way of obtaining a high probability, isomorphic lower bound on the quadratic empirical process, under weak assumptions on the indexing class. The key assumption was that class members satisfy a uniform small-ball estimate: that $Pr(|f| \geq κ\|f\|_{L_2}) \geq δ$ for given constants $κ$ and $δ$. Here we extend the small-ball method and obtain a high probability, almost-isometric (rather than isomorphic) lower bound on the quadratic empirical process. The scope of the result is considerably wider than the small-ball method: there is no need for class members to satisfy a uniform small-ball condition, and moreover, motivated by the notion of tournament learning procedures, the result is stable under a `majority vote'.