LSB: Local Self-Balancing MCMC in Discrete Spaces
Authors: Emanuele Sansone
Venue: NeurIPS 2021 Submitted (2021)
Keywords: MCMC
discrete sampling
mutual information

Abstract: Markov Chain Monte Carlo (MCMC) methods are promising solutions to sample from target distributions in high dimensions. While MCMC methods enjoy nice theoretical properties, like guaranteed convergence and mixing to the true target, in practice their sampling efficiency depends on the choice of the proposal distribution and the target at hand. This work considers using machine learning to adapt the proposal distribution to the target, in order to improve the sampling efficiency in the purely discrete domain. Specifically, (i) it proposes a new parametrization for a family of proposal distributions, called locally balanced proposals, (ii) it defines an objective function based on mutual information and (iii) it devises a learning procedure to adapt the parameters of the proposal to the target, thus achieving fast convergence and fast mixing. We call the resulting sampler as the Locally Self-Balancing Sampler (LSB). We show through experimental analysis on the Ising model and Bayesian networks that LSB is indeed able to improve the efficiency over a state-of-the-art sampler based on locally balanced proposals, thus reducing the number of iterations required to converge, while achieving comparable mixing performance.

LSB: Local Self-Balancing MCMC in Discrete Spaces
Anonymous Author(s) Affiliation
Address
email
Abstract
Markov Chain Monte Carlo (MCMC) methods promising solutions sample from target distributions in high dimensions. While MCMC methods enjoy nice theoretical properties, like guaranteed convergence and mixing the true target, in practice their sampling efficiency depends on the choice of the proposal distribution and the target at hand. This work considers using machine learning adapt the proposal distribution to the target, in order to improve the sampling efficiency in the purely discrete domain. Specifically, (i) proposes a new parametrization for a family of proposal distributions, called locally balanced proposals, (ii) it defines an objective function based on mutual information and (iii) devises learning procedure to adapt the parameters of the proposal to the target, thus achieving fast convergence and fast mixing. We call the resulting sampler as the Locally Self- Balancing Sampler (LSB). We show through experimental analysis on the Ising model and Bayesian networks that LSB is indeed able improve the efficiency over state-of-the trrt sampler based on locally balanced proposals, thus reducing the number of iterations required to converge, while achieving comparable mixing performance.
2
6
11
13
15
Introduction
17
18 Sampling from complex and intractable probability distributions is of fundamental importance for
19 learning and inference [16]. MCMC algorithms are promising solutions handle the intractability
20 of sampling in high dimensions and they have found numerous applications, in Bayesian statistics
21
and statistical physics 17 233, bioinformatics and computational biology [ as well as machine
22
learning [8)
Although, MCMC can be applied to sample from any target distribution, in practice its efficiency strongly depends on the choice of the proposal. Indeed, common phenomena, like slow convergence and slow mixing, are typically the result of wrong choices of the proposal distribution. Therefore, it's extremely important to devise strategies enabling the tuning of the proposal to target distributions (5)
24
26
27
13.
While there has been a lot of work focusing on designing machine learning-based strategies to
28
improve the efficiency of MCMC in the continuous domain 29 20
19] less effort has been devoted to the discrete counterpart. Most common solutions consider continuous relaxations of
29
30 the problem by using embeddings and then leverage existing sampling strategies designed for the
31 continuous case. These strategies are suboptimal, either because they consider limited settings, where
32 the target distribution has specific analytic forms [29), or because they make strong assumptions on
33 the properties of the embeddings. thus not having guarantees of preserving the topological properties
34 of the original discrete domain 22 [9]
35 This work focuses on MCMC strategies for the purely discrete domain. Specifically, (i) we introduce
38 a new parametrization for family of proposal distributions, called locally balanced proposals, which
37 have been recently studied in 28] (ii) we define an objective function based on mutual information,
38 which reduces the distance between the proposal and the target distribution and also reduces the
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

