Memory-Regret Tradeoff for Online Learning
summary
Shows two concrete tradeoffs and gives matching algorithms and lower bounds: against an oblivious adversary an algorithm using S bits achieves about sqrt(nT/S) regret matching prior lower bounds up to polylog factors, while against an adaptive adversary roughly sqrt(n) memory is necessary and sufficient to get o(T) regret. Algorithms partition time into epochs of size 1/ε^2, run multiplicative weights on carefully sampled subsets and a keep-longer subroutine; the adaptive lower bound reduces to multi‑set disjointness via direct product theorems.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:23Online Learning Problem
- 2:10Expert Selection Framework
- 5:22Memory Constraints
- 10:11Literature Review
- 12:55New Results Summary
- 15:46Adaptive Algorithm
- 25:36Adaptive Lower Bound
- 41:08Oblivious Algorithm
- 54:53Conclusion and Q&A
related talks
44mParsimonious Learning-Augmented Algorithms
48mA Simple Condition for Constant Regret in Online Decision-Making
49mFast Rates for No-Regret Learning in General Games
49mOracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning
30mOnline Paging with a Vanishing Regret
01h 17mOnline Reinforcement Learning and Regret
41mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors