Fetching the paper…
Reading the bibliography…
We show that the standard stochastic gradient decent (SGD) algorithm is guaranteed to learn, in polynomial time, a function that is competitive with the best function in the conjugate kernel space of the network, as defined in Daniely, Frostig and Singer.
Training a 3-node neural net is NP-Complete
Avrim Blum and Ronald L. Rivest · 1989
Earlier work this paper cites.
Cryptographic hardness of distribution-specific learning
Michael Kharitonov · 1993
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using fourier analysis
A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
Cryptographic limitations on learning Boolean formulae and finite automata
M. Kearns and L.G. Valiant · 1994
Earlier work this paper cites.
Computation with infinite neural networks
C.K.I. Williams · 1997
Earlier work this paper cites.
On learning width two branching programs
Nader H Bshouty, Christino Tamon, and David K Wilson · 1998
Earlier work this paper cites.
Universal approximation using feedforward neural networks: A survey of some existing methods, and some new results
Franco Scarselli and Ah Chung Tsoi · 1998
Earlier work this paper cites.
Cryptographic hardness for learning intersections of halfspaces
A.R. Klivans and A.A. Sherstov · 2006
Earlier work this paper cites.
Unconditional lower bounds for learning intersections of halfspaces
A.R. Klivans and A.A. Sherstov · 2007
Earlier work this paper cites.
Random features for large-scale kernel machines
A. Rahimi and B. Recht · 2007
Earlier work this paper cites.
Kernel methods for deep learning
Y. Cho and L.K. Saul · 2009
Earlier work this paper cites.
Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning
A. Rahimi and B. Recht · 2009
Cited alongside, same era.
Understanding the difficulty of training deep feedforward neural networks
X. Glorot and Y. Bengio · 2010
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2010
Cited alongside, same era.
Random feature maps for dot product kernels
P. Kar and H. Karnick · 2012
Cited alongside, same era.
Bayesian learning for neural networks , volume 118
R.M. Neal · 2012
Cited alongside, same era.
Learning polynomials with neural networks
Understanding Machine Learning: From Theory to Algorithms
S. Shalev-Shwartz and S. Ben-David · 2014
Later among the works it cites.
Deep convolutional networks are hierarchical kernel machines
F. Anselmi, L. Rosasco, C. Tan, and T. Poggio · 2015
Later among the works it cites.
On the equivalence between kernel quadrature rules and random feature expansions
F. Bach · 2015
Later among the works it cites.
Steps toward deep kernel methods from infinite neural networks
T. Hazan and T. Jaakkola · 2015
Later among the works it cites.
Bounds on the expectation of the maximum of samples from a gaussian, 2015
Gautam C Kamath · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. Andoni, R. Panigrahy, G. Valiant, and L. Zhang · 2014
Cited alongside, same era.
Provable bounds for learning some deep representations
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma · 2014
Cited alongside, same era.
Breaking the curse of dimensionality with convex neural networks
F. Bach · 2014
Cited alongside, same era.
From average case complexity to improper learning complexity
A. Daniely, N. Linial, and S. Shalev-Shwartz · 2014
Cited alongside, same era.
On the computational efficiency of training neural networks
R. Livni, S. Shalev-Shwartz, and O. Shamir · 2014
Cited alongside, same era.
Convolutional kernel networks
J. Mairal, P. Koniusz, Z. Harchaoui, and Cordelia Schmid · 2014
Cited alongside, same era.
l1-regularized neural networks are improperly learnable in polynomial time
Yuchen Zhang, Jason D Lee, and Michael I Jordan
Cited in the paper.
J. Pennington, F. Yu, and S. Kumar · 2015
Later among the works it cites.
Learning halfspaces and neural networks with random initialization
Yuchen Zhang, Jason D Lee, Martin J Wainwright, and Michael I Jordan · 2015
Later among the works it cites.
Provable learning of noisy-or networks
Sanjeev Arora, Rong Ge, Tengyu Ma, and Andrej Risteski · 2016
Later among the works it cites.
Complexity theoretic limitations on learning DNFs
A. Daniely and S. Shalev-Shwartz · 2016
Later among the works it cites.
Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity
Amit Daniely, Roy Frostig, and Yoram Singer · 2016
Later among the works it cites.
Random features for compositional kernels
Amit Daniely, Roy Frostig, Vineet Gupta, and Yoram Singer · 2017
Closest in time.