In this paper we propose to view the acceptance rate of the Metropolis-Hastings algorithm as a universal objective for learning to sample from target distribution -given either as a set of samples or in the form of unnormalized density. This point of view unifies the goals of such approaches as Markov Chain Monte Carlo (MCMC), Generative Adversarial Networks (GANs), variational inference. To reveal the connection we derive the lower bound on the acceptance rate and treat it as the objective for learning explicit and implicit samplers. The form of the lower bound allows for doubly stochastic gradient optimization in case the target distribution factorizes (i.e. over data points). We empirically validate our approach on Bayesian inference for neural networks and generative models for images.
One of the main contributions of the paper is showing how maximizing the acceptance rate in Metropolis Hastings (MH) translates in minimizing the symmetric KL divergence of the target and the proposal distribution. The result aligns with the intuition that if this variance is 0, detailed balanced is satisfied and, hence, we can always accept the proposal. Also Equation 11 nicely fits the intuition that a good (independent) proposal should minimize the KL divergence between proposal and target (as in VI) under the constraint that the proposal has full support compared to the target distribution, which is enforced by the last term. Theorem 1 and its proof are great.
However, the proposed algorithms leveraging these findings are problematic. Algorithm 1 suggest independent Metropolis-Hastings in order to avoid the proposal to collapse to a point distribution, that is, a Dirac delta function centered at the current position. However, in the experiments, the authors study a "modified" version using a random walk proposal parameterized with the current (diagonal) covariance estimate. This is surprising as the authors explicitly avoided this proposal when motivating MH acceptance rate maximization.
In any case, the correctness of the algorithm is neither shown for an independent proposal nor a Markov Chain proposal. Indeed, I would argue that Algorithm 1 generally does not find a sample distributed according to the target distribution. The algorithm assumes that we can create a sample from the target p(x) that can be used to approximate the loss (a bound on the expected acceptance rate). However, if we could find an unbiased sample in the very first iteration of the algorithm, we could immediately stop and there wouldn't be a need for the algorithm at all. Hence, we must assume that the sample drawn from the target is biased (in the beginning); which is indeed a realistic assumption as neither independent MH nor random walk MH will yield an unbiased sample in any reasonable time (for any practical problem). However, this would bias the loss and, consequently, the parameter update for the proposal distribution. In particular, for random walk MH, I would expect the covariance to contract such that the final proposal indeed collapses to a point distribution. This is because the proposal is only required to have support around the observed samples and this area will become smaller over time. I would expect a proof that the sample at iteration k is "better" than a sample drawn at iteration k-1, to show that the bias vanishes over time. Though, I assume that this is hard to show as the proposal parameters form a Markov Chain itself. So at least a rigor empirical study is needed.
Therefore, I would expect a metric measuring the quality of the final sample. The log-likelihood is not such a measure. While the marginalized log-likelihood could measure the quality of the sample, we cannot compute it for any real data/model (which is why we use sampling in the first place). So we need some artificial settings. However, the 1-dimensional toy example is insufficient as MH primarily suffers in high-dimensional spaces. It would be interesting to also report the acceptance rate depending on the number of dimensions of the target distribution. I would assume an exponential decay; even with learning, which might be the reason why the authors only report random walk MH in Section 4.2.
Algorithm 2 does not require to sample from some target distribution but can leverage the observed sample. While the algorithm nicely connects GANs and sampling, the actual value of the algorithm is not fully clear to me. Learning an independent proposal reduces the problem to learning a GAN; and learning a Markov Chain seems only relevant for sampling-based inference; however, we already have a sample from the target distribution, and we can sample more data using a trained GAN.
Minor comments:
- The prefix/in-fix notation of integrals is mixed, e.g. in Eq 19, "dx" appears before the integrand, but "du" appears after the integrand of the inner integral.
UPDATE:
The revised version is much better in empirically demonstrating the value of the method; though, there is still some work needed. First, the artificial examples are still rather low-dimensional where independent MH is expected to perform well. Second, ESS does not help to assess the biasedness of the sample; maybe [1] can help with this. Third, NUTS might be a better baseline than standard HMC which is know to be sensitive to the stepsize/number of leapfrog steps. An effective sample size of 1 suggests that the method did not even start to sample - likely because of a bad choice of the stepsize and/or mass matrix. I would suggest using PyMC3's NUTS implementation. Finally, to show the correctness of the method, I would suggest to 1) let alpha converge to zero such that \phi will be fixed at some point, and 2) ensure that the proposal has full support under the target for any value of \phi. In this case, the sample drawn from the target will be unbiased for large enough n (same arguments as for adaptive MCMC should apply).
The idea of reusing the samples from previous iterations for approximating the loss is interesting and worth exploring.
[1] Jackson Gorham, Lester Mackey. "Measuring Sample Quality with Kernels", https://arxiv.org/abs/1703.01717