Thomas Bonis

Thomas Bonis

We study the problem of sampling from a distribution $\target$ using the Langevin Monte Carlo algorithm and provide rate of convergences for this algorithm in terms of Wasserstein distance of order $2$. Our result holds as long as the continuous diffusion process associated with the algorithm converges exponentially fast to the target distribution along with some technical assumptions. While such an exponential convergence holds for example in the log-concave measure case, it also holds for the more general case of asymptoticaly log-concave measures. Our results thus extends the known rates of convergence in total variation and Wasserstein distances which have only been obtained in the log-concave case. Moreover, using a sharper approximation bound of the continuous process, we obtain better asymptotic rates than traditional results. We also look into variations of the Langevin Monte Carlo algorithm using other discretization schemes. In a first time, we look into the use of the Ozaki's discretization but are unable to obtain any significative improvement in terms of convergence rates compared to the Euler's scheme. We then provide a (sub-optimal) way to study more general schemes, however our approach only holds for the log-concave case.

Thomas Bonis, Steve Oudot

In this paper, we propose a new fuzzy clustering algorithm based on the mode-seeking framework. Given a dataset in $\mathbb{R}^d$, we define regions of high density that we call cluster cores. We then consider a random walk on a neighborhood graph built on top of our data points which is designed to be attracted by high density regions. The strength of this attraction is controlled by a temperature parameter $β> 0$. The membership of a point to a given cluster is then the probability for the random walk to hit the corresponding cluster core before any other. While many properties of random walks (such as hitting times, commute distances, etc\dots) have been shown to enventually encode purely local information when the number of data points grows, we show that the regularization introduced by the use of cluster cores solves this issue. Empirically, we show how the choice of $β$ influences the behavior of our algorithm: for small values of $β$ the result is close to hard mode-seeking whereas when $β$ is close to $1$ the result is similar to the output of a (fuzzy) spectral clustering. Finally, we demonstrate the scalability of our approach by providing the fuzzy clustering of a protein configuration dataset containing a million data points in $30$ dimensions.