Restricted Boltzmann Machines are Hard to
Approximately Evaluate or Simulate

Philip M. Long
Googleplong@google.com

Rocco A. Servedio
Columbia University

Abstract
Restricted Boltzmann Machines (RBMs) area type of probability model over the Boolean
cube {−1, 1}n that have recently received
much attention. We establish the intractability of two basic computational tasks involving
RBMs, even if only a coarse approximation to
the correct output is required.
We first show that assuming P 6= NP, for any
fixed positive constant K (which may be arbitrarily large) there is no polynomial-timealgorithm for the following problem: given an
n-bit input string x and the parameters of a
RBM M , output an estimate of the probability assigned to x by M that is accurate towithin a multiplicative factor of eKn . This
hardness result holds even if the parametersof M are constrained to be at most ψ(n) for
any function ψ(n) that grows faster than linearly, and if the number of hidden nodes of
M is at most n.
We then show that assuming RP 6= NP, there
is no polynomial-time randomized algorithm
for the following problem: given the parameters of an RBM M , generate a random example from a probability distribution whose
total variation distance from the distribution
defined by M is at most 1/12.

1. Introduction
A Restricted Boltzmann Machine (Smo87; FH91;
Hin02; Ben09) (henceforth simply denoted “RBM”)
Appearing in Proceedings of the 27 th International Conference on Machine Learning, Haifa, Israel, 2010. Copyright2010 by the author(s)/owner(s).

rocco@cs.columbia.edu

with m hidden nodes is defined by an m by n realmatrix A and two vectors a ∈ Rm , b ∈ Rn . These parameters θ = (A, a, b) define a probability distribution
RBMθ over x ∈ {−1, 1}n in the following way:def

RBMθ (x) =P

hT a+hT Ax+bT xh∈{−1,1}m e

Zθ

,

(1)

where Zθ is a normalizing factor (sometimes referred
to as the “partition function”) so that RBMθ is a probability distribution, i.e.
def

Zθ =

X

T

T

T

eh a+h Az+b z .

h∈{−1,1}m ,z∈{−1,1}nWhile RBMs were first introduced more than two
decades ago (Smo87; FH91), they have recently beenused as constituents of “deep belief network” learning systems (HOT06; Ben09). An approach to training deep networks that has been growing in popularity involves unsupervised training of RBMs asa subroutine. The success of this approach (see(HOT06; LEC+ 07; EBC+ )) motivates the subject of
this paper, which is to study the complexity of basic
computational tasks related to learning with RBMs.
Since RBMs are a way of modeling probability distributions over {−1, 1}n , the two most natural computational tasks regarding RBMs would seem to be thefollowing:
1. Evaluating an RBM: Given a parameter vector
θ and an input vector x ∈ {−1, 1}n , the task is to
output the probability value p = RBMθ (x) thatthe distribution assigns to x.
A potentially easier task is to approximately evaluate an RBM to within some multiplicative factor:
given a parameter vector θ, a vector x ∈ {−1, 1}n ,and an approximation parameter c > 1, the task

Hardness for Restricted Boltzmann Machines

is to output a value p̂ such that1
· p ≤ p̂ ≤ c · p.
c
2. Simulating an RBM distribution: Given a
parameter vector θ and an approximation parameter 0 < η < 1, the task is to output an efficiently
evaluatable representation1 of a probability distribution P over {−1, 1}n such that the total variation distance between P and RBMθ is at mostη.
This paper shows that each of these tasks is computationally hard in the worst case, even if only a coarse
approximation to the correct output is required.
As our first main result, we show that if P 6= NP thenthe approximate evaluation task cannot be solved inpolynomial time even with approximation parameterc = eKn , where K > 0 may be any fixed constant.
(A precise statement of our hardness result, which issomewhat technical, is given as Theorem 8 in Section 4.) As our second main result, we show that if
RP 6= NP then there is no polynomial-time algorithm
for the simulation task with approximation parameterη = 1/12. (See Theorem 13 in Section 5 for a precise
statement.)
These results show strong worst-case limitations on
evaluating and simulating general RBMs, but in manycases one may only be dealing with RBMs thathave moderate-sized weights and relatively few hidden nodes. Thus it is of special interest to understand the complexity of approximately evaluating andsimulating RBMs of this sort. We consider the approximate evaluation and simulation tasks when the
RBM is restricted to have at most n hidden nodes andeach real parameter Ai,j , ai , bj has magnitude at most
ψ(n). Our hardness results stated above hold for any
bound ψ(n) that grows faster than linearly, i.e. suchthat limn→∞ ψ(n)n = ∞.

