Competitive analysis via convex optimization

• Online algorithms and bandits
• Regret minimization vs. competitive analysis
• Exponential weights

Lecture notes

• Stability in bandit problems
• Mirror descent in continuous time
• Bregman divergence as a Lyapunov function

Lecture notes

MTS on weighted stars

Lecture notes

• The $k$-server problem
• Unweighted paging
• An $O(\log k)$-competitive algorithm for weighted paging

An $O(\log n)$-competitive algorithm for MTS on HSTs

• Random ultrametric embeddings
• Metric Ramsey theorem

Lecture notes

Lower bounds for MTS on ultrametrics

Lecture notes

$k$-server on HSTs, Part I

$k$-server via multiscale entropic regularization

$k$-server on HSTs, Part II

Online rounding for k-server

Dynamic HST embeddings

$\mathrm{poly}(\log k)$-competitive algorithm for $k$-server on the line, Part I

$\mathrm{poly}(\log k)$-competitive algorithm for $k$-server on the line, Part II

LECTURE MOVED (to 23-May)

Online learning with bandit feedback

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

Chasing convex bodies

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).

• In pursuit of the dynamic optimality conjecture

You can discuss your ideas with anyone in the class (or outside the class, for that matter). But please write the short report yourself.

NO CLASS

[Final project on self-organizing data structures]