Gradient-Guided Importance Sampling for Learning Binary Energy-Based Models
Authors: Meng Liu
Haoran Liu
Shuiwang Ji
Venue: ICLR 2023 poster (2023)

Abstract: Learning energy-based models (EBMs) is known to be difficult especially on discrete data where gradient-based learning strategies cannot be applied directly. Although ratio matching is a sound method to learn discrete EBMs, it suffers from expensive computation and excessive memory requirements, thereby resulting in difficulties in learning EBMs on high-dimensional data. Motivated by these limitations, in this study, we propose ratio matching with gradient-guided importance sampling (RMwGGIS). Particularly, we use the gradient of the energy function w.r.t. the discrete data space to approximately construct the provably optimal proposal distribution, which is subsequently used by importance sampling to efficiently estimate the original ratio matching objective. We perform experiments on density modeling over synthetic discrete data, graph generation, and training Ising models to evaluate our proposed method. The experimental results demonstrate that our method can significantly alleviate the limitations of ratio matching, perform more effectively in practice, and scale to high-dimensional problems. Our implementation is available at https://github.com/divelab/RMwGGIS.

Published as a conference paper at ICLR 2023
GRADIENT-GUIDED IMPORTANCE SAMPLING FOR LEARNING BINARY ANERGY-BASED MODELS
Meng Liu, Haoran Liu, Shuiwang Ji
Department of Computer Science Engincering Texas A&M University
College Station, TX 77843, USA
mmengliu, 1iuhr99, fji] @tamu. edu
ABSTRACT
Learning energy-based models (EBMs) is known to be difficult especially on discrete data where gradient-basee learning strategies cannot be applied directly. Although ratio matching is a sound method to learn discrete EBMs, suffers from expensive computation and excessive memory requirements, thereby resulting in difficulties learning EBMs on high-dimensional data. Motivated by these limita- tions, in this study, we propose ratio matching with gradient-guided importance sampling (RMwGGIS). Particularly, we use the gradient of the energy function w.e. the discrete data space approximately construct the provably optimal proposal distribution, which is subsequently used by importance sampling to efficiently estimate the original ratio matching objective. We perform experiments on den- sity modeling over synthetic discrete data, graph generation, and training Ising models to evaluate our proposed method. The experimental results demonstrate that our method can significantly alleviate the limitations of ratio matching, per- form more effectively in practice, and scale to high-dimensional problems. Our implementation is available at htttt:://// //gi thub. com dison/iivllll RM0///MWGGSS
INTRODUCTION
Energy-Based models (EBMs), also known unnormalized prohabilistic models, model distribu- tions by associating unnormalized probability densities. Such methods have been developed for
decades (Hopfield) 1982] Ackley et al., 1985. Cipra 1987 Dayan et al., 1995 Zhu et al. 1998 Hinton 2012) and are unified as energy-based models (EBMs) (LeCun et al. 2006 in the machine learning community. EBMs have great simplicity and flexibility since energy functions are not required to integrate or sum to one, thus enabling the usage of various energy functions. In practice, given different data types, we can parameterize the energy function with different neural networks as needed, such as multi-layer perceptrons (MLPs), convolutional neural networks (CNNs) (LeCun et al.) 1998), and graph neural networks (GNNs) (Gori et al. 2005 (Scarselli al. 2008). Recently, EBMs have been drawing increasing attention and are demonstrated to be effective in various domains, | 2016
including images (Ngiam et 2011 Xie et al.
Du Mordatch 2019). videos (Xic al.
2017). texts (Deng et al. 2020). 3D objects (Xie et al. 2018). molecules (Liu et al. 2021 Hataya
al. 2021. and proteins (Du et al. 2020b).
Nonetheless, learning (a.k.a., training) EBMs is known to be challenging since we cannot compute the exact likelihood due to the intractable normalization constant. As reviewed in Section 4 many approaches have been proposed to learn EBMs, such as maximum likelihood training with MCMC sampling (Hinton, (2022) and score matching (Hyvärinen Dayan 2005). However, most recent advanced methods cannot be applied discrete data directly since they usually leverage gradients over the continuous data space. For example, for many methods based on maximum likelihood training with MCMC sampling, they the gradient
the data space update samples in each MCMC step. However, we update discrete samples using such gradient, the resulting samples are usually invalid in the discrete space. Therefore, learning EBMs discrete data remains challenging.
Ratio matching (Hyvärinen) 2007) is a method to learn discrete EBMs on binary data by matching ratios of probabilities between the data distribution and the model distribution, detailed in Sec-

---

Published as a conference paper at ICLR 2023
tion 2.2 However, as analyzed in Section 3.1 it requires expensive computations and excessive memory usages, which is infeasible if the data is high- high-dimensional.
In this work, we propose to the gradient of the energy function w.z.f the discrete data space to guide the importance sampling for estimating the original ratio matching objective. More specifically, such gradient to approximately construct the provably optimal proposal distribution for importance sampling. Thus, the proposed approach termed as ratio matching with gradient-guide importance sampling (RMwGGIS). Our RMWGGIS can significantly overcome the limitations of ratio matching. In addition, it is demonstrated to be more effective than the original ratio matching in practice. We perform extensive analysis for this improvement by connecting with hard negative mining, and further propose an advanced version of RMwGGIS accordingly by reconsidering the importance weights. Experimental results on synthetic discrete data, graph generation, and Ising model training demonstrate that our RMwGGIS significantly alleviates the limitations of ratio matching, achieves better performance with obvious margins, and has the ability of scaling to high-dimensional relevant problems.
2 PRELIMINARIES
2.1
ENERGY-BASER MODELS
Let æ be a data point and (xr) E IR be the corresponding energy, where 0 represents the learnable parameters of the parameterized energy function E-(-). The probability density function of the model
distribution is given as po c α e Fm(m), where Zo E IR is the normalization constant ka.k.a., partition function). To be specific, Ze = f Ex(z) dx if æ is in the continuous space and Zo Σe e Es (ar) for discrete data. Hence, computing Zo is usually infeasible due to the intractable integral summation. Note that Zo is variable depending on but constant w.r.l. œ.
2.2 RATIO MATCHING
Ratio matching (Hyvärinen 2007) is developed for learning EBMs binary discrete data by matching ratios of probabilities between the data distribution and the model distribution. Note that we focus d-dimensional binary discrete data E {0, 1 in this work.
Specifically, ratio matching considers the ratio of p(x) and p(x-:). where ._, (I1, 22, F,, ..,,.., ,.a) denotes point in the data space obtained by flipping the i-th dimen- sion of æ. The key idea is to force the ratios _r(=)) defined by the model distribution pe to be as po(==-)
close as possible to the ratios Pp(a)
p=(a-.) given by the data distribution pp. The benefit of considering
ratios of probabilities is that they do not involve the intractable normalization constant Ze since
(m))
= = Eo(ss.))oo(a)) To achieve the match between ratios, Hyvärinen
Zo
2007
proposes to minimize the objective function
pol(n) po(( (p)
1 }=+ + ++ [D (PD(ar_)) pD(
pro (o( po (z)
Jaar = Ex-pp(a) (x)
Σ
The sum of two square distances with the role of x and w-; switched is specifically designed since it essential for the following simplification. In addition, the function g(u) = I+a is also carefully chosen in order to obtain the subsequent simplification. To compute the objective defined in Eq. ( it is known that the expectation over data distribution (i.e., (w)))(()) can be unbiasedly estimated by the empirical mean of samples æ pp(x). However, to obtain the ratios between PD (x:) and (=(=.)) in Eq. (I) the exact data distribution is required be known, which is usually impossible.
Fortunately, thanks to the above carefully designed objective, |Hyvärinen (2007) demostrates that the objective function in Fq. (T) is equivalent to the following simplified version
d
pe (z) Pe vo(x=,))
)
TRAS (0) = Emppp (at)
Σ
(2)
2

---

Published as a conference paper at ICLR 2023
which does not require the data distribution to be known and can be easily computed by evaluating the energy of x and w-1, according to _ - Further, Lyu 2009) shows that the above objective function of ratio matching agree with the following objective
Pe( +)
po po (x)_
JRM( = Propppp (az)
E Bap papppaa -a(())-o((a-)))
Po (x)
They agree with each other since function g(-) decreases monotonically in (0, +00), which aligns with the value range of probability ratios Pe
pa(w- Note that Eq. (3) is originally named as the discrete extension of generalized score matching in Lyu (209). Since it agrees with Eq. (2) and includes ratios of probabilities, we also treat as an objective function of ratio matching in our context. In
the rest of this paper, we provide our analysis and develop our method based on Eq. ( for clarity. Nonetheless, our proposed method below can be naturally performed on Eq. as well.
Intuitively, the objective function of ratio matching, as formulated in Eq. (3) Eq. (2) can push down the energy of the training sample æ and push up the energies of other data points obtained by flipping one dimension of Thus. this objective faithfully expect that each training sample has higher probability than its local neighboring points that are hamming distance from æ.
It is worth mentioning that ratio matching is not suitable for binary image data. This is because it faithfully treats æ as a positive sample and æ; for = 1, ... d as negative samples. However, this assumption does not hold for binary image data. Specifically, if we flip one dimension/pixel of binary image such as a digit image from MNIST, the resulting image is almost unchanged and is still a positive sample in nature. Thus, is not reasonable to use ratio matching train EBMs on binary images. Similarly, our RMwGGIS presented below also has this limitation. Having said this, our RMwGGIS still an effective and efficient method for a broad of binary discrete data. We leave extending its applicability to general discrete EBMs for future work.
3 THE PROPOSED METHOD
We first analyze the limitations of the ratio matching method from the perspective of computational time and memory usage. Then, we describe our proposed method, ratio matching with gradient- guided importance sampling (RMwGGIS), which uses the gradient of the energy function w.r.t. the discrete input to guide the importance sampling for estimating the original ratio matching objective. Our approach can alleviate the limitations significantly and shown to more effective in practice.
3.1 ANALYSIS OF RATIO MATCHING
Time-intensive computations. Based on Eq. 3 for a sample x, we have to compute the energies for all x-1. where = 1,.... .....,,,, ,d. This needs (dd) evaluations of the energy function for each training sample. This is computationally intensive, especially when the data dimension d is large.
Excessive memory usages. The memory usage of ratio matching is another limitation that cannot be ignored, especially when we learn the energy function using modern GPUs with limited memory. As shown in Eq. (3). the objective function consists of d terms for each training sample. When we do backpropagation, computing the gradient of the objective function w.r./ the learnable parameters of the energy function is required. Therefore, in order to compute such gradient, we have to store the whole computational graph and the intermediate tensors for all of the d terms, thereby leading to excessive memory usages especially if the data dimension d is large.
3.2 RATIO MATCHING WITH GRADIENT-GUIDER IMPORTANCE SAMPLING
The key idea is to use the well-known importance sampling technique reduce the variance of estimating JRM(08 with fewer than d terms. The most critical and challenging part of using the importance sampling technique is choosing good proposal distribution. In this work, propose to use the gradient of the energy function w.r.f. the discrete input æ to approximately construct the optimal proposal distribution for importance sampling. We describe the details of method below.
3

---

Published as a conference paper at ICLR 2023
The objective for each sample æ, defined by Eq. (3. can be reformulated
diC (ommm (o(())) Eo(m =))
(0,((0
(4)
where m((x-:) = for 1, d is discrete distribution. Thus, the objective of ratio matching
for each sample a can be viewed as the expectation of (e (" a) over the discrete distribution
m(x=1). In the original ratio matching method, as described in Section 2.2 we compute such expectation exactly by considering all possible æ-4, x. leading to expensive computations and excessive memory usages. Naturally, we can estimate the desired expectation with Monte Carlo method by considering fewer terms sampled based m(x=;). However, such estimation usually has high variance, and is empirically verified to be ineffective by our experiments in Section 5
Further, we apply the importance sampling method to reduce the variance of Monte Carlo estimation. Intuitively, certain values have more impact on the expectation than others. Hence, the estimator variance can be reduced if such important values sampled more frequently than others. To be specific, instead of sampling based on the distribution m(x importance sampling aims to sample from another distribution n))=;), namely, proposal distribution. Formally,
m(x==s) [o)) Eo 1)
e (o(a)) Eolæ .) =dEE pom(
JRA x)) = dE v-m
n n(
(5)
short derivation of Eq. (5) is in Appendix A Afterwards, we can apply Monte Carlo estimation
based on the proposal distribution n(x=,). Specifically, sample terms, denoted x (2)
x (x)
according to the proposal distribution n( Note that is usually chosen to be much smaller than Then the estimation for JRM (0, x) is computed based on these terms. Formally,
m(x Fe(m))-Fo(n
JRM (., x) = d
x n(x
(6)
n
To make clear, we stop the gradient flowing through the importance weights during back- propagation. It is known that the estimator obtained by Monte Carlo estimation with importance sampling an unbiased estimator, as the conventional Monte Carlo estimator. The key point of importance sampling is to choose appropriate proposal distribution n n(x=i), which determines the variance of the corresponding estimator. Based on Robert et al.] (1999), the optimal proposal distribution n² (x: which yields the minimum variance, given by the following fact.
[e Eo(m_.))2 Fact 1. Let n² (x=s) Ei (o w3j² be discrete distribution E- where
..... .d. Then for any discrete distribution n(xx:) on a- where = 1,... ,d. we have Var (0, 5 Var (O, x)....
Proof. The proof included Appendix
To construct the exact optimal proposal distribution n*(x=x), we still have evaluate the energies of all æ-1, where i = 1....... d. To avoid such complexity, we propose to leverage the gradient of the energy function w.n.t. the discrete input æ to approximately construct the optimal proposal distribution. Only (11) evaluations of the energy function is needed to construct the proposal distribution.
is observed by Grathwohl et al. (202T) that many discrete distributions are implemented as continu- ous and differentiable functions, although they are evaluated only in discrete domains, [rathwohl] ct al. (202I) further proposes a scalable sampling method for discrete distributions by using the gradients of the underlying continuous functions w.r.f. the discrete input. In this study, we extend this idea to improve ratio matching. More specifically, in our case, even though our input x is discrete, parameterized energy function Eo(-), such as a neural network, is usually continuous and differentiable. Hence, we can use such gradient information to efficiently and approximately construct the optimal proposal distribution given by Fact 1.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Ratio Matching with Gradient-Guider Importance Sampling (RMwGGIS)
1: Input: Observed dataset D = {x((m) PD]
m=1' parameterized energy function Eg (-), number of samples
8 for Monte Carlo estimation with importance sampling
2: for æ 'D do
> Batch training is applied in practice
3: Compute Ex(
4: Compute (z)
5: Compute the proposal distribution 7
Eq. 10P
6: Sample terms, denoted as æ (1) ---- according to ñi* (x-i)
7: Compute JAM (0, ))
Eq. 6 (or Eq.
8:
Update 0 based on VoJnm (0, x)a²-
9:
end for
The basic idea is that we can approximate Eo(x=)) based on the Taylor series of E-(-) at T. given that 2- close to x: in the data space because they only have differences in one dimensior Formally,
Eo(x_i) ze Eo(x) + (x -x=" V Eo)
Thus, can approximately obtain the desired term Es(x) (x in Fact 1 using Eq. (7). Note that Va Fo(a)) E Rd contains the information for approximating all Eo(x)) - Eo(x-i), where i= 1, d. Hence, consider the following d-dimensional vector
2xx 1) e (o)x
E R
(8)
if = 0 and where @ denotes the element wise multiplication. Note that we have Tj -
T; F. 1f n; 1, which can be unified as 2; I; 2x, 1. Therefore, we have
Eø(x) (x = [(2x 1) @ Eg
1..... .d.
Afterwards, we can provide a proposal distribution 7' (x=:) as an approximation of the optimal proposal distribution n² (x_i) given by Fact 1. Formally,
2222 1)3 aa
(x=
1. .d.
(10)
Then 7 (x=;) is used as the proposal distribution for Monte Carlo estimation with importance sampling, as in Eq. (6). The overall process of our RMwGGIS method is summarized in Algorithm
3.3 COMPARISON BETWEEN RATIO MATCHING AND RMWGGIS
Time and memory. Since only (s d) terms considered in the objective function of our RMwGGIS, as shown in Eq. (6). we have better computational efficiency and less memory requirement compared to the original ratio matching method. To be specific, our RMwGGIS only needs (s)) evaluations of the energy function compared with (dd) in ratio matching, leading to linear speedup, which significant especially when the data digediimesiional The improvement in terms of memory usage is similar. In Section 5.1 we compare the real running time and memory usage between ratio matching and our proposed RMwGGIS on datasets with different data dimensions.
Better optimization? In Section 3.2 we propose our RMwGGIS based on the motivation to approxi- mate the objective of ratio matching with fewer terms. Although our RMwGGIS can approximate the original ratio matching objective numerically, our objective only includes terms compared to terms in the original ratio matching objective. In other words, the objective of ratio matching, as shown in Eq. D intuitively pushes up the energies of all x for i 1.... d, while our RMwGGIS only considers pushing up energies of s terms among them, as formulated by Eq. (6) Thus, one may wonder why objective effective for learning EBMs without pushing up the energies of all d terms? In practice, we even observe that RMwGGIS achieves better density modeling performance
We have this assumption hecause data space is usually high-dimensional, If the number of data dimension is small, can simply the original ratio matching method since time and memory are affordable in this case.
5

---

Published as a conference paper at ICLR 2023
than ratio matching. We conjecture that this is because our RMwGGIS can lead to better optimization of Eq. (3) in practice for the following two properties, which are empirically verified in Section
(1) RMwGGIS introduces stochasticity. Without involving all d terms in the objective function, our method can introduce stochasticity, which could lead to better optimization in practice. This has the same philosophy the comparison between mini-batch gradient descent and vanilla gradient descent. The gradient is obtained based on each batch in mini-batch gradient descent, while is computed over the entire dataset in vanilla gradient descent. It is known that the mini-batch gradient descent usually performs better in practice since the stochasticity introduced by mini-batch training could help escape from the saddle points in non-convex optimization (Ge al., 2015). Therefore, the stochasticity introduced by sampling only terms in RMwGGIS might help the optimization especially when d large.
(2) RMwGGIS focuses on neighbors with low energies. Even though only energies of s terms are pushed up our method, these s terms correspond to the neighboring points that have low energies. According to n (x= given by Fact 1, neighbor of denoted as æ-i, is more likely to be sampled its corresponding energy value is lower 2 Hence, we choose to push up the energies according to their current energies. The lower the energy, the more likely it is to be selected. This is intuitively sound because the terms that have low energies are the most offending terms, which should have the higher priorities to be pushed up. In other words, neighbors with lower energies contribute more to the objective function according to Eq. 3 That is, the loss values for these neighbors larger. Thus, RMWGGIS has the same philosophy hard negative mining, which pays more attention to hard negative samples during training. More detailed explanation about this connection provided in Appendix C
neighbors
Following the hard negative mining perspective, we observe that the coefficients used in Eq. (6) provide smaller weights for terms with lower energies. In other words, among its selected offending terms (i.c.. hard negative samples), it pay least attention to the most offending terms, which is intuitively less effective. Therefore, we further propose the following advanced version as an objective function by removing the coefficients in Eq. (6). Formally.
JRM (0, x)..
adv
Σ (ole)
x 8 (x
(11)
This advanced version is essentially a heuristic extension of the basic version in Eq. (6) It is demonstrated to be more effective in practice. The explanation about this is discussed in Appendix D
4 RELATED WORKS
Learning EBMs has been drawing increasing attention recently. Maximum likelihood training with MCMC sampling, also known as contrastive divergence (Hinton 2002), is the most representative method. It contrasts samples from training set and samples from the model distribution. To draw samples from the model distribution, we can employ MCMC sampling approaches, such as Langevin dynamics (Welling& & Tch 2011) and Hamiltonian dynamics (Neal et al. 2011). Such methods are further improved and shown to be effective by recent studies (Xie et al. 2016 Gao et al., 2018 Du & Mordatch 2019 Nijkamp et al., 2019 Grathwohl et al.) 2019 Jacob et al. 2020: Qiu et al. 2019: Du et al. 2020a). These methods, however, require the gradient w.r.f. the data space to update samples in each MCMC step. Thus, they cannot be applied to discrete data directly. To enable maximum likelihood training with MCMC sampling on discrete data, we can naturally use discrete sampling methods, such as Gibbs sampling and Metropolis-Hastinggs algorithm (Zanella (200)), to replace the above gradient- based sampling algorithms. Unfortunately, sampling from discrete distribution extremely time-consumn consuminn and not scalable. Recently, DDa et al.) (2020) develops a learnable sampler parameterized as local discrete search algorithm to propose negative samples for contrasting. Grathwohl et al. (02T) proposes a scalable sampling method for discrete distributions by surprisingly using the gradient w.r.f. the data space, which inspires our work a lot.
An alternative method for learning EBMs is score matching (Hyvärinen & Dayan 2005 Vincent 2011 Song et al. 2020: Song & Ermon 2019), where the scores, i.e., the gradients of the logarithmic
Although this only strictly holds for n' (m- this can serve relaxed explanation for ni' (at(ar_)) :) well since n (2r is good approximation of (1) More detailed analysis is included in Appendix C

---

Published as a conference paper at ICLR 2023
Table I: Results on 32-dimensional synthetic discrete data in terms of MMD. The lower the better. The top two results on each dataset are highlighted as 1st and 2nd.
Method
2ppirals
8gaussions
circles
moons
piorkeel
swissroll
checkerboard
Ratio Matching
0.01514
0.10270
0.11856
0.02901
0.31353
0.05520
0.00059
RMwGGIS (basic)
0,01099
0.09763
0.11017
0,03111
0.27885
0,05176
0.00050
R.I (advanced)
0.00876
0.08414
0.10230
0.02787
0.26188
0.04477
0.00026
probability distribution w.F.t. the data space, of the energy function are forced to match the scores of the training data. Ratio matching (Hyvärinen 2007 Lyu 2009) is obtained by extending the idea of score matching to discrete data. Our work is motivated by the limitations of ratio matching, as analyzed in Section Stochastic ratio matching (Dauphin Bengio (013)) also aims to make ratio matching more efficient by considering the sparsity of input data. Stochastic ratio matching is limited to sparse data, while our method is effective for general EBMs
There are some other methods for learning EBMs, such noise contrastive estimation (Gutmann Hyvärinen] 2010; [Bose et al., 2018 Ceylan & Gutmann 2018 Gao et al.) (020) and learning the stein discrepancy (Grathwohl et al. 2020). We recommend readers to refer to Song & Kingma (202T) for a comprehensive introduction on learning EBMs. We note that several works (Elvira et al. 2015] (215)) use the gradient information of the target distribution to iteratively optimize the proposal distributions for adaptive importance sampling. However, compared to our method, they can only applied to continuous distributions and require expensive iterative processes.
5 EXPERIMENTS
5.1 DENSITY MODELING ON SYNTIETIC DISCRETE DATA
Setup. For both quantitative results and qualitative visualization, we follow the experimental setting of Dai et al. (2020) for density modeling on synthetic discrete data. We firstly draw 2D data points from 2D continuous space according to some unknown distribution P. which can be naturally visualized. Then, convert each 2D data point d E R22 discrete data point æ e {0, 13d, where d is the desired number of data dimensions. To be specific, we transform each dimension of æ. which is a floating-poin number, into a 4-bit Gray code and concatenate the results obtain a d-bit vector x. Thus, the unknown distribution in discrete space is p(æ)
á ( Gray/ooFloat g: ), GrayToFloat(2: (r))+ This density modeling task is challenging since the transformation from & to æ is non-linear.
To quantitatively evaluate the performance of density modeling, we adopt the maximum mean discrepancy (MMD) (Gretton et al. 2012) with linear kernel corresponding to (d-TtammingDistance to compare distributions. In our case, particularly, the MMD metric is computed based on 4000 samples, drawn from the learned energy function via Gibbs sampling, and the same number of samples from the training set. Lower MMD indicates that the distribution defined by the learned energy function is closer to the unknown data distribution. In addition, in order to qualitatively visualize the learned energy function, we firstly uniformly obtain 10k data points from 2D continuous space. Afterwards, they are converted into bit vectors and evaluated by the learned energy function. Subsequently, we can visualize the obtained corresponding energies in 2D space.
The energy function is parameterized by an MLP with the Swish (Ramachandran al. 2017) activation and 256 hidden dimensions. The number of samples s, involved in the objective functions of our RMWGGII method, is set to be 10. In the following,
compare our basic and advanced RMwGGIS methods, as formulated in Eq. (6) and Eq. (11) respectively, with the original ratio
matching method (Hyvärinen) 2007 Lyu 2009).
Quantitative and qualitative results. The quantitative results on 32-dimensional datasets are shown in Table [ Our RMwGGIS, including the basic and the advanced versions, consistently outperforms the original ratio matching by large margins, which demonstrates that it is effective for our proposed mandient-guided importance sampling to stochastically push up neighbors with low energies. This
httpss///en.... weeeenwwkiieee www.:niiiiiidii.rgg...... wiki /iki///ra_ccdde
7

---

Published as a conference paper at ICLR 2023
verifies analysis in Section 3.3 In Figure 1 we qualitatively visualize the learned energy functions of our proposed RMwGGIS. It is observed that EBMs learned by our method can fit the data distribution accurately. Note that we choose d' 32 for quantitative evaluation because Gibbs sampling cannot obtain appropriate samples from the learned energy function with an affordable time budget if the data dimension is too high, thus leading to invalid MMD results. We will compare the results on nigher-dimensiona data in the following by observing the qualitative visualization. To further demonstrate that the performance improvement of RMwGGIS over ratio matching brought by better optimization, we show that energy functions learned with our methods actually lead to lower value for the objective function defined by Eq. (3). The details are included in Appendix
Observations on higher-dimensional data. As analyzed in Section 3.3 the advantages of our approach can be greater on higher-dimensional data. To evaluate this, we conduct experiments on the 256-dimensional 2spirals dataset, and vi- sualize the learned energy functions correspond- ing to different learning iterations. We con- struct a ablation method, named as RMwRAND, which estimates the original ratio matching ob- jective by randomly sampling The only difference between our RMwGGIS method and RMWRAND is that we focus more on the terms corresponding to low energies, based on our proposed gradient-guided importance sampling.
Zeptrole Sggncxiions
circles
mouns
piewheed
owteroll
checkerboard
Data
RMwGGIS (basic)
RMwGGIS (advanced)
Figure Visualization of learned energy functions = 10 terms. on 32-dimensional synthetic discrete datasets.
As shown in Figure 4 Appendix F our RMwGGIS accurately captures the data distribution, while the original ratio matching method cannot. This further verifies that RMwGGIS leads to better optimiza- tion than ratio matching especially when the data dimension is high, as analyzed in Section [.3] In addition, although RMwRAND can also introduce stochasticity as RMwGGIS by randomly sampling, fails to capture the data distribution. This observation is intuitively reasonable since randomly push- ing up s = 10 terms among d 256 terms leads to large variance. Instead, our RMwGGIS performs well since we focus on pushing up terms with low energies, which are the most offending terms and should be pushed up first. Overall, these experiments can show the superiority of RMWGGIS endowed by our proposed maddient-guided importance sampling on high-dimensional data.
Selection of s. Note that we did not perform extensive tuning for 8, although tuning it might bring performance improve- ment. To further show the influence of and the effectiveness of RMWGGIS (advanced) over RMwRAND. We perform an experiment to train both models on 256-dimensional 2xpi- rals with s 5, 10, 50, 100. The visualization of the learned energy functions is shown in Figure 2 Our RMwGGIS is observed to achieve good density modeling performance that robust to the selection of s. In contrast, RMwRAND fails to capture the data distribution even with = 100. This further demonstrates the effectiveness and robustness of our proposed gradient-guided importance sampling strategy.
$=5
100
RMWRAND
RMwGGIS
Figure 2: Comparison of RMwG- GIS(advanced) and RMwRAND with several configurations of s.
Running time and memory usage. To verify RMwGGIS has better efficiency than ratio matching, we compare the real running time and memory usage on datasets of various dimensions. Specifically, we construct several 2spirals datasets with different data dimensions and train parameterized energy functions using ratio matching and our RMwGGIS, respectively. We choose batch size to be 256, The reported time corresponds to the average training time per batch. For RMwGGIS, report the results of the advanced version.
As summarized in Table Appendix G RMwGGIS is much more efficient in terms of running time and memory usage, compared to ratio matching. In addition, the improvement is more obvious with the increasing of data dimension. Specifically, compared with ratio matching, R.MGGII can achieve 6.2 times speedup and save 90.1% 5% memory usage on the 2048-dimensional dataset.
5.2 GRAPH GENERATION
Setup. We further evaluate our RMwGGIS on graph generation using the Ego-small dataset (You et al. 2018). It is set of one ego graphs, where the number of nodes < [V| S 18, obtained
8

---

Published as a conference paper at ICLR 2023
from the Citeseer network (Sen al. 2008). Following the experimental setting of You et al. (2018) and Liu et al. 2019), 80% of the graphs are used for training and the rest for testing. New graphs can be generated via Gibbs sampling on the learned energy function. To evaluate the graph generation performance based on the generated graphs and the test graphs, we calculate MMD over three statistics, i.e., degrees, clustering coefficients, and orbit counts, as proposed in You et al. (2018).
We parameterize the energy function by a 5-layer R- GCN (Schlichtkrull et al.] 2018) model with the Swish activation and 32 hidden dimensions, whose input is the up- per triangle of the graph adjacency matrix. The number of samples s used in our RMwGGIS objective is 50. We apply our advanced version to learn the energy function since it is more effective in Section 5.1 Besides ratio matching, we consider the recent proposed method EBM (GWG) (Grath- baseline. We also consider the
Table 2: Graph generation results in terms of MMD. Avg. denotes the av- erage over three MMD results.
Method
Degree
Cluster
Orbit
Aug.
GmphVAE DeeGGMG
0.130
0.050
0.030
0.100
0.020
0.053
GmphRNNN
0.090
0.220
0.003
0.104
GNF
0.030
0.100
0.001
0.044
EDP-GNN
0.052
0.083
0.007
0.050
wohl et al. 202[) recent works developed for graph generation as baselines, including Graph VAE (Simonovsky & Komodakis 2018).
GraphAF
0.030
0.110
0.001
0.047
GmphiDF
0.040
0.130
0.010
0.060
(GWG)
0.093
0.027
0.053
0.058
Ratio Matching
0.062
0.066
0.008
0.045
DeepGMG (Li et al. 2018). GraphRNN ( You et al. 2018).
RMwGGIS
0.044
0.050
0.013
0.039
GNF (Liu et al. 2019), EDP-GNN (Niu et al., 2020). GraphAF (Shi al. 2019), and GraphDF (uoo H
et al. 2021 The detailed setup is provided in Appendix
Quantitative and qualitative results. As summarized in Table 2 our RMwGGIS outperforms baselines in terms of the average over three MMD results. This shows that our method can learn EBMs generate graphs that align with various characteristics of the training graphs. The generated samples are visualized in Figure 5 Appendix[]] It can be observed that the generated samples are realistic one-hop ego graphs that have similar characteristics as the training samples.
5.3 TRAINING ISING MODELS
To further demonstrate the scaling ability of method and compare with recent baselines more thoroughly, use
Table 3: Comparison of training Ising models.
MUMC +Sieps
10
50
200
Rati Marching
RMWGGGS
lgg/MMSO
BBM (GBbbs)
2.50
3.00
-3.9
4.00
Timefka
EBM (GWG)
EBM (Gibbe)
262.
57.5ms
63.6m
5m.
1118.2m
100.ems
2524. 3nm
222.6m
4570 Jmn
205.
650
13.9ua
RMwGGIS to train the Ising model with a 2D cyclic lattice structure. following Grathwohl et al. (022I). We consider a 25 x 25 lattice, thus leading to a 625-dimension problem, which can be used to evaluate the ability of scaling to high-dimensional problems. We compare methods in terms of the RMSE between the inferred connectivity matrix J and the true J and the running time per iteration. The experimental details are included in Appendix [ As shown in Table 3 our RMWGGIS is more effective than ratio matching and EBM (Gibbs) with various sample steps. The recently proposed EBM (GWG) (Grathwohl et al. 202I) achieves better RMSE than ours. In terms of running time, our method is much more efficient than baselines since we avoid the expensive MCMC sampling during training and do not have to consider flipping all dimensions as ratio matching. According to this experiment, one future direction could be further improving the effectiveness of R.MGGGIS while preserving the efficiency advantage.
6 CONCLUSION
We propose ratio matching with gradient-guided importance sampling (RMwGGIS) for learning EBMs on binary discrete data. In particular, we use the gradient of the energy function w.e. the discrete input space to guide the importance sampling for estimating the original ratio matching objective. We further connect our method with hard negative mining, and obtain the advanced version of RMwGGIS. Compared to ratio matching, our RMwGGIS methods, including the basic and advanced versions, are more efficient in terms of computation and memory usage, and are shown to be more effective for density modeling. Extensive experiments on synthetic data density modeling. graph generation, and Ising model training demonstrate that our RMwGGIS achieves significant improvements over previous methods in terms of both effectiveness and efficiency.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported in part by National Science Foundation grant IIS-1908220
REFERENCES
David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A learning algorithm for boltzmann machines. Cognitive science, 9():1477-66, 1985.
Avishek Joey Bose, Huan Ling, and Yanshuai Cao. Adversarial contrastive estimation. In Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 1021-1032, 2018.
Ciwan Ceylan and Michael U Gutmann. Conditional noise-contrastive estimation of unnormalised models. In International Conference on Machine Learning, pp. 726-734. PMLR, 2018.
Barry A Cipra. An introduction to the ising model. The American Mathematical Monthly, 94(10): 937-959, 1987.
Hanjun Dai, Rishabh Singh, Bo Dai, Charles Sutton, and Dale Schuurmans. Learning discrete energy- based models via auxiliaryy-varrt variable local exploration. Advances in Neural Information Processing Systems, 13:10443-10455 2020.
Yann Dauphin and Yoshua Bengio. Stochastic ratio matching of rbms for sparse high-dimensional inputs. Advances in Neural Information Processing Systems, 26:1340-1348, 2013.
Peter Dayan, Geoffrey E Hinton, Radford M Neal, and Richard S Zemel. The helmholtz machine. Neural computation, 7(5):889-904, 1995.
Yuntian Deng, Anton Bakhtin, Myle Ott, Arthur Szlam, and Marc' Aurelio Ranzato. Residual energy-based models for text generation. In International Conference on Learning Representations, 2020.
Yilun Du and Igor Mordatch. Implicit generation and modeling with energy based models. In Advances in Neural Information Processing Systems, volume 32, pp. 3608-3618 2019.
Yilun Du, Shuang Li, Joshua Tenenbaum, and Igor Mordatch. Improved contrastive divergence training of energy based models. arXiv preprint arXiv:2012.01316. 2020a.
Yilun Du, Joshua Meier, Jerry Ma, Rob Fergus, and Alexander Rives. Energy-based models for atomic-resolution protein conformations. In International Conference Learning Representations, 2020b.
Victor Elvira, Luca Martino, David Luengo, and Jukka Corander. A gradient adaptive population importance sampler. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4075-4079. IEEE, 2015.
Pedro F Felzenszwalb, Ross B Girshick, David McAAlleter, and Deva Ramanan. Object detection with discriminatively trained bast- models. IEEE transactions on pattern analysis and machine intelligence, 32(9):6627-164) 2009.
Ruiqi Gao, Yang Lu, Junpei Zhou, Song-Chur Zhu, and Ying Nian Wu. Learning generative convnets via multi-grid modeling and sampling. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 9155-9164, 2018.
Ruiqi Gao, Erik Nijkamp, Diederik P Kingma, Zhen Xu, Andrew M Dai, and Ying Nian Wu. Flow contrastive estimation of energy-based models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattrnn Recognition, pp. 7518-7525 2020.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-oue online stochastic gradient for tensor decomposition. In Conference learning theory, pp. 797-842. PMLR, 2015.
10

---

Published as a conference paper at ICLR 2023
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734-744 IEEE, 2005.
Will Grathwohl, Kuan-Chieh Wang. Jörn-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky. Your classifier is secretly an energy based model and you should treat it like one. arXiv preprint arXiv:1912.0326: 2019.
Will Grathwohl, Kuan- Chinh Wang, Jörn-Hentn Henrik Jacobsen, David Duvenaud, and Richard Zemel. Learning the stein discrepancy for training and evaluating energy-based models without sampling. In International Conference on Machine Learning, pp. 1732-3747. PMLR, 2020.
Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. Oops i took a gradient: Scalable sampling for discrete distributions. In International conference on machine learning. PMIR, 2021.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastivy estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pp. 297-304. JMLR Workshop and Conference Proceedings, 2010.
Ryuichiro Hataya, Hideki Nakayama, and Kazuki Yoshizoe. Graph energy-based model for substruc- ture preserving molecular design. arXiv preprint arXtv:2102.04600, 2021.
Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8))177 2002.
Geoffrey Hinton. A practical guide to training restricted boltzmann machines. In Neural networks: Tricks of the trade, pp. 599-619. Springer, 2012.
John Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 7555):2554-2558, 1982.
Aapo Hyvärinen. Some extensions of score matching. Computational statisties & data analysis, 51 (5):2499 2512, 2007.
Aapo Hyvärinen and Peter Dayan, Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
Ernst Ising. Beitrag zur Theorie des Ferromagnetismus. Zeitschrift fur Physik, 31(1):253-258, February 1925. doi: 00.1007//FF22880577.
Pierre E Jacob, John O'Leary, and Yves Atchadé. Unbiased markov chain monte carlo methods with couplings. Journal of the Royal Statistical Society: Series (Statistical Methodology), 82(3): 543-600, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2288-2324, 1998.
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and F Huang. A tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. In International Conference on Machine Learning. 2018
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. 2019.
Advances in Neural Information Processing Systems,
11

---

Published as a conference paper at ICLR 2023
Meng Liu, Keqiang Yan, Bora Oztekin, and Shuiwang Ji. GraphEBM: Molecular graph generation with energy-based models. arXiv preprint arXiv:2102.00546. 2021.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. GraphDF: A discrete flow model for molecular graph generation. International Conference on Machine Learning, pp. 7192-7203, 2021.
Siwei Lyu. Interpretation and generalization of score matching. In Proceedings of the Twenty-Fifth Conference on Uncertainty Artificial Intelligence, pp. 359-366, 2009.
Radford M Neal et al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(11):2, 2011.
Jiquan Ngiam, Zhenghao Chen, Pang Wei Koh, and Andrew Ng. Learning deep energy models. In Proceedings of the 28th International Conference International Conference Machine Learning, pp. 1105-1112 2011.
Erik Nijkamp, Mitch Hill, Song-Chun Zhu, and Ying Nian Wu. Learning non-convergent non- persistent short-run meme toward energy-based model. Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 5232-5242, 2019.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permu- tation invariant graph generation via score-based based generative modeling. Artificial Intelligence and Statistics, 2020.
Yixuan Qiu, Lingsong Zhang, and Xiao Wang. Unbiased contrastive divergence algorithm for training energy based latent variable models. In International Conference on Learning Representations, 2019.
Prajit Ramachandran, Barret Zoph, and Quoc Le. Swish: self-gated activation function. arXiv preprint arXiv:1710005944, 7:1, 2017.
Christian P Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume 2. Springer, 1999.
Henry A Rowley, Shumeet Baluja, and Takeo Kanade. Neural network-based face detection. IEEE Transactions on pattern analysis and machine intelligence, 20(1):23-38, 1998.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Ingmar Schuster. Gradient importance sampling. arXiv preprint arXiv: 1507.05781, 2015.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. GraphAF: flow-based autoregressive model for molecular graph generation. In International Conference on Learning Representations, 2019.
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors with online hard example mining. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 761-769, 2016.
Martin Simonovsky and Nikos Komodakis. Graph Towards generation of small graphs using variational autoencoders, In International Conference on Artificial Neural Networks, pp. 412-422. Springer, 2018.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, pp. 11918-1199 2019.
12

---

Published as a conference paper at ICLR 2023
Yang Song and Diederik P Kingma. How to train your energy- energy-based models. arXiv preprint arXiv:2101.03288, 2021.
Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pp. 574-584, PMLR, 2020.
Tijmen Tieleman. Training restricted boltzmann machines using approximations to the likelihood gradient. In Proceedings the 2008.
the 25th international conference on Machine learning, pp. 1064-1071.
Pascal Vincent. A connection between matching and denoising autoencoders. Neural computa- tion, 23(7):1611-1674, 2011.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 681-688, 2011.
Jianwen Xie, Yang Lu, Song-Chun Zhu, and Yingnian Wu. A theory of generative convnet. In International Conference on Machine Learning, pp. 2635-2644, 2016.
Jianwen Xie, Song-Chin Chun Zhu, and Ying Nian Wu. Synthesizing dynamic patterns by spatial- temporal generative convnet. In Proceedings of the ieee conference computer vision and pattern recognition, pp. 7093-7101, 2017.
Jianwen Xie, Zilong Zheng, Ruiqi Gao, Wenguan Wang, Song-Chun Zhu, and Ying Nian Wu. Learning descriptor networks for 3d shape synthesis and analysis. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8629-8638, 2018.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International conference on machine learning, pp. 5708 5717. PMLR, 2018.
Giacomo Zanella. Informed proposals for local meme in discrete spaces. Journal of the American Statistical Association, 1 (15550))852-865, 2020.
Song Chun Zhu, Yingnian Wu, and David Mumford. Filters, random fields and maximum entropy (frame): Towards a unified theory for texture modeling. International Journal of Computer Vision, 1772):107-126, 1998.
13

---

Published as a conference paper at ICLR 2023
A
THE DETAILED DERIVATION OF EQ.
(5)
The detailed derivation of Eq. is as follows.
TRAS (0, x) = dE d_
Lo(x)) (x (x)
d
d
m m(x (x--))
c Fola) Eo(an-1)
m( (w) Eo ,)]2
(12)
d
n(x
n(x=i)
m( {e (Baa)) Es [am
dE ,-((
n (x=-))
B
PROOF OF FACT
Proof. According Eq. 66 we have
& -Var
Var m(xxi) Fo())) Eo (x- |
Var (JRM(0,
(13)
n(x
Then compare the variance of the estimator based n (i_ and n(x=.). Formally,
Var
(O,
(14)
d²
m((x=;) [c [o((m) Fo(m 2)12)
=Var
(15)
n² (x=_)
m(x [o((x) Eo (m= 27
m(x=i) [e Feg (x 27
d²
Ex (xn
E in (a
n (x=
n2 (x)
(16)
d²
m(x==)) :) Fo((x) Eg (mm_ 27
TRM (0,)))
E (a
(17)
n (x=
d
d²
d
m(x_:) [e ((r)) Fola (1) +) 27?
TRaS (0, x
12
(x)+)
(18)
d
n0
d
d2
2 (x=
Eo(x) (oo
Eo [x)) Eo (x)
JRM (0, x))
(19)
d
k=1
d2
TRM (0, xx)
m m(x [o( Fol Eolm i)
(20)
d
m(x Fo(a)) (x) Fo (m))
TRM (0, (0.
n( n(xx
(21)
d
n(x=1)
d
m(x x) (o(
Eolx 2
2 Σ
JRM ( xz 7
n x -1)
n n(x=
(22)
n(x=
1=1
14

---

Published as a conference paper at ICLR 2023
d²
m(x_i) (e (.Bo())-Bo(r--- Eo(m-()] 2
JRM (0, x0) )
(23)
1 -i)
d?
m(x-.i) (e
TRAS (0, 20) )
E8 (on(__))__)
(24)
n((0-1)
Var
JRM (RM((,22))) x)
(25)
Eq. 17 can be derived because the estimator is unbiased no matter what proposal distribution
applied. Eq. (19) is obtained by choosing n" (x=_:) [e (0)) (x(-)))
Eq. (0)) holds
since m(x mm==i) for 1,... d. To derive Eq. 22), apply the Cauchy-Schwarz inequality
a.bs)
a df) (Einbb) This completes the proof of Fact 1.
C CONNECTION WITH HARD NEGATIVE MINING
Here, we provide an insight to understand why the second property, described in Section 3.3 lead to better optimization, by connecting it with hard sample mining.
can
Hard sample mining (Felzenszwalb al. 2009 Rowley et al. 1998) has been widely applied to train deep neural networks (Shrivastava al. 201 Our RMwGGIS is particularly highly related to hard negative training strategies. The basic idea for hard negative mining to pay more attention to hard negative samples during training, which can usually achieve better performance since it can reduce false positives. In our setting of discrete EBMs, each training sample æ is positive sample, and its energy should be pushed down. For each positive sample æ, all a; for 1,2,.... d are negative samples, and their energy should be pushed up. Our RMMGGII with the specific proposal distribution shown in Eq. (I0) can approximately choose the æ x 's' that currently have low energies with larger probabilities. This has the same philosophy as hard negative mining. Specifically, in our case, x x-y's with low energies hard negative samples since they are the most offending terms, which are close to the positive sample æ and have low energies.
Since our proposal distribution defined in Eq. (10) approximates the provable optimal proposal distribution given in Theorem 1, our proposal distribution thus approximately performs "hard negative mining". The natural follow-up question is how accurate the approximation and how does affect the learning process? We answer this question by analyzing the following two stages during learning. which can intuitively show that our RMwGGIS is technically sound.
E-(-)
Eg(-X
E-1 1
2-
Ø-
(a)
(b)
Figure 3: An intuitive illustration of the approximation: (a) Stage and (b) Stage II. The black curves denote the energy functions. Green nodes and brown nodes represent the true energy values and approximated values of neighbors, respectively. Note that the approximated values are obtained based on Taylor series of (-)-) at æ, shown in Eq. (7). For clarity, we only show two neighbors of æ in this figure, but this illustration can also be extended to include all neighbors.
Stage L. As shown in Figure (a), at the early stage of learning, the energy function is not learned well, thus the energy Fx( of positive sample not smaller than its all neighbors. In this case,
15

---

Published as a conference paper at ICLR 2023
Table 4: Comparison of resulting objective values. highlighted as 1st and 2nd.
The top lowest values on each dataset
Method
2spirals
8gaussions
circles
moons
pinwheel
swissroll
checkerboard
Ratio Matching
46.02
39.26
31.82
28.57
28.50
37.52
26.05
RMwGGIS (basic)
26.84
30.15
29.89
27.80
28.08
32,20
26.09
RMwGGIS (advanced)
27.15
29.31
29.54
27.75
27.30
29.45
26.06
there are some neighbors æ which have lower energies than (z), such as x in Figure (a). Therefore, "hard negative mining" is in demand in this stage. Under this situation, our approximated energies of neighbors could help to perform "hard negative mining". To be specific, the estimated energies of neighbors are close the true energies, and the estimated energy of æ - is much lower than the estimated energy of Ø Thus, our proposal distribution will sample  with higher probability. This actually works as "hard negative mining" since _-1 is the current most offending term, i.e., the so-called hard negative sample.
Stage II. After learning for a while, we can obtain a relatively good energy function, where the positive sample æ locates in the low energy area compared to its local neighbors. In this case our approximation is less accurate. Fortunately, in this case, "hard negative mining" is not that necessary since there do not exist many offending terms. Specifically, shown in Figure (b), the energies of x-1 and 2 are safely higher than Es (z:).
Even though the above analysis is based on a simplified example, we believe it can serve good intuitive understanding of why our RMwGGIS performs better than ratio matching.
D WHY DOES THE ADVANCED VERSION PERFORM BETTER?
Here, we provide an intuitive explanation on why our advanced version usually performs better than the basic version.
Following our analysis of the connection between our method and hard negative mining, as described in Appendix C it obvious that both basie version (i.e., Eq. (6)) and advanced version (i.e., Eq.
ITT perform "hard negative mining". The difference lies in the coefficients for different terms.
Specifically, the advanced version gives the same weights to all sampled terms. In contrast, the
basic version provides weight m(=(())
to each sampled term x =0) as shown in Eq. (6). Note that
m(=") for all terms and nax(") would be larger
has lower energy. Hence, the basic version provides smaller weights for terms with lower energies. In other words, among its selected
offending terms (i.e., hard negative samples), it pay least attention to the most offending terms, which could be less effective than the advanced version with equal weights. This could explain why our advanced RMwGGIS usually performs better than the basic version.
E COMPARISON OF ACHIEVED OBJECTIVE VALUES
Specifically, for all the learned energy functions in Table I we sample 4000 data points on each dataset and evaluate the resulting objective value defined by Eq. (3). The results are summarized in T We can observe that our basic and advanced RMwGGIS indeed achieve lower objective values, which further demonstrates that our proposed RMwGGIS can lead to better optimization. This is quite natural and straightforward since our method focus on neighbors with low energies. Specifically, according to the objective function of ratio matching (i.e., Eq. (3), neighbors with lower energies contribute more to the objective function. In other words, the loss values for these neighbors are larger. This explains why our methods, focusing on reducing the loss values (ie., pushing up energies) of these neighbors, indeed lead lower value for the objective function defined by Eq. 4
16

---

Published as a conference paper at ICLR 2023
0
60000
#lterations
180000
240000
Ratio Matching
RMwRAND
RMwGGIS (basic)
RMwGGIS
(advanced)
Figure 4: Visualization of learned energy functions w.r.f number learning iterations on the 256-
dimensional 2spirals dataset.
Table 5: Comparison between ratio matching and our RMwGGIS on 2spirals datasets with different dimensions in terms of running time and memory usage.
Data Dimensions
64
128
256
512
1024
2048
Ratio Matching
63.9ms
106.5ms
185.6ms
372.9ms 86.9ms
735.2ms
1390.1ms
2684.1 ms
Memory Time
RMwGGIS
41.2ms
47.2ms
58.8ms
137.7ms
244.9ms
434.1ms
Speedup
1.6x
2.3x
3.2x
4.3x
5,3x
5.7x
6.2
Ratio Matching
957MB
1031MB
1189MB
1545MB
2315MB
4237MB
9633MB
RMwGGIS
891MB
893MB
893MB
915MB
919MB
931MB
951MB
Memory Saving
6.9%
13.4%
24.9%
40.8%
60.3%
78.0%
90.1%
VISUALIZATION OF LEARNED ENERGY FUNCTIONS ON DATA
The learned energy functions w.E. number of learning iterations on the 256-dimensional 2spirals dataset are qualitatively visualized in Figure
G COMPARISON OF RUNNING TIME AND MEMORY USAGE
The comparison of running time and memory usage are summarized in Table
H DETAILED SETTINGS OF GRAPH GENERATION
The results of baselines in Table are reported from You al. (018), Liu al. (2019), Niu et al. (2020). [Shi et al. (2019), and Luo et al. (202T). We obtain the result of EBM (GWG) by using their official implementation, and the detailed settings are provided as follows.
We use the official open-sourced implementatiorf" of EBM (GWG) to perform its graph generation experiment. We train models with persistent contrastive divergence (Tieleman 2008) with a buffer size of 200 samples. We use the Adam optimizer (Kingma & Ba 2015) with a learning rate of 1e-4 and a batch size of 200. The following hyperparameters are tuned and the finally chosen ones are underlined: buffer initialization rate E (0, 0..2 0.4, 0.6} and MCMC steps E (100, 200, 500, 1000, 2000].
I VISUALIZATION OF GENERATED GRAPHS
Generated graph samples are shown in Figure
17

---

Published as a conference paper at ICLR 2023
Training data
RMwGGIS samples
Figure 5: Visualization of training data and samples drawn from the energy function learned by our RMwGGIS for graph generation.
J DETAILS OF TRAINING ISING MODELS
Lattice Ising Models. Ising models (Cipra 1987) is firstly developed to model the spin magnetic particles (ssing 1925). For Ising models, our energy function can be naturally defined as
E(x) = - x Jæ 6" x.
(26)
where J and are the parameters. J is the connectivity matrix which indicates the correlation across dimensions in We follow one specific setting in Grathwohl al. (202I), where all of the non-zero entries of J are identical (denoted as a) and J is the adjacency matrix of a cyclic 2D lattice structure. Therefore,
E E(x) -ox Jæ b x.
(27)
Setup. We follow Grathwohl et al. 2021 for our experimental setting. To be specific, we create model using 25 x 25 lattice and 0.25, thus leading to 625 dimensional distribution. For training the model, 2000 examples are generated via 1, 000, 000 steps of Gibbs sampling. We apply proposed RMwGGIS method to train the model. The number of samples used in our RMwGGIS objective is set to 10. We use Adam optimizer (Kingma & Ba 2015) with a learning rate of le-4 and batch size of 100. Ll penalty with strength 0.01 is used encourage sparsity. In terms of basclines. in addition to ratio matching, we further consider the approaches which train discrete EBMs with persistent contrastive divergence (Tieleman) (2008). The number of steps for MCMC per training iteration is E {5, 10, 25, 50, 100}. The samplers are Gibbs and Gibbs-With-GG With-Gradient (GWG) Grathwohl et al. (022). Results of EBM (GWG) are obtained by running the official implementation from Grathwohl et al. (202T). Results of EBM (Gibbs) are obtained by reading from Figure in Grathwohl et al. (2021).
Evaluation. We evaluate the performance by computing the -quare-da-srrrrr-rrrro (RMSE) between the learned connectivity matrix J and the true matrix J. In addition, we compare the efficiency by reporting the running time for each iteration. To specific, for comparing efficiency, use the same batch size 100 for method and baselines. The report time is the average over 100 iterations.
18


Reviews:
[{"review_id": "o_zgS8wPW3E", "reviewer": "Reviewer_wsgm", "summary": "", "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": "", "summary_of_the_paper": "This paper proposed a gradient-guided importance sampling method for learning binary energy based models. The idea is to combine ratio matching with scalable gradient of the energy function for more efficient computation. The paper is clearly written. Numerical experiments show the advantage of the proposed method over alternative baselines.", "summary_of_the_review": "The paper present a new method for learning binary energy based model that combines ratio matching and scalable gradient-based importance sampling techniques. Overall, the paper is well written and organized. Although ratio matching and gradient-based information for scalable sampling from discrete energy based models have been proposed before, the combination for learning binary energy based model is new. The lack of novelty and significant empricial evidence of the proposed method is the main reason for my recommendation.", "strength_and_weaknesses": "Strength:\n\n1. The paper is well written and organized.\n2. The idea of combining gradient information of the energy function and ratio matching is new.\n\nWeaknesses:\n\n1. As the main idea is a combination of ratio matching and gradient information, there seems to be a lack of ablation study on which one is the main factor for the overall improvement. More specifically, there is no comparison to scalable gradient-based samping method for learning discrete EBMs (e.g., GWG, Grathwohl et al., 2021) in section 5.1, and stochastic ratio matching in section 5.2 and 5.3.\n\n2. The number of samples $s$ seems to be a crucial hyper-parameter and there is no ablation study of it throughout the experiments. It would be better to have it to clarify the choice of $s$ in your experiments. The author reported that the simple random sampling failed when $s=10$ which would be easily saved with more samples.\n\n3. The experiment results are not significant on real data tasks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZKfhY8VEkd", "reviewer": "Reviewer_pBMS", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies the problem of learning binary energy-based model using ratio matching method. The paper proposes to use importance sampling to improve the time and memory efficiency of the ratio matching method, where the proposal distribution is obtained based on the gradient of the energy function with respect to the binary variables. The effectiveness of the proposed method is demonstrated on synthetic and real datasets. ", "summary_of_the_review": "The paper proposes a simple and effective method for learning binary energy-based model. ", "strength_and_weaknesses": "Strengths: \n\n(1) The proposed method is novel, simple and useful. \n\n(2) The experiments illustrate the effectiveness of the proposed method. \n\n(3) The paper clearly discusses the limitation with respect to binary images. \n\nWeaknesses: \n\nMethods based on importance sampling may not work well for high dimensional problem. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "M4bXgJxXTw", "reviewer": "Reviewer_KMq7", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper proposes a new method to learn discrete EBMs based on ratio-matching. Specifically, they consider the “discrete extension of generalised score matching”. The main disadvantage of this approach is that it is inefficient in time and memory complexity since you need to compute d + 1 energies (d perturbations and x itself), then backprop through it. This paper proposes sampling s << d perturbations instead, and reducing the variance of this estimator via importance sampling. The optimal proposal distribution for importance sampling has a closed form, but is as expensive to compute as the original ratio matching approach. This proposal can be approximated via a first-order Taylor-approximation, following the GWG approach (related work). In practice, the authors dispense with reweighting the ratios by the importance factor (Eq. 11).", "summary_of_the_review": "The paper is well-written and clear, and the method is novel and interesting. Many of the claims are well-supported by either/both theoretical and empirical justification.\n\nThere are two versions of their method being used, and it’s unclear which they refer to in which experiment.\n\nI have some concerns regarding properties of their method. Specifically, experiments that show the bias/variance of the estimator, and experiments on higher-dimensional data showing that the learned energy functions are better (e.g. are the energy functions as easy to sample from at test-time if sampling is not done during training).\n", "strength_and_weaknesses": "The paper is very well-written and clear. There is a very good description of the background materials and the method itself. There are many experiments to back up their claims.\n\nI feel it could be explained more clearly in the main body that the “advanced version” is the method actually being used. It should be emphasised earlier in the work that the final method does not re-weight the samples according to the importance weights. My understanding is that both “basic” and “advanced” are denoted as “RMwGGIS”, which is confusing.\n\nAre there any experiments showing why the variance of the importance-weighted sampler is better?\n\nBesides on toy-data, can you show that the energy functions learned with your approach are better? e.g. can you show that you can do OOD detection with your models? Is it easier to sample from your learned energy functions compared to those where MCMC is used at training time?\n\nDo you stop_grad through the importance weights? If yes, this should be emphasised.\n\nThe top bar notation above equation 9 should be explained in a footnote, and it should be formatted better (e.g. \\overline{x}_i, not \\overline{x_i})\n\nCan you explain in the main body why you remove the importance sampling? How much bias does this induce in the estimator?\n\nIt should be emphasised earlier in the work (e.g. when introducing ratio matching), that this approach doesn’t work well for images.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AKgQcTWXCd", "reviewer": "Reviewer_D4Cv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "This paper proposed an importance sampling approach to alleviate the computation and memory complexity of ratio matching for training binary EBM. Specifically, the author first rewrites the ratio-matching objective as an expectation of the energy difference and then showed the form of optimal importance proposal to reduce the variance of the objective. In the end, the author showed that the optimal importance proposal can be approximated by using the Taylor expansion following the ideas from Gibbs-with-gradient (GWG) sampler. \n\nEmpirically, the author evaluates the proposed approach using synthetic data, graph generation, and ising model. In general, it achieves better results in the graph generation task. Although it performs worse than GWG, it is much faster in terms of training.", "summary_of_the_review": "The author proposed an improved version of ratio matching for training binary EBM by using importance sampling. In general, the paper is written clearly and does a good job of explaining the intuition of the proposed method. I am also curious why there is a discrepancy between the theory and empirical evaluations such that the advanced version performs better than the \"correct\" version. ", "strength_and_weaknesses": "## Strength\n\nThe paper is clearly written and easy to follow. The author also explains the intuition behind the proposed importance sampling approach in section 3.3, which help the understanding of the paper. Empirically, the author considers three tasks and includes many baselines in graph generation task. I briefly checked the math, which seems to be correct. \n\n## Weakness\nTheoretically, I am curious about why eq.11 has a better performance than eq.6? Eq.11 is not a proper objective anymore, which means it does not correspond to a valid discrepancy. How does this ensure that the model can converge to the correct distribution? In addition, from theorem 1, the importance proposal should be the optimal one (at least approximately). Why the advanced version is better?\n\nEmpirically, I think other than the graph generation task, more baselines should be considered. At the moment, only ratio matching is used for synthetic data and GWG and Gibbs are used for the Ising model. More baselines can further support the claims made by the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster