Complexity of Training ReLU Neural Network

Abstract

In this paper, we explore some basic questions on the complexity of training neural networks with ReLU activation function. We show that it is NP-hard to train a two-hidden layer feedforward ReLU neural network. If dimension of the input data and the network topology is fixed, then we show that there exists a polynomial time algorithm for the same training problem. We also show that if sufficient over-parameterization is provided in the first hidden layer of ReLU neural network, then there is a polynomial time algorithm which finds weights such that output of the over-parameterized ReLU neural network matches with the output of the given data.

arXiv commentHardness proof has been simplified. Accepted for publication at Discrete Optimization

References in corpus (4)

• Understanding deep learning requires rethinking generalization
• On the Computational Efficiency of Training Neural Networks
• The Computational Complexity of Training ReLU(s)
• An Approximation Algorithm for training One-Node ReLU Neural Network

Cited by in corpus (10)

• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Market Driven Multi-domain Network Service Orchestration in 5G Networks
• The Computational Complexity of Training ReLU(s)
• Standardized Non-Intrusive Reduced Order Modeling Using Different Regression Models With Application to Complex Flow Problems
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
• An Approximation Algorithm for training One-Node ReLU Neural Network
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Interpreting and Disentangling Feature Components of Various Complexity from DNNs
• Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time