Complexity of Training ReLU Neural Network
  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.
