To Relieve Your Headache of Training an MRF, Take AdVIL
Authors: Chongxuan Li
Chao Du
Kun Xu
Max Welling
Jun Zhu
Bo Zhang
Venue:  (2020)
Keywords: Markov Random Fields
Undirected Graphical Models
Variational Inference
Black-box Infernece

Abstract: We propose a black-box algorithm called {\it Adversarial Variational Inference and Learning} (AdVIL)  to perform inference and learning on a general Markov random field (MRF). AdVIL employs two variational distributions to approximately infer the latent variables and estimate the partition function of an MRF, respectively. The two variational distributions provide an estimate of the negative log-likelihood of the MRF as a minimax optimization problem, which is solved by stochastic gradient descent. AdVIL is proven convergent under certain conditions. On one hand, compared with contrastive divergence, AdVIL requires a minimal assumption about the model structure and can deal with a broader family of MRFs. On the other hand, compared with existing black-box methods, AdVIL provides a tighter estimate of the log partition function and achieves much better empirical results. 

Published as a conference paper at ICLR 2020
To RELIEVE YOUR HEADACHE OF TRAINING AN MRF, TAKE ADVIL
Chongxuan Li", Chao Du", Kun Xu", Max " Zhu", Bo Zhang [chongxuan1i1991 duchao0726, kunxu. @maal com, M. W.Wellinguuaa.ne ni, {deszj, deszb) @mail. tsinngua. edu en
ABSTRACT
We propose a black-box algorithm called Adversarial Variational Inference and Learning (AdVIL) to perform inference and learning in general Markov random field (MRF). AdVII employs two variational distributions to approximately infer the latent variables and estimate the partition function of an MRF, respectively. The two variational distributions provide an estimate of the negative log-likelihood of the MRF as a minimax optimization problem, which is solved by stochastic gradient descent. VdVIL is proven convergent under certain conditions. On one hand, compared to the contrastive divergence, AdVIL requires minimal assumptions about the model structure and can deal with a broader family of MRFs. On the other hand, compared to existing black-box methods, AdVII. provides a tighter estimate of the log partition function and achieves much better empirical results.
INTRODUCTION
Markov random fields (MRFs) find applications in a variety of machine learning areas (Krähenbühl & Koltun 2011 Salakhutdinov Larochelle] 2010 Lafferty et al. 200T]. In particular, one famous example is conditional random fields (Lafferty et al.) 2001). a conditional version of MRFs that was developed address the limitations (e.g., local dependency and label bias) of directed models for sequential data (e.g.. hidden Markov models and other discriminative Markov models based on directed graphical models). However, the inference and learning of general MRFs are challenging due to the presence of global normalizing factor, i.e. partition function, especially when latent variables are present. Extensive efforts have been devoted to developing approximate methods. On one hand, sample-based methods (Neal) 1993) and variational approaches (Jordan et al., 1999 Welling & Sutton 2005; Salakhutdinov & Larochelle 2010) are proposed to infer the latent variables. On the other
hand, extensive work (Meng & Wong 1996 Neal 2001 Hinton 2002 Tieleman, 2008 Wainwright et al. 2005| Wainwright & Jordan 2006) has been done to estimate the partition function. Among these methods, contrastive divergence (Hinton 2002) is proven effective certain types of models.
Most of the existing methods highly depend on the model structure and require model-specific analysis in new applications, which makes important develop black-box inference and learning methods. Previous work (Ranganath et al. 2014: Schulman et al. 2015) shows the ability to automatically infer the latent variables and obtain gradient estimate in directed models. However, there no black- box learning method for undirected models except the recent work of NVIL (Kuleshov & Ermon 2017).
NVIL introduces a variational distribution and derives an upper bound of the partition function in general MRF, in the same spirit as amortized inference (Kingma& & Welling 2013 Rezende et al. 2014 & Gregor] (2014) for directed models. NVIL has several advantages over existing methods, including the ability of black-box learning, tracking the partition function during training and getting approximate samples efficiently during testing. However, NVIL also comes with two disadvantages: (1) it leaves the inference problem of MRFs unsolved and only trains simple MRFs with tractable
DDett. of Comp. Sci. & Tech., BNRist Center, Institute for AI, THBI Lab, Tsinghua University, Beijing, 1 100084, China
1 University of Amsterdam, and the Canadian Institute for Advanced Research (CIFAR). NVII (Kuleshov & Ermon 2017) presents hybrid model. The "inference" in the title refers to directed
part but not for an MRF

---

