Interpolating Between Stochastic and Worst-case Optimization

on YouTube ↗34m

" summary

Proposes a hybrid input model that interpolates between stochastic and adversarial arrivals via a lever epsilon that flips each request with probability epsilon, recovers static optimal order at epsilon=0 and adversarial worst case at epsilon=1, and defines a simple algorithm move-from-back parameterized by epsilon which promotes items only if predecessors remain likely after perturbation. Experiments on Zipf, uniform and crafted adversaries show empirical ratios never worse than the baseline algorithms, and theoretical bounds interpolate between the expected-case and 2‑competitive worst‑case guarantees.

AI-written summary · about

" chapters (20)

1. 0:00Start
2. 0:48Risk-calculable gamble
3. 2:06Handling input uncertainty: Worst-case competitive analysis
4. 2:27Common complaints
5. 5:09Outline
6. 5:27Relax Pessimism
7. 7:14Temper optimism: Stochastic Programming Variants
8. 9:47Temper Optimism: Correlation Robustness
9. 10:18Have it all
10. 14:56Best of both: Online Resource Allocation
11. 17:04Best of both: Balanced guarantees for bandits
12. 21:10Proposal: Interpolate Models AND Performance
13. 22:25List Update Problem
14. 22:54List Update Example
15. 23:21Average Case Analysis
16. 24:39Competitive Ratio
17. 25:08Performance Comparison
18. 27:49New Hybrid Interpolating Model
19. 30:26Desiderata: Interpolating Algorithm for Hybrid Model
20. 33:09Conjecture