Fetching the paper…
Reading the bibliography…
We consider the computational complexity of training depth-2 neural networks composed of rectified linear units (ReLUs).
Leslie G. Valiant · 1984
Earlier work this paper cites.
Training a 3-node neural network is NP-complete
Avrim Blum and Ronald L Rivest · 1989
Earlier work this paper cites.
Probability in Banach Spaces: isoperimetry and processes
Michel Ledoux and Michel Talagrand · 1991
Earlier work this paper cites.
Decision theoretic generalizations of the PAC model for neural net and other learning applications
David Haussler · 1992
Earlier work this paper cites.
Toward efficient agnostic learning
Michael J. Kearns, Robert E. Schapire, and Linda Sellie · 1994
Earlier work this paper cites.
A threshold of ln n for approximating set cover
Uriel Feige · 1998
Earlier work this paper cites.
Minimum propositional proof length is NP-hard to linearly approximate
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, and Toniann Pitassi · 2001
Earlier work this paper cites.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
Which problems have strongly exponential complexity?
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane · 2001
Cited alongside, same era.
Rademacher and gaussian complexities: Risk bounds and structural results
Peter L. Bartlett and Shahar Mendelson · 2002
Cited alongside, same era.
On the hardness of approximating label-cover
Irit Dinur and Shmuel Safra · 2004
Cited alongside, same era.
On the complexity of linear prediction: Risk bounds, margin bounds, and regularization
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari · 2008
Cited alongside, same era.
Reliable agnostic learning
Adam Tauman Kalai, Varun Kanade, and Yishay Mansour · 2012
Cited alongside, same era.
Imagenet classification with deep convolutional neural networks
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton · 2012
Cited alongside, same era.
Convex optimization: Algorithms and complexity
Sébastien Bubeck et al · 2015
Later among the works it cites.
Polynomially low error PCPs with polyloglog n queries via modular composition
Irit Dinur, Prahladh Harsha, and Guy Kindler · 2015
Later among the works it cites.
Expressiveness of rectifier networks
Xingyuan Pan and Vivek Srikumar · 2016
Later among the works it cites.
Breaking the curse of dimensionality with convex neural networks
Francis Bach · 2017
Later among the works it cites.
Globally optimal gradient descent for a convnet with gaussian inputs
Alon Brutzkus and Amir Globerson · 2017
Later among the works it cites.
Reliably learning the relu in polynomial time
Surbhi Goel, Varun Kanade, Adam R. Klivans, and Justin Thaler · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Rectifier nonlinearities improve neural network acoustic models
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng · 2013
Cited alongside, same era.
On the computational efficiency of training neural networks
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir · 2014
Cited alongside, same era.
Understanding deep neural networks with rectified linear units
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee · 2018
Closest in time.
Complexity of training relu neural network
Digvijay Boob, Santanu S. Dey, and Guanghui Lan · 2018
Closest in time.