Fetching the paper…
Reading the bibliography…
We investigate the time complexity of SGD learning on fully-connected neural networks with isotropic data.
Rishabh Dudeja and Daniel Hsu, Learning single-index models in gaussian space , Conference On Learning Theory, PMLR, 2018, pp. 1887–1930
1930
Earlier work this paper cites.
Avrim Blum and Ronald Rivest, Training a 3-node neural network is np-complete , Advances in neural information processing systems 1
1988
Earlier work this paper cites.
Oded Goldreich and Leonid A. Levin, A hard-core predicate for all one-way functions , Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA (David S. Johnson, ed.), ACM, 1989, pp. 25–32
1989
Earlier work this paper cites.
Eyal Kushilevitz and Yishay Mansour, Learning decision trees using the fourier spectrum , SIAM Journal on Computing 22
1993
Earlier work this paper cites.
Yishay Mansour, Learning boolean functions via the fourier transform , pp. 391–424, Springer US, Boston, MA, 1994
1994
Earlier work this paper cites.
Shai Ben-David, Alon Itai, and Eyal Kushilevitz, Learning by distances , Information and Computation 117
1995
Earlier work this paper cites.
Michael Kearns, Efficient noise-tolerant learning from statistical queries , Journal of the ACM (JACM) 45
1998
Earlier work this paper cites.
Nader H Bshouty and Vitaly Feldman, On using extended statistical queries to avoid membership queries , Journal of Machine Learning Research 2
2002
Earlier work this paper cites.
Adam R Klivans, Ryan O’Donnell, and Rocco A Servedio, Learning intersections and thresholds of halfspaces , Journal of Computer and System Sciences 68
2004
Earlier work this paper cites.
Tong Zhang, Solving large scale linear prediction problems using stochastic gradient descent algorithms , Proceedings of the twenty-first international conference on Machine learning, 2004, p. 116
2004
Earlier work this paper cites.
Adam R Klivans and Alexander A Sherstov, Cryptographic hardness for learning intersections of halfspaces , Journal of Computer and System Sciences 75
2009
Earlier work this paper cites.
Santosh S Vempala, A random-sampling-based algorithm for learning intersections of halfspaces , Journal of the ACM (JACM) 57
2010
Earlier work this paper cites.
2011
Earlier work this paper cites.
Emmanuel J Candes, Thomas Strohmer, and Vladislav Voroninski, Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming , Communications on Pure and Applied Mathematics 66
2013
Earlier work this paper cites.
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz, From average case complexity to improper learning complexity , Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014, pp. 441–448
2014
Earlier work this paper cites.
Ryan O’Donnell, Analysis of boolean functions , Cambridge University Press, 2014
2014
Earlier work this paper cites.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points—online stochastic gradient for tensor decomposition , Conference on learning theory, PMLR, 2015, pp. 797–842
2015
Earlier work this paper cites.
Michael Kohler and Adam Krzyżak, Nonparametric regression based on hierarchical interaction models , IEEE Transactions on Information Theory 63
2016
Earlier work this paper cites.
Francis Bach, Breaking the curse of dimensionality with convex neural networks , The Journal of Machine Learning Research 18
2017
Earlier work this paper cites.
2017
Earlier work this paper cites.
Lénaïc Chizat and Francis Bach, On the global convergence of gradient descent for over-parameterized models using optimal transport , Advances in Neural Information Processing Systems 31
2018
Cited alongside, same era.
Arthur Jacot, Franck Gabriel, and Clément Hongler, Neural tangent kernel: Convergence and generalization in neural networks , Advances in neural information processing systems 31
2018
Cited alongside, same era.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen, A mean field view of the landscape of two-layer neural networks , Proceedings of the National Academy of Sciences 115
2018
Cited alongside, same era.
Zeyuan Allen-Zhu and Yuanzhi Li, What can resnet learn efficiently, going beyond kernels? , Advances in Neural Information Processing Systems 32
2019
Cited alongside, same era.
Anselm Johannes Schmidt-Hieber, Nonparametric regression using deep neural networks with relu activation function , Annals of statistics 48
2020
Later among the works it cites.
Emmanuel Abbe, Enric Boix-Adsera, Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj, The staircase property: How hierarchical structure can guide deep learning , Advances in Neural Information Processing Systems 34
2021
Later among the works it cites.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath, Online stochastic gradient descent on non-convex losses from high-dimensional inference. , J. Mach. Learn. Res. 22
2021
Later among the works it cites.
Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro, On the power of differentiable learning versus pac and sq learning , Advances in Neural Information Processing Systems 34
2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2019
Cited alongside, same era.
Anindya De, Elchanan Mossel, and Joe Neeman, Is your function low dimensional? , Conference on Learning Theory, PMLR, 2019, pp. 979–993
2019
Cited alongside, same era.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari, Limitations of lazy training of two-layers neural network , Advances in Neural Information Processing Systems 32
2019
Cited alongside, same era.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari, Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit , Conference on Learning Theory, PMLR, 2019, pp. 2388–2464
2019
Cited alongside, same era.
2019
Cited alongside, same era.
2019
Cited alongside, same era.
Emmanuel Abbe and Colin Sandon, On the universality of deep learning , Advances in Neural Information Processing Systems 33
2020
Cited alongside, same era.
Lenaic Chizat and Francis Bach, Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss , Conference on Learning Theory, PMLR, 2020, pp. 1305–1338
2020
Cited alongside, same era.
2021
Later among the works it cites.
2021
Later among the works it cites.
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová, Classifying high-dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed , International Conference on Machine Learning, PMLR, 2021, pp. 8936–8947
2021
Later among the works it cites.
2021
Later among the works it cites.
2022
Later among the works it cites.
2022
Later among the works it cites.
Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz, The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks , Conference on Learning Theory, PMLR, 2022, pp. 4782–4887
2022
Later among the works it cites.
Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, and Christopher Marquis, An initial alignment between neural network and target is needed for gradient descent to learn , Proceedings of the 39th International Conference on Machine Learning (Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, eds.), Proceedings of Machine Learning Research, vol. 162, PMLR, 17–23 Jul 2022, pp. 33–52
2022
Later among the works it cites.
2022
Later among the works it cites.
2022
Later among the works it cites.
2022
Later among the works it cites.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi, Neural networks can learn representations with gradient descent , Conference on Learning Theory, PMLR, 2022, pp. 5413–5452
2022
Later among the works it cites.
2022
Later among the works it cites.
2022
Later among the works it cites.
Itay Safran and Jason Lee, Optimization-based separations for neural networks , Conference on Learning Theory, PMLR, 2022, pp. 3–64
2022
Later among the works it cites.
2022
Later among the works it cites.