and Warmuth (AW92) showed that it is NP-hard to
approximate the maximum likelihood model for probabilistic automata with a fixed number of states but
a variable-sized alphabet. Kearns et al. (KMR+ 94)
showed that it is #P -hard to exactly evaluate probability models over {0, 1}n in which each observed bit isa disjunction of three unknown hidden variables, eachof which is assigned an unknown independent uniform
random bit. Roth (Rot96) showed that it is NP-hardto approximate the probability that a given node ina multiple-connected Bayesian belief network is true.
Bogdanov, Mossel and Vadhan (BMV08) studied thecomplexity of various computational tasks related toMarkov Random Fields. Yasuda and Tanaka (YT08)
claim that training RBMs is NP-hard, but such a claim
does not seem to address the approximate generation
and approximate simulation computational tasks that
we consider.
To the best of our knowledge, ours is the first work
establishing hardness of either evaluation or simulation(exact or approximate) for RBMs.
1.2. Our approach.
An important ingredient in our hardness results forboth evaluation and simulation is a more technical result (Theorem 1 in Section 3) which shows that it is
NP-hard to even coarsely approximate the value of thepartition function Zθ . We prove this by combining abinary search technique (Lemma 6) with a recent hardness result for approximating the pseudo-cut-norm ofa matrix due to Alon and Naor (AN04).
Our hardness result for approximate evaluation, Theorem 8, follows rather straightforwardly from Theorem 1. For our simulation hardness result, we combine Theorem 1 with ideas from Jerrum, Valiant andVazirani’s proof (JVV86) that approximate uniform
sampling from a set S and approximate counting of
the elements of S are polynomial-time equivalent.

1.1. Related work.

2. Background and Preliminaries

Our results have the same high-level flavor as thework of several previous researchers who have studied the computational complexity of various computational tasks for different types of probability distribution models. In an early work of this sort, Abe

We drop the subscript θ from Zθ when there is no
possibility of confusion. We sometimes concentrate onmodels whose parameters θ = (A, a, b) have a = ~0 andb = ~0. In this case, we sometimes replace θ with A,
for example writing RBMA and ZA .

1

We formalize the notion of an “efficiently evaluatable
representation of a distribution over {−1, 1}n ” in the following standard way: Such a representation consists of a
Boolean circuit of poly(n) size with k = poly(n) input bits
and n output bits. A draw from the distribution is obtainedby setting the input bits to an uniform random k-bit string
and reading the output string.

For A a matrix with real entries, we write ||A||∞ todenote maxi,j |Aij |. Similarly we write kak∞ to denotemaxi |ai | for a vector a.
For probability distributions P and Q over a finite
def
set S, the total variation distance is dT V (P, Q) =

Hardness for Restricted Boltzmann Machines

maxE⊆S |P (E) − Q(E)|.

Note that this is equiva-

deflent to dT V (P, Q) = maxE⊆S P (E) − Q(E) since
P (S − E) − Q(S − E) = Q(E) − P (E).
A function ψ is ω(n) if it grows faster than linearly,i.e., if limn→∞ ψ(n)n = ∞.

3. Approximating the partition
function is hard
The main result of this section is the following theorem, which says that it is hard to approximate thepartition function Zθ :Theorem 1 There is a universal constant ε > 0 suchthat if P 6= N P , then there is no polynomial-time algorithm with the following property: Given as input
an n × n matrix A satisfying kAk∞ ≤ ψ(n) (where thefunction ψ satisfies ψ(n) = ω(n)), the algorithm approximates the partition function ZA to within a multiplicative factor of eψ(n) .
Our proof uses a reduction from the problem of approximating a norm defined by Alon and Naor (AN04).
We refer to this norm, which is denoted by kAk∞7→1in (AN04), as the pseudo-cut-norm of A and denote it
simply by kAk.
Definition 2 The pseudo-cut-norm of an m × n realmatrix A is defined by
def||A|| =

