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

Tobias Reinhart; Gemma De les Coves

cs.LGOct 29, 2026

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

Authors: Tobias Reinhart, Gemma De les Coves

Organizations: Institute for Theoretical Physics, University of Innsbruck,, Technikerstr. 21a, A-6020 Innsbruck, Austria · ICREA, Institució Catalana d’Estudis i Recerca Avançats, Passeig Lluís Companys 23, 08010 Barcelona · Departament d’Enginyeria, Universitat Pompeu Fabra, Carrer Tànger 122, 08018 Barcelona

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.

Figures & tables

Panel of Figure 1 — 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 $\geq 3$ , there are models whose efficient reach is maximal, 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 $\to\infty$ ). RBMs (depth $2$ and interaction order $2$ ), $3$ -body RBMs (depth $2$ and interaction order $3$ ) and DBMs (depth $\geq 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.

Panel of Figure 2 — Figure 2: Characterization of maximal models. Set diagram showing properties of machine learning models and their interplay in our characterization of maximal models. Inclusions are not necessarily strict. The three properties given by universal, visible closed and maximal, are such that any two of them imply the third. The area where the three properties hold is depicted in a blue-gray shade. Maximal models are necessarily deep. DBMs are maximal. RBMs and $3$ -body RBMs are universal, but are not deep, and thus not maximal. We expect most “natural” deep models to be visible closed, and hence most deep universal models to be maximal.

Representation task	shallow	maximal	maximal and strongly visible closed
Simulate $\mathsf{NP}$ -hard ground-state energies $G_{n}$ ( Theorem 20 )	$\times$ No	$\checkmark$ Yes	$\checkmark$ Yes
Approximate $\mathsf{\#P}$ -hard partition functions $Z_{n}$ in unnormalized marginals ( Theorem 24 )	$\times$ No	—	$\checkmark$ Yes
Approximate $\mathsf{\#P}$ -hard distributions $q_{n}\propto Z_{n}$ in normalized marginals ( Theorem 26 )	$\times$ No	—	$\checkmark$ Yes

Table 1: Separation between shallow and maximal models. We consider three representation tasks and prove separations between shallow and maximal models.

\mathsf{NP}

-hard functions such as the Ising ground-state function

G_{n}

can be efficiently simulated by maximal models, but not by shallow models.

\mathsf{\#P}

-hard functions such as the Ising partition function

Z_{n}

(and respective probability distribution

q_{n}\propto Z_{n}

) can be efficiently approximated by maximal and strongly visible closed models in their unnormalized (normalized) visible spin marginals. Shallow models cannot carry out these tasks.

Panel of Figure 3 — Figure 3: Separation hierarchy for shallow models. Set diagram showing the efficient reach of various 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 $\mathsf{NP}$ -hard functions such as the Ising ground-state function $G_{n}$ . Shallow models have strictly smaller efficient reach; for example, they cannot efficiently simulate $G_{n}$ . 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$ , $\mathrm{IP}_{k}$ , whereas shallow $k$ -local models cannot.

Panel of Figure 4 — Figure 4: Ising system and model. A 2d (square lattice) Ising system 4(a) , spins are blue vertices, their interactions are attached to edges of the graph and are not explicitly shown, and the 2d Ising model 4(b) , that is, the set of all such 2d Ising systems, for arbitrary system size and local couplings. Both are defined in Example 2 .

Panel of Figure 5 — Figure 5: Example of a simulation. A source system $S$ ( 5(a) , LHS) physical spins in opaque, auxiliary spins in transparent) simulates a target system $T$ ( 5(a) , RHS) if $\min_{\mathbf{h}}H_{S}(\mathbf{v},\mathbf{h})=H_{T}(\mathbf{v})+\Gamma$ . This condition relates the two respective energy functions, as shown in 5(b) . In this example, the simulation has constant degeneracy $d=1$ , so each target configuration ( 5(b) , RHS) $\mathbf{v}_{i}$ has a unique source configuration ( 5(b) , LHS) $(\mathbf{v}_{i},\mathbf{h}_{\min}(\mathbf{v}_{i}))$ with up to a shift of $\Gamma$ , equal energy. The cut-off $\Delta$ of the simulation is the minimal energy gap between “correct” auxiliary configuration ( $\mathbf{h}_{\min}(\mathbf{v})$ , thick lines), and “incorrect” auxiliary configurations (dashed lines).

Panel of Figure 6 — Figure 6: RBM 6(a) and DBM 6(b) , visible spins (or units) in blue, hidden spins (or units) in red. Both have pair-interactions, attached to edges between spins and fields, attached to the individual spins. The respective couplings (or weights) of both are not explicitly shown.

Panel of Figure 7 — Figure 7: The elliptic shapes depict the set of all spin models, with squares representing individual models. Fig. 7(a) A universal spin model (light blue square) can simulate (indicated by arrows) all spin models (dark grey squares). Fig. 7(b) In contrast to that a p-maximal model (dark blue square) can efficiently simulate (indicated by arrows) all models that can be efficiently simulated, i.e. are reached by an arrow (light blue-grey squares). There exist models that cannot be efficiently simulated, i.e. are not reached by an arrow (dark grey squares).

Panel of Figure 8 — Figure 8: Compositions of visible simulations are not visible. A spin ML system $S$ and two spin systems $T$ and $R$ , all depicted as abstract sets (gray boxes) of spins (blue and red dots, blue spins are visible red spins are hidden). The systems provide a chain of simulations $T\longrightarrow R$ and $S\overset{\mathrm{v}}{\longrightarrow}T$ so their composition yields $S\longrightarrow R$ . Physical spins of this composition simulation are opaque, auxiliary spins are transparent. The composition $S\longrightarrow R$ is not visible as visible spins of $S$ agree with spins of $T$ while physical spins of $S\longrightarrow R$ (blue, opaque) agree with spins of $R$ .

Panel of Figure 9 — Figure 9: Visible closure and composition of simulations. Spin ML systems $S,S^{\prime}$ and $S^{\prime\prime}$ depicted as abstract sets (gray boxes) of spins (visible spins in blue hidden spins in red). $S^{\prime}$ is obtained from $S$ by restricting visible spins to a subset $V^{\prime}$ , i.e. visible spins outside of $V^{\prime}$ are made hidden. This yields a system $S^{\prime}$ . If $S\in\mathcal{M}$ and $\mathcal{M}$ is strictly visible closed then also $S^{\prime}\in\mathcal{M}$ . If $\mathcal{M}$ is strongly visible closed then it simulates $S^{\prime}$ , i.e. there exists some system $S^{\prime\prime}\in\mathcal{M}$ with visible spins $V^{\prime}$ that simulates $S^{\prime}$ (physical spins opaque, auxiliary spins transparent, note that by definition, all auxiliary spins must be hidden). If $\mathcal{M}$ is visible closed then it visibly simulates the effective Hamiltonian of $S^{\prime}$ over its visible spins $V^{\prime}$ (not shown).

Panel of Figure 10 — Figure 10: Visible closure of DBMs. DBMs of depth at least 3 are strictly visible closed; making visible spins hidden introduces hidden spins (red) in the bottom layer (RHS system). However, these can equivalently be considered as belonging to the second hidden layer (LHS system). The two systems are equivalent and only differ w.r.t. their drawing.

Panel of Figure 11 — Figure 11: A fully connected $3$ -body RBM. Visible spins in blue hidden spins in red. Each translucent triangle denotes a three-body interaction involving one hidden spin and two distinct visible spins.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

configuration $(v_{i},v_{j},m_{i,j},a_{i,j})$	energy $H_{T_{i,j}}(v_{i},v_{j},m_{i,j},a_{i,j})$
$(-1,-1,-1,-1)$	$2+4\Delta$
$(-1,-1,-1,1)$	$0$
$(-1,-1,1,-1)$	$3+12\Delta$
$(-1,-1,1,1)$	$1$
$(-1,1,-1,-1)$	$0$
$(-1,1,-1,1)$	$-2+4\Delta$

Appendix

Table 2: Values of

H_{T_{i,j}}

simulating

S_{i,j}

Panel of Figure 12 — Figure 12: System $T_{i,j}^{\prime}$ that simulates $T_{i,j}$ . The additional spins $v_{i}^{\prime},v_{j}^{\prime}$ ensure that $T_{i,j}^{\prime}$ is compatible with the DBM constraints. They are coupled to $v_{i},v_{j}$ with strong ferromagnetic coupling $-\Delta^{\prime}$ such that in the low-energy sector $v_{i}^{\prime}=v_{i}$ and $v_{j}^{\prime}=v_{j}$ .

RBM			3RBM
$m$	$P$	Best KL	$m$	$P$	Best KL
24	324	$0.247303$	4	328	$0.253821$
73	961	$0.136275$	12	960	$0.065374$
219	2859	$0.014836$	36	2856	$0.000200$

Appendix

Table 3: Exact population optimization of the IP target at

n=6

\beta=1

B=4

. Each entry is the best of five starts with the same optimization limits. The KL values are evaluated by full enumeration, but the minima are not certified.

Quantity	$n=8$	$n=12$
Visible spins $d$	16	24
Hidden spins $m$ , RBM / 3RBM	$516\,/\,64$	$1734\,/\,144$
Parameters $P$ , RBM / 3RBM	$8788\,/\,8784$	$43374\,/\,43368$
Independent training draws $N$	$131\,072$	$33\,554\,432$
Minibatch size $b$ (also $b^{\prime}$ )	$256$	$4096$
Parameter updates $U$	$50\,000$	$480\,000$

Appendix

Table 4: Budgets for learning the IP distribution. All runs use

\beta=1

B=4

, zero initial fields, Gaussian initial couplings of standard deviation

0.05

, and gradient-norm clipping at

10

. At

n=8

the learning rate stays at

0.002

for the first

25\,000

updates, then decreases along a cosine schedule to

0.0002

. At

n=12

it remains

0.004/3

throughout. These are matched budgets within each size, not a comparison at fixed resources across sizes.

Size	Model	Final KL	Final $R_{S}$	Training time
$n=8$	RBM	$0.32633\;[0.32614,0.32647]$	$0.999\;[0.998,0.999]$	$3.36$ min
	3RBM	$0.10414\;[0.10107,0.10547]$	$0.562\;[0.558,0.565]$	$5.17$ min
$n=12$	RBM	—	$1.003\;[1.002,1.003]$	$3.07$ h
	3RBM	—	$0.512\;[0.505,0.553]$	$1.82$ h

Appendix

Table 5: Final-checkpoint results: median and full range in brackets over three repetitions. Ranges describe run-to-run variation, not confidence intervals. KL is exact at

n=8

and unavailable here at

n=12

;

R_{S}

is estimated from uniform probes at both sizes. Times are medians of measured training wall time, excluding subsequent checkpoint evaluation and dataset generation.

Figure 13: Learning the IP target with parameter-matched RBMs and all-pairs 3RBMs. Top: exact population KL at

n=8

. Bottom: estimated energy error

R_{S}

n=12

. Left: error versus parameter updates; right: the same checkpoints versus measured training time. Thin lines show all three repetitions. Thick lines join checkpoint medians; in the time panels, both time and error are medians at each common update count, rather than interpolated equal-time averages. Dashed lines give the uniform-distribution KL (top) and constant-energy error

R_{S}=1

(bottom). The two rows use different error measures and time units.

Figure 14: Representative non-IP comparisons at

d=16

. Smaller KL is better; the horizontal axis is logarithmic. Each target has two instances, each with three training repetitions (small symbols); vertical ticks mark medians and horizontal lines span the full range, not confidence intervals. Unlike the final-checkpoint IP results, CD depth and checkpoint are chosen by maximizing mean single-bit conditional log probability on

2048

independent validation configurations, not by minimizing the plotted KL. Candidate checkpoints are

250

1000

3000

10\,000

20\,000

, and additionally

30\,000

for interacting targets. Both architectures receive the same data and search budgets, but not equal wall time. These are selected families from a broader exploratory comparison.

Restricted Boltzmann Machines

Restricted Boltzmann Machines (RBMs) are energy-based models that learn probability distributions using linked visible and hidden units.

See all 18 papers

Any-Dimensional Invariant Universality
May 22, 2026Shengtai Yao, Eitan Levin, Mateo DíazUniversal Approximation Neural Network Approximation Theory
Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD 21218, USA. · Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125, USA.
Characterizing Universal Object Representations Across Vision Models
May 13, 2026Florian P. Mahner, Johannes Roth, Ka Chun Lam +3Visual Representation Learning Representation Alignment
Vision and Computational Cognition Group Max Planck Institute Justus-Liebig-University Giessen · Machine Learning Core National Institute of Mental Health Bethesda, MD, USA · Department of Cognitive Science Johns Hopkins University Baltimore, MD, USA
Communication Complexity of Universal Features
Oct 19, 2026Lunjia Hu, Anish Jayant, Peter Li +2Representation Learning Communication Complexity
Northeastern University · Georgia Institute of Technology · Harvard University

May 22, 2026J/K move · Enter open · S save

Any-Dimensional Invariant Universality

Shengtai Yao, Eitan Levin, Mateo Díaz

Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD 21218, USA. · Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125, USA.

Universal Approximation Neural Network Approximation Theory

Open paper AskPDF arXiv

Several machine learning models are defined for inputs of any size, such as graphs with different numbers of nodes and point clouds containing varying numbers of points. The universality properties of such any-dimensional models remain poorly understood, as universality is traditionally studied for models accepting inputs of a fixed size, defined on a compact subset of their domain. In sharp contrast, any-dimensional models can be viewed as sequences of functions defined on growing-sized inputs, and it is not clear in which sense they can be universal. We develop a systematic approach to establish any-dimensional universality, by identifying any-dimensional functions with a unique function taking inputs in a suitable infinite-dimensional limit space containing inputs of all finite sizes as well as their limits. Using the symmetries of these inputs and relations between inputs of different sizes, we show that this limit space admits a natural topology with rich families of compact sets on which any-dimensional universality can be established. We illustrate our approach by showing that several existing architectures fail to be universal, and we propose simple modifications that restore universality.

Abstract

Restricted Boltzmann Machines

Explore similar work

Any-Dimensional Invariant Universality

Characterizing Universal Object Representations Across Vision Models

Communication Complexity of Universal Features