Use covering number to get uniform concentration from pointwise concentration

Question

Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $L$-Lipschitz and with the property that there exists constants $A, B>0$ such that for every $\epsilon>0$ and $\theta \in \Theta$, it holds that $P(X_\theta \ge \epsilon) \le A\exp(-B\epsilon^2)$.

Question

• What upper bounds can be obtained on $P(\sup_{\theta \in \Theta} X_\theta \ge \epsilon)$ in terms of the Lipschitz constant $L$, and the covering number of $\Theta$ ?

• In case the conditions are not sufficient, what can be added in order to obtain any interesting answers ?

Answer 1

If for all $\theta \in\Theta$ we have $P(X_\theta\ge\epsilon)\le A\exp(-B\epsilon^2)$ and $\Theta$ has $\epsilon$-packing number $M(\epsilon)$ and additionally $X_\theta$ is $L$-Lipschitz in $\theta$, then $$P(\sup_{\theta\in\Theta} X_\theta>\epsilon(L+1)) \le AM(\epsilon)\exp(-B\epsilon^2) .$$

Answer 2

Disclaimer: This is just a detailed version of Aryeh's answer.

So, let $\mathcal C_\epsilon$ be $\epsilon/2$-cover for $\Theta$ of minimal cardinality $N(\Theta;\epsilon/2)$. Let $C \in \mathcal C_\epsilon$ and $\theta_0 \in C$. Then because the distance between any two points in $C$ is at most $\epsilon$, one has $$ \sup_{\theta \in C} X_\theta = X_{\theta_0} + \sup_{\theta \in C}\;(X_\theta-X_{\theta_0}) \le X_{\theta_0} + \epsilon L, $$ and so

$P(\sup_{\theta \in C} X_\theta \ge \epsilon(L+1)) \le P(X_{\theta_0} \ge \epsilon) \le A\exp(-B\epsilon^2)$.

On the other hand,

$$ \sup_{\theta \in \Theta} X_\theta \ge \epsilon(L + 1) \implies \exists \theta \in \Theta | X_\theta \ge \epsilon(L + 1) \implies \exists C \in \mathcal C_\epsilon | \sup_{\theta \in C} X_\theta \ge \epsilon(L+1), $$ and so applying the union bound on the finite cover $\mathcal C_\epsilon$, one gets

$$ \begin{split} P\left(\sup_{\theta \in \Theta} X_\theta \ge \epsilon(L + 1)\right) &\le P\left(\bigsqcup_{C \in \mathcal C_\epsilon}\left\{\sup_{\theta \in C} X_\theta \ge \epsilon(L+1)\right\} \right) \\ &\le \sum_{C \in \mathcal C_\epsilon}P\left(\sup_{\theta \in C} X_\theta \ge \epsilon(L+1)\right)\\ &\le AN(\Theta;\epsilon/2)\exp(-B\epsilon^2). \end{split} $$ Thus, we have the concentration inequality

$$P\left(\sup_{\theta \in \Theta} X_\theta \ge \epsilon\right) \le AN(\Theta;\epsilon/2)\exp\left(-\frac{B\epsilon^2}{L+1}\right) $$