Restricted Boltzmann Machines Are Hard to Approximately Evaluate or Simulate

Abstract

Restricted Boltzmann Machines (RBMs) are a type of probability modelover the Boolean cube {-1,1\}^n that have recently received muchattention. We establish the intractability of two basiccomputational tasks involving RBMs, even if only a coarseapproximation to the correct output is required. We first show that assuming P != NP, for any fixed positive constant K (which may be arbitrarily large)there is no polynomial-time algorithm for the followingproblem: given an n-bit input string x and the parameters of aRBM M, output an estimate of the probability assigned to x byM that is accurate to within a multiplicative factor ofe^Kn. This hardness result holds even if the parametersof M are constrained to be at most psi(n) for anyfunction psi(n) = \omega(n), and if the number of hidden nodes ofM is at most n.We then show that assuming RP != NP,there is no polynomial-time randomized algorithm for thefollowing problem: given the parameters of an RBM M, generate arandom example from a probability distribution whose total variationdistance from the distribution defined by M is at most 1/12.