Fetching the paper…
Reading the bibliography…
We establish connections between the problem of learning a two-layer neural network and tensor decomposition.
Richard A. Harshman, Foundations of the parafac procedure: models and conditions for an “explanatory” multimodal factor analysis , UCLA Working Papers in Phonetics (1970), no. 16, 1–84
1970
Earlier work this paper cites.
Avrim Blum and Ronald L. Rivest, Training a 3-node neural network is NP-complete , Advances in Neural Information Processing Systems (NIPS), 1989, pp. 494–501
1989
Earlier work this paper cites.
Johan Håstad, Tensor rank is NP-complete , Journal of Algorithms 11
1990
Earlier work this paper cites.
Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle, Blind source separation by simultaneous third-order tensor diagonalization , Proc. of European Signal Processing Conference (EUSIPCO), 1996, pp. 1–4
1996
Earlier work this paper cites.
Peter Bartlett and Shai Ben-David, Hardness results for neural network approximation problems , Proc. of Computational Learning Theory (COLT), 1999, pp. 50–62
1999
Earlier work this paper cites.
Christian Kuhlmann, Hardness results for general two-layer neural networks. , Proc. of Computational Learning Theory (COLT), 2000, pp. 275–285
2000
Earlier work this paper cites.
Olivier Bousquet and André Elisseeff, Stability and generalization , Journal of Machine Learning Research 2
2002
Earlier work this paper cites.
Jiří Šíma, Training a single sigmoidal neuron is hard , Neural Computation 14
2002
Earlier work this paper cites.
Jack W. Silverstein and Zhidong Bai, Spectral Analysis of Large Dimensional Random Matrices ( 2 n d 2^{nd} edition) , Springer, 2010
2010
Earlier work this paper cites.
2010
Earlier work this paper cites.
Christopher J. Hillar and Lek-Heng Lim, Most tensor problems are NP-hard , Journal of the ACM (JACM) 60
2013
Earlier work this paper cites.
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma, Provable bounds for learning some deep representations , Proc. of International Conference on Machine Learning (ICML), 2014, pp. 584–592
2014
Earlier work this paper cites.
2014
Earlier work this paper cites.
Ryan O’Donnell, Analysis of boolean functions , Cambridge University Press, 2014
2014
Cited alongside, same era.
Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms , Cambridge university press, 2014
2014
Cited alongside, same era.
Animashree Anandkumar, Rong Ge, and Majid Janzamin, Learning overcomplete latent variable models through tensor methods , Proc. of Conference on Learning Theory (COLT), vol. 40, 2015, pp. 36–112
2015
Cited alongside, same era.
Boaz Barak, Jonathan A. Kelner, and David Steurer, Dictionary learning and tensor decomposition via the sum-of-squares method , Proc. of Annual ACM Symposium on Theory of Computing (STOC), 2015, pp. 143–151
2015
Cited alongside, same era.
Rong Ge and Tengyu Ma, Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms , Proc. of APPROX-RANDOM, 2015, pp. 829–849
Tengyu Ma, Jonathan Shi, and David Steurer, Polynomial-time tensor decompositions with sum-of-squares , Proc. of IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2016, pp. 438–446
2016
Later among the works it cites.
2016
Later among the works it cites.
Itay Safran and Ohad Shamir, On the quality of the initial basin in overspecified neural networks , Proc. of International Conference on Machine Learning (ICML), 2016, pp. 774–782
2016
Later among the works it cites.
2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2015
Cited alongside, same era.
Samuel B. Hopkins, Jonathan Shi, and David Steurer, Tensor principal component analysis via sum-of-square proofs , Proc. of Conference on Learning Theory (COLT), 2015, pp. 956–1006
2015
Cited alongside, same era.
2015
Cited alongside, same era.
Hanie Sedghi and Anima Anandkumar, Provable methods for training neural networks with sparse connectivity , Proc. of International Conference on Learning Representation (ICLR), 2015
2015
Cited alongside, same era.
2015
Cited alongside, same era.
Boaz Barak, Samuel B Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin, A nearly tight sum-of-squares lower bound for the planted clique problem , Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, IEEE, 2016, pp. 428–437
2016
Cited alongside, same era.
Amit Daniely, Complexity theoretic limitations on learning halfspaces , Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, ACM, 2016, pp. 105–117
2016
Cited alongside, same era.
2016
Cited alongside, same era.
2017
Later among the works it cites.
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer, The power of sum-of-squares for detecting hidden structures , Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, IEEE, 2017, pp. 720–731
2017
Later among the works it cites.
2017
Later among the works it cites.
Yuandong Tian, Symmetry-breaking convergence analysis of certain two-layered neural networks with ReLU nonlinearity , Workshop at International Conference on Learning Representation (ICLR), 2017
2017
Later among the works it cites.
2017
Later among the works it cites.
Rina Panigrahy, Ali Rahimi, Sushant Sachdeva, and Qiuyi Zhang, Convergence results for neural networks via electrodynamics , LIPIcs-Leibniz International Proceedings in Informatics, vol. 94, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018
2018
Closest in time.
Ohad Shamir, Distribution-specific hardness of learning neural networks , Journal of Machine Learning Research 19
2018
Closest in time.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee, Theoretical insights into the optimization landscape of over-parameterized shallow neural networks , IEEE Transactions on Information Theory (2018)
2018
Closest in time.