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?
1 Answer
Your inequality is trivial and useless as written. On its lefthand side we have a probability which is $\le1$ and goes to $0$ as $t\to\infty$, whereas on the righthand 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 lefthand side of your inequality depends on $n$, whereas the righthand 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 zeromean realvalued 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^{hY_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}(txl(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}(txl(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 thl(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 semicontinuous, being the pointwise suprema of a family of nondecreasing continuous functions; so, the functions $I_\pm$ are also leftcontinuous. 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).

$\begingroup$ @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$. $\endgroup$ Aug 9, 2021 at 17:18

$\begingroup$ 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! $\endgroup$ Aug 11, 2021 at 7:22