Fetching the paper…
Reading the bibliography…
A supervised learning algorithm has access to a distribution of labeled examples, and needs to return a function (hypothesis) that correctly labels the examples.
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.
Toward efficient agnostic learning
Michael J Kearns, Robert E Schapire, and Linda M Sellie · 1994
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Limitations of learning via embeddings in euclidean half spaces
Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon · 2002
Earlier work this paper cites.
On using extended statistical queries to avoid membership queries
Nader H Bshouty and Vitaly Feldman · 2002
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.
Learning dnf in time 2o (n1/3)
Adam R Klivans and Rocco A Servedio · 2004
Earlier work this paper cites.
On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
Jürgen Forster and Hans Ulrich Simon · 2006
Earlier work this paper cites.
Evolvability from learning algorithms
Vitaly Feldman · 2008
Earlier work this paper cites.
Halfspace matrices
Alexander A Sherstov · 2008
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.
Distribution-independent evolvability of linear threshold functions
Vitaly Feldman · 2011
Earlier work this paper cites.
A complete characterization of statistical query learning with applications to evolvability
Vitaly Feldman · 2012
Cited alongside, same era.
On the representational efficiency of restricted boltzmann machines
James Martens, Arkadev Chattopadhya, Toni Pitassi, and Richard Zemel · 2013
Cited alongside, same era.
On the number of response regions of deep feed forward networks with piece-wise linear activations
Razvan Pascanu, Guido Montufar, and Yoshua Bengio · 2013
Cited alongside, same era.
Representation benefits of deep feedforward networks
Matus Telgarsky · 2015
Cited alongside, same era.
On the expressive power of deep learning: A tensor analysis
Nadav Cohen, Or Sharir, and Amnon Shashua · 2016
Cited alongside, same era.
Spurious local minima are common in two-layer relu neural networks
Itay Safran and Ohad Shamir · 2018
Later among the works it cites.
Bounding and counting linear regions of deep neural networks
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam · 2018
Later among the works it cites.
Distribution-specific hardness of learning neural networks
Ohad Shamir · 2018
Later among the works it cites.
What can resnet learn efficiently, going beyond kernels?
Zeyuan Allen-Zhu and Yuanzhi Li · 2019
Later among the works it cites.
Complexity of linear regions in deep networks
Boris Hanin and David Rolnick · 2019
Later among the works it cites.
Is deeper better only when shallow is good?
Eran Malach and Shai Shalev-Shwartz · 2019
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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
Cited alongside, same era.
Benefits of depth in neural networks
Matus Telgarsky · 2016
Cited alongside, same era.
Depth separation for neural networks
Amit Daniely · 2017
Cited alongside, same era.
Notes on the number of linear regions of deep neural networks
Guido Montúfar · 2017
Cited alongside, same era.
On the expressive power of deep neural networks
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein · 2017
Cited alongside, same era.
Failures of gradient-based deep learning
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah · 2017
Cited alongside, same era.
Later among the works it cites.
On the power and limitations of random features for understanding neural networks
Gilad Yehudai and Ohad Shamir · 2019
Later among the works it cites.
Backward feature correction: How deep learning performs deep learning
Zeyuan Allen-Zhu and Yuanzhi Li · 2020
Closest in time.
Learning parities with neural networks
Amit Daniely and Eran Malach · 2020
Closest in time.
Superpolynomial lower bounds for learning one-layer neural networks using gradient descent
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans · 2020
Closest in time.
Approximate is good enough: Probabilistic variants of dimensional and margin complexity
Pritish Kamath, Omar Montasser, and Nathan Srebro · 2020
Closest in time.
Neural networks with small weights and depth-separation barriers
Gal Vardi and Ohad Shamir · 2020
Closest in time.