39 statistical dependence between consecutive samples, and (iii) we devise learning procedure to adapt the parameters of the proposal to the target distribution using our objective. The resulting procedure. called the Local Saff-inaancing sampler (L.SB), automatically discovers an optimal locally balanced 41
40
42 proposal, with the advantage of reducing the amount of user intervention and of improving the overall sampling efficiency, both in terms of convergence speed and mixing time.
48
44
We provide some empirical analysis of sampling from the 2D Ising model and from Bayesian networks and show that in some cases LSB is able to halve the number of iterations required to converge, while achieving similar mixing performance to 28
45
46
47
We start by providing some background on locally balanced proposal distributions (Section 2 introduce LSB by describing the parametrizations, the objective and the learning procedure (Section 3 we discuss the related work (Section 4) and the experiments (Section 5 and finally we
49
50
conclude by highlighting the main limitations of LSB and possible future directions (Section 66)
2 Background
51
52
We consider the problem of sampling from a distribution p with support defined over a large finite discrete sample space X, i.e. p(x) - p(x) Ex"ex p(x"), where the normalization term cannot be tractably computed and only p can be evaluated. One solution to the problem consists of sampling using MCMC [17]. The main idea of MCMC is to sequentially sample from a tractable surrogate distribution, alternatively called proposal, and to use an acceptance criterion to ensure that generated samples are distributed according to the original distribution. More formally, MCMC is Markov chain with transition probability of the form:
58
54
55
56
57
58
T(x|x) = A(x', x Q) + 1[xxx==X = Σ (1-A(xx; (1=A(x",)))((x*"1) X"EX
where Q(x'[x) [x) is the probability of sampling x' given previously sampled x, namely the proposal 60 distribution, 1[-] is the Kronecker delta function and A(x', x) is the probability of accepting sample
((x))((xxx) I In this work, we consider the family of locally 61 x' given x, e.g. x(x'x))= mmnn {1, p[x]Q(x<|<>
62 informed proposals (28) which are characterized by the following expression:
9
A(x')
1[x' E Nx))
Q(x' x)
p(x)
2(x)
where (xx) is the neighborhood of x based the Hamming metric
64
Note that the choice of g has a dramatic impact on the performance of the Markov chain, as investigated in (28). In fact, there is a family of functions called balancing functions, satisfying the relation g(t) = (g /t) (for all i. > 0), which have extremely desirable properties, briefly recalled hereunder.
65
66
68
Acceptance rate. The balancing property allows to rewrite the acceptance function in a simpler form, namely A(x'xx) x) = min {1, 2(x) }. Therefore, a proper choice of g can increase the ratio 2
69
between the normalization constants (x) and Z(x') with consequent increase of the acceptance rate even in high dimensional spaces.
71
72
Detailed balance. Note that for all x' x, detailed balance trivially holds, viz. p(x)T(x' x) p(x')T(xxxx In all other cases, detailed balance can be proved, by exploiting the fact that T(x [x)
73
74 A(x', xx)(x'|x) and by using the balancing property (see the Supplementary material for more details). Detailed balance is a sufficient condition for invariance. Consequently, the target is fixed point of the Markov chain.
76
77 Ergodicity. Under mild assumptions, we have also ergodicity (we leave more detailed discussion
78 to the Supplementary material). In other words, the Markov chain converges to the fixed point
79 independently from its initialization.
Other choices are available 17 as well.
In other words, consider all points having Hamming distance equal to I from x.

---

80
Efficiency. The efficiency of MCMC is generally measured in terms of the resulting asymptotic 81 variance for sample mean estimators. This indeed a proxy to quantify the level of correlation between samples generated through MCMC. Higher levels of asymptotic variance correspond to higher levels of correlation, meaning that the Markov chain produces more dependent samples and it is therefore less efficient. Balancing functions are asymptotically optimal according to Peskun
85
84
85
ordering (28].
86
The work in 28 proposes a pool of balancing functions with closed-form expression together with
87
some general guidelines to choose one. However, this pool is only subset of the whole family of balancing functions and several cases do not even have an analytical expression. Consequently, it is
88
89
not clear which function use in order to sample efficiently from the target distribution. Indeed, we will see in the experimental section that (i) the optimality of the balancing function depends on the target distribution and that (ii) in some cases the optimal balancing function may be different from the
90
91
ones proposed in [28]. In the next sections, we propose strategy to automatically learn the balancing function from the target distribution, thus achieving fast convergence (burn-in) and fast mixing.
93
3 LSB: Local Self-Balancing Strategy
94
95 We start by introducing two different parametrizations for the family of balancing functions in increasing order of functional expressiveness. Then, we propose an objective criterion based on mutual information, that allows us to learn the parametrization with fast convergence and fast mixing on the target distribution.
96
97
99
3.1
Parametrizations
100
We state the following proposition and then use it to devise the first parametrization.
101
Proposition 1. Given n balancing, functions g(t) [g (t)..... .n (t))" and a vector of scalar
positive weights w [w....., ,I,"" the linear combination g(t) w" g(t) satisfies the balancing property.
102
103
Proof. s(t) w ((gg(() = E (1== wog()) tw? TowTg((2) g(1()) (g(1/))
=
105
Despite simplicity, the proposition has important implications. First of all, allows to convert the problem of choosing the optimal balancing function into learning problem. Secondly, the lincar combination introduces only few parameters (in the experiments we consider n = 4) and therefore the learning problem can be solved in an efficient way. The requirement about positive weights is necessary to guarantee ergodicity (see Supplementary material on ergodicity for further details).
107
109
The first parametrization (LSB 1) consists of the relations w; = -e Ey= eai for all = 1...., where 0- 101.... 0x] E R". Note that the softmax is used to smoothly select among the balancing functions. Therefore, we refer to this paramctrization as learning to select among existing balancing functions.
110
112
114
The second parametrization (LSB 2) is obtained from the following proposition.
115
Proposition 2. Given (t) min he (t), the (1/f)), where he is universal real valued function approximator parameterized by vector 0 R (e.g. neural network), and any balancing function E, there always exists 0 E R such that ga (t) f(t) for all t > 0.
117
118
Given any balancing function É, we can always find a θ such that hg) = E(t) for all / > 0 (because hy is universal function approximator). This implies that ha satisfies the balancing property, ie. ht(t) = the (1/t) for all > O. Consequently, by definition of gø. we have that go ) = hg (t). And finally can conclude that go (t) E(t) for all t O.
Proof.
120
122 In theory, LSB 2 parameterizes the whole family of balancing functions and allows to find the optimal one from the whole set increasing functions, as we prefer to choose a proposal distribution sampling from regions of higher
| In practice, it is better to restrict the analysis only to monotonic
123
124
Note also that ge (t) is balancing function for any parameter 0.
3

---

125
probability mass. In the following proposition. we provide sufficient conditions to ensure the monotonicity of LSB 2.
126
127
Proposition 3. Define ge as in LSB 2. Assume that (t) is a differentiable and monotonic increasing
function with respect to variable t, satisfying the relation he (1/t) 2 dhall/U) for all t > 0. Then, ge is a monotonic increasing feaeeasinnffucctti function in t.
129
Proof. We have that hg(1/t) 1 dh/(1/1)
7 di 2 0 for all t > 0. Also, note that (1/1(1/1))
130
di dh/(1/0) O. Therefore, (1/Ll a monotonic increasing function in for min(ho((1)) (1 (1/4(1144)) (1g)))) (22hi(/(22()) By monotonicity of ht) and (h/(1/)), we have that he((t) 2 (12) and 1 (1/t)) 2 (1/2() Therefore, we can conclude that 9o (t1) 2 go g0())) for
(1/1/))
131
di
132
all L > 0. Now, consider any 1,,2 with 4 2 l2 > 0. go(())
133
and go (12)
134
135
all 12 with 8 2 12 0.
Therefore, to build yo. we need monotonic function hl)) Specifically, we can choose monotonic
network (24] and constrain he satisfy the condition (1/t)) 2 [hhe(l/t) for all > (see the Supplementary material for further information on how to impose the condition on he). In the next paragraphs, we propose an objective and a learning strategy train the parameters of the two parametrizations.
137
138
139
140
141
3.2
Objective and Learning Algorithm
142
The goal here is to devise a criterion to find the balancing function with the fastest speed of conver- gence/mixing on the target distribution p. Note that the ideal case would be to sample from p in an independent fashion. We have already mentioned that this operation is computationally expensive due to the intractability of computing the normalizing constant. In our case, we have to consider the agnostic case, because the proposal distribution is tractable surrogate for p. In this regard, define a criterion taking into account the distance from this ideal case. Specifically, we measure the distance of the transition probability of the Markov chain in Eq. [ from the target p and the amount of dependence between consecutive samples generated through it. In other words, we introduce the following criterion, which is indeed form of mutual information objective:
143
145
147
149
150
Io K ((((()))) (a (=))l=(=))p(==)) (="")//") p (TT.(To (()_===))]ll((()))
(3)
151
where KL is the Kullback Leibler divergence and E, is the expected value of random vector x distributed according p and
152
(a(='( Zr
Vx' + x
To(2' =
otherwise
153
a conditional distribution defined over the transition probability (z' (x) in Eq. | where we have explicited the dependence on 0 and we have introduced the normalizing constant Zr, to ensure that To (x') [z) is a proper probability distribution. Note also that 7g (x' (z) discards all pair of equal samples, i.c. x' x. as they are samples rejected by the Markov chain.
154
155
156
157 Minimizing Eq. 3 aallows us to find the configuration of parameters bringing us "closer" in terms of Kullback Leibler the ideal case, namely To (x' (x) = p(x') for all x' * x. The expectation in Eq. requires access to samples from p and therefore cannot be computed. Nevertheless, note that
158
159
the KL term in Eq. 3 can be rewritten in an equivalent form (see the Supplementary material for the
181
derivation):
I(0 = Eqoo w0,00 Ag ,x) log Ag (aa,,x))ee 2x)Qo(a (x)
(T
(5)
p(x')
162
where wo.0g
Qo(x'(z)) Qa (=' ø)
and On is the reference parameter vector for the proposal distribution.
163
Alternatively to Eq. 3 we can minimize the following quantity
((0) Equ... (J(0.)) Eqe, (T(0,z))
184
where Qinit is the distribution used initialization, typically uniform on the support X. Note that the first and the second terms in Eq. [oeeuurr fast burn-in and fast mixing, respectively. Therefore,
185
186
0 can be learnt using the procedure described in Algorithm 1.
See the Supplementary material for the modification of the objective for parametrization LSB 2.

---

Algorithm 1: Local Self-Balancing Training Procedure.
Learning rate 17- le 4, initial parameter Og. burn-in iterations K and batch of samples N.
(+)
R==1 ~ Qinit
while
k=I:K do
a fi=t ~ Qinit
1N
while i=/:N do
Joyy + Estimate of J (() using one sample from Qo, (z/ mnse)
200 F0a Estimate of [(0, = using one sample from Qo, (I (0))
end
[(0) = N E==1 fo' + E J0:
+
0 0- # (0):
Update
(5) (0) J.V. with accepted samples;
0,+ 8- 0
end
4
Related Work
168
It's important to devise strategies, which enable the automatic adaption of proposals to target distributions, not only to reduce user intervention, but also to increase the efficiency of MCMC samplers S 13 Recently, there has been a surge of interest in using machine learning and in particular deep learning learn proposals directly from data, especially in the continuous domain. Here, we provide a brief overview of recent integrations of machine learning and MCMC samplers according to different parametrizations and training objectives.
170
172
173
174
Parametrizations and objectives the continuous domain. The work in 27 proposes a strategy based on block Gibbs sampling, where blocks are large motifs of the underlying probabilistic graphical structure. It parameterizes the conditional distributions of each block using mixture density networks and trains them using meta-learning
175
176
log- we--ikkeihood--bseeeee objective. The work in [25] considers a global sampling strategy, where the proposal is parameterized by a deep generative model. The
178
model is learnt through adversarial training, where a neural discriminator is used detect whether or not generated samples are distributed according to the target distribution. Authors in [10] propose a global sampling strategy based on MCMC with auxiliary variables [1]. The proposals are modelled as Gaussian distributions parameterized by neural networks and are trained on a variational bound of bog-likelihood-basee
180
182
183
objective. The works in [5] g propose a mradient-based MCMC 77 9 where neural models are used to learn the hyperparameters of the equations governing the dynamics of the sampler. Different objectives are used during training. In particular, the work in [8] uses a log- likeliield based objective, whereas the work in [15] considers the expected squared jump distance, namely tractable proxy for the lag-1 autocorrelation function [21]. The work in [30] proposes a global two-stage strategy, which consists of (i) sampling according to a Gaussian proposal and (ii) updating its parameters using the first- and second-order statistics computed from a properly maintained pool of samples. The parameter update can be equivalently seen as finding the solution maximizing a likeeiiidhoo function defined over the pool of samples. Finally, the work in [22 extends this last strategy to the case of Gaussian mixture proposals. All these works differ from the current one in least two aspects. Firstly, not clear how these parametrizations can applied to sampling in the discrete domain. Secondly, the proposed objectives compute either a distance between the proposal distribution and the target one, namely using an adversarial objective or a variational bound on the likeeihodo, or proxy on the correlation between consecutive generated samples, namely the expected squared jump distance. Instead, our proposed objective is more general in the sense that it allows to (i) reduce the distance between the proposal and the target distribution as well as to (ii) reduce the statistical dependence between consecutive samples, as being closely related to mutual information.
184
185
186
187
188
189
190
191
193
194
195
197
199
Sampling in the discrete domain. Less efforts have been devoted to devise sampling strategies 201
for a purely discrete domain. Most of the works consider problem relaxations by embedding the discrete domain into a continuous one, applying existing strategies like Hamiltonian Monte
203
Carlo [29 20
I 6, 19 on it and then moving back to the original domain. These strategies are
5

---

(a) Noisy
(b) Clean
Figure I: Examples of a in different settings of the Ising model (30x 30), i.e noisy μ = 1, = and clean 3,0 3.
suboptimal, either because they consider limited settings, where the target distribution has specific
206
analytic forms [29], or because they make strong assumptions on the properties of the embeddings,
thus not preserving the topological properties of the discrete domain (20) I 6 [9] The work
208
in 288 provides an extensive experimental comparison between several discrete sampling strategies,
including the ones based on embeddings, based stochastic local search [11] and the Hamming ball
210
sampler [26). which can be regarded as a more efficient version of block Gibbs sampling. Notably,
211
the sampling strategy based on locally informed proposals and balancing functions proposed in (28) can be considered as the current state of the art for discrete MCMC. Our work builds and extends upon this sampler by integrating with machine learning strategy. To the best of our knowledge,
212
213
214
this is the first attempt to consider the integration of machine learning and MCMC in the discrete setting.
215
Experiments
216
Firstly, we analyze samplers' performance the 2D Ising model. Then, we perform experiments on additional UAI benchmarks. Code to replicate the experiments in this section is available in the Supplementary material. All experiments are performed on a laptop provided with 4 Intel i5 cores (2 GHz) and 16 GB of RAM memory.
218
220
221
5.1
2D Ising Model
222
The Ising model has been introduced in statistical mechanies in 1920 and it has been applied in several domains since then. In this section, we consider an application to image analysis, where the
223
224
goal is to segment an image to identify an object from its background. Consider a binary state space
225
X
13, where (V, E) defines square lattice graph of the same size of the analyzed image, namely n. For each state configuration x (Ii)sEV X, define a prior distribution
226
Pprior(x)) x exp A
Σ (KJ)EE
where À is a non-negative scalar used to weight the dependence among neighboring variables in the lattice. Then, consider that each pixel is influenced only by the corresponding hidden variable 229 I; and generated according to a Gaussian density with mean Juz; and variance a². Note that each variable in the lattice tells whether the corresponding pixel belongs to the object to the background
227
231 (1 or -1, respectively). The corresponding posterior distribution hidden state x given an observed
image is defined as follows:
pxx) exp Σ 044 A
Σ و ((d)E
233 where a; = /////02 2 is a coefficient biasing I; towards either or 11 Therefore, a = (ax)eev contains information about the observed image. Figure Jshows two synthetically generated examples
235 of a Our goal is to analyze the sampling performance on the distribution defined in Eq. 7
236
Universally optimal balancing function. We start by comparing the balancing functions proposed
237
in 28 namely g(t) = t/(1+t) (a.k.a Barker function), VF. min (1, t} and max,1, t}. in order to test
For example by considering transformations that are bijective and/or by proposing transformations which allow tractably compute the marginal distribution on the continuous domain.

---

Autroenniiii fintion
db
(2)
<2
AR1EL11 17
Harfor Chall
Cartor
Vanco Crac
Vanco
(a) Independent (burn-in) (b) Dependent (burn-in) (c) Independent (mixing) (d) Dependent (mixing)
Figure 2: Samplers' performance on noisy and clean cases of the Ising model (30 x 30), (a)-(b) are the traceplots for the burn-in phase, (c)-(d) are the autocorrelation functions for the mixing onc.
Table I: Quantitative performance for mixing measured by effective sample size on the noisy and clean cases of the Ising model (30 30). max 1, () is performing significantly worse in statistical terms than the other functions.
Setting
Vi
min
max (1,4)
Noisy
2.48 + 0.21
2.30 + 0.22
2.42 0.19
1.75 + 0.17
Clean
2.58 + 0.73
1.99 + 0.43
2.56 + 0.62
1.26 = 0.12
238
whether there is a universally optimal balancing function among this subset. In particular, we run the samplers over two instances of the Ising model, viz. a setting with independent (A, ju, o) (0, 1,3)
240
and another one with dependent (A, 14, 0) = 1,,1,3) variables. We evaluate the performance over 30 repeated trials by analyzing the convergence speed during the burn-in phase (using traceplots) and the mixing time (computing the autocorrelation function and the effective sample size). We visualize
242
243
the corresponding results in Figure 2 and report the quantitative performance in Table [ Further details about the simulations are available in the Supplementary Material.
244
By comparing the performance of convergence speed and mixing time in Figure we observe that unbounded functions, like max 1) and vl, tend to converge faster while having slower mixing compared to the other two functions, thus being in line with the empirical findings of [28]. This is due
246
247
248
to the fact that unbounded functions have an intrinsic preference for visiting more likely regions at the cost of reduced amount of exploration. Moving a step further, we compare Figure 2a and Figure 2b and observe that the optimal function is different for the two cases (i.e. max (1, { in the independent case and vi in the dependent one). These results suggest that optimality not only depends on the performance of burn-in and mixing but also on the distribution we are sampling from. This allows us to reject the hypothesis about the existence of universal optimum among the pool of balancing functions proposed in (28) and to motivate our next set of experiments, where the aim is to lcarn to adapt the balancing function to the target distribution.
249
252
254
255
256 L Learning the balancing function. We compare the four balancing functions used in the previous set of experiments with our two parametrizations on four different settings of the Ising model, namely independent and noisy (A, f4, o) = (0, 1, 3). independent and clean (A, μ. σ)) = (0, 3, 3), dependent and noisy (A, μ, o) = (1, 1, 3) and dependent and clean (X, μ4 o) (1, cases and show the
257
258
259
280
corresponding performance in Figure 3 and Table 2
We leave additional details and results to the
Supplementary Material.
261
Twvelr
Twa yi
majls]
L99
(a) Case
(b) Case (c) Case 3
(d) Casc 4
Figure 3: Samplers' performance on four cases of the Ising model (30 x 30) for the burn-in phase.
(a) Case 1: Independent-noisy. (b) case 2: Independent-clean, (c) case 3: Dependent-noisy, (d) case
Dependent-clean
7

---

Table Quantitative performance for mixing measured by effective sample size on the four cases of the Ising model (30 x 30). max 1, t is performing significantly worse in statistical terms than the other functions.
Setting
VE
min
max 1, t]
LSB
LSB
1+f
Case
2,48 + 0.21
2.30 + 0.22
2.42 + 0.19
1.75 = 0.17
2.50 + 0.28
2.46 + 0.28
Case 2
3.33 + 0.32
2.94
3.33 - 0.33
1.72 = 0.18
2.98 0.24
3.33 + 0.43
Case 3
2.58 + 0.73
0.43
2.56 0.62
1.26 = 0.12
2.67 + 0.84
Case 4
9.2
18.5 6.8
31.8 10.0
2.60 = 1.46
18.4
30.8 + 9.2
rea(i.))
198
LS82
mastLIS
(a) Case 3
(b) Case 4
Figure 4: Realizations obtained after 500 (Case 3) and 300 (Case 4) burn-in iterations the Ising model.
262
From Figure we can see that our first parametrization LSB is able to always "select" an unbounded balancing function during burn-in, while when approaching convergence is able to adapt to preserve fast mixing, as measured by the effective sample size Table It's interesting to mention also that the softmax nonlinearity used in LSB I can sometimes slow down the adaptation due to vanishing gradients. This can be observed by looking at the case of Figure 3 where for a large part of the
264
286
burn-in period the strategy prefers max (1, {) over vi. Nevertheless, is still able to recover solution different from max (1, 1) at the end of burn-in, as confirmed by the larger effective sample size in Table 2 compared to the one achieved by ma
267
289
270
Furthermore, we observe that our second parametrization LSB 2, which is functionally more expres- sive compared LSB 1, allows to outperform all previous cases in terms of convergence speed, while preserving optimal mixing, as shown in Figure and Table This provides further evidence that the optimality of the balancing function influenced by the target distribution and that exploiting such information can dramatically boost the sampling performance (e.g. in case 3 of Figure LSB
271
272
273
274
converges twice time faster as the best balancing function Vt). Figure 4 provides some realizations obtained by the samplers for the cases with dependent variables À I. We clearly see from these
275
278
277
pictures that convergence for LSB 2 occurs at an earlier stage than the other balancing functions and
278
therefore the latent variables in the Ising model converge faster their ground truth configuration.
Torglr
Twa
majls]
L89
(a) BN (burn-in)
BN (burn-in)
(c) BN (mixing)
(d) BN (mixing)
Figure 5: Samplers' performance on Bayesian networks from UAI competition (100 variables). (a)-(b) are the traceplots for the burn-in phase, (c)-(d) are the autocorrelation functions for the mixing one.

---

Table 3: Quantitative performance for mixing measured by effective sample size on two Bayesian networks from UAI competition.
Dataset
Vt
1,4)
max
LSB 1
LSB 2
BN
2.90 - 0.76
3.41 + 0.77
2.54 = 0.32
2.70 + 0.63
3.19 - 0.46
3.22 + 0.38
BN 2
3.43 = 0.75
3.92 + 0.94
3.78 = 0.50
3.63 + 0.67
3.52 = 0.42
3.44 = 0.44
279
5.2
Bayesian Networks: UAT data
We evaluate how strategy generalizes different graph topologies compared the one of the Ising model. In particular, we consider two Bayesian networks, with 100 discrete variables each and near-deterministic dependencies, from the 2006 UAI competition Similarly to the previous experiments for the Ising model, we measure the performance over 5 repeated trials by analyzing the convergence speed during the burn-in phase (using traceplots) and the mixing time (computing the autocorrelaion function and the effective sample size). Further details about the simulations are available in the Supplementary Material.
281
282
283
284
285
286
287
We observe that the proposed strategy is able to adapt to the target distribution, thus achieving fast convergence (Figure 5)) while preserving fast mixing (both Figure and Table 3) compared to existing
289
balancing functions.
Conclusion
290
291
We have presented a strategy to learn locally informed proposals for MCMC discrete spaces. The strategy consists of (i) new parametrization of balancing functions and (ii) a learning procedure adapting the proposal to the target distribution, in order to improve the sampling performance, both in terms of convergence speed and mixing.
292
293
295
Note that the LSB sampler belongs the family of local sampling strategies, thus inheriting their limitations. The locality assumption can be quite restrictive, for example when sampling from discrete distributions with deterministic dependencies among variables. In such situations. local sampling
296
297
298
might fail to correctly sample from the target in a finite amount of time, as being required to cross regions with zero probability mass. This remains an open challenge to be investigated in future work.
299
300
It's important to mention that this work is foundational and general. The proposed strategy reduces the amount of user intervention and improves the sampling efficiency. However, these results could have potential impacts on society. At first glance, one could argue that the automation of the sampling procedure could have negative impact on society as reducing the amount of human labour required
302
303
304
to run the sampling strategy. However, we think that the benefits are of far greater number compared
305
to the negative aspects. In fact, the procedure reduces the costs of domain knowledge, with the
308
advantage of democratizing the sampling strategy and reducing suboptimal configurations of the algorithm resulting from possibly wrong human decisions. Furthermore, the proposed strategy introduces a small amount of additional computation, which is used to reduce the amount of queries to the target distribution, thus improving the query and the sampling efficiency. We think that this last aspect could contribute positively towards devising more energy-efficien algorithms and therefore being more environment friendly.
307
308
309
310
311
312 References
313 [1] H. Mohasel Afshar, Domke, et al. Reflection, Refraction, and Hamiltonian Monte Carlo. In NeurlPS, pages 3007-3015, 2015.
[2] N. Alexeev, J. Isomurodov, V. Sukhov, G. Korotkevich, and A. Sergushichev. Markov Chain Monte Carlo for Active Module Identification Problem. BMC Bioinformatics, 21(6): 2020.
316
317
[3] G. Altekar, S. Dwarkadas, J. P. Huelsenbeck, and F. Ronquist. Parallel Metropolis Coupled Markov Chain Monte Carlo for Bayesian Phylogenetic Inference. Bioinformatics, 20(3):407- 415, 2004.
318
http://sli.. ics. uci www//

---

320
[4] C. Andrieu, N. De Freitas, A. Doucet, and M. I. Jordan. An Introduction to MCMC for Machine Learning. Machine learning. 50(1):5 2003.
321
322
[5] C. Andrieu and J. Thoms. Tutorial on Adaptive MCMC. Statistics and Computing, 18(4):343 373, 2008.
323
324
[6] V. Dinh, A. Bilge, C. Zhang, and Frederick A. Matsen I. V. Probabilistic Path Hamiltonian Monte Carlo. In ICML, pages 1009-1018, 2017.
325
326
[7] Duane, A. D. Kennedy,
Pendleton, and Roweth. Hybrid Monte Carlo. Physics letters
B. 195(2):21--222, 1987.
[8] W. Gong, Y. Li, and J. M. Hernández-Lobato. Meta-Learning for Stochastic Gradient MCMC. ICLR, 2019.
329
330 (9] U. Grenander and M. I. Miller. Representations of Knowledge in Complex Systems. Journal of the Royal Statistical Society: Series B (Methodological), 56(4):549-581, 1994.
[10] R. Habib and D. Barber. Auxiliary Variational MCMC. In ICLR, 2018.
[1]] C. Hans, A. Dobra, and M. West. Shotgun Stochastic Search for "Large P" Regression. Journal of the American Statistical Association, 102(478):507-516, 2007.
334
335
[12] D. M. Higdon. Auxiliary Variable Methods for Markov Chain Monte Carlo with Applications. Journal of the American statistical Association, 93(442):585-553 1998.
[13] M. D. Hoffman and A. Gelman. The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res., 15(():1593-163, 2014.
338
339
[14] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT press, 2009.
340
[15] D. Levy, Matt D. H., and J. Sohl-Dickstein. Generalizing Hamiltonian Monte Carlo with Neural Networks. In ICLR, 2018.
342
343
[16] D. J.C.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge university press, 2003.
345
[17] R. Neal. Probabilistic Inference Using Markov Chain Monte Carlo Methods. Department of Computer Science, University of Toronto Toronto, Ontario, Canada, 1993.
346
347
[18] E. Nijkamp, M. Hill, T. Han, S. C. Zhu, and Y. N. Wu. On the Anatomy of MCMC-Based
348
Maximum Likelihood Learning of Energy-Based Models. In AAAI, pages 5272-5280, 2020.
3/9
[19] A. Nishimura, D. B. Dunson, and J. Lu. Discontinuous Hamiltonian Monte Carlo for Discrete
350
Parameters and Discontinuous Likelihoods. Biometrika, 107(2):365-380, 2020.
351
[20] A. Pakman and L. Paninski. Auxiliary-Variable Variable Exact Hamiltonian Monte Carlo Samplers for Binary Distributions. In NeurIPS, 2013.
352
353
[21] C. Pasarica and A. Gelman. Adaptively Scaling the Metropolis Algorithm Using Expected Squared Jumped Distance. Statistica Sinica, pages 343-364, 2010.
354
355
[22] Pompe, E. and Holmes, C. and Latuszyáski, K. and others. A Framework for Adaptive MCMC Targeting Multimodal Distributions. Annals of Statistics, 48(5):2930-29) 2952, 2020.
356
357
[23] C. Robert and Casella. Monte Carlo Statistical Methods. Springer Science Business Media, 2013.
[24] J. Sill. Monotonic Networks. In NeurlPS, pages 661-667, 1997.
360
[25] J. Song, S. Zhao, and S. Ermon. A-NICE-MC: Adversarial Training for MCMC. In NeurIPS,
361
2017.
362
[26] M. K. Titsias and C. Yau. The Hamming Ball Sampler. Journal of the American Statistical Association, 1 159850)) 2017. 2017.
10

---

384
[27] T. Wang. Y. Wu, D. A. Moore, and S. J. Russell. Meta-Learning MCMC Proposals. In NeurlPS, pages 4150 41600 2018.
385
386
[28] G. Zanella. Informed Proposals for Local MCMC in Discrete Spaces. Journal of the American Statistical Association, 115(530)852-8866) 2020.
367
388
[29] Y. Zhang, Z. Ghahramani, A. J. Storkey, and C. Sutton. Continuous Relaxations for Discrete Hamiltonian Monte Carlo. NeurIPS, 15:3194-3202 2012.
389
370
[30] M. Zhu. Sample Adaptive MCMC. In NeurlPS, volume 32, 2019.
Checklist
371
372
1. For all authors...
373
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
375
(b) Did you describe the limitations of your work? [Yes] We included a paragraph in the conclusions (Section 66) discussing the main limitations of our strategy.
376
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We included a paragraph in the conclusions (Section 6 discussing both pros and cons of the proposed work from the societal perspective.
378
380
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
382
2. If you are including theoretical results...
383
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please check the three propositions in Section 3
384
385
(b) Did you include complete proof' of all theoretical results? [Yes] Proofs are shown in the main paper in Section 3
386
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] Code and instructions to replicate the experiments in the paper are available in the Supplementary Material.
389
391
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The Supplementary Material provide all details about the experiments. Furthermore, we are sharing the scripts to run all experiments.
383
394
385
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
396
(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] At the beginning of Section S we have described the resources used to run the experiments.
398
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] The only external asset used in this work is the UAI benchmark data, which is publicly available at http://sli: ics uci. source of the data in the main paper.
402
We have explicitly mentioned the
404
405
(b) Did you mention the license of the assets? [Yes] UAI data is freely accessible online without any explicit license, that means that copyright law applies in this case. We will not share the data, but only the source code and include a README file with a pointer to the main website and credit the main author.
406
407
408
409
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We have included the URL of the UAI dataset in the main paper.
410
411
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] See answer (b).

---

418
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] This doesn't t apply to UAI data.
414
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
417
418
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
419
420
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "ic8GFHq0oY", "reviewer": "Reviewer_PwEa", "summary": "The paper built on top of the work \"Informed proposals for local MCMC in discrete spaces\" Giacomo Zanella. Author propose to learn the balancing function by optimising mutual information objective between $KL[p(x)T(x'|x) | p(x)p(x')]$.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Minor comments\n\nL 63 Formal definition of $N(x)$ is missed, I used from  Zanella.\nL 71 It is not clear why only acceptance rate important \nL 101 In proposition 1 maybe it will be interesting to discuss mixture of balancing functions vs. mixture of transitional kernels with corresponding balancing functions.\n\nGeneral\n\nIn Proposition 2 general form of balancing function $\\min \\left[h(t), t h( \\frac{1}{t} )\\right]$ was proposed in Zanella. So, contribution in parametrization h with DNN, which is also interesting. Then the crucial question, in my opinion, is the selection of the optimization criterion. This however discussed very briefly in 3.2 In L 144 motivation is not clear \"Note that the ideal case would be to sample from $p$ independently\", given the fixed neighbourhood of $N(x)$ (see also arXiv 1810.07151, arXiv 1711.09268 as examples of discussion about loss for transition kernel learning). Moreover, given the fixed neighbourhood of $N(x)$, I don't understand L 158 $T(x'|x) = p(x')$. ?!\nDespite that I can guess the overall reason for the objective: the balancing function should incorporate global information about the target density. I suppose the choice of the loss should be discussed more. \n\nThe next paper is discussed universally optimal balancing functions. First, I don't understand (and paper don't provide) any intuition of existing such thing. For continuous support, such function does not exist, what is different in discrete cases? Assuming that it exists, I also don't understand the selected functions to compare: I can provide infinitely many such functions in terms of hyperbolic functions. Maybe I miss the point.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitations to discuss.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns to discuss.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "cmu47d86FlH", "reviewer": "Reviewer_ueJZ", "summary": "This work proposed a strategy to learn locally informed proposals for MCMC in discrete spaces. In spirit, it is more or less similar to the multiple-try Metropolis method proposed in Liu et al. (2001), and it is unclear whether the new method is more efficient than the multiple-try Metropolis method. \n\nLiu, J. S., Liang, F. and Wong, W. H. (2000). The multiple-try method and local optimization in Metropolis sampling, Journal of the American Statistical Association, 95(449): 121–134. ", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This work presents a new parametrization for learning locally balanced proposals, and it is basically can be viewed as  a supplementary material of the recent work Zanella (2020). \n\n] G. Zanella. Informed Proposals for Local MCMC in Discrete Spaces.  Journal of the American Statistical Association, 115(530):852–865, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable ", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "OWWJREl-Z0M", "reviewer": "Reviewer_2Vii", "summary": "The paper address the problem of sampling in discrete spaces by learning proposal distributions that could potentially lead to faster convergence. The paper primarily builds on the original idea by G.Zanella, 2020 where the idea of locally balanced proposals was first proposed. The authors in this work aim to learn these proposals for \"better\" sampling in discrete spaces. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Positives:** The paper is well written and easy to follow. Sampling in discrete spaces is a challenging problem and the paper proposed a nice solution to learn proposal distributions for this. As discussed in the paper, the idea address to a large extent the limitations of previous works of Afshar and Domke, 2015, Pakman and Paninski 2013, Nishimura et.al 2020 etc. \n\n**Limitations and Questions:** \n\n1) **Prior work:** The authors missed two recent work on sampling in discrete spaces that also learn proposal distributions namely \"Sampling in Combinatorial Spaces using SurVAE Flow Augmented MCMC\" by Jaini et.al 2021 where the authors use normalizing flows to learn a transformation to transform the discrete distribution to a \"easy to sample\" continuous distribution. This is in-line with the other work on sampling in discrete spaces by using continuous relaxations but the paper also address the drawbacks of the previous works as mentioned by the authors and \"Oops I Took A Gradient: Scalable Sampling for Discrete Distributions\" by Gratwohl et.al 2021 where the authors also use the idea of locally balanced proposals for scalable sampling in discrete spaces. I believe at the very least these papers need to discussed as they are directly relevant to the problem and solution the authors propose. Finally, the idea of learning proposal distributions (atleast in continuous spaces) has been explored in a lot of detail by [Marzouk and Spantini] and [Hoffman et.al 2019, Neutralizing bad geometry in HMC using Neural transport] which I believe is also relevant to this work and warrants a discussion.\n\n2) **Use of Universal Approximation to build locally balanced proposals:** The authors appeal to the universal approximation result to construct the family of proposals named LSB 2. While, theoretically, this affords advantages to the LSB 2 sampler,  the approximation results necessarily requires an infinite capacity network for such guarantees.  In practice, since finite capacity networks are used for function approximation (and thus the resultant locally balanced proposals) this would incur some error since the approximation will never be exact. I wonder if the sampler suffers due to this error and if the resultant proposal is still locally balanced. Put another way, since h_{\\theta} is of limited capacity in practice, it approximated a locally balanced proposal function g within some error epsilon. Does this error break the properties of locally-balanced proposals and does all the theoretical advantages still hold? What are the implications of this error on the sampler (eq 2. in particular).\n\n3) **Experiments:** I believe the paper will benefit greatly from a more detailed experimental evaluation that involves comparisons to other methods. Specifically, I believe that apart from the present experiments where the comparison is mostly made wrt other locally balanced proposals, the authors should also compare to other samplers including discrete MCMC (random-walk), Gibbs sampling, discrete HMC (Nishimura et.al, code is available publicly), SurVAE+MH (Jaini et.al, code is public), and Gratwohl et.al (code is public) to back up claims of faster convergence and better performance. I also think that it will be interesting to see how this idea of learning locally balanced proposals work in higher dimensional problems eg. Ising model for denoising MNIST, or quantized bayesian neural nets.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the societal impact is adequately discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "I6IPtOFRnkW", "reviewer": "Reviewer_j21t", "summary": "This paper improves upon a recently proposed MCMC method ([Zanella. JASA 2020], cited as [28] in the paper) and considers optimizing the choice of balancing function in that method. A collection of rigorous techniques are proposed so that the balancing function can be represented by a neural network, and the network is trained by minimizing a heuristic objective (two possibilities are provided), which seems to be an approximation of the KL divergence from a Metropolis-Hasting proposal to the target distribution. Limited empirical evidence of effectiveness is provided.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The method is new and interesting. I especially like results in Section 3.1, which are smart and innovative. Overall, I feel the idea has a lot of potential and deserves a better demonstration, both theoretically and experimentally. More precisely, if I understood correctly, the goal is to accelerate the convergence of Metropolis-Hasting-type MCMC algorithms. Ideally, some theoretical analysis should be provided to quantitative establish an improved convergence speed, which is not the same as showing detailed balance (which is rather standard for Metropolis-Hasting) or ergodicity (which is not quantitative and not hard for finite state space Markov chains). However, I understand that this kind of analysis is typically highly nontrivial, and therefore empirical demonstration is also a possibility. In this case, some convincing numerical experiments with comparison to SOTA methods should be designed and provided. Such comparisons are currently missing, except one that compares against [28], which this work aims at improving. How much improvement over [28] was obtained was not very clear either; for example, I wonder whether Table 2,3 imply significant improvement or marginal ones. At the same time, can effective sample size be used to illustrate (improved) speed of convergence? I also don’t understand what `achieving fast convergence while preserving fast mixing’ means in Section 5.2, as one way to quantify convergence speed is through mixing time. More evidence of improved convergence speed will significantly strengthen the paper and illustrate the advantages of the new idea.\n\nSome additional comments are:\n\nNot all MCMC methods are based on proposals. Perhaps the authors were thinking about Metropolis-Hasting, which is just one class (albeit very important) of MCMC methods. Other classes include, for example, Gibbs sampler, (unadjusted-)LMC, etc. Not all references cited in the section of Related Work, however, seem to be Metropolis-Hasting based approaches.\n\nDo \"continuous domain\" and \"discrete domain\" mean continuous state-space and discrete state-space? It has been repeated that less effort has been devoted to the discrete counterpart (of MCMC), but in general finite state-space Markov processes (chains) are easier than the infinite ones (for example, if a finite chain is ergodic then it must be geometrically ergodic, but this is not true for continuous state space). It will be great if more clarification can be provided on what makes sampling from a finite set a challenging problem and why tools developed for general state-space are insufficient/inefficient.\n\nIs an indicator function $1[x’\\neq x]$ missing in front of the first term on the right hand side of equation(1)?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3YywFvWdskw", "reviewer": "Reviewer_ufwd", "summary": "The authors propose a method to adapt the MCMC proposal to the discrete distribution of interest. The parametric proposal is constructed to be locally balanced, and the parameters are learned by maximizing a mutual information-based objective.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is well-written and I did not have problems following the exposition.\n\nThe main idea of the paper is largely based on previous work by Zanella [1] on locally-balanced proposals for MCMC on discrete distributions. Rather than hardcoding such a proposal, the authors propose learning a parametric form either as a linear combination of known proposals or as a (monotonic) neural network. The setup of the optimization problem in eq. (3) to learn these parametric proposal could have been better motivated in the paper. More importantly, the transition from eq. (3) to eq. (6), which is the actual objective optimized, seems rather heuristic and not fully explained. Is there an intuitive reason why it may not be a problem to completely discard the expectation over $p$ in eq. (3)?\n\nThe experiments on some small-scale Ising models and on UAI Bayes nets show that the proposed methods seems to be comparable or faster in terms of burn-in and mixing. However, the authors do not show plots comparing the actual (wall-clock) time of the different sampling methods. The original paper by Zanella [1] already comments on the fact that locally-balanced proposals incur computational overhead (e.g., in comparison to a M-H sampler), and I assume that the steps in algorithm 1 for computing and optimizing the objective $J$ increase this overhead. As a result, it is hard to judge whether the proposed method is actually superior in practice.\n\nFurthermore, at least for the Ising model simulations, the authors could compare to a recently proposed method by Grathwolh et al. [2], which use gradient-based local information in the proposal.\n\nOther comments:\n* The plots in Fig. 2, 3, and 5 are too small and hard to read.\n* It is not explained what exactly the summary statistics are in the plots that evaluate the burn-in.\n\n&nbsp;\n### References\n\n[1] Zanella. Informed proposals for local MCMC in discrete spaces. J. Am. Stat. Assoc. '20.\\\n[2] Grathwohl et al. Oops I Took A Gradient: Scalable Sampling for Discrete Distributions. ICML '21.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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

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

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

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

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

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

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

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

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