A uniform Dvoretzky-Kiefer-Wolfowitz inequality

We show that under minimal assumptions on a class of functions $\mathcal{H}$ defined on a probability space $(\mathcal{X},\mu )$, there is a threshold ${\mathrm{\Delta }}_0$ satisfying the following: for every $\mathrm{\Delta }\ge {\mathrm{\Delta }}_0$, with probability at least $1-2\exp (-c\mathrm{\Delta }m)$ with respect to ${\mu }^{\otimes m}$, $$\underset{h\in \mathcal{H}}{\sup }\underset{t\in \mathbb{R}}{\sup }\mid \mathbb{P}(h(X)\le t)-\frac{1}{m}\sum _{i=1}^m{1}_{(-\mathrm{\infty },t]}(h(X_i))\mid \le \sqrt{\mathrm{\Delta }};$$ here $X$ is distributed according to $\mu$ and $(X_i{)}_{i=1}^m$ are independent copies of $X$. The value of ${\mathrm{\Delta }}_0$ is determined by an unexpected complexity parameter of the class $\mathcal{H}$ that captures the set’s geometry (Talagrand’s ${\gamma }_1$-functional). The bound, the probability estimate and the value of ${\mathrm{\Delta }}_0$ are all optimal up to a logarithmic factor.