Competitive Analysis of Online Algorithms (Part 2)

on YouTube ↗01h 04m

" summary

Defines competitive analysis and proves concrete bounds: ski‑rental gets 2 - 1/B deterministically and ~e/(e-1) randomized as B→∞; cat‑and‑mouse is n‑competitive deterministically and log n randomized. Shows metrical task systems unify caching and k‑server and gives algorithms with O(log N) guarantees and a refined bound 1+ε (hit) + (log N)/ε (movement), which converts to switching‑regret bounds (K log n / ε). Implements online covering via multiplicative weights/doubling with a primal–dual/KL‑projection analysis; algorithms are practical and match the stated ratios.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 19:14Regret Analysis
3. 24:29Unfair Mts
4. 44:17Recovery Problem
5. 48:19The Dual Constraint

" related talks

• 01h 00mContinuous Methods 4Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka, Reza Eghbali · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 44mParsimonious Learning-Augmented AlgorithmsRavi Kumar · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 44mSomething for Almost Nothing: Advances in Sub-Linear Time AlgorithmsRonitt Rubinfeld · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 33mOnline Multiserver Convex Chasing and OptimizationYuval Rabani · Mathematics of Online Decision Making 2020
• 58mMemory-Regret Tradeoff for Online LearningAviad Rubinstein, Binghui Peng · Sketching and Algorithm Design 2023
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)