1
$\begingroup$

I am reading the book Bandit Algorithms. On page 257, it talks about how to approximate the maximum of a function with Laplace's method. I cannot understand how this method can be used to find the maximum of a function. The book presents Laplace's method as follows:

Assume that $f:[a,b]\rightarrow\mathbb{R}$ is twice differentiable and has a unique maximum at $x_0\in (a,b)$ with $-q=f^{''}(x_0)<0$. Laplace's method for approximating $f(x_0)$ is to compute the integral $$ I_s=\int_{a}^{b}\exp\left( sf(x) \right)\: dx $$

I am wondering how we can determine $f(x_0)$ from $I_s$. I would be thankful if someone can give me an example and intuition behind this method. I read Wikipedia page but I don't understand how it can be used to find the maximum of a function.

on Page 258, it presents "Method of Mixtures" as follows:

Lapalce's approximation suggests that $\max_{x} \: M_t(x)\approx \int_{\mathbb{R}^d} M_t(x)\: dh(x)$, where $h$ is some measure on $\mathbb{R}^d$ chosen so that the integral can be calculated in closed form.

I am wondering if $h(x)$ should be always a probability distribution and if $M_t(x)$ can be any arbitrary function.

$\endgroup$

1 Answer 1

1
$\begingroup$

The intuition behind Laplace's method is that because the exponential function exaggerates large values, as $s\rightarrow \infty$, the function $x\mapsto e^{sf(x)}$ will eventually be totally dominated by its maximum value, which is $e^{s f(x_0)}$, where $x_0$ maximizes $f$.

It's easier to see this in the discrete case first, so let $f \colon \{1, \dotsc, n\} \rightarrow \mathbf{R}$ and let $x_0 = \mathop{\mathrm{argmax}}_{x} f(x)$ be a unique maximizer. Now, we have that \begin{align*} \sum_{x=1}^n e^{sf(x)} &= e^{s f(x_0)}\sum_{x=1}^n e^{s(f(x) - f(x_0))} \\ &= e^{s f(x_0)}\Bigl(1 + \sum_{x\neq x_0} e^{s(f(x) - f(x_0))}\Bigr) \\ &= e^{s f(x_0)}(1 + o(1)), \end{align*} where we see that the latter sum is $o(1)$ from the fact that $f(x) < f(x_0)$ for each $x \neq x_0$.

Therefore, in this case, we can determine $f(x_0)$ from the resulting limit $$ \frac{1}{s}\log\Bigl(\sum_{x=1}^n e^{sf(x)}\Bigr) \rightarrow f(x_0). $$

The continuous case is more complicated since we have to take into account the curvature of $f$ at $x_0$, but the idea is the same. I'll omit the technical details, which are presented in the textbook that you linked, but the upshot is that the analogous result is that \begin{align*} \int_a^b e^{s f(x)} dx &= e^{s f(x_0)} \sqrt{\frac{2\pi}{s |f''(x_0)|}}(1 + o(1)), \end{align*} from which we similarly get that $$ \frac{1}{s}\log\Bigl(\int_a^b e^{s f(x)} dx\Bigr) \rightarrow f(x_0). $$


As for your second question, the $h$ need not be a probability measure, and that this doesn't matter much due to the very liberal meaning of $\approx$.

In particular, since we're taking $s^{-1}\log I_s$, the $\approx$ can hide even any polynomial factor without affecting the result. So unless $h$ is really bad (like $dh(x) = e^{|x|} dx$ or something), there's no problem.

We can again see what's going on schematically in the discrete case, so let $h$ be any measure on $\{1, \dotsc, n\}$. We then have that \begin{align*} \int e^{s f(x)} dh(x) = \sum_{x=1}^n e^{s f(x)} h(x) = e^{s f(x_0)}(h(x_0) + o(1)), \end{align*} from which we have \begin{align*} \frac{1}{s}\log \Bigl(\int e^{s f(x)} dh(x)\Bigr) = f(x_0) + \frac{1}{s}\log(h(x_0) + o(1)) \rightarrow f(x_0). \end{align*}

Basically, $e^{s f(x)}$ only cares about what's going on in the immediate vicinity of $x_0$, where the value of the measure is approximately constant. But then any constant contribution gets killed by the $s^{-1} \log I_s$ transformation.

$\endgroup$
5
  • $\begingroup$ Thank you so much for the great explanation. Regarding the "Method of Mixtures", I would be thankful if you could help me know what are the requirements for this method. $\endgroup$
    – Amin
    Oct 11, 2022 at 4:24
  • 1
    $\begingroup$ See the latest edits to my post $\endgroup$ Oct 11, 2022 at 4:54
  • $\begingroup$ Thanks @Damian. Your answer for the second part seems a bit different. I mean you considered $\int e^{sf(x)} dh(x)$ but not $\int f(x)\: dh(x)$. $\endgroup$
    – Amin
    Oct 11, 2022 at 15:56
  • 1
    $\begingroup$ Right, but in the textbook $M_t(x) = \exp\{\langle x, S_t\rangle - \frac{1}{2}\lVert x\rVert_{V_t(\lambda)}^2\}$, which is sort-of of the form $e^{t f(x)}$. Of course, it isn't exactly, but this is why Laplace's method merely "suggets" the approximation rather than showing it $\endgroup$ Oct 12, 2022 at 2:23
  • $\begingroup$ Ooo. I missed this point and I thought that it is true for all functions. I really appreciate your help $\endgroup$
    – Amin
    Oct 12, 2022 at 4:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .