Fetching the paper…
Reading the bibliography…
While on some natural distributions, neural-networks are trained efficiently using gradient-based algorithms, it is known that learning them is computationally hard in the worst-case.
Samet Oymak and Mahdi Soltanolkotabi · 1902
Earlier work this paper cites.
On the learnability of boolean formulae
Michael Kearns, Ming Li, Leonard Pitt, and Leslie Valiant · 1987
Earlier work this paper cites.
Constant depth circuits, fourier transform, and learnability
Nathan Linial, Yishay Mansour, and Noam Nisan · 1989
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Relations between communication complexity, linear arrangements, and computational complexity
Jürgen Forster, Matthias Krause, Satyanarayana V Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon · 2001
Earlier work this paper cites.
Noise-tolerant learning, the parity problem, and the statistical query model
Avrim Blum, Adam Kalai, and Hal Wasserman · 2003
Earlier work this paper cites.
New results for learning noisy parities and halfspaces
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami · 2006
Earlier work this paper cites.
On agnostic learning of parities, monomials, and halfspaces
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami · 2009
Earlier work this paper cites.
Probabilistic graphical models: principles and techniques
Daphne Koller and Nir Friedman · 2009
Earlier work this paper cites.
The sign-rank of ac ˆ0
Alexander A Razborov and Alexander A Sherstov · 2010
Earlier work this paper cites.
Shallow vs. deep sum-product networks
Olivier Delalleau and Yoshua Bengio · 2011
Earlier work this paper cites.
On the number of response regions of deep feed forward networks with piece-wise linear activations
Razvan Pascanu, Guido Montufar, and Yoshua Bengio · 2013
Earlier work this paper cites.
Provable bounds for learning some deep representations
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma · 2014
Earlier work this paper cites.
On the computational efficiency of training neural networks
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir · 2014
Earlier work this paper cites.
On the number of linear regions of deep neural networks
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio · 2014
Earlier work this paper cites.
Representation benefits of deep feedforward networks
Matus Telgarsky · 2015
Earlier work this paper cites.
On the expressive power of deep learning: A tensor analysis
Nadav Cohen, Or Sharir, and Amnon Shashua · 2016
Earlier work this paper cites.
The power of depth for feedforward neural networks
Ronen Eldan and Ohad Shamir · 2016
Cited alongside, same era.
Deep vs. shallow networks: An approximation theory perspective
Hrushikesh N Mhaskar and Tomaso Poggio · 2016
Cited alongside, same era.
Exponential expressivity in deep neural networks through transient chaos
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli · 2016
Cited alongside, same era.
On the expressive power of deep neural networks
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein · 2016
Cited alongside, same era.
Depth-width tradeoffs in approximating natural functions with neural networks
Itay Safran and Ohad Shamir · 2016
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Later among the works it cites.
Boolean functions: Influence, threshold and noise
Gil Kalai · 2018
Later among the works it cites.
A provably correct algorithm for deep learning that actually works
Eran Malach and Shai Shalev-Shwartz · 2018
Later among the works it cites.
Overparameterized nonlinear learning: Gradient descent takes the shortest path?
Samet Oymak and Mahdi Soltanolkotabi · 2018
Later among the works it cites.
Distribution-specific hardness of learning neural networks
Ohad Shamir · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Matus Telgarsky · 2016
Cited alongside, same era.
Diverse neural network learns true target functions
Bo Xie, Yingyu Liang, and Le Song · 2016
Cited alongside, same era.
Globally optimal gradient descent for a convnet with gaussian inputs
Alon Brutzkus and Amir Globerson · 2017
Cited alongside, same era.
Sgd learns over-parameterized networks that provably generalize on linearly separable data
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz · 2017
Cited alongside, same era.
Statistical query algorithms for mean vector estimation and stochastic convex optimization
Vitaly Feldman, Cristóbal Guzmán, and Santosh Vempala · 2017
Cited alongside, same era.
Notes on the number of linear regions of deep neural networks
Guido Montúfar · 2017
Cited alongside, same era.
Why and when can deep-but not shallow-networks avoid the curse of dimensionality: a review
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao · 2017
Cited alongside, same era.
Zeyuan Allen-Zhu and Yuanzhi Li · 2019
Closest in time.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang · 2019
Closest in time.
Decoupled greedy learning of cnns
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon · 2019
Closest in time.
Why do larger models generalize better? a theoretical perspective via the xor problem
Alon Brutzkus and Amir Globerson · 2019
Closest in time.
Id3 learns juntas for smoothed product distributions
Alon Brutzkus, Amit Daniely, and Eran Malach · 2019
Closest in time.
On the learnability of deep random networks
Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, and Rina Panigrahy · 2019
Closest in time.
On functions computed on trees
Roozbeh Farhoodi, Khashayar Filom, Ilenna Simone Jones, and Konrad Paul Kording · 2019
Closest in time.
Wide neural networks of any depth evolve as linear models under gradient descent
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington · 2019
Closest in time.
Chao Ma, Lei Wu, et al · 2019
Closest in time.
Is deeper better only when shallow is good?
Eran Malach and Shai Shalev-Shwartz · 2019
Closest in time.
On the power and limitations of random features for understanding neural networks
Gilad Yehudai and Ohad Shamir · 2019
Closest in time.