Published as a conference paper at ICLR 2020
posteriors, and (2) the upper bound of the partition function can be underestimated (Kuleshov & Ermon 2017), resulting in sub-optimal solutions on nigh-diiennsionl data.
We propose Adversarial Variational Inference and Learning (AdVIL) to relieve some headache of learning an MRF model. AdVIL is a black-box inference and learning method that partly solves the two problems of NVIL. and retains the advantages of NVIL at the same time. First, AdVIL introduces a variational encoder to infer the latent variables, which provides an upper bound of the free energy. Second, AdVIL introduces a variational decoder for the MRF, which provides lower bound of the log partition function. The two variational distributions provide an estimate of the negative log- oog-liklihood of the MRF. On one hand, the estimate is in an intuitive form of an approximate contrastive free energy, which is expressed in terms of the expected energy and the (conditional) entropy of the corresponding variational distribution. On the other hand, similar to GAN (Goodfellow et al. 2014), the estimate is a minimax optimization problem, which is solved by stochastic gradient descent (SGD) in an alternating manner. Theoretically, our algorithm is convergent if the variational decoder approximates the model well. This motivates us introduce an auxiliary variable to enhance the flexibility of the variational decoder, whose entropy approximated by the third variational trick.
We evaluate AdVIL in various undirected generative models, including restricted Boltzmann machines (RBM) (Ackley et al. 1985), deep Boltzmann machines (DBM) (Salakhutdinov & Hinton 2009), and Gaussian restricted Boltzmann machines (GRBM) (Hinton & Salakhutdinov (006), several real datasets. We empirically demonstrate that (1) compared to the black-box NVIL. (Kuleshov & Hrmon 2017) method, AdVIL provides tighter estimate of the log partition function and achieves much
better log-likelihood results; and (2) compared to contrastive divergence based methods (Hinton) [2002] Welling & Sutton 2005), AdVIL can deal with a broader family of MRFs without model-specific analysis and obtain better results when the model structure gets complex as in DBM.
2 BACKGROUND
We consider a general case where the model consists of both visible variables v and latent variables where & denotes the h. An MRF defines the joint distribution over v and h as P(u, h) -((,,,)] س associated energy function that assigns scalar value for a given configuration of (v. h) and 2 is the partition function such that 2 = -e., E-E(v,h)
Let Pb(v) denote the empirical distribution of the training data. Minimizing the negative log- likelihood (NLL) of an MRF is a commonly chosen learning criterion and is given by:
e ((e.h)
(()) = Er(()) log
dh
(1)
Z
where 9 denotes the trainable parameters in E Further, the gradient of 0 is:
Vol(O) = Epo(.) [VoF(v)] Ep(,) [VF[(v)].
(2)
where F(v)- log Sn e E(. denotes the free energy and the gradient in Eqn. (2) is the difference of the free energy in two phases. In the first positive phase, the expectation of the free energy under the data distribution decreased. In the second negative phase, the expectation of the free energy under the model distribution is increased.
Unfortunately, both the NLL in Eqn. T and its gradient in Eqn. (2) are intractable in general for two reasons. First, the integral of the latent variables in Eqn. {I) or equivalently the computation of the free energy in Eqn. (2) is intractable. Second, the computation of the partition function Eqn. ( or
equivalently the negative phase in Eqn. 2 is intractable.
Variational inference. Extensive work introduces deterministic approximations for the intractability of inference, including the mean-field approximation (Welling & Hinton 2002. Salakhutdinov & Hinton 2009), the Kikuchi and Bethe approximations (Welling & Sutton (005) and the recognition model approach (Salakhutdinov & Larochelle, 2010). In this line of work, the intractability of the partition function is addressed using Monte Carlo based methods.
Contrastive free energy. Contrastive divergence (CD) (Hinton 2002) addresses the intractability of the partition function by approximating the negative phase in Eqn. (2) as follows:
VoL(O) Epp(v) (VoF(r)) Epen(v) (V [V)F())),
(3)
2

---

Published as a conference paper at ICLR 2020
q(h)
Qrhivi
P(v,
avv h)
vvv.
qth, 2)
(2th))
Illustration of the models involved in AdVIL. From left to right: variational encoder (hlu), MRF P(u, h), variational decoder ((v, h) with a simple prior and g(v, h) with an expressive prior.
Figure 1:
where (v) denotes the empirical distribution obtained by starting from a data point and running several steps of Gibbs sampling according to the model distribution and the freee energy F(v) is assumed to be tractable. Existing methods (Welling & Hinton 2002 Welling & Sutton 2005 approximate F(u) using certain function ((v) and the gradient of is:
veC(0) ~ (p)(s)
[Ve[())] - (v) [Ve[()]].
(4)
Although these generalized methods exist, it is nontrivial extend CDD-based methods general MRFs because the Gibbs sampling procedure is highly dependent on the model structure.
Black-box learning. The recent work of NVIL (Kuleshov Ermon 2017) addresses the intractability of the partition function in a black-box manner via variational upper bound of the partition function:
P(v) ((0)2
IE gw)
Zz
(5)
where P(r) = e-(() is the unnormalized marginal distribution on and q(v) is neural variational distribution. As a black-box learning method, NVIL potentially allows application to broader model families and improves the capabilities of probabilistic programming systems (Carpenter et al. (017). Though promising, NVIL leaves the intractability of inference in MRF unsolved, and the bound in Eqn. 5 is of high variance and is easily underestimated (Kuleshov & Ermon 2017).
METHOD
As stated above, the black-box inference and learning of MRFs are still largely open. In this paper, we make a step towards solving the problems by a new variational approach. For simplicity, we focus on the resulting objective function in this section. See Appendix A for detailed derivation.
3.1 ADVERSARIAL VARIATIONAL INFERENCE AND LEARNING
First, we rewrite the NL. of the MRF (See an illustration in Fig. I as follows:
(())= = EE (p)) [-F(t)] + log Z,
(6)
where the negative free energy and the log partition function in the form of logarithm of an integral. Naturally, we can apply the variational trick (Jordan et al. 1999) twice and approximate the two terms individually. Due the presence of the minus before the first term in Eqn. (6) the two variational tricks bound the two parts of the NLL in the opposite directions, detailed as below.
Formally, on one hand, we introduce an approximate posterior for the latent variables Q(huu) which is parameterized as neural variational encoder (See an illustration in Fig. [ to address the intractability of inference as follows:
(())= < (pp(s)(()))) [E(v, h) + log Q(h[o)] - log Z = Li(0,
(7)
where ø denotes the trainable parameters in Q(1vv). The upper bound is derived via applying the Jensen inequality and the equality holds if and only if Qhh)v)) P(h(v) for all v. In the bound, the first term the expected energy, which encourages Q(hlv) ) to infer latent variables that have low values of the energy function E(V, h), equivalently high probabilities of P(v, h). The second term corresponds to the negative conditional entropy of Q(h/v). which increases the uncertainty of Q(h)v). In the paper, we denote the conditional entropy of (h) as H(Q) (Ppo())(()))) (log Q(hlu)).
3

---

Published as a conference paper at ICLR 2020
On the other hand, introduce approximate sampler q(, U, h), which is parameterized by neural variational decoder (See Fig. D. to address the intractability of the partition function as follows:
Tenergy term
entropy term
energy temn
entropy term
(0, ()2BP(())((M)))
E(v,h) h) +log Q(hyu)
Eg Bgte,h)
h(u,h) Hlgggee = (2,0,,,),, (8)
Positive Phase
Negative Phuse
where ai denotes the trainable parameters in q(v, , f). The lower bound is derived via applying the Jensen incquality well, and the equality holds if and only if q(u, h) P(v, h). It can be seen that the lower bound given by q(v. h)) consists of the entropy (denoted as H(Gg) and energy terms, which is similar to the upper bound in Eqn. 77). and the overall objective is in the form of approximate contrastive free energy (Hinton, 2002, Welling & Sutton, 2005). Because the double variational trick bounds the NLL in opposite directions as above, have minimax optimization problem:
min min max (2 o, eb).
@
1
The minimax formulation has been investigated in GAN (Goodfellow et al. 2014) and is interpreted as an adversarial game between two networks. We name our framework adversarial variational inference and learning (AdVIL) following the well-established literature.
Note that C2 Φ. v is neither an upper bound, nor a lower bound of L(0) due to the double variational trick. However, we argue that solving the optimization problem in Eqn. (9) is reasonable because (1) is equivalent to optimizing C()) under the nonparametric assumption, which is similar to GAN (Goodfellow et al. 20144); and (2) it converges to stationary point of Li (0, (),, which is an
upper bound of (()). under a weaker assumption, as stated in the following theoretical analysis.
3.2 THEORETICAL ANALYSIS OF ADVIL
In this section, we present our main theoretical results and the proofs can be found in Appendix C Firstly, similarly to GAN (Goodfellow et al. 2014), we can prove that L2 is a tight estimate of L under the nonparametric assumption, which is summarized in Proposition | in Appendix C.I However, the nonparametric assumption does not tolerate any approximation error between P h) and q(v, during training and guarantee can be obtained in finite steps. To this end, we establish a convergence theorem based on a weaker assumption that allows non-zero approximation error
before convergence. A key insight is that the angle between @L2(0.0.V) and
@6,(0.0) is positive if 88
q(v, h) approximates P(u, h)) well, as stated the following Lemma
Lemmal
For any (8, o), there exists a symmetric positive definite matrix H such that (C2(0.6.0) Eu 8(v, h) (v,u,b)
09
H (0,(0.0) under the assumption:
||| (0.))) .0)
||2 if 0C,
(9.d)
l| > 0 and
00
00
00
00
(E(u.)) Er ō(v, h)
(L1(0.)) ||2 O, where 8(v, h) - g(v, P(v,h). 2 (
80
30
Based on Lemma and other commonly used assumptions in the analysis of stochastic optimiza- tion (Bottou et al., 2018), AdVIL converges to a stationary point of (1, Φ). as stated in Theorem ! Theorem I. Solving the optimization problem in Eqn. (9) using stochastic gradient descent, then (0, Φ) converges stationary point of (1, o) under the assumptions in the general stochastic optimization (Bottou et 2018) and that the condition of Lemma holds in each step.
Please see Appendix C.2 for a detailed and formal version of Theorem 1 Compared to Proposition I and the analysis in GAN (Goodfellow et al., 2014). Theorem Taas weaker statement that AdVIL converges to stationary point of the negative evidence lower bound (i.e., Li) instead of L. Never- theless, we argue that converging to L1 is sufficiently good for variational approaches in general. Besides, Theorem staaess that AdVIL can at least decrease L1 in expectation if the assumption holds in finite steps. Indeed, we empirically justify Theorem T as detailed in Appendix E.I Theorem [ also provides insights for the implementation of AdVIL. Indeed, its assumption motivates to use a sufficiently powerful q(v, h)) with neural networks and auxiliary variables, and update q hv) multiple times per update of P(u. h), detailed in Sec. 3.3 and Sec. 5.1 respectively.
3.3 SPECIFYING THE VARIATIONAL DISTRIBUTIONS
To efficiently get samples, both variational distributions are directed models. We use a directed neural network that maps to h as the variational encoder Qhh/v) (Kingma & Welling 2013).
4

---

