Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] (No organized) Next TCS+ talk (but FYI, there is one you can watch): Wednesday, December 13, Sebastien Bubeck, MSR

Clément Canonne ccanonne at
Sat Dec 9 14:51:06 PST 2017

Hi everyone,

Although I won't be here to organize a common viewing for this talk, 
there /is/ a TCS+ talk happening next Wednesday. (See details below.)

If someone wants to try to set up a viewing at Stanford, I can brief 
them on that (it's quite simple -- ask for a slot on an online form, 
wait to have confirmation -- pretty much). Otherwise, if you are 
intererested you can watch it non-interactively with a 2mn-lag on 
Youtube, from .


-- Clément


Speaker: Sebastien Bubeck (MSR)
Title:  k-server via multiscale entropic regularization

Abstract: I will start by describing how mirror descent is a natural
strategy for online decision making, specifically in online learning and
metrical task systems. To motivate the k-server problem I will also
briefly recall what we know and what we don't know for structured
state/action spaces in these models. Using the basic mirror descent
calculations I will show how to easily obtain a log(k)-competitive
algorithm for k-paging. I will then introduce our new parametrization of
fractional k-server on a tree, and explain how to analyze the movement
cost of entropy-regularized mirror descent on this parametrization. This
leads to a depth*log(k)-competitive (fractional) algorithm for general
trees, and log^2(k) for HSTs. I will also briefly mention dynamic
embeddings to go beyond the standard log(n) loss in the reduction from
general metrics to HSTs.

Joint work with Michael B. Cohen, James R. Lee, Yin Tat Lee, and
Aleksander Madry.

More information about the theory-seminar mailing list