The Extremal Principle for Estimating Integrals — A Beginner's Version of the Variational Principle

积分估计的极值原理——变分原理的初级版本 苏剑林 · 2016-02-15 · Mathematics inequality integral extremum

Regular readers of Scientific Spaces will have noticed that I've always had a soft spot for extremal principles. For instance, I once wrote a series of posts called Natural Extrema, introducing various extremal problems and the calculus of variations; in physics, I'm partial to the formulation based on the principle of least action; in data mining, this is also why I've taken a strong interest in maximum entropy models built on the maximum entropy principle. Recently, while working through exercises from Quantum Mechanics and Path Integrals, I also became very interested in the variational principle discussed in Chapter 11.

When learning something new, my method is to work out its underlying principle and idea using the simplest possible example, and only then gradually build up to more complex cases — that way I don't lose my footing. The variational principle is a powerful method for estimating path integrals, and path integrals are functional integrals, or in other words, infinite-dimensional integrals. So it's natural to ask: is there an analogous estimation principle for finite-dimensional integrals, say the simplest one-dimensional integral? As it turns out, there is, and it's not complicated at all — understanding it helps clarify the core idea behind the variational principle. Unfortunately, I haven't found existing material that describes this simplified version, which may just be because I haven't searched hard enough.

Starting from a Gaussian-type integral

The variational principle is, at its core, an application of Jensen's inequality. Let's start from the following integral:

$$\begin{equation}\label{jifen}I(\epsilon)=\int_{-\infty}^{\infty}e^{-x^2-\epsilon x^4}dx\end{equation}$$more

We have previously studied this integral from the perspective of perturbative expansion. This integral is usually regarded as a one-dimensional version of the more complicated path integral, and studying it typically yields useful strategies for tackling path integrals in general. To estimate the integral above, a very natural idea arises: can we represent it using a simple Gaussian integral instead?

$$\begin{equation}\label{jinsi}\int_{-\infty}^{\infty}e^{-px^2}dx=\sqrt{\frac{\pi}{p}}\end{equation}$$

The key question is how to choose $p$ so that $\eqref{jinsi}$ is as close as possible to $\eqref{jifen}$. Let's rewrite $\eqref{jifen}$ as

$$\begin{equation}\label{bianhuan}I(\epsilon)=\sqrt{\frac{\pi}{p}}\int_{-\infty}^{\infty}e^{(p-1)x^2-\epsilon x^4}\left(\sqrt{\frac{p}{\pi}}e^{-px^2}\right)dx\end{equation}$$

How should we interpret $\eqref{bianhuan}$? I've deliberately written it in this particular form — from a statistical point of view, it is the average of $e^{(p-1)x^2+q-\epsilon x^4}$ under the weight $\sqrt{\frac{p}{\pi}}e^{-px^2}$. So we might as well write it as

$$\begin{equation}\label{pingjun}I(\epsilon)=\sqrt{\frac{\pi}{p}}\left\langle e^{(p-1)x^2-\epsilon x^4}\right\rangle\end{equation}$$

Let me remind you again: this integral is an average taken under the weight $\sqrt{\frac{p}{\pi}}e^{-px^2}$. So far, all we've done is a formal rewriting — there's been no substantive progress, and we still haven't actually computed the integral we set out to compute.

Now let's recall Jensen's inequality: it states that if $f(x)$ is a convex function (regarding convexity, different books may use slightly different definitions; here, a convex function is one whose second derivative is non-negative), then

$$\begin{equation}\label{jensen}f(\langle x \rangle)\leq \langle f(x) \rangle\end{equation}$$

You may be used to seeing Jensen's inequality written differently, but if you think it over carefully, isn't this exactly what it's saying? Jensen's inequality has a clear physical meaning: if several points lie on the graph of a convex function, then the centroid of these points lies above the convex function.

Using Jensen's inequality, we can further simplify $\eqref{pingjun}$, since it's clear that $e^x$ is a convex function, and therefore

