Fetching the paper…
Reading the bibliography…
We present and study approximate notions of dimensional and margin complexity, which correspond to the minimal dimension or norm of an embedding required to approximate, rather then exactly represent, a given hypothesis class.
What can resnet learn efficiently, going beyond kernels?
Zeyuan Allen-Zhu and Yuanzhi Li · 1905
Earlier work this paper cites.
Über die Abgrenzung der Eigenwerte einer Matrix
Semyon Aronovich Geršgorin · 1931
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
Summing and Nuclear Norms in Banach Space Theory
G. J. O. Jameson · 1987
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using fourier analysis
Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
Sphere packing numbers for subsets of the boolean n n -cube with bounded vapnik-chervonenkis dimension
David Haussler · 1995
Earlier work this paper cites.
An algorithmic theory of learning: Robust concepts and random projection
Rosa I. Arriaga and Santosh S. Vempala · 1999
Earlier work this paper cites.
Backward feature correction: How deep learning performs deep learning
Zeyuan Allen-Zhu and Yuanzhi Li · 2001
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.
Estimating the optimal margins of embeddings in euclidean half spaces
Jürgen Forster, Niels Schmitt, Hans Ulrich Simon, and Thorsten Suttorp · 2003
Cited alongside, same era.
Generalization error bounds for collaborative prediction with low-rank matrices
Nathan Srebro, Noga Alon, and Tommi S. Jaakkola · 2004
Cited alongside, same era.
On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
Jürgen Forster and Hans Ulrich Simon · 2005
Cited alongside, same era.
Rank, trace-norm and max-norm
Nathan Srebro and Adi Shraibman · 2005
Cited alongside, same era.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2007
Cited alongside, same era.
A theory of learning with similarity functions
Maria-Florina Balcan, Avrim Blum, and Nathan Srebro · 2008
The approximate rank of a matrix and its algorithmic applications: approximate rank
Noga Alon, Troy Lee, Adi Shraibman, and Santosh S. Vempala · 2013
Later among the works it cites.
Understanding Machine Learning: From Theory to Algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Later among the works it cites.
Sign rank versus VC dimension
Noga Alon, Shay Moran, and Amir Yehudayoff · 2016
Later among the works it cites.
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
Daniel M. Kane and Ryan Williams · 2016
Later among the works it cites.
Probabilistic rank and matrix rigidity
Josh Alman and R. Ryan Williams · 2017
Later among the works it cites.
SGD learns the conjugate kernel class of the network
Amit Daniely · 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…
Cited alongside, same era.
Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning
Ali Rahimi and Benjamin Recht · 2008
Cited alongside, same era.
Halfspace matrices
Alexander A. Sherstov · 2008
Cited alongside, same era.
The sign-rank of 𝖠𝖢 0 \mathsf{AC}^{0}
Alexander A Razborov and Alexander A Sherstov · 2010
Cited alongside, same era.
A Short List of Equalities Induces Large Sign Rank
Arkadev Chattopadhyay and Nikhil S. Mande · 2018
Later among the works it cites.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Clément Hongler, and Franck Gabriel · 2018
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.