Search Mailing List Archives
[theory-seminar] (No organized) Next TCS+ talk (but FYI, there is one you can watch): Wednesday, December 13, Sebastien Bubeck, MSR
rayyli at stanford.edu
Wed Dec 13 09:41:04 PST 2017
Just a reminder this will be happening at 10am (in 20 minutes) in Gates 463A.
From: Ray Li
Sent: Monday, December 11, 2017 10:18:55 AM
To: Clement Louis Arthur Canonne; theory-seminar at lists.stanford.edu
Subject: Re: [theory-seminar] (No organized) Next TCS+ talk (but FYI, there is one you can watch): Wednesday, December 13, Sebastien Bubeck, MSR
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 lists.stanford.edu> on behalf of Clément Canonne <ccanonne at stanford.edu>
Sent: Saturday, December 9, 2017 2:51:06 PM
To: theory-seminar at lists.stanford.edu
Subject: [theory-seminar] (No organized) Next TCS+ talk (but FYI, there is one you can watch): Wednesday, December 13, Sebastien Bubeck, MSR
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 https://sites.google.com/site/plustcs/livetalk .
Next TCS+ talk - Google Sites<https://sites.google.com/site/plustcs/livetalk>
An online seminar series in theoretical computer science
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
theory-seminar mailing list
theory-seminar at lists.stanford.edu
theory-seminar Info Page - Stanford University<https://mailman.stanford.edu/mailman/listinfo/theory-seminar>
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...
More information about the theory-seminar