Author Archives: Sebastien Bubeck

Some updates

The blog has been eerily silent for most of 2018, here is why: The main culprit is definitely the COLT 2018 chairing. This year we received a surprise 50% increase in number of submissions. This is great news for the … Continue reading

Posted in Announcement | 3 Comments

Youtube channel

I just started a youtube channel. The hope is that this will be a companion to the blog. Some of the posts will “graduate” into videos (e.g., the first set of videos will correspond to an expanded version of bandit … Continue reading

Posted in Announcement | 4 Comments

k-server, part 3: entropy regularization for weighted k-paging

If you have been following the first two posts (post 1, post 2), now is time to reap the rewards! I will show here how to obtain a -competitive algorithm for (weighted) paging, i.e., when the metric space corresponds to … Continue reading

Posted in Theoretical Computer Science | 4 Comments

k-server, part 2: continuous time mirror descent

We continue our -server series (see post 1 here). In this post we briefly discuss the concept of a fractional solution for -server, which by analogy with MTS will in fact be a fractional “anti-solution”. Then we introduce the continuous … Continue reading

Posted in Theoretical Computer Science | Leave a comment

k-server, part 1: online learning and online algorithms

The -server problem is a classical and very attractive instance of online decision making. The decisions to be made in this problem are simple: given a requested location in some finite metric space and a fleet of k servers currently sitting … Continue reading

Posted in Theoretical Computer Science | 1 Comment

Algorithms, Machine Learning, and Optimization: we are hiring!

As some of you already know there has been some movement at MSR lately, specifically for the theory group. We have now branched out into two groups, one in Machine Learning and Optimization -MLO- (with Zeyuan Allen-Zhu, myself, Ofer Dekel, … Continue reading

Posted in Announcement | Leave a comment

COLT 2018 call for papers

Philippe Rigollet and myself will be the program chairs for this year’s edition of COLT. It will be in Stockholm in July, which I hear is absolutely gorgeous at that time of the year. We also have a fantastic lineup … Continue reading

Posted in Conference/workshop | Leave a comment

Michael B. Cohen

This is an incredibly difficult post to write. Michael Benjamin Cohen, an amazing student and person passed away this week in Berkeley. Below is the official MSR statement (where he spent the summer together with many friends) and some personal … Continue reading

Posted in Uncategorized | 7 Comments

Smooth distributed convex optimization

A couple of months ago we (Kevin Scaman, Francis Bach, Yin Tat Lee, Laurent Massoulie and myself) uploaded a new paper on distributed convex optimization. We came up with a pretty clean picture for the optimal oracle complexity of this … Continue reading

Posted in Optimization | Leave a comment

COLT 2017 accepted papers

The list of accepted papers at COLT 2017 has been published and it looks particularly good (see below with links to arxiv version)! The growth trend of previous years continues with 228 submissions (14% increase from 2016) and 73 accepted … Continue reading

Posted in Conference/workshop | 1 Comment