$$\begin{equation}\label{pingjun-jensen}I(\epsilon)=\sqrt{\frac{\pi}{p}}\left\langle e^{(p-1)x^2-\epsilon x^4}\right\rangle \geq \sqrt{\frac{\pi}{p}}e^{\left\langle (p-1)x^2-\epsilon x^4\right\rangle}\end{equation}$$

where $\left\langle (p-1)x^2-\epsilon x^4\right\rangle$ can be computed directly:

$$\left\langle (p-1)x^2-\epsilon x^4\right\rangle=\int_{-\infty}^{\infty}\left[(p-1)x^2-\epsilon x^4\right]\left(\sqrt{\frac{p}{\pi}}e^{-px^2}\right)dx=\frac{2 (p-1) p-3 \epsilon}{4 p^2}$$

so that

$$\begin{equation}\label{pingjun-guji}I(\epsilon)\geq\sqrt{\frac{\pi}{p}}\exp\left[\frac{2 (p-1) p-3 \epsilon}{4 p^2}\right]\end{equation}$$

No matter how we choose $p$, the rightmost expression will always be smaller than $I(\epsilon)$. So naturally, in order to get as close as possible to $I(\epsilon)$, we should choose $p$ so that the right-hand side of the inequality attains its maximum value! This is where the extremal principle comes from. Taking the derivative, we find that the right-hand side is maximized when

$$p=\frac{1}{2} \left(\sqrt{12 \epsilon+1}+1\right)$$

Substituting this back into $\eqref{pingjun-guji}$ gives

$$\begin{equation}\label{pingjun-guji2}I(\epsilon)\geq \sqrt{\frac{2 \pi }{\sqrt{12 \epsilon+1}+1}}\exp\left[\frac{3 \epsilon}{\left(\sqrt{12 \epsilon+1}+1\right)^2}\right]=\hat{I}(\epsilon)\end{equation}$$

Here are some results:

$$\begin{array}{c|cccc} \hline & \epsilon=0 & \epsilon=1 & \epsilon=10 & \epsilon=100 \\ \hline I(\epsilon) & 1.77245 & 1.36843 & 0.921961 & 0.554577 \\ \hat{I}(\epsilon) & 1.77245 & 1.34547 & 0.891204 & 0.531509 \\ \hline \end{array}$$

Comparing with the results in http://kexue.fm/archives/3280/, we can see that $\hat{I}(\epsilon)$ is a rather good estimate, and indeed $\hat{I}(\epsilon)\leq I(\epsilon)$ holds.

My Summary

From the process above, we can see some of the power of the extremal principle: it provides a good estimate of the integral, and this estimate is stable — no matter the magnitude of the parameter $\epsilon$, a reasonable estimate can always be obtained. Moreover, it doesn't merely give an estimate of the integral, but the estimate is also a lower bound on the integral, which is quite a valuable feature. Ordinarily, we can use all sorts of methods to obtain a useful estimate of an expression, but it's often hard to determine the relationship between the estimated value and the exact value (unless we sacrifice a great deal of precision). The extremal principle achieves both at once — it retains high accuracy while also giving us a bound.

The extremal principle discussed in this post derives from Jensen's inequality, and the key point is that $e^x$ is a convex function, and $e^{\left\langle h(x)\right\rangle}$ is usually easier to compute than $\left\langle e^{h(x)}\right\rangle$. So the direction for generalization is clear: switch to other weights, or replace $e^x$ with a general convex function, as long as $f(\left\langle h(x)\right\rangle)$ is easier to compute than $\left\langle f(h(x))\right\rangle$.

Of course, the drawbacks of the extremal principle are also quite obvious. First, finding a good, integrable approximating function is not easy. Second, even if we can carry out the integration, the subsequent process of finding the extremum is not necessarily simple either, since it involves solving nonlinear equations, and once approximations are introduced, the result often degenerates back into a perturbative expansion, losing the unique advantages of the variational method. Finally, there's a less obvious drawback of the extremal principle's estimate: it's very difficult to further improve its accuracy.