Compositional sparsity and learnability
summary
Claim: functions that are compositionally sparse—built from small-arity constituent maps (example: a binary tree of 2-variable nodes)—avoid the curse of dimensionality so deep nets approximate them without exponential parameters; every function computable in polynomial time is shown to admit such a decomposition (efficiently Turing computable ⇒ compositional sparsity). Training autoregressively (next-token prediction) often recovers the constituent pieces (autoregressive next-token predictor), sparsity shows up in learned weight matrices, and exploiting it tightens generalization bounds by orders of magnitude; the remaining bottleneck is optimization: finding the right sparse decomposition from only input–output data.
AI-written summary · about
chapters (6)
- 0:00AI revolution foundations
- 5:16Deep networks avoid curse
- 12:16Compositional sparsity property
- 18:14Optimization challenges
- 22:30Theory behind LLMs' success
- 24:27Q&A
related talks
01h 04mLearning Staircases
01h 07mTheory of Computation II
36mCompositional distributional semantics for modelling natural language
40mSparse models are fast models: Improving DNN inference performance by over 10X
33mProvably Efficient Algorithms for Training Deep Networks
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
01h 04mNeural Networks meet Nonparametric Regression: Generalization by Weight Decay and Large...
01h 40mBoot camp on generalization theory for graph learning