The Computational Complexity of Training ReLU(s)

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.

References in corpus (1)

• Complexity of Training ReLU Neural Network

Cited by in corpus (12)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Understanding and Improving Information Transfer in Multi-Task Learning
• Complexity of Training ReLU Neural Network
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• Approximation Schemes for ReLU Regression
• An Approximation Algorithm for training One-Node ReLU Neural Network
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• Interpreting and Disentangling Feature Components of Various Complexity from DNNs
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• ReLU Regression with Massart Noise