###### tags: `one-offs` `diffusions` `sampling` # On the Benefits of Marginalisation for Langevin Diffusions **Overview**: In this note, I compare the convergence behaviour of Langevin diffusions as applied to joint and marginal simulation. I give a quick proof that when possible, simulating the marginal process leads to convergence which is at least as rapid as that of the joint process. ## Prelude and Problem Setting A basic thought is that at different times, there have been innovations in Monte Carlo which are centered around both "add in extra variables to make sampling easier" and "marginalise out variables to make sampling easier". Of course, there is no contradiction per se, since "easier" means different things in each case. A small related exercise: fix a nice density $p\left(x,y\right)$, with $\left(x,y\right)$ of arbitrary dimension (and not necessarily equal). Consider using the standard overdamped Langevin diffusion to sample from 1. the joint distribution $p\left(x,y\right)$, and 2. the marginal distribution $p\left(x\right)$. Prove that for an appropriate measure of convergence, the marginal sampler will converge at least as fast as the joint sampler. ## Solution Since any overdamped Langevin diffusion is reversible with respect to its invariant measure, its $L^{2}$ convergence rate can be written in terms of the Rayleigh quotient as \begin{align} \gamma_{\mathrm{Joint}} &:=\inf\left\{ \frac{\int p\left(x,y\right)\cdot\left|\nabla_{x,y}f\left(x,y\right)\right|^{2}\,\mathrm{d}x\,\mathrm{d}y}{\int p\left(x,y\right)\cdot\left|f\left(x,y\right)\right|^{2}\,\mathrm{d}x\,\mathrm{d}y}:p\left(f\right)=0,p\left(f^{2}\right)<\infty\right\} \\ \gamma_{\mathrm{Marginal}} &:=\inf\left\{ \frac{\int p\left(x\right)\cdot\left|\nabla_{x}f\left(x\right)\right|^{2}\,\mathrm{d}x}{\int p\left(x\right)\cdot\left|f\left(x\right)\right|^{2}\,\mathrm{d}x}:p\left(f\right)=0,p\left(f^{2}\right)<\infty\right\} . \end{align} Consider the infimum which defines $\gamma_{\mathrm{Joint}}$, but taken over functions $f$ which depend only on $x$. Since this infimum is taken over a smaller set, it will be greater. It thus follows that \begin{align} \gamma_{\mathrm{Joint}} &\leqslant \inf\left\{ \frac{\int p\left(x,y\right)\cdot\left|\nabla_{x}f\left(x\right)\right|^{2}\,\mathrm{d}x\,\mathrm{d}y}{\int p\left(x,y\right)\cdot\left|f\left(x\right)\right|^{2}\,\mathrm{d}x\,\mathrm{d}y}:p\left(f\right)=0,p\left(f^{2}\right)<\infty\right\} \\ &=\inf\left\{ \frac{\int p\left(x\right)\cdot\left|\nabla_{x}f\left(x\right)\right|^{2}\,\mathrm{d}x}{\int p\left(x\right)\cdot\left|f\left(x\right)\right|^{2}\,\mathrm{d}x}:p\left(f\right)=0,p\left(f^{2}\right)<\infty\right\} \\ &=\gamma_{\mathrm{Marginal}}. \end{align} The spectral gap of the marginal process is thus lower-bounded by that of the joint process, establishing that the marginal sampler converges at least as fast as the joint sampler.
Last changed by  
 
sp-monte-carlo
637

Read more

Denoising Diffusions

Overview: In this note, I log some basic observations about diffusion-based generative models.

8/14/2023
Nested Structure in MCMC Algorithms

Overview: In this note, I describe some aspects of hierarchical structure in MCMC algorithms, and how they can be of theoretical and practical relevance.

8/9/2023
The "Approximation to What?" Principle

Overview: In this note, I discuss a recurrent question which can be used to generate research questions about methods of all sorts. I then discuss a specific instance of how this question has proved fruitful in the theory of optimisation algorithms. Methods and Approximations A nice story is that when Brad Efron derived the bootstrap, it was done in service of the question “What is the jackknife an approximation to?”. I can't help but agree that there's something quite exciting about research questions which have this same character of ''What is (this existing thing) an approximation to?''. One bonus tilt on this which I appreciate is that there can be multiple levels of approximation, and hence many answers to the same question. One well-known example is gradient descent, which can be viewed as an approximation to the proximal point method, which can then itself be viewed as an approximation to a gradient flow. There are probably even more stops along the way here. In this case, there is even the perspective that from the perspective of mathematical theory, there may be at least as much to be gained by stopping off at the proximal point interpretation, as there is from the gradient flow perspective. My experience is that generalist applied mathematicians get to grips with the gradient flow quickly, but optimisation theorists can squeeze more out of the PPM formulation. There is thus some hint that using this 'intermediate' approximation can be particularly insightful in its own right. It would be interesting to collect more examples with this character.

5/22/2023
Hoeffding's Inequality by Convex Ordering

Overview: In this note, I prove Hoeffding's inequality from the perspectives of martingales and convex ordering. The Basic Construction Let $-\infty<a<x<b<\infty$, and define a random variable $M$ with law $M\left(x;a,b\right)$ by \begin{align} M=\begin{cases} a & \text{w.p. }\frac{b-x}{b-a}\ b & \text{w.p. }\frac{x-a}{b-a}. \end{cases}

5/22/2023
Read more from sp-monte-carlo
Published on HackMD