max

h∈{−1,1}m ,x∈{−1,1}nhT Ax.

Theorem 3 ((AN04)) There is a universal constant ε > 0 such that, if P 6= NP, then there isno polynomial-time algorithm that approximates thepseudo-cut-norm to within a factor of 1 + ε.
The reduction in the proof of Theorem 3 in (AN04)
uses non-square matrices, but an easy corollary extends this hardness result to square matrices (we givethe simple proof in Appendix A):
Corollary 4 Theorem 3 holds even if the matrix isconstrained to be square.
We will need the following upper and lower bounds on
the pseudo-cut-norm of A:
Lemma 5 For an m × n matrix A, we have ||A||∞ ≤||A|| ≤ mn||A||∞ .
Proof: Alon and Naor (AN04) note that the pseudocut-norm satisfies||A|| ≥

maxu,v∈{0,1}nuT Av(the RHS above is the actual “cut-norm” of A). Since
Aij equals eTi Aej (where ei has a 1 in the ith coordinate and 0’s elsewhere), we get||A|| ≥ max |Aij | = kAk∞ .
i,jIt remains only to observe that for any h ∈{−1, 1}m , x ∈ {−1, 1}n , we haveX
hT Ax =
hi xj Aij ≤ mn||Aij ||∞ .

ij

3.1. Proof of Theorem 1
Throughout this section ψ denotes a function ψ(n) =ω(n) as in Theorem 1.
We first show that it is hard to distinguish between matrices with “large” versus “slightly less large” pseudocut-norm:
Lemma 6 There is a universal constant α > 0 suchthat if P 6= N P , then there is no polynomial-time algorithm to solve the following promise problem:
Input: An n-by-n matrix A such that||A||∞ ≤ ψ(n) and either (i) ||A|| > ψ(n);or (ii) ||A|| ≤ (1 − α)ψ(n).
Output: Answer whether (i) or (ii) holds.
Proof: The proof is by contradiction; so suppose thatfor every α > 0, ALGα is a polynomial-time algorithm
that solves the promise problem with parameter α.
We will show that there is a polynomial-time algorithm ALG0α (which performs a rough binary searchusing ALGα as a subroutine) that can approximate
the pseudo-cut-norm kBk of any n × n input matrix B
2

1. This yields
to within a multiplicative factor 1−αa contradiction with Corollary 4.
So let B be any n × n input matrix. Since ||λB|| =λ||B||, we may rescale B as a preprocessing step, so we
assume without loss of generality that B has ||B||∞ =1. Now fix any c > 1 and consider an execution of
ALGα on the matrix A = (ψ(n)/c)B. If ALGα returns“(i)” then (ii) does not hold, so ||A|| > (1 − α)ψ(n),which implies that kBk > (1 − α)c. Similarly, if ALGαreturns “(ii)” then B must have kBk ≤ c.
The algorithm ALG0α maintains an interval [`, u] of
possible values for log ||B|| which it successively prunes
using ALGα to do a rough binary search. Using
kBk∞ = 1 and Lemma 5, initially we may take[`, u] = [0, 2 ln n] to be an interval of length r0 = 2 ln n.

Hardness for Restricted Boltzmann Machines

After the tth stage of binary search using ALGα , the
new length rt of the interval is related to the old length
rt−1 by rt ≤ rt−1 /2 + log(1/(1 − α)). As long as rt−1
is at least 4 log(1/(1 − α)), this implies rt ≤ 3rt−1 /4.

so an approximation factor better than this would contradict Lemma 7, and thus any  < α/2 suffices in
Theorem 1.
So after O(log log n) iterations of binary search, ALG0α
narrows the initial interval [0, 2 ln n] to an interval [`, u]of width at most 4 log(1/(1 − α)). (We note that each
execution of ALGα in the binary search indeed uses
a value c which is at least 1 as required.) Algorithm
ALG0α outputs e(u+`)/2 as its estimate of kBk.

