Beyond Worst-Case Analysis (Lecture 20: From Unknown Input Distributions to Instance Optimality)

From unknown input distributions to restricted instance optimality. Case study: regret bounds for online decision-making. Full course playlist: https://www.youtube.com/playlist?list=PLEGCF-WLh2RL8jsZpaf2tLHa5LotFEt5b Book: https://www.amazon.com/dp/1108494315 Lecture notes: http://timroughgarden.org/f14/l/l20.pdf Top 10 list: http://timroughgarden.org/f14/l/top10.pdf