Rosenblatt’s first theorem and frugality of deep learning. (arXiv:2208.13778v1 [cs.LG])

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.