A concentration inequality related to suprema of sub-Gaussian processes

Question

Let $x_1,\dots,x_n$ be deterministic points in some space $X$ and consider a class of real-valued functions $\mathcal G$ on $X$. We further assume that for any $g \in \mathcal G$, $$ \Bigl(\frac1n \sum_{i=1}^n g(x_i)^2\Bigr)^{1/2} \le \rho. $$ (In the language of statistics, $\mathcal G$ is inside the ball of radius $\rho$ in the empirical $L^2$ norm defined by $\{x_i\}$.)

Let $w_1,\dots,w_n$ be a sequence of i.i.d. random variables and define $$ U_g := \frac1{\sqrt n} \sum_{i=1}^n w_i g(x_i), \quad Z := \sup_{g \in \mathcal G} U_g. $$ We are interested in proving concentration inequalities of the form $$ \mathbb P( Z - \mathbb E Z \ge \rho t) \le C \exp(- c t^2), \quad \text{for all}\; t \ge 0, \quad (*) $$ where $C, c > 0$ are absolute constants. This is true when $\{w_i\}$ are i.i.d. $N(0,1)$, since the map $(w_1,\dots,w_n) \mapsto Z$ is $\rho$-Lipschitz (w.r.t. $\ell_2$ norm) and such functions concentrate as above in the Gaussian setting. We want to relax the Gaussian assumption. Assume that:

1. $\mathcal G$ is uniformly 1-bounded, i.e., $\|g\|_\infty \le 1$ for all $g \in \mathcal G$,
2. $|w_i| \le 1$ almost surely for all $i$.

Question 1: Can we achieve an inequality like (*) in this case?

Some consideration: Using the bounded difference inequality we can have (*) but with $\rho t$ replaced with $t$ which is not good enough. On the other hand, it seems that Talagrand's empirical process inequality applied to the derived function class $\{(w, x) \mapsto w g(x):\; g \in \mathcal G\}$ can give a similar control but with sub-exponential tails $$ \mathbb P( Z - \mathbb E Z \ge \rho t) \le C \exp\bigr( - c \min\{t^2, \rho \sqrt n t\}\bigl), \quad \text{for all}\; t \ge 0. $$ This is close but not quite there. (EDIT: and apparently not correct.)

Answer 1

The answer to Question 1 is yes: Shift-rescale the $w_i$'s by considering $v_i:=(1+w_i)/2$ with values almost surely in $[0,1]$, so that $w_i=2v_i-1$, for all $i$. By the Cauchy--Schwarz inequality, $U_g$ is a $2\rho$-Lipschitz function of $v:=(v_1,\dots,v_n)$. So, $Z/(2\rho)$ is a convex $1$-Lipschitz function of the random point $v$ in $[0,1]^n$. Now use (say) Theorem 13 or, rather, its proof -- look, in particular, at the end of that proof on p. 48 of those notes to get $$P(Z-EZ\ge\rho t)=P\Big(\frac Z{2\rho}-E\frac Z{2\rho}\ge\frac t2\Big)\le e^{-(t/2)^2/2}=e^{-t^2/8}.\quad\Box.$$ (Weirdly, the conclusion of Theorem 13 stated in the notes is not what is actually proved in the proof of Theorem 13, and that conclusion is at odds with the "dimension-free" discussion preceding Theorem 13.)

---

The answer to Question 1.5 is: No, you cannot use Talagrand's empirical process inequality here, because that inequality is for sums of i.i.d. random variables (r.v.'s), whereas your r.v.'s $w_ig(x_i)$ are not i.i.d. in general.