On the Complexity of Learning Neural Networks

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.

Training a 3-node neural network is NP-complete

Avrim Blum and Ronald L. Rivest · 1992

Earlier work this paper cites.

Universal approximation bounds for superpositions of a sigmoidal function

Andrew R Barron · 1993

Earlier work this paper cites.

Efficient noise-tolerant learning from statistical queries

Michael J. Kearns · 1993

Earlier work this paper cites.

Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich · 1994

Earlier work this paper cites.

Efficient noise-tolerant learning from statistical queries

Michael Kearns · 1998

Earlier work this paper cites.

Characterizing statistical query learning:simplified notions and proofs

B. Szörényi · 2009

Cited alongside, same era.

Statistical algorithms and a lower bound for planted clique

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao · 2013

Cited alongside, same era.

Learning polynomials with neural networks

Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang · 2014

Cited alongside, same era.

Generalization bounds for neural networks through tensor factorization

Original

Majid Janzamin, Hanie Sedghi, and Anima Anandkumar · 2015

Cited alongside, same era.

Complexity theoretic limitations on learning dnf’s

Amit Daniely and Shai Shalev-Shwartz · 2016

Cited alongside, same era.

The power of depth for feedforward neural networks

Ronen Eldan and Ohad Shamir · 2016

Reliably learning the ReLU in polynomial time

Original

Surbhi Goel, Varun Kanade, Adam R. Klivans, and Justin Thaler · 2016

Later among the works it cites.

Cryptographic hardness of learning

Adam R. Klivans · 2016

Later among the works it cites.

Distribution-specific hardness of learning neural networks

Original

Ohad Shamir · 2016

Later among the works it cites.

Benefits of depth in neural networks

Original

Matus Telgarsky · 2016

Later among the works it cites.

Globally optimal gradient descent for a convnet with gaussian inputs

Original

Alon Brutzkus and Amir Globerson · 2017

Closest in time.