Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: - Consider the task of MH-MCMC on a EBM defined over discrete state space.
- [GZ] proposed a Kernel which evaluates the energy function over a Hamming ball surrounding the current state and [GWG] improved the efficiency of the latter by using a Taylor series expansion of the energy function.
- The authors of the current paper improve the acceptance ratio (Eq 2) and mixing (Thm3) by sampling a multiple transitions (a path) instead of a single neighborhood sample.

[GZ] - Giacomo Zanella. Informed proposals for local mcmc in discrete spaces. Journal of the American Statistical Association, 115(530):852–865, 2020.

[GWG] - Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris J Maddison. Oops i took a gradient: Scalable sampling for discrete distributions. arXiv preprint arXiv:2102.04509, 2021.

main_review: 
## Weakness

1 - The primary weakness in the paper is that the proof of Theorem 1 is incorrect. Equation (17) can be split into two parts:

A - $\pi(x)\sum_{L} \alpha(L) \sum_{(\sigma,L) \in \Sigma(\mathcal{X}, \mathcal{N}) \colon \sigma_0 = x, \sigma_L = y} \Big[ \prod_{l=1}^L Q_0(\sigma_{l-1},\sigma_l)\Big]$

B - $\min{} \Big[1, \frac{\pi(y)\prod_{l=1}^L Q_0(\sigma_l, \sigma_{l-1})}{\pi(x)\prod_{l=1}^L Q_0(\sigma_{l-1}, \sigma_{l})}\Big]$

While part A marked above is acurate, part B should technically be  $\min{} \Big[      1, \frac{\pi(y)\prod_{l=1}^{L'} Q_0(\delta_l, \delta_{l-1})}{\pi(x)\prod_{l=1}^{L'} Q_0(\delta_{l-1}, \delta_{l})} \Big]$

where $L'$ and $\delta$ are the length samples and path samples drawn in the algorithm mentioned above Theorem 1.
As such Equation 17 doesn't imply Equation 18.

Despite this theoretical inconsistency, it is not surprising that the experimental section shows that the proposed method works better than [GWG]. 
This is because the method is a Pseudo Marginal MH procedure (where the acceptance probability is a Monte Carlo sample of the true acceptance probability like [Section 4.2, RB]).
If so presented, I would be inclined to accept the paper but in the current form, the paper is mathematically incorrect.

2 - The second listed contribution (linearization) is a rehash of [GWG] and is not novel.

3 - There are multiple grammatical errors in the paper examples include:
  - The first phrase of the abstract should've been `EBMs offer`
  - Second sentence, second para, page 3 should be `Instead of directly sampling from a large neghborhood path auxiliary sampler sequentially samples new states from a ...`.

4- Minor question: In the thrid paragraph, do you mean a simple random walk? If so what is the graph over which the RW takes place? Did you mean Gibbs sampling?

## Stregths

1 - The experimental section is very strong and the explanation in terms of the toy example is very intuitive.

[GWG] - Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris J Maddison. Oops i took a gradient: Scalable sampling for discrete distributions. arXiv preprint arXiv:2102.04509, 2021.
[RB] - On Markov chain Monte Carlo methods for tall data
R Bardenet, A Doucet, C Holmes - The Journal of Machine Learning Research, 2017 https://www.jmlr.org/papers/volume18/15-205/15-205.pdf

summary_of_the_review: 
The proof of the main theorem is incorrect and hence I am rejecting the paper.

--------------
I am updating my scores based on author discussion. Please refer to comments for details.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: MCMC in discrete spaces using locally informed proposals usually use small neighborhoods (e.g. changing only one component), for efficiency reasons. The paper proposes a method to efficiently explore bigger neighborhoods using locally informed proposals (with a locally balanced function) to sample "auxiliary paths". Additionally, following previous work, they propose an efficient version using a linear Taylor expansion, thus saving a significant number of likelihood evaluations.
main_review: Locally informed proposals and the use of locally balanced functions were proposed by Zanella (2020). The paper uses these ideas in a new way to efficiently explore large neighborhoods via auxiliary paths.

Strengths:
1. The method proposed is more efficient (in terms of likelihood evaluations) than naively expanding the neighborhood using a locally-informed proposal.
2. Using a balanced function the resulting acceptance rate takes a very simple form and can be computed efficiently.
3. Experiments include many models and several baselines (though I have some comments on the specifics).

