# Concentration Inequality for Bounding Lipschitz Empirical Lass

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?

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).

• @Joe_Affine : Oops, I did miss the normalization. This is now fixed. I think this result is partly folklore, which can be found in books on large deviations, except that they seem to be usually focused on asymptotics, rather than inequalities. Here the main difficulty was converting the two rates $I_\pm$ into one rate $I$. Aug 9, 2021 at 17:18
• That makes sense, at first glance, the result looks very similar to Cramèr's Theorem in LD Theory...So I guess maybe it would appear embedded within that result's proof (I'll take a look); also thanks! Aug 11, 2021 at 7:22