4. Approximate Evaluation is Hard

Since u − ` ≤ 4 log(1/(1 − α)) implies that eu−` ≤41, the estimate e(u+`)/2 is accurate for kBk
1−α
to within a multiplicative approximation factor of21. As noted at the start of the proof, since α1−αcould be any constant greater than 0, this contradicts
hardness of approximating kBk (Theorem 3).
2
An easy consequence of Lemma 6 is that it is hard to
distinguish between RBMs whose partition functions
are “large” versus “much less large”:
Lemma 7 There is a universal constant α > 0 suchthat if P 6= N P , then there is no polynomial-time algorithm to solve the following promise problem:
Input: An n-by-n matrix A such that||A||∞ ≤ ψ(n) and either (i) ZA >exp(ψ(n)); or (ii) ZA ≤ 4n exp((1 −α)ψ(n)).
Output: Answer whether (i) or (ii) holds.
Proof: By Lemma 6, if an n-by-n matrix A satisfies||A||∞ ≤ ψ(n) and either (a) maxh,x hT Ax > ψ(n)holds or (b) maxh,x hT Ax ≤ (1 − α)ψ(n) holds, it ishard to determine whether (a) or (b) holds.
It is clear that (a) implies (i) and that (b) implies(ii). Since ψ(n) = ω(n), for all but finitely many n wehave that the two alternatives (i) and (ii) are mutually
exclusive. So for all sufficiently large n, an algorithm
to determine whether (i) or (ii) holds could directly be
used to determine whether (a) or (b) holds.
2
Proof of Theorem 1: Let α > 0 be the constant from
Lemma 7. Let U = exp(ψ(n)) and L = 4n exp((1 −α)ψ(n)). An algorithm that canp approximate Z towithin a multiplicative factor of U/L can distinguish
Z ≥ U from Z < L. We haverUαψ(n) − n ln 4
= exp
,
L
2

In this section we show that it is hard to approximately
evaluate a given RBM A on a given input string x:
Theorem 8 There is a universal constant ε > 0 suchthat if P 6= N P , then there is no polynomial-time algorithm with the following property: Given as input
an n × n matrix A satisfying kAk∞ ≤ ψ(n) (where
the function ψ satisfies ψ(n) = ω(n)) and an input
string x ∈ {−1, 1}n , the algorithm approximates theprobability RBMA (x) to within a multiplicative factorof eψ(n) .
Note that since ψ(n) = ω(n), the above result implies
that approximating RBMA (x) to the smaller multiplicative factor eKn is also hard, where K may be any
positive constant.
We will use the fact that the numerator of the expression (1) for RBMA (x) can be computed efficiently,
which is known and not difficult to show. (Seee.g. (5.12) of (Ben09) for an explicit proof.)
Lemma 9 There is a poly(n)-timealgorithm that,P
given A and x, computes h∈{−1,1}n exp(hT Ax).
Now we are ready for the proof that evaluation is hard.
Proof of Theorem 8: We actually show somethingstronger: if P 6= NP then there is no polynomialtime algorithm which, given an RBM A as described,^A (x)), where RBM^A (x)
can output any pair (x, RBMεψ(n)is a multiplicative e-approximation to RBMA (x).
(In other words, not only is it hard to approximate
RBMA (x) for a worst-case pair (A, x), but for a worstcase A it is hard to approximate RBMA (x) for any x.)
To see this, note that since Lemma 9 implies that we
can efficiently exactly evaluate the numerator of theexpression (1) for RBMA (x), approximating RBMA (x)to within a given multiplicative factor is equivalent toapproximating 1/ZA to within the same factor.
But since f (u) = 1/u is monotone in u, for an estimate
Ze of Z and a desired approximation factor c, we ofcourse have that
1
1
1
1
× ≤
≤c×
c Z
Z
Ẑ
if and only if
cZ ≥ Ẑ ≥ Z/c,
so we are done by Theorem 1.

.

Hardness for Restricted Boltzmann Machines

5. Approximate Simulation is Hard
In this section we establish the hardness of constructing an efficiently evaluatable representation of any distribution P that is close to RBMθ , where θ = (A, a, b)
is a given set of RBM parameters. Our proof is inspired by Jerrum, Valiant and Vazirani’s proof thatapproximate counting reduces to approximate uniform
sampling (JVV86). To aid in explaining our proof, in
the following paragraph we briefly recall the idea ofthe (JVV86) reduction from approximate counting toapproximate uniform sampling, and then explain theconnection to our scenario.
n

Let S ⊆ {0, 1} be a set whose elements we would liketo approximately count, i.e. our goal is to approximate|S|. Suppose that ALG is an algorithm that can approximately sample a uniform element from S, i.e. eachelement of S is returned by ALG with some probability
1
1
1
· |S|
, (1 + τ ) · |S|]. The reduction proin the range [ 1+τceeds for n stages. In the first stage, by drawing samples from S using ALG, it is possible to approximately
estimate |S0 | and |S1 | where Sb is {x ∈ S : x1 = b}, sothat the larger one is estimated to within a multiplicative factor of (1 + 2τ ). Let b1 ∈ {0, 1} be the bit suchthat |Ŝb1 | ≥ |S|/2, where |Ŝb1 | is the estimated size of|Sb1 |, and let p̂1,b1 ≥ 1/2 denote |Ŝb1 |/|S|. In the second stage we repeat this process, using ALG on Sb1 ,to obtain values b2 , |Ŝb1 ,b2 | and p̂2,b2 , where |Ŝb1 ,b2 | isthe estimated size of Sb1 ,b2 = {x ∈ S : x1 = b1 andx2 = b2 }. By continuing in this way for n stages, wereachQa set Sb1 ,...,bn of size 1. The final estimate of |S|n
is 1/ i=1 p̂i,bi , and it can be shown that this is an accurate approximator of |S| to within a multiplicative
factor of (1 + 2τ )n .
In our setting the ability to approximately simulate agiven RBMθ distribution plays the role of the ability toapproximately sample from sets like Sb1 ,...,bi . Approximate counting of |S| corresponds to approximately
computing RBMθ (x) for a particular string x (whichcorresponds to the bitstring b1 . . . bn ). Since Theorem 1 implies that approximating RBMθ (x) is hard,
it must be the case that approximately simulating agiven RBM distribution is also hard.
5.1. Preliminaries
As the above proof sketch suggests, we will need tobuild RBM models for various distributions obtainedby conditioning on fixed values of some of the observed
variables.
Definition 10 Let P be a probability distribution over{−1, 1}n , i1 , . . . , ik be a list of distinct variable indicesfrom [n], and xi1 , . . . , xik be values for those variables.

We write cond(P ; Xi1 = xi1 , ..., Xik = xik ) to denotethe distribution obtained by drawing a random variable(X1 , ..., Xn ) distributed according to P and conditioning on the event that Xi1 = xi1 , ..., Xik = xik .
It will be helpful to have notation for the numerator in
the formula for the probability assigned by an RBM.
Definition 11 For an RBM θ = (A, a, b) and a stringx ∈ {−1, 1}n , define
P the energy of x w.r.t. θ, denotedby fθ (x), to be h∈{−1,1}n exp(hT a + hT Ax + bT x).
5.2. Building RBM Models for Conditional
Distributions
In the following lemmas, for parameters θ = (A, a, b)
we write kθk∞ to denote max{kAk∞ , kak∞ , kbk∞ }.
Lemma 12 There is a poly(n,1/η, kθk∞ )-time algorithm with the following properties: The algorithm
is given any η > 0, any parameters θ = (A, a, b)
where A is an n × n matrix (and all the parameters of A, a, b have poly(n) bits of precision), andany values u1 , . . . , uk ∈ {−1, 1} for observed variables X1 , . . . , Xk . The algorithm outputs a parameterization θ0 = (A0 , a0 , b0 ) of an RBM such thatdT V (RBMθ0 , cond(RBMθ ; X1 = u1 , ..., Xi = uk )) ≤ η.
Moreover, the matrix A is (n + k) × n, the parameterization θ0 satisfies kθ0 k∞ ≤ poly(kθk∞ , n, log 1/η),and all the parameters A0 , a0 , b0 have poly(n) +O(log log(1/η)) bits of precision.
Proof: We will start by describing how the algorithm
handles the case in which u1 = ... = uk = 1, and thendescribe how to handle the general case at the end of
the proof.
The RBM parameterized by θ0 is obtained from θ by• adding k extra hidden nodes;• adding k rows to A, and making An+j,j a large
positive value M (we will show that an integer
value that is not too large will suffice), and theother components of the n + jth row are all 0;• adding k components to a that are the same large
value M . The vector b0 equals b.
Roughly, the idea is as follows. Each hidden node
clamps the value of one variable. The role of an+j is
to clamp the value of the jth extra hidden variable to1. The role of An+j,j is to force Xj to be equal to thevalue of the jth extra hidden variable, and therefore
equal to 1.

Hardness for Restricted Boltzmann Machines

Let A0 , a0 and b0 be these parameters. Breaking up thevector of hidden variables into its new components andold components, and applying the definitions of A0 and
h0 , we havefθ0 (x1 , ..., xn )X
exp(hT a0 +hT A0 x+(b0 )T x)=
h∈{−1,1}n+k

X

=

X

exp(hT a+hT Ax+bT xh∈{−1,1}n g∈{−1,1}k+kX

M xj gj + M gj )j=1

fθ0 (x1 , ..., xn )


k
X
X
=
exp(
M xj gj + M gj )
j=1

×

X

by (2).

exp(hT a+hT Ax+bT x)

Finally, since c(x) differs from x in k components, wehave that for all x 6∈ F ,h∈{−1,1}n


=



k
X
exp(
M xj gj + M gj )

Xg∈{−1,1}kRBMθ0 (¬F )P
x6∈F ψ(x)fθ (x)=P
ψ(x)fθ (x)Px∈X
x6∈F ψ(x)fθ (x)≤Px∈F ψ(x)fθ (x)Pk(2 − 1) x6∈F ψ(x)fθ (x)= Pkx∈F (2 − 1)ψ(x)fθ (x)P(2k − 1) x6∈F ψ(x)fθ (x)= P
x6∈F ψ(c(x))fθ (c(x))(since, ∀x ∈ F, |c−1 ({x})| = 2k − 1)P
(2k − 1) x6∈F ψ(x)fθ (x)P=(since c(x) ∈ F )x6∈F ψ(F )fθ (c(x))
P
4k e−2M x6∈F fθ (x)P≤(5)
x6∈F fθ (c(x))

which immediately givesg∈{−1,1}kcomponents of x to 1. We havefθ (x) ≤ e2k(n+1)||θ||∞ fθ (c(x)).

j=1×fθ (x1 , ..., xn ).

(6)

Thus (5) implies that
RBMθ0 (¬F ) ≤ 4k e2k(n+1)||θ||∞ e−2M

Let F be the event that X1 = 1, ..., Xk = 1 and let


k
X
X
ψ(x) = exp(
M xj gj + M gj ) .
g∈{−1,1}k

and this, together with (3) and (4), implies
RBMθ0 (E) ≤ cond(RBMθ ; F )(E)+4k e2k(n+1)||θ||∞ e−2M .

j=1

Note that ψ(x) is maximized using any x ∈ F . Let
ψ(F ) be this value. Note that ψ(F ) ≥ e2kM , andψ(x) ≤ 2k e(2k−2)M otherwise, so that∀x 6∈ F, ψ(x) ≤ 2k e−2M ψ(F ).

(2)

Now fix any event E, and let X denote {−1, 1}n . We
have
RBMθ0 (E) ≤ RBMθ0 (E|F ) + RBMθ0 (¬F ).

This implies that RBMθ0 (E) ≤ cond(RBMθ ; F )(E) +η provided that M ≥ (1/2) ln(1/η) + k ln 2 + k(n +1)||θ||∞ . Since the event E was arbitrary, recalling thedefinition of total variation distance, this completes
the proof in the case u1 = ... = uk = 1.
The general case can be treated with a nearly identicalanalysis, after setting An+j,j to be uj M for each j =1, . . . , k.
2

(3)First,P
x∈E∩F ψ(F )fθ (x)= RBMθ (E|F ).
RBMθ0 (E|F ) = P
x∈F ψ(F )fθ (x)(4)
For any x 6∈ F , let the “correction” of x, called c(x),be the member of F obtained by setting the first k

5.3. Approximate Simulation is Hard
Theorem 13 If RP 6= N P , then there is no
polynomial-time algorithm with the following property:
Given as input θ = (A, a, b) such that A is an n × nmatrix and kθk∞ ≤ ψ(n) (where ψ(n) = ω(n)), thealgorithm outputs an efficiently evaluatable representation of a distribution whose total variation distancefrom RBMθ is at most η = 1/12.

Hardness for Restricted Boltzmann Machines

Proof: The proof is by contradiction; here is a highlevel outline. We will suppose that OUTPUT-DIST isa polynomial-time algorithm that, on input θ, constructs an η-close distribution to RBMθ . We willshow that there is a randomized algorithm which, using OUTPUT-DIST, with high probability (at least9/10) can efficiently find a particular x ∈ {−1, 1}nfor which the value of RBMθ (x) can be estimated towithin a multiplicative factor of 2n . Since RBMθ (x) =fθ (x)/Zθ , and we can efficiently exactly compute fθ (x)(see Lemma 9), this will imply that we can approximate Zθ to within a factor 2n . Since 2n is less thaneεψ(n) , where ε is the constant from Theorem 1, thiscontradicts Theorem 1 unless RP = NP.
The randomized algorithm creates x = (x1 , ..., xn ) as
follows. Fix δ = 1/10. Set θ1 = θ, and, for each i ∈ [n]in turn,• Run OUTPUT-DIST to obtain an efficiently evaluatable representation of a distribution Pi suchthat dT V (Pi , RBMθi ) ≤ η;
• Sample (4/η 2 ) log(n/δ) times from Pi (note that
this can be done efficiently);• Set xi to be the bit that appears most often for
the ith component Xi in the sampled strings;• Use Lemma 12 to construct a setofRBM
parameters
θi+1
such
that
dT V (RBMθi+1 , cond(RBMθ ; X1 = x1 , ..., Xi =xi )) ≤ η.
For each i ∈ [n] let p̂i denote the fraction of times
that Xi = xi over the samples drawn during the ith
stage. The Chernoff-Hoeffding bound implies that,with probability 1 − δ, for all i ∈ [n] we have|p̂i − Pi [Xi = xi ]| ≤ η(where the notation D[E] denotes the probability of event E under distribution D).
Since
dT V (Pi , RBMθi ) ≤ η, this implies that|p̂i − RBMθi [Xi = xi ]| ≤ 2η,and the fact that dT V (RBMθi , cond(RBMθ ; X1 =x1 , ..., Xi−1 = xi−1 )) ≤ η implies that|p̂i − RBMθ [Xi = xi | X1 = x1 , ..., Xi−1 = xi−1 ]| ≤ 3η.
Since η = 1/12 and p̂i ≥ 1/2, this implies that
RBMθ [Xi = xi | X1 = x1 , ..., Xi−1 = xi−1 ] ≥ 1/4

and therefore that
p̂i
1
≤
≤ 2.
2
RBMθ [Xi = xi | X1 = x1 , ..., Xi−1 = xi−1 ]|(7)
Let usQ compute an estimate p̂ of RBMθ (x) by settingp̂ = i p̂i . We can use the probability chain rule toevaluate the accuracy of this estimate as follows:
Q


pˆi
1 n
p̂
i
=Q
∈ n,2 .
RBMθ (x)2i RBMθ (xi |x1 ...xi−1 )As mentioned above, since RBMθ (x) = fθ (x)/Zθ andwe can exactly compute fθ (x) in polynomial time, this
implies that we can estimate 1/Zθ to within a 2n factor, and, as noted in the proof of Theorem 8, this
implies that we can estimate Zθ to within a 2n factor.
This contradicts Theorem 1 and completes the proof.
2

6. Discussion
We have established strong worst-case computational
hardness results for the basic tasks of evaluating andsimulating RBMs. We view these hardness results
as providing additional motivation to obtain a comprehensive theoretical understanding of why and how
RBMs perform well in practice. One possibility is thatthe parameters of real-world RBMs tend to be evensmaller than the bounds satisfied by the constructions
used to establish our results; the recent analysis of(BD09) seems to conform with this possibility. Further
study of the theoretical benefits of different properties
of RBM models, and of algorithms that promote those
properties, may lead to improvements in the practicalstate of the art of learning using these models.

References[AN04] N. Alon and A. Naor. Approximating the
cut-norm via Grothendieck’s inequality. In
STOC, pages 72–80, 2004.
[AW92] N. Abe and M. K. Warmuth. On the computational complexity of approximating
distributions by probabilistic automata.
Machine Learning, 9(2–3):205–260, 1992.
[BD09] Y. Bengio and O. Delalleau. Justifying andgeneralizing contrastive divergence. Neural Computation, 21(6):1601–1621, 2009.
[Ben09] Y. Bengio. Learning deep architectures for
AI. Foundations and Trends in Machine
Learning, 2(1):1–127, 2009.

Hardness for Restricted Boltzmann Machines[BMV08] A. Bogdanov, E. Mossel, and S. P. Vadhan.
The complexity of distinguishing markov
random fields. In APPROX-RANDOM,
pages 331–342, 2008.
[EBC+ ] D. Erhan, Y. Bengio, A. Courville,
P. Manzagol, P. Vincent, and S. Bengio.
Why does unsupervised pre-training help
deep learning? Journal of Machine Learning Research. To appear.
[FH91] Y. Freund and D. Haussler. Unsupervised
learning of distributions of binary vectors
using 2-layer networks. In NIPS, pages
912–919, 1991.
[Hin02] G. E. Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14(8):1771–
1800, 2002.
[HOT06] G. E. Hinton, S. Osindero, and Y. W.
Teh. A fast learning algorithm for deep belief nets. Neural Computation, 18(7):1527–
1554, 2006.
[JVV86] M. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution.
Theor. Comput. Sci., 43:169–188, 1986.
[KMR+ 94] M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie. On
the learnability of discrete distributions.
In Proc. of Twenty-sixth ACM Symposiumon Theory of Computing, pages 273–282,
1994.
[LEC+ 07] H. Larochelle, D. Erhan, A. C. Courville,
J. Bergstra, and Y. Bengio. An empiricalevaluation of deep architectures on problems with many factors of variation. In
ICML, pages 473–480, 2007.
[Rot96] D. Roth. On the hardness of approximate
reasoning. Artificial Intelligence, 82(12):273–302, 1996.
[Smo87] P. Smolensky. Information processing in
dynamical systems: Foundations of harmony theory. In D. E. Rumelhart, J. L.
McClelland, et al., editors, Parallel Distributed Processing: Volume 1: Foundations, pages 194–281. MIT Press, Cambridge, 1987.

[YT08] M. Yasuda and K. Tanaka.
Approximate
learning
algorithm
forrestricted boltzmann machines.
In
CIMCA/IAWTIC/ISE, pages 692–697,
2008.

A. Proof of Corollary 4
Let A be a non-square m×n matrix; we suppose m > n(the other case is entirely similar). We may pad A withm − n all-zero columns on the right, to form an m × m
matrix B which is at most quadratically larger than A.
We claim that the pseudo-cut-norm of B is the sameas the pseudo-cut-norm of A: for any h, u ∈ {−1, 1}m ,if we form x out of the first n components of u, then,since the last m − n columns of B are all zeroes, hT Bu
does not depend on the last m − n components of u,
so hT Bu = hT Ax. Since any h and x may be formed
this way, we have||A|| = max hT Ax = max hT Bu = ||B||.
h,x

h,u

Thus, a polynomial-time algorithm for approximating the pseudo-cut-norm for square matrices (like B)
to within an arbitrary constant factor would yield acorresponding polynomial-time algorithm for approximating the pseudo-cut-norm of matrices (like A) for
which m > n.