Category Archives: Probability theory
Guest post by Miklos Racz: Confidence sets for the root in uniform and preferential attachment trees
In the final post of this series (see here for the previous posts) we consider yet another point of view for understanding networks. In the previous posts we studied random graph models with community structure and also models with an … Continue reading
Posted in Probability theory, Random graphs
Leave a comment
Local max-cut in smoothed polynomial time
Omer Angel, Yuval Peres, Fan Wei, and myself have just posted to the arXiv our paper showing that local max-cut is in smoothed polynomial time. In this post I briefly explain what is the problem, and I give a short … Continue reading
Posted in Optimization, Probability theory
2 Comments
Guest post by Miklos Racz: Entropic central limit theorems and a proof of the fundamental limits of dimension estimation
In this post we give a proof of the fundamental limits of dimension estimation in random geometric graphs, based on the recent work of Bubeck and Ganguly. We refer the reader to the previous post for a detailed introduction; here … Continue reading
Posted in Probability theory, Random graphs
Leave a comment
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
6 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
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 Machine learning, Optimization, Probability theory
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
