Author Archives: Sebastien Bubeck

New journal: Mathematical Statistics and Learning

I am thrilled to announce the launch of a new journal, “Mathematical Statistics and Learning”, to be edited be the European Mathematical Society. The goal of the journal is be the natural home for the top works addressing the mathematical … Continue reading

Posted in Announcement | 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

Posted in Conference/workshop, Theoretical Computer Science | 2 Comments

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 | 2 Comments

Geometry of linearized neural networks

This week we had the pleasure to host Tengyu Ma from Princeton University who told us about the recent progress he has made with co-authors to understand various linearized versions of neural networks. I will describe here two such results, … Continue reading

Posted in Optimization | 1 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

Prospective graduate student? Consider University of Washington!

This post is targeted at prospective graduate students, especially foreigners from outside the US, who are primarily interested in optimization but also have a taste for probability theory (basically readers of this blog!). As a foreigner myself I remember that … Continue reading

Posted in Uncategorized | 3 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: The fundamental limits of dimension estimation in random geometric graphs

This post is a continuation of the previous one, where we explored how to detect geometry in a random geometric graph. We now consider the other side of the coin: when is it impossible to detect geometry and what are … Continue reading

Posted in Uncategorized | 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