The Computational Complexity of Training ReLU(s)
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
An efficient black-box reduction from PQ to TDS learning for any Boolean concept class in the distribution-free setting implies hardness for TDS learning of halfspaces, while membership queries enable efficient PQ lea...
-
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
PQ and TDS learning are equivalent in the distribution-free setting for Boolean classes, implying hardness for TDS halfspace learning but efficient algorithms with membership queries.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.