Category Archives: Theoretical Computer Science
Convex body chasing, Steiner point, Sellke point, and SODA 2020 best papers
Big congratulations to my former intern Mark Sellke, and to the CMU team (C. J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang) for jointly winning the best paper award at SODA 2020 (as well as the best student paper … Continue reading
Posted in Theoretical Computer Science
31 Comments
Optimal bound for stochastic bandits with corruption
Guest post by Mark Sellke. In the comments of the previous blog post we asked if the new viewpoint on best of both worlds can be used to get clean “interpolation” results. The context is as follows: in a STOC … Continue reading
Amazing progress in adversarially robust stochastic multi-armed bandits
In this post I briefly discuss some recent stunning progress on robust bandits (for more background on bandits see these two posts, part 1 and part 2, in particular what is described below gives a solution to Open Problem 3 … Continue reading
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
13 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
1 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
4 Comments
Discrepancy algorithm inspired by gradient descent and multiplicative weights; after Levy, Ramadas and Rothvoss
A week or so ago at our Theory Lunch we had the pleasure to listen to Harishchandra Ramadas (student of Thomas Rothvoss) who told us about their latest discrepancy algorithm. I think the algorithm is quite interesting as it combines … Continue reading
Posted in Theoretical Computer Science
1 Comment
STOC 2017 accepted papers
The list of accepted papers to STOC 2017 has just been released. Following the trend in recent years there are quite a few learning theory papers! I have already blogged about the kernel-based convex bandit algorithm; as well as the … Continue reading
Kernel-based methods for convex bandits, part 3
(This post absolutely requires to have read Part 1 and Part 2.) A key assumption at the end of Part 1 was that, after rescaling space so that the current exponential weights distribution is isotropic, one has (1) for … Continue reading
Kernel-based methods for convex bandits, part 2
The goal of this second lecture is to explain how to do the variance calculation we talked about at the end of Part 1 for the case where the exponential weights distribution is non-Gaussian. We will lose here a factor … Continue reading
