Concentration Inequality for Bounding Lipschitz Empirical Lass

Question

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, $(X_n:\Omega\rightarrow \mathbb{R}^m)_n$ be a sequence of i.i.d. random variables and let $L:\mathbb{R}^m\rightarrow [0,\infty)$ be Lipschitz. Let $\mu_n:=\frac1{n} \sum_{k=1}^n \delta_{X_k}$. Are there conditions under which: $$ \mathbb{P}\left(|\mathbb{E}_{X\sim\mu_n}[L(X)]-\mathbb{E}_{X\sim Law(X_1)}[L(X)]|\geq t\right)\leq \exp\left( I(t) \right), $$ where $I$ is a good rate function?

Answer 1

Your inequality is trivial and useless as written. On its left-hand side we have a probability which is $\le1$ and goes to $0$ as $t\to\infty$, whereas on the right-hand side we have an expression which is $\ge1$ and goes to $\infty$ as $t\to\infty$, because for any good rate function $I$ on $[0,\infty)$ we have $I(t)\to\infty$ as $t\to\infty$. Also, the left-hand side of your inequality depends on $n$, whereas the right-hand side does not. Overall, this is not how a good rate function is used.

The corrected version of your inequality is as follows: \begin{equation*} P(|T_n|\ge t)\le e^{-nI(t)} \tag{1} \end{equation*} for some good rate function $I$ and all real $t\ge0$, where \begin{equation*} T_n:=\frac1n\,\sum_1^n Y_k,\quad Y_k:=L(X_k)-EL(X_k). \end{equation*}

Moreover, the conditions that the $X_k$'s take values in $\mathbb R^m$ and that $L$ is Lipschitz are of no relevance. Instead, all we need here is that the $Y_k$'s are iid zero-mean real-valued random variables.

Once all this preliminary cleaning is done, we can now say that for (1) to hold (for some good rate function $I$ and all real $t\ge0$), it is sufficient that \begin{equation*} Ee^{h|Y_1|}<\infty \tag{2} \end{equation*} for some real $h>0$. (It is also easy to see that (2) is also necessary for (1).)

Indeed, assume (2) holds for some real $h>0$. By Markov's inequality, for any $t\ge0$, \begin{equation*} P(T_n\ge t)\le e^{-ntx+nl(x)} \end{equation*} for all $x\ge0$, where \begin{equation*} l(x):=\ln Ee^{xY_1} \end{equation*} and hence \begin{equation*} P(T_n\ge t)\le e^{-nI_+(t)}, \end{equation*} where \begin{equation*} I_+(t):=\sup_{x\ge0}(tx-l(x)). \end{equation*} Similarly, \begin{equation*} P(-T_n\ge t)\le e^{-nI_-(t)}, \end{equation*} where \begin{equation*} I_-(t):=\sup_{x\ge0}(tx-l(-x)), \end{equation*} so that \begin{equation*} P(|T_n|\ge t)\le\min(1,e^{-nI_+(t)}+e^{-nI_-(t)}). \tag{3} \end{equation*} Note that $I_+(t)\ge th-l(h)\to\infty$ as $t\to\infty$, and similarly $I_-(t)\to\infty$ as $t\to\infty$. Also, the functions $I_\pm$ are nondecreasing and lower semi-continuous, being the pointwise suprema of a family of nondecreasing continuous functions; so, the functions $I_\pm$ are also left-continuous. Also, $I_\pm(0)=0$ -- because $l(0)=0$, $l'(0)=EY_1=0$, and $l$ is convex, so that $l(x)\ge0$ for all $x\ge0$. So, there exists \begin{equation*} t_*:=\max\{t\ge0\colon e^{-I_+(t)}+e^{-I_-(t)}\ge1\}\in(0,\infty), \end{equation*} and then $e^{-I_+(t)}+e^{-I_-(t)}\ge1$ for $t\in[0,t_*]$ and $e^{-I_+(t)}+e^{-I_-(t)}<1$ for $t\in(t_*,\infty)$. Defining now the function $I$ by the requirement that \begin{equation*} e^{-I(t)}=e^{-I_+(t)}+e^{-I_-(t)} \end{equation*} for $t>t_*$, with $I(t):=0$ for $t\in[0,t_*]$, we get \begin{equation*} \min(1,e^{-nI_+(t)}+e^{-nI_-(t)})\le e^{-nI(t)} \end{equation*} for all natural $n$ and all real $t\ge0$.

Thus, (3) yields (1).