Weaknesses:
1. I find section 3.3 a bit confusing. A few concrete comments: (a) Where does the definition of an "ideal" function come from? Theorem 2 states that, for every ideal function f, there is a locally balanced function g asymptotically better than f. Why does this mean asymptotic optimality for locally balanced functions? Am I missing something simple? (b) Is the conditional independence graph (thm 2) defined anywhere? Is it the DAG that defines the factorization of the distribution as in a directed graphical model?

2. The result from theorem 3 (about the use of the Taylor expansion) and its analysis seem problematic. Specifically the part that claims that the use of the approximation does not lead to a large detrimental effect. The theorem lower bounds the efficiency lost by using the approximation. But this lower bound decreases *exponentially* with K and with $U^2$, where U is the length of the path. If U=10 this bound says that using the Taylor approximation leads to a method whose efficiency is at least $T\times e^{-50}$, where $T$ is the efficiency of the method without the approximation. Claiming that the approximation does not lead to "losing too much proposal quality" does not seem justified. It could be the case that this bound is very lose, and thus not informative. Or it could be that there are models for which the inequality becomes an equality, and the use of the Taylor approximation becomes extremely problematic (would it be possible to find a simple model that satisfies this?). Do you have any comments on this? I am not claiming the approximation is necessarily bad, I'm just asking about this specific theoretical result and its relevance.

Finally, I have some comments on the empirical evaluation. First, I'd like to mention that I find the wide variety of models, tasks and baselines very nice. However, I think the section can be improved by showing more organized experiments addressing each component of the proposed method separately. Concretely:

E1. Section 3.2 shows that the method with a path of length L is more efficient than running LB-1 for L steps. It would be nice to have experiments that show the effect of this in practice. This could be done by comparing PAS-L and LB-1 on several models, in terms of likelihood evaluations, not MCMC steps (PAS-L uses L times as many likelihood evaluations per step). Figs 1 and 2 compare these methods in terms of MCMC steps on two simple models. I think the results in terms of likelihood evaluations would be similar. However, these models, while simple and illustrative, may be too tailored to make LB-1 fail. It would be great to see results for the Ising model, RBM, FHMM. 

E2. Effect of introducing the Taylor approximation. This could be seen by compare PAS-M vs PAFS-M for a bunch of models, for varying M, in terms of MCMC steps (not likelihood evaluations). While not a fair comparison, this reflects the effect the approximation has, and how much we are losing by using it. (In this setup, we can only expect that using the approximation will hurt performance. This would show how much.) For a practical comparison, results in terms of likelihood evaluations should be shown too (and are currently shown). Also, for the real models, PAS and PAFS are compared only for the Ising model, which the authors state is close to linear (and thus possibly favors the Taylor expansion approximation).

E3. Comparison of the final method with the Taylor approximation against other baselines (GWG-M, LB, Gibbs, etc) in terms of likelihood evaluations.


Additional comments:
- Should add labels (in x and y axis) in all plots (e.g. x-axis in Fig 4, is it likelihood evaluation? MCMC steps?).
- Plots in Fig. 3 would be nice to have in same scale for the y-axis.
- Is there a typo in equation 10? Should it be p instead of n in the summation?
summary_of_the_review: On the positive side, I think the paper provides a nice and natural extension of MCMC methods in discrete spaces based on locally informed proposals. 

On the negative side, I think that some of the theory could be presented more clearly, some of the claims revisited, and the empirical evaluation could be modified a bit to better show the benefits/drawbacks of each of the method's components.

-----

I updated my score after the authors' response.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides a generalisation of the work of pointwise informed proposals (Zanella 2020), where the acceptance criterion is applied after L sampling steps, instead of each single one.
This comes with the advantage that the overall acceptance criterion  is guaranteed to be larger than the corresponding one in (Zanella 2020). The authors also extend the results in (Zanella 2020), by proving under mild conditions that weighting functions based on balancing ones are asymptotically optimal as for sampling efficiency according to Peskun ordering. Lastly, they provide an algorithmic extension reducing the number of target likelihood evaluations by applying the approximation strategy proposed in (Grathwohl 2021). The analysis is corroborated by experiments on several energy based models both for inference and learning tasks, thus showing the superiority of the proposed algorithm and its extension over existing MCMC strategies.

