Fetching the paper…
Reading the bibliography…
We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent.
Asymptotic coefficients of hermite function series
John P Boyd · 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.
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 distribution-free learning of probabilistic concepts
Michael J Kearns and Robert E Schapire · 1994
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 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.
Cryptographic hardness for learning intersections of halfspaces
Adam R Klivans and Alexander A Sherstov · 2009
Earlier work this paper cites.
Characterizing statistical query learning: simplified notions and proofs
Balázs Szörényi · 2009
Earlier work this paper cites.
A complete characterization of statistical query learning with applications to evolvability
Vitaly Feldman · 2012
Earlier work this paper cites.
Learning sparse polynomial functions
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang · 2014
Earlier work this paper cites.
Embedding hard learning problems into gaussian space
Adam R. Klivans and Pravesh Kothari · 2014
Earlier work this paper cites.
On the computational efficiency of training neural networks
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir · 2014
Cited alongside, same era.
Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar · 2015
Cited alongside, same era.
Globally optimal gradient descent for a convnet with gaussian inputs
Alon Brutzkus and Amir Globerson · 2017
Cited alongside, same era.
A general characterization of the statistical query complexity
Vitaly Feldman · 2017
Cited alongside, same era.
Statistical algorithms and a lower bound for detecting planted cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao · 2017
Cited alongside, same era.
Learning one-hidden-layer neural networks with landscape design
Rong Ge, Jason D. Lee, and Tengyu Ma · 2018
Later among the works it cites.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Clément Hongler, and Franck Gabriel · 2018
Later among the works it cites.
Distribution-specific hardness of learning neural networks
Ohad Shamir · 2018
Later among the works it cites.
Attribute-efficient learning of monomials over highly-correlated variables
Alexandr Andoni, Rishabh Dudeja, Daniel Hsu, and Kiran Vodrahalli · 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.
Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Reliably learning the relu in polynomial time
Surbhi Goel, Varun Kanade, Adam R. Klivans, and Justin Thaler · 2017
Cited alongside, same era.
Failures of gradient-based deep learning
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah · 2017
Cited alongside, same era.
On the complexity of learning neural networks
Le Song, Santosh Vempala, John Wilmes, and Bo Xie · 2017
Cited alongside, same era.
Electron-proton dynamics in deep learning
Qiuyi Zhang, Rina Panigrahy, and Sushant Sachdeva · 2017
Cited alongside, same era.
Recovery guarantees for one-hidden-layer neural networks
Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon · 2017
Cited alongside, same era.
Santosh Vempala and John Wilmes · 2019
Later among the works it cites.
Learning one-hidden-layer relu networks via gradient descent
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu · 2019
Later among the works it cites.
Poly-time universality and limitations of deep learning
Emmanuel Abbe and Colin Sandon · 2020
Closest in time.
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, and Nikos Zarifis · 2020
Closest in time.
Hardness of learning neural networks with natural weights
Amit Daniely and Gal Vardi · 2020
Closest in time.