[proofplan] We first handle the degenerate case $L=0$, where the Lipschitz condition forces $f$ to be constant. For $L>0$, the proof uses the Gaussian logarithmic Sobolev inequality together with Herbst's argument to control the centered exponential moment of $f(G)$. The resulting sub-Gaussian moment bound is converted into the tail estimate by Chernoff's inequality and an explicit optimization over the exponential parameter. [/proofplan] [step:Handle the constant case when $L=0$] Assume $L=0$. Then for every $x,y \in \mathbb{R}^n$, \begin{align*} |f(x)-f(y)| \leq 0|x-y|=0. \end{align*} Hence $f(x)=f(y)$ for all $x,y \in \mathbb{R}^n$, so $f$ is constant. Let $a \in \mathbb{R}$ denote this constant value. Then $f(G)=a$ almost surely and $\mathbb{E}[f(G)]=a$, so \begin{align*} f(G)-\mathbb{E}[f(G)]=0 \end{align*} almost surely. Therefore the event $\{f(G)-\mathbb{E}[f(G)] \geq t\}$ has probability $1$ if $t=0$ and probability $0$ if $t>0$. [/step] [step:Verify integrability and introduce the centered random variable] Let $(\Omega,\mathcal{F},\mathbb{P})$ be the probability space on which the Gaussian random vector $G:\Omega\to\mathbb{R}^n$ is defined. Assume now that $L>0$. Since $f$ is $L$-Lipschitz, for every $x \in \mathbb{R}^n$, \begin{align*} |f(x)| \leq |f(0)|+L|x|. \end{align*} Taking $x=G$ and using Cauchy-Schwarz for the real [random variable](/page/Random%20Variable) $|G|$ gives \begin{align*} \mathbb{E}[|G|] \leq \left(\mathbb{E}[|G|^2]\right)^{1/2}=\sqrt{n}. \end{align*} Thus \begin{align*} \mathbb{E}[|f(G)|] \leq |f(0)|+L\sqrt{n}<\infty. \end{align*} Define the centered real-valued random variable $X:\Omega \to \mathbb{R}$ by \begin{align*} X=f(G)-\mathbb{E}[f(G)]. \end{align*} Then $\mathbb{E}[X]=0$. [/step] [step:Use the logarithmic Sobolev inequality to bound exponential moments] For $\lambda>0$, define the moment generating function $M:(0,\infty)\to(0,\infty)$ by \begin{align*} M(\lambda)=\mathbb{E}[e^{\lambda X}] \end{align*} and define $\psi:(0,\infty)\to\mathbb{R}$ by \begin{align*} \psi(\lambda)=\log M(\lambda). \end{align*} The Lipschitz bound gives $|f(x)| \leq |f(0)|+L|x|$, and the standard Gaussian measure has finite exponential moments of linear functions of $|x|$, so $M(\lambda)<\infty$ for every $\lambda>0$. Let $\mathcal{L}^n$ denote $n$-dimensional [Lebesgue measure](/page/Lebesgue%20Measure) on $\mathbb{R}^n$. For a nonnegative measurable function $Y:\mathbb{R}^n\to[0,\infty)$ with finite entropy, define its Gaussian entropy by \begin{align*} \operatorname{Ent}_{\gamma_n}(Y)=\int_{\mathbb{R}^n}Y(x)\log Y(x)\,d\gamma_n(x)-\left(\int_{\mathbb{R}^n}Y(x)\,d\gamma_n(x)\right)\log\left(\int_{\mathbb{R}^n}Y(x)\,d\gamma_n(x)\right). \end{align*} For a nonnegative real-valued random variable $Z:\Omega\to[0,\infty)$ with finite entropy, define \begin{align*} \operatorname{Ent}(Z)=\mathbb{E}[Z\log Z]-\mathbb{E}[Z]\log\mathbb{E}[Z]. \end{align*} We use the Gaussian logarithmic Sobolev inequality for locally Lipschitz functions as an external input, since this result is not yet available as an Androma theorem page. [Rademacher's theorem](/theorems/3069) gives that $f$ is differentiable $\mathcal{L}^n$-a.e., and the Lipschitz condition implies \begin{align*} |\nabla f(x)| \leq L \end{align*} for $\mathcal{L}^n$-a.e. $x \in \mathbb{R}^n$. Applying the logarithmic Sobolev inequality to the locally Lipschitz function $x \mapsto \lambda f(x)$ gives \begin{align*} \operatorname{Ent}_{\gamma_n}(e^{\lambda f}) \leq \frac{\lambda^2}{2}\int_{\mathbb{R}^n} |\nabla f(x)|^2 e^{\lambda f(x)}\,d\gamma_n(x) \leq \frac{\lambda^2L^2}{2}\int_{\mathbb{R}^n} e^{\lambda f(x)}\,d\gamma_n(x). \end{align*} Since multiplying by the constant $e^{-\lambda\mathbb{E}[f(G)]}$ does not change the normalized entropy identity below, this is equivalently \begin{align*} \operatorname{Ent}(e^{\lambda X}) \leq \frac{\lambda^2L^2}{2}\mathbb{E}[e^{\lambda X}]. \end{align*} By the definition of entropy, \begin{align*} \operatorname{Ent}(e^{\lambda X})=\mathbb{E}[\lambda X e^{\lambda X}]-\mathbb{E}[e^{\lambda X}]\log \mathbb{E}[e^{\lambda X}]. \end{align*} For the fixed parameter $\lambda>0$, choose $\varepsilon>0$. The Lipschitz growth bound gives $|X|\leq 2|f(0)|+L|G|+\mathbb{E}[|f(G)|]$ almost surely, and hence $|X|e^{(\lambda+\varepsilon)|X|}$ is integrable because the standard Gaussian random vector has finite exponential moments of $|G|$. Therefore differentiation under the expectation is justified on a neighbourhood of $\lambda$, so $M'(\lambda)=\mathbb{E}[Xe^{\lambda X}]$. Since $\psi'(\lambda)=M'(\lambda)/M(\lambda)$, division by $M(\lambda)>0$ yields \begin{align*} \lambda\psi'(\lambda)-\psi(\lambda)\leq \frac{\lambda^2L^2}{2}. \end{align*} [guided] The goal of this step is to prove a sub-Gaussian bound for the exponential moment of $X=f(G)-\mathbb{E}[f(G)]$. Exponential moments are the right object because Markov's inequality can later turn them into tail bounds. For $\lambda>0$, define \begin{align*} M(\lambda)=\mathbb{E}[e^{\lambda X}] \end{align*} and \begin{align*} \psi(\lambda)=\log M(\lambda). \end{align*} These quantities are finite because the Lipschitz condition gives \begin{align*} |f(x)| \leq |f(0)|+L|x|, \end{align*} and standard Gaussian random vectors have finite exponential moments of $|G|$. Let $\mathcal{L}^n$ denote $n$-dimensional Lebesgue measure on $\mathbb{R}^n$. For a nonnegative measurable function $Y:\mathbb{R}^n\to[0,\infty)$ with finite entropy, define its Gaussian entropy by \begin{align*} \operatorname{Ent}_{\gamma_n}(Y)=\int_{\mathbb{R}^n}Y(x)\log Y(x)\,d\gamma_n(x)-\left(\int_{\mathbb{R}^n}Y(x)\,d\gamma_n(x)\right)\log\left(\int_{\mathbb{R}^n}Y(x)\,d\gamma_n(x)\right). \end{align*} For a nonnegative real-valued random variable $Z:\Omega\to[0,\infty)$ with finite entropy, define \begin{align*} \operatorname{Ent}(Z)=\mathbb{E}[Z\log Z]-\mathbb{E}[Z]\log\mathbb{E}[Z]. \end{align*} We now use the Gaussian logarithmic Sobolev inequality for locally Lipschitz functions as an external input, since this result is not yet available as an Androma theorem page. Its relevant form says that, for a locally Lipschitz function $u:\mathbb{R}^n\to\mathbb{R}$, \begin{align*} \operatorname{Ent}_{\gamma_n}(e^u)\leq \frac{1}{2}\int_{\mathbb{R}^n}|\nabla u(x)|^2e^{u(x)}\,d\gamma_n(x). \end{align*} We take $u(x)=\lambda f(x)$. Since $f$ is Lipschitz, Rademacher's theorem gives differentiability $\mathcal{L}^n$-a.e., and the pointwise derivative satisfies \begin{align*} |\nabla f(x)|\leq L \end{align*} for $\mathcal{L}^n$-a.e. $x$. Therefore $|\nabla(\lambda f)(x)|^2\leq \lambda^2L^2$ almost everywhere, and the logarithmic Sobolev inequality gives \begin{align*} \operatorname{Ent}_{\gamma_n}(e^{\lambda f})\leq \frac{\lambda^2L^2}{2}\int_{\mathbb{R}^n}e^{\lambda f(x)}\,d\gamma_n(x). \end{align*} Centering by $\mathbb{E}[f(G)]$ only multiplies $e^{\lambda f}$ by a positive constant. Entropy is homogeneous in the sense that $\operatorname{Ent}(cY)=c\operatorname{Ent}(Y)$ for every constant $c>0$, so the same inequality becomes \begin{align*} \operatorname{Ent}(e^{\lambda X})\leq \frac{\lambda^2L^2}{2}\mathbb{E}[e^{\lambda X}]. \end{align*} Now compute the entropy term explicitly. By definition, \begin{align*} \operatorname{Ent}(e^{\lambda X})=\mathbb{E}[\lambda Xe^{\lambda X}]-\mathbb{E}[e^{\lambda X}]\log\mathbb{E}[e^{\lambda X}]. \end{align*} Because $M(\lambda)=\mathbb{E}[e^{\lambda X}]$, we next justify differentiating under the expectation. Fix the current $\lambda>0$ and choose $\varepsilon>0$. The Lipschitz estimate and centering give the almost sure bound \begin{align*} |X|\leq 2|f(0)|+L|G|+\mathbb{E}[|f(G)|]. \end{align*} Thus $|X|e^{(\lambda+\varepsilon)|X|}$ is integrable, because $G$ is standard Gaussian and therefore has finite exponential moments of $|G|$. This integrable random variable dominates the difference quotients for $e^{sX}$ when $s$ stays near $\lambda$, so the [dominated convergence theorem](/theorems/4) justifies \begin{align*} M'(\lambda)=\mathbb{E}[Xe^{\lambda X}]. \end{align*} Hence \begin{align*} \psi'(\lambda)=\frac{M'(\lambda)}{M(\lambda)}. \end{align*} Dividing the [entropy inequality](/theorems/6729) by $M(\lambda)>0$ gives the differential inequality \begin{align*} \lambda\psi'(\lambda)-\psi(\lambda)\leq \frac{\lambda^2L^2}{2}. \end{align*} This is the key Herbst inequality: it converts the functional inequality into a one-variable differential estimate for the log moment generating function. [/guided] [/step] [step:Integrate the Herbst differential inequality] Define $\Phi:(0,\infty)\to\mathbb{R}$ by \begin{align*} \Phi(\lambda)=\frac{\psi(\lambda)}{\lambda}. \end{align*} The preceding step gives \begin{align*} \Phi'(\lambda)=\frac{\lambda\psi'(\lambda)-\psi(\lambda)}{\lambda^2}\leq \frac{L^2}{2}. \end{align*} Extend $M$ to $[0,\infty)$ by $M(0)=1$ and extend $\psi$ by $\psi(0)=0$. The same domination argument used above, now in a neighbourhood of $0$, gives $M'(0)=\mathbb{E}[X]$. Since $\mathbb{E}[X]=0$ and $M(0)=1$, we obtain $\psi'(0)=M'(0)/M(0)=0$. Therefore \begin{align*} \lim_{\lambda\downarrow 0}\Phi(\lambda)=\lim_{\lambda\downarrow 0}\frac{\psi(\lambda)-\psi(0)}{\lambda}=\psi'(0)=0. \end{align*} Integrating the inequality for $\Phi'$ from $0$ to $\lambda$ gives \begin{align*} \frac{\psi(\lambda)}{\lambda}\leq \frac{\lambda L^2}{2}. \end{align*} Thus, for every $\lambda>0$, \begin{align*} \psi(\lambda)\leq \frac{\lambda^2L^2}{2}. \end{align*} Equivalently, \begin{align*} \mathbb{E}[e^{\lambda X}]\leq \exp\left(\frac{\lambda^2L^2}{2}\right). \end{align*} [/step] [step:Apply Chernoff's inequality and optimize the parameter] Fix $t\geq 0$. If $t=0$, then \begin{align*} \mathbb{P}(X\geq 0)\leq 1=\exp(0)=\exp\left(-\frac{0^2}{2L^2}\right). \end{align*} It remains to consider $t>0$. Fix $\lambda>0$. Since the exponential function is increasing, \begin{align*} \mathbb{P}(X\geq t)=\mathbb{P}(e^{\lambda X}\geq e^{\lambda t}). \end{align*} Markov's inequality applied to the nonnegative random variable $e^{\lambda X}$ gives \begin{align*} \mathbb{P}(X\geq t)\leq e^{-\lambda t}\mathbb{E}[e^{\lambda X}]. \end{align*} Using the exponential moment estimate from the preceding step, \begin{align*} \mathbb{P}(X\geq t)\leq \exp\left(-\lambda t+\frac{\lambda^2L^2}{2}\right). \end{align*} Choose \begin{align*} \lambda=\frac{t}{L^2}. \end{align*} This choice is valid because $L>0$ and we are in the case $t>0$. Substituting it gives \begin{align*} -\lambda t+\frac{\lambda^2L^2}{2}=-\frac{t^2}{L^2}+\frac{t^2}{2L^2}=-\frac{t^2}{2L^2}. \end{align*} Therefore \begin{align*} \mathbb{P}(f(G)-\mathbb{E}[f(G)]\geq t)\leq \exp\left(-\frac{t^2}{2L^2}\right). \end{align*} Taking $c=\frac{1}{2}$ gives the stated universal-constant form as an immediate consequence. [/step]