Post date: May 6, 2011 9:24:20 PM
In early 2010, I came up with a very simple idea to approximate moments of a probability distribution when an exact computation is intractable. The method involves fitting a simplified distribution for which the integral has a closed-form expression, and using a set of randomly sampled control points to optimize the fit. Hence, I called this "variational sampling".
Previous methods from computational statistics, known as Bayesian Monte Carlo or Bayesian quadrature, implement the same basic idea but using a different objective function. Traditional importance sampling may also be viewed in this framework, but is not equivalent.
My first impression was that variational sampling was such a natural thing to do that it had to be known for ages. But I found no trace of it in the literature, which surprised me but could suggest that there was some serious flaw in the concept. So I implemented it to compare with some existing methods: importance sampling, Bayesian Monte Carlo, the Metropolis-Hastings algorithm, the Laplace approximation. My Python code is available at github.
From a number of simulations on toy examples, I observed that, in brief, variational sampling can massively outperform all these methods, meaning that it can reach the same accuracy with much smaller samples. And it is way much faster than Bayesian Monte Carlo. So far, I haven't tested it in large dimension because some engineering issues still need to be solved.
Meanwhile, I started studying the method mathematically, and realized a series of nice properties: the underlying variational problem is convex, with a very simple condition on the sample size for the existence and uniqueness of a minimizer. Moreover, we have a central limit theorem just like in the case of importance sampling. So we can actually prove that variational sampling is more accurate than importance sampling in many situations.
At that point, it appeared to me that variational sampling was both an incredibly simple idea, and a potential breakthrough in the art of statistical computing, so it has become one of my main research activities.
I have a working paper on the topic, which is still somewhat incomplete but describes the basic setting. I was invited to talk about variational sampling at the Humboldt-Kolleg workshop on mathematics, statistics and computer science for interpreting structure in May 2011 (see my slides).