Original Contribution: Training a 3-node neural network is NP-complete

By Avrim Blum, R. Rivest. 1992

Subfields: Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

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

In Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks (2018, neutral): “…the average distance, measured using a loss function L , between the network’s predictions on the training dataset and ground-truth, i.e., For DNNs, the training problem is NP-Hard [8] and is typically solved using sophisticated heuristic procedures such as stochastic gradient descent (SGD).”
BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain (2017, background): “Indeed, the problem in its most general form has been shown to be NP-Hard [19].”
Visualizing the Loss Landscape of Neural Nets (2017, background): “Despite the NP-hardness of training general neural loss functions [2], simple gradient methods often find global minimizers (parameter configurations with zero or near-zero training loss), even when data and labels are randomized before training [42].”
Deep Learning without Poor Local Minima (2016, background): “Unfortunately, it was shown in 1992 that training a very simple neural network is indeed NP-hard (Blum & Rivest, 1992).”
fPINNs: Fractional Physics-Informed Neural Networks (2018, background): “000parameterstobeoptimized. There are multiple local minima for the loss function, and the gradient-based optimizer almost surely getsstuckinoneofthelocalminima[61];ﬁndingglobalminimaisaNP-hardproblem[62,63]. InFig.5wecomparethesolutionsoffPINNsagainstFDM.WerunthefPINNcode10times, eachtimetryingdiﬀe”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “It is well known that without any additional assumption, even training a shallow neural network is an NP-hard problem (Blum and Rivest, 1989).”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “It is well-known that, training one hidden layer neural network is NP-complete (Blum & Rivest, 1988).”
Diverse Neural Network Learns True Target Functions (2016, methodology): “ smaller models as shown in [Barron, 1993]. However it is a non-convex problem and it is difﬁcult to ﬁnd the global optima. e.g., one-hidden-layer networks are NP-complete to learn in the worst case [Blum and Rivest, 1993]. We will make novel use of techniques from kernel methods to analyze learning”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, methodology): “For example, (Blum & Rivest, 1993) show that learning a neural network with one hidden layer with a sign activation function is NP-hard in the realizable case.”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, background): “From the point of view of learning theory, it is well known that training a neural network is hard in the worst cases [Blum and Rivest, 1989, Livni et al., 2014, ˇS´ıma, 2002, Shalev-Shwartz et al., 2017a,b] and recently, Shamir [2016] showed that assumptions on both the target function and the…”