Transformers can learn compositional function
summary
Two concrete results: a shallow single-index teacher-plus-student model shows sharp d^{k-1} plateau emergence times (Hermite coefficients control tiny initial gradients), and summing many power-law-weighted neurons a_p ∝ p^{−β} recovers the observed scaling laws only if SGD uses a decaying step size (continuous-time rates must be square-rooted to match classical minimax exponents). Separately, transformers can express k-fold function composition in O(log k) depth but are SQ-hard (sample n^k); using a curriculum of 1/2/4/... hops or mixed-data training makes gradient descent learnable in polynomial (empirically near-linear) samples.
AI-written summary · about
chapters (10)
- 0:00Introduction to scaling laws
- 1:00Mechanisms of emergence
- 7:15Toy model for emergence
- 12:10Scaling in two-layer networks
- 20:04Refining scaling law theory
- 28:16Proof sketches and conclusions
- 38:06Introduction to compositional reasoning
- 44:05Transformer expressivity
- 51:31Curriculum learning for composition
- 57:26Concluding remarks
related talks
01h 33mOn large language models and transformers: perspectives from physics, neuroscience, and theory
38mHow Transformers Learn Causal Structure with Gradient Descent
01h 16mHow Do Transformers Work?
46mLearning Theory of Transformers: Generalization and Optimization of In-Context Learning
01h 10mIntroduction to Transformers
40mAn Occam's Razor Principle for Transformers?
34mTransformers End to End Experience training...
38mTalk by Pranjal Awasthi (Google)