On the complexity of loading shallow neural networks
We formalize a notion of loading information into connectionist networks that characterizes the training of feed-forward neural networks. This problem is NP-complete, so we look for tractable subcases of the problem by placing constraints on the network architecture. The focus of these constraints is on various families of ``shallow architectures which are defined to have bounded depth and unbounded width. We introduce a perspective on shallow networks, called the support cone interaction (SCI) graph, which is helpful in distinguishing tractable from intractable subcases: When the SCI graph is a tree or if of limited bandwidth, loading can be accomplished in polynomial time; when its bandwidth is not limited we find the problem NP-complete even if the SCI graph is a simple 2-dimensional planar grid.
- scientific article; zbMATH DE number 774006
- On the infeasibility of training neural networks with small mean-squared error
- Loading Deep Networks Is Hard: The Pyramidal Case
- The computational intractability of training sigmoidal neural networks
- Complexity of shallow networks representing finite mappings
- Wrappers for feature subset selection
- A review of combinatorial problems arising in feedforward neural network design
- On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
- Stable recovery of entangled weights: towards robust identification of deep neural networks from minimal samples
- Information theory and recovery algorithms for data fusion in Earth observation
- Training a Single Sigmoidal Neuron Is Hard
- scientific article; zbMATH DE number 774006 (Why is no real title available?)
- scientific article; zbMATH DE number 910890 (Why is no real title available?)
- On the complexity of approximating and illuminating three-dimensional convex polyhedra
- Neural networks and complexity theory
- Loading Deep Networks Is Hard: The Pyramidal Case
- On minimal representations of shallow ReLU networks
- Complexity of network training for classes of Neural Networks
- Efficient identification of wide shallow neural networks with biases
- Tight hardness results for training depth-2 ReLU networks
- Learning from hints in neural networks
- On learning a union of half spaces
This page was built for publication: On the complexity of loading shallow neural networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105389)
