Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper built on top of the work "Informed proposals for local MCMC in discrete spaces" Giacomo Zanella. Author propose to learn the balancing function by optimising mutual information objective between $KL[p(x)T(x'|x) | p(x)p(x')]$.
main_review: Minor comments

L 63 Formal definition of $N(x)$ is missed, I used from  Zanella.
L 71 It is not clear why only acceptance rate important 
L 101 In proposition 1 maybe it will be interesting to discuss mixture of balancing functions vs. mixture of transitional kernels with corresponding balancing functions.

General

In Proposition 2 general form of balancing function $\min \left[h(t), t h( \frac{1}{t} )\right]$ was proposed in Zanella. So, contribution in parametrization h with DNN, which is also interesting. Then the crucial question, in my opinion, is the selection of the optimization criterion. This however discussed very briefly in 3.2 In L 144 motivation is not clear "Note that the ideal case would be to sample from $p$ independently", given the fixed neighbourhood of $N(x)$ (see also arXiv 1810.07151, arXiv 1711.09268 as examples of discussion about loss for transition kernel learning). Moreover, given the fixed neighbourhood of $N(x)$, I don't understand L 158 $T(x'|x) = p(x')$. ?!
Despite that I can guess the overall reason for the objective: the balancing function should incorporate global information about the target density. I suppose the choice of the loss should be discussed more. 

The next paper is discussed universally optimal balancing functions. First, I don't understand (and paper don't provide) any intuition of existing such thing. For continuous support, such function does not exist, what is different in discrete cases? Assuming that it exists, I also don't understand the selected functions to compare: I can provide infinitely many such functions in terms of hyperbolic functions. Maybe I miss the point.

