Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proposes a novel MCMC kernel which consists of a "local" move $\mathsf{R}$ (e.g. a Metropolis-adjusted Langevin update) followed by a "global" i-SIR update. The latter is an MCMC kernel which proposes multiple particles from a distribution $\lambda$ which does not depend on the current state of the Markov chain and then potentially accepts one of these as the new state. The authors prove that the algorithm is geometrically ergodic.

The authors also consider adapting the proposal distribution $\lambda$ to the target distribution by specifying it through a normalising flow and taking gradient steps to minimise a suitable convex combination of forward and backward KL divergence at each iteration. Under additional assumptions, they show that the amount of adaptation converges to zero, i.e. adapting the proposal does not "break" the algorithm.
strengths_and_weaknesses: Strengths:

1. Extensive theoretical guarantees including for the adaptive case (although I didn't not check the proofs in the appendix). To my knowledge, these are novel.

2. The presentation is very clear.

3. The proposed algorithm is demonstrated to be competitive in low to moderate dimensions.

Weaknesses:

1. The proposed algorithm itself is not the most original since it is simply a composition of two well-known MCMC kernels.

2. I appreciate that the page limit is very tight but it would be useful to have more explanation of the constants that appear in Theorem 2 in the main manuscript. For instance, in Theorem 2, does the analysis demonstrate that the convergence rate is provably better for the proposed algorithm than for just the rejuvenation kernel alone?

3. In the "multimodal distributions" example in Section 5.1, I think it needs to be stressed that the proposed method would likely not work well for larger dimensions $d$ (the example uses $d = 2$). The way the example is presented might give some non-experts the idea that the proposed algorithm can overcome the problem targetting a distribution with well-separated modes in higher dimensions which is not the case. Of course, in fairness, I don't know of any other method that would work in such a scenario.


Some typos:

- l.117: missing space after "strategy"
- l.213: work -> works
- l.213: alternates -> alternate
- l.218: author -> authors
- l.248: stalls -> stall
- l.257: "remind"
- l.257: define the "$[x;y]$" notation
- l.272: outperforms -> outperform
- Bibliography: there are missing details/inconsistent use of journal name abbreviations/missing capitalisation of proper nouns in a number of entries
- Theorem 2: Equation 13 is referenced here but can only be found in the appendix
questions: I'm curious why this has been submitted here rather than to a computational statistics journal where the theoretical guarantees may find more appreciation (and where reviewers have more time to review these).

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose to combine a global MCMC kernel with a local MCMC kernel to achieve exploration and exploitation. Specifically, they use iterate sampling importance resampling proposed in [H. Tjelmeland, 2004] as the global kernel and MALA as the local kernel. To further improve the proposal distribution in the global kernel, the authors apply normalizing flow to learn a proposal that is close to the target distribution. The authors prove the V -uniform geometric ergodicity of the proposed method. Empirical results on synthetic distributions, and the latent space of Generative adversarial networks demonstrate the effectiveness. 


strengths_and_weaknesses: Strengths

- The motivation is clear and the paper is easy to follow.

- As far as I understand, the proposed method is technically sound.

- The authors provide both theoretical and empirical analysis to the proposed method.

Weaknesses

- It is unclear whether the methodology significantly differs from previous local-global MCMC work. Thus, the originality is unclear.

- The empirical results do not include previous local-global MCMC methods as baselines, so it is unclear whether the empirical improvement is significant. 

My main concern is the originality and significance. To me, the proposed method is very similar to [1] and the authors did not compare it with [1] in the experiments. If the authors can show significant differences and improvements of the proposed method over the previous work in the rebuttal, I'm happy to increase the score.

[1] Adaptive Monte Carlo augmented with normalizing flows
questions: In Figure 1, how does local MCMC (which is MALA on this task) perform? On a standard Gaussian, I guess MALA should perform well. It might be more convincing to show a case, such as the multimodal distribution in Section 5.1, where Ex2MCMC is better than purely i-SIR and purely MALA. 

Theorem 2 provides the mixing rate of the proposed Ex2MCMC. Could the authors compare it with the mixing rate of i-SIR and MALA? Under which conditions, Ex2MCMC is faster? I do not find a discussion on it in the current form.

It might be clearer to summarize the adaptive Ex2MCMC in an algorithm box, then we can see what are the differences between Ex2MCMC and adaptive Ex2MCMC by comparing it with Algorithm 2.

The related work section is a bit vague. It is unclear to me how the proposed method differs from previous work and what are the pros and cons. For example, [1] also combines local and global MCMC kernels and the global kernel is also learned by a normalizing flow. Is the difference only in the global sampler where [1] uses independent MH and the proposed method uses i-SIR? In the second paragraph, the authors simply claimed, “another line of work exploits both normalizing flows and common local MCMC kernels for sampling, yet in a different way” without explaining in what different way. 

In the experiments, I think it is necessary to include previous local-global methods, such as [1], as baselines. The empirical results look reasonable to me. It is expected that combining local and global moves improves the sampling results on multimodal distributions. 


limitations: There is no related discussion on limitations in the paper.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper addresses MCMC sampling from unnormalized probability distributions. The main idea here is to combine sampling importance resampling using a global proposal with an interleaved local update -- a local MCMC transition kernel (such as MALA or HMC) with a metropolis correction. The authors argue that this simple approach effectively combines the best of both worlds -- faster mixing between modes (from the global proposal) and better local exploitation of modes (from the local kernel). The authors provide theory and empirical results which back up this claim. A key theoretical result is that the proposed method is geometrically ergodic even if the importance weights are unbounded (assuming properties of the local kernel which hold for most sensible choices). This is in contrast to i-SIR which requires bounded importance weights. Thus the approach retains the nice mixing properties of i-SIR while inheriting some convergences guarantees from the local methods. 

The authors also propose an adaptive variant of the method where the global proposal is a normalizing flow which is tuned online using the outputs of the sampler. Modifying the proposal online can break ergodicity but the authors present sufficient conditions to guarantee it (basically just ensure that the flow converges).

The authors present some nice toy results to help visualize the performance of the approach compared to some obvious baselines (pure-global and pure-local MCMC). They then present results on some standard benchmark distributions of increasing dimension and show that their method outperforms most baselines except for NUTs (only outperformed in high dimensions). They then sample from high-dimensional EBM-GANs and show similar improvements. 

strengths_and_weaknesses: Strengths:

I enjoyed reading this work. This method is very simple (a good thing!) and once you hear it, it makes perfect sense. Its always great to see simple, intuitive ideas that appear to perform well. In my experience, it is methods like these that end up having the most impact (which is what we should all be trying to achieve). While the method is relatively simple, it is not obvious where and when it should outperform related methods. The theory shown here definitely makes that clear and does so in a way that is easily understandable and not over-cluttered with unnecessary math that would obfuscate the presentation of the method and the results. 

The results are presented nicely. I like the progression from toy visualizations, to challenging standard benchmarks, to real-world deep learning models. I am convinced that the approach scales to high-dimensional problems and still performs well.

Weaknesses: 

I do not have too many large critiques for the work but I do have a few questions (which will be expanded on in the next section). 

I do feel there is some related work that has not been addressed (not my work I swear!). There has been a fair bit of work in the EBM space using a mix of local MCMC and global proposals ([3] is a good starting point but this family of methods has been explored quite thoroughly). Most of this has been focused on improving MCMC used to train energy-based models. To my knowledge, these methods have not been given the same theoretical treatment presented here, so it might be nice to compare these methods to your work and discuss where your theory could (or could not) be applied.

I feel the experimental results in the image generation section could be improved. I know it can be difficult to come up with quantitative measures of sampler performance for image data but some decent proxies do exist. I am not super-convinced by looking at energy values alone. Some measure which could compare likelihood and entropy would be nice. While not a perfect metric, FID could be used on the CIFAR experiments to give a solid proxy for this. Another idea would be to use a tractable model as a target. For example, you could train a normalizing flow on MNIST or CIFAR and sample from the flow, treating it as unnormalized. Then you could compare likelihood histograms between the MCMC samples and actual samples from the model. This has been done in other work dealing with unnormalized models [1, 2].

Like I said, I enjoyed this work, but some further large-scale experiments like this would greatly improve its experimental section. 

[1] https://arxiv.org/pdf/1905.07088.pdf
[2] https://arxiv.org/abs/2010.04230.pdf
[3] http://www.stat.ucla.edu/~ywu/CoopNets/doc/CoopNets_AAAI.pdf
questions: Most of my questions relate to the adaptive variant of the method. First, I am curious how important it is to train using the mixture of forward and reverse kl. Do we need both? I know you note (correctly) that reverse kl can suffer from mode-dropping, but it can also be made to work in many scenarios if done carefully. It would be great to have some sort of ablation on this? Maybe compare reverse only, forward only, and the mixture. I would not be surprised if the mixture performs better but it would be useful to back up the choice used here.

Next, I am curious how important the initialization of the proposal distribution is to the performance of the method. In my experience, reverse kl can be made to work if the proposal is initialized properly. Does the mixture save us from that? It might also be nice to see how the approach performs when we use a good init (distribution with the right scale) to a bad init (distribution with scale too small or too large). It would also be nice to discuss a practical initialization procedure such as: start with a wide proposal, run K steps of HMC and take the mean/std of the resulting samples and use that to parameterize the initial proposal. It would be very cool to see if the method is relatively robust to these choices. 
limitations: I feel the limitations of the method are clear from reading the work. There is no specific limitations section (might be nice to add), but I do not think it is absolutely necessary.
review_title: null

Meta-review: metareview: Three domain experts recommended acceptance for this paper. One reviewer in particular made a confident and strong recommendation. I find all three convincing.

Reviewers agree that the paper is clear (both in presenting the motivation and the argument), and that the contribution to theory is substantial (proving desirable mixing properties and convergence guarantees, and developing an adaptive variant of the algorithm). Reviewers also agree on the whole that the empirical section adequately supports the paper's main point, even though (as Reviewer PqJ7 mentioned) larger-scale simulations would strengthen it further.

There were some questions raised early on about related work. Reviewer PqJ7 pointed out specific related lines of work worth discussing in the paper, and a thread with Reviewer 9sXT drew some comparisons to another paper that combines local and global MCMC kernels. In both cases, concerns seemed adequately addressed during the discussion that ensued, and were covered in the draft update. Reviewer PqJ7 initially suggested computing additional metrics (namely FID) as part of the experiments and the reviewers did this too (adding an IS calculation as well).

Discussion was productive – a case where the course of review strengthened the paper slightly further. Thanks to the reviewers for being thorough and responsive and to the authors for incorporating their feedback well. Altogether this is a nice and well-presented result.
confidence: Certain
Decision: Accept