A uniform Dvoretzky-Kiefer-Wolfowitz inequality

Abstract

We show that under minimal assumptions on a class of functions $\mathcal{H}$ defined on a probability space $(\mathcal{X},\hat{I}¼)$, there is a threshold $\hat{I}{”}_0$ satisfying the following: for every $\hat{I}”\ge \hat{I}{”}_0$, with probability at least $1-2\exp (-c\hat{I}”m)$ with respect to $\hat{I}{¼}^{\otimes m}$, \[ \sup_{h\in\mathcal{H}} \sup_{t\in\mathbb{R}} \left| \mathbb{P}(h(X)\leq t) - \frac{1}{m}\sum_{i=1}^m 1_{(-\infty,t]}(h(X_i)) \right| \leq \sqrtΔ;\] here $X$ is distributed according to $\hat{I}¼$ and $(X_i{)}_{i=1}^m$ are independent copies of $X$. The value of $\hat{I}{”}_0$ is determined by an unexpected complexity parameter of the class $\mathcal{H}$ that captures the set's geometry (Talagrand's ${\hat{I}}_1^3$-functional). The bound, the probability estimate and the value of $\hat{I}{”}_0$ are all optimal up to a logarithmic factor.