Monotone deep Boltzmann machines
Authors: Zhili Feng
Ezra Winston
J Zico Kolter
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Boltzmann machine
mean-field inference
deep equilibrium model

Abstract: Deep Boltzmann machines refer to deep multi-layered probabilistic models, governed by a pairwise energy function that describes the likelihood of all variables in the network. Due to the difficulty of inference in such systems, they have given way largely to \emph{restricted} deep Boltzmann machines (which do not permit intra-layer or skip connections). In this paper, we propose a class of model that allows for \emph{exact, efficient} mean-field inference and learning in \emph{general} deep Boltzmann machines.  To do so, we use the tools of the recently proposed monotone Deep Equilibrium (DEQ) Model, an implicit-depth deep network that always guarantees the existence and uniqueness of its fixed points.  We show that, for a class of general deep Boltzmann machine, the mean-field fixed point can be considered as the equivalent fixed point of a monotone DEQ, which gives us a recipe for deriving an efficient mean-field inference procedure with global convergence guarantees. In addition, we show that our procedure outperforms existing mean-field approximation methods while avoiding any issue of local optima. We apply this approach to simple deep convolutional Boltzmann architectures and demonstrate that it allows for tasks such as the joint completion and classification of images, all within a single deep probabilistic setting. 

Under review as a conference paper at ICLR 2022
MONOTONE DEEP BOLTZMANN MACHINES
Anonymous authors
Paper under double-blind review
ABSTRACT
Deep Boltzmann machines refer to deep multi- multi-layered probabilistic models, gov- erned by a pairwise energy function that describes the likelihood of all variables in the network. Due the difficulty of inference in such systems, they have given way largely to restricted deep Boltzmann machines (which do not permit intra- layer or skip connections). In this paper, we propose class of model that allows for exact, efficient mean-field inference and learning in general deep Boltzmann machines. To do so, we use the tools of the recently proposed monotone Deep Equilibrium (DEQ) Model, an implicit-depth deep network that always guaran- tees the existence and uniqueness of its fixed points. We show that, for class general deep Boltzmann machine, the mean-field fixed point can be considered as the equivalent fixed point of a monotone DEQ, which gives us a recipe for deriving efficient mean- mean-field inference procedure with global convergence guarantees. We apply this approach to simple deep convolutional Boltzmann architectures and demonstrate that it allows for tasks such the joint completion and classification of images, all within a single deep probabilistic setting.
INTRODUCTION
This paper considers (deep) Boltzmann machines, which are pairwise energy-based probabilistic models. Theses models specify a joint distribution over variables x given by the density
n
p(x) x exp
Σ (i.))E
x TT
Pajay
(1)
where each 21mm denotes discrete random variable over k; possible values, represented as a one- hot encoding x, E {0, 1 bbk;; denotes the set of edges in the model; tig E x represents pairwise potential; and b; E R represents unary potential. Depending on context, these models typically referred to pairwise Markov random fields (MRFs) (Koller & Friedman) 2009), or (potentially deep) Boltzmann machines (Goodfellow et al., 2016; Salakhutdinov & Hinton 2009) Hinton 2002). In the above setting each I; may represent an observed or unobserved value, and there can be substantial structure within the variables; for instance, the collection of variables x may (and indeed will, in the main settings we consider in this paper) consist of several different "layers" in joint convolutional structure, leading to the deep convolutional Boltzmann machine (Norouzi al. 2009).
In this paper, we propose new parameterization and algorithmic approach to approximate inference of these probabilistic models. There are two main contributions: First, we define generic param- eterization of the pairwise kernel function & that can represent a general Boltzmann machine. Our parametrization flexible enough to incorporate almost all operators and network topology, includ- ing fully-connected layers, convolution operators, and akip-connectionns the recently developed monotone DEQ (Winston & Kolter (020),, we constraint & to satisfy cer- tain monotonicity conditions through training and inference: this thereby assures that the mean-field approximation will always have a unique, globally-optimal fixed point under this parameterization. Second, although previous works (Krähenbühl & Koltun 2013 Baqué et al. 2016) have made ap- proaches to parallel mean-field updates, they either require strong conditions on Ø, or fail to con- verge the true mean-field distribution. We provide based upon a generic proximal operator, which is guaranteed to converge to the mean-field fixed point, even if applied in parallel to all random variables simultaneously. Although there is no exact
etc. Through the lens of
properly-damper mean meendfield update method,

---

Under review as a conference paper at ICLR 2022
Restricted Boltzmann machine
Restricted deep Boltzmann machine
General Boltzmann machine
Xhx
Xky
4 Ab
Xh.
L he
X
Figure I: Neural network topology of different Boltzmann machines. The general case a complete graph. Our proposed parameterization is equivalent a general Boltzmann machine. Technically in our setting the oo connections exist, but they are not updated due to the input injection.
closed form solution of this proximal operator, we derive a very efficient Newton-based implemen- tation. To estimate the parameters of model, follow the marginal-based loss minimization approach in Krähenbüül & Koltun (2013); Domke (2013), where the objective to directly maxi- mize the likelihood induced by the approximated mean-field distribution. Such approach grants us the ability to update parameters via taking gradient steps of the proposed mean-field iterations.
With the proposed approaches, we perform both learning and inference for deep convolutional, multi-resolution Boltzmann machine, and apply the network to model MNIST and CIFAR-10 1- pixels and their classes conditioned on partially observed images. Such joint probabilistic modelling allows us to simultaneously impute missing pixels and predict the class. While these are naturally a small- scale problem, we emphasize that performing joint probabilistic inference over a complete model of this type is relatively sigh-dimensional task as far as traditional mean-field inference is concerned. We also compare our inference method to previous ones and demonstrate different convergence properties of each. We conclude by highlighting limitations and directions for future work with the method.
2 BACKGROUND AND RELATED WORK
This paper builds upon three main avenues of work: 1) deep equilibrium models, especially their convergent version, the monotone DEQ: 2) the broad topic of energy-based deep model and Boltz- mann machines in particular; and 3) work on concave potentials and parallel methods for mean-field inference. We discuss each these below.
Equilibrium models and their provable convergence The DEQ model was first proposed by Bai et al. (2019). Based the observation that neural network -1+ a oW 2, Ux + b) with input injection x usually converges to a fixed point, they modeled an effectively infinite-depth network with input injection directly via its fixed point: z* oWW=* Ux b). Its backpropagation is done through the implicit function theorem and only requires constant memory. Bai et al. (2020) also showed that the multiscale DEQ models achieve near state-of- oftth--rt performances on many large-scale tasks. Winston & Kolter (2020) later presented parametrization of the DEQ (denoted as monDEQ) that guarantees provable convergence a unique fixed point, using monotone op- erator theory. Specifically, they parameterize W in way that / W N mī (called m-strongly monotone) is always satisfied during training for some m 0; they convert nonlinearities into prox- imal operators (which include ReLU, tanh, etc.), and show that using existing splitting methods like and Peaceman- Peaceman-Rachfor can provably find the unique fixed point.
Markoy random field (MRF) and its variants MRF is a form of energy-based model, which model joint probabilities of the form pa (z) = exp (x)) Zeo for an energy function Eg. A com- mon type of MRF is the Boltzmann machine, the most successful variant which the restricted Boltzmann machines (RBM) (Hinton, 2002) and its deep (multi-layer) variant (Salakhutdinov & Hinton 2009). Particularly, RBMs define Eg (v, h) -a
h Wh, where (W, b), is the set of visible variables, and h is the of latent variables. It is usually trained using the
2

---

Under review as a conference paper at ICLR 2022
contrastive-diverss divergence algorithm, and its inference be done efficiently by block mean- mean-field approximation. However, a particular restriction of RBMs is that there can be no intra-layer connec- tions, that is, each variable in (resp. h) is independent conditioned on h (resp. v). A deep RBM allows different layers of hidden nodes, but there cannot be intra-layer connections. By contrast, our formulation allows intra-layer connections and is therefore is more expressive in this respect. See fig. [ for the network topology of RBM, deep RBM, and general BM (we also use the term general deep BM interchangeably to emphasize the existence of deep structure). Wu al. (2016) proposed a deep parameterization of MRF, but their setting only considers grid of hidden variables and the connections among hidden units are restricted the neighboring nodes. Therefore, is special case of our parameterization (although their learning algorithm is orthogonal to ours). Numerous works also try to combine deep neural networks with conditional random fields (CRF)
(Krähenbühl & Koltun 2013 Zheng et al. 2015 Schwartz et al.) (017) These models either train pre-determined kernel as an RNN or use neural networks for producing either inputs or parameters of their CRFs.
Parallel and convergent mean-field is well-known that mean-field updates converge locally using a coordinate ascent algorithm (Blei et al. 2017). However, local convergence is only guaran- several teed if the update is applied sequentially. Nonetheless, several works have proposed techniques to parallelize updates. Krähenbühl & Koltun (2013) proposed a concave-convex procedure (CCCP) to minimize the KL divergence between the true distribution and the mean-field variational family. To achieve efficient inference, they use concave approximation to the pairwise kernel, and their fast update rule only converges if the kernel function is concave. Later, Baqqu et al.) (2016) derived a similar parallel damped forward iteration to ours that provably converges without the concave po- tential constraint. However, unlike our approach, they do not use parameterization which ensures global mean-field optimum, and their algorithm therefore may not converge to the actual fixed point of the mean-field updates. This is because Baqué et al. (0166) used the prox/ proximal operator (described below), whereas we derive the proxy operator to guarantee global convergence when doing mean-field updates in parallel. What's more, [Baqué et al. (2016) focused only on inference over prescribed potentials, and not on training the (fully parameterized) potentials as we do here. Lē-Huu & Alahari (2021) brought up generalized Frank-Wolfe based framework for mean field updates which include the methods proposed by [Baqué et al. (2016); Krähenbühl & Koltun (013). Their results only guarantee global convergence to a local optimal.
3 MONOTONE DEEP BOLTZMANN MACHINES AND APPROXIMATE INFERENCE
In this section, we present the main technical contributions of this work. We begin by presenting a parameterization of the pairwise potential in Boltzmann machine that guarantees the monotonicity condition. We then illustrate the connection between a (joint) mean-field inference fixed point and the fixed point of our monotone Boltzmann machine and discuss how deep structured networks can be implemented in this form practically; this establishes that, under the monotonicity conditions on Φ there exists unique globally-optimal mean-field fixed point. Finally, we present an efficient parallel method for computing this mean-field fixed point, again motivated by the machinery of monotone DEQs and operator splitting methods.
3.1 A MONOTONE PARAMETERIZATION OF GENERAL BOLTZMANN MACHINES
In this section, we show how to parameterize our probabilistic model in way that the pairwise potentials satisfy 1 - 4 2 ml, which will be used later to show the existence of a unique mean- field fixed point. Additionally, since o defines a graphical model that has no self-loop, we further require & to be a block hollow matrix (that is, the K; x K; diagonal blocks corresponding to each variable must be zero). While both these conditions on & are convex constraints, in practice it would be extremely difficult to project generic set of weights onto this constraint set under an ordinary parameterization of the network.
Thus, we instead advocate for a non-convex parameterization of the network weights, but one which guarantees that the monotonicity condition is always satisfied, without any constraint on the weights in the parameterization. Specifically, define the block matrix
A
A
Ag
An
(2)
3

---

Under review as a conference paper at ICLR 2022
with A, Rd matrices for each variables, and where d can be some arbitrarily chosen dimension. Then let A, be spectrally-normalizae version of A;
A; = A; min { V1 m/11A,,12,, 1}
(3)
i.., a version of A, normalized such that its largest singular value is at most v1 m (note that we can compute the spectral norm of A; as ||A l2 I| A.ll2 which involves computing the singular values of only & x k; matrix, and thus is very fast in practice). We define the A matrix analogously as the block version these normalized matrices.
Then propose to parameterize & as
4 blkdiag( Å ÁTÁ) AT Á
(4)
where bikdiag denotes the block diakonaa portion of the matrix along the h; x k; block. Put another way, this parameterizes as
A A
if
(5)
0
i-
As the following simple theorem shows, this parameterization guarantees both hollowness of the Φ matrix and monotonicity of ④, for any value of the A matrix.
Theorem 3.1. For any choice of parameters A, under the parametrization equation above, we have that 1) 4. 0 for all i ,....,,,, 1,, and 2) I + ml.
Proof. Block hollowness of the matrix follows immediately from construction. To establish mono- tonicity, note that
I- + ml = I + A A blkdiag( A A] = ml
= I blkdiag (Å" A) 2 ml
(6)
+ I A ł mI, Vi
| S /1 m, Vi.
This last property always holds by the construction of A,-
3.2 MEAN-FIRLD INFERENCE AS A MONOTONE DEQ
In this section, we formally present how to formulate the mean-field inference DEQ update. Recall from before that we are modelling a distribution of the form eq. (I). We are interested in approximating the conditional distribution p(x, x,)), where and h denote the observed and hidden variables respectively, with factored distribution g(xx)) = Ihe (xx)). Here, the standard mean-field updates (which minimize the KL divergence between gxx.) and p(x, (x.) over the single distribution q: (x;)) are given by the following equation,
(x;)) softmax
Σ (1)) +
where overloading notation slightly, we let (I,) denote a one-hot encoding of the observed value for any j E (see c.g., Koller & Friedman (2009) for full derivation).
The essence of the above updates is a characterization of the joint fixed point to mean-field inference. For simplicity of notation, defining q [qı (x1)
92 (2
...)==
We see that q is a joint fixed point of all the mean-field updates if and only if
softmax (p + PhoX0 + by)
(8)
where x, analogously denotes the stacked one-hot encoding of the observed variables.
We briefly recall the monotone DEQ framework of Winston Kolter 2020). Given input vector x, monotone DEQ computes the fixed point 2" that satisfies the equilibrium equation
(x) (W z (x) Ux + b).
(9)
4

---

