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: The paper provides an optimal scaling analysis of Locally Balanced Proposals (LBP), a recently-proposed class of informed MCMC algorithms for discrete spaces, see in particular [9,10,11]. In particular the paper:

a) Provides an optimal scaling result (theorem 3.1) for LBP on discrete spaces, more specifically on product-form binary spaces. Interestingly, the optimal acceptance rate and asymptotic scaling is the same as MALA on continuous spaces, i.e. an optimal acceptance rate of 0.574 and O(N^1/3) steps for each effective sample in dimension N, see Corollary 3.2.

b) Provides an optimal scaling result for RWM (theorem 3.8) for random-walk metropolis (RWM), under the stronger assumption that each bit has probability close to 0.5. Under this somewhat more artificial scenario, one recovers again the same behavior as RWM in continuous spaces, namely an optimal acceptance rate of 0.234 and O(N) steps for each effective sample in dimension N, see Corollary 3.9. This result seems to be mainly interesting to have a comparison with the one in a).

c) Implements adaptive MCMC versions of multi-step LBP, exploiting the theoretical results of (a) and (b), and tests the resulting algorithms on a variety of sampling tasks in high-dimensional discrete spaces. 

d) The proposed methods are applied to energy-based models (EBM) training, obtaining a 2- to 5-fold speedup compared to non-tuned single-step LBP.
strengths_and_weaknesses: Strengths:

- there is a large and well-established optimal scaling literature for MCMC in high-d continuous spaces. On the contrary, providing an analogous and meaningful analysis for discrete spaces is not easy and could be helpful to advance the practical and theoretical understanding of informed MCMC in high-d discrete spaces. This paper provides an interesting and significant step in this direction, coupling the optimal scaling framework with LBP and providing a meaningful and non-trivial analysis. Interestingly, the author obtain results that mirror the ones of continuous spaces both in terms of optimal acceptance rates and scaling with dimensionality.

- While recent work using LBP for discrete spaces sampling, e.g. [9,10,11], have witnessed promising empirical results in various tasks including EBM training, there is not much theory (even with some heuristics or on toy cases) quantifying the potential improvements given by LBP in high-dimensions. The analysis of the current paper provides some interesting results in this direction suggesting an O(N^2/3) gain, at least under some simplifying assumptions.

- The numerical results are well-designed, match with remarkable fidelity what predicted by the theory and suggest that the adaptive multi-step LBP schemes under consideration are promising algorithms for discrete space sampling and EBM training.

Weaknesses:

- While the result for LBP is interesting and genuinely novel, the one for RWM is derived under the unsatisfactory assumption that flipping probabilities are close to 0.5 (i.e. the target is close to flat) and is quite reminiscent of (though technically different from) the one in [30], both in terms of setting, spirit and conclusion.

- The results are derived for the specific case of product-form binary targets, which is quite specific and potentially restrictive. Also it somehow feels that in the context of discrete spaces, which is probably harder to study in terms of the questions considered in the paper, specific assumptions about the algorithm and the target distribution can play a more crucial role than in continuous spaces (e.g. use of gradient approximation or not, use of continuous versus discrete time LBP scheme, binary versus more general spaces, sampling bits with or without replacement, etc). For example, it would be interesting to have theoretical results that also quantify the impact of the gradient approximation as in [10] (since without that the cost per iteration of LBP and RWM is not comparable). This however would require considering more complex target distributions.

- Some mathematical statements (e.g. Lemma 3.3) are hard to follow and not rigorous enough. Also, there are quite a few typos throughout the paper. More details below.

- The novelty of the proposed methodology is relatively limited (basically an adaptive version of previously proposed schemes). In that sense the main contribution is the theoretical one, which provides results on optimal acceptance rates to guide tuning, and results quantifying the scaling with dimensionality under some simplifying assumptions.
questions: - You use EJD as a metric. It may be helpful to discuss and justify that in a more convincing way. For example, in continuous spaces, the ESJD is typically used. I believe the EJD makes more intuitive sense in discrete spaces than ESJD, but it may be worth discussing if that is the case or not. Also, are the optimality results sensitive to the choice? They seem to be, which makes it important to justify the choice. Also, the sentence in line 98 about ergodic averages being bad since they depend on the specific test function is not that convincing, since also the choice of EJD implies basically a (similarly arbitrary) choice of metric (and implicitly test function?).

