2018

Complexity of Training ReLU Neural Network

Boob, Digvijay, Dey, Santanu S., Lan, Guanghui

Understand

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.

H. Edelsbrunner, J. O’Rouke, R. Seidel, Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput. 15 (2) (1986) 341–363
1986
Earlier work this paper cites.
A. Blum, R. L. Rivest, Training a 3-node neural network is np-complete, in: Proceedings of the First Annual Workshop on Computational Learning Theory, COLT ’88, 1988, pp. 9–18
1988
Earlier work this paper cites.
N. Megiddo, On the complexity of polyhedral separability., Discrete and Computational Geometry 3 (4) (1988) 325–338
1988
Earlier work this paper cites.
B. DasGupta, H. T. Siegelmann, E. Sontag, On a learnability question associated to neural networks with continuous activations, in: Proceedings of the Seventh Annual Conference on Computational Learning Theory, COLT ’94, 1994, pp. 47–56
1994
Earlier work this paper cites.
S. Hochreiter, Y. Bengio, P. Frasconi, J. Schmidhuber, Gradient flow in recurrent nets: the difficulty of learning long-term dependencies (2001)
2001
Earlier work this paper cites.
G. E. Hinton, S. Osindero, Y.-W. Teh, A fast learning algorithm for deep belief nets, Neural Computation 18 (7) (2006) 1527–1554
2006
Earlier work this paper cites.

R. Collobert, J. Weston, A unified architecture for natural language processing: Deep neural networks with multitask learning, in: Proceedings of the 25th International Conference on Machine Learning, ICML ’08, 2008, pp. 160–167
2008
Cited alongside, same era.
A. R. Klivans, A. A. Sherstov, Cryptographic hardness for learning intersections of halfspaces, J. Comput. Syst. Sci. 75 (1) (2009) 2–12
2009
Cited alongside, same era.
A. Mohamed, G. E. Dahl, G. Hinton, Acoustic modeling using deep belief networks, Trans. Audio, Speech and Lang. Proc. (2012) 14–22
2012
Cited alongside, same era.
A. Krizhevsky, I. Sutskever, G. E. Hinton, Imagenet classification with deep convolutional neural networks, in: Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 1, NIPS’12, 2012, pp. 1097–1105
2012
Cited alongside, same era.
S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014
2014
Cited alongside, same era.
R. Livni, S. Shalev-Shwartz, O. Shamir, On the computational efficiency of training neural networks, in: Advances in Neural Information Processing Systems 27, 2014, pp. 855–863
2014
Cited alongside, same era.

C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding deep learning requires rethinking generalization, CoRR (2016)
2016
Later among the works it cites.
O. Shamir, Distribution-specific hardness of learning neural networks, CoRR (2016)
2016
Later among the works it cites.
R. Arora, A. Basu, P. Mianjy, A. Mukherjee, Understanding deep neural networks with rectified linear units, 2016
2016
Later among the works it cites.
L. Song, S. Vempala, J. Wilmes, B. Xie, On the complexity of learning neural networks, CoRR (2017)
2017
Later among the works it cites.
arXiv:1810.04207
Original
P. Manurangsi, D. Reichman, The computational complexity of training relu(s) , CoRR abs/1810.04207 (2018) · 2018
Closest in time.
arXiv:1810.03592
Original
S. S. Dey, G. Wang, Y. Xie, An approximation algorithm for training one-node relu neural network (2018) · 2018
Closest in time.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…