Under review as a conference paper at ICLR 2022
Q2
43
q4
Poknard fimelee trastarr
A4
H
A41
15
((z))
Traning drgg.
Figure 2: Illustration of a possible deep convolutional Boltz- mann machine, where the monotonicity structure can still be enforced.
Figure 3: Convergence of the forward- backward splitting.
Winston & Kolter 2020) showed that if: 1) is given by proximal operato [xx) = (2) for some convex closed proper (CCP) f. and 2) if we have the monotonicity condition I - W ž ml (in the positive semidefinite sense) for some m > then for any x there exists unique fixed point x (x), which can be computed through standard operator splitting methods, such as forward- backward splitting.
We now state our main claim of this subsection, that under certain conditions the mean-field fixed point can be viewed as the fixed point of an analogous DEQ. This is formalized in the following proposition.
Proposition 3.1. Suppose that the pairwise kernel d satisfies 1 - +b > md mor > 0. Then the mean-field fixed point
Th softmax (hhiqs + PhoXo bb))
(10)
corresponds to the fixed point of a monotone DEQ model. Specifically, this implies that for any X there exists unique, globally-opting fixed point of the mean-field distribution Qh-
As the monotonicity condition of the monotone DEQ is assumed in the proposition, the proof of the proposition rests entirely in showing that the softmax operator is given by prox/ for some CCP f. Specifically, as shown in (Krähenbühl Koltun 2013), this the case for
f(=) Σ 24 log 2, - 11:11
T
[ ===1,
(11)
i.e, the restriction of the entropy minus squared norm to the simplex (note that even though we are subtracting squared norm term it is straightforward to show that this function convex, since the second derivatives are given by 1 1/ze 1, which is always non-negative over its domain).
3.3 PRACTICAL CONSIDERATIONS WHEN MODELLING MONOTONE BOLTZMANN MACHINES
The construction in section 3.1 guarantees monotonicity of the resulting pairwise probabilistic model. However, instantiating the model in practice, where the variables represent hidden units of deep architecture (i.e., representing multi-channel image tensors with pairwise potentials de- fined by convolutional operators), requires substantial subtlety and care implementation. setting, we do want to actually represent A explicitly, but rather determine a method for multi- plying Av and AT for some vector v (as we see in section 3.2 this is all that is required for the parallel mean-field inference method we propose). This means that certain blocks of are typically parameterized as convolutional layers, with convolution and transposed convolution operators as the main units of computation.
this
More specifically, we typically want to partition the full set of hidden units into some K distinct sets
q
iqi
42
qKl
(12)
A proximal operator is defined by prox (x) = arg min, 1| 2|12 (z).
Technically speaking, only need 1 Abh 2 mī, but since we want this to hold for any choice of h, need the condition apply to the entire & matrix.
5

---

Under review as a conference paper at ICLR 2022
where e.g.. q; would be best represented height x width x groups cardinality tensor (i.e., collection a multiple hidden units corresponding to different locations in typical deep network hidden layer). Note that here q: is not the same (2(),, but rather the collection of many different individual variables. These terms can be related to each other via different operators, and a natural manner of parameterizing A in this case is dense operators. To represent the pairwise interactions, we can create similarly- matrix A, e.g., one of the form
interconnected set of convolutional or
A1
0
0
A2
A
0
(13)
:
: AKK
Aςι Aς2
where c.g., A,y is a (possibly strided) convolution mapping between the tensors representing q and q. In this case, we emphasize that A.j is not the kernel matrix that one "slides" along the variables. Instead, Ai is the linear mapping as if we write the convolution as a matrix-matrix multiplication. For example, 2D convolution with stride can be expressed as doubly block circulant matrix (the case is more complicated when different striding is allowed). This parametrization is effectively general Boltzmann machine, since each random variable eq. (12) can interactive with any other variables except for itself. Varying A.j. the formulation in eq. (13) is rich enough for any types of architectures including convolutions, fully-connected layers, and skip- coiieccnnnctions, etc.
An illustration of one possible network structure is shown in fig. 2 The precise details of how one computes the block diagonal elements of A A, and how one normalizes the proper diagonal blocks (which, emphasize, still just requires computing the singular values of matrices whose size is the cardinality of a single q:(x;) are somewhat involved, so we defer complete descrip- tion the Appendix (and accompanying code). The larger takeaway message, though, is that it is possible to parameterize complex convolutional multi-scale Boltzmann machines, all while ensuring monotonicity.
3.4 EFFICIENT PARALLEL SOLVING FOR THE MEAN-FIELD FIXED POINT
Although the monotonicity of + guarantees the existence of unique solution, it does necessarily guarantee that the simple iteration
(A) softmax P (( Pho bb)
(t-1),
(14)
will converge this solution. Instead, guarantee convergence, one needs apply the damped iteration (see, e.g. (Winston & Kolter 2020))
proxf (11 (1 (t-1) + a(Pn (t-1) + Pho + by))
(15)
The damped forward-backwart iteration converges linearly the unique fixed point if S 2m/ L.2. assuming + is m-strongly monotone and L-Lipsehitz (Ryu & Boyd 2016). Crucially, this update can be formed in parallel descent approach as is typically needed by mean-field inference.
all the variables in the network: do not require coordinate
The key issue, though is that while prox} softmax(zr) for f defined in eq. 11. in general this does not hold for # 1. Indeed, for * 1, there is no closed form solution the proximal operation, and computing the solution is substantially more involved. Specifically, computing this proximal operator involves solving the optimization problem
prox (x) = arg min
=112= 2112 + Σ 24 log 2,
a -
1|
2
i
(16)
subject to
Σ = 1, 2 2 0.
The following theorem, proved in the Appendix, characterizes the solution to this problem for a E (0, 1) (although it is also possible to compute solutions for 1, this is not needed in practice, as corresponds to a "negatively damped" update, and it is typically better to simply use the softmax update in such cases).

---

Under review as a conference paper at ICLR 2022
Theorem 3.2. Given f as defined in eq. (1p. (0, and x R the proximal operator prox3 (x) is given by
(r) - W [ (ta exp
2 - (
a
where E R is the unique solution chosen ensure that the resulting Σ, proxf 1, and where W.) is the principal branch of the Lambert W function.
In practice, however, this is not the most numerically stable method for computing the proximal operator, especially for small a, owing to the large term inside the exponential. Computing the proximal operation efficiently is somewhat involved, though briefly, we define the alternative func- tion
g log W 1 ("=" exp
-1
- a
(17)
and show how to directly compute (vV) using Halley's method (note that Halley's 's method is also the preferred manner to computing the Lambert W function itself numerically (Corless et al. 1996)).
Finding the prox operator then requires that we find À such that - exp(g(a; + A)) = 1. This can be done via (one-dimensional) root finding with Newton's method, which is guaranteed always find a solution here, owing to the fact that this function is convex monotonic for À E (-oo, 1)- We can further compute the gradients of the g function and of the proximal operator itself via im- plicit differentiation (i.c., we can do it analytically without requiring unrolling the Newton or Halley iteration). We describe the details the Appendix, and include an efficient PyTorch function imple- mentation in the supplementary material.
Comparison to Winston & Kolter (2020) Although this work uses the same monotonicity con- straint as in Winston & Kolter (2020), our result further requires the linear module & to be hollow, and extend their work the softmax nonlinear operator well. These extensions introduce signif- icant complications, but also enable us to interpret our network as probabilistic model, while the network in Winston & Kolter (2020) cannot.
3.5 TRAINING CONSIDERATIONS
Finally, we discuss approaches for training these monotone Boltzmann machines, exploiting their efficient approach to mean-field inference. Probabilistic models are typically trained via approxi- mate likelihood maximization, and since the mean-field approximation is based upon particular likelihood approximation, it may seem most natural to use this same approximation to train param- eters. In practice, however, this is often a suboptimal approach. Specifically, because our forward inference procedure ultimately uses mean-field inference, it is better to train the model directly to output the correct marginals, when rumning this mean-field procedure. This is known based loss (Domke) (013). In the context of monotone Boltzmann machines, this procedure has particularly convenient form, as it corresponds roughly to the "typical" training of DEQ.
marginal-
In more detail, suppose we are given sample E X (i.e., at training time the entire sample is given), along with a specification of the "observed"" and "hidden" sets, and h respectively. Note that the choice of observed and hidden sets is potentially up to the algorithm designer, and can effectively allows one to train our model "self-supervised" fashion, where the goal is to predict some unobserved components from others. In practice, however, one typically wants to design hidden and observed portions congruent with the eventual use of the model: e.g., if one is using the model for classification, then at training time it makes sense for the label to be "hidden" and the input to be "observed."
Given this sample, we first solve the field inference problem to find q (x,) such that
(18) For this sample, we know that the true value of the hidden states is given by x Thus, we can apply some loss function E(g xx) between the prediction and true value, and update parameters of the model f = { [A, b) using their gradients
t%h softmax ( + 2 no.,, + by).
de (t xx)
dE(g,, Xn.
0g. 30
al(g,, Xn.) (1 Og(g:) dqz,
-1
Og(gh) 00
(19)
00
dq.
dqg
7

---

Under review as a conference paper at ICLR 2022
with 9(9%) = prox3 (1-a))q, + a( + Phooo - b₂)) and where the last equality comes from the standard application of the implicit function theorem as typical in DEQs or monotone DEQs. This backward pass can also be computed via an iterative approach, and here the details exactly mirror that of Winston & Kolter (2020).
As a final note, we also mention that owning to the restricted range of weights allowed by the monotonicty constraint, the actual output marginals qı(1;) are often more uniform in distribution than desired. Thus, we typically apply the loss to a scaled marginal
(x:) x qi (x:)"*
(20)
where 7, R2 is variable-dependeen learnable temperature parameter. Importantly, we emphasize that this is only done after convergence to the mean-field solution, and thus only applies to the marginals to which we apply loss: the actual internal iterations of mean-field cannot have such a scaling, as it would violate the monotonicity condition.
4 EXPERIMENTAL EVALUATION
We evaluate the performance of our model primarily on the MNIST dataset. Our model is able to approximate any conditional distribution. Here we demonstrate how model missing pixels and the class digits conditioned on the observed pixels, as well as model missing pixels conditioned on class digits and observed pixels. Although MNIST is of course small-scale problem, the goal here is to demonstrate joint inference and learning over what is still a reasonably-size joint model, considering the number of hidden units. Nonetheless, the current experiment is admittedly largely a demonstration of the proposed method rather than a full accounting of its performance, point we highlight in the subsequent section as well. After descríbing the MNIST experiments, we detail a similar experiment on CIFAR-10 to demonstrate the potential for scaling the approach.
We also show how our inference method differs from the previous ones. On the joint imputation and classification task, we train models using our updates and the updates in Krähenbüül & Koltun (003);; Baqué et al. (2016), and inference each using all three update methods, with and without the monotonicity constraint. We show that our inference method is superior in both performance and convergence speed. Numerically, we also demonstrate that the other two methods could either diverge or not converging the actual mean-fiee field fixed point. All deferred experiments and details can be found in the appendix.
The original MNIST dataset has one channel representing the gray-scale inten- sity, ranging between O and 1. Here we adopt the strategy of Van Oord et al. (2016) to convert this continuous distribution to a discrete one. We bin the intensity evenly 4 categories {0, ......... 3), and for each channel uses a one-hot encoding of the category so that the input data has shape 4 x 28 x 28. We remark that the number of categories is chosen arbitrarily and can be any integer. For image with missing data, if the pixels are randomly masked, we always mask each pixel off independently with probability 60%, such that in expectation only 40% pixels are observed. a whole patch of pixels is masked, randomly pick 14 x 14 patch. The p image, similar to the query training in Lázaro--rrrrir Gredilla et al. (2020). To make the model class richer, in the patch case we lift the monotonicity constraint, and the model converges regardless. We also conduct the same set of MNIST experiments using a 3-layer DBM and include the results in the appendix.
Experiment setup
chosenly differently for every
Results on imputation and classification Training the above described model for 40 epochs with 40% missing pixels leads to a 92.95% test accuracy, and the image reconstruction result is shown in fig. [4d] Based on the reconstructed images and our classification results, our model successfully recovers the unimodal distribution conditioned on the observed pixels. Despite working simulta- neously on two different tasks, our model can simply be trained jointly. taking full advantages of the existing auto-differentiation frameworks without additional burden. It worth noting that while the autoregressive models Van Oord et al. (2016) are comparable to ours, they require sampling pixels one-by-one in a sequential order at inference time, whereas our model does not assume an underlying sequence and can generate all pixels at once. Comparing to the pnteerently-prrrmeeett monDEQ in Winston & Kolter (2020), whose linear module suffers from drastically increasing con- dition number (hence in later epochs taking around 20 steps converge, even with tuned (x), our
8

---

Under review as a conference paper at ICLR 2022
2.
4
7
2
1 0 3
6
4
1
4
9
8
ç
5
9
60
9
0
5
L
7
7
9
7
4
7
6
4
5
4
0
7
4
0
3
L
3
4
7
2
7
2
(a) Test data with 60% pixels randomly
(h) Test data with 14 x 14 patch masked
(c) Original test data
masked
7
2
7
4
4
R
7
2
6
4
1
4
9
7
5
7
9
0
5
9
0
6
9
0
5
9
7
3
7
7
4
4
9
5
4
9
7
3
4
9
6
4
5 |
0
7
3
4
0 4
7
4
5
4
0
7
4
0
1
3
4
7
2
7
2 7
3 4
7 2
7
2
1
Imputation 60% pixels randomly masked
Imputation masked, inference without injection labels
patch
(n)
Imputation masked, inference with injection lahels
patch
Figure 4: MNIST pixel imputation
(a) Test data has 50% pixels randomly
(b) Imputed pixel inference (without injec. labels)
(c) Original image
Figure 5: CIFAR-10 pixel imputation
parameterization produces much nicer convergence pattern: the average number of forward iter- ations over the 40 training epochs less than 6 steps, see fig. 3 When the missing pixels form consecutive patches, our model reconstructs readable digits despite potentially large chunk of miss- ing pixels (fig. 4c). Mcanwhile, if the model is given the image labels as input injections, our model performs conditionaly generation fairly well (fig. 4f). These results demonstrate the flexibility of our parameterization for modelling different conditional distributions.
CIFAR-10 Experiment We additionally conduct an experiment on the simultaneous tasks of im- age pixel imputation and label prediction given partially observed features. Model architecture and training details are given in the appendix. With 50% of the pixels observed, the model obtains 58% test accuracy, and can impute the missing pixels effectively (see fig.
CONCLUSION
In this work, we give monotone parameterization for general Boltzmann machines, and connect its mean-field fixed point to monotone DEQ model. We provide a mean-field field update method that is proven to be globally convergent. Our parameterization allows for full parallelization mean-field updates without restricting the potential function to be concave, thus addressing issues with prior approaches. Morcover, we allow complicated and hierarchical structures among the variables and show how to efficiently implement them. For parameter lcarning, directly optimize the marginal- based loss over the mean-fich field variational family, circumventing the intractability of computing the partition function. Our model is evaluated the MNIST and CIFAR-10 dataset for simultaneously predicting with missing data and imputing the missing data itself. There are several potential future directions. First, the monotone parameterization in theorem 3.J not an if-and--oly-if statement, hence potentially making our model more restrictive than necessary. The second direction is that although we have fairly efficient implementation of prox is still slower than normal nonlinear- ities like ReLU softmax. It is interesting direction to more efficiently scale these models.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. arXiv:1909. 01377, 2019.
arXiv preprint
Shaojie Bai, Vladlen Koltun, and Zico Kolter. Multiscale deep equilibrium models. arXiv preprint arXiv:2006. 08656, 2020.
Pierre Baqué, Timur Bagautdinov, François Fleuret, and Pascal Fua. Principled parallel mean-field inference for discrete random fields. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.
2016.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: review for statisti- cians. Journal of the American statistical Association, 112(518):859 8877777777777888 2017.
Robert M Corless, Gaston H Gonnet, David EG Hare, David Jeffrey, and Donald E Knuth. On the lambertw function. Advances in Computational mathematics, 5(1):329-359, 1996.
Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 90689926899988 0887-977,, 2019.
Justin Domke.
transactions on pattern analysis and machine intelligence, (5(10))2454-246) 2013. Learning graphical model parameters with approximate marginal inference. IEEE
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1.
MIT press Cambridge, 2016.
Geoffrey E Hinton.
Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1711-180) 2002.
Daphne Koller and Nir Friedman. Probahilistic graphical models: principles and techniques. MIT press, 2009.
Philipp Krähenbühl and Vladlen Koltun. Parameter learning and convergent inference for dense random fields. International Conference on Machine Learning, pp. 513-521. PMLR, 2013.
Miguel Lázaro-Gredee -Geeill,,, Wolfgang Lehrach, Nishad Gothoskar, Guangyao Zhou, Antoine Dedieu, and Dileep George. Query training: Learning rected graphical models with hidden variables. arXiv preprint arXiv:2006.0668 2020.
model infer better marginals in undi-
Khuê Lê-Huu and Karteek Alahari. Regularized frank-wolfe for dense crfs: Generalizing mean field and beyond. Advances in Neural Information Processing Systems, 34, 2021.
Mohammad Norouzi, Mani Ranjbar, and Greg Mori. Stacks of convolutional restricted boltzmann machines for shift-invariant feature learning. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pp. 2735-2742. IEEE, 2009.
Ernest K Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. Comput. Math, 15 (1):3-43, 2016.
Ruslan Salakhutdinov and Geoffrey Hinton. Deep boltzmann machines. In Artificial intelligence and statistccs pp. 448-455. PMLR, 2009.
Idan Schwartz, Alexander G Schwing, and Tamir Hazan. High-order attention models for visual question answering. arXiv preprint arXiv:1711.04323. 2017.
Aaron Van Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks. In International Conference Machine Learning, pp. 1747-1756. PMLR, 2016.
Homer F Walker and Peng Ni. Anderson acceleration for fixed-point iterations. SIAM Journal
Numerical Analysis, 1714):175- 2.
Ezra Winston and J Zico Kolter. Monotone operator equilibrium networks. arXiv:2006.0859), 2020.
arXiv preprint
10

---

Under review as a conference paper at ICLR 2022
Zhirong Wu, Dahua Lin, and Xiaoou Tang. Deep markov random field for image modeling. In European Conference on Computer Vision, pp. 295-312. Springer, 2016.
Shuai Zheng, Sadeep Jayasumana, Bernardino Romera- Parera,,,rrees, Vibhav Vineet, Zhizhong Su, Da- long Du, Chang Huang, and Philip HS Tom. Conditional random fields recurrent neural net- works. In Proceedings of the IEEE international conference on computer vision, pp. 1529-1537, 2015.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 DEFERRED PROOFS
Proof of theorem 3.2 By definition, the proximal operator induced by f (the same f in eq. I1 and a solves the following optimization problem:
min 2
2 || =112 +
0z Σ
2j log
a 2i
2 2
|=
s.t.
2, 2,2 0,
i= ,,...dd,
Σ ===1
of which the KKT condition is
24 + 24
a log 2 02 + 14, for i [d]
2 0
2 2
p42 0
(E(d]
2
1=1
We have that μ4 0 is feasible and the first equation of the above KKT condition can be massaged
as
I; + 2 + a a logo 02; + X - /4 = 0
(1 a)2; + a log 24 I; x
(1 a)4 log 2 I ー A
a
a
(1 a)2z + a logogg
Tj
exp
exp
1
x
2i exp
z
exp
a
1
1
2i exp
exp
a
a
24 W
exp
a
where W is the lambert W function. Notice here zi condition holds. Hence, we conclude that
O. Our primal problem is convex and Slater's
1 a
F a A ))
2, =
W
exp
a
a
A.2 CONVOLUTION NETWORK
clear that the monotone parameterization section 3 directly applies to fully-connected net- works, and all the related quantities can be calculated easily. Nonetheless, the real power of the DEQ model comes in when we use more sophisticated linear operators like convolutions. In the context of Boltzmann machines, the convolution operator gives edge potentials beneficial structures. For ex- ample, when modeling the joint probability pixels in an image, is intuitive that only the nearby pixels depend closely each other.
12

---

Under review as a conference paper at ICLR 2022
Let A Rexxxxx denote convolutional tensor with kemnel size and channel size k, let x denote some imput. For a convolution with stride 1, the block diagonal elements A" A simply form a 1 x convolution. In particular, apply the convolutions
- -A7(A())) + A(x)
(21)
where is a x convolution given by
A[::]
Σ Alisi, i, i." Ahrii,
(22)
We can normalize by the spectral norm of Å term to ensure strong monotonicity. Since À can be rewritten as k matrix and l is usually small, its spectral norm can be easily calculated.
takes more effort to work out convolutions with stride other than 1. Specifically, the block diagonal terms do not form 1 x convolution anymore, instead, the computation varies depending the location. It is easier to see the computation directly in the accompanying code.
Grouped channels It crucial introduce the concept of grouped channels, which allows to represent multiple categorical variables in single location, such as the three categorical variables representing the three (binned) color channels of an RGB pixel. In this case, each of the three RGB channels will be represented by different group of k channels representing the & bins. The grouping is achieved by having the nonlinearity function (softmax applied to each group separately. We remark that the convolutions themselves are not grouped, otherwise none of the red pixels would interact with green or blue pixels, etc. Instead, we want all RGB channels to interact with each other (except that channel blkdiag( ÅT A) is grouped in the following way. Recall that this block diagonal term has element of size k; x k; for E [n). This parameterization has only 1 group. With groups, the element of the block diagonal matrix then has size k; .i...... kig ki, for E [n], where Σje(g) hi, k;- We also observe empirically that grouping the latent variables improves the performance.
position kj) does not interact with itself). That means in eq. (4). the
A.3 EFFICIENT COMPUTATION OF prox?
The solution the proximal operator in damped forward iteration given in theorem 3.2 involves the Lambert W function, which does not attain an analytical solution. In this section. we show how to efficiently calculate the nonlinearity (Ix),, as well its Jacobian matrix for backward iteration.
1-a W (2-a exp - 1)), and have Let f --a
log fy) log 1-a log ev/a-1 log 1
1 (1-a a
L 14-1) -1) la
W where the last equality uses the identity log(W(x))
exp
log x
W Rewrite
W (Tー exp -x- 1)) alent to finding the root of
f()) ع- a
and massage the terms, we have that solving log f(y is equiv-
M(x) y 6"
Direct calculation shows that N (xx)) aa - a)e and l((x)) = -(1 - a)e". Note here is
the input and it known to us, and scalar. Hence we can efficiently solve the root finding problem using Halley's method. For backpropagation. we need de which can be computed by dy
implicit differentiation:
1(x)
et - a) ax =0
1
dy a a)e²
Our
Now we can find À s.t E, = using Newton's method on g()) = E, cloR(((r+t))) - 0. Note this is still one-dimensional optimization problem. A direct calculation shows that dg Σ, (ox(((2.-)) ((zg(f( and above we have already calculated that
ax
d)
d log(f + X)
dx
1
yA
dy y +
13

