Size (OOD) Generalization of Neural Models via Algorithmic Alignment
summary
Claims a provable path to size generalization: combining algorithmic alignment with L0 sparsity and a carefully curated small training set yields provable approximation of Bellman‑Ford on arbitrary graphs — one‑step Bellman‑Ford requires fitting just eight tiny graphs and achieving training loss ≤ ε to force a (near) correct implementation. Practical pipeline uses an encoder‑processor‑decoder with a relaxed epsilon kernel approximator implemented by a SumFormer, trained on ~200‑point sets and tested up to 3k–5k points; SumFormer runs linear time vs transformer quadratic and shows up to ~20× speedups on harder annulus problems.
AI-written summary · about
chapters (7)
- 0:00Algorithmic neural models intro
- 3:44Size generalization
- 7:21Theory for algorithm alignment
- 22:39Geometric optimization models
- 36:00Improving OOD generalization
- 45:56Summary of OOD challenges
- 51:02Q&A
related talks
01h 20mThe elusive generalization: classical bounds to double descent to grokking
58mStrong Generalization from Small Brains and No Training Data
33mProvably Efficient Algorithms for Training Deep Networks
35mSize-free Generalization Bounds for Convolutional Neural Networks
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
01h 04mRandomized Embeddings and Neural Networks
41mSub-Linear Algorithms meets Large Language Models
20mFeature Learning: From Optimization to Modern Generalization