Uniform inequality of the form $\text{Proba}(\sup_{v \in [-M,M]^k}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta$

Question

Let $M > 0$, $k$ be a positive integer, and $\mathcal V:=[-M,M]^k$. Finally, let $p \in \Delta_k$, (where $\Delta_k$ is the $(k-1)$-dimensional probability simplex) and let $\hat{p}_n$ be an empirical version of $p$ based on an iid sample of size $n$. Given $\delta \in (0, 1)$, my objective to obtain a uniform-bound of the form

[Objective] $\text{Proba}(\sup_{v \in \mathcal V}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta $, for some $\epsilon_n >0 $ (the smaller the better).

Idea using covering argument

Presumably, for each $v \in \mathcal V$, I can use Bernstein's inequality to control $|p^Tv-\hat{p}_n^Tv|$. For example,

$$ \text{Proba}\left(|p^Tv-\hat{p}_n^Tv| \le \left(\operatorname{Var}_p(v)\frac{\log(2/\delta)}{n}\right)^{1/2} + \frac{2M\log(2/\delta)}{3n}\right) \ge 1 -\delta. $$

On the other hand,

The mapping $G:v \mapsto |p^Tv-\hat{p}_n^Tv|$ is $2$-Lipschitz w.r.t the $\ell_\infty$-norm on $\mathbb R^k$.

Indeed, for all $v',v \in \mathcal V$, one has $$ \begin{split} |G(v')-G(v)| &:= ||p^Tv'-\hat{p}_n^Tv'|-|p^Tv-\hat{p}_n^Tv|| \le |p^Tv'-\hat{p}_n^Tv'-(p^Tv-\hat{p}_n^Tv)|\\ &= |p^T(v'-v)-\hat{p}_n^T(v'-v)| \le |p^T(v'-v)|+|\hat{p}_n^T(v'-v)| \\ &\le (\|p\|_1+\|\hat{p}_n\|_1)\|v'-v\|_\infty = 2 \|v'-v\|_\infty, \end{split} $$ where the first and second inequalities are triangle inequalities, the third inequality is a Cauchy-Schwarz inequality, and the last inequality is because $p,\hat{p}_n \in \Delta_k$ are probability distributions.

Also, the sup-norm covering number of $\mathcal V$ is $\mathcal N_\infty(\mathcal V;\varepsilon)\le(2M/\varepsilon)^k$.

By using the fact that $\|v\|_\infty \le M$ for all $v \in \mathcal V$, I can replace the variance term in the above Bernstein bound (i.e we'd use a Hoeffding inequality instead) to get $\operatorname{Var}_p(v) \le M^2$ for all $v \in \mathcal V$, and then use covering arguments (e.g see https://mathoverflow.net/a/322161/78539) to get an inequality of the sough-for form [Objective] above. However, such an inequality is presumably "blurred".

Question

How can these ramblings be pieced together to obtain a strong uniform inequality of the form [objective] ? Of course, I'm more than happy to learn other tricks for obtain such a results, which might not use any of the ideas I've discussed above.

Answer 1

$\newcommand{\R}{\mathbb{R}} \newcommand{\ep}{\epsilon} $ Apparently, the still best available general result from which your desired bound will follow is the now pretty old result due to Talagrand, Theorem 1.3, part (ii). Indeed, the probability in the tiltle of your question can be rewritten as \begin{equation*} P\Big(\sup_{\|u\|_\infty\le1/k}\Big(\sum_1^nf_u(X_i)-n\,Ef_u(X_1)\Big)\le t\sqrt n\Big), \end{equation*} where $f_u(x):=(1+u\cdot x)/2$, $u\cdot x:=u_{(1)}x_{(1)}+\dots+u_{(k)}x_{(k)}$ and $\|u\|_\infty:=\max(|u_{(1)}|,\dots,|u_{(k)}|)$ for $u=(u_{(1)},\dots,u_{(k)}),x=(x_{(1)},\dots,x_{(k)})\in\R^k$, \begin{equation*} t:=\frac{\ep_n\sqrt n}{2kM}, \tag{1} \end{equation*} $X_i:=(X_{i1},\dots,X_{i,k})$, $X_{ij}:=1_{Y_i=j}$, $Y_1,\dots,Y_n$ are iid random variables such that $P(Y_1=j)=p_{(j)}$ for $j=1,\dots,k$, and $(p_{(1)},\dots,p_{(k)}):=p$.

Applying the mentioned theorem by Talagrand, we get your desired inequality with \begin{equation*} \delta=(Kt/\sqrt k)^k e^{-2t^2}, \end{equation*} where $K>0$ is an absolute real constant and $t$ is as in (1).