# State-of-the-art sampling methods for different information about target density

I was wondering what are the current state-of-the-art methods (i.e., your favourite methods, if you are an expert) for Monte Carlo sampling from a target density function $f(x)$ with $x \in \mathbb{R}^d$, $d > 1$, given different amount of accessible knowledge about $f$.

If you already know a lot about $f$, or you spend a lot of time to get to know the details of $f$, you could do pretty clever stuff; but this is not often the case. I am curious to know what would be your general strategy and your first out-of-the-box method to attack the problem in the following cases.

Basic assumptions: For simplicity, in the following I will assume that most of the probability mass of $f(x)$, $x \in \mathbb{R}^d$, belongs to a single connected component ("mode jumping" for disconnected modes is a topic in itself). This connected component does not necessarily have a simple shape (e.g., multivariate normal), and it is not necessarily "unimodal" in the analytical sense. Also, let us focus on the low- to medium- dimensional case ($2 \le d \le 20$).

Specifically, let us consider the following scenarios:

1. When for $f(x)$ you only have an unnormalized black-box. That is, you can only evaluate $f$ exactly at a given point $x$, and up to a normalization constant. You may have some vague information about the meaning of $x$.
2. As (1) but also with gradient information.
3. As (1) but the normalization constant is known (does it allow to do better?).
4. As (1) but we know that $f(x)$ has compact support within a known region $\mathcal{U} \subset \mathbb{R}^d$.
5. As any above and we know that $\log f(x) = \sum_{i = 1}^n \log f_i(x)$, and we can evaluate the various $f_i$ separately.
6. As (1) but we can only get a noisy (unbiased) estimate of $f(x)$ itself.
7. As (6) but with an unbiased estimate of $\log f(x)$.
8. [new] As (1) (or any other above) and you know that $f$ is actually unimodal (or some other specific property about the shape of $f$).

I think that gathering answers to these questions in a single thread might be very useful as a general guide for the community, for people who use sampling methods in their work (or might want to start to), and perhaps do not know the whole array of existing methods.

I'll post below what would be my answers, to give an idea. Also, please feel free to expand with other scenarios about possible kinds of prior knowledge on $f(x)$ that I did not explicitly consider but that you think are particularly important.

• For me the expected shape of the target would be a key decision criterion. Differences between samplers may not be huge for multi-normal targets, but they can be substantial for bi-modal or other complicated targets. Should the shape somehow be included in the question? Another issue is the dimensionality of the problem - the difference samples scale differently with # parameters. – Florian Hartig Feb 17 '16 at 17:04
• (+1) Good point, included some extra comments. Please feel free to expand on this. – lacerbi Feb 17 '16 at 17:30

(I am the OP.)

For example, my answers would be:

1. Slice sampling as per Neal (2003). It requires very little tuning; you only need to very vaguely know the length scales of your problem (and you can get those wrong with little harm, as long as you err on the larger side).
2. Some type of Hamiltonian Monte Carlo. I would probably first try no-U-Turn Sampling by Homan and Gelman (2014). This is an active area of research with many interesting proposals (e.g., Riemannian Monte Carlo by Girolami and Calderhead (2011)) but I am not in the field and don't know what would be the established state-of-the-art.
3. I don't know if knowledge of the normalization constant would allow for a more powerful method (e.g., would it allow to be smarter in how you slice your distribution?).
4. Same as above.
5. Don't know either, but I have the intuition that you should be able to gain something by knowing the factorization of $f$ (perhaps with additional assumptions on how the $f_i$ are related). My gut feeling is based on the fact that, for example, WAIC is more powerful than DIC exactly because it does not take $f(x)$ as a black-box but computes the contribution of each data point separately.
6. Interestingly, Metropolis-Hastings still works if you have a noisy but unbiased estimate of $f(x)$ (although you'll have to fight a large increase in variance and worse mixing properties); see this post at Darren Wilkinson's blog for a good discussion. An accepted paper by Murray and Graham (2016) extends slice sampling to the case of a noisy, unbiased estimate of $f(x)$ via a relatively efficient pseudo-marginal method (I have not tried it yet).
7. I assume that you can perhaps attack it with something like (6) plus a convexity correction. Edit: I just found out a previous question on CrossValidated that addresses this issue.

References:

1. Neal, R. M. (2003). "Slice Sampling". Annals of Statistics 31 (3): 705–767.
2. Homan, M. D., & Gelman, A. (2014). "The no-U-turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo". The Journal of Machine Learning Research, 15(1), 1593-1623.
3. Girolami, M., & Calderhead, B. (2011). "Riemann manifold langevin and hamiltonian monte carlo methods". Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73(2), 123-214.
4. Murray, I., & Graham, M. M. (2016). "Pseudo-Marginal Slice Sampling" To appear in AISTATS 2016.