Category Archives: Theoretical Computer Science
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
Kernel-based methods for bandit convex optimization, part 1
A month ago Ronen Eldan, Yin Tat Lee and myself posted our latest work on bandit convex optimization. I’m quite happy with the result (first polynomial time method with poly(dimension)-regret) but I’m even more excited by the techniques we developed. Next … Continue reading
Crash course on learning theory, part 2
It might be useful to refresh your memory on the concepts we saw in part 1 (particularly the notions of VC dimension and Rademacher complexity). In this second and last part we will discuss two of the most successful algorithm paradigms in … Continue reading
Crash course on learning theory, part 1
This week and next week I’m giving 90 minutes lectures at MSR on the fundamentals of learning theory. Below you will find my notes for the first course, where we covered the basic setting of statistical learning theory, Glivenko-Cantelli classes, Rademacher complexity, VC … Continue reading
Guest post by Sasho Nikolov: Beating Monte Carlo
If you work long enough in any mathematical science, at some point you will need to estimate an integral that does not have a simple closed form. Maybe your function is really complicated. Maybe it’s really high dimensional. Often you … Continue reading
Posted in Theoretical Computer Science
8 Comments
Komlos conjecture, Gaussian correlation conjecture, and a bit of machine learning
Today I would like to talk (somewhat indirectly) about a beautiful COLT 2014 paper by Nick Harvey and Samira Samadi. The problem studied in this paper goes as follows: imagine that you have a bunch of data points in with a certain … Continue reading
A zest of number theory
I just encountered an amazing number theoretic result. It is probably very well known, but for those who never saw it it’s quite something, so I thought I would share it. Let be a positive integer. A partition of is … Continue reading
Posted in Theoretical Computer Science
Leave a comment
First week of activity at the Simons Institute
This first week at the Simons Institute was a lot of fun! I attended the first workshop in the Real Analysis program which was about Testing, Learning and Inapproximability. There was plenty of good talks and I learned a lot of … Continue reading
Posted in Theoretical Computer Science
4 Comments
Random-Approx 2013
Last week I attended the Random-Approx conference at Berkeley. I missed quite a few talks as I was also settling in my new office for the semester at the Simons Institute so I will just report on the three invited talks: Luca Trevisan gave a … Continue reading
Posted in Random graphs, Theoretical Computer Science
2 Comments
