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!