Competitive analysis via convex optimization

Spring, 2018

WF 3-4:20pm, CSE 303

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

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]