Oracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning

on YouTube ↗49m

" summary

Claim: efficient no-regret online learning is possible by reusing a standard ERM oracle rather than redesigning algorithms from scratch, provided the adversary is sigma-smoothed. Construction uses hallucinated future samples, coupling the adaptive adversary to a uniform world (rejection sampling), nets and Rademacher-type bounds; regret scales with VC/Littlestone-style dimension and roughly with 1/sigma (equivalently needing about T/sigma samples), and the algorithm only calls oracle once per round.

AI-written summary · about

" chapters (12)

1. 0:00Introduction to the topic
2. 1:47Batch vs sequential models
3. 4:43Adversarial manipulations
4. 6:43Online learning paradigms
5. 9:30Oracle-efficient learning
6. 13:16Philosophical motivations
7. 15:20Oracle interaction mechanics
8. 18:30Approaches to oracle use
9. 24:19Worst-case vs beyond
10. 28:17Smooth analysis and gaps
11. 32:40The role of hallucination
12. 38:11Conclusion and robustness

" related talks

• 31mLearning in Games with Best-Response OraclesTomer Koren · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 58mMemory-Regret Tradeoff for Online LearningAviad Rubinstein, Binghui Peng · Sketching and Algorithm Design 2023
• 55mLearning Minimax Estimators Via Online LearningPradeep Ravikumar · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 35mOnline Learning with A Lot of Batch DataShie Mannor · Reinforcement Learning from Batch Data and Simulation
• 01h 17mOnline Reinforcement Learning and RegretSean Sinclair, Christina Lee Yu · Data-Driven Decision Processes Boot Camp 2022
• 41mEfficient Algorithms for Outlier-Robust RegressionAdam R. Klivans · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)