Going deep, reaching further: What can Boltzmann machines efficiently represent?
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.
Related
- Classifications in modular restricted Boltzmann machines
- Updating zigzag representatives efficiently
- Efficiently Computed Marginal Likelihoods for Multivariate Mixture Models
- What does ethnic density represent? Spatial co-occurrence networks of a widely used contextual measure using harmonised UK small-area census data
- On the cost of reaching an attainable state for the boundary-controlled 1-D heat equation
BibTeX
@misc{reinhart2026going,
title = {{Going deep, reaching further: What can Boltzmann machines efficiently represent?}},
author = {Tobias Reinhart and Gemma De les Coves},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39731},
eprint = {2610.39731},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39731},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Going deep, reaching further: What can Boltzmann machines efficiently represent?
AU - Tobias Reinhart
AU - Gemma De les Coves
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39731
UR - https://arxiv.org/abs/2610.39731
AB - 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.
ER -