# PAC-learning gains of Turing machines over circuits and neural networks

arXiv: https://arxiv.org/abs/2103.12686 · HTML: https://mlsanity.com/paper/2103.12686/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 43 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 12 of 12)

- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Why Deep Neural Networks for Function Approximation?](https://mlsanity.com/paper/1610.04161/) (2016)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [Relational recurrent neural networks](https://mlsanity.com/paper/1806.01822/) (2018)
- [Neural Random-Access Machines](https://mlsanity.com/paper/1511.06392/) (2015)
- [Learning to Reason with Third-Order Tensor Products](https://mlsanity.com/paper/1811.12143/) (2018)

## Abstract (arXiv)

A caveat to many applications of the current Deep Learning approach is the need for large-scale data. One improvement suggested by Kolmogorov Complexity results is to apply the minimum description length principle with computationally universal models. We study the potential gains in sample efficiency that this approach can bring in principle. We use polynomial-time Turing machines to represent computationally universal models and Boolean circuits to represent Artificial Neural Networks (ANNs) acting on finite-precision digits. Our analysis unravels direct links between our question and Computational Complexity results. We provide lower and upper bounds on the potential gains in sample efficiency between the MDL applied with Turing machines instead of ANNs. Our bounds depend on the bit-size of the input of the Boolean function to be learned. Furthermore, we highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.