limitations_and_societal_impact: No limitations to discuss.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper improves upon a recently proposed MCMC method ([Zanella. JASA 2020], cited as [28] in the paper) and considers optimizing the choice of balancing function in that method. A collection of rigorous techniques are proposed so that the balancing function can be represented by a neural network, and the network is trained by minimizing a heuristic objective (two possibilities are provided), which seems to be an approximation of the KL divergence from a Metropolis-Hasting proposal to the target distribution. Limited empirical evidence of effectiveness is provided.
main_review: The method is new and interesting. I especially like results in Section 3.1, which are smart and innovative. Overall, I feel the idea has a lot of potential and deserves a better demonstration, both theoretically and experimentally. More precisely, if I understood correctly, the goal is to accelerate the convergence of Metropolis-Hasting-type MCMC algorithms. Ideally, some theoretical analysis should be provided to quantitative establish an improved convergence speed, which is not the same as showing detailed balance (which is rather standard for Metropolis-Hasting) or ergodicity (which is not quantitative and not hard for finite state space Markov chains). However, I understand that this kind of analysis is typically highly nontrivial, and therefore empirical demonstration is also a possibility. In this case, some convincing numerical experiments with comparison to SOTA methods should be designed and provided. Such comparisons are currently missing, except one that compares against [28], which this work aims at improving. How much improvement over [28] was obtained was not very clear either; for example, I wonder whether Table 2,3 imply significant improvement or marginal ones. At the same time, can effective sample size be used to illustrate (improved) speed of convergence? I also don’t understand what `achieving fast convergence while preserving fast mixing’ means in Section 5.2, as one way to quantify convergence speed is through mixing time. More evidence of improved convergence speed will significantly strengthen the paper and illustrate the advantages of the new idea.

Some additional comments are:

Not all MCMC methods are based on proposals. Perhaps the authors were thinking about Metropolis-Hasting, which is just one class (albeit very important) of MCMC methods. Other classes include, for example, Gibbs sampler, (unadjusted-)LMC, etc. Not all references cited in the section of Related Work, however, seem to be Metropolis-Hasting based approaches.

Do "continuous domain" and "discrete domain" mean continuous state-space and discrete state-space? It has been repeated that less effort has been devoted to the discrete counterpart (of MCMC), but in general finite state-space Markov processes (chains) are easier than the infinite ones (for example, if a finite chain is ergodic then it must be geometrically ergodic, but this is not true for continuous state space). It will be great if more clarification can be provided on what makes sampling from a finite set a challenging problem and why tools developed for general state-space are insufficient/inefficient.

Is an indicator function $1[x’\neq x]$ missing in front of the first term on the right hand side of equation(1)?

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper address the problem of sampling in discrete spaces by learning proposal distributions that could potentially lead to faster convergence. The paper primarily builds on the original idea by G.Zanella, 2020 where the idea of locally balanced proposals was first proposed. The authors in this work aim to learn these proposals for "better" sampling in discrete spaces. 
main_review: **Positives:** The paper is well written and easy to follow. Sampling in discrete spaces is a challenging problem and the paper proposed a nice solution to learn proposal distributions for this. As discussed in the paper, the idea address to a large extent the limitations of previous works of Afshar and Domke, 2015, Pakman and Paninski 2013, Nishimura et.al 2020 etc. 

**Limitations and Questions:** 

1) **Prior work:** The authors missed two recent work on sampling in discrete spaces that also learn proposal distributions namely "Sampling in Combinatorial Spaces using SurVAE Flow Augmented MCMC" by Jaini et.al 2021 where the authors use normalizing flows to learn a transformation to transform the discrete distribution to a "easy to sample" continuous distribution. This is in-line with the other work on sampling in discrete spaces by using continuous relaxations but the paper also address the drawbacks of the previous works as mentioned by the authors and "Oops I Took A Gradient: Scalable Sampling for Discrete Distributions" by Gratwohl et.al 2021 where the authors also use the idea of locally balanced proposals for scalable sampling in discrete spaces. I believe at the very least these papers need to discussed as they are directly relevant to the problem and solution the authors propose. Finally, the idea of learning proposal distributions (atleast in continuous spaces) has been explored in a lot of detail by [Marzouk and Spantini] and [Hoffman et.al 2019, Neutralizing bad geometry in HMC using Neural transport] which I believe is also relevant to this work and warrants a discussion.

2) **Use of Universal Approximation to build locally balanced proposals:** The authors appeal to the universal approximation result to construct the family of proposals named LSB 2. While, theoretically, this affords advantages to the LSB 2 sampler,  the approximation results necessarily requires an infinite capacity network for such guarantees.  In practice, since finite capacity networks are used for function approximation (and thus the resultant locally balanced proposals) this would incur some error since the approximation will never be exact. I wonder if the sampler suffers due to this error and if the resultant proposal is still locally balanced. Put another way, since h_{\theta} is of limited capacity in practice, it approximated a locally balanced proposal function g within some error epsilon. Does this error break the properties of locally-balanced proposals and does all the theoretical advantages still hold? What are the implications of this error on the sampler (eq 2. in particular).

3) **Experiments:** I believe the paper will benefit greatly from a more detailed experimental evaluation that involves comparisons to other methods. Specifically, I believe that apart from the present experiments where the comparison is mostly made wrt other locally balanced proposals, the authors should also compare to other samplers including discrete MCMC (random-walk), Gibbs sampling, discrete HMC (Nishimura et.al, code is available publicly), SurVAE+MH (Jaini et.al, code is public), and Gratwohl et.al (code is public) to back up claims of faster convergence and better performance. I also think that it will be interesting to see how this idea of learning locally balanced proposals work in higher dimensional problems eg. Ising model for denoising MNIST, or quantized bayesian neural nets.  
limitations_and_societal_impact: Yes, the societal impact is adequately discussed.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This work proposed a strategy to learn locally informed proposals for MCMC in discrete spaces. In spirit, it is more or less similar to the multiple-try Metropolis method proposed in Liu et al. (2001), and it is unclear whether the new method is more efficient than the multiple-try Metropolis method. 

Liu, J. S., Liang, F. and Wong, W. H. (2000). The multiple-try method and local optimization in Metropolis sampling, Journal of the American Statistical Association, 95(449): 121–134. 
main_review: This work presents a new parametrization for learning locally balanced proposals, and it is basically can be viewed as  a supplementary material of the recent work Zanella (2020). 

] G. Zanella. Informed Proposals for Local MCMC in Discrete Spaces.  Journal of the American Statistical Association, 115(530):852–865, 2020.
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose a method to adapt the MCMC proposal to the discrete distribution of interest. The parametric proposal is constructed to be locally balanced, and the parameters are learned by maximizing a mutual information-based objective.
main_review: The paper is well-written and I did not have problems following the exposition.

The main idea of the paper is largely based on previous work by Zanella [1] on locally-balanced proposals for MCMC on discrete distributions. Rather than hardcoding such a proposal, the authors propose learning a parametric form either as a linear combination of known proposals or as a (monotonic) neural network. The setup of the optimization problem in eq. (3) to learn these parametric proposal could have been better motivated in the paper. More importantly, the transition from eq. (3) to eq. (6), which is the actual objective optimized, seems rather heuristic and not fully explained. Is there an intuitive reason why it may not be a problem to completely discard the expectation over $p$ in eq. (3)?

The experiments on some small-scale Ising models and on UAI Bayes nets show that the proposed methods seems to be comparable or faster in terms of burn-in and mixing. However, the authors do not show plots comparing the actual (wall-clock) time of the different sampling methods. The original paper by Zanella [1] already comments on the fact that locally-balanced proposals incur computational overhead (e.g., in comparison to a M-H sampler), and I assume that the steps in algorithm 1 for computing and optimizing the objective $J$ increase this overhead. As a result, it is hard to judge whether the proposed method is actually superior in practice.

Furthermore, at least for the Ising model simulations, the authors could compare to a recently proposed method by Grathwolh et al. [2], which use gradient-based local information in the proposal.

Other comments:
* The plots in Fig. 2, 3, and 5 are too small and hard to read.
* It is not explained what exactly the summary statistics are in the plots that evaluate the burn-in.

&nbsp;
### References

[1] Zanella. Informed proposals for local MCMC in discrete spaces. J. Am. Stat. Assoc. '20.\
[2] Grathwohl et al. Oops I Took A Gradient: Scalable Sampling for Discrete Distributions. ICML '21.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper considers the learning to accelerate the MCMC sampling. Specifically, the authors proposed a learning objective, which is minimizing the dependence between consecutive samples, for learning the proposal. Meanwhile, the authors discussed the parametrization of the balancing function. The authors evaluated the proposed algorithms empirically on 2D Ising model and Bayesian networks. 

All the reviewers think the paper is interesting and promising. However, there are still several concerns:

- The paper is largely relying on [Zenella, 2020], and shared some similarity with the related work as Reviewer PwEa, 2Vii mentioned [1, 2, 3]. The significance of the paper is not clear for current version.

- The choice of the loss should be discussed more as Reviewer PwEa and j21t raised.

- The empirical experiments is not comprehensive (Reviewer j21t) and experimental analysis around the method is lacking (Reviewer 2Vii). 

In sum, the paper indeed is proposing some interesting method, however, the current version is not ready to be published. I encourage the authors can take the suggestion from the reviewers into account to improve the draft and submit to next venue.

[1] "Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration" by Dai et. al 2020

[2] "Oops I Took A Gradient: Scalable Sampling for Discrete Distributions" by Gratwohl et.al 2021

[3] "Sampling in Combinatorial Spaces using SurVAE Flow Augmented MCMC" by Jaini et.al 2021
Decision: Reject