Complexity of Training ReLU Neural Network
This addresses fundamental theoretical challenges in deep learning for researchers, providing rigorous complexity bounds that are incremental but clarify when efficient training is possible.
The paper tackles the computational complexity of training ReLU neural networks, proving that training a two-hidden layer network is NP-hard in general, but becomes polynomial-time solvable with fixed input dimension and topology or with sufficient over-parameterization in the first hidden layer.
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.