Theory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives
summary
Claims a formal framework for learning verifiers for chain-of-thought reasoning with provable guarantees, using PAC and online learning tools, VC bounds (VC · log L) and a new SC‑Littlestone dimension that characterizes optimal online mistake bounds given a budget of k soundness errors. Presents an optimal greedy look‑ahead algorithm and shows a practical win: sequential verification needs L/α calls instead of 1/α^L worst‑case for best‑of‑N, proven but not yet turned into large‑scale deployed systems.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:24Modern AI learning objects
- 3:53Motivation for verifier learning
- 7:50Formalizing verifier learning
- 15:15PAC learning verifier training
- 21:57OOD inference challenges
- 24:25Online learning verifiers
- 29:02SC-Littlestone dimension
- 31:30Verifiers improve generators
- 34:34Future directions in verifier learning
- 36:00Verifiers as multi-agent systems
- 36:41Learning intractable algorithms
- 38:06Data-driven algorithm design
- 40:33Conclusion & Q&A
related talks
46mInteractive Proofs for Verifying Machine Learning
31mMaking the most of test-time compute in LLMs
07mProbabilistic Reasoning and Learning for Trustworthy AI
34mFrom Vibe Coding to Vericoding
12mTheoretical understanding of learning through the computational lens
42mReasonable AI
01h 02mOut-of-Distribution Generalization as Reasoning: Are LLMs Competitive?
23mReturn of the Theorem