Fetching the paper…
Reading the bibliography…
We prove several hardness results for training depth-2 neural networks with the ReLU activation function; these networks are simply weighted sums (that may include negative coefficients) of ReLUs.
Reducibility among combinatorial problems
Richard M. Karp · 1972
Earlier work this paper cites.
Coverings and colorings of hypergraphs
Laszlo Lovasz · 1973
Earlier work this paper cites.
Planar 3-colorability is polynomial complete
Larry Stockmeyer · 1973
Earlier work this paper cites.
On the complexity of loading shallow neural networks
Stephen Judd · 1988
Earlier work this paper cites.
On the complexity of polyhedral separability
Nimrod Megiddo · 1988
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.
Approximation by superpositions of a sigmoidal function
George Cybenko · 1989
Earlier work this paper cites.
Multilayer feedforward networks are universal approximators
Kurt Hornik, Maxwell Stinchcombe, and Halbert White · 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.
On the hardness of approximating minimization problems
Carsten Lund and Mihalis Yannakakis · 1994
Earlier work this paper cites.
The hardness of approximation: Gap location
Erez Petrank · 1994
Earlier work this paper cites.
A threshold of ln n for approximating set cover
Uriel Feige · 1998
Earlier work this paper cites.
On the infeasibility of training neural networks with small mean-squared error
Van H Vu · 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
Earlier work this paper cites.
Rademacher and gaussian complexities: Risk bounds and structural results
Peter L. Bartlett and Shahar Mendelson · 2002
Earlier work this paper cites.
On the hardness of approximating label-cover
Irit Dinur and Shmuel Safra · 2004
Earlier work this paper cites.
The hardness of 3-uniform hypergraph coloring
Irit Dinur, Oded Regev, and Clifford D. Smyth · 2005
Cited alongside, same era.
On basing lower-bounds for learning on worst-case assumptions
Benny Applebaum, Boaz Barak, and David Xiao · 2008
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.
Linear level lasserre lower bounds for certain k-CSPs
Grant Schoenebeck · 2008
Cited alongside, same era.
CSP gaps and reductions in the lasserre hierarchy
Madhur Tulsiani · 2009
Cited alongside, same era.
Smoothness, low noise and fast rates
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari · 2010
Cited alongside, same era.
Approximation algorithms for label cover and the log-density threshold
Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, and Aravindan Vijayaraghavan · 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.
Almost-polynomial ratio ETH-hardness of approximating densest k k -subgraph
Pasin Manurangsi · 2017
Later among the works it cites.
A birthday repetition theorem and complexity of approximating dense csps
Pasin Manurangsi and Prasad Raghavendra · 2017
Later among the works it cites.
What circuit classes can be learned with non-trivial savings?
Rocco A Servedio and Li-Yang Tan · 2017
Later among the works it cites.
On the complexity of learning neural networks
Le Song, Santosh Vempala, John Wilmes, and Bo Xie · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Inapproximabilty of densest k k -subgraph from average case hardness
Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein · 2011
Cited alongside, same era.
Polynomial integrality gaps for strong SDP relaxations of densest k k -subgraph
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, and Yuan Zhou · 2012
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.
How to refute a random CSP
Sarah R. Allen, Ryan O’Donnell, and David Witmer · 2015
Cited alongside, same era.
Convex optimization: Algorithms and complexity
Sébastien Bubeck et al · 2015
Cited alongside, same era.
Polynomially low error PCPs with polyloglog n queries via modular composition
Irit Dinur, Prahladh Harsha, and Guy Kindler · 2015
Cited alongside, same era.
Later among the works it cites.
Understanding deep neural networks with rectified linear units
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee · 2018
Later among the works it cites.
Complexity of training relu neural network
Digvijay Boob, Santanu S Dey, and Guanghui Lan · 2018
Later among the works it cites.
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
Amey Bhangale · 2018
Later among the works it cites.
Gradient descent finds global minima of deep neural networks
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai · 2018
Later among the works it cites.
An approximation algorithm for training one-node relu neural network
Santanu S Dey, Guanyi Wang, and Yao Xie · 2018
Later among the works it cites.
The computational complexity of training relu(s)
Pasin Manurangsi and Daniel Reichman · 2018
Later among the works it cites.
Learning and generalization in overparameterized neural networks, going beyond two layers
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang · 2019
Later among the works it cites.
Learning two layer rectified neural networks in polynomial time
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff · 2019
Later among the works it cites.
Nearly tight bounds for robust proper learning of halfspaces with a margin
Ilias Diakonikolas, Daniel Kane, and Pasin Manurangsi · 2019
Later among the works it cites.
Nearly tight bounds for robust proper learning of halfspaces with a margin
Ilias Diakonikolas, Daniel M. Kane, and Pasin Manurangsi · 2019
Later among the works it cites.
Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals
Surbhi Goel, Sushrut Karmalkar, and Adam Klivans · 2019
Later among the works it cites.
Refined complexity of PCA with outliers
Kirill Simonov, Fedor Fomin, Petr Golovach, and Fahad Panolan · 2019
Later among the works it cites.
Polynomial convergence of gradient descent for training one-hidden-layer neural networks
Santosh Vempala and John Wilmes · 2019
Later among the works it cites.
Beyond the worst-case analysis of algorithms, 2020
Tim Roughgarden · 2020
Closest in time.