Particle-Based Optimization and Sampling

Optimization and sampling are quintessential tasks in applied mathematics, both of which arise naturally from solving inverse problems. In applications, Here is \(\mathcal{G}\) is expensive to evaluate (e.g., solving a PDE), and derivatives of $\mathcal{G}$ are unavailable.

These tasks arise from formulating the Bayesian inverse problem, where one wishes to recover a parameter $\theta \in \mathbb{R}^d$ from data $y \in \mathbb{R}^m$, with $\mathcal{G} : \mathbb{R}^d \to \mathbb{R}^m$ and $\eta \sim \mathcal{N}(0,\Gamma)$: \[y = \mathcal{G}(\theta) + \eta\] For a Gaussian prior $\mathbb{P}(\theta)=\mathcal{N}(\theta_0,\Sigma)$, the posterior $\mathbb{P}(\theta \mid y)$ can be written $$ \mathbb{P}(\theta \mid y) \propto \exp\left(-\tfrac12\,\lvert y-\mathcal{G}(\theta)\rvert_{\Gamma}^{2} - \tfrac12\,\lvert \theta-\theta_0\rvert_{\Sigma}^{2}\right) = \exp!\big(-\Phi(\theta)\big), $$ where $\lvert x\rvert_{A}^{2} := \langle x, A^{-1}x\rangle$.

Some natural questions are: 1) Optimization: Find the MAP estimate (the maximizer of $\mathbb{P}(\theta \mid y)$). 2) Uncertainty Quantification: Sample from the posterior $\mathbb{P}(\theta \mid y)$.

Interacting particle methods have become a popular alternative because they: (i) do not need gradient information ✓, (ii) allow for parallelization ✓, (iii) enjoy convergence guarantees through mean-field analysis* ✓

* under appropriate assumptions on the interaction and potential.