The Power of Predictions in Online Optimization
summary
Predictive noise is modeled as a filter-like noise model (impulse weights times IID shocks), letting adversarial instances coexist with stochastic prediction error. Analysis shows a simple algorithm—averaging fixed horizon control—achieves constant competitive ratio and sublinear regret with a constant lookahead under that noise model; tuning a committed horizon parameter V trades switching cost versus prediction error, and IID errors favor large V while long-range correlation favors small V. Variants power deployed data‑center and camera/planning systems.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:52How do you use predictions
- 2:54Algorithms that use predictions
- 4:50Online convex optimization
- 8:30How to use predictions
- 9:13Regret vs Competitive Ratio
- 12:38Gradient Descent
- 14:51Predictions
- 18:12Algorithm
- 19:16What do we get
- 20:36Fixed horizon control
- 26:15Prediction noise
- 29:44Analysis
- 32:34Committed Horizon Control