Published as a conference paper at ICLR 2020
As for the variational decoder, we first factorize it as the product of prior over h and conditional distribution, namely q(v, h) = (h)) It is nontrivial to specify the prior q(h) because the marginal distribution of h in the MRF, i... P(h), can be correlated across different dimensions. Consequently, a simple ((h) is not flexible enough to track P(h) and can violate the condition of Lemma [ To this end, we introduce an auxiliary variable which can be discrete continuous, on top of h and define q(v, f)) = S2 (h(=))(((((((())))
(See an illustration in Fig. D However, the entropy term of ((. h) is intractable because we need to integrate out the auxiliary variable 2. Therefore, we introduce the third variational distribution r(=]A) approximate the entropy of q(v, h).
As in Eqn. applying the standard variational trick gives an upper bound:
g(h, x)
(B log (v, S (Bg( log (((()) (gth)resA) log
(10)
rr([h)
which is unsatisfactory because the estimate is minimized w.r. r(2 h) while maximized w.r.t q(v, h). Instead, after some transformations (See details in Appendix A we get lower bound as follows:
g/b,z) r(=[h)
- Ey(o,)) log g(v, h) 2 - -Ey(o,n) log g h)) (h.,,.) log
(11)
The equality holds if and only if (2
(2/h) for all h. The difference between the two bounds is subtle: the last expectation in Eqn. I0 is over ((k)r(2)h) but that in Eqn. [1] is over (h, Here, a lower bound is preferable hecause the estimate is maximized with respect to both r(=[h) and q(v. h) and we can train them simultaneouslyy For simplicity, we absorb the trainable parameters of (22(h) into e). Note that after introducing and r(=[h), we can still obtain a convergence theorem of AdVIL under the conditions that r(2) (=]h) approximates (z(/h) well and (v, h) = f q h, z)dz sufficiently close to P(v, h)) in every step, together the assumptions in general stochastic optimization.
Following GAN (Goodfellow al., 2014), we optimize 0, Φ and jointly using stochastic gradient descent (SGD) in an alternating manner. The partial derivatives of & and i are estimated via the reparameterization trick (Kingma & Welling, 2013) for the continuous variables and the Gumbel- Softmax trick (Jang et al., 2016, Maddison et al., (0166) for the discrete variables. See Algorithm [ in Appendix [or the whole training procedure. Note that vp is updated K₁ > 1 times per update of
4 RELATED WORK
Existing traditional methods (Neal 2001| Hinton 2002 Winn Bishop 2005
Wainwright & Jordan
2006 Rother et al. 2007) can be used to estimate the log partition function but are nontrivial to be extended to learn general MRFs. Some methods (Winn Bishop) 2005 Neal 2001) require an expensive inference procedure for each update of the model and others (Hinton | Rother et al.) 2007) cannot be directly applied to general cases (c.g., DBM). Among these methods, contrastive divergence (CD) (Hinton| 2002) is proven effective in certain types of models and it is closely related to AdVIL. Indeed, the partial derivative of in AdVIL is:
@L2(0, (,)) (P(())(())))
a E(v, m)) - Bo((,h) ae
O ae E(v, h))
(12)
00
which also involves positive phase and negative phase naturally and is quite similar to Eqn. (3) However, notably, the two phases average over the (v, h) pairs and only require the knowledge of the energy function without any further assumption of the model in AdVIL. Therefore, AdVIL is more suitable to general MRFs than CD (See empirical evidence in Sec. (.3).
In the context of black-box learning in MRFs, AdVIL competes directly with NVIL Kuleshhvv & Ermon, (201)). It seems that the upper bound in Eqn. 5 is suitable for optimization because P and share the same training direction. However, the bound holds only if the support of a subset of the support of q. Further, the Monte Carlo estimate of the upper bound of high variance. Therefore. the bound of NVIL can be easily underestimated, which results in sub-optimal solutions (Kuleshov & Ermon 2017). In contrast, though AdVIL arrives a minimax optimization problem, the estimate of Eqn. (8) is tighter and of lower variance. We empirically verify this argument (See Fig. and systematically compare the two methods (See Tab. in Sec.5.4.
An alternative way is to use an autoregressive model q(h). See results and analysis in Appendix F.3
5

---

Published as a conference paper at ICLR 2020
40.0
Exact Entropy
Portition Function
Lower Bound
Lower Bound
30-
37.5
-10
20-
45-
NLL
-15
Free Energy
40-
10-
Upper Bound
30.0
-20
5000
5000
10000
Eieratooss
Iteaaioos
(a) upper bound of F(v) (b) lower bound of H((g) (c) lower bound of log 2 (d) RBM loss and NLL
Figure 2: Curves of AdVIL Digits. (a-c) compare the values of the variational approximations and the corresponding ground truths. All bounds are rather tight after 5,000 iterations. (d) shows that the RBM loss (i.e., the loss of 0 as in Eqn. (8) tends to zero and the model converges gradually.
Apart from the work on approximate inference and learning in MRFs as mentioned above, AdVIL is also related some directed models. Kim & Bengio (016) jointly trains a deep energy model (Ngiam
cet al. 201T) and a directed generative model by minimizing the KL-divergence between them. Similar
ideas have been highlighted in (Finn al.] 2016 Zhai et al. 2016 Dai et al. 2017 Liu & Wang
2017). In comparison. firstly, AdVIL obtains the objective function in a unified perspective on the
black-box inference and learning in general MRFs. Note that dealing with latent variables in MRFs is nontrivial (Kim & Bengio 2016) and therefore existing work focuses on fully observable models. Secondly, AdVIL uses a sophisticated decoder with auxiliary variables to handle the latent variables and derives principled variational approximation of the entropy term instead of the heuristics (Kim) & Bengio 2016 Zhai et al. 2016). Lastly, the convergence of AdVIL is formally characterized by Theorem while the effect of the approximation error in inference is not well understood in existing methods. Adversarially learned inference (ALI) (Donahue et al.) 2016 Dumoulin et al.) 2016) is also formulated minimax optimization problem but focuses on directed models.
5 EXPERIMENTS
In this section, we evaluate AdVIL in restricted Boltzmann machines (RBM) (Ackley al. 1985). deep Boltzmann machines (DBM) Salakhutdinov & Hinton| 2009) and Gaussian restricted Boltz- mann machines (GRBM) (Hinton Salakhutdinoy (0066) on the Digits dataset, the UCI binary databases (Dheeru & Karra 2017) and the Frey faces datasets (See detailed settings in Appendix [ and the source code D. We compare AdVIL with strong baseline methods systematically and show the promise of AdVIL to learn broad family of models effectively black-box method.
5.1 EMPIRICAL ANALYSIS OF ADVIL
We present a detailed analysis of AdVIL in RBM, whose energy function is defined as Ev, h) = -b -ー Wh- c h. The conditional distributions of an RBM are tractable, but we still treat P(h v) as unknown and train AdVII in a fully black-box manner. The analysis is performed on the Digits dataset and we augment the data of five times by shifting the digits following the protocol in (Kuleshov) & EEmmon 2017). The dimensions of v. h and are 64, 15 and 10, respectively. Therefore, the log partition function of the RBM and the entropy of the decoder can be computed by brute force.
Firstly, we empirically validate AdVIL in Fig. 2 Specifically, Panel (a) shows that the variational encoder Q(h b) provides tight upper bound of the free energy after 2,000 iterations. Panel (b) demonstrates that the variational distribution r(2[h) estimate the entropy of q(u, h) accurately. Panel (c) shows that qv, h)) can successfully track the log partition function after 5,000 iterations. Panel (d) presents that the RBM loss balances well between the negative phase and positive phase, and the model converges gradually. See Appendix E. for an empirical test of the condition in Lemma [
Secondly, we empirically show that both P and gg can generate data samples in Appendix E.2
Lastly, we analyze the sensitivity of K₁. Theoretically, enlarging K2 will make quv, h) and P(u, to be close and then help the convergence according to Theorem T As shown in Fig. 3 (a), larger
Kj at least won't t hurt the convergence, which agrees with Theorem I Though Ki = 15 is sufficient on the Digits dataset, we use K₁ 100 default setting for AdVIL on larger datasets.
"eee the source code in http://aaannonooo//sssscc/ce//ea

---

Published as a conference paper at ICLR 2020
29
NLL K1-5
logz bound
log2 in allon
125
Test NLL PF
Test of CD1D
NLL,
125
125
Test NLL K1=50
100
Anho
100
75-
50
50
20000 26
25
25
10000
8000
8000
Iterations
Iterations
ttrratooss
Porations
(a) Sensitivity of K
(b) NVIL
(c) AdVIL
(d) PCD-1
Figure 3: (a) Sensitivity analysis of K₁ the Digits dataset. (b-d) Learning curves of NVIL, AdVIL and CD on the Mushrooms dataset. Compared to NVIL, AdVIL provides a tighter and lower variance estimate of log 2 and achieves better performance. Compared to PCD-1 and CD-10, AdVIL can track the log partition function and achieve comparable results though trained in a black-box manner.
Table 1: Anneal importance sampling (AIS) results in RBM. The results are recorded on the test set according to the best validation performance and averaged over three runs. AdVIL outperforms NVIL consistently and significantly. See the standard deviations in Appendix E.5
Method
Digits
Adult
Connect4
DNA
Mushrooms
NIPS-0-12
Ocr-letters
RCV1
NVIL-mean
27.36
20.05
24.71
97.71
29.228
290.01
47.56
50.47
AdVIL-mman
-26.34
19.229
21.95
-97.59
-99.59
-276.42
-45.64
50.22
5.2 RBM RESULTS
To the best of our knowledge, NVIL (Kuleshov & Ermon 2017 is the only existing black-box learning method for MRFs and hence it is the most direct competitor of AdVIL. In this section, we provide a systematic comparison and analysis of these two methods in terms of the log- likelihoodd results on the UCI databases (Dheeru & Karral 2017).
For fair comparison, & Murray| 2008) metric for quantitative evaluation. Besides, we carefully perform grid search over the default settings of NVIL (Kuleshov & Ermon, 2017) and our settings based their code, and choose the best configuration including K₁ = 100 (See details in Appendix D). We directly compare with the best version of NVIL in Tab. | can be seen that AdVIL consistently outperforms NVIL on all datasets, which demonstrate the effectiveness of AdVIL. Besides, the time complexity of AdVIL comparable that of NVIL with the same hyperparameters.
the aidely-adopted anneal importance sampling (AIS) (Salakhutdinov
We compare the learning curves of NVIL and AdVIL on the Mushroom dataset. As shown in Fig, (b). the upper bound of NVIL underestimated after 4,000 iterations and then the model can get worse or even diverge. In contrast, as shown in F the lower bound of AdVII. is consistently valid. Besides, the estimate of NVIL is looser and of higher variance than that of AdVII. The results agree with our analysis in Sec. 4 and explain why AdVIL significantly outperforms NVIL. Further, as shown in Fig. (d), AdVIL comparable to CD- 10 and persistent contrastive divergence (PCD) Tieleman 2008 which leverage the tractability of the conditional distributions in RBM.
5.3
DBM RESCITT
We would like to demonstrate that AdVIL has the ability deal with highly intractable models such as a DBM conveniently and effectively, compared to standard CD-based methods (Hinton 2002
Welling Hinton 2002 WWeling Sutton 2005) and NVIL (Kuleshov & Ermon 2017).
DBM (Slakhuudiino & Hinton 2009 is powerful family of deep models that stack multiple RBMs together. The energy function of two-layer DBM is defined as E(v, h1, h2) = bb
W, - c. h1 - h Wnhr c₂ h2. Learning DBM is challenging because P(h hog w)) is not tractable and CD (Hinton) 2002) is not applicable. Inspired by (Welling & Hinton 2002; Welling & Sutton 2005), we construct a variational CD (VCD) baseline by employing the same variational encoder Qh, by (v) as in AdVIL. The free energy is approximated by the same upper bound as in Eqn. 77), which is minimized with respect to the parameters in Q(hi, halv). The gradient of the parameters in the DBM is given by Eqn. (4), where the Gibbs sampling procedure is approximated by hy Q( (v) and P(rlhı). Note that AdVII can be directly applied to this case. As for
7

---

Published as a conference paper at ICLR 2020
Table AIS results in DBM. The results are recorded according to the best validation performance and averaged by three runs. AdVIL achieves higher averaged AIS results on five out of eight datasets and has a better overall performance than VCD. See the standard deviations in Appendix E..
Method
Digits
Adult
Connect4
DNA
Mushrooms
NIPS-0-12
Ocr-letters
RCVI
VCD-mean
-8..49
22.26
-66.79
-97.59
-23.15 23
-656.26 2287.15
-45.77
50.83
AdVIL-mean
27.899
20.29
- 26..44
-99.40
-21 21.21
- -48.38
-51.02
(a) Data
(b) Filters of the GRBM
(c) Samples from g
(d) Samples from P
Figure 4: Filters and samples of a GRBM learned by AdVIL on the Frey faces dataset. (a) presents the training data. (b) presents the first 40 filters of the GRBM. (c) and (d) show random samples from the variational decoder and the GRBM, respectively. We present the mean of y for better visualization.
the time complexity, the training speed of AdVIL is around ten times slower than that of VCD in our implementation. However, the approximate inference and sampling procedure of AdVIL is very efficient thanks to the directed variational distributions.
The log-likelihood results on the UCI databases are shown in Tab. 2 can be seen that AdVII. has a better overall performance even trained in black-box manner, which shows the promise of AdVIL. See Appendix E.4 for learning curves and a detailed analysis of the results.
We also extend NVIL by using the same Q(h,, (g) and g(v, h1, h2) as AdVIL. However, NVIL diverges after 300 iterations and gets bad A1S results (e.g., less than -40 on Digits) in our implemen- tation. A potential reason is that the upper bound given by q in NVIL can be underestimated if q is high-dimensional, as analyzed in Sec. and Fig- Note that g(v, h1, h2) in DBM involves latent variables and has higher dimension (e.g. 164 on the Digits dataset) than q(v) in RBM (e.g. 64 on the Digits dataset). The results again demonstrate the advantages of AdVIL over NVII..
5.4 GRBM RESULTS
We now show the ability of AdVII to learn GRBM on the continuous Frey faces dataset. The energy function of a GRBM is Ev, h) = 2 ||0 61|² c h - fo" Wh, where a is the standard deviation of the Gaussian likelihood and is set as 1 manually. We standardize the data by subtracting the mean and dividing by the standard deviation. The dimensions of h and z are 200 and 50, respectively.
Though GRBM is more sensitive the hyperparameters and hence harder train than an RBM (Cho) et al. 2011) 2013), AdVIL can successfully capture the underlying data distribution using the default hyperparameters (See Appendix D). As shown in Fig. the samples from both the GRBM (via Gibbs sampling after 100,000 burn-in steps) and the decoder are meaningful faces. Besides, the filters of the GRBM outline diverse prototypes of faces, which accords with our expectation.
In summary, the results of the three models together demonstrate that AdVIL can learn a broad family of models conveniently and effectively in a fully black-box manner.
CONCLUSION AND DISCUSSION
novel black-box learning and inference method for undirected graphical models, called adversarial variational inference and learning (AdVIL), is proposed. The key to AdVIL is double variational trick that approximates the negative free energy and the log partition function separately. A formal convergence theorem, which provides insights for implementation, is established for AdVIL. Empiri- cal results show that AdVIL can deal with a broad family of MRFs in a fully black-box boo manner and outperforms both the standard contrastive divergence method and the black-box NVIL algorithm.
Though AdVIL shows promising results, we emphasize that the black-box learning and inference of the MRFs are far from completely solved, especially on high-dimensional data. The two intractability
8

---

Published as a conference paper at ICLR 2020
problems of MRFs are distinct since the posterior of the latent variables is local in terms of but the partition function is global by integrating out v. The additional integral makes estimating the partition function much more challenging. In AdVIL, simply increasing the number of updates of the decoder to obtaín a tighter estimate of the partition function on high-dimensional data can be expensive. A potential future work to avoid the problem is adopting recent advances on non-convex optimization (Dauphin et al. [2014] Reddi et al., 2016) Wang et al. 2017) to accelerate the inner loop optimization. We conjecture that AdVIL comparable CD RBM and superior VCD in DBM on larger datasets if AdLIL can be trained to nearly converge based on our current results.
ACKNOWLEDGEMENTS
This work was supported by the National Key Research and Development Program of China (No. 70077940,0))))), NSFC Projects (Nos. 61620106010, U19B2034, U1811461), Beijing NSF Project (No. L172037), Beijing Academy of Artificial Intelligence (BAAI), Tsinghua-Huawei Joint Research Program, grant from Tsinghua Institute for Guo Qiang, Tiangong Institute for Intelligent Computing, the JP Morgan Faculty Research Program and the NVIDIA NVAIL Program with GPU/DGX Acceleration. C. Li was supported by the Chinese postdoctoral innovative talent support program and Shuimu Tsinghua Scholar.
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. TensorFlow: system for large-scale machine learning. 2016.
David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A learning algorithm for boltzmann machines. Cognitive science, 11):1177,1,, 1985.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Bob Carpenter, Andrew Gelman, Matthew D Hoffman, Daniel Lee, Ben Goodrich, Michael Be- tancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. Stan: A probabilistic programming language. Journal of statistical software, 76(1). 2017.
Kyung Hyun Cho, Tapani Raiko, and Alexander Ilin. Gaussian-bernoull deep boltzmann machine. In Neural Networks (IJCNN), The 2013 International Joint Conference on, pp. 1-7. IEEE, 2013.
KyungHyun Cho, Alexander Ilin, and Tapani Raiko. Improved learning of gaussian- bernoulll restricted boltzmann machines. In International conference on artificial neural networks, pp. 10-17. Springer, 2011.
Zihang Dai, Amjad Almahairi, Philip Bachman, Eduard Hovy, and Aaron Courville. Calibrating energy-based generative adversarial networks. arXiv preprint arXiv: 2017.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Advances in neural information processing systems, pp. 2933 2941, 2014.
Dua Dheeru and Taniskidou E Karra. UCI machine learning repository, 2017. URL http://
archive. ies..cs... ius.uci.............. edu/ml
Jeff Donahue, Philipp Krähenbühl, and Trevor Darrell. Adversarial feature learning. arXiv preprint arXiv:1605.09782. 2016.
Vincent Dumoulin, Ishmael Belghazi, Ben Poole, Olivier Mastropietro, Alex Lamb, Martin Arjovsky, and Aaron Courville. Adversarially learned inference. arXiv preprint arXiv: 1606, 00704, 2016.

---

Published as a conference paper at ICLR 2020
Chelsea Finn, Paul Christiano, Pieter Abbeel, and Sergey Levine. A connection between generative adversarial networks, inverse reinforcement learning, and energy- based models. arXiv preprint arXiv:1611.03882. 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- lion processing systems, pp. 2672-2680, 2014.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge to a local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626 66666 2017.
Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771-1800 2002.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):5045507, 2006.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv:1611.00 1.00111114444 144, 2016.
Michael Jordan, Zoubin Ghahramani, Tommi Jaakkola, and Lawrence Saul. An introduction variational methods for graphical models. Machine learning, 37(2):183-22 233, 1999.
Taesup Kim and Yoshua Bengio. Deep directed generative models with energy-based probability estimation. arXiv preprint arXiv: /606. 03439, 2016.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Diederik P Kingma and Max Welling. arXiv:1312.6114 2013.
Auto-encoding variational bayes.
arXiv preprint
Philipp Krähenbühl and Vladlen Koltun. Efficient inference in fully connected crfs with gaussian edge potentials. In Advances in neural information processing systems, pp. 109-117, 2011.
Volodymyr Kuleshov and Stefano Ermon. Neural variational inference and learning in undirected graphical models. In Advances in Neural Information Processing Systems, pp. 6734-6743, 2017.
John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. 2001.
Hugo Larochelle and lain Murray. The neural autoregressive distribution estimator. The Proceed-
ings of the 14th International Conference Artificial Intelligence and Statistics, volume 15 of JMLR: W&CP, pp. 29-37, 2011.
Qiang Liu and Dilin Wang. Learning deep energy models: Contrastive divergence vs. amortized mle. arXiv preprint arXiv: 100011007777777 2017.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.000 2016.
Xiao-Li Meng and Wing Hung Wong. Simulating ratios of normalizing constants via a simple identity: a theoretical exploration. Statistica Sinica, pp. 831-860, 1996.
Andriy Mnih and Karol Gregor. Neural variational inference and learning in belief networks. arXiv preprint 1402v:1402.00334 2014.
Radford M Neal. Probabilistic inference using markov chain monte carlo methods. 1993.
Radford M Neal. Annealed importance sampling, Statistics and computing, 1 1152): 139, 2001.
Jiquan Ngiam, Zhenghao Chen. Pang W Koh, and Andrew Y Ng. Learning deep energy models. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 1105-1112, 2011.
10

---

Published as a conference paper at ICLR 2020
Rajesh Ranganath, Sean Gerrish, and David Blei. Black box variational inference. In Artificial Intelligence and Statistics, pp. 814-822, 2014.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp. 314-323, 2016.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. arXiv preprint arXi::140..4082, 2014.
Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky, and Martin Szummer. Optimizing binary mrfs via extended roof duality. 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2007.
Ruslan Salakhutdinov and Geoffrey Hinton. Deep Boltzmann machines. In Proceedings of the twelfth international conference artificial intelligence and statistics, 2009.
Ruslan Salakhutdinov and Hugo Larochelle. Efficient learning of deep Boltzmann machines. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp- 693-700, 2010.
Ruslan Salakhutdinov and lain Murray, On the quantitative analysis of deep belief networks. In Proceedings of the 25th international conference on Machine learning. pp. 372-879. ACM, 2008.
John Schulman, Nicolas Heess, Theophane Weber, and Pieter Abbeel. Gradient estimation using stochastic computation graphs. In Advances in Neural Information Processing Systems, pp. 3528 3536, 2015.
Tijmen Tieleman. Training restricted boltzmann machines using approximations to the likelihood gradient. In Proceedings of the 25th international conference on Machine learning, pp. 1064-1071. ACM, 2008.
Martin Wainwright and Michael Jordan. Log- Log-determinant relaxation for approximate inference in discrete markov random fields. IEEE transactions on signal processing, 54(6):2099-1199, 2006.
Martin Wainwright, Tommi S Jaakkola, and Alan S Willsky. A new class of upper bounds on the log partition function. IEEE Transactions on Information Theory. 5177):2313-2335, 2005.
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2) 2017.
Max Welling and Geoffrey E Hinton. A new learning algorithm for mean field boltzmann machines. In International Conference on Artificial Neural Networks, pp. 351-357. Springer, 2002.
Max Welling and Charles A Sutton. Learning in markov random fields with contrastive free energies. In AISTAT'S Citeseer, 2005.
John Winn and Christopher M Bishop. Variational message passing. Journal of Machine Learning Research, 6(Apr):661-694 2005.
Shuangfei Zhai, Yu Cheng. Rogerio Feris, and Zhongfei Zhang. Generative adversarial networks as variational training of energy based models. arXiv preprint arXiv:1611.01799 2016.
A DERIVATION OF THE OBJECTIVE FUNCTION
Here we derive the objective function of AdVIL in detail. Let 0, and vé denote the trainable parameters in the MRF, the variational encoder and the variational decoder, respectively. The first variational trick bounds the free energy as follows:
((0) = -Epp()) log( - -((.A)) + log 2
E(v,h)
--Epo()) logl Q(hlo) Q(hlv) dhl + log Z
< (pp(oiQ(())) (E(u, + log Qhhlv)) - log Z = L)(0,
11

---

Published as a conference paper at ICLR 2020
where the bound is derived via applying the Jensen inequality and the equality holds if and only if Q(h/v) = P(hlv) for all v.
The second variational trick bounds the log partition function follows:
(0( = (p(())(()))) [8(u, h) + log (hhw)) - log( S.J. J E(v.)) dudh)
(P(())(()))) [E h) + log Q(h[v]] - log( 1. q(,,h)
E(v,A)
g(o, h) dudh)
E(o,h) log( g(v, h))
(Pp(v)Q(M))) [E(u, (E( h) log (hhuv)] (v,h)
Tenergy term
eatropy term
energy torm
catropy term
(P
E(u,)) + log Q(hvv)
E(u, h))
log q(v, h) Negative Phase
Positive Phase
= C2(0,, (,(0,,,00 0, s))
where the bound also derived via applying the Jensen inequality and the equality holds if and only if q(, h)) P(u, h).
To enhance the expressive power of the variational decoder, we introduce an auxiliary variable and define qu, h) I,, ((2 (()))(h)) ( (t))))dz which makes the entropy term in the negative phase intractable. To address the problem, we propose the third variational approximation. First, we can decompose the entropy of q(v,, h) gi log ((,,)) h) - Eey(,,)) log q(v) h) ( log (h)) and we only need to approximate (,) log (h)). However, simply applying the standard variational trick as above, we get an upper bound as follows:
(n) log (h)) -Eu(h) log / q(h, 2)dz
- log r(zlh) g(h,
dz
r(2(h)
[(hh, r(2 ())
-Eu(M)(((())) log
which is not satisfactory because the optimization problem will be minp ming max, min,. Instead, derive lower bound as follows:
(ky log (h))
Ey(e) log (hh) (h.).) log ((((h) (,,,.)) log ((2(h)
Ey,,,)) log {hh, 2) E,(h,)) logg(2//1)))
((1,2)
Ey(hh.)) log
+ +Dxx((((2()))><((1))
r(z(h)
(h,,)))) log q(h, 2)
r(2(h)
where D (.1-)- denotes the KL-divergence and the equality holds if and only if r((/h) g(2(h) for all h. The difference between the two bounds is that the expectation is taken over ((hrr==)h (=]h) the upper bound while over y(h, z) in the lower bound. Using the lower bound, the optimization problem will be mine ming max, max,,
B FORMAL TRAINING PROCEDURE
The formal training procedure of AdVIL is presented in Algorithm 1
12

---

Published as a conference paper at ICLR 2020
Algorithm I Adversarial variational inference and learning by stochastic gradient descent
Input: Constants K1 and K2, learning rate schemes a and 7, randomly initialized 8, Φ and
2: repeat
3:
ior K1 do
4: Sample batch of (u, h, 2) ~ q(v, 2)
5: Estimate the objective of and r according to Eqn. (11 and the negative phase in Eqn.
6: Update v to maximize the objective according to
7:
end for
8:
for L...,, do
9:
Sample batch of hv, Po(o)Q(Mlp) Estimate the objective of according to the positive phase in Eqn. (8)
10:
11:
Update & to minimize the objective according to end for
13:
Sample a batch of (v, h) ~ (b(v))((()) and another batch of (u, /t) k(v,h)
Estimate the objective of P according to Eqn. (8)
15:
Update 9 to minimize the objective according to
until Convergence or reaching certain threshold
C DETAILED THEORETICAL ANALYSIS
For simplicity, we consider discrete v and (e.g., in an RBM) and the analysis can be extended the continuous cases, We assume E {0,1) 1 and h E {0, 1]dh, where d, and d, are the dimensions of the visible and latent variables respectively.
ANALYSIS IN THE NONPARAMETRIS CASE
We first analyze the nonparametric
in Proposition aas follows.
Proposition 1. For any P(v, h.) exp(- (v, h))/2, L2(0, á, 1/) is tight estimate of the negative log-likelihood of P(v), under the following assumptions
1. (hlv) and q(v,h) are nonparametric.
2. The inner optimization over Qhlvv) and q(v, h) can get their optima.
Proof. Given P(v, hi,, i.e., E(v, h), to find q² (v, h), we optimize L2 over {g(v, hile e {0, 1J4 h E {0, 1 (d (we will use a shortcut {q(v, h)} for simplicity). The optimization problem is equivalent
to:
min Σ (u, [E(v, h) log (v,
{g(o)h)
w.h
subject to:
Σ quu, h) = 1,
a,h
glv. h) 2 0, Vo,h. h.
Note that the objective function convex since Hessian matrix is positive semi-definite. Besides, the constraints are linear. Therefore, it is convex optimization problem. Further, we can verify that the Slater's condition (Boyd Vandenberghe (004)) holds when q is uniform and then the strong duality holds. Then, we can the KKT conditions to solve the optimization problem.
The Lagrangian G((a(r, h)}, X, (u(v,h)) is:
Σ gl, M) [E(u, h) + log ((v, M)] + X X (). v.h
-1
Σ p(e, h)g(o,)) v.h
e.h
where À and (n(v, hi} the associated Lagrange multipliers.
To satisfy the stationarity, we take gradients with respect to q(v, h) for all (v. h) and get:
[E(v, h) log 9" ("(', h) + 1] + ((v, h) 0,
13

---

Published as a conference paper at ICLR 2020
which implies
(xp(-E((;;) - -1))-(11-0 (1+ + (((e,, (((o
According to the complementary slackness, have p(v, h/ggggggg (v, h) = 0, h,
which implies ylv, h) 0, Vu, h, since q" h) 0, Ve, h.
To satisfy the primal equality constraint, we have
(v, -===en Exxp(-E(o,t) -Ssptti)_))))) (1) =1,
n.h
which implies
exp(-E(v,,))
9" h)
Vl,,
Eve exp(-E(e', (())
To find (hlo),, we optimize L2 over (Q(hl))lv E (0,1)d h E {0, 1)dh du (we will use shortcut {Q(1l)) for simplicity). The optimization problem is equivalent to:
min (Q())())
Σ Po(u)) Q(hle) [E(v, + log ((h[v)]
subject to:
Σ Q(1uv) = 1, Vu,
Q(huu) 2 0, Vu, h.
Similar to the above procedure, get
exp( - E(v, h))
(h|pe) Σn
P(hlu), Vv,h.
h())
Under the assumptions that (1) (hlvv) and g(v, h) are nonparametric, and (2) the inner optimization over e and can get the optimum, the optimal variational distributions P(u, h) and P(hlv) can be obtained. Plugging them back into C2, we get
L2 (Po())((M))) [E(,,)) log P(N|v)] EPp(,) [8(u, h) log P(u,
(PP())
log Σ e E((sh)
+ +Ppoo,) [log 2]
Erp(1) [F()]] log C.
Remark Similar to Theorem in (Goodfellow et al., 2014). Proposition]] I is under the nonparametric assumption, which is relaxed in following analysis. Namely, will consider more practical cases where qu, h) may not be exactly the same as P(u, h) during training.
C.2 MAIN CONVERGENCE THEOREM
For convenience, summarize the training dynamics of Algorithm with K; K₂ and the exact gradients (not the stochastic ones), as follows:
θC, (0 2r v2x)
a 4/k + ap
2C Ōk. vk++1)
Φ141 dy 7
Ox+1 = 0g - DC2(0en Øk. vb+1)
(13)
00
where = 1,2, We will prove that even though we are optimizing (0 o, v)), (0s, Φx) converges stationary point of (0, σ) under certain conditions. To establish this, we first prove that the angle between (C2(0,).0) and (0.0) are sufficiently positive if quv h) and P(v, h) satisfy certain 26 conditions, summarized in Lemma
86
14

---

Published as a conference paper at ICLR 2020
Lemma 1. For any (6, there exists symmerric positive definite matrix H such that
(C2
80
H @C1(0.6) under the assumption:
En 8(v, h1) (E(u,h)
00 ||2 < (C,(0.4) ||2 if
_C1(0.0)
1|2 > 0 and
80
00
86
(e(e.)) |I 0(v, h)
1a 0
(0,(0.)) de
laa O, where δ(v, h) - (e,, h) - P(v, h).
Proof. According to the Cauchy-Schwarr Schwarz inequality, we have
@Li(0, Φ)
(E(v,h) h),
@C1 Φ)
8E(v, h)
Σ
8(v,h) h)
1/2 Σ
8(0, h)
11e.
00
00
00
v,h
v.h
If
(0. 89
2
O. according to the assumption
Σ u. 6(v, h)
30
1|2
(8.6)
2. we have
80
80
aC, (0, Φ)
@E(u, h),
(0, Φ)
8L (0, の)
6(v, h))
00
00
00
00
00
v.h
which implies that
1 Φ)
(L1
0E ht)
Σ o(v h))
> 0.
00 00
00
According to the definitions of (0, Φ) and C2(0, Φ, v²), we have
(6, Φ)
(0 h)
8(v,h) h)
00
a0
v.h
Σ (Po())Q(M)v)) Pmu, h)] (E h)
8E h)
Σl(0,, h) - P(v, h)]
00
08
v.h
v,h
(E h)
aL2(0, db 1))
Σ (Pb(t)Q(M))) ((w,))
00
00
w.h
which implies that
aL, (0, (0, v)
> 0.
00
00
Equivalently, there exists symmetric positive definite matrix H such that 8C2(0.0.)) H
16,10,0) (0.0) 80
Note that this also holds when 00
||
||2 O (i.e.,
(Lr(9.d) = 0) because || 80
||2 S
00
[aC((000) (0.0) 112 + +II v.A 5(v,
(e.h))
1l2 (i.e., (0, 0), according to the assumption.
00
a6
8e
Remark Lemma D assumes that q(v, h) and P(e. h) are sufficiently close, which is encouraged by choosing a sufficiently powerful family of q(u, h) and updating &i multiple times per update of 0, i.e. K1 > 1. If Lemma Tholds, optimizing L2 ø, v)) with respect to 0 will decrease L, Φ) in
expectation with sufficiently small stepsize. Also note that for any (0, v)). (L2(0.0.0) (C,(0,0) de
and therefore, optimizing (2 de vb) with respect to & will decrease Li (0, Φ) in expectation with sufficiently small stepsize.
Based on Lemma and other commonly used assumptions in the analysis of stochastic gradient descent (Bottou et al. 2018), Algorithm I converges to stationary point of (0, Φ), as stated in Theorem
Theorem 1. Solving the optimization problem in Eqn.
99) using stochastic gradient descent according
to Algorithm 1 then
0C (Os, Φx)
lim E[]
0,
k
00
under the following assumptions.
1. The condition of Corollary 4.12 in (Bottou et al. with respect 0, & and vb.
2018 : Cz(0, d. v) is twice differentiable
15

---

Published as a conference paper at ICLR 2020
2. Assumption 4.1 in (Bottou al. 2018 the gradients of C2(0.0, 4)) with respect to 6, and vb are Lipschitz.
3. Assumption 4.3 in (Bottou et al. 2018): the first and second moments of the stochastic gradients are bounded by the expected gradients.
4. The stepsize satisfies the diminishing condition (Bottou et al. 2018 i.e. ax 7/k Σk=1 cc, Ek=1 rh <c.
5. The condition of Lemmal 7 holds in each step k. Therefore,
@C2(0k. Øk vx+1)
HN dL, Φx)
wk, 3H,,
00
00
Proof. See Corollary 4.12 in (Bottou et al. 2018).
Remark Assumption 1 and Assumption in Theorem are ensured because we use the sigmoid and tanh activation functions. Assumption 3 and Assumption 4 in Theorem [ ensured by the sampling and learning rate schemes of the stochastic gradient descent. Assumption than the nonparametric assumption of Proposition [ but still requires large K1. Also note that the statement of converging to L1 in Theorem Tis is weaker than that in Proposition
Theorem i is weaker
C.3 COMPLEMENTARY CONVERGENCE THEOREM
Heusel al. (017)) propose a two-time scale update rule train minimax optimization problems with a convergence guarantee even using K₁ = 1. AdVIL converges if using the same training
method as in (Huuell al. (017). which summarized in Proposition
Proposition 2. AdVIL trained with two-time scale update rule (Heusel et al. 2017 converges stationary local Nash equilibrium almost surely under the following assumptions.
1. The gradients with respect to and vp are Lipschitz.
2. Σ. on xc, Ex az xo, Ex 7h 00, 0o, En 2h < 0c,7% = olax).
3. The stochastic gradient errors are bounded in expectation.
4. For each 0, the ordinary differentiable equation corresponding to Equation 13 has a local asymptotically stable attractor within domain of attraction such that the attractor is Lipschitz. Similar assumptions are required for á and tb
5. sup |00|| < oc, supk ||/x|l < oc, sups || < oc.
Proof. See Theorem in (Heusel et al. 2017).
Remark Compared to Theorem Proposition ensures the convergence of AdVIL without assuming q(v,h) h) is sufficiently close to P(v, h) in each step. However, two time-sclac update rule (Heusel al. 2017) is required satisfy Assumption and extra weight decay terms are needed to satisfy Assumption 4. Further, the convergence point is not necessarily stationary point of L (1 ().
D DATASETS AND EXPERIMENTAL SETTINGS
We evaluate our method on the Digits datase the UCI binary databases and the Frey faces datasets The information of the datasets summarized in Tab, B We implement our model using the TensorFlow (Abadi et al. 2016) library. In all experiments, q and are updated 100 times per update We use the ADAM (Kingma Bal 2014) optimizer with
of and Q, i.e. K1 100 and K₂ the learning rate 0.0003, the moving average ratios 31 0.5 and B2 0.999, and the batch size of 500. We use continuous z and the sigmoid activation function. All these hyperparameters are
walcarn.datasets..ee Bogiisshtml##skleeee wtt.skkaaaa..atassss... digits
16

---

Published as a conference paper at ICLR 2020
Table 3: Dimensions of the visible variables and sizes of the train, validation and test splits.
Datasets
# visible
Train
Valid.
Test
Digits
64
1438
359
Adult
123
5,000
1414
26147
Connect4
126
16,000
4000
47557
DNA
180
1400
600
1186
Mushrooms
112
2,000
500
5624
NIPS-0-12
500
400
100
1240
OCR-letters
128
32,152
10,000
10,000
RCVI
150
40,000
10,000
150,000
Frey faces
560
1965
Table 4: The model structures in RBM experiments.
Digits
Adult
Connect4
DNA
Mushrooms
NIPS-O-12
Ocr-letters
RCV1
dimension
15
15
15
15
15
50
15
15
dimension of h
50
50
50
50
50
200
50
50
dimension 64
123
126
180
112
500
128
150
set according to the validation performance of an RBM the Digits dataset and fixed throughout the paper unless otherwise stated. The sizes of the variational distributions depend on the structure the MRF and are chosen according to the validation performance. The model structures in RBM and DBM experiments are summarized Tab. and Tab. respectively.
In two-layer DBM with variables h and h2. we both AdVIL and VCD. The decoder for AdVIL the inverse of the encoder with one extra layer the top, namely q(v, h1, h2) sqq())/))(() ( 2)9(2)d2. (bg))(h2))((2)ddz In our implementation, both AdVIL and VCD exploits that and h2 are conditionally independent given h1 The layer- wise structure potentially benefits the training of both methods. Nevertheless, in principle, any differentiable variational distributions be used in AdVIL and a systematical study is left for future work.
encoder
Q(h ( (()2(())))))
The authors of NVIL (Kllehhvv & Ermon 2017) propose two variants. The first one employs mixture of Bernoulli q. The second one involves auxiliary variables and employs neural network as q. Both variants scale up to an RBM of at most 64 visible units as reported in their paper (Kuleshoy Ermon 2017). For fair comparison, of NVIL and our settings based on their code and choose the best configuration. In this setting, the first variant of NVIL still fails scale up to larger datasets and the version of the second variant shares the same key hyperparameters as AdVIL, including K₁ 100 and batch size of 500.
carefully perform grid search over the default settings
E
MORE RESULTS
E. EMPIRICAL VERIFICATION OF THEOREM
We empirically test the assumption Σ.,, 8(v, h) @E(u.h) 8C, (0u.bu) for k < 10000, where
||2 exactly requires summing over and l and therefore train small RBM where the dimensions of h and are 4 on synthetic dataset. The data distribution is a categorical distribution over (0, 1] and it is sampled from a Dirichlet distribution with all concentration parameters be one. We get 10,000. 1.000 and 1,000 ii.d samples from the categorical distribution for training, validation and test respectively. We find Ki 10 is sufficient in this case.
8(v, h) g(v, h) P(v, ft). Note that computing BC, (0..6u)
17

---

Published as a conference paper at ICLR 2020
Table 5: The model structures in DBM experiments.
Digits
Adult
Connect4
DNA
Mushrooms
NIPS-0-12 12
Ocr-letters
RCVI
dimension of
15
15
15
15
50
15
15
dimension of h1
50
50
50
50
50
200
50
50
dimension of h2
50
50
50
50
50
200
50
50
dimension of 64
123
126
180
112
500
128
150
Right hand side condition Left hand side the condition
0.5
Log likellhood
Evidence lower bound
7500
5000 Iterations
7500
10000
Iterations
(a)
(b)
Figure 5: (a) shows that |1 ōv, h) 8E(e.h) 86, ||2 (in red) is less than || aC, (8 (b)))) 89, ||2 (in blue) during
training. (b) shows that both the evidence lower bound (ELBO) -2, (in red) and the log likelihood -C (in blue) converge gradually. The ELBO may be slightly over estimated because we approximate the first term in Eqn. 7 by Monte Carlo estimate.
The results are shown Fig. can be seen that a decoder with neural networks and auxiliary variables are sufficiently powerful to track the model distribution and therefore Assumption 5 in Theorem [ hholds in 10,000 steps. Besides, the model converges gradually, which agrees with our convergence analysis. The gap between the red curve in Fig. (a) and the horizontal axis can be further reduced by using more powerful q(, (e,A h) and advanced optimization techniques for q(v, h).
Theoretically, how Lemma holds the number of variables increases is not clear. Intuitively, agree that it may get harder to satisfy this condition in a high-dimensional space. However, it is still possible with advanced optimization methods because the MRF is randomly initialized and learned gradually, and the variational decoder is trained to track the MRF (based on an old version of the decoder) after every update of the MRF. Empirically, computing both sides of the condition requires the value of the partition function, which is as hard as training the MRF. Therefore, verifying this dimeeniimnii case highly nontrivial.
condition during training
E.2 SAMPLES IN RBM
We present the samples from the RBM P and the decoder g in Fig. 6 In this case, number the hidden units to 50 and other settings remain the same as in 5.1l The first column demonstrates that the decoder from the decoder are obtained from efficient ancestral sampling but those from the RBM is obtained by Gibbs sampling after 100,000 burn-in steps. The second column shows that H(Q) is removed, both models collapse to certain mode of the data. The third column shows that if H(() is removed, both models fail generate meaningful digits. These results demonstrate the importance of the entropy terms and the necessity of approximating H(g) in principled way.
the
good approximate sampler for the RBM. Note that the samples
E.3 ADVIL WITH AN AUTOREGRESSIVE PRIOR
Here we present the results of AdVIL with a neural autoregressive distribution estimator (NADE) (I (Larochelle & Murray 2011) the prior on the Digits dataset. We the same RBM in Sec. 5.1
18

---

Published as a conference paper at ICLR 2020
(a) normal (b) w.o. H(Q) (c) w.o. H(g) (d) normal
(c) 9 W.O. H(Q)
w.o. H(g)
Figure 6: (a-c) Samples from the RBM in different settings. (d-f) Samples from the decoder in different settings. We present the mean of for better visualization in all settings.
37
NLL on test data, K1=5
NLL on test data
37
31
28
28
25
25
0
10000
20000 Iterations
30000
0
10000 20000 30000 40000 Iterations
(a) AdVIL with NADE decoder
(b) AdVIL with hierarchial decoder
Figure 7: AdVIL with two types decoders. We set K2 = 5 in the NADE decoder and K2 = 100 in the hierarchical decoder. The two models have a similar model capacity and training time.
The dimension the latent units in NADE is 15, which is the same as the dimension of the auxiliary variables in the hierarchical decoder presented in Sec. 3.3
Compared to the hierarchical decoder, the NADE decoder has tractable entropy and hence does not require r(2(h). However, getting samples from NADE is slow while AdVII requires samples during training. Therefore, K₁ = 5 for the NADE decoder has similar training cost as the hicrarchical decoder.
Fig. 7 compares the two decoders. AdVIL with the NADE decoder achieves a slightly worse and unstable result.
E.4 LEARNING CURVES AND ANALYSIS IN DBM
We plot the learning curves of AdVIL and VCD in DBM, as shown in Fig. AdVIL achieves better result than VCD, which agrees with the quantitative results in Tab. Note that report the test NLL results in Tab. according to the best validation performance.
There are two types of biases introduced by using Qh, fulw)) Q( Q1)((h)))) VCD. The first type of bias is introduced by using the approximate free energy in both the positive phase and the negative phase (See Eqn. (3) and Eqn. (4 The second bias is introduced by the usage of Q(ha (w) to approximate P(h,|e) [w) in the Gibbs sampling procedure to approximate the negative phase in Eqn. (4). The influence of the two types of biases on the negative phase is not clear, which can potentially explain the relatively inferior performance of VCD in DBM. In contrast, AdVIL approximates the negative phase by introducing one bias (i.e., the approximation error between (v, h) and P(v, h)), whose effect on learning theoretically characterized by Theorem 1. The above results and analysis essentially demonstrate the advantages of AdVIL over CD-based methods in DBM and the importance of developing black-box inference and learning algorithms for general MRFs.
19

---

Published as a conference paper at ICLR 2020
Test NLL AdVIL
Test NLL VCD
35
30
30
25
25
4500
9000 13500 18000
0
20000 40000 60000 80000
Iterations
Iterations
(a) AdVIL
(b) VCD
Figure 8: DBM results of AdVIL and VCD on the Digits dataset. The curve of AdVIL is less stable due to the presence of the minimax optimization problem but AdVIL achieves better performance.
Table 6:
The AIS results of NVIL and AdVIL in RBM with the means and standard deviations. The results are averaged over three runs with different random seeds.
Method
Digits
Adult
Connect4
DNA
Mushrooms
NIPS-0-12
Ocr-letters
RCVI
NVIL-mean
27.36
20.05
24.77
-97.71
-99.28
2290.01
447.56
-00447
NVIL-std
0.13
0.27
0.61
0.12
0.31
2.68
0.14
0.09
AdVIL-mean
-26.34
199229
21.95
-97.59
-19.59
-276.42
-45.64
-50.22
AdVIL-std
0.02
0.07
1.04
0.10
2.01
0.21
0.34
0.06
E.5
AIS RESULTS WITH STANDARD DEVIATIONS
The AIS results in RBM and RBM with the means and standard deviations are shown in Tab, and Tab. respectively.
Table 7: The AIS results VCD-1 and AdVIL in DBM with the means and standard deviations. The results averaged over three runs with different random seeds.
Method
Digits
Adult
Connect4
DNA
Mushrooms
NIPS-0-12
Ocr-letters
RCVI
VCD-mean
28.49
22.26
26.79
97.59
-23.15
-35.266
45.77
50.83
VCD-std
0.47
0.51
1.42
0.03
1.42
34.70
1.15
0.62
AdVIL-mman
22.
20.29
-66.44
-99.40
-21.11
-287.15
-48.38
-51.02
AdVIL-std
0.44
0.24
1.50
0.71
0.40
0.63
1.32
0.42
20


Reviews:
[{"review_id": "BkxP9JsX9H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a black-box style learning algorithm for Markov Random Fields (MRF). The approach doubles down on the variational approach with variational approximations for both the positive phase and negative phase of the log likelihood objective function. For the negative phase, the authors use two separate variational approximations, one of which involves the modeling of the latent variable prior under the approximating distribution,\n\nThe approach is novel, as far as I know, though not particularly so, and I view this as one of the weak point of the paper. That said, it does seems like a fairly creative combination of existing approaches. As others have found in the past, a variational approximation to the partition function contribution to the loss function (i.e. the negative phase) results in the loss of the variational lower bound on log likelihood and the connection between the resulting approximation and the log likelihood becomes unclear. To deal with this issue, the authors argue (in Lemma 1) that the gradient of their approximate objective is at least in the same direction as the ELBO (lower bound) objective. The result is fairly obvious, but the conditions for validity have interesting consequences for the training algorithm, as it relates the approximation error to the norm of the gradient of the ELBO loss.\n\nI have a minor issue with the discussion (in the last paragraph of sec. 3.2) stating that the theoretical statement of the proposed objective relies on a much weaker assumption than the nonparametric assumption made in the theoretical justification of GANs. While I agree with the statement as such, the GAN development makes a stronger statement about the nature of the learning trajectory. Specifically, it states that the generator is minimizing a Jenson-Shannon divergence which has a fixed point at the true data density. In the current development, Theorem 1 only states that the optimization process will converge to the stationary points of the approximate ELBO objective (L1 in the paper's notation).\n\nClarity: I found the paper to be very well written with a clear exposition of the material and sound development of the technical details. \n\nRelevance and Significance: This paper is highly relevant to the ICLR community and -- to the extent that one believes that training and inference in MRFs is important -- also significant. One this last point, it seems ironic to me that the proposed strategy for training the MRF is through the use of three separate directed graphical models (an encoder q(h | x),  a decoder and a VAE to model the approximate prior over the latents h). In most modeling situations, one would simply impose the directed graphical model directly and skip the formalization in terms of an MRF. I would appreciate a more forceful motivation of the relevance of MRFs rather than just stating it as a important model with applications. What is unique\nabout the MRF formalism that -- for practical applications -- could not be effectively captured in a directed graphical model?\nI note that I am aware of the theoretical representation differences between directed and undirected models, I am wondering how these differences actually matter in practical applications at scale.\n\nExperiments: The authors show the empirical advantages offered by the proposed method over the existing literature. I was surprised not to see how this model performs on the binarized MNIST dataset, and would like to see that result as well as CIFAR likelihood.  MNIST, in particular, is a well studied dataset that many readers will be able to easily interpret. Its absence seems like a serious omission.\n\nWhat is meant by \"RBM loss\" in Fig. 2(d), I do not see this defined? \n\nI am somewhat alarmed at the use of 100 updates of the joint model q(v,h) (K1 = 100) for every update of the other parameters. For larger scale domains, I fear this could become an important obstacle to effective model training. The comparison to PCD-1 in Fig. 3 seems a bit unfair in that the learning curve ends at 8000 iterations, while PCD-1 continues to\nimprove NLL. I would like to see this curve extended until we start to see signs of overfitting. Perhaps PCD-1 results in performance that is far better than AdVIL. I would also like to see a comparison to CD-k, which often outperforms PCD-k. While I understand the stance taken by the authors that these methods leverage the tractability of the conditional\ndistributions, these strategies are sufficiently general to be considered widely applicable and a true competitor for AdVIL. \n\nWith respect to Deep Boltzmann Machine (DBM), I would prefer to see quantitative comparisons against published results. Here again, MNIST would be a useful dataset.  It seems as though, in the application of AdVIL to the DBM, the authors are exploiting the structure of the model in how they define their sampling procedure. Is that the case? More detail for this application of AdVIL would be nice. Also, I would like to see the test estimated NLL (via AIS) learning curves for VCD and AdVIL. Given the comparison to PCD in the RBM setting, I am somewhat surprised that AdVIL is so competitive with VCD in\nthe case of the DBM.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkx48mSRKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work proposes using variational distributions to model the model the inference of latent variables and model the partition function building on NVIL, thereby providing an algorithm that would work on general MRFs for both inference and learning. Since the two terms in the NLL are opposite in sign, it is a minimax operation and GAN like adversial training can be used. The paper shows providing tighter results to estimate the log partition function and comparisons on the digits dataset and Anneal importance sampling.\n\nThe paper builds on NVIL by using two variational distributions for the NLL and how to solve the parameter estimation problem. I think this strategy can be tested more extensively on more types of general MRFs and more rigourous experimentation and that the community will benefit from reading from these ideas. The paper contains some theory behind the work and experimental analysis of Advil including the sensitivity to parameters. Advil shows promise compared to the competing methods in some of the problems.\n\nQuestions and suggestions for improving the paper\n1. Is this applicable to multivalued nodes or just binary problems? Or are any modifications needed?\n2. Inference can be done in general using approximate methods like variational message passing, QBPO among others that don't depend on graph structures either, how does this work compared when those algorithms are used with simple gradient descent while training the parameters?\n3. The paper states that the algorithm is convergent if the variational encoder approximates the model well. How would you define good approximation?\n4. It would be good to add more details of how the GAN framework/adversial training is used.\n5. Would it be possible to compare Advil to ALI in some of the experiments?\n6. Fig. 2 d was not clear to me as why to expect the plot we see. The NLL flattens out with no progress.\n7. It would be helpful to the reader to understand the comparison using persistent contrastive divergence. Why is it not used in other experiments. The paper says the main comparison point is NVIL but different experiments either mention ALI, VCD or PCD which is confusing.\n8. It would be nice to see the time comparison between this learning parameters and other methods.\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJegMJ0hKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This manuscript proposes a new approach to fitting Markov Random Fields (MRFs).  The general structure of the algorithm is amenable to many MRF structures and can be fairly straightforwardly applied to learning on a wide variety of problems.  The theoretical analysis supports that the algorithm is reasonable.  Experimental results show strong results on several different MRF models, albeit on relatively small problems.\n\nI am giving this manuscript a weak accept.  The approach, to me, seems novel in fitting MRFs.  However, the theoretical claims and their limitations need to be more realistically discussed, and the empirical results need to be shown on larger and more complex datasets.\n\nFirst, on the empirical results, there is a large literature on fitting RBM models, including many on scaling to much larger models.  Given that AdVIL actually diverges on the logZ estimation as the number of iterations goes up makes me worry about the efficacy of this approach on larger RBMs (Figure 2 uses v=64 and h=15 while a common RBM on MNIST is v=784 and h=500, a huge difference in scale).  As a large literature shows that estimating partition functions or normalizing constants gets much harder as the dimensionality goes up, I worry about this strategy and I think the manuscript would be greatly enhanced by looking at more common model sizes from the ML literature.\n\nAlso, to me, the classic MCMC+SGD is as much a black box as the proposed technique.  I realize that many of the top performing MCMC adapt specifically to the problem, but much of this is transferable between systems and can be put in simple sampling schemes.  Table 1 should be updated to include these typical techniques, because it is not clear that the proposed system actually outperforms the typical PCD-1 scheme (especially given in Figure 3).  Or succinctly, it should be made clear why I should use this over an MCMC approach.\n\nTo address these concerns, I would like the authors to answer how their proposed algorithm works in larger MRFs and do a more complete analysis compared to more traditional strategies.\n\nSecond, the theoretical claims are nice, but the manuscript should be revised to address the limitations of the theory.  In particular, Lemma 1 is extremely strong, and I disagree with the assessment that it is \"much weaker\" than the typical nonparametric assumption.  It seems that as the optimization gets close to the solution, this is essentially the exact same condition.  The authors need to clarify how exactly this is different, and dive into the practical implementations.  This also seems like it would get increasingly difficult as the number of hidden and visible units increases, so they should address how this Lemma holds as the theory scales.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a black box algorithm for MRF training, utilizing a novel approach based on variational approximations of both the positive and negative phase terms of the log likelihood gradient (as R2 puts it, "a fairly creative combination of existing approaches"). 

Several technical and rhetorical points were raised by the reviewers, most of which seem to have been satisfactorily addressed, but all reviewers agreed that this was a good direction. The main weakness of the work is that the empirical work is very small scale, mainly due to the bottleneck imposed by an inner loop optimization of the variational distribution q(v, h). I believe it's important to note that most truly large scale results in the literature revolve around purely feedforward models that don't require expensive to compute approximations; that said, MNIST experiments would have been nice. 

Nevertheless, this work seems like a promising step on a difficult problem, and it seems that the ideas herein are worth disseminating, hopefully stimulating future work on rendering this procedure less expensive and more scalable.
Decision: Accept (Poster)