Parsimonious Learning-Augmented Algorithms
summary
New results show a sublinear number of predictions suffices for meaningful gains. For online linear optimization a randomized algorithm combines FTRL with a query chooser via 1D OGD and flips a coin to query; it gets O(√B·log P/α) regret when B hints are bad (B=0 gives logarithmic regret, B=T recovers √T), and querying <√T times can force √T regret. For caching a sample-B eviction scheme trades queries for competitiveness (≈log_{B}K) while using O(B·OPT) queries.
AI-written summary · about
chapters (19)
- 0:00Intro
- 1:02Online algorithms
- 1:50Handling the unknown
- 5:16Online performance metrics
- 7:33Problem space
- 9:53Desiderata
- 13:33Constrained OLO [Zinkevich 2003]
- 15:38FTL & FTRL
- 17:00Constrained OLO with hints
- 17:52When is a hint good?
- 20:04Sublinear regret bounds
- 24:01Main result
- 26:24Key idea: when FTRL fails
- 27:23Key idea: when FTRL works
- 29:33Proof outline
- 32:50Lower bounds
- 37:04Caching & hints
- 38:11Marking algorithms for caching
- 42:01Summary
related talks
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
58mMemory-Regret Tradeoff for Online Learning
30mOnline Paging with a Vanishing Regret
22mOnline Learning and Bandits with Queried Hints
43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
45mCharting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ...
49mFast Rates for No-Regret Learning in General Games
35mOnline Learning with A Lot of Batch Data