Optimal Scaling for Locally Balanced Proposals in Discrete Spaces
Authors: Haoran Sun
Hanjun Dai
Dale Schuurmans
Venue: NeurIPS 2022 Accept (2022)
Keywords: MCMC
Discrete
Locally Balanced
Optimal Acceptance Rate

Abstract: Optimal scaling has been well studied for Metropolis-Hastings (M-H) algorithms in continuous spaces, but a similar understanding has been lacking in discrete spaces.
Recently, a family of locally balanced proposals (LBP) for discrete spaces has been proved to be asymptotically optimal, but the question of optimal scaling has remained open.
In this paper, we establish, for the first time, that the efficiency of M-H in discrete spaces can also be characterized by an asymptotic acceptance rate that is independent of the target distribution. 
Moreover, we verify, both theoretically and empirically, that the optimal acceptance rates for LBP and random walk Metropolis (RWM) are $0.574$ and $0.234$ respectively. 
These results also help establish that LBP is asymptotically $O(N^\frac{2}{3})$ more efficient than RWM with respect to model dimension $N$. 
Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces.
We demonstrate empirically that such adaptive M-H sampling can robustly improve sampling in a variety of target distributions in discrete spaces, including training deep energy based models.

Optimal Scaling for Locally Balanced Proposals in Discrete Spaces
Haoran Sun"
Hanjun Dai
Dale Schuurmans Google Brain, U of Alberta schuurmans@google com
Georgia Tech
Google Brain
hsun349@gatech.ede
fadai@google.co
Abstract
Optimal scaling has been well studied for Setropolis-Hastinne (M-H) algorithms in continuous spaces, but similar understanding has been lacking in discrete spaces. Recently, a family of locally balanced proposals (LBP) for discrete spaces has been proved to be asymptotically optimal, but the question of optimal scaling has remained open. In this paper, we establish, for the first time, that the efficiency of M-H in discrete spaces also be characterized by an asymptotic acceptance the target distribution. Moreover, we verify, both
rate that is independent theoretically and empirically, that the optimal acceptance rates for LBP and random walk Metropolis (RWM) are 0.574 and 0.234 respectively. These results also help establish that LBP is asymptotically O(N more efficient than RWM with respect model dimension N. Knowledge of the optimal acceptance rate allows one automatically tune the neighborhood size of proposal distribution in a discrete space, directly analogous step-size control in continuous spaces. We demonstrate empirically that such adaptive M-H sampling can robustly improve sampling in a variety target distributions in discrete spaces, including training deep energy based models.
Introduction
The Markov Chain Monte Carlo (MCMC) algorithm is one of the most widely used methods for sampling from intractable distributions (Robert & Casella 2013). important class of MCMC algorithms is Metropolis- Hastings (M-H) (Metropolis et al. 1953 Hastings 1970), where new states are generated from proposal distribution followed by M-H test. The efficiency for M-H algorithms depends critically on the proposal distribution. For example, gradient based methods, such as the Metropolis Adjusted Langevin Algorithm (MALA) (Rossky al.) 1978), Hamiltonian Monte Carlo (HMC) (Neal et al. 2011), and their variants Girolami & Calderhead (2011); Hoffman et al. (2014) substantially improve the performance M-H algorithms in theory and practice, compared to naive Random Walk Metropolis (RWM), by leveraging gradient information to guide the proposal distribution (Roberts & Rosenthal 2001.
Despite many advances, progress in gradient based methods has generally focused continuous spaces, However, Zanella (2020) recently proposed a general framework of locally balanced proposals (LBP) for discrete spaces, where a proposal distribution is designed to utilize probability changes between states. Subsequently, (rrtthwhl et al. (20T)) accelerated the sampler by using gradient information to approximate the probability change. In empirical evaluations, similar to gradient based samplers in continuous spaces, LBP significantly outperforms RWM and other samplers in discrete spaces. However, both Zanella (2020) and Grathwohl et al. (202T) constrain the proposal distribution to lie within I-Hamming ball; i.c., only one site of the state variable allowed to change per M-H
Work done during an internship at Google.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

step, Such a restricted update reduces the efficiency of the sampler. Sum et al. (021) noticed this problem and modified the proposal distribution to allow multiple sites to be changed per M-H step. Although such larger updates significantly improve efficiency. [Snn et al. (202]) do not show how to tune.
determine the update size, leaving the number of sites updated in an M-H step as a hyperparameter to
In continuous spaces, the scale of the proposal distribution is known be a critical hyperparameter for obtaining an efficient M-H sampler. For example, consider a Gaussian proposal Wiz o²) for modifying a current state z with scale a. If too small, the Markov chain will converge slowly since its increments will be small. Conversely, if a is too large, the M-H test will reject too high a proportion of proposed updates. A significant literature has studied optimal scaling for gradient based methods in continuous spaces (Gelman et al. 1997 Roberts & Rosenthal 1998] 2001; Beskos et al. 2013), showing that the optimal scaling can be adaptively tuned w.r.t. the acceptance rate, independent of the target distribution. Such results suggest a direction for solving the optimal scaling problem for LBP. However, the underlying techniques for approximating a diffusion process cannot be directly applied to LBP given its discrete nature.
In this work, we consider an asymptotic analysis as the dimension of the discrete model, N. converges to infinity. Starting with a product distribution, we prove that the asymptotic efficiency of LBP in dis- crete spaces is 2 3 X1 R# /N) with an asymptotic acceptance rate of 2 - A1 R$ /N), where the scale R represents the number of sites to update per M-H step. Therefore, the asymptotically optimal scale of the proposal distribution R = O 3) with an asymptotically optimal acceptance rate of 0.574, independent of the target distribution. Moreover, for RWM in a discrete space, we show that the asymptotic efficiency and acceptance rate 2 2/2 R² and 2 {222 ) respec- tively. Hence, the asymptotically optimal scale is ((1) and the asymptotically optimal acceptance rate is 0.234 for RWM. By comparing LBP and RWM at their respective optimal scales, it can be determined that LBP is 3( more efficient than RWM.
These asymptotically optimal acceptance rates are robust in the following respects. First, although the initial derivation is established w.r.t. product distributions, the result can be expanded to more general distributions. Second, the efficiency is not sensitive around the optimal acceptance rate. For example, whereas 0.574 is the optimal acceptance rate for LBP, the algorithm retains high efficiency for acceptance rates between 0.5 and 0.7. Based on these observations, we propose an adaptive LBP (ALBP) algorithm that automatically tunes the update scale to suit the target distribution.
We validate these theoretical findings in series of empirical simulations on the Bernoulli model, the Ising model, factorized hidden Markov models (FHMM) and restricted Boltzmann machines (RBM). The experimental outcomes comport with the theory. Moreover, we demonstrate that ALBP can automatically find near optimal scales for these distributions. We also use ALBP to train deep energy based models (EBMs), finding that it reduces the MCMC steps needed in contrastive divergence training (Hinton 2002 Tieleman & Hinton 2009), significantly improving the efficiency of the overall training procedure.
2 Background
Metropolis-Hastingg Algorithm Let x denote the target distribution. Given a current state 2=(1),
M-H sampler draws a candidate state from a proposal distribution g(x:(m) y). Then, with probability min {1, =(g)g(u.e(") ((a the proposed state is accepted and (=(++1) = y: otherwise, x ((*+1) (!1)
In this way, the detailed balance condition is satisfied and the M-H sampler generates Markov chain
Co, .i, that has π as its stationary distribution.
Locally Balanced Proposal. The locally balanced proposal (LBP) is special case of the pointwise informed proposal (PIP), which is a class of M-H algorithms for discrete spaces (Zanella 2020)
using the proposal distribution Q y) x g (Tt)/ such that g is a scalar weight function. Zanella (2020) shows that the family of locally balancing functions G = [g : R4 + R4, g(t) = tg(?), Vt > 0} (e.g. g(t) = vi or + is asymptotically optimal for PIP. Hence, PIP with a locally balanced function for its weight function is referred to as LBP. Despite having good proposal quality, PIP requires the weight g ( (z)) (2)(m((()) (z))) to be calculated for all candidate states z in the neighborhood

---

of z, which results in its high computational cost. Grathwohl et al. 2021 propose to estimate the probability change by leveraging the gradient, improving the scalability of LBP.
Locally Balanced Proposal with Auxiliary Path. Sun et al. 2021 generalize LBP by introducing auxiliary path sampler, which allows multiple sites to be updated per M-H step. In particular, [Sun et al. (202T) sequentially selects the update indices without replacement, and uses these indices as auxiliary variables keep the proposal distribution tractable while preserving the detailed balance condition. Although this can achieve significant improvements in empirical performance, [Sun et al.
(202T) manually tune the update size per M-H step, and leave the optimal scale problem open.
Main Result
3.1 Problem Statement
We establish asymptotic limit theorems for two M-H algorithms in discrete spaces: the locally balanced proposal (LBP) and random walk Metropolis (RWM). Following previous work (Gelman et al,, 1997; Roberts & Rosenthal] 1998, Beskos et al. 2013 Vogrine et al. 2022). we conduct our analysis a product probability measure In particular, for state space X {0, 1 1 we consider a factored target distribution
N
N II
(x)
II (T.))
P (1 ==1
(1-p.)
(1)
where each site assumed to have a sufficiently large probability for being both 0 and 1; that is, for a fixed E (0, 7t) we assume the target distribution belongs to:
P=:= (===)(() :c << - - 1
where we denote a (a, b}. To measure the efficiency of the sampler, an ergodic estimate varies with the objective function considered. Alternatively, we use natural progress estimate: the expected jump distance (EJD). Denote Po the transition kernel, d(x, y) as the Hamming distance between and For a M-H sampler parameterized by 0, its expected jump distance p(0) and corresponding expected acceptance rate a(f) are
p(0) Σ (())))(X, X.EE
a(I) E 7XX)))(XX X.EX
(3)
In continuous space, the limit of sampling process is a diffusion process, whose efficiency is de- termined by the expected squared jump distance (ESJD) (Roberts & Rosenthal 2001). In discrete space, the limit of the sampling process a jump process, whose velocity is characterized by the EJD. Hence, EJD is the correct metric to measure the efficiency in discrete space; see more details in Appendix B.T.
3.2 Locally Balanced Proposal
We consider the M-H sampler LBP-R, where R refers flipping R indices in each M-H step. Given a current state æ, LBP-R calculates the weight wy for flipping index j as in PIP. Since we are considering a binary target distribution of the form I have
wy(x) = w, g( F1 xz)
(4)
n. (イ)
where g is locally balanced function. Following Sun et al. (021). LBP-R select indices u, with probability P(u,, = .) x wy sequentially for r 1, ..., R, without replacement. The new state y is obtained by flipping indices u1.n of x. If we consider as auxiliary variable, the accept rate A(r, y, u) in the M-H acceptance test can written as
()))
R =
Wn. Wn-(y) (v)
R
A(x,y,u) 11
W(g.))+ E Wa, (0)
where W(r, u(r,u)=
Σ w; Σ
Wu. (5)
R
W ((z
- Wey (x)
3

---

From theorem in Sun et al. (022)) the auxiliary sampler LBP-R satisfies detailed balance. A M-H step of LBP-R RIZ is summarized Algorithm
Algorithm 1: M-H step of LBP-R and ALBP
1 Given current state z((), current R, initialize candidate set C (L,.,,N}
2 for = 1, R or 1,..., rounding (R)) do
3 Sample u, with P(u, = j) x (z((z!)) [
4
Pop ", out of the candidate set: t citu):
$ end
6 Obtain by flipping indices u., uR of x(().;
7 if rand(0,1) < A(x(n) y, u) then 2(++1)_ y else z(1-1) = (();;
8 if T Tormup then R441 < Re + (A(x(*), y. u) 0.574);
3.3 Optimal Scaling for Locally Balanced Proposal
We are now ready state the first asymptotic theorem. Theorem 3.1. For arbitrary sequence of target distributions {a (x))) )== C Pes the M-H sampler LBP-R with a locally balanced weight function obtains the following, if = [IN
1 -2 (- =0
lim a(R) N
(6)
where & is the c.d.f. of standard normal distribution and A1 only depends on n (N)
Σ/ P, (w) (1))
4(E ΣN wi (z)))) Σx=1
The definition of Å in explains the motivation of restricting the target distributions in In fact, introducing the gives upper and lower bounds of Ay. When all py are arbitrarily close to 2.- (w) - 22))) numerator will be zero, so is A1 As a result, the acceptance rate will always be 1. Else, when all pj arbitrarily close to 0 or 1. Ex Y Ei= (x:)) in denominator will be zero, and ê will be infinity. As result, the acceptance rate will always be O. So, we have to make the mild assumption in 2 to assure the following asymptotic result holds. A more detailed discussion about c given Appendix B.2
Corollary 3.2. The optimal choice scale for R = IN's is obtained when the expected acceptance rate 0.574, independent of the target distribution.
Proof. When R = 1 denote = = X I, we have:
p(R) = o(R)R 21 (0 (- + +o(1)) = (x,) 22Φ
N
1 7
+ t (N3)
(8)
means the optimal value of = independent of the target distribution (N), As known, can numerically solve z = 1.081, and the corresponding expected acceptance rate is a 0.574.
3.4 Proof of Theorem
Denote the current state as x and a new state proposed in LBP-R as y. Consider the acceptance rate A y, u) in Using the fact that, if index j not flipped then wy (g) wy wyr we have:
1=1 Wu. (v)
T(v)
1= wa(y)
N
II
= (9)
r= Wa, (x) T(x) 1= (x)
g(F.(v.)/TT

---

where ( takes advantage of the property of locally balanced function. Hence, the acceptance rate Azz y, u) can be simplified to:
R
1 1+ I+ iior Wn, (x)/W
1 AA exp
Σ log
(10)
1+ I+E = Way (w)/W (y, u)
From the definition in 5 we have W u) (w, u). Denote A min(i,)) and i V
max (i,j], we have the following approximation:
Lemma 3.3. Define W = Ex,a [W u)]. We have: limN-0 Ers log(
14 Sis "yy (m)(w))((2.)))
14 14 2is1 Wuy (t//W((w.))
(A + B) = 0, where
R Σ
A
R r 1) wure (Irm)) - rwre (tree)
(11)
W r=1
B 2 W
Σ
inj Wn, (w,, (Fuz) -R-iVj 1)w, (Yu.) Mw,, (Mus))
(12)
To analyze A and B, we reverse the order and u. In particular, instead of first sampling x ~ I (x)) then sampling p(x u), values of Tus and finally the values æ-w- Lemma 3.4. The joint distribution p(r, u) (u))(()( can be decomposed in the following form:
reversed order where first determine the indices ut then the
R
R p( lu, Tuie 1) p(xxuluu uu, T.)
p(x, u) II p( (1r-1) II
(13)
r=1
Denote j & u1r-1 represents j * for i 1,...,- the conditional probabilities are
p, (,,;(1)1 (54m O(N-
p(u, j(u1--1)
(14)
Σi=1 Piw; (r); (1)grruu
2 + w)(() w)(() +(N-
1
p(z, 1/u, 21, U4 ])
(15)
W
With the conditional distribution in Lemma 3.4 we are able to give concentration property of the term and show is safe ignore:
Lemma 3.5. With probability larger than - -1--0 O(exp(-N+)) B ONN +).
For term A, we use martingale central limit theorem with convergence rate (Haeusler) 1988 bound the Kolmogorov-Smirnov statistic.
Lemma 3.6.
When = 3, A defined as we have:
A P(
/ (0)--(())=000000 O i)), μ ==- 1713 0²
17113
(16)
By [6), the expectation w.r.t. A asymptotically equals to the expectation on Ni,, o2). The final step to prove Theorem 3.1 is to exploit property of the normal distribution.
Lemma 3.7. If Z ~ ((p,o3) then we have:
E[ exp( 2 ((t) exp (u+
)
0² 2
H
(17)
where To is the c.d.f. of the standard normal distribution.
By Lemma
3.6 3.7
we have the expectation of (10). which is the expected accept rate, equals to:
E E (R)
2 x11 exp(0)
2 (
24
1 (112
(18)
2
5

---

3.5 Optimal Scaling for Random Walk Metropolis
We denote the Random Walk Metropolis in discrete space as RWM-R, where R refers to flipping R indices in each M-H step. Under the Bernoulli distribution, site is more likely to stay high probability position, so if we randomly flip site, it is more likely to decrease its probability. That is, intuitively, the acceptance rate will decrease exponentially as the scale increases. Consequently, the optimal scale for RWM-R should be O(1). Though this is not a rigorous proof, the constant scaling indicates that will hard directly prove an asymptotic theorem for RWM-R. To address this difficulty, we first restrict our target distribution to a smaller class of Bernoulli distributions
p! C. Pe. which is formally defined as follows. For fixed e (0, ( and fixed / > define
P!l)
7 (N)
1 2N
NB <
(19)
No
When N is large, each pj will be very close to 1. In this way, the acceptance rate will not drop too fast when Ri is increased, and non-constant R will be permitted. This enables us to prove:
Theorem 3.8. For arbitrary sequence of target distributions (x( RWM-R R obtains the following, if R IN28.
C! the M-H sampler
(-Ebatt)
lim a(R) 24
(20)
N
where t is the f.f.f. of the standard normal distribution and x2 only depends on (N))
N
23 = =1)((((0))
= N
2 (2p,
Pi
(21)
Corollary 3.9. The optimal scale R = 1N28 is obtained when the expected acceptance rate is 0.234,
independent of the target distribution.
The rate in Corollary 3.9 is proved for arbitrary 3 >> O. we let 3 decrease to 0, at = the optimal scale for RWM-R is O(1) while the optimal acceptance rate is 0.234. Also, we can notice that (! converges to P. when 33 decrease to 0 and we are able to show the optimal scale RWM in Pa is O(1), see details in Appendix B.3 However, this limit is not mathematically rigorous, because Theorem 3.8 and Corollary 3.9 only hold asymptotically, such that smaller requires larger N. Hence, when 3 decreases to O, N must approach infinity to satisfy the asymptotic theorem. Although there is this minor gap in the analysis, the conclusion nevertheless aligns very well with different target distributions in the experiment section.
4 Adaptive Algorithm
Given knowledge of the optimal acceptance rate, one can design an adaptive algorithm that automati- cally tunes the scale of the M-H samplers. For this purpose, we use stochastic optimization Andrieu & T'homs (008); Robbins Monro (195T) to adjust the scaling parameter R, to ensure that the statistic ò approaches O, where is the acceptance probability for iteration t and 5 is the target acceptance rate (0.574 for LBP and 0.234 for RWM). According to Theorem 3. and Theorem 3.8 the acceptance rate is decreasing function of the scaling Rg. Hence, we use the update rule:
A
R < R₂ + A,
(22)
with step size 7) We follow common practice and adapt the tunable MCMC parameters during warmup phase before freezing them thereafter Gelman et al. (2013). The computational cost for (22) ignorable comparing the total cost of a M-H step. The algorithm boxes for ALBP and ARWM are
given in Appendix More advanced implementations are possible, but it is out of the focus in the
paper. We observe below that this simple approach able to maintain the sampler robustly near the optimal acceptance rate.

---

5 Related Work
Informed proposals for Eetropolli--asstinge (M-H) algorithms have been extensively studied for
continuous spaces (Robert & Casella 2013). The most famous algorithms are the
Langevin algorithm (MALA) (Rossky al. 1978) and Hamiltonian Monte Carlo (HMC) (Neal
ct al. 201T). MALA, HMC, and their variants Girolami & Calderhead 2011] [offman et al. 2014
Welling & Teh. 2011 Titsias& & Dellaportas, 2019. Hirt al.j 2021 Hoffman al. [021] Hird et al.
2020 Livingstone & Zanella 2019) use the gradient of the target distribution to guide the proposal
distribution toward high probability regions, which brings substantial improvements in sampling
efficiency compared to uninformed methods, such as random walk Metropolis (RWM) (Metropolis
al. }953).
Informed proposals have also demonstrated recent success in discrete spaces. Zanella
(020) first
gives formal definition of the pointwise informed proposal (PIP) for discrete spaces, then proves that locally balanced proposals (LBP), using a family of locally balanced functions as the weight function in PIP, are asymptotically optimal for PIP. Following this work, (Power& & Goldman (019) extended the framework to Markov jump processes and introduced non-reversible heuristics to accelerate sampling. [Sansone (202T) parameterize the locally balanced function and tune it by minimizing a mutual information. Grathwohl et al. (202T) give a more scalable version of I.BP for differentiable target distributions by estimating the probability change through the gradient. Despite strong empirical results, the LBP method of Zanella (2020) only flips one bit per M-H step, since PIP has restrict the proposal distribution
small neighborhood, e.g. I-Hamming ball, due to its computational cost. Sun et al. (202T) generalize LBP to flip multiple bits in single M-H step. gaining significant improvement in sampling efficiency. However, the scaling of the proposal distribution in Sun et al. (202T) was manually tuned and the optimal scaling problem was left open.
For continuous spaces, the optimal scaling problem for informed proposals has been well studied. A significant literature has already shown that the scale can be tuned with respect to the optimal acceptance rate (Roberts & Rosenthal 200T). e.g. 0.234 for RWM (Gelman al. 1997). 0.574 for MALA Roberts & Rosenthal (1998), 0.651 for HMC Beskos et al. (0013). and 0.574 for Barker (Vogrinc et al.) 2022). by decreasing the scale so that the Markov chain converges to a diffusion process. However, such a technique is not directly applicable to LBP given its discrete nature. Roberts 1998) make an initial attempt on discrete space, however assumes all dimensions satisfy
independent, identical Bernoulli distribution. In this work, we have established for the first time the optimal scale for LBP and RWM in discrete spaces.
Experiments
The effectiveness of LBP has been extensively demonstrated in previous work, e.g. Zanella (020);
Grathwohl et al. (202T); Sun et al. (202T), comparison to other M-H samplers for discrete spaces, such as RWM. Gibbs sampling, the Hamming Ball sampler (Titsias & Yau 2017), and continuous relaxation based methods Zhang et al. 2012); Pakman & Paninski (013); Nishimura et al. (017):
Han et al. (220)). Therefore, we focus on simulating LBP-R, with weight function gt)) T and RWM- to validate our theoretical findings. More experiments, including different weight functions and comparison between "with" " and "without" replacement versions of LBP are given in Appendix D
Throughout the experiment section, we will use the gradient approximation (Grathwohl et al. 2021). That is to say, we estimate the change in probability of flipping index i is estimated by: dz, = exp((1 - (V log (<r))) For the Bernoulli distribution, this is still exact and does not hinder the justification of the theoretical results. For more complex models, this approximation makes the algorithms significantly more efficient. particular, the gradient approximation only requires two calls of the probability function and two calls of the gradient function. Consequently, LBP with gradient approximation will take about twice time per update compared to RWM. our experiments, we observe that LBP and GWG takes 1.2 + 0.2 and 1.1 + 0.1 more time per update, respectively, than RWM, across all target distributions. We therefore omit reporting the detailed run time for each method.
7

---

6.1 Sampling from different target distributions
We consider four target distributions: the Bemoulli distribution, the Ising model, the factorial hidden Markov model (FHMM), and the restricted Boltzmann machine (RBM). For each model, we consider three configurations: C1, C2, and C3 for smooth, moderate, and sharp target distributions. To obtain performance curves, we first simulate LBP-1 and RWM-1 for an initial acceptance rate 4max- Then, we adopt Omax 0.02, Qmax 0.02k as target acceptance rate. For each rate, we use the adaptive sampler to obtain an estimated scale R, with which we simulate 100 chains and calculate the final real acceptance rate and efficiency. In this way, we collect abundant data points to characterize the relationship between acceptance rate and efficiency to facilitate the following analyses.
LIP 28 derizell Red00
HAA pemoedl E-Rco
LSF Hing p-50
speld on p-50
100
80
300
Emieerry
60-
25
40-
1
01
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
3.0
0.2
0.4
0.6
0.8
3.0
0.2
0.4
0.6
0.8
Accepcance Rate
Acceptaicc Rate
Accestancee Race
Accoptance Ratt
Figure 1: Efficiency Curves on Bernoulli
Figure 2: Efficiency Curves on Ising
Bernoulli Distribution. We validate our theoretical results on Bernoulli distribution. The probability mass function is given in ① For each configuration, we simulate domains with three dimen- 100, 800, 6400. The scatter plot for N = 800 is reported in Figure [ We also estimate À in and 21 and plot the theoretical efficiency curve in ( and 20 From Figure D can see that the simulation results align well with the theoretically predicted curves, and the optimal efficiencies were achieved at 0.574 for LBP and 0.234 for RWM for all configurations.
sionalities:
Ising Model. The Ising model [Ising 1924) is classical model physics defined on a x square lattice graph (Vp, Ep) (details in Appendix D.2 For cach configuration,
simulate three sizes p = 20, 50, 100. We report the results for 50 in Figure 2 For LBP, the optimal efficiencics are achieved at around 0.5, which is slightly less than 0.574, although these values are close. Thus can say that the asymptotically optimal acceptance rate for LBP still applies to the Ising model. For RWM, 0.234 perfectly matches the acceptance rate where the optimal efficiencies obtained.
Factorial Hidden Markov Model. The FHMM (Ghahramani & Jordan 1995) uses latent variables E X {0, 1) J to characterize time series data y E IR_ (details in Appendix D.3). Given y, we sample the hidden variables x from the posterior (>x) = p(=ly) For each configuration we simulate
in three sizes I, = 200, 1000, 4000. We report the results for 7. 1000 in Figure S One can observe that these results match the theoretical predictions very well.
E-1032
C-2003
230
200
0.150
350
0.125
100
0.100-
0.0
0.2
0.4
06
0.
1.0
0.0
0.2
0.4
0.6
0.5
0.4
0.6
0.8
1.0
0.05
0.10
0.15
0.20
Acceprance Rate
Accopcance Rate
Acceptance Race
Acceptance Race
Figure 3: Efficiency Curves on FHMM
Figure 4: Efficiency Curves on RBM
Restricted Boltzmann Machine. A RBM Smolensky 1986) is a bipartite latent- variable model that defines distribution over binary data E {0,1}* and latent data E {0. 13 (details in Appendix D.4). We train an RBM on the MNIST dataset using contrastive divergence (Hinton 2002) and sample observable variables r. We report the results Figure 4 For LBP, although RBM is much more complex than a product distribution, its efficiency versus acceptance rate curves still match the theoretical predictions very well. For RWM, even using R will result in acceptance rates less than 0.234 for all configurations. Although cannot check what the optimal value is,

---

Bemoulli
Hinn
PHMMM
L8F
L8P G
107
LGP
Oetiml Scaling R
187 C2
LBP C2
180
18P C2
207
101
sbabe = 0.620
slose 0.033
02 rpp 0.000
slice 0.980
(3 skge 0.666
10
10
10P
102
10t
1.0
10'
Emicency Ratto Ratto
10
107-
CL sless 0,850 saas
E1 shoe - d.1 klagg 0.613
C2 pipp 0.480
10a
10"
10a
10"
10
10'
12"
Number of Variables
Number of Variabies N
Number of Variables
Figure 5: Optimal Scaling R and Efficiency Ratio with respect to model dimension N
still observe that efficiency is an increasing function of the acceptance rate when the acceptance rate less than 0.234, predicted by the theory.
Optimal Scaling and Efficiency. We examine how optimal scaling for LBP, RWM and their relative efficiency ratio grow w.r.t. the model dimension N. In figure 5 we can see that both the optimal scaling and efficiency ratio are lincar log-log plot and the slopes are close to 2/5 across Bernoulli, Ising, and FHMM. The results matches the theories that the optimal scaling R R= ONN) for LBP, R = (1) for RWM, and the relative efficiency ratio LBP over RWM is O(N3)
Table I: Performance of the Samplers on Various Distributions
Size
Bemoulli
Ising
FHMM
RBM
Sampler
FJD
ESS
Time
FJD
ESS
Time
ETD
ESS
Time
EJD
ESS
Time
RWM-1
0.65
10.02
15.44
0.64
12.14
74.28
0.79
7.26
58.03
0.17
10.76
59.54
ARWM
L70
18.44
14.90
1.58
19.60
77.45
4.32
13.32
60.02
0.17
11.13
61.24
18.67
61.19
10.76
LBP.1
1.00
13.39
24.36
1.00
14.11
111.19
1.00
6.91
134.42
0.98
13.38
116.04
ALBP
78.63
622.35
28.07
821.06
124.37
242.01
129.28
487.63
26.07
25.59
144.03
GLBP
78.83
644.43
25.42
96.68
809.12
129.28
242.52
140.43
508.27
25.86
25.83
119.38
6.2
Adaptive Sampling
We have validated the theoretical findings regarding the optimal acceptance rates various distri- butions. In this section, we examine the performance of the adaptive sampler. In addition to the expected jump distance (EJD), we also report the effective sample size (ESS) B We compare the adaptive sampler ALBP, ARWM with their single step version LBP-1, RWM-1, and grid search version GLBP, GRWM, where tune the scaling R by grid search. We give the sampling results on Bernoulli model, Ising model, FHMM, and RBM with medium size and configuration C2 in table More results given in Appendix [ We can see that the adaptive samplers significantly more efficient than single step samplers, especially for LBP. Also, the adaptive samplers can robustly achieve almost the same performance comparing using grid search find the optimal scaling.
6.3 Training Deep Energy Based Models
Learning an EBM challenge task. Given data sampled from true distribution π,, we maximize the likelihood of the target distribution (x(x)) x e fofo( parameterized by 0. The gradient estimation requires samples from the current model, which is typically obtained via MCMC. The speed of training an EBM determined by how fast MCMC algorithm can obtain a good estimate of the second expectation.
"Computed using Tensorflow Probability

---

4
3
8
R
5
6
0
0
8
N
7
7
3
3
9
4
0
9 4
6
2
2
5
8
6
9
4
7
9
1
12
7
4
6
9
6
8
9
9
8
0
8 0 6
3 8 0
AL
2
/
7
1
2
8
4
A
Y
P
RR
po 3
5
3 E
2
2 4
L
2
6
9
MNIST
Omniglot
Caltech
Figure 6: Samples from deep EBMs trained by ALBP, sampler.
We evaluate adaptive samplers by learning deep EBMs. Following the setting in Grathwohl et al. (202T), train deep EBMs parameterized by Residual Networks (He et al. (016) small binary image datasets using PCD (Tieleman & Hinton 2009) with replay butfer (Du & Mordatch 2019). We compare two single step samplers and adaptive samplers, where LBP, uses g(t) . as
weight function and LBP: uses gt) = vt as weight function. When we allow them to run enough iterations in PCD, they are able to train EBMs in same good quality, To measure the efficiency of these samplers, we compare the minimum number of M-H steps needed in PCD in table 2 We can see that adaptive samplers only need one half even one fifth iterations compare to single step samplers. We also present long-run samples from our trained models via ALBP, in Figure 6
Table 2: Minimum M-H Steps Needed for PCD
Dataset
LBP,-1
ALBP,
LBP
ALBP,
Static MNIST
90
20
40
15
Dynamic MNIST
100
20
40
15
Omniglot
100
60
30
Caltech
100
60
80
30
7 Discussion
In this paper, we have addressed the optimal scaling problem for the locally balanced proposal (LBP) in (Sun et al. 202T). We verified, both theoretically and empirically, that the asymptotically optimal acceptance rate for LBP is 0.574, independent of the target distribution. Moreover, knowledge of the optimal acceptance rate allows one to adaptively tune the neighborhood size for proposal distribution in a discrete space. We verified the theoretical findings on diverse set of distributions, and demonstrated that adaptive LBP can improve sampling efficiency for learning deep EBMs.
We believe there is considerable room for future work that builds on these results. For theoretical investigation, the theory established under a strong assumption that the target distribution is product distribution, despite the results applics very well to more complicated distributions. We believe the results still hold under a weaker assumption that the target distribution has phase transition. We also believe it is possible to design a HMC style sampler for discrete spaces in the framework of Sun al. 202T) using LBP as block for the auxiliary path. For empirical investigation, many real-world problems involve probability models of discrete structured data, such as syntax trees for natural language processing (Tai al. 2015). program synthesis (Dai al. 2020), and graphical models for molecules (Gilmer et al. 7). Efficient discrete samplers should be able to accelerate both learning and inference with such models.
Acknowledgement
We thank Vladimir Koltchinskii, Pengcheng Yin, Matthew D. Hoffman, and three anonymous reviewers for their helpful comments to improve the manuscript. Dale Schuurmans gratefully acknowledges the support of Canada CIFAR AI Chair, NSERC and Amii.
10

---

References
Andrieu, C. and Thoms, A tutorial on adaptive meme. Statistics and computing, 18(4))343-373 2008.
Beskos, A., Pillai, N., Roberts, G., Sanz-Sema, J.-M., and Staart, A. Optimal tuning of the hybrid monte carlo algorithm. Bernoulli, 1905A)1501-1534, 2013.
Dai, H., Singh, R., Dai, B., Sutton, C., and Schuurmans, D. Learning discrete energy-based models auxiliary-variable local exploration. arXiv preprint arXiv:201 1.003230 2020.
Du, Y. and Mordatch, I. Implicit generation and generalization in energy-based models. arXiv preprint arXiv: 1903:9903.0000 99..08889,, 2019.
Gelman, A., Gilks, W. R., and Roberts, G. O. Weak convergence and optimal scaling of random walk metropolis algorithms. The annals of applied probability, 7(1):1 10-120, 1997.
Gelman, A., Carlin, J. B., Stem, H. S., Dunson, D). B., Vehtari, A., and Rubin, D. B. Bayesian data analysis. CRC press, 2013.
Ghahramani, and Jordan, M. Factorial hidden markov models. Advances in Neural Information Processing Systems, 8, 1995.
Gilmer, J., Schoenholz, S. S., Riley, F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 12722227. PMLR, 2017.
Girolami, M. and Calderhead, B. Riemann manifold langevin and hamiltonian monte carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73(2):123-2144 123-214, 2011.
Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D., and Maddison, C. J. Oops i took gradient: Scalable sampling for discrete distributions. arXiv preprint 1.Xiv:21020045000 2021.
Hacusler, E. On the rate of convergence in the central limit theorem for martingales with discrete and continuous time. The Annals of Probability, pp. 275-299, 1988.
Han, J., Ding, F., Liu, X., Torresani, L.., Peng, J., and Liu, Q. Stein variational inference for discrete distributions. In International Conference on Artificial Intelligence and Statistics, pp. 4563-4572. PMLR, 2020.
Hastings, W. K. Monte carlo sampling methods using markov chains and their applications. 1970.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Hinton, G. E. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771-1800, 2002.
Hird, M., Livingstone, S., and Zanella, G. A fresh take on' barker dynamics' for meme. arXiv preprint arXiv:20/2.09731, 2020.
Hirt, M., Titsias. M.. and Dellaportas, P. Entropy- based adaptive hamiltonian monte carlo. Advances in Neural Information Processing Systems, 34, 2021.
Hoffman, M., Radul, A., and Sountsov, P. An adaptive-meme scheme for setting trajectory lengths in hamiltonian monte carlo. In International Conference Artificial Intelligence and Statistics, pp. 3907-3915. PMLR, 2021.
Hoffman, M. D., Gelman, A., et al. The no-u-turn sampler: adaptively setting path lengths in hamiltonian monte carlo. J. Mach. Learn. Res., 15():1593--163, 2014.
Ising, E. Beitrag zur theorie des ferro-und paramagnetismus. PhD thesis, Grefe & Tiedemann, 1924.
Livingstone, and Zanella, G. The barker proposal: combining robustness and efficiency in gradient-based meme. arXiv preprint 1188 2019.

---

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. Equation of state calculations by fast computing machines. The journal of chemical physics, 2166):0877-1022. 1953.
Neal, R. M. et al. Mcme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2 (11):2, 2011.
Nishimura, A., Dunson, D., and Lu, J. Discontinuous hamiltonian monte carlo for sampling discrete parameters. arXiv preprint arXiv: 853, 2017.
Pakman, A. and Paninski, L.. Auxiliary-variable exact hamiltonian monte carlo samplers for binary distributions. arXiv preprint arXiv:1311.2166, 2013.
Power, S. and Goldman, J. V. Accelerated sampling on discrete spaces with non-reversible markov processes. arXiv preprint 1rXiv:1912.04681, 2019.
Robbins, H. and Monro, S. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Robert, C. and Casella, G. Monte Carlo statistical methods. Springer Science & Business Media, 2013.
Roberts, G. O. Optimal metropolis algorithms for product measures on the vertices of a hypercube. Stochastics and Stochastic Reports, 62(3-4):275-283, 1998.
Roberts, G. O. and Rosenthal, J. S. Optimal scaling of discrete approximations to langevin diffusions. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 60(1):255-266, 1998.
Roberts, G. O. and Rosenthal, J. S. Optimal scaling for various metropollishhattings algorithms. Statistical science, 16(4):351-367. 2001.
Rossky, J., Doll, J., and Friedman, Brownian dynamics as smart monte carlo simulation. The Journal of Chemical Physics, 69(10):4628 4633, 1978.
Sansone, E. Lsb: Local self- gelf-balancing meme in discrete spaces. arXiv preprint arXiv:2109.03867 2021.
Smolensky, P. Information processing in dynamical systems: Foundations of harmony theory.
Technical report, Colorado Univ at Boulder Dept of Computer Science, 1986.
Sun, H., Dai, H., Xia, W., and Ramamurthy, A. Path auxiliary proposal for meme in discrete space.
In International Conference on Learning Representations, 2021.
Tai, K. S., Socher, R., and Manning, C. D. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.000 2015.
Tieleman, T. and Hinton, G. Using fast weights to improve persistent contrastive divergence. In Proceedings of the 26th annual international conference on machine learning, pp. 1033-1040, 2009.
Titsias, M. and Dellaportas, P. Gradient- based adaptive markov chain monte carlo. Advances in Neural Information Processing Systems, 32: 15730-1915,3,, 2019.
Titsias, M. K. and Yau, C. The hamming ball sampler. Journal of the American Statistical Association, 112(520): 2017.
Vogrinc, J., Livingstone, S., and Zanella, G. Optimal design of the barker proposal and other locally-balanced metropolis-hastings algorithms. arXiv preprint arXiv:2201.01 2022.
Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-/1), pp. 681-688. Citeseer, 2011.
Zanella, G. Informed proposals for local meme in discrete spaces. Journal of the American Statistical Association, 115(530):552-863 2020.
12

---

Zhang, Y., Ghahramani. Z., Storkey, A. J., and Sutton, C. Continuous relaxations for discrete hamiltonian monte carlo. Advances in Neural Information Processing Systems, 25:3194-333 3202, 2012.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] . You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See cttps://githut thub com/
haOransun/LBP SScale.eeeee-- git
Did you include the license to the code and datasets? [Yes]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen- tal material
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A] The work does not use existing assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
Codebase is included in supplemental materials.
(d) Did you discuss whether and how consent obtained from people whose data you'ne
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "iuDRjKSfOzU", "reviewer": "Reviewer_GHqz", "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. ", "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?", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\nThis 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. \n\n# Weaknesses\nWhile 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.\n\nThe 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}$:\n$$ \\epsilon < \\min (p_j , 1-p_j ) < \\frac{1}{2} - \\epsilon \\qquad \\text{for some } \\epsilon \\in (0,\\frac{1}{4}). $$\nHow 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).\n\nIn 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.\n\nIn addition, I have found some potential mathematical typos in this paper:\n* Page 3, Eq (2), $\\wedge$ is used here but has never been defined before.\n* 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.\n* Page 14, Eq (25), what is $M_0$? \n* Page 14, Eq (29) and (30), should the middle expressions be put in absolute values?\n* 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}})$.\n* Page 15, Eq (36), what is the appropriate value of $t$ in order to apply Lemma A.1?\n* Page 16, Eq (58), I am not sure how the factor of $1+O(N^{-\\frac{1}{3}})$ pops up here.\n* 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$.\n* Page 20, Line 529, \"we have:\" -> \"We have:\"\n* 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}}$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XJsEY1G5miq", "reviewer": "Reviewer_xSRR", "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.", "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. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nHowever, 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.\n\nAlso, 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.\n\nAs 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.\n\nThe paper has good potential, but I think there is room for improvement.\n\nMinor\n- 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$. \n- It would be nice if the authors could comment on the guideline for choosing the function $g$. \n\n[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\n\n[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\n\n(I updated my rating after reading the authors response and follow-up.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lh9oqGPE4p", "reviewer": "Reviewer_Lua3", "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:\n\na) 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.\n\nb) 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).\n\nc) 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. \n\nd) 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.", "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?).\n\n- 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)?)\n\n- 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?\n\n- Why are the ESS results in Table 1 not that satisfying for RBM compared to the EJD and to the other models considered?\n\n- 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).\n\nThe paper contains various typos or inaccuracies, e.g.\n- line 105: (??)\n- line 118: additional \".\" at the end of line\n- line 117: R should be an integer, while l N^(2/3) will not be n general.\n- line 140: \"we first determines\"\n- line 185: do Andrieu and Thoms [19] recommend freezing tuning parameters after warmup?\n- line 287: typo in \"wight\"", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- 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.\n\n- 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.\n\n- 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.\n\nWeaknesses:\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept