Learning Staircases
summary
Claim: certain nested “staircase” Boolean functions with growing degree are not kernel learnable (NTK/random features require ~D^K samples/features) but are learnable by gradient-trained, permutation-invariant sparse nets via a mean-field dimension-free PDE that reduces to P-dimensional dynamics. Tools: SGD one-pass mean-field limit, PDE simulation, layer-wise/neuron-wise training and kernel-ridge certificates. Experiments show dense nets fail on high-degree monomials but succeed on staircases; caveat: sample/time constants can grow very rapidly with sparsity, even double-exponentially in P.
AI-written summary · about
chapters (10)
- 0:00Start
- 8:13The Vanilla Staircase
- 9:00Learn a Staircase of Degree 10
- 18:21The Valence Staircase
- 22:23Learning Sparse Functions on the Hypercube
- 25:48Min Field Normalization
- 34:13Dimension Free Dynamics
- 37:33Sgd Learnability in Od Scaling
- 50:19Source Theorem
- 57:04Non-Degenerate Condition
related talks
56mHow neural networks learns simple functions?
33mThe Power and Limitations of Kernel Learning
29mCompositional sparsity and learnability
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
46mOn the Foundations of Deep Learning: SGD, Overparametrization, and Generalization
01h 02mTutorial: Statistical Learning Theory and Neural Networks II
01h 06mAnalytic Methods for Supervised Learning III
59mWhen do dependencies in your data help?