Double Coverage with Machine-Learned Advice
summary
Defines Lambda-DC, an online k-server algorithm that interpolates between Double Coverage and Follow-the-Prediction by moving the predicted-side server at speed 1 and the other at speed lambda in [0,1]. Proves for k=2 it is 1+lambda consistent and 1+1/lambda robust, generalizes to explicit k-dependent consistency (sum of lambda powers) and robustness (geometric sum of 1/lambda powers), and gives an error-dependent bound CR ≤ consistency·(1+relative prediction error). Implements proofs via potential functions, shows near-optimality among memoryless local algorithms, and validates improvements on real traces.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:28The K-server problem on the line
- 5:12Learning-augmented online algorithms
- 8:31Prediction model
- 13:30Results for - 2
- 15:56Roadmap
- 17:07Potential function analysis (consistency for k-2)
- 22:41Potential function analysis (robustness for - 2)
- 23:46Results for general case
- 25:16Conclusion
related talks
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
13mDistribution-Free, Risk-Controlling Prediction Sets
25mConfidence-Based Active Learning
01h 11mA Theory of Multi-objective Machine Learning
01h 04mCompetitive Analysis of Online Algorithms (Part 2)
38mMulti-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere!
33mOnline Multiserver Convex Chasing and Optimization
33mDistributed Learning, Communication Complexity, and Privacy