main_review: **Contribution and Potential:**

The work tackles an important open problem for MCMC in discrete spaces, as it enables making large sampling steps while retaining the local benefits of pointwise informed proposals. This has important consequences, for instance when sampling from or training energy-based models. The result in Theorem 2 is to my knowledge a simple but non-trivial extension of the result in (Zanella 2020) and it’s significant in this context, as it provides an initial answer to the question “are balancing functions optimal on large neighborhoods?”. (Indeed, (Zanella 2020) focused on the case of L=1, while the authors consider the extended setting with L>=1.)

**Related Work**

Some recent work must be discussed. For instance, see (Dai 2020), (Jaini 2021) and (Sansone 2021).

**Questions:**

1. Theory. While certainly the result in Theorem 2 holds in the limit of infinite dimension. Is there a limit on the result of Theorem 2, or equivalently an upper bound on the value of L when the dimension of the space is finite? Indeed, as (Zanella 2020) points out, balancing proposals may not be optimal when considering global moves. Similarly, the constant in the Peskun ordering relation (in Theorem 2) should vanish when increasing L. Can the authors elaborate more on that?
2. Experiments. How is the maximum L determined and how can it be chosen in practice?
3. Experiments. How is the burn-in time chosen in all experiments?
4. Related Work. How does the proposed solution relate to existing recent work? 

**Minor:**

Page 2 should $\{0,1\}^p$ be replaced by $\{0,1\}^n$, in order to be consistent with what follows?

Page 7 Figure 10 -> Figure 3

Spacing between text and citations

**References**

(Zanella 2020) Informed Proposals for Local MCMC in Discrete Spaces

(Grathwohl 2021) Oops I Took a Gradient: Scalable Sampling for Discrete Distributions

(Dai 2020) Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration

(Jaini 2021) Sampling in Combinatorial Spaces using SurVAE Flow Augmented MCMC

(Sansone 2021) LSB: Local Self-Balancing MCMC in Discrete Spaces
summary_of_the_review: **Initial recommendation**

The paper is well written and technically sound. I went through the proofs and confirm their validity.
The paper represents an added value to the existing body of knowledge on MCMC, especially in the discrete domain. However, I have some questions for the authors, which might affect the final result. I initially recommend for a weak accept.

**Final recommendation**

The authors have addressed all concerns during the rebuttal. Therefore, I increase my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes an MCMC sampling algorithm for discrete distributions. The algorithm can be thought of as an extension of Locally-Balanced proposals from Zanella where the sampler proposes local moves changing one dimension of the input at a time proportional to the likelihood difference of the model in the current state versus each proposed modified state. The key difference here is the authors propose to sample from this proposal distribution multiple times before the accept/reject step. This is somewhat analogous to the difference between Langevin Dynamics and Hamiltonian Monte-Carlo. Ideally, by applying the proposal distribution multiple times before the accept/reject step, the sampler is more likely to escape local modes than the original Locally Balanced algorithm. 

The authors propose a fast variant of this algorithm which is an extension of the recently proposed Gibbs-With-Gradients sampler. This variant replaces the Locally Balanced proposal with the fast approximate version given by Gibbs-With-Gradients. This sampler approximately retains the benefits of the Locally Balanced proposal while being much faster to compute. 

The authors demonstrate the performance of their sampler at sampling from a number of common discrete distributions and at training discrete Energy-Based Models. They find their sampler performs favorably when compared with Locally Balanced proposals, and Gibbs-With-Gradients.  

--------------------- Post rebuttal period ------------------
I am very glad with the discussion that we've had and I thank the authors for responding to my critiques with new experiments and new results. I think they tell a more complete story of how the method relates to prior work. I believe we have cleared up many issues that other reviewers had with the work. I liked this work initially and I am glad now that other reviewers see it as I did. Having said that, I will keep my recommendation as it was initially. I would be very happy to see this work accepted. 

main_review: Strengths:

This paper presents a simple improvement over LB and GWG which alleviates the largest issue with these two samplers -- their inability to escape local energy wells. For LB/GWG to escape such a well we would need a long series of *accepted* transitions through low-likelihood regions, meaning we need the proposal to choose these unlikely transitions *and* the A/R step to accept them. Conversely, for PAS-X we only need to choose these unlikely transitions and the accept will then be likely. This removes a large factor that keeps these transitions from happening. 