- It would help to provide algorithmic box (in supplement) of the actual algorithm you use in simulations, including both the use of gradient approximation and clarifying that the gradient is not recomputed R times (as it is in the methodology of Sun et al (2021)?)

- In the specific setting of Theorem 3.1, the acceptance rates of multi-step LBP depends only on the ratio of normalizing constants Z. Would this still be the case in more realistic cases with non-product targets and gradient approximations? If not, what is your intuition for the results extrapolating well to more realistic scenarios?

- Why are the ESS results in Table 1 not that satisfying for RBM compared to the EJD and to the other models considered?

- Lemma 3.3: I find it hard to understand the exact mathematical statement contained therein (e.g. specify distribution of x and u; which limit are we taking exactly when we say "weakly converges to A+B"? e.g. are we taking a limit where N,R\to\infty? If yes, how can the limit A and B depend on R?). Also, I would remove "Using Taylor's series" since the Lemma should contain the mathematical statement, not how it is proved. Looking at the proof it seems more appropriate to state something like "the difference sum.... -(A+B) converges to 0", rather than "sum... converges to A+B" since A+B depend itself on N and R (like you stated e.g. in (6) of Theorem 3.1).

The paper contains various typos or inaccuracies, e.g.
- line 105: (??)
- line 118: additional "." at the end of line
- line 117: R should be an integer, while l N^(2/3) will not be n general.
- line 140: "we first determines"
- line 185: do Andrieu and Thoms [19] recommend freezing tuning parameters after warmup?
- line 287: typo in "wight"
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
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: This paper studies the optimal scaling of Metropolis-Hastings algorithms on the cube $\mathbb{Z}_2^N$. The analysis of optimal scaling for Markov chain Monte Carlo methods has been studied extensively for continuous state spaces, but not for discrete spaces. The authors provide a scaling analysis for the locally balanced proposal (LBP) in [2]. The authors show that the LBP has a better asymptotic property than the random-walk Metropolis (RWM) algorithm. Simulation results support the theoretical results.
strengths_and_weaknesses: The results in this paper are interesting and show a systematic difference between LBP and RWM. LBP is a new and useful method for discrete state space. I believe that the results in this paper are a good contribution to this field if the following weak points are solved. From the theoretical point of view, the result shows the similarity of LBP with the Langevin algorithm. Therefore, it is reasonable that LBP is superior to RWM. From a practical point of view, the result provides a guide for the choice of tuning parameters.

However, I feel that there is a gap between theory and claim. The efficiency presented in this paper only makes sense if the limit is a class of diffusion processes. However, the literature suggests that the limit is not a diffusion process, but a  Poisson process. Therefore, the meaning of efficiency is not obvious to me in this paper.

Also, I have a less clear picture of comparing LBP and RWM. The analysis of LBP focuses on the case $p\ll 1/2$, while the analysis of RWM focuses on the case $p \approx 1/2$. Therefore, it isn't easy to draw a general conclusion comparing the two algorithms. However, the paper [1] is useful in this comparison.

As a novelty, I need to mention that the scaling limit for discrete space is not new. More precisely, the LBP results are new, but the RWM results are known. See [1].  In [1], only the iid target distribution is considered, so the class of target distribution in this paper is much more general in this sense.  However, the authors only study the case where $p \approx 1/2$, but [1] also studied $p \ll 1/2$ and identified the limit process.

The paper has good potential, but I think there is room for improvement.

Minor
- I recommend checking statements and proofs once again. There are many minor errors. For example, in Lemma 3.3 $A+B$ is a limit of the random variable, say $X_N$, but $A+B$ still depends on $N$. 
- It would be nice if the authors could comment on the guideline for choosing the function $g$. 

[1] Gareth O. Roberts (1998) Optimal metropolis algorithms for product measures on the vertices of a hypercube, Stochastics and Stochastic Reports, 62:3-4, 275-283

[2] Haoran Sun, Hanjun Dai, Wei Xia, and Arun Ramamurthy. Path auxiliary proposal for mcmc in discrete space. In International Conference on Learning Representations, 2021

