Sampling Playground: Algorithms and Math Notes

This page documents the algorithms implemented in sampling_playground. The implementation is designed for visualization and pedagogy: the “step-by-step” mode exposes the proposal and the accept/reject logic.

Targets

The playground supports two types of targets.

Uniform on a drawn set $X \subset \mathbb{R}^2$: $$\pi(x) \propto \mathbf{1}_{\{x\in X\}}.$$
Continuous targets with density $\pi(x) \propto \exp(-f(x))$ (Gaussian, mixtures, banana, donut, funnel).

Shared parameterization

The UI uses a single “scale” parameter $\sigma$ (proposal standard deviation in world coordinates). For Langevin-type steps, we set $$\eta \;:=\; \tfrac{1}{2}\sigma^2,\qquad \sqrt{2\eta}=\sigma.$$ This matches the Euler–Maruyama discretization of overdamped Langevin dynamics.

ULA (Unadjusted Langevin Algorithm)

For $\pi(x) \propto e^{-f(x)}$, ULA is the “noisy gradient descent” update

$$x_{k+1} = x_k - \eta\,\nabla f(x_k) + \sqrt{2\eta}\,z_k,\qquad z_k\sim\mathcal{N}(0,I).$$

ULA is a first-order discretization and is generally biased at finite step size; there is no accept/reject correction.

MRW (Metropolized Random Walk / Random-Walk Metropolis)

MRW uses a Gaussian random-walk proposal and a Metropolis–Hastings correction:

$$y = x + \sigma z,\quad z\sim\mathcal{N}(0,I),\qquad \alpha(x,y)=\min\left\{1,\frac{\pi(y)}{\pi(x)}\right\}.$$

The proposal is symmetric ($q(x,y)=q(y,x)$), so the acceptance ratio only involves the target. For uniform targets, this reduces to “accept iff $y\in X$”.

MALA (Metropolis-Adjusted Langevin Algorithm)

MALA uses the ULA proposal, then performs a Metropolis–Hastings correction. The proposal is

$$y = x - \eta\,\nabla f(x) + \sqrt{2\eta}\,z,\qquad z\sim\mathcal{N}(0,I),$$

with Gaussian transition density

$$q(x,y) \propto \exp\!\left(-\frac{\|y-(x-\eta\nabla f(x))\|^2}{4\eta}\right).$$

The Metropolis–Hastings acceptance probability is

$$\alpha(x,y) = \min\left\{1,\frac{\pi(y)\,q(y,x)}{\pi(x)\,q(x,y)}\right\}.$$

Proximal Sampler and In-and-Out

The proximal sampler can be viewed as the composition of a forward Gaussian channel and a reverse Gaussian (restricted) channel. With parameter $\eta>0$, the conceptual step is:

Forward: sample $Y\mid X\sim\mathcal{N}(X,\eta I)$.
Reverse / proximal: sample $X'\mid Y$ from $$\tilde\pi_Y(x) \propto \exp\!\left(-f(x) - \frac{\|x-Y\|^2}{2\eta}\right).$$
Update: set $X\leftarrow X'$.

In the implementation, the reverse step is sampled via a rejection sampler (a standard implementation approach for strongly log-concave/log-smooth targets).

Reverse-step implementation options (RGO)

The “reverse” step $X'\mid Y\sim ilde\pi_Y$ is the only computationally nontrivial component. In general dimensions this is an inner sampling problem, and different implementations trade off correctness, speed, and required oracles.

Exact log-concave rejection sampler (this playground’s default for continuous targets): when $f$ is $eta$-smooth and $\eta<1/eta$, the regularized potential $ ilde f_Y$ is strongly convex and smooth. One can sample $ ilde\pi_Y$ by proposing from a Gaussian centered at the minimizer $x^*=rg\min_x ilde f_Y(x)$ and accepting with an analytically derived bound. In 2D, the playground computes $x^*$ numerically (damped Newton, warm-started per particle) and then runs the rejection step.
Inner MCMC (approximate): run a few steps of ULA/MALA targeting $ ilde\pi_Y$. This can be much faster per outer iteration, but introduces additional bias unless the inner chain is run sufficiently long. (Not enabled by default.)
Uniform targets (In-and-Out): for $\pi\propto\mathbf{1}_{\{x\in X\}}$, the reverse step is an exact restricted Gaussian on $X$ and can be implemented by membership-rejection. More sophisticated implementations use projection/separation oracles to make this efficient in higher dimensions.

For the uniform target $\pi\propto\mathbf{1}_{\{x\in X\}}$, the reverse distribution becomes a restricted Gaussian on $X$:

$$X'\mid Y \sim \mathcal{N}(Y,\eta I)\;\text{restricted to }X,$$

and the resulting two-stage walk (out of $X$, then back into $X$) is the In-and-Out algorithm.

References

MRW and MALA: Dwivedi, Chen, Wainwright, Yu. “Log-concave sampling: Metropolis–Hastings algorithms are fast.” arXiv:1801.02309.
Proximal Sampler: Wibisono. “Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality.” arXiv:2502.05623.
In-and-Out (uniform targets): Kook, Vempala, Zhang. “Algorithmic Diffusion for Sampling Convex Bodies.” arXiv:2405.01425.

Note: the UI uses a finite viewing window for visualization. For rigorous sampling, the algorithms are defined on $\mathbb{R}^d$ (or on $X$ for uniform targets).