Training a Single Sigmoidal Neuron Is Hard

By Jirí Síma. 2002

61 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “Most previous results on learning neural network are negative [39, 28, 38], or positive but with algorithms other than SGD [23, 43, 37, 14, 15, 16], or with strong assumptions on the model [1, 2].”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, background): “However, theoretical explanations seem to lag far behind this empirical success (though many hardness results exist , e.g. , (Síma, 2002; Shamir, 2016)).”
The loss surface and expressivity of deep convolutional neural networks (2017, background): “…well known that the optimization problem for training neural networks can have exponentially many local minima (Auer et al., 1996; Safran & Shamir, 2016) and NP-hardness has been shown in many cases (Blum & Rivest., 1989; Sima, 2002; Livni et al., 2014; Shamir, 2017; Shalev-Shwartz et al., 2017).”
Generalization Bounds for Neural Networks through Tensor Factorization (2015, background): “There are extensive negative results on training neural networks, and training even simple networks with guaranteed generalization bounds, e.g., a network with a single neuron, is NP-hard (Rojas, 1996; ˇS´ıma, 2002; Blum and Rivest, 1993; Bartlett and Ben-David, 1999; Kuhlmann, 2000).”
Global optimization issues in deep network regression: an overview (2018, background): “Even the WO problems arising in the easiest architecture of network (shallow network with few neurons) are NP-hard [23,128], so that the structure of the problem does not allow any simpliﬁcation.”
Collapse of Deep and Narrow Neural Nets (2018, result): “While the aforementioned theoretical results are very powerful, they do not necessarily coincide with the results of training of NNs in practice which is NP-hard ( ˇ S ´ ıma, 2002).”
The Loss Surface of Deep and Wide Neural Networks (2017, background): “It has been shown that the training of a network with a single neuron with a variety of activation functions turns out to be NP-hard (Sima, 2002).”
Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods (2017, background): “The findings are mostly negative (Rojas, 1996; Š́ıma, 2002; Blum and Rivest, 1993; Bartlett and Ben-David, 1999; Kuhlmann, 2000).”
Trends and Applications in Constructive Approximation Evolutionary Optimization of Neural Systems: the Use of Strategy Adaptation (unknown): “However, the general question of how to efficiently design an appropriate neural system for a given problem remains open and complexity theory reveals the need for using heuristics (e.g., [41]).”
Optimization Landscape and Expressivity of Deep CNNs (2017, background): “…well known that the optimization problem for training neural networks can have exponentially many local minima (Auer et al., 1996; Safran & Shamir, 2016) and NP-hardness has been shown in many cases (Blum & Rivest., 1989; Sima, 2002; Livni et al., 2014; Shamir, 2017; Shalev-Shwartz et al., 2017).”