Category Archives: Probability theory

Guest post by Miklos Racz: Estimating the dimension of a random geometric graph on a high-dimensional sphere

Following the previous post in which we studied community detection, in this post we study the fundamental limits of inferring geometric structure in networks. Many networks coming from physical considerations naturally have an underlying geometry, such as the network of … Continue reading

Posted in Probability theory, Random graphs | Leave a comment

Guest post by Miklos Racz: A primer on exact recovery in the general stochastic block model

Foreword: this will be a series of blog posts written by our Theory Group postdoc Miklos Racz. It is essentially the transcript of a mini-course that Miki gave at the University of Washington and at the XX Brazilian School of … Continue reading

Posted in Probability theory, Random graphs | Leave a comment

Bandit theory, part II

These are the lecture notes for the second part of my minicourse on bandit theory (see here for Part 1). The linear bandit problem, Auer [2002] We will mostly study the following far-reaching extension of the -armed bandit problem. Known … Continue reading

Posted in Optimization, Probability theory | 4 Comments

Bandit theory, part I

This week I’m giving two 90 minutes lectures on bandit theory at MLSS Cadiz. Despite my 2012 survey with Nicolo I thought it would be a good idea to post my lectures notes here. Indeed while much of the material … Continue reading

Posted in Optimization, Probability theory | 5 Comments

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

Posted in Optimization, Probability theory, Theoretical Computer Science | Leave a comment

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

Posted in Optimization, Probability theory, Theoretical Computer Science | 9 Comments

Some stuff I learned this week

This week I had the pleasure to spend 3 days at a wonderful workshop (disclaimer: I was part of the organization, with Ofer Dekel, Yuval Peres and James Lee, so I might be a bit biased). Below you will find … Continue reading

Posted in Conference/workshop, Probability theory | Leave a comment

Some pictures in geometric probability

As I discussed in a previous blog post, I have been recently interested in models of randomly growing networks. As a starting point I focused my attention on the preferential attachment rule and its variants, in part because its ubiquity … Continue reading

Posted in Probability theory, Random graphs | 2 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

Posted in Optimization, Probability theory, Theoretical Computer Science | 5 Comments

Probability in high dimension

The Barcelona events have just ended, and I’m happy to report that everything went very smoothly. In my opinion the quality of the works presented at COLT and at the Foundations of Learning Theory workshop were truly outstanding. I hope … Continue reading

Posted in Probability theory | Leave a comment