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.



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$
$\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)](https://projecteuclid.org/euclid.aop/1176988847). 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). 


