Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class

摘要

Given a bounded class of functions $mathscr{G}$ and independent random variables $X_{1},ldots,X_{n}$, we provide an upper bound for the expectation of the supremum of the empirical process over elements of $mathscr{G}$ having a small variance. Our bound applies when $mathscr{G}$ is a VC-subgraph or a VC-major class and it is of smaller order than those one could get by using a universal entropy bound over the whole class $mathscr{G}$. It also involves explicit constants and does not require the knowledge of the entropy of $mathscr{G}$.