Theoretical understanding of learning through the computational lens
summary
Proves that worst-case continual learning requires memory scales linearly with number of tasks but shows allowing multiple passes over the task stream removes that memory overhead; shows some online decision problems can run in polylog space while certain iteration‑optimal optimization needs quasi‑linear memory. Gives an exponential speedup in swap‑regret minimization achieving near‑optimal computation/communication/iteration tradeoffs, and derives the first polynomial‑time algorithm for approximate correlated equilibria in games with exponentially large action spaces (Bayesian/extensive‑form).
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:02Computational learning theory
- 2:07Memory complexity in continual learning
- 3:10Computation limits in dynamic learning
- 4:14Learning agents and equilibrium
- 7:23Decentralized learning for equilibrium
- 8:28Faster learning algorithms for equilibrium
- 9:29Future research goals
related talks
45mCharting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ...
39mComputational Thinking on Learning Models
01h 07mTheory of Computation II
58mMemory-Regret Tradeoff for Online Learning
44mParsimonious Learning-Augmented Algorithms
01h 06mLearning in Games II
49mFast Rates for No-Regret Learning in General Games
41mTheory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives