An inequality for uniform deviations of sample averages from their means (Q1962162): Difference between revisions

Let \(X_1,\dots,X_n\) be independent and identically distributed random variables with values in some arbitrary set \(\mathcal{X}\), and let \(\mathcal{F}\) be a class of uniformly bounded functions from \(\mathcal{X}\) to \([0,1]\). For \(f\in\mathcal{F}\), introduce the sample averages \(P_n(f)=n^{-1}\sum_{i=1}^nf(X_i)\) and the population means \(P(f)=E(f(X_1))\). The authors derive new exponential bounds on \[ P(\sup_{f\in\mathcal{F}}(P(f)-P_n(f)-\gamma)/\sqrt{P(f)}>\varepsilon) \] and \[ P(\sup_{f\in\mathcal{F}}(P_n(f)-P(f)-\gamma)/\sqrt{P_n(f)}>\varepsilon) \] which involve an appropriate expected coverage number to measure the size of the class \(\mathcal{F}\). These results are applied to obtain tight upper bounds for the loss of a decision selected by empirical loss minimization from a class of decisions.