# 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$

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.

• Recently I am reading some materials in learning theory. I just notice that Talagrand's inequality can be used for establishing a uniform concentration inequality for empirical process, but the condition in the original paper requires the function class to be countably infinite, which seems does not apply for many parametric model. Commented Feb 14, 2022 at 20:24

$$\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).
• Hi. Actually, I just looked at the Talagrand paper for the first time now, and it seems that the results in the paper assume the function class $\mathcal F$ is countable. In the case here, $\mathcal F = \{f_u \mid \|u\|_\infty \le 1/k\}$ which is not countable. Thus the results of the paper, specifically Theorem 1.3, don't apply. No ? Commented Oct 30, 2019 at 9:52