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

Ray Li rayyli at
Mon Dec 11 10:18:55 PST 2017

Hi All,

I plan to watch the TCS+ talk this Wednesday in Gates 463A. Let me know if you are interested. If there's enough interest I will sign up for a hangouts slot, otherwise I'll plan to show it non-interactively.



From: theory-seminar <theory-seminar-bounces at> on behalf of Clément Canonne <ccanonne at>
Sent: Saturday, December 9, 2017 2:51:06 PM
To: theory-seminar at
Subject: [theory-seminar] (No organized) Next TCS+ talk (but FYI, there is one you can watch): Wednesday, December 13, Sebastien Bubeck, MSR

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 .
Next TCS+ talk - Google Sites<>
An online seminar series in theoretical computer science


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

theory-seminar mailing list
theory-seminar at
theory-seminar Info Page - Stanford University<>
For scheduling meetings/lunches/lectures/talks for the CS Theory group. To see the collection of prior postings to the list, visit the theory-seminar Archives.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list