Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate

Philip M. Long, Rocco A. ServedioICML 2010

Introduction

Restricted Boltzmann Machines (RBMs) were foundational to the "Deep Belief Network" era of deep learning, serving as ubiquitous building blocks for probabilistic modeling. However, this paper demonstrates that RBMs are computationally "hard" in a fundamental sense. Specifically, the authors prove that even approximately calculating the probability of an input or generating a random sample from an RBM is NP-hard. This theoretical result suggests that the practical success of RBMs relies on specific, non-worst-case properties rather than general algorithmic efficiency.

The Problem: Evaluation and Simulation

RBMs are probabilistic models that utilize a layer of visible units and a layer of hidden units to capture complex data distributions. Utilizing these models typically requires researchers to perform two core tasks:

  1. Evaluation: Determining the probability the model assigns to a specific input $x$.
  2. Simulation: Generating a new, random example from the model's learned distribution.

Because the partition function (the normalizing constant $Z$) requires summing over an exponential number of possible states, exact calculation is notoriously intractable. This paper investigates a more profound question: Is it possible to obtain even a rough approximation of these values in a reasonable (polynomial) amount of time?

Theoretical Framework and Methodology

As a purely theoretical work, this research does not rely on empirical datasets. Instead, the authors leverage computational complexity theory to establish hardness results through a rigorous logical chain:

  • The Pseudo-Cut-Norm Connection: The foundation of the proof relies on a known hard problem from combinatorial optimization: approximating the "pseudo-cut-norm" of a matrix.
  • Hardness of the Partition Function: The authors demonstrate that coarsely approximating the partition function $Z$ of an RBM would allow one to solve the pseudo-cut-norm problem. Because the latter is NP-hard, approximating $Z$ must also be NP-hard.
  • Reduction to Evaluation: Approximating the probability of a single input $x$ is mathematically equivalent to approximating $1/Z$.
  • Reduction to Simulation: Utilizing a classic technique from Jerrum, Valiant, and Vazirani (1986), the authors prove that a "black box" capable of generating samples from an RBM could be used to estimate the partition function. Thus, if counting (estimating $Z$) is hard, sampling must inherently be hard as well.

Key Insights

  • The "Coarseness" of Hardness: The most striking revelation is the sheer scale of approximation error that remains computationally hard. The authors prove that even if one accepts an enormous multiplicative error factor of $e^{Kn}$ (which grows with the input size), the problem remains NP-hard.
  • Sampling is as Hard as Counting: In machine learning, it is often assumed that intractable probabilities can be bypassed via sampling (e.g., using Markov Chain Monte Carlo methods). This paper formalizes that, for RBMs, evaluation and simulation are inextricably linked at a fundamental complexity level.
  • The Role of Weights: These hardness results hold even when the number of hidden nodes is limited and weights are constrained to grow only slightly faster than linearly. The intractability is not merely an artifact of infinitely large weights or unbounded hidden units.

Main Results

The paper formalizes its findings through several key theorems:

  • The Partition Function Bottleneck (Theorem 1): The core technical result establishes that approximating the normalizing constant $Z$ is the fundamental computational bottleneck.
  • Evaluation Hardness (Theorem 8): Assuming $P \neq NP$, there is no polynomial-time algorithm that can estimate the probability assigned to an input $x$ by an RBM within a multiplicative factor of $e^{\epsilon \psi(n)}$.
  • Simulation Hardness (Theorem 13): Assuming $RP \neq NP$, there is no polynomial-time randomized algorithm that can generate a sample from a distribution that is within a Total Variation Distance of $1/12$ from the true RBM distribution.

Limitations and Practical Implications

While the theoretical results are robust, they come with important caveats that explain why RBMs can still be useful in practice:

  • Worst-Case vs. Average-Case: These proofs establish worst-case scenarios—showing that there exist RBMs that are impossible to solve efficiently. They do not necessarily imply that the specific RBMs trained on real-world data (like images or speech) exhibit this same hardness.
  • Weight Constraints: The proofs require weights that grow faster than linearly. Real-world models often employ "small" weights or structural regularities, which might bypass these theoretical hardness limits.
  • Practical Heuristics: The paper establishes a theoretical "speed limit" on exact or approximate evaluation, but it leaves open the question of why heuristics like Contrastive Divergence (CD) perform well enough to train useful models, despite not performing "true" simulation.

Summary updated

BibTeX
@inproceedings{long2010restricted,
  author = {Philip M. Long and Rocco A. Servedio},
  title = {{Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
}
Figure