I'm looking for "tail-bound-like" inequalities that look like this (I state a specific setting but more general settings are interesting):



> 
> Let $D$ be a distribution on a set of "nice" functions $g$: $[0,1]^d \to [0,1]$. Define
>  $$\bar{g}(x) = \mathbb{E}\_{g \sim D} g(x) ,$$
>  and let $\hat{g}\_n$ be a random variable equal to the average of $n$ iid draws $g\_1,\dots,g\_n$ from $D$, i.e.
>  $$\hat{g}\_n(x) = \frac{1}{n}\sum\_{j=1}^n g\_j(x) .$$
>  Then
>  $$\Pr[ \|\bar{g} - \hat{g}\_n\|\_{\infty} > \epsilon ] ~~~ \leq ~~ ???$$
> 
> 
> 


I'm interested in ??? being an exponentially decaying "tail" and looking for theorems for various choices of "nice":


* If we restrict to constant functions, we're back in the realm of Bernstein/Chernoff/Hoeffding/Azuma/etc.
* For degree-$k$ polynomials, I think you can just apply those bounds on each coefficient and get a similar result with a (poor) dependence on $k$ and $d$.
* Perhaps Lipschitz conditions are sufficient?
* For general functions, we cannot get a good bound, by a simple counterexample using indicator functions in the comment on my [previous question on math.se](https://math.stackexchange.com/questions/828511/dkw-style-ell-infty-bounds-for-sum-of-i-i-d-random-functions-to-0-1) (unanswered).
* **I'm most interested in the case "nice" = convex. A counterexample would be great if such a bound is not achievable.** I have not thought of one yet. But I also can't see any strategy towards proving it (not that this says much). The most closely related theorem I know of is the [DKW inequality](http://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality).


I'm having trouble finding any such results with an online search and hoping for pointers to some literature or observations that could be useful to a non-expert. Thanks!



Concentration inequalities in $\ell_{\infty}$ for sums of iid random ("nice") functions?
What you have is called an *empirical process*, although it is usually written with the points and the functions reversed: let $\mathcal{F}$ be a family of functions $\Omega \to \mathbb{R}$ and let $X\_1, \dots, X\_n$ be i.i.d. elements of $\Omega$. The empirical process indexed by $\mathcal{F}$ is the collection
of random variables $\{Z\_f : f \in \mathcal F\}$ where
$$
Z\_f =
n^{-1/2} \sum\_{i=1}^n (f(X\_i) - \mathbb{E} f)
$$
(sometimes you will see it un-centered or differently normalized).


To translate this into your notation, you should take $\Omega$ to be a space of "nice" functions and $\mathcal F$ to be the set of point-evaluation functionals. Then you asked for a bound on
$$
\mathrm{Pr}\left(n^{-1/2} \sup\_{f \in \mathcal F} Z\_f \ge \epsilon \right).
$$
It might be best to break this into two quantities: a bound on $\mathbb{E} \sup\_{f \in \mathcal F} Z\_f$ and a concentration inequality for $\sup\_{f \in F} Z\_f$ around its mean. The second part can be done (when $\mathcal F$ is uniformly bounded, as in your question) using a concentration inequality of Talagrand (see, e.g, "Concentration inequalities using the entropy method" by Boucheron, Lugosi and Massart).


Bounding $\mathbb{E} \sup\_{f \in \mathcal F} Z\_f$ will depend more on the class $\mathcal F$. One technique is to use Koltchinskii-Pollard entropy (which should be contained in the book by van der Waart and Wellner, but I can't check right now): if for every finitely supported probability distribution $\mu$ on $\Omega$, you can bound the metric entropy of $\mathcal F$ with respect to the $L\_2(\mu)$ metric then you can bound $\mathbb E \sup\_{f \in \mathcal F} Z\_f$. For example, if "nice" means 1-Lipschitz and $x\_1, \dots, x\_k$ are an $\epsilon$-cover of $[0, 1]^d$ then for any finitely supported probability distribution $\mu$ on Lipschitz functions, the point-evaluation functionals at $x\_1, \dots, x\_k$ form an $\epsilon$-cover w.r.t. $L\_\infty(\mu)$ and hence also $L\_2(\mu)$. That means that the Koltchinskii-Pollard entropy at scale $\epsilon$ is $O(d \log(1/\epsilon))$ and that will imply that $\mathbb{E} \sup Z\_f = O(d)$.


When you put everything together, that should give you a bound like
$$
\mathrm{Pr} (n^{-1/2} \sup\_f Z\_f \ge C d n^{-1/2} + \epsilon) \le C e^{-c n \epsilon^2}.
$$


