Going deep, reaching further: What can Boltzmann machines efficiently represent?

Tobias Reinhart, Gemma De les CovesarXiv 2026 · arXiv

TL;DR

This paper provides a theoretical foundation for why "deep" models outperform "shallow" ones by proving that depth and higher-order interactions significantly expand a model's efficient reach—the set of functions it can represent using only a polynomial number of parameters. The authors demonstrate that while both Restricted Boltzmann Machines (RBMs) and Deep Boltzmann Machines (DBMs) are "universal," only deep models can efficiently represent certain computationally hard functions (NP-hard and #P-hard), establishing a formal hierarchy of representational power.

What Problem Does This Paper Address?

In machine learning, we rely on Universal Approximation Theorems (UATs) to tell us that a model class (like neural networks) can represent any function. However, UATs have two major "blind spots":

  1. Efficiency: They often prove a model can represent a function but ignore that it might require an exponential number of neurons to do so.
  2. Depth Insensitivity: Traditional UATs often show that even a single hidden layer is "universal," failing to explain the widely observed empirical superiority of deep architectures.

The authors tackle these shortcomings by asking: Are all universal models equal in what they can represent efficiently? and What specific properties (like depth) characterize "efficiently universal" models?

Methods

The authors bridge machine learning and statistical physics by treating Boltzmann machines as spin models. They utilize several sophisticated theoretical frameworks:

  • Simulations: A formal way to show how one spin model can "mimic" another in its low-energy states.
  • Visible Closure: A new property introduced to characterize depth. It formalizes the idea that deep models can "hide" interactions within internal layers, allowing for modular, compositional representations.
  • Computational Complexity: They use the "non-collapse of the polynomial hierarchy" (a standard conjecture in CS theory) to prove that shallow models cannot represent certain functions that deep models can.
  • Communication Complexity: They apply bounds from multi-party communication games to prove a strict hierarchy among shallow models based on their "interaction order" (how many units interact at once).

Datasets

The paper is primarily theoretical and does not use standard image or text datasets. Instead, it uses "hard" mathematical target functions to test representational limits:

  • Ising Ground-State Energies ($G_n$): An NP-hard physics problem.
  • Ising Partition Functions ($Z_n$): A #P-hard counting problem.
  • $k$-party Inner Product Modulo 2 ($IP_k$): A function used to diagnose the limits of shallow models with $k$-body interactions.

Key Insights and Ideas

  • The Landscape of Efficient Reach: The authors map out a "landscape" where models are categorized by depth and interaction order. As seen in Figure 1, deep models (depth $\ge 3$) reach a "maximal" plateau of efficiency that shallow models can never touch, regardless of how many $k$-body interactions they have.
Figure 1: Efficient reach of machine learning models. The efficient reach (vertical axis), i.e. the efficient representation capabilities of several machine learning models, as a function of their depth and interaction order (horizontal axes), where the latter is the number of units involved in each interaction. Height depicts ordinal inclusion, so that larger efficient reach means the respective models can efficiently represent more targets. We prove that, for depth ≥3, there are models whose efficient reach is max- imal, irrespective of the interaction order. Models of depth 2 form an infinite hierarchy for increasing interaction order that saturates strictly below the maximal efficient reach (gray limit surface for depth 2 and interaction order →∞). RBMs (depth 2 and interaction order 2), 3-body RBMs (depth 2 and interaction order 3) and DBMs (depth ≥3 and interaction order 2) are located in the figure with visible spins/units in blue and hidden spins/units in red. They all have different efficient reach.
  • Visible Closure is the Key to Depth: The paper proves that for a model to be "maximal" (most efficient), it must be "visible closed." This property essentially means the model can turn visible units into hidden ones via simulation, which is a hallmark of deep, layered architectures like DBMs.
  • The Shallow Hierarchy: For shallow models (like RBMs), there is an infinite hierarchy. A model that allows 3 units to interact at once (3-body RBM) is strictly more powerful than a standard 2-body RBM, but it still falls short of the power provided by true depth.
Figure 3: Separation hierarchy for shallow models. Set diagram showing the efficient reach of var- ious machine learning model classes. Each rounded rectangle depicts the maximal set of target functions that the respective model class can efficiently simulate. All shown inclusions are proven to be strict. By definition maximal models have maximal efficient reach, i.e. can efficiently simulate all targets that can be efficiently simulated, including NP-hard functions such as the Ising ground-state function Gn. Shallow models have strictly smaller efficient reach; for example, they cannot efficiently simulate Gn. The efficient reach of shallow models is given by an infinite, strict inclusion hierarchy indexed by their interaction order k. Shallow (k + 1)-local models can efficiently simulate certain functions with large k-party communication complexity such as the k-party inner product modulo 2, IPk, whereas shallow k-local models cannot.

Key Results

  • DBMs are Maximal: The authors prove that DBMs with at least two hidden layers have maximal efficient reach.
  • Shallow Models Fail on Hard Tasks: They prove that shallow models (like RBMs) cannot efficiently simulate NP-hard ground-state energies or approximate #P-hard partition functions.
  • Empirical Validation: In numerical experiments, they showed that a 3-body RBM could learn the "Inner Product" function significantly better than a standard RBM with the same number of parameters, confirming that increasing interaction order helps when depth is restricted.

Limitations and Future Work

  • Asymptotic vs. Practical: The results are "asymptotic," meaning they distinguish between polynomial and exponential scaling. In practice, the specific degree of the polynomial (e.g., $n^2$ vs $n^{10}$) matters immensely for real-world performance.
  • Learning vs. Representation: The paper focuses on what a model can represent (existence), not necessarily what a specific algorithm like Gradient Descent will find (learnability).
  • Weight Constraints: Some results rely on the assumption of "small weights." The authors conjecture these results hold for larger weights but haven't proven it yet.
  • Extension to Other Models: While focused on Boltzmann machines, the authors suggest this framework could be extended to other architectures like feedforward neural networks or transformers.

Summary updated

Abstract

While universal approximation theorems theoretically underpin the representation capabilities of machine learning models, they have two shortcomings: They do not focus on efficient representations and they tend to be insensitive to depth and other heuristically important properties. In this work we show that these two shortcomings are intertwined. We prove that machine learning models which are deeper or have higher-order interactions can efficiently represent a larger set of functions, i.e. have larger efficient reach. It follows that deep Boltzmann machines (DBMs) have maximal efficient reach, restricted Boltzmann machines (RBMs) sub-maximal, and k-body generalizations of RBMs form a hierarchy between the two, even though all are universal. More generally, (i) we provide a full characterization of machine learning models with maximal efficient reach; (ii) we derive separations between deep and shallow models for three representation tasks; and (iii) we prove that the efficient reach of shallow models constitutes an infinite hierarchy indexed by the interaction order. The proofs draw on different methodologies, namely on (i) a recent characterization of universal spin models; (ii) computational complexity bounds for spin models; and (iii) communication complexity bounds applied to shallow models. This work shows that universal machine learning models can strongly differ in their efficient representation capabilities, and provides a theoretical foundation for heuristic observations.
BibTeX
@misc{reinhart2026going,
  author = {Tobias Reinhart and Gemma De les Coves},
  title = {{Going deep, reaching further: What can Boltzmann machines efficiently represent?}},
  year = {2026},
  eprint = {2610.39731},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39731},
}
Figure