Rosenblatt's first theorem and frugality of deep learning

• URL: http://arxiv.org/abs/2208.13778v1
• Date: Mon, 29 Aug 2022 09:44:27 GMT
• Title: Rosenblatt's first theorem and frugality of deep learning
• Authors: A. N. Kirdin, S. V. Sidorov, N. Y. Zolotykh
• Abstract summary: 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. 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• On the Principles of ReLU Networks with One Hidden Layer [0.0]
  It remains unclear how to interpret the mechanism of its solutions obtained by the back-propagation algorithm. It is shown that, both theoretically and experimentally, the training solution for the one-dimensional input could be completely understood.
  arXiv  Detail & Related papers  (2024-11-11T05:51:11Z)
• Verified Neural Compressed Sensing [58.98637799432153]
  We develop the first (to the best of our knowledge) provably correct neural networks for a precise computational task. We show that for modest problem dimensions (up to 50), we can train neural networks that provably recover a sparse vector from linear and binarized linear measurements. We show that the complexity of the network can be adapted to the problem difficulty and solve problems where traditional compressed sensing methods are not known to provably work.
  arXiv  Detail & Related papers  (2024-05-07T12:20:12Z)
• Depth Separation with Multilayer Mean-Field Networks [14.01059700772468]
  We show that arXiv:1904.06984 constructed a function that is easy to approximate using a 3-layer network but not approximable by any 2-layer network. Our result relies on a new way of extending the mean-field limit to multilayer networks.
  arXiv  Detail & Related papers  (2023-04-03T15:18:16Z)
• From Compass and Ruler to Convolution and Nonlinearity: On the Surprising Difficulty of Understanding a Simple CNN Solving a Simple Geometric Estimation Task [6.230751621285322]
  We propose to address a simple well-posed learning problem using a simple convolutional neural network. Surprisingly, understanding what trained networks have learned is difficult and, to some extent, counter-intuitive.
  arXiv  Detail & Related papers  (2023-03-12T11:30:49Z)
• Reachability In Simple Neural Networks [2.7195102129095003]
  We show that NP-hardness already holds for restricted classes of simple specifications and neural networks. We give a thorough discussion and outlook of possible extensions for this direction of research on neural network verification.
  arXiv  Detail & Related papers  (2022-03-15T14:25:44Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Redundant representations help generalization in wide neural networks [71.38860635025907]
  We study the last hidden layer representations of various state-of-the-art convolutional neural networks. We find that if the last hidden representation is wide enough, its neurons tend to split into groups that carry identical information, and differ from each other only by statistically independent noise.
  arXiv  Detail & Related papers  (2021-06-07T10:18:54Z)
• A neural anisotropic view of underspecification in deep learning [60.119023683371736]
  We show that the way neural networks handle the underspecification of problems is highly dependent on the data representation. Our results highlight that understanding the architectural inductive bias in deep learning is fundamental to address the fairness, robustness, and generalization of these systems.
  arXiv  Detail & Related papers  (2021-04-29T14:31:09Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  We present a simple proof for the benefit of depth in multi-layer feedforward network with rectified activation ("depth separation") We present a concrete neural network with linear depth (in $m$) and small constant width ($leq 4$) that classifies the problem with zero error.
  arXiv  Detail & Related papers  (2021-01-18T15:40:27Z)
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations [160.33479656108926]
  In this work, we demonstrate that intermediate neural representations add more flexibility to neural networks. We show that neural representation can achieve improved sample complexities compared with the raw input. Our results characterize when neural representations are beneficial, and may provide a new perspective on why depth is important in deep learning.
  arXiv  Detail & Related papers  (2020-06-24T02:44:54Z)
• Neural Networks with Small Weights and Depth-Separation Barriers [40.66211670342284]
  For constant depths, existing results are limited to depths $2$ and $3$, and achieving results for higher depths has been an important question. We focus on feedforward ReLU networks, and prove fundamental barriers to proving such results beyond depth $4$.
  arXiv  Detail & Related papers  (2020-05-31T21:56:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.