3
$\begingroup$

Suppose I define a probability distribution $\mu\in\mathrm{Prob}(\Sigma)$ over some compact $\Sigma\subseteq\mathbb{R}^n$ using a variational problem: $$ \mu:=\arg\min_{\mu\in\mathrm{Prob}(\Sigma)} F[\mu]. $$ Here, $F[\cdot]:\mathrm{Prob}(\mathbb{R}^n)\rightarrow[0,\infty)$ is an energy functional on the space of probability distributions. Feel free to put any reasonable regularity assumptions you want to on $F[\cdot]$.

Is there a way to sample approximately from $\mu$ without explicitly solving the variational problem?


For instance, consider the following inefficient and likely incorrect strategy:

  1. Randomly generate a sample of $k$ points $p_1,\ldots,p_k\in\Sigma$ uniformly from $\Sigma$
  2. Evaluate $f:=F[\sum_i \delta_{p_i}]$, where $\delta_x$ is a delta function centered at $x$.
  3. With probability "proportional to" $f$ (e.g. after repeating this process a few times to get an idea of how $F[\cdot]$ behaves), return a uniformly random sample from $\{p_1,\ldots,p_k\}$; otherwise return to step 1.

This algorithm obviously makes no sense, but hopefully you see what I'm after. I could imagine for some class of $F$'s (uniformly Lipschitz?) and large enough $k$, a strategy like this could get a reasonable approximation. Or maybe there's an MCMC interpretation?

$\endgroup$
  • $\begingroup$ This is a most interesting question! In the event $\Sigma$ is a finite set, you can always use some sort of simulated annealing algorithm to solve the optimisation problem but this is not answering the question. $\endgroup$ – Xi'an Mar 7 '17 at 6:01
  • $\begingroup$ Glad to hear it's interesting! I'm always nervous to ask something completely ill-posed... If you have any ideas or which to chat, please let me know --- I can think of quite a few applications of such an idea. $\endgroup$ – Justin Solomon Mar 7 '17 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.