---

Under review as a conference paper at ICLR 2022
For backward computation, by the chain rule, we have: de f(x++A) elug ((x+ dlog(f((;; + A))
dx;
dæ
+ dd/dr;
Am
X log(S (z; X))
where the last step is derived by implicit differentiation. Now to get dlA /d,, notice that by applying implicit function theorem on p(z, A(x)) = E, elog(((est2) = O, we get
dA
dp
dp
dx:
dx:
Thus we have all the terms computed, which finishes the derivation.
B ADDITIONAL EXPERIMENTS AND DETAILS
Here we provide the model architectures and experiment details omitted in the main text.
Model architecture For MNIST experiments, using the notation in eq. 13 we design a 20-layer deep monotone DEQ with the following structure:
A
1l
0
A21
A22
0
0
A31
A32
A33
0
0
0
A13
A
where An is 20x20x3x3 convolution, A22 is 40 40 convolution, A2i is 40x convolution with stride 2, A33 is 80 80 3 convolution, A31 is 80 x0 convolution with stride 4, Asz is 80 x 40 x 3 3 convolution with stride 2, Aas is (80-7- 7- x 10 dense
linear layer, and Au is a 10 x 10 dense linear layer. The corresponding variable q as in eq. ([2) then has elements of shape (20 x 28 28), (40 14 x 14), (80 x 7 7), (10 x 1). When applying the proximal operator to q. we use 1, 10, 20, as their number of groups, respectively.
dense classifica- cross-entropy loss and class weights 1-8"r with B 0.9999 (Cui et al. 2019 where n, is the number of times pixels with intensity appear in the hidden pixels. For classifica- tion, we use standard cross-entropy loss. To enable joint training, we put equal weight of 0.5 on both task losses and backpropagate through their sum. For both tasks, we put 7. 7. into the cross- entropy loss as logits, as described in eq. (20). Since mean-field approximation is (conditionally) unimodal, the scaling grants us the ability model more extreme distributions. To achieve faster damped
Training details and hyperparameters Treating the image reconstruction 1-8
tion task,
iteration, we implement Anderson acceleration (Walker & Nij [201T), and stop the fixed point update as soon as the relative difference between two iterations (that is, ||q:11 7e / | q:l) is less than 0.01, unless we hit a maximum number of 50 allowed iterations. For prox and the damped iteration, we set a 0.125 (Although one can tune down a whenever the iterations do not converge, empirically this never happens on our task). We use the Adam optimizer with learning rate 0.001. Our models are trained on one GeForce GTX 2080 Ti GPU.
Comparison to past inference methods We conduct numerical experiments to compare our in- ference updating method to the ones proposed by Krähenbühl & Koltun (2013): Baqué et al.) (2016), denoted as Krähenbühl's and Baqué's respectively. Krähenbühl's fast concave-convex procedure (CCCP) essentially decomposes to eq. (14). the un-damped mean-field update with softmax. This update only converges provably when + is concave. Baqué's s inference method can be written as
(t) softmax (1 - a) log dn
(t-1) a (aPPnng) (1-1) + Pnn + by.)
(23)
This algorithm provably converges despite the property of the pairwise kernel function. However, this procedure converges in the sense that the variational free energy keeps decreasing. Therefore their fixed point may not be the true mean-field distribution eq. (10). In this experiment, train the
14

---

Under review as a conference paper at ICLR 2022
Table 1: Relative update residual when monotonicity is enforced
Inference
Krähenhiühl
Baqué
Our
Train
Krähenbühh
0.0004
0.0061
0.0024
Baqué
1,250
0.0059
0.0024
Our
1.144
0.0057
0.0017
Table 2: Relative update residual when monotonicity is not enforced
Inference
Krähenbühl
Baqué
Our
Train
Krähenbühl
0.0005
0.00665
0.0024
Baqué
1.0924
0.0119
0.0042
Our
1.1286
0.0065
0.0022
models using three different updating methods, and perform inference using three methods as well, with and without the monotonicity condition.
Krähenbühl's 's and Baqué's methods often do not converge in the backward pass (there's no theo- retical guarantees neither). To rule out the impact of the backward iteration, during training we directly update use the gradient of the forward pass, instead of using a backward gradient hook to compute eq. (19). Figure 7 and fig. & demonstrate how the three update methods impute missing pixels when trained with different update rules, with and without the monotonicity condition, re- spectively. Krähenbühl's 's usually does not converge when the model is trained with method or Baqué's, s, whereas the other two methods impute the missing pixels well. The classification results presented in table 3 and table 4 Notice that when trained with our method Baqué's, the convergence issue of Krähenbühl's Teads to horrible classification accuracy. Our method is superior other inference methods when the model trained in a different update fashion. For example, if the model is trained by using Krähenbühl's. s,, it makes sense that the model performs the best the inference also Krähenbühl's since the parameters are biased toward that particular inference method. However, our method in this case outperforms Baqué's.
After these methods halt and return qh/ we run one more iteration of
T+I 1 softmax PRigh + PnoXo + bn) q
(24)
and record the relative update residual |/ T+1 9 /1/11/1 for randomly selected 4000 MNIST images. The results are listed in table T and table 2 To alleviate the effect of numerical issues, strength the convergence condition to either the relative residual is less than 10-3 or the number of iterations exceeds 100 steps.
It appears in table D and table 2 that although our method has a much lower residual compare to Baqué's, both of them seem small and convergent. This is because the "optimal" fixed point in this setting on MNIST might be unique and both methods happen to converge to the same point. However, this is general not true. We compare our method Baqué's on 400 randomly se- lected MNIST test images with 40% pixels observed, and perform mean-field update until the rel- ative residual of 10 0.05, 0.01, 0.005. 0.001, 0.0005, 0.0001] is reached (without step constraint), respectively. Then we measure the TV distance between the distributions computed by these two methods on the remaining 60% pixels, as well as the convergence speed. The results are demon- strated in fig. 6 One can that when the model is trained (using Krähenbühl's, fig. Da), the TV distance converges to as the tolerance decreases. However, when the model is just initialized (but still constrained to be monotone), the TV distance remains large (fig. (c). Even though in this case the optimal fixed point may be unique, our method is still superior to Baqué's s: takes us less iterations till convergence, despite whether the model is trained or not..
15

---

Under review as a conference paper at ICLR 2022
Our
3.013
50
Baque
40
3.005
7V dvalteee
20
2.004
3.002
0.10
0.05
0.05
0.04
0.02
0.00
0.30
0.08
0.06
0.04
0.02
0.00
Telorance (dcercasing
Talerance (decresonn)
(a) TV distance when trained
(b) Number of iteration till convergence when trained
0.085
0.080
Baque
0.073
TW
3.063
3.050
0.04
Telerance (dacrcasing)
Talerance (decreasing)
(c)
initialization
(d) iteration convergence initialization
Figure distance and convergence speed
7 Z
/
6
4
4 A
7 2
6
4
4 J 4 3 Z 4 0 6 5 33 2 / 0
1 0 6 1
7 2
/
6
4
4
4
Krähenbühl
9
0
6
4
5
5 9
0
6
9
5
9
0
6
9
5.
9
7
8
4
6 1
4 3 2 4 1 5
5
9
8
7 0 2 4
5
7
8
4
4
6
4
5' 1
4
O
7
4
0
1
4 0
4
4 0
4
0
1
3
3 41
7
27
7
1
3
4
7
3 7
L 2
7 /
2 4
2 4
4
7 7
2
O
9
7
O
/ A
Baqué
f
0
8
0 "6 1 2 4
6
9
0
6
9
5
6
9
O 8
6
9
0
5
17
4
9
8
7 0 2
4 4
6
9 7
4
7
6
5
4 0
3
4
0
7
4
0
3
3 L 2
7
L 2
7
2
2
0
/
7
0
4
7
0
4
4
9
2
6.) 5
9 7 0 4
0
6
9
1
5
6
9
0
6
9
0
5
Our
3 30 5
9
8 7
4
7
6
4
5
7
8
4
9
6
4
5
6 1
4
4
0
3 2
0
7
4
0
3
1
1
3
7
2
7
3 4
7
2
7
1
(4) Krähhenühhl
(b) Baqué
(c) Our
Figure 7: Training and inference using all three update rules with 40% observed pixels with the monotonicity condition. The labels each represent the training update rule. and the labels the columns represent the inference update rule.
16

---

Under review as a conference paper at ICLR 2022
7 2
1
O
4
4 }
9
7 2
0
4
1
4
7 2
1
6
4
4
Krähenbüh
9
0 3 7
6
9
0
5
9
0
6
4
0 6 1
1 10 3
5
9
0
6
9
5
9
7
4 4
9
6
10 3 2
5
9 7
8 7
4
7
5
97
4
7
6
10
5 1
4
0
0
1
4 O
4
O
401 4
0
3
3
7
2
7
1
3 4
1.2 2// 1 A ! 4 5 3 1 4
4 347217
|
2 44 A
7 7
0
4
7 7
0
4
/
Baqué
88
8 7
3:
53
5 9
6 f
9
0 6
5
S 9
0 8 4
6 4
9
0
5
3
9
37
7 8
9
9 7 4 0
9
6
5
0
82
4 0
0 3
0
3
3 L 2
L 2 9 4 7 0
1 4
1 9
7
0
1
9
7
0
4
5
9
0
6
9
0
5
5
0
6
9
0
Our
9 4
7 0
3 7
4 4
7
6
10 3
5
3 7
4 4
1
6
l0 3 2
0
4
0
3 4
7
2
7
2
3 4
7
2
7
1
(a) Krähenbuhl
(b) Baqué
(c) Our
Figure 8: Training and inference using all three update rules with 40% observed pixels withou the monotonicity condition. The labels each represent the training update rule, and the labels the columns represent the inference update rule.
Table 3: Classification (standard deviation) when monotonicity is enforced
Inference
Kräähenüühl
Baqué
Our
Train
Krähenbühl
0.042 (0.0013)
0.114 (0.0019)
0.0498 (0.0014)
Baqué
0.958 (0.0013)
0.038 (0.0010)
0.034 (0.0012)
Our
0.946 (0.0024)
0.0425 (0.0016)
0.0412 (0.0017)
CIFAR-10 model architecture Architecture is the same as for the MNIST experiments with the following exceptions: A₁ 1 is 20 20 3 convolution, A22 24 24 x 3 convolution, A21 is 24 x 20 x 3 x 3 convolution with stride 2, Ag3 is 48 x 48 x 3 x 3 convolution, Ay is 48 20 3 convolution with stride A32 is 48 24 3 convolution with stride 2, A4 is (48-8-8) 8) x 10 dense linear layer, and A4 is a 10 x 10 dense linear layer. The corresponding variable q as in eq. (12) then has elements of shape (60 x x 32), (24 x 16), (48 8 8), (10 x 1). When applying the proximal operator to q. we use 1, 6, 12, as their number of groups, respectively.
CIFAR-10 training details Training details are the same as for the MNIST experiments with the following exceptions: The model is trained for 100 epochs using standard data augmentation. During the first 10 epochs, the weight on the reconstruction loss is ramped up from 0.0 to 0.5 and the weight the classificatiin loss ramped down from 1.0 0.5. Also during the first 20 epochs, the percentage of observation pixels ramped down from 100% to 50%.
C COMPARISON TO RBM/DBM
We conduct the same set of experiments on MNIST using DBM for comparison. We use a 3- layer DBM where the first hidden layer has 300 neurons, and the last hidden layer (representing the digits) has 10 neurons, amounting to in total 238,200 parameters. Our proposed model in the MNIST experiments
165,300 parameters.
For image imputation, we randomly mask off 60% pixels, or a randomly selected 14 x 14 patch; the results shown in fig. g In the experiment with 60% of pixels randomly masked, we also test
17

---

Under review as a conference paper at ICLR 2022
Table 4: Classification (standard deviation) when monotonicity is enforced
Inference
Krähenbühl
Baqué
Our
Train
Krähenbühl
0.035 (0.0017)
0.189 (0.0023)
0.051 (0.0015)
Baqué
0.762 (0.0013)
0.041 (0.0013)
0.055 (0.0012)
Our
0.90 (0.0002)
0.063 (0.0021)
0.036 (0.0017)
7
2
0
4
1
4
9
7
2
/
0
4
1
4
9
7
9
0
6
9
0
5
5
9
0
6
9
0
5
75
7
3
4
6
6
5
25
9
7
3
4
9
6
6
5
75
3
4 4
7
5
0
7
4
1
4
0
7
4
0
1
100
125
3
L
7
2
2
125
3
4
7
2
2
125
1
?
150
150
150
50
100
200
50
100
150
200
50
100
150
260
(a) 60% pixels are randomly musked. From left to right: imputed image, true imagge, masked imagee.
2
6
4
1 4
A
7
2
1
0
4
1
9
9
0
6
9
0
S
5 9
0
6
9
0
5
9
75
7
9
4
9
6
4
5
75
9 7
8
4
9
6
6
5
75
100
O
7
4
0
3
1
100
4 0
4
0
1
3
100
L
7
2
2
3 4
2
2
150
150
150
50
100
150
200
50
100
150
200
50
1000
150
200
(b) 14 x 14 patches are randomly masked. From left right: imputed image, trae image, masked image.
Figure 9: DBM for image imputation
the model on predicting the actual digit simultaneously. The test accuracy is 93.58%. Our model achieves comparable test accuracy (92.95%) and imputation compared to this DBM, given fewer parameters and despite the the monotonicity constraint of our model.
The DBM is trained using CD-1 algorithm for 100 epochs with batch size of 128 and learning rate of 0.01. For imputation and classification, the DBM uses Gibbs sampling of 100 steps, although the quality of the imputed image and test accuracy are insensitive to the number of steps.
18


Reviews:
[{"review_id": "s8oleR0t3w", "reviewer": "Reviewer_8YQo", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and easy to follow. Most of its contents come from existing literature, but this work nicely puts those existing pieces (single fixed point, parallel updates) together, providing a probabilistic interpretation as a Boltzmann machine that is new.\n\nWhile this paper emphasizes how the proposed approach enables the use of general Boltzmann machines (BM) and not just stacked restricted BMs, the resulting model might actually be more restricted than the stacked RBMs that it intends to improve upon. It is true that the proposed model can contain intra-layer and skip-layer connections that a DBN lacks, but all the parameters are restricted so as to produce a monomodal posterior approximation for _any_ partial evidence. The true posterior, even for a single-layer RBM, can be multimodal if the parameters are not restricted. This means that, as a modeling tool, the proposed BM with restricted weights might be less flexible than a DBN. Many densities of interest are multimodal, particularly as we reduce the available evidence. In fact, in the absence of evidence, any useful BM will have to be multimodal (for instance, to be able to sample different MNIST digits from it).\n\nThe proposed mechanism for training is also lacking in that it only allows for marginal supervised learning: it cannot be used for unsupervised learning, which is the typical mode of operation for RBMs and DBNs. Basically, the tasks that it can solve need to be crafted in such a way that the evidence provided is enough to disambiguate a single mode of the posterior. For instance, if we want to perform MNIST digits inpainting and we provide only the top 25% of the image showing a semicircle ⌒, possible completions could be 0, 2, 3, 6 8, 9. This method would fail at this task since it would consistently default to a single digit, or even worse, a single combination of the possible completions.\n\nThus, the presented paper does provide an efficient mechanism for conditional training of parameter-restricted BMs (and does a good job at it), but the use cases in which it can be applied are severely limited, both due to the type of training and parameters it can use.\n\nThe experimental section does not contain meaningful comparisons with other methods/baselines:\n- Baseline 1: Use your loss function with damped parallel mean field inference (i.e. consider damping a hyperparameter and do not impose any restriction on the parameters of the BM).\n- Baseline 2: Use a DBN (less raw expressive power, but unrestricted in parameters and with a more proper loss function).\n\nSo it is difficult to gauge the practical advantage in the provided examples.\n\nMinor comments and questions:\n- You show that the mean field inference problem has a single global optimum. But is the true posterior monomodal under this parameterization? That would be a stronger result and convenient to know.\n\n- Is the query (the split between observed variables and variables one wants to predict) fixed throughout training? Although this is not explicitly pointed out in the theoretical part of your paper (it seems to be fixed, citing Domke 2013), this split could be different for each training sample, which seems to be the case based on your experiments. Using different splits is called \"query training\" in this AAAI 2021 paper \"Query Training: Learning a Worse Model to Infer Better Marginals in Undirected Graphical Models with Hidden Variables\", which seems to propose a very similar approach, although using a different type of inference. It'd be good to clarify which approach you are using in the description of training.\n\n- The definition of the function in Eq. (11) is a bit confusing because of how the domain is included. Could you define it by parts, or define I(.)?\n\n- Which is the value of alpha that you use for your experiments?\n\n- The figure \"92.95% test accuracy\" corresponds to the 10-way labels of each digit? Or to the 4-way categories of the pixels?\n\n- Typo: \"that owning to the restricted\" -> owing", "summary_of_the_paper": "In this paper the authors propose a restricted parameterization of the Boltzmann machine that guarantees that for any set of observations, the mean field objective has a single global optimum. Furthermore, that global optimum can be provably achieved using damped parallel mean-field updates, which make inference efficient. To turn inference into learning, the model is treated as a supervised learning model: some of its variables are considered to be observed inputs and some of its variables are considered to be target outputs (known at test time). The usual, marginal cross-entropy loss is the optimization target for learning.", "summary_of_the_review": "Pros: This paper does a good job at providing a mechanism for inference in (parameter restricted) BMs with convergence guarantees, as well as an efficient method to learn the parameters of these BMs.\n\nCons: The proposed method cannot be applied in many settings in which BMs can (unsupervised learning, sampling, use of multimodal posteriors). Little experimental validation of the usefulness of the convergent inference.\n\nSo the settings in which this approach can be used is very limited, but within that setting, it provides the required details for efficient training and robust guarantees for inference.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_lSJhPraQyn", "reviewer": "Reviewer_1tpT", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "On one hand, this paper has some significant strengths. First, the paper is fairly well written in general. Second, while this work is heavily inspired by Winston & Kolter (2020), I find that the connection between mean field and monotone DEQ is quite interesting (although relatively straightforward), and the proposed method is theoretically well founded.\n\nOn the other hand, the paper also has some limitations. \n\n1. First and foremost, I find the experiments quite limited, which is also acknowledged by the authors. A more diverse set of applications would have made the paper much more solid. At the very least, I would have expected some experimental comparison with restricted Boltzmann machines (not to mention also its variants such as extensions to multi-label). The proposed model is theoretically sound, but it is not clear why one should use it.\n\n\n2. The paper also has some minor presentation issues, but before ending my review with them, I would like to have some comments on the bibliographical discussion.\n\n2a. Since the convergence of mean field is presented as an emphasis in the paper, I would like to point out a very recent NeurIPS 2021 paper on the topic: \"Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond\" (https://arxiv.org/abs/2110.14759). In this paper they view parallel mean field as an instance of the generalized conditional gradient method and thus obtain different convergent variants of parallel mean field with different step-size rules. It seems to me that these variants do not have the same limitations as Krahenbuhl's and Baqué's as discussed in this paper (even though their resulting algorithms seem to be similar to Baqué's at first glance). Could you give some comments on this? Including such discussion would give the reader a broader and more up-to-date view of the current state of the art. (Of course no experimental comparison would be needed, that's not the focus of the paper).\n\n\n2b. \"Numerous works also try to combine deep neural networks with conditional random fields (CRF) (Arnab et al., 2018; Schwartz et al., 2017; Zheng et al., 2015).\"\n\nEven though this is just a minor detail in the current paper, I would like to take this opportunity to raise an important issue regarding credit assignment.\n\nThe first to view \"CRFs as RNNs\" for the dense CRFs of Krahenbuhl & Koltun (2011) was actually Krahenbuhl & Koltun (2013) and not Zheng et al. (2015). Krahenbuhl & Koltun (2013) had two major contributions in their paper: (a) convergent parallel mean field, and (b) parameter learning of dense CRFs with reverse-mode automatic differentiation (i.e., viewing \"CRFs as RNNs\" and backpropagating through time). Unfortunately, Krahenbuhl & Koltun (2013) have been often credited with (a) only and not (b), while (b) is to me even more significant than (a). This is not fair, and I think this happened because some previous work didn't cite them correctly or in a misleading manner. For example, Arnab et al., (2018) didn't even cite this paper (even though they did cite in their previous work (Zheng et al., 2015), not sure why they removed the citation from the journal version). The fact that Arnab et al., (2018) completely ignored Krahenbuhl & Koltun (2013) and credited Zheng et al., (2015) for viewing \"CRFs as RNNs\" made their presentation misleading (and unacceptable to me).\n\nI would like to encourage the authors to give proper credits to Krahenbuhl & Koltun (2013) whenever they have an opportunity to do so. Starting with the current submission, I would suggest to slightly change the above sentence to the following, for example:\n\n\"Numerous works also try to combine conditional random fields (CRF) with pixel-wise classifiers (such as neural networks) to obtain fully end-to-end models (Krahenbuhl & Koltun, 2013; Schwartz et al., 2017; Zheng et al., 2015).\"\n\nBut of course it is up to the authors to decide.\n\n\n3. Some comments on the presentation:\n\nMajor:\n\nIn the abstract: \"In addition, we show that our procedure outperforms existing mean-field approximation methods while avoiding any issue of local optima.\" I guess the authors are referring to the comparison with Krahenbuhl's and Baqué's that is presented in the appendix. If something is mentioned in the abstract, then it's important enough to be included in the main content instead of being left in the appendix. I would suggest to either remove the above sentence from the abstract, or to move such comparison from the appendix to the main content (the former seems more appropriate to me, since this is not the focus of the paper).\n\n\nMinor:\n\n- Eq. (1) should end with a comma instead of a dot.\n\n- Page 3, 1st paragraph: \"proposed a deep parameterization of MRF. However, their...\" --> \n\n- Page 3, 1st paragraph: \"proposed a deep parameterization of MRF, but their...\"\n\n- Section 3.1, 1st paragraph: lines 3-4 are not clear to me.\n\n- Page 6, before Eq. (13): \"similarly-factored A matrix\" --> \"similarly-factored matrix A\"", "summary_of_the_paper": "This paper proposes a class of model called monotone deep Boltzmann machines, where the underlying potentials are parameterized (e.g., by CNNs) such that they obey some monotonicity constraint. This constraint ensures that the inference problem has a global optimum, which can be found using some generalized variant of parallel mean field. The method is inspired from monotone DEQ, previously proposed by Winston & Kolter (2020). Experiments on a joint task of image denoising and classification show that the proposed method can effectively model complex data distributions such as images.", "summary_of_the_review": "Interesting and theoretically sound model. The set of experiments is quite modest, in addition to some minor presentation issues.", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "FQ8y6QfOWW7", "reviewer": "Reviewer_ihMA", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "## Strength\n\nThe strength of this paper is the technical contribution of finding the connection between the DBMs and the DEQ model by characterizing the monotone DBMs. I think this is a good contribution as it can be essential for further development of BMs, considering that the current progress of BMs is not so rapid, in my understanding.\n\nThe quality of presentation is also good, and this paper is clearly written overall. I have just a minor comment:\n- Since the current explanation of a block hollow matrix is vague, please mathematically define it for the self-completeness.\n \n## Weaknesses\n\nThe significance of this paper is not high, and evaluation is weak. In particular, the practical advantage of the proposed monotone DBMs is not clear. \n\nAlthough it is true that the family of BMs to which the contrastive divergence algorithm can be applied is limited, any BMs with any connection patterns of hidden variables can be trained by directly applying Gibbs sampling, which of course includes the monotone DBMs.\nTherefore, the monotone DBMs have no merit with respect to the effectiveness of inference, and I guess the only practical advantage of the monotone DBMs can be the efficiency. However, there is neither analysis of computational complexity nor empirical runtime comparison to such a straightforward approach.\n\nIn addition, it has been already proven that RBMs can represent any distribution, therefore, from the viewpoint of the representation power, there is no difference between RBMs and monotone DBMs. Of course, I agree that monotone DBMs can be more effective than RBMs and existing DBMs in practice, for example, monotone DBMs can achieve more accurate inference with less parameters than RBMs. However, there are no such comparisons in this paper.\n\nI am happy to increase my score if the above my concerns are properly addressed by the authors' response.", "summary_of_the_paper": "This paper theoretically shows that the mean-field equation for a certain family of Boltzmann machines with hidden variables, called the monotone DBMs, can be modeled as the recently proposed monotone Deep Equilibrium (DEQ) model. This paper further characterizes properties of such Boltzmann machines and its training, and shows its behavior in experiments on MNIST and CIFAR-10.\n", "summary_of_the_review": "This paper potentially includes an interesting technical contribution, while the significance is not convincing and the evaluation is weak.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "3KsvJUU3nV", "reviewer": "Reviewer_fJmJ", "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": "The paper is very well-written and easy to read. However, I found the novelty aspect of the work to be a bit lacking:\n- Aside from the new parameterization Eq (3),(4) introduced to satisfy the monotonicity condition, the method of this paper seems like a straightforward combination of [Krahenbuhl & Kolten 2013], [Baque et al. 2016], and [Winston & Kolter 2020].\n- It is also unclear how restirctive this parameterization is (which itself is quite simple) within all possible pairwise potentials that satisfy the monotonicity condition. \n- The parallel updates and the convergence proof are almost exactly the same as [Winston & Kolter 2020], except for the extension to softmax operation.\n\nI would be happy with the novelty aspect if convincing experiments results are shown. Sadly this does not seem to be the case:\n- The practical benefit of deep Boltzmann machine compared to more traditional neural architectures (e.g. CNN for image classification) is not clear to me and has not been highlighted in the paper. When would someone use deep BM instead of the alternatives? The experimental results do not seem to answer this question.\n- Although deep Boltzmann machine can be more flexible for modeling different conditional distributions without retraining, it seems to come at the cost of being much harder to train while relying on mean-field approximation. I'm wondering how crude the mean-field approximation of the posterior distribution is in the current paper's setting, which has not been discussed.\n- The experiments are very small-scaled. The images are all with very low-resolution. This seems to suggest the impracticality of deep Boltzmann machine. In CIFAR-10 experiment, the test accurarcy is only 58%, which is a lot lower than using conventional neural architectures.\n- In Eq (20) a very arbitrary scaling is used after convergence to the mean-field solution. This seems like an ad-hoc fix for a method that doesn't really work due to the monotonicity constraint. I'd be interested in seeing experimental comparison between the scaled version and the original version.\n- For the patch case, the model works better without the monotonicity constraint. This seems to be against the whole point of the paper.\n- The proposed method does not seem to have significant improvement compared to past works in this line of work (e.g. diagonal entries in Table 3, 4).\n\nAdditional comments:\n- Page 3, \"We remark the readers upon ...\" this doesn't sound grammatically correct.\n- Sec 3.5 mentions the model is trained directly to output correct marginals, instead of the usual likelihood maximization, which can be intractable. What is lost in this simplification (in addition to mean-field approximation)? Matching only marginals seems very coarse to me.\n- How to train the proposed model on batches of images? If I understand correctly, the current training procedure would sample a single image, split it into $x_h$ and $x_o$, run mean-field inference given $x_o$ in a differentiable manner, then backpropagate through loss $\\ell(q_h^*, x_h)$. Are multiple mean-field inferences run in parallel? If so do they use the same number of iterations? If not, I would imagine the training to have very high variance.\n- At the end of Sec 3.5, at the top of page 8, why is $g(q_h^*)$ not the damped version?\n", "summary_of_the_paper": "This paper proposes a new family of monotone deep Boltzmann machines where the pairwise potentials satisfy a monotonicity condition, giving rise to efficient mean-field iteration with provable convergence guarantees. The convergence is obtained by drawing connections with monotone deep equilibrium models. Small-scale experiments are done as proof of concept.\n", "summary_of_the_review": "This paper is well-written but its contributions are incremental with somewhat weak experimental results.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting contribution to the Boltzmann machine (BM) literature that makes a nice connection to DEQ models. On a positive note, reviewers found that it was well-written, clear, and interesting. Unfortunately, there were significant concerns with the manuscript that were not fully addressed in the revision: inappropriate or incomplete baselines, insufficient credit given to previous works, and the fact that this model is limited as compared to its BM relatives.

I would recommend that the authors take into account the reviewers' feedback in a revision of the work.
Decision: Reject