(I updated my rating after reading the authors response and follow-up.)
questions: - Does Theorem 3.1 hold regardless of the choice of $g$? What is the optimal choice of $g$ that minimises the value of $\lambda_1^2$?
limitations: The main limitation is the gap between theory and claim. The authors evaluate the expected squared jump distance. However, the meaning of this statistic is not clear in the current context, since the limit process is a pure jump process and not the Langevin diffusion.
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: The optimal scaling problem is the problem of finding the right scale of each jump in Metropolis-Hasting that leads to optimal convergence rate. Even though the problem has been well-studied in the continuous settings, it has been seldomly explored in discrete settings. As a contribution in this direction, the authors study the locally balanced proposal (LBP) proposed by Zanella (2020) which is designed to move one coordinate at a time, with the proposal distribution depending on the likelihood ratio between the local change. Later, Sun et al. (2021) propose a more general version of LBP which can switch multiple coordinates in one step. With this version of LDP, the authors are able to derive the optimal scaling, and with this scaling, they show that the multi-step LBP has an asymptotic acceptance rate that is independent of the target distribution, which is greater than that of the random walk Metropolis. 
strengths_and_weaknesses: # Strengths
This paper provides sufficient contribution towards efficient Metropolis-Hasting algorithms on discrete spaces. The authors provide thorough analyses and experiments, which agree with the results. I find the application on efficient energy based model to be very interesting. 

# Weaknesses
While the paper can be easily read by experts in the fields, I feel that some additions/explanations would be appreciated by outsiders. For example, the authors should explain what **scale** means in both continuous and discrete settings, and they should give a precise definition of **optimal scaling problem** in Section 1 or 2.

The authors have the following assumption on the target distribution $\pi(x) = \prod_{i=1}^N p_i^{x_i} (1-p_i)^{1-x_i}$:
$$ \epsilon < \min (p_j , 1-p_j ) < \frac{1}{2} - \epsilon \qquad \text{for some } \epsilon \in (0,\frac{1}{4}). $$
How the choice of $\epsilon$ in Eq. (2) affects the rate of convergence in Eq. (6) is still unclear to me. I have a hunch that the quality of the Taylor approximation in Lemma 3.3 depends on $\epsilon$ as well. All in all, I think the authors should expand more, in the main paper, on the effect of $\epsilon$ on the efficiency (I see that the choices of $\epsilon$ are mentioned in Appendix C.1 but not in the main paper), and whether the assumption above is reasonable in real-life scenarios (e.g. in EBM).

In the experiments, the authors only compare between two methods, namely LBP and RWM. Even though there are many experiments in the past which have already shown effectiveness of LBP against other methods, such as RWM, Gibbs sampling, the Hamming Ball sampler and continuous relaxation based methods, I still want to see how LBP performs against some of these methods, at least in energy based models.

In addition, I have found some potential mathematical typos in this paper:
* Page 3, Eq (2), $\wedge$ is used here but has never been defined before.
* Page 4, Eq (8), $a(R)R$ should be equal $2lN^{\frac{2}{3}}\Phi\left(-\frac{1}{2}\lambda_1 l ^{\frac{3}{2}}\right)$ in the asymptotic limit, not exactly equal.
* Page 14, Eq (25), what is $M_0$? 
* Page 14, Eq (29) and (30), should the middle expressions be put in absolute values?
* Page 14, Eq (29) and (31), $\mathbb{P}(|W(x,u)-W|>N^{\frac{1}{2}})$ should be $\mathbb{P}(|W(x,u)-W|>tN^{\frac{1}{2}})$.
* Page 15, Eq (36), what is the appropriate value of $t$ in order to apply Lemma A.1?
* Page 16, Eq (58), I am not sure how the factor of $1+O(N^{-\frac{1}{3}})$ pops up here.
* Page 18, Eq (84), $X_N$ should be $x_N$, $u_i,\ldots u_R$ should be $u_i,\ldots, u_R$ and $u'_i,u_R$ should be $u'_i,\ldots, u_R$.
* Page 20, Line 529, "we have:" -> "We have:"
* Page 23, Eq (164), should the lower order term depends on $t$ and $\lambda_2$ as well? Also, $R^{\frac{3}{2}}$ should be $R^{\frac{3}{4}}$.
questions: As mentioned above, I would like to know to what extent the choice of $\epsilon$ affects the convergence rate in Eq (6).
limitations: In addition to what the authors suggest in the Discussion, one might try to find (non-asymptotic) convergence rate as a function of $\epsilon$. There is also the question of finding the best weight function $g(t)$ which might depend on the task at hand. Can we find a heuristic on $g$ that gives us optimal or near-optimal performance?
review_title: null

Meta-review: metareview: The reviewers and I agree that the contributions of the paper are of interest and useful addition to the literature. Therefore, I recommend accepting the paper.

Please consider the reviewers' comments when preparing the camera-ready version.

confidence: Certain
Decision: Accept