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, \(\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(-\tfrac{1}{2}\lvert y-\mathcal{G}(\theta)\rvert_{\Gamma}^{2} - \tfrac{1}{2}\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.