On top of this, I enjoy the fact that the implementation of this algorithm is nearly trivial on top of LB or GWG. One must simply add the path-length proposal and apply the LB/GWG proposal X times. Methods like this are likely to find quick impact since they can be easily incorporated into existing systems. This is compared to continuous relaxation-based discrete sampling methods which add many additional hyper-parameters, must be carefully tuned, and still tend not to perform as well as the methods discussed in this work.

I find the results presented here compelling. On a wide array of distributions, PAS (and PAFS) appear to outperform LB (and GWG) when evaluated in distinct ways. Further, there *appears* (see comments in Weaknesses section) to also be a notable improvement when using PAFS to train EBMs. 

The work is not overloaded with theory (a good thing!). The authors provide what is necessary for understanding and correctness of the algorithm while leaving the work accessible to readers who are not experts in MCMC. Theorems 1 and 2 were easy to follow.

Overall, this method appears to be a solid step forward in MCMC for general discrete distributions, well supported with theory and empirical results. 


Weaknesses:

A key elegance of LB/GWG is the lack of hyper-parameters to tune. MCMC hyper-parameters are notoriously difficult to tune and, at the same time, crucial for good performance. This work adds a path-length proposal distribution as a new hyper-parameter on top of those earlier works. Do the authors have any proposals for how to choose the path-length proposal? I can imagine we'd like to maximize something like the average hop distance. Do the authors have any thoughts on this? If X is set too large for example, then I would assume most proposals would be rejected. There has been much work on this in the context of HMC (to which this method has some spiritual similarities). Even if the authors do not have a concrete approach for choosing this distribution, some discussion of the desiderata of the optimal choice would be appreciated to help guide practitioners in the future. 

Section 3.4 should contain a reference to Grathwohl et al. (2021) as this is clearly an extension of ideas presented in that work. As well, theorem 3 of this work is remarkably similar to theorem 1 of that work. This should be noted.

I find the deep EBM (and Ising training) results somewhat misleading. Which PAFS-X do you use? What is the runtime compared to GWG? How many steps are used per iteration in training? If you are using PAFS-X and N steps per iteration then you should compare with GWG using N*E[a(X)] steps since the runtime of PAFS-X is E[a(x)] times the runtime of GWG. How does this change the relative performance of the approaches? When training EBMs one can often get away with simpler MCMC approaches as the model tends to tune itself to the sampler used. This is why SGLD has had much more success in EBMs than more sophisticated samplers such as HMC. If the evaluation was more fair and the performance was still improved I'd be more likely to view this as a straight win over GWG for EBM training. If not, then there would still be some benefit to using GWG since it has no hyper-parameters to tune making it easier for practitioners less familiar with the nuances of tuning MCMC algorithms. 

The authors should add an appendix section on experimental details for the EBM training. How many steps are used per iteration? Which PAFS-X is used? How are the log-likelihood scores evaluated? As it stands the results are not reproducible and I am not convinced of the improvements over GWG presented. Based on the other results in the paper, I believe the results are likely to hold but further evidence should be presented.  

Add x-axis labels to figures 2 and 4. 

summary_of_the_review: This work presents a simple extension over prior state-of-the-art discrete MCMC methods which the authors demonstrate leads to improved performance on a wide variety of tasks. The method is simple, easy to implement, and appears correct. The authors provide the necessary theory for understanding the method and provide sufficient evidence for the performance of the method. There are some minor issues with the presentation of this evidence that should be addressed, particularly in the EBM training section. I would support acceptance of this work.
review_title: null

Meta-review: This paper provides a novel path auxiliary algorithm for more efficiently exploring discrete state spaces within a Metropolis-Hastings sampler for energy based models. In particular, it essentially replaces the "single site update" by instead proposing an entire path using local information, thus enabling the chain to take larger steps, which can improve acceptance/mixing significantly as they demonstrate. The work is a timely contribution that improves upon exciting recent work. After much discussion among several knowledgeable reviewers and clarifications regarding some details of the main theorem from the authors, there is consensus that the contributions are correct, novel, and likely of impact to the machine learning community. Since the revision period, the empirical evaluations have also been improved and the contributions have methodological novelty as well as promising practical performance.
Decision: Accept (Spotlight)