As promised, this post will be about the useful inequality from logarithmic Sobolev inequality post. Without further ado…

Starting simple

We are going to prove the inequality

$$\left( e^{z/2} - e^{y/2} \right)^2 \le \frac{(z-y)^2}{8}(e^{z} + e^{y})$$

for real numbers $z \ge y$.

Proof

We can rewrite the inequality as

$$\left( e^{(z-y)/2} - 1 \right)^2 \le \frac{(z-y)^2}{8}(e^{z-y} + 1).$$

Now, let’s define $x = z - y$, where $x \ge 0$ because $z \ge y$. Let’s move everything to the righthand side and open up the square, which gives

$$0 \le \frac{x^2}{8} (e^x + 1) - \left( e^x - 2e^{x/2} + 1 \right).$$

Now, let’s collect like terms

$$0 \le e^x \left( \frac{x^2}{8} - 1 \right) + \frac{x^2}{8} + 2e^{x/2} - 1 = f(x).$$

When $x = 0$, $f(x)$, i.e., the righthand side, is also 0. Let’s look at the derivative of $f$ to see whether the function is increasing or decreasing:

$$\frac{df(x)}{dx} = \frac{1}{8} e^x (x^2 + 2x - 8) + \frac{x}{4} + e^{x/2}.$$

Unfortunately, that pesky $-e^x$ means we still have some work to do. Let’s keep taking derivatives and see if we can’t get rid of that negative:

$$\begin{align*} \frac{d^2f(x)}{dx^2} &= \frac{1}{8} \left( e^x \left( x^2 + 4x - 6 \right) + 4e^{x/2} + 2 \right) \\ \frac{d^3f(x)}{dx^3} &= \frac{1}{8} \left( e^x \left( x^2 + 6x - 2 \right) + 2e^{x/2} \right) \\ \frac{d^4f(x)}{dx^4} &= \frac{1}{8} \left( e^x \left( x^2 + 8x + 4 \right) + e^{x/2} \right). \end{align*}$$

Cool! The righthand side of $\frac{d^4f(x)}{dx^4} > 0$ since $x \ge 0$. Also, we have that

$$\frac{df(0)}{dx} = \frac{d^2f(0)}{dx^2} = \frac{d^3f(0)}{dx^3} = 0,$$

which means we’re in good shape (because the fourth derivative being positive). In particular, we integrate the fourth derivative four times and conclude that our original function that is always greater than or equal to zero

$$\begin{align*} 0 \le \int \frac{d^4f(x)}{dx^4} \, d^4x &= \frac{e^x (x^2 - 8)}{8} + 2 e^{(x/2)} + \frac{c_1 x^3}{6} + \frac{c_2 x^2}{2} + c_3 x + c_4 \\ &= e^x \left( \frac{x^2}{8} - 1 \right) + \frac{x^2}{8} + 2e^{x/2} - 1, \end{align*}$$

where $c_4 = -1$, $c_3 = 0$, $c_2 = 1/4$, and $c_1 = 0$.

Remarks

This inequality is neat because you can approach it a few different ways. If we didn’t use $x = z - y$, and worked directly with the function of $y$ and $z$, we could’ve gotten away with taking two derivatives instead of four. I find the “$x$-consolidated”, “fourth derivative” approach easier as it requires less bookkeeping for $y$ and $z$.

And the best for last: the easiest way to solve this problem is to plot it. 😏

Next up

… more Rademacher rad-ness, modified logarithmic Sobolev inequalities or bandits!

References

This post is related to material from Chapter 5 of (my new favorite book):

• Concentration Inequalities: A Nonasymptotic Theory of Independence by S. Boucheron, G. Lugosi, and P. Masart.