Concentration inequalities in $\ell_{\infty}$ for sums of iid random ("nice") functions?

Question

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 (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.

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!

Answer 1

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}. $$