Fetching the paper…
Reading the bibliography…
We study the power of learning via mini-batch stochastic gradient descent (SGD) on the population loss, and batch Gradient Descent (GD) on the empirical loss, of a differentiable model or neural network, and ask what learning problems can be learnt using these paradigms.
Linearized two-layers neural networks in high dimension
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari · 1904
Earlier work this paper cites.
Training a 3-node neural network is np-complete
A. Blum and R. L. Rivest · 1992
Earlier work this paper cites.
Cryptographic limitations on learning boolean formulae and finite automata
M. Kearns and L. Valiant · 1994
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
M. Kearns · 1998
Earlier work this paper cites.
Backward feature correction: How deep learning performs deep learning
Z. Allen-Zhu and Y. Li · 2001
Earlier work this paper cites.
On learning correlated boolean functions using statistical queries
K. Yang · 2001
Earlier work this paper cites.
Noise-tolerant learning, the parity problem, and the statistical query model
A. Blum, A. Kalai, and H. Wasserman · 2003
Earlier work this paper cites.
New lower bounds for statistical query learning
K. Yang · 2004
Earlier work this paper cites.
Computational Complexity: A Modern Approach
S. Arora and B. Barak · 2009
Cited alongside, same era.
Cryptographic hardness for learning intersections of halfspaces
A. R. Klivans and A. A. Sherstov · 2009
Cited alongside, same era.
In search of the real inductive bias: On the role of implicit regularization in deep learning
B. Neyshabur, R. Tomioka, and N. Srebro · 2015
Cited alongside, same era.
The implicit bias of gradient descent on separable data
D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro · 2018
Cited alongside, same era.
What can resnet learn efficiently, going beyond kernels?
Z. Allen-Zhu and Y. Li · 2019
Cited alongside, same era.
Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate
On the universality of deep learning
E. Abbe and C. Sandon · 2020
Later among the works it cites.
Learning parities with neural networks
A. Daniely and E. Malach · 2020
Later among the works it cites.
When do neural networks outperform kernel methods?
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari · 2020
Later among the works it cites.
Learning over-parametrized two-layer neural networks beyond NTK
Y. Li, T. Ma, and H. R. Zhang · 2020
Later among the works it cites.
Computational separation between convolutional and fully-connected networks
E. Malach and S. Shalev-Shwartz · 2020
Later among the works it cites.
The staircase property: How hierarchical structure can guide deep learning
E. Abbe, E. Boix-Adserà, M. S. Brennan, G. Bresler, and D. M. Nagaraj · 2021
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
M. S. Nacson, N. Srebro, and D. Soudry · 2019
Cited alongside, same era.
On the power and limitations of random features for understanding neural networks
G. Yehudai and O. Shamir · 2019
Cited alongside, same era.
Closest in time.
Quantifying the benefit of using differentiable learning over tangent kernels
E. Malach, P. Kamath, E. Abbe, and N. Srebro · 2021
Closest in time.