# Competitive analysis via convex optimization

#### Instructors: Sébastien Bubeck and James R. Lee

Office hours: By appointment

## Lectures

 date topic Wed, Mar 28 James Online algorithms and bandits Regret minimization vs. competitive analysis Exponential weights Lecture notes Fri, Mar 30 Seb Stability in bandit problems Mirror descent in continuous time Bregman divergence as a Lyapunov function Lecture notes Wed, Apr 04 Seb MTS on weighted stars Lecture notes Fri, Apr 06 Seb The $k$-server problem Unweighted paging An $O(\log k)$-competitive algorithm for weighted paging Wed, Apr 11 Seb An $O(\log n)$-competitive algorithm for MTS on HSTs Fri, Apr 13 James Random ultrametric embeddings Metric Ramsey theorem Lecture notes Wed, Apr 18 James Lower bounds for MTS on ultrametrics Lecture notes Fri, Apr 20 NO CLASS Wed, Apr 25 Seb $k$-server on HSTs, Part I $k$-server via multiscale entropic regularization Fri, Apr 27 Seb $k$-server on HSTs, Part II Wed, May 02 James Online rounding for k-server Fri, May 04 James Dynamic HST embeddings Wed, May 09 James $\mathrm{poly}(\log k)$-competitive algorithm for $k$-server on the line, Part I Fri, May 11 James $\mathrm{poly}(\log k)$-competitive algorithm for $k$-server on the line, Part II Wed, May 16 Seb LECTURE MOVED (to 23-May) Fri, May 18 Seb Online learning with bandit feedback Wed, May 23 Seb Special time: 3-6pm (room TBA) Bandit convex optimization Part I: One-point gradient estimate Part II: Kernels Kernel-based methods for bandit convex optimization Multi-scale exploration of convex functions and bandit convex optimization Fri, May 25 Seb Chasing convex bodies Wed, May 30 James NO CLASS [Final project on self-organizing data structures] PROJECT DUE: Friday, June 8th (by email to jrl@cs) Assignment: A one page+ (can be longer) report on self-organizing data structures and the the possible application of mirror descent for competitive analysis. I would like you to read the following survey and write your thoughts on issues that might arise, and/or ideas you have to overcome them. You may consult any other papers you like (please include references if you do). You can discuss your ideas with anyone in the class (or outside the class, for that matter). But please write the short report yourself. Fri, Jun 01 James NO CLASS [Final project on self-organizing data structures]