The Computational Complexity of Training ReLU(s)

By Pasin Manurangsi, Daniel Reichman. 2018

47 citations recorded by the source corpus.

We consider the computational complexity of training depth-2 neural networks composed of rectified linear units (ReLUs). We show that, even for the case of a single ReLU, finding a set of weights that minimizes the squared error (even approximately) for a given training set is NP-hard. We also show that for a simple network consisting of two ReLUs, the error minimization problem is NP-hard, even in the realizable case. We complement these hardness results by showing that, when the weights and samples belong to the unit ball, one can (agnostically) properly and reliably learn depth-2 ReLUs with $k$ units and error at most $\epsilon$ in time $2^{(k/\epsilon)^{O(1)}}n^{O(1)}$; this extends upon a previous work of Goel, Kanade, Klivans and Thaler (2017) which provided efficient improper learning algorithms for ReLUs.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Stronger hardness results have been proved over the last decade [13, 15, 23, 32, 37, 38, 51].”
Proving the Lottery Ticket Hypothesis: Pruning is All You Need (2020, background): “Pruning Weights is Computationally Hard It is well known in the literature of neural networks that learning even a depth-two ReLU network is computationally hard in the general case (see [19, 21, 4]).”