# Rosenblatt's first theorem and frugality of deep learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 29 Aug 2022.

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

- [The Modern Mathematics of Deep Learning](https://mlsanity.com/paper/2105.04026/) (2021)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Trajectories, bifurcations and pseudotime in large clinical datasets: applications to myocardial infarction and diabetes data](https://mlsanity.com/paper/2007.03788/) (2020)
- [Robust And Scalable Learning Of Complex Dataset Topologies Via Elpigraph](https://mlsanity.com/paper/1804.07580/) (2018)
- [How deep should be the depth of convolutional neural networks: a backyard dog case study](https://mlsanity.com/paper/1805.01516/) (2018)

## Built on by (most cited first, 2 of 2)

- [The Boundaries of Verifiable Accuracy, Robustness, and Generalisation in Deep Learning](https://mlsanity.com/paper/2309.07072/) (2023)
- [A new Uncertainty Principle in Machine Learning](https://mlsanity.com/paper/2603.06634/) (2026)

## Abstract (arXiv)

First Rosenblatt's theorem about omnipotence of shallow networks states that elementary perceptrons can solve any classification problem if there are no discrepancies in the training set. Minsky and Papert considered elementary perceptrons with restrictions on the neural inputs: a bounded number of connections or a relatively small diameter of the receptive field for each neuron at the hidden layer. They proved that under these constraints, an elementary perceptron cannot solve some problems, such as the connectivity of input images or the parity of pixels in them. In this note, we demonstrated first Rosenblatt's theorem at work, showed how an elementary perceptron can solve a version of the travel maze problem, and analysed the complexity of that solution. We constructed also a deep network algorithm for the same problem. It is much more efficient. The shallow network uses an exponentially large number of neurons on the hidden layer (Rosenblatt's A-elements), whereas for the deep network the second order polynomial complexity is sufficient. We demonstrated that for the same complex problem deep network can be much smaller and reveal a heuristic behind this effect.