Nous montrons ensuite comment nos résultats peuvent être utilisés pour quantifier la convergence de mesures invariantes de marches aléatoires sur des graphes géométriques aléatoires en prenant comme exemple le cas des graphes de k plus proches voisins. Enfin, nous étudions les performances d'un algorithme basique de type Monte-Carlo.

Dans le Chapitre 6, nous présentons l'approche "sac-de-mots" pour la reconnaissance de formes ainsi que les forces et faiblesses des méthodes de pooling usuelles. Nous présentons notre nouvelle méthode de pooling basée sur l'homologie persistante 0-dimensionnelle et étudions ses performances sur le jeu de données SHREC 2014.

Enfin, dans le Chapitre 7, nous présentons différentes pistes de nouvelles recherches pour mieux comprendre la convergence de marches aléatoires sur des graphes géométriques aléatoires.

Chapter 1 Introduction en français 1.1 Motivation

Les algorithmes d'analyse de données sont utilisées dans de nombreux domaines tels que les moteurs de recherche, la publicité en ligne ou encore le sport. Récemment, on parle de plus en plus des potentielles applications de l'analyse de données dans la santé par exemple. Ces nouvelles applications ont des enjeux tels que l'on aura besoin d'une profonde compréhension des algorithmes utilisés et, autant que possible, de garanties théoriques permettant de donner des garanties sur les résultats obtenus par les algorithmes utilisés. D'un autre côté, les bases de données que l'on a à traiter sont de plus en plus grandes tandis que les données elle-même sont de plus en plus difficiles à traiter : on a donc besoin d'algorithmes plus complexes, souvent plus difficiles à analyser. Par exemple, les performances de nombreux algorithmes diminuent très vite lorsque la dimension des données augmente, un phénomène appelé malédiction de la dimension. Cependant, il est possible que des données étant à première vue de grande dimension vivent en réalité sur une structure de faible dimension : une sous-variété plongée dans un espace de grande dimension. Il est alors capital de pouvoir travailler dans cette structure de faible dimension plutôt que dans l'espace ambiant. Supposons que nos données sont des variables aléatoires indépendantes tirées selon une mesure µ dont le support est une variété plongée. N'ayant pas directement accès à la variété, on peut vouloir construire un maillage de cette variété pour l'approcher. Néanmoins le calcul d'un tel maillage risque bien souvent d'être trop long. En pratique, on utilisera plutôt un graphe de voisinage, obtenu en prenant comme sommets les points de données et en ajoutant une arête entre deux points s'ils sont suffisamment proches. Ces graphes portent le nom de graphes géométriques aléatoires. On peut 2 CHAPTER 1. INTRODUCTION EN FRANC ¸AIS alors supposer que ce graphe contient la structure de la variété, la prochaine étape consiste alors à traiter l'information contenue dans ce graphe en utilisant des algorithmes d'analyse de graphe. En analyse de graphes, une des approches les plus efficaces consiste à utiliser les propriétés de marches aléatoires pour comprendre la structure générale du graphe étudié. Afin de comprendre le comportement ce type d'algorithme dans notre cas, il suffit donc d'étudier les propriétés des marches aléatoires sur des graphes géométriques aléatoires. Cependant, ces marches aléatoires sont difficiles à étudier directement. Néanmoins, il est possible de mieux les comprendre dans un cadre asymptotique : lorsque le nombre de points de données augmente, et sous certaines hypothèses concernant la façon dont on construit les graphe géométriques aléatoire, les marches aléatoires sur ces graphes convergent vers un processus de diffusion dont le générateur infinitésimal dépend à la fois de la variété et de la mesure µ. On peut donc s'attendre à ce que le comportement de marches aléatoires soit influencé à la fois par la structure de la variété plongée et par la structure de µ. Ainsi, même si le support de µ n'est pas une variété mais plus simplement l'espace ambiant, les approches utilisant des propriétés de marches aléatoires peuvent quand même être utilisées pour obtenir des algorithmes d'analyse de données non linéaires. Dans une première partie de cette thèse, nous allons utiliser la convergence des marches aléatoires sur des graphes géométriques aléatoires pour proposer un nouvel algorithme de partitionnement de données flou. Puis nous allons approfondir les résultats concernant la convergence des mesures invariantes de ces marches aléatoires, souvent utilisées dans des algorithmes d'analyse de graphe. Outre les mesures invariantes, les algorithmes d'analyse de graphes utilisent souvent deux autres propriétés de marches aléatoires : le Laplacien de graphe et les temps d'atteinte.

Laplacien de graphe Les Laplaciens de graphe sont des opérateurs agissant sur les fonctions définies sur les sommets d'un graphe. Ici, on se concentre sur un type particulier de Laplacien de graphe, appelé Laplacien de marche aléatoire, défini comme étant l'inverse du générateur d'une marche aléatoire sur un graphe. Les Laplaciens de graphe sont utilisés dans plusieurs types d'algorithmes comme le partitionnement de données [START_REF] Luxburg | A tutorial on spectral clustering[END_REF], la réduction de dimension [START_REF] Belkin | Laplacian eigenmaps for dimensionality reduction and data representation[END_REF] ou encore la classification semi-supervisée [START_REF] Chapelle | Semi-Supervised Learning[END_REF]. Puisque des marches aléatoires sur des graphes géométriques aléatoires converge vers des processus de diffusion, on peut s'attendre à ce que leur générateur convergence vers le générateur infinitésimal du processus de diffusion, entranant la convergence des Laplaciens de graphe correspondants. Cette convergence peut être utilisée de plusieurs manières. Dans un premier temps, on a cherché à montrer la convergence de l'action des Laplaciens sur certains ensembles de fonctions [START_REF] Belkin | Towards a theoretical foundation for laplacian-based manifold methods[END_REF][START_REF] Gin | Empirical graph Laplacian approximation of LaplaceBeltrami operators: Large sample results[END_REF][START_REF] Hein | Graph Laplacians and their convergence on random neighborhood graphs[END_REF]. La convergence des marches aléatoires vers des processus de diffusion est en fait obtenue via une telle convergence [START_REF] Ting | An analysis of the convergence of graph laplacians[END_REF]. D'autres travaux se sont ensuite concentrés sur la convergence du spectre des Laplaciens de graphe [START_REF] Belkin | Convergence of laplacian eigenmaps[END_REF][START_REF] García Trillos | A variational approach to the consistency of spectral clustering[END_REF].

Temps d'atteinte Il est aussi possible d'étudier la structure d'un graphe en utilisant le temps requis par une marche aléatoire pour passer d'un sommet x à un autre sommet x . Cette quantité est appelée temps d'atteinte de x à x , notée H(x, x ). Les temps d'atteinte peuvent être utilisés pour définir une métrique sur le graphe, appelée distance de commutation, en prenant comme distance entre deux sommets x et x la somme H(x, x ) + H(x , x). La distance de commutation est plus informative que des distances plus simples telles que la distance de plus court chemin car elle est influencée par la structure globale du graphe. Par exemple, considérons le graphe présenté dans la Figure 1.1, formé de deux composantes fortement connectées reliées par une seule arête. A priori, on souhaiterait qu'un sommet appartenant à la composante de gauche, tel que le sommet bleu, soit plus proche d'un autre sommet appartenant à la même composante comme le sommet rouge, que d'un sommet appartenant à la composante de droite, comme le sommet vert. Pour la distance de commutation, le sommet bleu est bien plus proche du sommet rouge que du vert, mais ce n'est pas le cas pour la distance de plus court chemin. Cette capacité à prendre en compte la structure complète du graphe explique le succès de cette distance dans de nombreuses applications comme le plongement de graphe [START_REF] Saerens | The principal components analysis of a graph, and its relationships to spectral clustering[END_REF][START_REF] Qiu | Graph Embedding Using Commute Time[END_REF], le partitionnement de données [START_REF] Yen | Clustering using a random-walk based distance measure[END_REF] ou encore la classification semi-supervisée [START_REF] Zhou | Learning from Labeled and Unlabeled Data Using Random Walks[END_REF]. Cependant, lorsque l'on considère des graphes géométriques aléatoires, la convergence des marches aléatoires nous déconseille d'utiliser ce type de quantité. En effet, en dimension supérieure à un, le temps d'atteinte d'un processus de diffusion à un point fixé est infini. Il n'existe donc pas de quantité naturelle vers lesquelles les temps d'atteinte sur des graphes géométriques aléatoires risquent pourraient converger, le risque étant que les temps d'atteinte convergent vers des quantités peu informatives. Ce phénomène a été étudié dans [START_REF] Ulrike Von Luxburg | Hitting and commute times in large random neighborhood graphs[END_REF], où les auteurs prouvent que la distance de commutation entre deux sommets converge vers une quantité dépendant essentiellement des structures locales du graphe autour des deux sommets: la distance ne capture donc pas la structure du graphe.

Mesure invariante La mesure invariante est une autre propriété des marches aléatoires couramment utilisée en analyse de graphes. L'algorithme PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF], qui classe des pages web via la mesure invariante d'une marche aléatoire sur le graphe ayant pour sommets les pages web et pour arêtes les hyperliens, est probablement l'exemple le plus connu d'un algorithme utilisant cette propriété. En ce qui concerne l'étude de la mesure invariante d'une marche aléatoire sur un graphe on peut distinguer deux cas suivant si le graphe est orienté ou non. Quand le graphe considéré est un graphe non orienté, la mesure invariante peut être facilement étudiée : elle est égale au degré des sommets du graphe. Cependant, quand le graphe est orienté, la mesure invariante de la marche aléatoire sur le graphe ne peut pas être calculée facilement. Ceci est problématique car de nombreux graphes intéressants sont orientés, comme le graphe de pages web décrit précédemment ou les graphes de plus proches voisins, souvent utilisés en analyse de données. Dans le cas de graphes géométriques aléatoires, on peut espérer que la mesure invariante des marches aléatoires convergent vers la mesure invariante du processus de diffusion limite, que le graphe soit orienté ou non. Si la mesure µ selon laquelle les données sont générées admet une densité f , la mesure invariante du processus de diffusion limite a une densité qui dépend de f . La mesures invariante d'une marche aléatoire sur un graphe géométrique aléatoire pourrait donc être utilisée pour calculer un estimateur de la densité f . Un tel estimateur pourrait être calculé en utilisant uniquement la structure du graphe, répondant ainsi à un problème posé dans [START_REF] Von | Density estimation from unweighted k-nearest neighbor graphs: a roadmap[END_REF]. Bien que cet estimateur de densité serait sans doute peu intéressant quand on a accès aux coordonnées des points de données, en quel cas il est possible d'utiliser des estimateurs de densité plus classiques, avoir accès à un tel estimateur nous garantirait qu'utiliser un graphe pour analyser les données n'entrane pas de perte majeure d'information. En effet, si on peut retrouver f à partir du graphe, alors ce graphe contient quasiment toute l'information initiale. Un résultat de convergence faible pour les mesures invariantes de marches aléatoires sur des graphes géométriques aléatoires a été obtenu dans [START_REF] Tatsunori | Metric recovery from directed unweighted graphs[END_REF].

1.2. CONTRIBUTIONS 5

Contributions

En général, la convergence des marches aléatoires sur des graphes géométriques aléatoires est utilisée pour obtenir des garanties théoriques pour des algorithmes utilisant certaines propriétés de ces marches. Dans cette thèse, nous commençons par suivre une démarche inverse et utilisons cette convergence pour proposer un nouvel algorithme de partitionnement de données flou. Le but du partitionnement de données est de répartir les échantillons de données en paquets en espérant que les échantillons appartenant à un paquet similaire aient des propriétés similaires. Cependant, cette approche n'apporte qu'une connaissance limitée de la structure des données car elle n'apporte a priori aucune information sur les relations entre les différents paquets : lesquels sont proches, à quel point ces paquets sont bien séparés etc. Afin d'obtenir une compréhension plus profonde des données, il faut donc identifier les interfaces entre les différents paquets. Considérons par exemple le cas de l'étude de l'espace des conformations d'une protéine. D'un côté, il est possible de détecter les conformations stables d'une protéine en utilisant du partitionnement de données [START_REF] Chodera | Long-time protein folding dynamics from short-time molecular dynamics simulations[END_REF]. D'un autre côté comprendre la structure des interfaces entre paquets permettrait d'identifier les étapes probables de transition entre deux conformations stables. On pourrait simplement définir ces interfaces comme l'ensemble de points dont le voisinage contient des points appartenant à plusieurs paquets différents. Néanmoins, les interfaces obtenues en utilisant cette définition peuvent être très instables. Le partitionnement de données flou semble un meilleur outil pour répondre à ce problème. Plutôt que de placer chaque échantillon de données dans un paquet, on cherche à attribuer à chaque échantillon des coefficients d'appartenance à chacun des paquets. Les interfaces correspondent alors simplement aux échantillons de données dont les coefficients d'appartenance sont bien répartis. Ces interfaces sont bien plus stables que les interfaces obtenues via la première définition proposée. Dans ce travail, on se concentre sur le partitionnement de données obtenu par une approche de recherche de modes. Dans cette approche, on suppose que les échantillons de données sont des variables aléatoires indépendantes tirées selon une mesure ayant une densité f et on identifie les paquets de données aux bassins d'attraction des maxima locaux de f : on utilise donc un flot de gradient pour partitionner les données. Ici, on propose d'obtenir un partitionnement de données flou en utilisant une version perturbée de ce flot de gradient prenant la forme d'un processus de diffusion dépendant de la densité f . Nous approchons ce flot de gradient en utilisant une marche aléatoire sur un graphe géométrique aléatoire calculé en utilisant un estimateur de f . En pratique on obtient une version floue de l'algorithme CHAPTER 1. INTRODUCTION EN FRANC ¸AIS de recherche de mode "Topological Mode Analysis Toolbox" (ToMATo) [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF] et, en utilisant les résultats théoriques existant pour cet algorithme, nous obtenons des garanties pour notre algorithme flou. Nous obtenons aussi des résultats expérimentaux encourageant pour notre algorithme sur des jeux de données synthétiques et réelles. En pratique, notre algorithme n'a besoin que d'un graphe géométrique aléatoire et d'un estimateur de la densité f . Ainsi, on pourrait l'utiliser sur des données ayant directement une structure de graphe, supposé être un graphe géométrique aléatoire, à condition d'être capable de calculer un estimateur de densité. Comme vu précédemment, un tel estimateur peut être obtenu en utilisant la mesure invariante de la marche aléatoire sur le graphe. Cependant, en général, on ne peut qu'obtenir la convergence faible de cette mesure invariante vers une mesure à partir de laquelle on peut estimer f . Améliorer ce résultat en obtenant une vitesse de convergence de la mesure invariante constitue le second apport de cette thèse.

Notre approche se base sur la méthode de Stein, initialement développée pour obtenir des vitesses de convergence pour le théorème central limite [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF]. Plus tard, Barbour [START_REF] Barbour | Stein's method for diffusion approximations[END_REF] a montré que cette approche pouvait être généralisée pour comparer la mesure invariante d'une chane de Markov réversible à la mesure invariante d'un processus de diffusion. En fait, sous certaines hypothèses techniques, ces mesures sont proches si le générateur de la chane de Markov correctement renormalisé et le générateur infinitésimal d'un processus de diffusion le sont. Il y a deux problèmes avec cette approche : elle est difficile à utiliser dans un cadre multidimensionnel et elle requiert une chane de Markov réversible. En effet, dans notre cas, la chane de Markov que nous souhaitons utiliser est la marche aléatoire sur le graphe qui n'est réversible que si le graphe est non orienté, auquel cas la mesure invariante de cette marche aléatoire peut être directement calculée. En nous basant sur des résultats récents obtenus dans [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF], nous proposons une nouvelle manière de borner la distance de Wasserstein entre deux mesures ν et µ où µ est une mesure réversible pour un opérateur différentiel L µ , satisfaisant certaines conditions techniques, et ν est la mesure invariante d'une chane de Markov, réversible ou non. Plus précisément, on montre que si le générateur de la chane de Markov renormalisé et L ν sont proches alors la distance de Wasserstein d'ordre deux entre µ et ν est faible. En utilisant ce résultat, nous sommes capables de quantifier la convergence des mesures invariantes de marches aléatoires sur des graphes géométriques aléatoires et nous prenons comme exemple le cas des graphes des k plus proches voisins. Notre résultat peut aussi être utilisé pour étudier un algorithme de Monte-Carlo basique. Enfin, il est possible de raffiner notre résultat dans le cas où µ est la mesure gaussienne. Nous pouvons ainsi donner des vitesses de convergence pour la distance de Wasserstein pour le théorème central limite.

La dernière partie de cette thèse n'est pas liée aux marches aléatoires sur des graphes mais utilise le concept d'homologie persistante utilisé par l'algorithme de partitionnement de données ToMATo pour faire de la reconnaissance de formes. De nombreux algorithmes ont été proposés pour traiter automatiquement des bases de données de formes 3D. Parmi ces algorithmes, certains des plus performants se basent sur l'approche dite "sac-de-mots". Dans cette approche, on commence par extraire un ensemble de descripteurs de chacune des formes de la base de données considérée. Ces descripteurs sont ensuite quantifiés par des vecteurs dont chaque coordonnée correspond à un "mot". L'information contenue dans chaque mot est ensuite extraite et compressée lors d'une étape dite de "pooling" : pour chaque forme, on considère la moyenne, "sum-pooling", ou le maximum, "max-pooling", de chaque mot sur la forme correspondante. On a donc caractérisé chaque forme par un vecteur et on peut ainsi classifier ces formes en utilisant l'ensemble des vecteurs obtenus dans des algorithmes de classification classiques. Dans l'idéal, toutes les étapes de ce processus devraient être robustes vis-à-vis des transformations que les formes peuvent subir : translations, rotations ou encore changement d'échelle, tout en étant suffisamment discriminantes. Maintenant, considérons les mots non pas comme un simple ensemble de valeurs mais comme des fonctions définies sur un graphe de voisinage, par exemple si on utilise un maillage pour calculer les descripteurs on peut utiliser le graphe fourni par le maillage et associer à chaque sommet la valeur du mot obtenu pour le descripteur correspondant. Le max-pooling consiste alors à construire un vecteur contenant les maxima globaux de chacune des fonctions mots. On serait alors tenté de rendre le max-pooling plus discriminant en considérant tous les maxima locaux de chaque fonction mot plutôt que de se restreindre aux maxima globaux. Cependant, une telle approche serait fortement instable : perturber les fonctions mots, même faiblement, peut créer de nombreux maxima locaux qui ne sont pas forcément caractéristiques de la forme 3D considérée. Pour pallier ce problème, nous proposons d'utiliser le concept d'homologie persistante 0-dimensionnelle, ou proéminence, afin de sélectionner les maxima locaux les plus stables par rapport aux perturbations des fonctions mots. Nous appelons la procédure obtenue "Topological Pooling", et nous montrons qu'elle est plus efficace que le schéma de max-pooling classique.

CHAPTER 1. INTRODUCTION EN FRANC ¸AIS

Plan de la thèse

Dans le Chapitre 3, nous introduisons le concept de marches aléatoires sur des graphes et les algorithmes d'analyse de graphes utilisant ces marches. Nous définissons ensuite les processus de diffusion et présentons leurs propriétés en lien avec ce travail. Nous introduisons ensuite les graphes géométriques aléatoires et nous présentons les résultats de convergence existant pour les marches aléatoires sur ces graphes.

Dans le Chapitre 4, nous présentons le cadre de la recherche de mode en partitionnement de données ainsi que l'algorithme ToMATo. Nous présentons ensuite notre algorithme de partitionnement de données flou utilisant une marche aléatoire sur un graphe géométrique aléatoire approprié. Nous obtenons ensuite des garanties théoriques pour notre algorithme et nous montrons son efficacité sur des jeux de données synthétiques et réelles.

Dans le Chapitre 5, nous utilisions une approche basée sur la méthode de Stein pour borner la distance de Wasserstein entre deux mesures et nous donnons plusieurs applications de nos résultats. Nous commençons par donner des vitesses de convergence pour le théorème central limite.

Chapter 2 Introduction

Motivation

Data analysis algorithms are used in a large number of applications such as search engines, online advertisement, sports, etc. The range of these applications is to become even broader as new promising applications in other domains such as health care are arising. As the stakes involved in these new applications are higher, we need a strong understanding of the algorithms we are using and, if possible, theoretical guarantees ensuring the correctness of these algorithms. Another challenge posed by these new applications is the increasing complexity of the data to process, either due to the sheer amount of data available or to the nature of the data itself. The dimensionality of the data is one such source of complexity: the efficiency of learning algorithms drops quickly when the dimension of the data increases, a phenomenon called the curse of dimensionality. Fortunately, in some cases the data happens to be drawn from a lower dimensional structure, a manifold, embedded in a higher dimensional space. It is then crucial to take advantage of this structure. Suppose the data takes the form of a point cloud of independent and identically distributed random variables drawn from a measure µ with density f supported on a manifold. Since we do not have access to the manifold itself, a natural idea to use the manifold structure would be to build a mesh from the data point cloud and then perform data analysis using this mesh. As computing an actual mesh might be too computationally expensive, one can instead compute a graph using the data points as vertices and adding an edge between two vertices if they are sufficiently close. Such a graph is called a random geometric graph. At this point, we can expect the graph to capture the structure of the manifold, thus the next step is processing the information contained in the graph 10 CHAPTER 2. INTRODUCTION through graph analysis algorithms. An efficient approach to graph analysis consists in using the properties of a random walk to gain insight of the full graph structure. Obtaining theoretical guarantees, such as consistency, for algorithms using random geometric graphs can then be achieved by understanding the properties of random walks on these graphs. Although these are complex objects, it turns out it is possible to gain some insight on their properties in an asymptotic setting. Indeed, when the number of data samples goes to infinity, and under some rather natural assumption on the way the graphs are built, random walks on random geometric graphs converge to a diffusion process whose generator depends on both the Laplacian of the manifold and the sampling density f . Since the limiting diffusion does not only depend on the manifold structure but also on f , it makes sense to use random walks on random geometric graphs to perform non-linear data analysis even when µ has a full-dimensional support. Moreover, the convergence of random walks on random geometric graphs to diffusion processes can also be exploited to study the consistency of random-walk based algorithms on such graphs. Our work will consist in using the convergence of random walks on random geometric graphs to propose a new data analysis algorithm and to provide a better understanding of the convergence of a property of random walks often used by data analysis algorithm: the invariant measure. Outside of the invariant measure, random walk-based data analysis usually rely on two properties: the graph Laplacian and hitting times. Let us discuss the consequences of the convergence of random walks to diffusion processes for these three properties.

Graph Laplacian Graph Laplacians are operators acting on functions of the vertices of a graph G. Here we focus on the random walk graph Laplacian L of G which is simply the opposite of the generator of a random walk on G. As the spectrum of L contains information regarding the connectivity of G, it is often used by Spectral clustering algorithms [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. Graph Laplacians are also used in many other applications such as dimensionality reduction using Diffusion maps [START_REF] Belkin | Laplacian eigenmaps for dimensionality reduction and data representation[END_REF] or semi-supervised classification [START_REF] Chapelle | Semi-Supervised Learning[END_REF]. Since random walks on random geometric graphs converge to diffusion processes, we can expect the generators of the random walks to converge to the infinitesimal generators of the limiting diffusion processes. There are two main approaches to obtain such a convergence. The first approach is to show the convergence of Lφ for φ belonging to a set of functionals [START_REF] Belkin | Towards a theoretical foundation for laplacian-based manifold methods[END_REF][START_REF] Gin | Empirical graph Laplacian approximation of LaplaceBeltrami operators: Large sample results[END_REF][START_REF] Hein | Graph Laplacians and their convergence on random neighborhood graphs[END_REF]. The convergence of random walks to diffusion processes is actually obtained using this type of convergence [START_REF] Ting | An analysis of the convergence of graph laplacians[END_REF]. The second approach focuses on proving the convergence of the spectrum of the graph Laplacian to the spectrum of the infinitesimal generator of the limiting diffusion process [START_REF] Belkin | Convergence of laplacian eigenmaps[END_REF][START_REF] García Trillos | A variational approach to the consistency of spectral clustering[END_REF].

Hitting times

It is also possible to study the structure of the graph by using the time required for a random walk to travel from a vertex x to another vertex x . This quantity is called hitting time from x to x , and we denote it by H(x, x ). Hitting times can be used to define a metric on the graph called commute distance, where the commute distance between two vertices x, x is simply the sum H(x, x ) + H(x , x). The commute distance is more informative than simpler distances such as the shortest path distance as it takes into account the full graph structure. For instance, let us consider the graph drawn in Figure 2.1 which is composed of two highly connected components linked by a single edge. Intuitively, we expect the blue vertex and the red vertex to be close, since they belong to the same highly connected component, while being far away from a vertex from the other component such as the green vertex. While this is true for the commute distance, it is not the case for the shortest path distance. Hence, the commute distance is used with great success in many different applications such as graph embedding [START_REF] Saerens | The principal components analysis of a graph, and its relationships to spectral clustering[END_REF][START_REF] Qiu | Graph Embedding Using Commute Time[END_REF], clustering [START_REF] Yen | Clustering using a random-walk based distance measure[END_REF] or semi-supervised learning [START_REF] Zhou | Learning from Labeled and Unlabeled Data Using Random Walks[END_REF].

To study the consistency of hitting times, it would seem natural to compare hitting times of random walks on random geometric graphs to hitting times of the limiting diffusion processes. However, in dimension greater than one, the hitting time of a diffusion process to a given point is infinite, thus we cannot expect hitting times of random walks on random geometric graphs to converge to meaningful quantities. This ill-behaviour was described in [START_REF] Ulrike Von Luxburg | Hitting and commute times in large random neighborhood graphs[END_REF], where the authors proved the hitting times between two vertices of a large random geometric graph depend mostly on local quantities alone, in which case hitting times do not capture the global structure of the graph.

Invariant measure Finally, it is possible to use the invariant measure of a random walk on a connected graph to process data. The most famous algorithm using this approach is probably the PageRank algorithm [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] which ranks web-pages using the invariant measure of a random walk on the graph obtained by taking web pages as vertices and hyperlinks as edges. When studying the invariant measure of a random walk on a graph, there are two cases. When the graph undirected, the invariant measure can be directly computed: it is proportional to the degree function. On the other hand, it is hard to say anything about the invariant measure of a random walk on a directed graph. This is problematic since nearest neighbor graphs, which are quite popular in data analysis due to their sparsity, are directed.

In our case, one may wonder whether the convergence of random walks to diffusion processes implies the convergence of the invariant measure of the random walks to the invariant measure of the diffusion processes. Let us note that the invariant measure of the limiting diffusion process depends can be used to recover the underlying density f . Hence, the invariant measure of a random walk on a random geometric graph can be used to obtain an estimator of f . Moreover, this estimator can be computed using the graph structure alone, which would solve an open problem stated in [START_REF] Von | Density estimation from unweighted k-nearest neighbor graphs: a roadmap[END_REF]. Indeed, while this density estimator would not be interesting whenever we have access to the coordinates of the data points, in which case it is more efficient to use a standard density estimator, it would confirm we are not loosing information by working with the random geometric graph rather than the original point cloud. Indeed, if we are able to recover f , and thus µ, from the sole graph structure, then it means it contains most of the original information. However, the current results regarding the convergence of invariant measure of random walks on random geometric graphs are not sufficient to prove the consistency of such an estimator since the only known result is a weak convergence result proved in [START_REF] Tatsunori | Metric recovery from directed unweighted graphs[END_REF].

Contributions

As we have seen, the convergence of random walks on random geometric graphs is usually used to prove the consistency of data analysis algorithms. In a first part of this work, we propose to use this convergence to design a new algorithm for soft clustering. The objective of clustering algorithms is to partition the data in clusters, hoping that data belonging to a similar cluster shares similar properties. Overall, clustering provides a fairly limited knowledge of the structure of the data: while the partition into clusters is well understood, the interplay between clusters -respective locations, proximity relations, interactions-remains unknown. Identifying interfaces between clusters is the first step toward a higher-level understanding of the data, and it already play a prominent role in some applications such as the study of the conformations space of a protein, where a fundamental question beyond the detection of metastable states is to understand when and how the protein can switch from one metastable state to another [START_REF] Chodera | Long-time protein folding dynamics from short-time molecular dynamics simulations[END_REF]. Clustering can be used in this context, for instance by defining the border between two clusters as the set of data points whose neighborhood, in the ambient space or in some neighborhood graph, intersects the two clusters, however this kind of information is by nature unstable with respect to perturbations of the data. Soft clustering appears as the appropriate tool to deal with interfaces between clusters. Rather than assign each data point to a single cluster, it computes a degree of membership to each cluster for each data point. The promise is that points close to the interface between two clusters will have similar degrees of membership to these clusters and lower degrees of membership to the rest of the clusters. Thus, compared to hard clustering, soft clustering uses a fuzzier notion of cluster membership in order to gain stability on the locations of the clusters and their boundaries. Here, we are interested in the mode-seeking approach to clustering. In mode-seeking, clusters are defined continuously as the basins of attractions of the modes of the density. In other words, clusters are defined through the limit of a gradient flow of the density. We propose to derive a soft clustering approach to a mode-seeking algorithm called Topological Mode Analysis Toolbox algorithm [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF] by turning this gradient flow into a stochastic differential equation whose solution is a diffusion process depending on the density f . In practice, we approximate the behaviour of the diffusion process by a random walk on a random geometric graph computed using a density estimator. We then prove the consistency of our algorithm, study the impact of the various parameters on the output of our algorithm and evaluate the performance of our algorithms on several datasets. An interesting aspect of our algorithm is that it does not require the actual coordinates of the data points but merely a random geometric graph structure and a density estimator. Hence, this algorithm could directly be used as a graph analysis algorithm for random geometric graphs provided we are able to compute a density estimator using the graph structure alone. As we have mentioned earlier, it is possible to compute a density estimator from a random geometric graph using a random walk on the graph. However, the only result regarding the convergence of this invariant measure is expressed in terms of weak convergence. The second contribution of this thesis will consist in strengthening this result by quantifying this convergence.

Our approach is based on Stein's method, which was originally developed to bound the distance to the Gaussian measure to provide rates for the Central Limit Theorem [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF]. In [START_REF] Barbour | Stein's method for diffusion approximations[END_REF], it was shown Stein's method can actually be used to bound the distance between the invariant measure of a reversible Markov chain to the invariant measure of a diffusion process CHAPTER 2. INTRODUCTION using their (infinitesimal) generators. This seems close to our objective since a random walk on a graph is a Markov chain, however there are two main issues with using this result in our setting. First, it is difficult to use in a multidimensional setting. Second, it requires a reversible Markov chain and thus would only be helpful to study random walks on undirected graphs which we already know how to deal with. By adapting a recent result from the Stein's method literature [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF], we provide a way to bound the 2-Wasserstein distance between the invariant measure ν of a Markov chain with generator L ν and a measure µ which is the reversible measure of a differential operator L µ . More precisely, we show that the distance between µ and ν can be bounded using a discrepancy between the two operators L ν and L µ . We are thus able to quantify the convergence of invariant measures of random walks on random geometric graphs: as an illustration, we compute the rate of convergence in the case of a k-nearest neighbor graph. Whenever µ is the Gaussian measure, we provide a more refined bound which allows us to give rates of convergence for the Wasserstein distance for the Central Limit Theorem, either for the p ≥ 2-Wasserstein distance in the unidimensional setting or for the 2-Wasserstein distance distance in the multidimensional case. Finally, we also show how our result can be used to study a simple Markov Chain Monte Carlo algorithm.

The last work of this thesis is not related to random walks on random geometric graphs. Instead, we tackle the problem of shape recognition by using the concept of 0-dimensional persistent homology used by the Topological Mode Analysis Toolbox clustering algorithm. In order to automatically process 3D shapes databases, there exist multiple retrieval and classification algorithms. The bag-of-words approach, originally developed for image analysis, is one such classification pipeline used to process 3D shapes. Traditionally, the bag-of-words method relies on extracting an unordered collection of descriptors from the shapes we consider. Each descriptor is then quantized by a vector whose coordinates are called words. The information available in the words values is then extracted and summarized through a step called pooling, producing a vector usable by standard learning algorithms. Traditional pooling schemes consist in taking either the average of the value -sum-pooling-or the maximum value -max-pooling-of each words across the shape. Ideally, each step of this framework should be robust to standard transformations which may affect 3D shapes -translations, rotations or changes of scale-while being sufficiently discriminative. Here, we propose to put more structure in the bag-of-words approaches: rather than considering an unordered collection of word values, we instead view these values as a set of functions on the mesh of the shape. From here, the pooling step should extract information from a function opening up new avenues to

ORGANIZATION OF THE THESIS

refine traditional pooling schemes. For instance, the max-pooling scheme, which consists in taking the global maximum of a word function, could be refined by considering all the local maxima of a word function instead. But such an approach would not be stable since perturbing a function, even slightly, can create many uninteresting multiple local maxima. To fix this issue, we use the concept of 0-dimensional persistent homology, or prominence, to obtain a pooling procedure which uses all the local maxima of the word functions and weights them regarding to their stability which respect to perturbations. Thus, we are able to generalize max-pooling to design a more discriminative scheme while retaining most of its stability. We provide experimental results proving the efficiency of this new pooling scheme.

Organization of the thesis

In Chapter 3, we present random walks on random graphs along with algorithms using these random walks to perform graph analysis. We then give a brief presentation of diffusion processes. Finally, we present random geometric graphs and known results on the convergence of random walks on random geometric graphs.

In Chapter 4, we present the mode-seeking framework and the Topological Mode Analysis Toolbox algorithm. We then show how this algorithm can be turned into a soft clustering algorithm by using a random walk on a properly weighted random geometric graph. We prove the consistency of this new algorithm and show its effectiveness on both synthetic and real datasets.

In Chapter 5, we obtain new bounds on the Wasserstein distance between two measures using Stein's method and provide several applications of these bounds. We first derive convergence rates in the Central Limit Theorem which hold in the multivariate setting. We then show how to apply our result to bound the Wasserstein distance between the invariant measure of a random walk and the invariant measure of a diffusion process. Using this result, we are able to give rates for the convergence of the invariant measure of a random walk on a random geometric graph. As an illustration, we study the special case of the k-nearest neighbor graph. Finally, we show how our results can be used to study a simple Monte Carlo algorithm.

In Chapter 6, we present the bag-of-word approach for shape recognition and discuss the strengths and weaknesses of traditional pooling procedure. We then provide a new pooling procedure based on 0-dimensional persistent homology and assess its performance on the SHREC 2014 dataset.

Finally, in Chapter 7, we highlight possible avenues for new research to

CHAPTER 2. INTRODUCTION
better understand the convergence of algorithms relying on random walks on random geometric graphs.

Chapter 3

Random walks on random geometric graphs

In this chapter, we formally introduce the concept of random walks on graphs as Markov chains and we provide an overview of the main random walk-based algorithms used in graph analysis. Then, we introduce diffusion processes, their relevant properties for our works and we show how to approximate a diffusion process through a Markov chain. Finally, we describe random geometric graphs and we explore the consequences of the convergence of random walks on random geometric graphs to diffusion processes.

Markov chains for graph analysis

A (time-homogeneous) Markov chain is a sequence of random variables (X n ) n∈N taking values in a measurable space (E, F) such that the behavior of X n depends on X n-1 only. More formally we say that (

X n ) n∈N is a Markov Chain if ∀n ∈ N, ∀F ∈ F, P(X n+1 ∈ F | X 0 , . . . , X n ) = P(X n+1 ∈ F | X n ) = K(X n )(F ),
where K is a function from E to the space of probability measures on E called the transition kernel of the Markov chain. A Markov chain is completely characterized by its state space E, the measure of X 0 and K. Whenever E is discrete, the measures K(.) are completely characterized by their values on singletons. Hence, we can define K as a function from

E 2 to [0, 1] such that ∀x, x ∈ E, K(x, x ) = P(X 1 = x | X 0 = x).

CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS

In the remainder of this Section, we assume E to be discrete. Let G be a weighted graph with vertices X and weight function w : X × X → R + . A random walk on G is a Markov chain with state space X and transition kernel K defined by

∀x, x ∈ X , K(x, x ) = w(x, x ) x∈X w(x, x)
.

We say a graph is undirected if

∀x, x ∈ X , w(x, x ) = w(x , x).
Finally, the degree of a vertex x is given by

d(x) = x ∈X w(x , x),
and the volume of a subset A ⊂ X is

vol(A) = x∈A d(x).

Graph Laplacian

Consider a Markov chain with state space E and transition kernel K. We call generator of the Markov chain the operator L such that, for any function φ : E → R and any state x ∈ E,

Lφ(x) = E[φ(X 1 )|X 0 = x] -φ(x) = x ∈X (φ(x ) -φ(x))K(x, x ).
In the case of a random walk on a graph, the opposite of this generator is called the graph Laplacian L := -L. Actually, there exist three possible definitions of graph Laplacians depending on the normalization used [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]; the graph Laplacian defined here is usually called random walk graph Laplacian. Let us study the spectrum of L.

Proposition 1 (Proposition 3 [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]). If G is undirected, then L is positive semi-definite and admits |X | positive real eigenvalues.

These eigenvalues and the corresponding eigenvectors contain a great deal of information regarding the structure of the graph itself. As an example, let us consider the problem of clustering which consists in gathering vertices of the graph in clusters such that the intra-cluster connectivity is high while the inter-cluster connectivity is small. The most elementary way to cluster a graph is to associate clusters with connected components. While there are more direct ways to recover the connected components of an undirected graph, they can be computed from the spectrum of the graph Laplacian.

Proposition 2 (Proposition 4 [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]). If G is undirected, then the multiplicity of the eigenvalue 0 of L equals the number of connected components A 1 , . . . , A k in the graph. Moreover, the eigenspace of 0 is spanned by the indicator functions of these components.

Since an eingenvalue equal to zero indicates a connected component, we could expect a small eingenvalue to indicate a subset of X that is close to being disconnected from the rest of the graph. In order to quantify how close A ⊂ X is close to being disconnected from the graph, we can consider the cut value

cut(A) = 1 2 x∈A,x / ∈A w(x, x ).
This cost corresponds to the total weight of the edges we would need to remove in order to disconnect A from the rest of the graph. If this quantity is small, it means A and X -A are close to being disconnected. In order to define two clusters on a connected graph, it is tempting to assign the first cluster to a set A minimizing the cut value and the second cluster to X -A. However, quite often, the set A minimizing this cut value is simply a vertex of the graph so this quantity alone cannot be used to obtain a good clustering. Instead, one possibility is to minimize a regularized quantity such as Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] N

cut(A) = cut(A)(V ol(A) -1 + V ol(X -A) -1 ).
In this case, if A (or X -A) is reduced to a point, then its volume will be low and N cut(A) large. To divide a graph in two clusters, one would like to find the set minimizing the Ncut value and define it as a cluster while the second cluster would correspond to the remainder of the graph. However, this minimization problem is NP-hard [START_REF] Wagner | Between min cut and graph bisection[END_REF]. Fortunately, a relaxation of this minimization problem is easier to deal with: its solution is simply the second eigenvector of the graph Laplacian [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. Moreover, if the associated eigenvalue is small, so is the corresponding relaxed quantity. This analysis can be generalized when we want to cluster X in k different subclusters in which case it involves the first k eigenvalues and eigenvectors of the graph Laplacian.

CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS

Algorithms using the spectral properties of graph Laplacians to perform clustering belong to the family of Spectral clustering algorithms [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. The Spectral clustering algorithm corresponding to our definition of the graph Laplacian was introduced in [START_REF] Shi | Normalized cuts and image segmentation[END_REF]: one computes the first k (k being the number of clusters) eigenvectors of L, each vertex of the graph is then embedded into R d with coordinates equal to the values of the eigenvectors on the vertex, the clustering is finally obtained using a k-means algorithm [START_REF] Hartigan | A k-means clustering algorithm[END_REF].

Hitting time and commute distance

Let x ∈ E and let (X x n ) n≥0 be a random walk on the graph such that X x 0 = x. For any state x ∈ E, we define the hitting time from x to x by

τ x,x = inf n≥0 (X x n = x ),
and we denote by H x,F the mean hitting time from x to x

H x,F = E[τ x,x ].
Finally, we define the commute distance between any two states x and x as

C x,x = H x,x + H x ,x .
For a random walk on a connected graph, the commute distance between two vertices is always finite. Moreover, on an undirected graph, the commute distance can be computed using the generalized inverse of the graph Laplacian [START_REF] Luxburg | A tutorial on spectral clustering[END_REF].

Invariant measure

A probability measure π is said to be an invariant measure for the Markov

chain if ∀x ∈ E, π(x) = x ∈E K(x , x)π(x ).
We say a Markov chain to be irreducible if

∀x, x ∈ E, ∃n > 0, P(X n = x |X 0 = x) > 0.
Furthermore, we say a Markov chain to be positive recurrent if

∀x ∈ E, H x,x < ∞.
Irreducibility and positive recurrence ensures the existence of a unique invariant measure for the Markov chain.

Proposition 3 (Theorem 1.7.7 [START_REF] Norris | Markov chains. Cambridge series in statistical and probabilistic mathematics[END_REF]). An irreducible Markov chain admits a unique invariant measure π if and only if it is positive recurrent. Moreover,

∀x ∈ E, π(x) = 1 H x,x x ∈E H -1 x,x .
Computing the invariant measure of a random walk on an undirected graph is simple: it is proportional to the degree function of the graph.

Proposition 4. The random walk on a connected and undirected graph admits a unique invariant measure π with ∀x ∈ X , π(x) =

x ∈X w(x, x ) x ,x ∈X w(x , x ) .

On the other hand, the invariant measure of a random walk on a directed graph cannot be deduced from local quantities alone. For instance, let us take n ∈ N and consider the random walk of the graph with vertices X = {0, . . . , n} and weight function

∀i, j ∈ X , w(i, j) =      1 if j = 0 1 if j = i + 1 0 otherwise .
The invariant measure of a random walk on this graph is defined on any vertex i ∈ {1, . . . , n} by

π(i) = 2 n-i 2 n+1 -1 .
As we can see, the values of this invariant measure do not depend on local quantities such as the degree of a vertex. For directed graphs, computing π requires solving a system of linear equations. However, the computations can be prohibitive whenever |E| is large. Instead, it is sometimes possible to approximate π. We say a Markov chain to be aperiodic if

∀x ∈ E, ∃n ∈ N, ∀n ≥ n , P(X n = x|X 0 = x) > 0.
An approximation of π can be obtained through the measures of X n for large values of n as long as the Markov chain is aperiodic, irreducible and positive recurrent, in which case it is said to be ergodic.

Proposition 5 (Theorem 1.8.3 [61]). If E is connected and (X n ) n≥0 is ergodic then ∀x ∈ E, lim n→∞ P(X n = x) = π(x).

CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS

There is a large variety of results providing convergence rates of X n to π, for example if the generator of the Markov chain is diagonalisable with eigenvalues λ |E| ≤ . . . λ 2 ≤ λ 1 = 0, then when |λ 2 | is large, the convergence of the measure of X n to π is fast [START_REF] Asher | Markov chains and mixing times[END_REF]. This is not a surprise: if we consider a random walk on a graph, when λ 2 is close to zero then the first non-zero eigenvalue of the graph Laplacian is small as well. This means there exists A ⊂ X such that the connectivity between A and the rest of the graph is small. Hence, the random walk will take a long time entering or leaving A.

Invariant measures of random walks on graphs are commonly used for graph analysis. For example, let X be the set of all web-pages and, for two web-pages x, x , let a(x, x ) = 1 if the page x contains a link to the page x . For α > 0, let

w α (x, x ) = α |X | + (1 -α) a(x, x ) x∈X a(x, x)
.

The random walk on the random graph with vertices X and weight function w α can be used as a simple model of a person clicking randomly on links or, sometimes, jumping to a totally unrelated page. This random walk is irreducible and positive recurrent, it thus admits an invariant measure π. By Proposition 5, the value of this invariant measure on a vertex corresponds to the probability for the random surfer to be visiting the corresponding web-page after an infinite amount of time, it will thus tend to be higher for web-pages having many incoming hyperlinks, which can be assumed to be more relevant than other pages. Hence, the value of the invariant measure can be used to rank vertices of the graph and thus web-pages. This algorithm is a simpler version of the PageRank algorithm [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] which is used along many other ranking algorithms in the Google search engine.

As the total number of web-pages is very large, this invariant measure is computed using bots actually performing the random walk.

From Markov chains to diffusion processes

In order to study the behaviour of algorithms based on random walks on graphs, we want to exploit the convergence of these random walks to continuous processes called diffusion processes. In this section, we introduce these processes and give a brief overview of their relevant properties for our work. A more detailed presentation of these processes can be found in [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF][START_REF] Durrett | Stochastic calculus : a practical introduction. Probability and stochastics series[END_REF][START_REF] Stewart | Markov processes : characterization and convergence[END_REF][START_REF] Stroock | Multidimensional diffusion processes. Die Grundlehren der mathematischen Wissenschaften[END_REF]. We start by introducing a few notations.

Notations for multivariate analysis

Let x ∈ R d and k ∈ N, we denote by x ⊗k ∈ (R d ) ⊗k the tensor of order k of x:

∀j 1 , . . . , j k ∈ {1, . . . , d}, (x ⊗k ) j 1 ,...,j k = k i=1 x j i .
For any x, y ∈ (R d ) ⊗k , the Hilbert-Schmidt scalar product between x and y is < x, y >= i∈{1,...,d} k

x i y i , and, by extension,

x 2 =< x, x > .
Let x ∈ R d and k ∈ N, we have

x ⊗k 2 = i∈{1,...,d} k ( k j=1 x i j ) 2 = i∈{1,...,d} k k j=1 x 2 i j = ( k l=1 x 2 l ) k = x 2k .
Hence,

x ⊗k = x k .
For any smooth function φ and

x ∈ R d , let ∇ k φ ∈ (R d ) ⊗k such that ∀j 1 , . . . , j k ∈ {1, . . . , d}, (∇ k φ(x)) j 1 ,...,j k = ∂ k φ ∂x j 1 . . . ∂x j k (x).
Finally, the Laplacian of a function φ is

∆φ =< ∇ 2 φ, I d >= d i=1 ∂ 2 φ ∂ 2 x i .

Diffusion processes

Let E be an open domain of R d . Let (K t ) t≥0 be a family of kernels from E to the space of probability measures on E such that CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS

• for any x ∈ E, and any Borel set

B ⊂ E such that x ∈ B, K 0 (x)(B) = 1 (K 0 (x)
is the Dirac measure centered on x) ;

• for any Borel set B ⊂ E and any t ≥ 0, K t (.)(B) is a measurable function;

• for any Borel set B and any s, t ≥ 0,

K t+s (x)(B) = E K t (y)(B)K s (x)(dy).
This family is said to be a transition function and plays a similar role as the transition kernel for Markov chains. A family of random variables (X t ) t≥0 taking values in E is a Markov process if, for every compactly supported continuous function φ,

∀s 1 ≤ • • • ≤ s n ≤ t, E[φ(X t )|X s 1 , . . . , X sn ] = E φ(y)K t-sn (X sn )(dy).
Remark that such a definition implies that (X t ) t≥0 satisfies the Markov property:

∀s 1 ≤ • • • ≤ s n ≤ t, E[φ(X t )|X s 1 , . . . , X sn ] = E[φ(X t )|X sn ].
Let us consider a simple case of a Markov process (W t ) t≥0 for which

• W 0 = 0; • t → W t is almost surely continuous; • For any s ≤ t, W t -W s is a d-dimensional centered normal random variable with variance (t -s)I d ; • W t -W s is independent of W s .
W t is called the d-dimensional Brownian motion. By Donsker's Theorem, we know that if Z 1 , . . . , Z n are i.i.d. random variables with mean 0 and variance 1 then

1 √ n n i=1 Z i 1 i n ≤t converges to (W t ) t∈[0,1]
. In other words, we are able to approximate the trajectories of (W t ) t≥0 by trajectories of a Markov Chain (X k ) k∈N with state space R such that

X k+1 = X k + 1 √ n Z k ,
where the Z k are i.i.d. random variables with the same measure as Z 1 .

While this is a good start, we cannot expect random walks on random geometric graphs to always converge to a Brownian motion. On the other hand, the class of Markov processes is too large to study convergence of Markov chains.

FROM MARKOV CHAINS TO DIFFUSION PROCESSES

25

Let C 0 be the space of real-valued, continuous and compactly supported functions on E. For any φ ∈ C 0 , any x ∈ E and any t > 0, let

P t φ(x) = E[φ(X t ) | X 0 = x] = E φ(y)K t (x)(dy).
We say (P t ) t≥0 is the semigroup associated to (X t ) t≥0 because

P t+s φ(x) = E φ(y)K t+s (x)(dy) = E×E φ(z)K s (x)(dz)K t (z)(dy) = P t (P s φ(x)).
A family of bounded operators (P t ) t≥0 acting on E is a Feller semigroup if

• P 0 = Id; • ∀t ≥ 0, P t 1 = 1; • ∀s, t ≥ 0P t+s = P t P s ; • ∀φ ∈ C 0 , t ≥ 0, P t φ ∞ ≤ φ ∞ ; • ∀φ ∈ C 0 , t ≥ 0, φ ≥ 0 =⇒ P t φ ≥ 0; • ∀φ ∈ C 0 , lim t→0 (P t -Id)f ∞ → 0.
A Markov process associated to a Feller semigroup is called a Feller process. Furthermore, given a Feller semigroup, it is always possible to define a Feller process associated to this semigroup.

In particular, a Feller semigroup is a strongly continuous positive contraction semigroup. These semigroups are well-studied objects [START_REF] Engel | A short course on operator semigroups[END_REF] and can be characterized by an operator called infinitesimal generator. The infinitesimal generator L of a Feller semigroup (P t ) t≥0 is an operator acting on

D(L) = {φ ∈ C 0 | lim t≥0 (P t -Id)φ t exists},
and such that, for any φ ∈ D(L),

lim t≥0 (P t -Id)φ t = Lφ.
D(L) is dense in C 0 and L is a linear operator. Moreover, by the Hille-Yosida Theorem, a linear operator satisfying some technical conditions is CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS also the generator of a Feller semigroup. Hence, there is a one to one correspondence between Feller semigroups and a set of linear operators. A diffusion process (X t ) t≥0 is a Markov process associated to a Feller semigroup with infinitesimal generator L such that ∀φ ∈ D(L),

Lφ = b.∇φ+ < a, ∇ 2 φ >, where b : E → R d and a = σ T σ 2 with σ : E → R d × R d such
that σ is symmetric and positive definite on E. For any diffusion process (X t ) t≥0 , there exists ( Xt ) t≥0 such that the trajectories of ( Xt ) t≥0 are almost surely continuous and ∀t ≥ 0, P(X t = Xt ) = 1. Hence, without loss of generality, we can assume the trajectories of diffusion processes to be almost surely continuous.

In order to give more intuition about diffusion processes, let us note that a diffusion process (X t ) t≥0 is actually the solution to the following stochastic differential equation

dX t = b(X t )dt + σ(X t )dW t , (3.1)
where W t is a d-dimensional Brownian motion. The function b is called a drift and correspond to a deterministic trend for the trajectories of X t whereas σ, called diffusion coefficient, controls the noise disrupting the trajectories. If σ were equal to zero then Equation 3.1 would be a purely deterministic ordinary differential equation.

Convergence of Markov chains to diffusion processes

In order to tackle the problem of convergence of Markov chains, we must first specify a suitable notion of convergence. Let µ and (ν n ) n∈N be measures on a space E. We say (ν n ) n∈N converges weakly to µ if, for any continuous and bounded function φ on E,

E φdν n → E φdµ.
Weak convergence can actually be characterized in several ways.

Theorem 6 (Portmanteau Theorem). A family of probability measure (ν n ) n∈N converges weakly to another probability measure µ if and only if

• For any uniformly continuous function φ, E φdν n → E φdµ;

• For any closed set F ⊂ E, lim sup ν n (F ) ≤ µ(F );

FROM MARKOV CHAINS TO DIFFUSION PROCESSES

• For any open set F ⊂ E, lim inf ν n (F ) ≥ µ(F );

• For any Borel set F ⊂ E such that µ(∂F ) = 0, ν n (F ) = µ(F ).
By extension, we say a family of random variables (X n ) n∈N converges weakly to Y if the measures of (X n ) n≥0 converges weakly to the measure of Y .

As we have seen, diffusion processes are continuous processes, so one may be tempted to obtain a convergence in the space of continuous trajectories of E. However, as we have seen with the example of Donsker's Theorem, an approximation built using a Markov chain is in general not continuous. Instead, given T > 0, we are going to work in the space of trajectories [0, T ] → R d that are right-continuous and have left limits. This space is called the Skorokhod space and is equipped with the following metric

d(f, g) = inf {∃λ ∈ Λ, λ ≤ , sup t≤T |f (t) -g(λ(t))| ≤ },
where Λ denotes the space of strictly increasing automorphisms of the unit segment [0, 1], and where λ is

λ = sup s =t log λ(t) -λ(s) t -s .
Consider a family of Markov chains (X s n ) n∈N,s≥0 defined on discrete state spaces E s ⊂ E with initial states X s 0 = x s and transition kernels K s . For x ∈ E s , γ > 0 and s > 0, let

• b s (x) = 1 s x ∈Es (x -x)K s (x, dx ); • a s (x) = 1 2s x ∈Es (x -x)(x -x) T K s (x, dx ); • ∆ γ s = 1 s K s (x, B(x, γ) c
), where B(x, γ) c is the complementary of the ball of radius γ centered in x.

Theorem 7 (Theorem 7.1 [START_REF] Durrett | Stochastic calculus : a practical introduction. Probability and stochastics series[END_REF] ). Suppose (X t ) t≥0 is a diffusion process on E ⊂ R d with X 0 = x 0 and generator L = b.∇+ < a, ∇ 2 > such that b and a are continuous on E. If,

(i) lim s→0 sup x∈Es b s -b ∞ = 0; (ii) lim s→0 sup x∈Es a s -a ∞ = 0; (iii) ∀γ > 0, lim s→0 sup x∈Es ∆ γ s = 0; CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS (iv) lim s→0 x s -x 0 ∞ = 0,
then, for any T > 0, the continuous time process (X s s t/s ) t≥0 converges weakly in D([0, T ], R d ) to (X t ) t≥0 . Furthermore, the convergence is uniform with respect to x 0 ∈ U .

This result tells us that, if the expected direction of a step of the Markov chain is close to b, its second moment is close to a and the length of the jump is small, then the trajectory of the Markov chain is close to the trajectory of the diffusion process. It is possible to relate these assumptions to a convergence of the generator of the Markov chain. Proposition 8. Suppose there exists R > 0 such that

∀s > 0, ∀x ∈ E s , x ∈Es, x -x ≥R K(x, dx ) = 0. If assumptions (i) -(iii) of Theorem 7 hold, then lim s→0 sup φ, ∇φ , ∇ 2 φ , ∇ 3 φ ≤1 sup x∈Es |( 1 s L s -L)φ(x)| → 0.
Proof. In order to simplify the notations, we prove the result in dimension one. Let φ be a smooth function with bounded first three derivatives. By Taylor's expansion we have, for any γ > 0,

1 s L s φ(x) = 1 s Es (φ(x ) -φ(x))K s (x, dx ) = 1 s Es φ (x)(x -x) + φ (x) (x -x) 2 2 + x x φ (3) (y) (y -x) 2 2 dy K s (x)(dx ).
Therefore,

1 s L s -L φ(x) = (b s -b)(x)φ (x) + (a s -a)(x)φ (x) + Es x x φ (3) (y) (y -x) 2 2 dyK s (x)(dx ).
Since φ has bounded derivatives, for any γ > 0,

1 s L s -L φ ≤ |b s -b| + |a s -a| + γ 3 6 + 4R 3 3 ∆ γ s . Therefore, if assumptions (i) -(iii) are verified, then lim s→0 sup x∈X 1 s L s -L φ(x) = 0.

FROM MARKOV CHAINS TO DIFFUSION PROCESSES

Invariant measure

We say a measure µ to be an invariant measure for a diffusion process associated to a semigroup (P t ) t≥0 with infinitesimal generator L if, for any function φ in C 0 and any t > 0,

E P t φdµ = E φµ.
Equivalently, for any φ ∈ D(L),

E Lφdµ = 0.
If this measure is finite, that is

E dµ < ∞,
then we assume it is a probability measure. An invariant measure is said to be reversible, if for any two functions φ, φ ∈ C 0 ,

E φP t φ dµ = E φ P t φdµ,
or for two compactly supported smooth functions φ, φ ,

E φLφ dµ = E φ Lφdµ.
According to Section 1.11.3 [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF], an absolutely continuous measure µ = hdλ is reversible for P t if and only if

b i = n j=1 ∂a i,j ∂x i + a i,j ∂ log h ∂x i . Furthermore, since 1 2 (L(φφ ) -φLφ -φ Lφ) =< ∇φ, a∇φ >,
if µ is reversible then it satisfies the following integration by parts formula

- E φLφ dµ = E 1 2 (L(φφ ) -φLφ -φ Lφ) = E < ∇φ, a∇φ > dµ.
When µ is reversible, it is after interesting to consider (P t ) t≥0 and L as operators acting on the Hilbert space L 2 (µ) in which case they are bounded and symmetric operators. This is going to be especially useful when studying the spectral properties of L.

CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS

Spectrum of the infinitesimal generator

As we have seen, many graph analysis algorithms use the spectrum of the graph Laplacian, and thus of the generator of the random walk on the graph. The convergence of the outputs of these algorithms can thus be obtained through the convergence of the spectra of generators of random walks on graphs. Should these random walks converge to diffusion processes, one may expect the spectra of the corresponding generators to converge to the spectra of infinitesimal generators of the limiting diffusion processes, should it exists. We say a bounded operator from a Banach space X to another Banach space Y is compact if the image of the unit ball of X is relatively compact in Y . Let L be the infinitesimal generator of a semigroup (P t ) t≥0 acting on a Hilbert space H. Theorem 9 (Theorem A.6.4 [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF]). If -L is positive and there exists t > 0 such that P t is a compact operator, then L has a discrete spectrum with eigenvalues

• • • ≤ λ n ≤ • • • ≤ λ 1 = 0. Moreover, λ n → n→∞ -∞.
Let us note that, although we are only going to deal with diffusion processes in R d , this results holds even if L and (P t ) t≥0 are defined as operators acting on functions defined on manifolds. In particular, if the manifold is compact, (P t ) t≥0 is compact as well. Hence, results dealing with convergence of graph Laplacians for random geometric graphs are usually obtained in a compact manifold setting.

Hitting times

Given F ⊂ E, let τ F = inf t≥0 (X t ∈ F ).
For the simplest case of diffusion process, the Brownian motion (W t ) t≥0 , we have the following result.

Proposition 10 (Corollary 2.26 [START_REF] Morters | Cambridge Series in Statistical and Probabilistic Mathematics[END_REF]). If d > 1, then for any T > 0 and

x ∈ R d , P(∃t ∈ (0, T ], W t = x) = 0.
Thus, in dimension greater than one, a Brownian motion does not hit any fixed point in finite time. Hence, we can expect this is going to be the case for general diffusion processes. This is a major difference with respect to random walks on graphs which always hit any given vertex of the graph in finite time.

Random geometric graphs

Let M be a p-dimensional manifold embedded in R d and let ν be a measure with support M and strictly positive smooth density f . Let X 1 , . . . , X n be i.i.d. random variables drawn from ν and let X n = {X 1 , . . . , X n } ∈ R d . Consider a function W Xn : R d → R + , a radius function r Xn : R d → R + and a bandwidth h n ∈ R + . Let K : R + → R + be a decreasing function, called kernel, such that

• K > 0; • R p K( x )dx = 1; • R p x 2 K( x )dx < ∞.
We call random geometric graph the graph G with vertices X n and weight function

∀x, x ∈ X , w(x, x ) = W Xn (x ) 1 h d n K x -x h n r Xn (x)
.

Random geometric graphs encompass many graphs used in data analysis such as the -graph, obtained by taking r Xn = W Xn = 1 and h n = . Taking k ∈ N, K = 1 [0,1] , W Xn = 1 and

h n r Xn (x) = inf(r ∈ R + | y∈Xn 1 y-x ≤r ≥ k),
we obtain a graph such that each point is linked to its k-nearest neighbors. Such a graph is called k-nearest neighbor graph and is a widely used type of graph as it is very sparse, however since this graph is directed, it is harder to analyze than -graphs.

Convergence of random walks on random geometric graphs

For simplicity, we will assume in this Section that points are not drawn from a manifold embedded in R d but rather from the flat torus T = (R/Z) d and we suppose random geometric graphs are built using the Riemaniann metric of T . As h n goes to zero and n goes to infinity, the length of the jumps of the random walks get smaller and smaller. Hence, if the first and second moments of the jumps also converge, the random walk itself should converge CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS to a diffusion process. Moreover, since the structure of the graph is going to be influenced by ν, it is reasonable to expect the limiting diffusion process to depend on ν as well. This dependency is made explicit by the following result.

Theorem 11 (Theorem 3 [START_REF] Ting | An analysis of the convergence of graph laplacians[END_REF]). Suppose h n → 0 and nh d+2 n log n → 0. Moreover, assume there exists deterministic smooth quantities W , r such that

sup x∈T sup ∈R d , ≤h(n) |W n (x + ) -W (x) -∇ W . | = o(h(n) 2 ); sup x∈T sup ∈R d , ≤h(n) |r n (x + ) -r(x) -∇r. | = o(h(n) 2 ).
Then, for any T > 0, the random walk on the random geometric graph converges weakly in D([0, T ]) to a diffusion process with generator

Lφ = r2 (∇ log(f W ).∇ + 1 2 ∆).
The approximation timestep is s = C h d+2 , where C is a constant depending on d and K.

For -graphs, the corresponding generator is simply L = ∇ log f.∇ + 1 2 ∆, so trajectories of (X t ) t≥0 are attracted by high density regions. This result is readily obtained using Taylor's expansion along with concentration inequalities and Theorem 7. As an example, we prove this result for the case of the k-nearest neighbor graph via the following Lemma, which will prove useful in Chapter 5.

Lemma 12. Let k > 0, and pose

s = k n 2/d x ≤1 x 2 1 dx x ≤1 1dx 1+2/d ; r = f -1/d .
For any x, x ∈ X , we pose

K n (x, x ) = w(x, x ) x w(x, x )
, where w is the w function corresponding to a k-nearest neighbor graph.

There exists a constant C such that, with probability

1 -C n , (i) sup x∈Xn 1 s x ∈Xn (x -x)K n (x, x )-f (x) -2/d ∇f (x) ≤ C( √ log nn 1/d k 1/2+1/d + k n 2/d ); (ii) sup x∈Xn 1 s x ∈Xn (x -x) T (x -x)K n (x, x )-f (x) -2/d I d ≤ C( logn k + k n 2/d ); (iii) sup x∈Xn 1 s x ∈Xn (x -x) ⊗3 K n (x, x ) ≤ C( √ log nk 1/d n 1/d k 1/2 + k n 2/d ); (iv) ∃n 0 , ∀n > n 0 , ∀x ∈ X n x ∈Xn, x-x ≥C( k n ) 1/d K n (x, x ) = 0. Proof. Let x ∈ T .
In the remainder of this proof, C denotes a generic constant depending only on d and f . For any r > 0, we denote by B(x, r) the ball centered in x with radius r. Let P r = B(x,r) µ(dx) and, for k > 0, we pose V k = B(0,1) x k 1 dx. Let N r be the number of points in B(x, r). For any 0 < < 1, Chernoff's bound yields

P (|N r -nP r | ≥ n P r ) ≤ 2e - 2 nPr 3 . (3.2)
Take

r M = 2k nV 0 min y∈T f (y) 1/d , we have P r M ≥ 2k n + C k n 1+2/d
. Hence, for k n sufficiently small, with probability greater than 1 -1 n 2 , N r M ≥ k. Thus the k-th nearest neighbor of x is at most at distance r M of x. Applying a union-bound, this is true for any x ∈ X n = {X 1 , . . . , X n } with probability 1 -1 n so we proved (iv). Let us now prove (i), we have

E[(X i -x)1 X i ∈B(x,r) ] = B(x,r) (y -x)µ(dy) = B(x,r) (y -x)f (y)dy = B(x,r) (y -x)f (x) + (y -x) ⊗2 ∇f (x) + (y -x) ⊗3 ∇ 2 f (x) 2 + Cr 4 dy = V 2 r d+2 ∇f (x) + Cr d+4 .
Therefore, letting b 1 = X i ∈B(x,r) X i -x and applying Bernstein's inequality,

P b 1 -nV 2 r d+2 ∇f (x) ≥ C r nP r log n + nr d+4 ≤ 2 n 2 . CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS Taking r = k nV 0 f (x) 1/d , we have |P r -k n | ≤ C k n 1+2/d . Hence, by Equa- tion 3.2, |N r -k| ≤ C( √ k log n + k 1+2/d n 2/d ) holds with probability 1 -1 n 2 . Thus, for b 2 = X i ∈B(x,r) X i -x, we have |b 1 -b 2 | ≤ Cr M k log n + k 1+2/d n 2/d .
Putting everything together, we have, with probability 1

-C n 2
1 ks

X i ∈B(x,r) (X i -x)-f -2/d ∇ log f = b 2 ks -f -2/d ∇ log f ≤ b 1 ks -f -2/d ∇ log f + C √ log nn 2/d k 1/2+2/d + 1 k ≤ C √ log nn 1/d k 1/2+1/d + k n 2/d
.

Using a union bound, we obtain the uniform convergence of 1 s

x ∈Xn (xx)K n (x, x ) over X n with probability 1 -C n 2 . Bounds (ii) and (iii) can be obtained in the same way.

Hitting times

By Proposition 10, we know that, in dimension greater than one, the Brownian motion does not hit fixed points in finite time and we cannot expect diffusion processes to do otherwise. Hence, while random walks on random geometric graphs converge to diffusion processes, there are no continuous quantities we can expect hitting times and commute distances to converge to. Therefore, the limiting behaviour of these quantities might not be of interest. In [START_REF] Ulrike Von Luxburg | Hitting and commute times in large random neighborhood graphs[END_REF], it is proved the mean hitting time between two vertices x and x of a random geometric graph converges to a quantity depending on the local structure of the graph around x alone. Hence, hitting times fail to describe the general structure of large random geometric graphs. Different ways to correct this issue for the commute distance have been proposed, see for example the amplified commute distance [START_REF] Ulrike Von Luxburg | Hitting and commute times in large random neighborhood graphs[END_REF].

Invariant measure

Suppose a family of random walks converge to a diffusion process admitting a unique invariant probability measure µ. Can we expect the invariant measures of the random walks to converge to µ?

Let us start with an -graph. Random walks on such random geometric graphs converge to diffusion processes with infinitesimal generator L = ∇ log f.∇ + ∆ 2 . This generator has an invariant probability measure µ with a density proportional to f 2 . By Proposition 4, the invariant measure of a connected and undirected graph is proportional to its degree function. An -graph being undirected, the invariant measure π of a random walk on such a graph is

∀x ∈ X , π(x) = d(x) V ol(X ) = n i=1 K( X i -x hn ) n i,j=1 K( X i -X j hn ) .
Actually, π is proportional to the value of a standard kernel density estimator.

Proposition 13. Suppose the density f is supported on the flat torus T and has bounded second derivative. Then there exists C > 0 such that, with probability 1 -ne

n 2 2h d n , sup x∈X n i=1 1 h d n K X i -x h n -f (x) ≤ + Ch 2 n .
Proof. Let x ∈ T and let X be a random variable drawn from ν. Since T is compact and f is smooth, its second derivative is bounded. Thus, Taylor's expansion yields

E 1 h d n K X i -x h n = T 1 h d n K x -x h n f (x )dx = T 1 h d n K x -x h n (f (x) + (x -x).∇f (x) + O( x -x 2 ))dx .
By our assumptions on the kernel K, we thus have

E K X i -x h n = f (x) + O(h 2 n ).
Therefore, by Hoeffding's inequality, we have, with probability 1 -e

n 2 2h d n , n i=1 K X i -x h n -f (x) ≤ + O(h 2 n ).

CHAPTER 3. RANDOM WALKS ON RANDOM GEOMETRIC GRAPHS

We then conclude the proof using the union bound inequality on all x ∈ X n .

Hence, as long as h n → 0 and n log n h d n → ∞, there exists

C > 0 such that lim n→∞ sup x∈Xn |π(x) -C f (x) n | = 0. Hence, for any open set A of E, π(A) ≈ C x∈Xn∩A f (x) n ≈ C A f (x)dµ ≈ C A f 2 (x)dx.
Therefore, π converges to µ. While this gives an idea regarding why algorithms relying on invariant measures of random walks on such graphs actually work well in practice, it also guarantees these random geometric graphs do retain most of the information contained in the input data since it is possible to recover f , and thus ν, from the sole graph structure.

One may now wonder whether a similar result holds for directed random geometric graphs such as the k-nearest neighbor graph. By Theorem 11, the random walk on a k-nearest neighbor graph converges to a diffusion process with infinitesimal generator L = f -2/d ∇ log f.∇ + ∆ 2 . This diffusion process admits an invariant measure µ with density proportional to f 1+2/d . In [START_REF] Tatsunori | Metric recovery from directed unweighted graphs[END_REF], the authors prove the weak convergence of the invariant measures of random walks on random geometric graphs. Applying this result to knearest neighbor graphs, we obtain that π converges weakly to µ as long as k d+2

(n log(n)) 2 → ∞. Moreover, it is conjectured that, similarly to the undirected case, the convergence holds as long as k log n → ∞ and is pointwise.

Chapter 4

Soft-clustering

In this Chapter, we propose a new soft clustering algorithm based on the mode seeking algorithm ToMATo [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF] which relies on hitting times of random walks on random geometric graphs. As we have seen in Section 3.1.2, we cannot expect consistency of hitting times to fixed points. We solve this issue by using hitting times to a set rather than hitting times to a point, allowing us to prove the consistency of our algorithm. We finally provide some experimental results for our algorithm on both synthetic and real data. This work was done in collaboration with Steve Oudot. We thank Cecilia Clementi for providing the Alanine dipeptide dataset.

Mode-seeking

Let us assume the data points X n = {X 1 , . . . , X n } are i.i.d. random variables drawn from a measure ν with smooth density f . We assume f is a Morse function, i.e. f is a smooth function with non-degenerate critical points such that all the critical values are distinct, with a finite number of critical points. For x ∈ R d , we define the gradient flow induced by f with initial state x dy x (t) = ∇f (u(t))

y x (0) = x . (4.1)
Let v 1 , . . . , v m be the set of local maxima of f , the sets (M i ) i∈{1,...,m} defined by ∀i ∈ {1, . . . , m},

M i = {x ∈ R d | lim t→∞ y x = v i },
are called modes of f . These modes define a partition of R d \U , where U is a set of measure zero containing points whose gradient flow lead to 37 saddle points. The mode-seeking approach consists in associating clusters to modes of f . Of course, since we do not have access to the density f itself, we do not have access to its modes either. A simple way to turn this framework into a clustering algorithm would consist in computing a density estimator f and define clusters as the modes of f . However, modes of f do not necessarily correspond to modes of f . Mode seeking algorithms such as [START_REF] Chen | A Comprehensive Approach to Mode Clustering[END_REF][START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF][START_REF] Cheng | Mean shift, mode seeking, and clustering[END_REF][START_REF] Cho | Authority-shift clustering: Hierarchical clustering by authority seeking on graphs[END_REF][START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF][START_REF] Koontz | A graph-theoretic approach to nonparametric cluster analysis[END_REF] aim at recovering the modes of f from f to perform clustering. From a statistical point of view, the analysis of mode inference was developed recently in [START_REF] Chen | Nonparametric Modal Regression[END_REF][START_REF] Azizyan | Risk Bounds For Mode Clustering[END_REF][START_REF] Chen | Density Level Sets: Asymptotics, Inference, and Visualization[END_REF][START_REF] Chen | Statistical Inference using the Morse-Smale Complex[END_REF]. Let us present one of these mode seeking algorithms: the Topological Mode Analysis Tool (ToMATo) algorithm [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF].

ToMATo

The ToMATo algorithm relies on the concept of 0-dimensional persistent homology, which we present below, in order to estimate the modes of f . 4.1.2 0-dimensional persistent homology of the superlevel sets of a function 0-dimensional persistent homology was introduced in the context of Topological Data Analysis under the name size theory [START_REF] Verri | On the use of size functions for shape analysis[END_REF] and was later generalized by the persistent homology theory (see [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF][START_REF] Zomorodian | Computing persistent homology[END_REF] for more details). Here we are interested in the 0-dimensional persistent homology of the superlevel sets of a function, also called prominence.

Let G be an unweighted graph with vertices V and edges E, and suppose there exists an ordering on V . Consider a function φ : V → R. For any α ∈ R, we define the superlevel sets of φ by

V α = {x ∈ V | φ(x) ≥ α}.
For any x ∈ G, we denote by V x α the connected component containing x in the subgraph G α with vertices V α and edges E α such that

∀x, x ∈ V α , (x, x ) ∈ E α ⇐⇒ (x, x ) ∈ E.
Let b φ (x) be the highest α such that x ∈ V α (i.e. φ(x)). For α < b φ (x), we use the ordering on V to define

D α,x := max{x ∈ V x α | φ(x ) ≥ φ(x)}.

MODE-SEEKING

39

We define d φ (x) as the highest α such that D α,x = x and we pose D φ,x = D d φ (x),x . The prominence p φ (x) of x with respect to φ is then defined as b φ (x) -d φ (x). If a vertex x is not a local maximum of φ on the graph, i.e.

∃x ∈ V, φ(x) > φ(x),
then it has a prominence equal to zero. Replacing G by R d , it is possible to define a similar notion of prominence in the continuous domain.

The prominence information is usually encoded as a collection of points in the plane with coordinate (b φ (x), d φ (x)) called persistence diagram. These diagrams are endowed with a natural metric called the bottleneck distance involving the notion of partial matching. A partial matching M between two diagrams ∆ 1 and ∆ 2 is a subset of ∆ 1 × ∆ 2 such that each point of ∆ 1 and ∆ 2 appears at most once in M . The bottleneck cost C(M ) of a partial matching M between two diagrams ∆ 1 and ∆ 2 is the infimum of δ ≥ 0 such that

• For any (p 1 , p 2 ) ∈ M , ||p 1 -p 2 || ∞ ≤ δ; • For any other point (b, d) of ∆ 1 or ∆ 2 , b -d ≤ 2δ.
The bottleneck distance between two diagrams D 1 and D 2 , is then defined as

d B (∆ 1 , ∆ 2 ) = inf δ {δ | ∃M, C(M ) ≤ δ}
Intuitively, the bottleneck distance can be seen as the cost of a minimum perfect matching between persistence diagrams with possibility to match points to the diagonal y = x. A remarkable property of persistence diagrams is their stability, proved in [START_REF] Cohen-Steiner | Stability of persistence diagrams[END_REF] and [START_REF] Chazal | The structure and stability of persistence modules[END_REF]. Let φ and φ be two functions defined on the vertices of the same graph and ∆ φ , ∆ φ be the persistence diagrams of the superlevel-sets of φ and φ , applying these stability results, we obtain the following

d B (∆ φ , ∆ φ ) ≤ ||φ -φ || ∞ = sup x∈V |φ(x) -φ (x)| (4.2)
Computation As 0-dimensional persistence encodes the evolution of the connectivity of the superlevel-sets of a function, it can be computed using a simple variant of a Union-find algorithm. In practice, we use Algorithm 1 described in [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF], with parameter τ set to infinity. This algorithm has close to linear complexity in the number of vertices of the meshes; more precisely it has complexity

O(|V | log(|V |) + |V |α(|V |))
where α is the inverse of the Ackermann function.

The Algorithm

The algorithm starts by computing an unweighted graph with vertices X n , while it is not mandatory, the graph is usually either an -graph with kernel K = 1 [0,1] or a k-nearest neighbors graph. We then compute the values of a density estimator f on X n . In order to pinpoint local maxima of f which correspond to local maxima of f , we use the prominence of the vertices of the graph with respect to the function f . In this case, the higher the prominence of a local maximum, the more likely it is to correspond to an actual maximum of the underlying density f and thus to indicate a mode of f . Given a prominence threshold τ > 0, we pose

∆ τ (x) = x if p f (x) > τ or x = D f ,x ∆ τ (D f ,x ) otherwise.
If v 1 , . . . , v K denote the vertices of G with prominences higher than τ , the algorithm outputs

K clusters C 1 , . . . , C K where ∀i ∈ {1, . . . , K}, C i = {x ∈ X n | ∆ τ (x) = v i }.
Moreover, if f (v i ) ≤ τ , then the points belonging to C i are considered as outliers. Upon a proper choice of τ with respect to n and as long as the density estimator converges, this clustering procedure can be shown to be consistent [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF].

Soft clustering

A natural way to turn the mode seeking approach into a soft-clustering algorithm is to add some randomness in Equation 4.1. Here, we use the following stochastic differential equation

dY t = 1 β ∇(log f )dt + dW t ,
where W t is a d-dimensional Brownian motion and β is a strictly positive temperature parameter controlling the amount of noise introduced in the gradient flow. If it exists, the solution to this stochastic differential equation is a diffusion process with generator

L = 1 β ∇(log f ).∇ + 1 2 ∆.
Fortunately, by Theorem 11, this diffusion process can be approximated by a random walk on the (properly weighted) random geometric graph used by ToMATo. From here, one possibility would be to consider the first local maximum of the density encountered by the random walk. When β = 1, such an approach can be compared to the soft clustering procedure proposed in [START_REF] Chen | A Comprehensive Approach to Mode Clustering[END_REF]. In this work, the authors use a statistical method to select relevant local maxima of f in R d denoted m 1 , . . . , m K . Then, they build an -graph with vertices X n ∪{m 1 , . . . , m K } and consider the first local maximum m i hit by the random walk on the graph. However, as emphasized in Section 3.3.2, we cannot expect consistency regarding the amount of time required to hit a given point in the random geometric graph. Thus, if we apply this method to a dataset consisting in two unbalanced Gaussian measures in Figure 4.1, the obtained soft memberships are definitely wrong. In order to circumvent this issue, we assign a zone of high density to each cluster, called cluster core and computed using ToMATo, and we look at the first cluster core encountered by the random walk.

Our Algorithm

The input of the algorithm is a finite set of points X n = {X 1 , • • • , X n }, a radius > 0 -or an integer k if one wants to use a nearest neighbors graph-, a density estimator f , a prominence threshold τ > 0 and a temperature parameter β > 0.

CHAPTER 4. SOFT-CLUSTERING

Our algorithm then proceeds as follows. It first computes an -graph (or a k-nearest neighbors graph) G from X n then runs the ToMATo algorithm using G. The output of ToMATo is a set of K clusters C 1 , • • • , C K each corresponding to a local maximum of f on the graph denoted by x 1 , . . . x K . We define the i-th cluster core as the connected component containing X i within the subgraph of G spanned by those vertices x such that f (x ) > f (x i ) -τ /2, in other words, the i-the cluster core is equal to

F x i f (x i )-τ /2
. We then compute a random geometric graph G with the same parameters used to compute G except for

W Xn (x) = f (x) 1/β-1 . (4.3)
Finally, we compute the soft-membership values µ 1 , . . . , µ K by solving the linear system A T µ = µ, where the matrix A is defined by:

A kl = δ kl if ∃i, X k ∈ C i,n K G(X k , X l ) otherwise,
where K G is the transition kernel of the random walk on the graph G. The output of the algorithm is the set of those soft-membership values.

Parameters selection

Density estimator, window size, kernel and prominence threshold

These four parameters are tied to the classical mode-seeking framework. The density estimator can be linked to the window size in practice, for instance by using a density kernel estimator, as is done e.g. in Mean-Shift [START_REF] Cheng | Mean shift, mode seeking, and clustering[END_REF] and its successors. This not only reduces the number of parameters to tune in practice, but it also gives a way to select the window size -or k-using standard parameter selection techniques for density estimation, which is done for example in [START_REF] Chen | A Comprehensive Approach to Mode Clustering[END_REF]. Finally, the prominence threshold τ can be selected by running ToMATo with prominence threshold equal to 0 in order to obtain the distribution of prominences of the vertices within the neighborhood graph G. An adequate value of τ can then be inferred by looking for a gap in the distribution. This procedure is detailed in [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF].

Temperature parameter

As for temperature or fuzziness parameters in other soft clustering algorithms, it is not clear how β should be selected. Outputs corresponding to large values of β will tend to have smooth interfaces between clusters while small values of β will encourage quick transitions from one cluster to another. β can also be interpreted as a trade-off between the respective influences of the Euclidean metric and of the density: when β is small, the output of our algorithm is mostly guided by the density and therefore close to the output of the hard mode seeking algorithm; by contrast, when β is large, the definition of the cluster cores is the only influence of the density on the output of the algorithm. In practice, one may get insights into the choice of β by looking at the evolution of a certain measure of fuzziness for the clustering output across a range of values of β. We elaborate on this in Section 4.4.

Convergence guarantees

In this Section we provide theoretical guarantees for our soft-clustering scheme by exploiting the convergence of random walks on random geometric graphs to diffusion processes.

As usual in mode-seeking, we assume our input data points X n = {X 1 , ..., X n } to be i.i.d. random variables drawn from some unknown probability density f over R d . We also assume that f and ∇ log f are smooth and Lipschitz continuous over R d . This condition is sufficient to ensure the existence of a diffusion process (X t ) t≥0 , with X 0 = x ∈ R d , associated to the infinitesimal generator

L = 1 β ∇ log f.∇ + 1 2 ∆.
Let us assume the unweighted graph G used by our algorithm is angraph. For x ∈ X n , let M x, be the random walk on the weighted graph G whose initial state is the closest neighbors of x in X n (break ties arbitrarily). The weighting we use to create G trajectories was designed such that M x, converges weakly to (X t ) t≥0 . From here, convergence of the cluster cores to continuous sets is sufficient to prove the consistency of the algorithm. Formally, letting v 1 , . . . , v K be the local maxima of f with prominence higher than τ , we can define the limit cluster cores as ∀i ∈ {1, . . . , K}, Ci = F v i τ /2 , and we define μi (x) as the probability for the diffusion process with generator L started at x to hit Ci before any other Cj .

In order to obtain a consistency result for our algorithm, we require these continuous cluster cores to satisfy some assumptions. For any C ⊂ R d and CHAPTER 4. SOFT-CLUSTERING any δ > 0, let us pose

C δ = {x ∈ R d | ∃y ∈ C, x -y ≤ δ}.
Assumption 14. The boundary of the Ci are smooth. Moreover, for any δ > 0 there exist δ > 0 such that

F v i τ /2+δ ⊂ (F v i τ /2 ) δ = Cδ i ,
and

F v i τ /2 = Ci ⊂ (F v i τ /2-δ ) δ . Theorem 15.
Let β > 0, τ > 0 and suppose the cluster cores verify Assumption 14. Let : N → R + be a decreasing window size such that lim

x∈U sup h∈R d , h ≤ (n) | f 1/β-1 n (x+h)-(f 1/β-1 (x)+∇f 1/β-1 .h)| ≥ (n) 2 η) = 0.
Almost surely, there exists n 0 such that, for n ≥ n 0 , the number of clusters output by ToMATo is equal to K. Let (µ n,i ) n≥n 0 ,i∈{1,...,K} be the output of our algorithm. There exists a family of permutation (π n ) n≥n 0 such that, for any compact set U ⊂ R d , any η > 0 and any i ∈ {1, . . . , K},

lim n→∞ P sup x∈U |μ i (x) -µ n,πn(i) (x)| ≥ η = 0.
When the input graph is a k-nearest neighbors graph, the trajectories of the random walk converge to a diffusion process (X t ) t≥0 with generator

L = f -2/d ( 1 β ∇ log f.∇ + 1 2 ∆).
Since trajectories of (X t ) t≥0 correspond, up to a time-change, to trajectories of (X t ) t≥0 , a similar result can be obtained.

Experiments

We first illustrate the effect of the temperature parameter β on the clustering output using synthetic data. We then apply our method on three UCI repository datasets and on simulated protein conformations data. In all our experiments we use a k-nearest neighbors graph along with a distance to measure density estimator [11] computed using the k-nearest neighbors.

Synthetic data

The first dataset is presented in Figure 4.2a and is composed of two highdensity clusters connected by two links. The bottom link is sampled from a uniform density while the top link is sampled from a density that has a gap in-between the two clusters. Standard mode seeking algorithms will have a hard time clustering the bottom link as the separation between the two modes of f is extremely smooth. Thus, ToMATo missclusters most of the bottom link (see Figure 4.2b). We display the results of our algorithm for three values of β : β = 0.2 in Figure 4.2c, β = 1 in Figure 4.2d and β = 2 in Figure 4.2e. As we can see from the output of the algorithm, for small values of β, the temperature parameter is not large enough to compensate for the influence of the noise in the density estimation: the result obtained is really close to hard clustering. Large values of β do not give enough weight to the density function which leads to a smooth transition between the two clusters on the top link despite the density gap. Intermediate values of β seem to give more satisfying results. In order to gain intuition regarding which value of β one should use, it is possible to look at the evolution of a fuzziness value for the clustering. For example, one can consider a notion of clustering entropy:

H = i j µ j (X i ) log(µ j (X i )), (4.4)
which gets lower when the fuzziness of the clustering increases. As we can see in Figure 4.2f, the evolution of H with respect to β presents three distinct plateaus corresponding to the three behaviours highlighted earlier.

The second dataset we consider is composed of two interleaved spiralssee Figure 4.3. An interesting property of this dataset is that the head of each spiral is close -in Euclidean distance-to the tail of the other spiral. Thus, the two clusters are well-separated by a density gap but are close in terms of Euclidean metric. We use our algorithm with two different values of β: β = 1 and β = 0.3, we also run a spectral fuzzy C-means algorithm on a subsampling of this dataset. The first thing we want to emphasize is that the output result of spectral C-means and our algorithm using β = 1 are similar, this is to be expected as both algorithms rely on the properties of the same diffusion operator. On the other hand, giving more weight to the structure of the density by setting β 0.3, we correctly recover the two clusters.

UCI datasets

In order to perform a quantitative evaluation of our soft clustering scheme, we evaluate it in a classification scenario on a few datasets from the UCI repository: the Pendigits dataset (10, 000 points and 10 classes), the Waveset dataset (5, 000 points and 3 classes) and the Landsite Satellite dataset (6, 435 points and 7 classes). We preprocess each dataset by renormalizing the various coordinates so they have unit variance. Then, for each dataset, we run our algorithm with various values of the parameter β between 0.1 and 5, but a single value of k. We select the prominence threshold τ using a prominence gap. Since there are two possible prominence gaps for the Pendigits and the Landsite Satellite datasets, we run the experiments twice using both thresholds and indicate the corresponding number of clusters K in our results. As a baseline, we use the fuzzy C-means algorithm with fuzziness parameters between 1.2 and 5 using the same number of clusters as detected by the ToMATo algorithm. We also consider the soft clustering algorithm proposed by [START_REF] Chen | A Comprehensive Approach to Mode Clustering[END_REF], for which the cluster cores are reduced to a single point and β = 1. Let X 1 , . . . , X n denote our sample points and Y 1 , . . . , Y n their respective labels taking values in {1, . . . , K }.

We propose an automatic selection of β by computing the values of the clustering entropy H for multiple values of β and by selecting

β = arg max dH dβ ,
in other words we take β maximizing the slope of H. In order to evaluate hard clustering algorithms, it is common to use the purity measure defined by

P = max π 1 n n i=1 K j=1 1 µ j (X i )=1 1 Y i =π(j) ,
where π is a map from the set of clusters {1, . . . , K} to the set of labels {1, . . . , K }. As this measure is not adapted to soft clustering, we consider instead a quantity we call -entropic purity and defined by

HP = max π 1 n i log   + j,π(j)=Y i μj (X i )   ,
for some > 0. The parameter is used to prevent the quantity from exploding due to possible outliers. This quantity can be viewed as an approximation of E[log( + j,π(j)=Y µ j (X))], for X a random variable drawn from a CHAPTER 4. SOFT-CLUSTERING Algorithm/Data(K) Wave( 3) Pend( 9) Pend( 13) Sat( 5) Sat( 9) Ours, optimal β -0.

f ∈R d →R K , f 1 =1 E[log( + f (X))] = (1 -) -1 (P(Y = j | X)) 1≤j≤K -.
Thus, for small values of , a soft clustering minimizing the -entropic purity recovers the conditional probabilities of the labels of the data points with respect to their coordinates. Hence, this extension of the traditional purity can be useful to evaluate soft clustering We provide the best 0.1-entropic purity obtained by each algorithm on all datasets in Table 4.1.

Alanine-dipeptide conformations. We now turn to the problem of clustering protein conformations. We consider the case of the alaninedipeptide molecule. Our dataset is composed of 1, 420, 738 protein conformations, each one represented as a 30-dimensional vector. The metric used on this type of data is the root-mean-squared deviation (RMSD). The goal of soft clustering in this case is twofold: first, to find the right number of clusters corresponding to metastable states of the molecule; second, to find the conformations lying at the border between different clusters, as these represent the transition phases between metastable states. It is well-known that conformations of alanine-dipeptide only have two relevant degrees of freedom, so it is possible to project the data down to two dimensions (called a Ramachadran plot) to have a comfortable view of the clustering output. In order to highlight interfaces between clusters, we only display the second highest membership function. As we can see in Figure 4.4 there are 5 clusters and 6 to 7 interfaces.

x∈U sup h∈R d , h ≤ (n) | f 1/β-1 n (x+h)-(f 1/β-1 (x)+∇f 1/β-1 .h)| ≥ (n) 2 η) = 0.
Then, for any T, η > 0, for any compact set U ⊂ R d , and for any Borel set B of D([0, T ], R d ) such that P(Y y ∈ ∂B) = 0 for all y ∈ U , there exists s(n) > 0 such that

lim n→∞ P(sup x∈U |P(M x,n s(n) t/s(n) ∈ B) -P(Y x t ∈ B)| ≥ η) = 0.
The proof relies on Theorem 11 along with a proper control of boundary effects.

Let X n = (X 1 , ..., X n ) and let

F α = {x ∈ R d | f (x)
≥ α} be the α superlevel-set of f . Throughout the course of the proof, the notation M x, stands for the continuous time process M x, s t/s . Let T and η be strictly positive reals.

For α > 0, F α is closed as f is continuous. Moreover, since f is Lipschitz continuous, lim x 2 →∞ f (x) = 0. Hence, F α is also bounded and thus 50 CHAPTER 4. SOFT-CLUSTERING compact. Following the proof of Theorem 11, there exists s(n) > 0 such that

(i) lim n→∞ P(sup y∈Xn∩Fα |b s -∇f βf | ≤ ν) = 0, (ii) lim n→∞ P(sup y∈Xn∩Fα |a s -I d 2 | ≤ ν) = 0, (iii) sup y∈Xn ∆ s = 0, (iv) lim n→∞ P( M x, 0 -x ≤ ν) = 0.
Thus, the assumptions (i)-(iv) of Theorem 7 are verified on F α which implies that M x,n approximates correctly Y x as long as it does not leave F α . More precisely, for α > 0, let

B α = {w ∈ D([0, T ], R d ) | ∀t, w(t) ∈ F α }.
Since ∇ log f is Lipschitz continuous, there exists α > 0 such that, for any x ∈ U , P(Y x ∈ B α ) ≥ 1 -η/4 (i.e. (Y x t ) t≥0 does not explode in finite time [START_REF] Durrett | Stochastic calculus : a practical introduction. Probability and stochastics series[END_REF]). Since f is continuous, B α is an open set. Therefore, there exists n 0 > 0 such that, for any n > n 0 , using Theorem 7 along with Theorem 6,

sup x∈U P(M x,n ∈ B α ) ≥ sup x∈U P(Y x ∈ B α ) -η/4 ≥ 1 -η/2.
Therefore, for any Borel set B,

sup x∈U |P(M x,n ∈ B) -P(M x,n ∈ B ∩ B α )| ≤ η/2.
Thus, we only need to approximate trajectories that do not leave F α to obtain a good approximation of P(M x,n ∈ B). Applying Theorem 7 and Theorem 6 on these trajectories, we obtain

sup x∈U |P(M x,n ∈ B) -P(Y x ∈ B)| ≤ η.
Every step of the proof hold with high probability as n tends to infinity, so the proof of Proposition 16 is complete.

Proof of Theorem 15

Since f is C 1 -continuous, the Ci are compact sets of R d and are disjoint sets. Let β and τ be strictly positive real numbers, U ⊂ R d be a compact set and i ∈ {1, . . . , K}. Let B(x, r) denotes the ball of radius r > 0 centered on x ∈ R d . For δ > 0, we pose Cδ

i = ∪ x∈ Ci B(x, δ) and C-δ i = Ci \ ∪ x / ∈ Ci B(x, δ).
Let η be a strictly positive real and, for x ∈ R d ,

PROOFS

51

• µ + i,δ (x) be the probability that Y x hits Cδ i before any other C-δ j ;

• µ - i,δ (x) be the probability that Y x hits C-δ i before any other Cδ j .

Let us show that, for any i, a trajectory entering Cδ i has a high probability to enter Ci if δ is small enough. Since the Ci are closed and disjoint there exists δ 0 > 0 such that the Cδ 0 i are disjoints. Moreover, since the Ci have smooth boundaries, there exists δ + i > 0 such that if d(x, Ci ) ≤ δ + i then, the probability for Y x to hit Ci before exiting Cδ 0 i is at least 1-η/8. Similarly, if a trajectory of Y x enters Ci , then it enters C-δ i with high probability. More precisely there exists δ - i such that if a trajectory of Y x hits Ci , then it hits C-δ i with probability at least 1 -η/8. Let δ = min(δ + j , δ - j ), since Y x satisfies the strong Markov property, we have

• µ + i,δ (x) -µ i (x) ≤ η/4, • µ i (x) -µ - i,δ (x) ≤ η/4
. The next step is to show that the approximation of µ + i,δ provided by the Markov chain is correct. For T > 0, let

B = {w ∈ D([0, ∞], R d ) | ∃τ such that w(τ ) ∈ Cδ i and ∀t < τ, w(t) ∈ R d \ ∪ j C-δ j }, B T = {w ∈ D([0, T ], R d ) | ∃τ such that w(τ ) ∈ Cδ i and ∀t < τ, w(t) ∈ R d \ ∪ j C-δ j }. We define the stopping time τ (Y ) = inf t Y ∈ Cδ i ∪ j∈{1,...,K},j =i C-δ j .
Since C i ⊂ R d and R d has a single connected component, we have that

P(τ (Y x t ) < ∞) = 1
, in particular that means that there exists T 0 such that, for any T ≥ T 0 , P(τ (Y x ) ≤ T ) ≥ 1 -η/6. Using Proposition 16, we have that, with high probability with respect to X n ,

P(τ (M x,n ) ≤ T ) ≥ P(τ (Y x ) ≤ T ) -η/6 ≥ 1 - 1 3
η.

Hence, we have

P(M x,n ∈ B \ B T ) + P(Y x ∈ B \ B T ) ≤ P(τ (M x,n ) > T ) + P(τ (Y x ) > T ) ≤ η/2.
Since P(Y x ∈ ∂B T ) = P(Y x ∈ ∂B) = 0, we can apply Proposition 16 on the set B T , and obtain

sup x∈U |P(M x,n ∈ B T ) -P(Y x ∈ B T )| ≤ η/4.
Combined with our previous result, we obtain:

sup x∈U |P(M x,n ∈ B) -P(Y x ∈ B)| ≤ 3η/4.
Let C 1 , . . . , C K(n) be the cluster cores used by the algorithm and computed with the density estimator f . These cluster cores are approximations of the sets C1 , . . . , CK obtained using the same computation with the true density f . By our assumptions on the convergence of f , Theorems 9.2 and 11.1 [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF] guarantee lim n→∞ K(n) = K almost surely. Hence, we can assume that n is sufficiently large for K(n) to be equal to K. By our assumptions on the cluster cores and the convergence of f , Theorem 10.1 [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF] guarantees there exists π such that, almost surely,

∀δ > 0, ∀i ∈ {1, . . . , K}, lim n→∞ P( C-δ i ⊂ C π(i) ⊂ Cδ i ) = 1. (4.5)
Without loss of generality, we can assume π(i) = i. Hence, P(M x,n ∈ B) ≥ lim n→∞ µ n,i (x) and

lim n→∞ µ n,i (x) -µ i (x) ≤ lim n→∞ µ n,i (x) -µ + i,δ (x) + η/4 ≤ η.
Similarly,

µ i (x) -lim n→∞ µ n,i (x) ≤ η,
concluding the proof.

Chapter 5

Stein's method for diffusion approximation

At the end of Section 3.3.3, we have seen it is possible to obtain the weak convergence of the invariant measure of random walks on random geometric graphs to the invariant measure of the limiting diffusion process. In this Section, we improve this result by quantifying this convergence in terms of Wasserstein distance of order 2 (Proposition 28). In order to obtain this bound, we adapt the approach of [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF] which relies on Stein's method and derive new ways to bound Wasserstein distances between measures (Theorems 18, 21 and 23). We then deal with possible applications of our results. We first obtain convergence rates for the Central Limit Theorem (Theorem 25). Then, we bound the distance between the invariant measures of a random walk and of a diffusion process. This bound can be used to solve our initial problem and to quantify the convergence of the invariant measure of a random walk on a random geometric graph. To illustrate this result, we tackle the case of the k-nearest neighbor graph (Proposition 28). Finally, we show how our bound can also be used to study the complexity of a simple Monte Carlo algorithm (Proposition 29).

An introduction to Stein's method

Stein's method corresponds to a family of approaches used to bound distances between measures. It was introduced by Charles Stein in 1972 [START_REF] Stein | A bound for the error in the normal approximation to the distribution of a sum of dependent random variables[END_REF] to bound the distance to the Gaussian measure γ. His approach relied on the following idea: since the Gaussian measure is the only measure such we can expect that if a measure ν satisfies

(xφ(x) -∇φ) ν(dx) ≈ 0,
then ν should be close to γ.

Barbour [START_REF] Barbour | Stein's method for diffusion approximations[END_REF] generalized this idea by replacing the Gaussian measure by a measure µ assumed to be the invariant measure of a diffusion process with infinitesimal generator L µ = b.∇+ < a, ∇ 2 >. Indeed, for any suitable function φ,

L µ φµ(dx) = 0.
In the case of the Gaussian measure the corresponding generator is L γ = -x.∇ + ∆, hence this equation generalizes Stein's identity by replacing φ by ∇φ. Thus, if a measure ν satisfies L µ φν(dx) ≈ 0, for φ belonging to some set of functional, we can expect ν to be close to µ. In order to show that such a condition holds there are two possibilities. The first one is to "solve the Stein's Equation" by computing L µ φ. But this approach is not always feasible, in particular in the multi-dimensional setting. Instead, let us assume that there exists L ν such that L ν φν(dx) = 0, in which case we say ν is invariant under L ν . Then, for any compactly supported smooth function φ,

L µ φν(dx) = (L µ -L ν )φν(dx).
Thus if L ν is close to L µ , then L µ φν(dx) should be close to zero and ν should be close to µ.

In our case, deriving such an operator is rather straightforward: if ν is the invariant measure of a Markov chain with generator L ν then ν is invariant under L ν . Using this type of operators in Stein's method can be

DISTANCES AND DIVERGENCES BETWEEN MEASURES

55 related to approach of [START_REF] Röllin | A note on the exchangeability condition in steins method[END_REF] in which the author uses the a pair (X, X ) of random variables drawn from ν as such a pair of variable corresponds to using a Markov chain with transition kernel defined by

∀x ∈ E, ∀F ⊂ F, K(x, F ) = E[X ∈ F |X = x].
Let us note there are many other ways to obtain an operator L ν under which ν is invariant such as the original method of exchangeable pairs [START_REF] Stein | Approximate computation of expectations[END_REF], biasing techniques [START_REF] Baldi | On normal approximations of distributions in terms of dependency graphs[END_REF][START_REF] Goldstein | Stein's method and the zero bias transformation with application to simple random sampling[END_REF] or the Stein kernel [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF]. For a more complete presentation of Stein's method and results obtained using this framework, we invite the reader to consult the following survey [START_REF] Chatterjee | A short survey of Stein's method[END_REF].

Distances and divergences between measures

So far, we have only been interested into weak convergence of measures. Unfortunately, since this convergence is not associated to a distance, it cannot be quantified. Let us browse through potential candidates distances we could use to quantify the convergence between measures. Let µ and ν be two measures defined on a domain E of R d and let B denotes the class of Borel sets of R d . A classical distance between µ and ν is the total variation distance:

T V (µ, ν) = max B |µ(B) -ν(B)| = sup φ ∞≤1 | E φdµ - R d φdν|.
If dν = hdµ, one can also use the relative entropy of ν with respect to µ, also called Kullback-Lieber divergence,

H(ν|µ) = E h log hdµ.
Whenever h is smooth, one can also use the Fisher information of ν with respect to µ

I(ν|µ) = E ∇h 2 h dµ.
Unfortunately, these quantities are not appropriate for our task. Indeed, if the total variation distance between a discrete measure and an absolutely continuous measure is always one (the maximum is obtained by taking B to be the support of the discrete measure). Similarly, the relative entropy and Fisher information of a discrete measure with respect to a continuous one is not defined. Instead, we are going to focus on another family of distances called Wasserstein distances. Let µ and ν be two measures on E, a measure π on E × E is a transport plan between ν and µ if π(., E) = µ(.) and π(E, .) = ν(.). For any p > 0, we say a measure µ has finite p-th moment if E x p µ(dx) < ∞ . Let p ≥ 1 and suppose µ and ν have finite p-th moment, the p-Wasserstein distance between µ and ν on E is

W p p (µ, ν) = inf π E×E
x -y p π(dx, dy)

1/p
where the infimum is taken over all transport plans between µ and ν. These distances quantify the weak convergence and are adapted to compare discrete and continuous measures.

Theorem 17 (Theorem 6.8 [START_REF] Villani | Optimal transport : old and new[END_REF]). Let p ≥ 1 and let µ and (ν n ) n∈N be measures on R d with finite p-th moment. The following statements are equivalent

• lim n→∞ W p (ν n , µ) = 0;
• (ν n ) n≥0 converges weakly to µ and

∀1 ≤ q ≤ p, lim n→∞ R d x q ν n (dx) = R d
x q µ(dx).

Recently, Ledoux, Nourdin and Peccati [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF] have provided a way to bound the 2-Wasserstein distance between two measures µ, invariant under an operator L µ = b.∇+ < a, ∇ 2 >, and ν, invariant under an operator of the form

L ν = b.∇+ < τ ν , ∇ 2 >, in which case τ ν is called a Stein kernel.
Hence, if we manage to adapt their result and define L ν as the generator of a Markov chain, our objective would be achieved. As mentioned in the end of Section 5.1, ν is the invariant measure of a Markov chain with transition kernel K if and only if there exists a pair (X, X ) of random variables with measure ν such that, for any x ∈ R d , the measure of E[X | X = x] is equal to K(x). The generator of the corresponding Markov chain is then given by

L ν φ(x) = E[φ(X ) -φ(X) | X = x].
Since it leads to clearer notations, we will use pairs of random variables rather than Markov chains in the remainder of this Chapter.

The approach

Let us first introduce some notations and recall notations introduced in Section 3.2.1. Let x ∈ R d and k ∈ N, we denote by x ⊗k ∈ (R d ) ⊗k the tensor of order k of x,

∀j 1 , . . . , j k ∈ {1, . . . , d}, (x ⊗k ) j 1 ,...,j k = k i=1 x j i .
For any x, y ∈ (R d ) ⊗k and any symmetric positive-definite d × d matrix A, let

< x, y > A = l,j∈{1,...,d} k x l y j k i=1 A j i ,l i ,
and, by extension,

x 2 A =< x, x > A . For any smooth function φ and x ∈ R d , let ∇ k φ ∈ (R d ) ⊗k where ∀j 1 , . . . , j k ∈ {1, . . . , d}, (∇ k φ(x)) j 1 ,...,j k = ∂ k φ ∂x j 1 . . . ∂x j k (x).
Let E be a convex domain of R d and ν and µ be two measures with support E. Suppose µ is a reversible measure for the diffusion process with generator L µ = b.∇+ < a, ∇ 2 > where b and a are smooth on E and a is symmetric positive-definite on all of E.

Let (P t ) t≥0 be the Markov semigroup with infinitesimal generator L µ . For any measure dη = hdµ, let dη t = P t hdµ. We first assume that dν = hdµ and I µ (ν t ) < ∞ for any t > 0.

Since µ is the invariant measure of L µ , under reasonable assumptions, ν t converges to µ as t goes to infinity. We can thus control the distance between µ and ν by controlling the distance between between ν t and ν. The latter can be achieved via the following inequality (see [START_REF] Villani | Optimal transport : old and new[END_REF]),

d + dt W 2 (ν, ν t ) ≤ I µ (ν t ) 1/2 , (5.2)
along with a bound on I µ (ν t ). We have

I µ (ν) = E ∇h 2 a h dµ = E < ∇h, ∇ log h > a dµ.
If we write v t = log(P t h),

I µ (ν t ) = E < ∇P t h, ∇v t > a dµ.
Since µ is reversible, it satisfies the following integration by parts formula: for any smooth compactly supported functions f and g,

E < ∇f, ∇g > a dµ = - E f L µ gdµ.
Since I µ (ν) is finite and P t hL µ v t can be shown to be integrable by the results of the following sections, we can apply this integration by parts formula to obtain

I µ (ν t ) = E < ∇P t h, ∇v t > a dµ = - E P t hL µ v t dµ.
Using the symmetry of µ with respect to P t and the commutativity of P t and L µ ,

I µ (ν t ) = - E hP t L µ v t dµ = - E L µ P t v t dν.
Now, suppose there exists an operator L ν such that,

E L ν P t v t dν = 0, then I µ (ν t ) = E (L ν -L µ )P t v t dν.
In [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF], L ν is given by the Stein kernel but it can be defined in many other ways. For example, as mentioned at the end of Section 5.1, if (X, X ) is a couple of random variables drawn from ν then, taking

L ν φ(x) = 1 s E [φ(X ) -φ(X)|X = x] ,
we have

R d L ν P t v t dν = 0.
Now, suppose P t v t is real analytic on E, then for any s > 0,

L ν P t v t (x) = 1 s E ∞ k=1 < (X -X) ⊗k k! , ∇ k P t v t > |X = x ,
In which case,

I µ (ν t ) =E [< E[X -X | X] -b(X), ∇P t v t (X) >] + E < E[ (X -X) ⊗2 2 | X] -a(X), ∇ 2 P t v t > (5.3) + E ∞ k=3 < E[ (X -X) ⊗k k! | X], ∇ k P t v t (X) > .
The last step of the approach consists in using the regularizing properties of the semigroup P t in order to bound the last equation by a quantity involving P t ∇v t 2 a . Then, since E[P t ∇v t 2 a (X)] 1/2 = I µ (ν t ) 1/2 and I µ (ν t ) is finite, we obtain a bound on I µ (ν t ) 1/2 and conclude. Let us note that, since a is positive-definite on all of E, the bounds we derive on ∇ k P t v t a imply P t v t is real analytic on all of E [START_REF] Komatsu | A characterization of real analytic functions[END_REF].

In order to deal with discrete measures, let us note that, for > 0, ν is well-defined. Thus, if it has a finite Fisher information with respect to µ, we can apply the previous approach to any ν and let go to 0 to obtain a bound on W 2 (ν, µ) even though ν is discrete.

Our goal in the remainder of this section will thus consist in providing bounds for Equation 5.3. We start with the Gaussian case where such a bound can be directly obtained using the integral representation of (P t ) t≥0 and integrations by parts. We then deal with more general measures µ and derive a bound using Gamma calculus.

Gaussian case

Let dµ = dγ = (2π) -d/2 e -|x| 2
2 dx be the Gaussian measure in R d . γ is the invariant measure of L γ = -x.∇ + ∆ and the associated semigroup (P t ) t≥0 is the Ornstein-Uhlenbeck semigroup. Let φ be a smooth function with compact support on R d . For any x ∈ R d , P t φ admits the following representation

P t φ(x) = R d φ(xe -t + √ 1 -e -2t y)dγ(y).
Using an integration by part, we obtain

∇P t φ(x) = e -t R d ∇φ(xe -t + √ 1 -e -2t y)dγ(y) = e -t √ 1 -e -2t R d yφ(xe -t + √ 1 -e -2t y)dγ(y).
For any k > 0 and any i ∈ {1, . . . , d} k , let H i be the multivariate Hermite polynomial of index i,

H i = (-1) k e |x| 2 2 ∂ k ∂x i 1 . . . ∂x i k e -|x| 2 2 .
Multiple integrations by parts yield

(∇ k P t φ(x)) i = e -kt (1 -e -2t ) k/2 R d H i (y)φ(xe -t + √
1 -e -2t y)dγ(y).

CHAPTER 5. STEIN'S METHOD FOR DIFFUSION APPROXIMATION

Hermite polynomials form an orthogonal basis of L 2 (γ) with norm ∀i ∈ {1, . . . , d} k , H i

2 γ = R d H 2 i (y)dγ(y) = d j=1 k l=1 δ i l ,j !. Hence, ∞ k=1 i∈{1,...,d} k-1 e 2kt (1 -e -2t ) k-1 H i 2 γ (∇ k P t φ) 2 i (x) = ∞ k=1 i∈{1,...,d} k-1 e 2kt (1 -e -2t ) k-1 H i 2 γ R d (∇ k φ) i (xe -t + √ 1 -e -2t y)dγ(y) 2 = ∞ k=1 i∈{1,...,d} k-1 R d H i H i γ ∇φ(xe -t + √ 1 -e -2t y)dγ(y) 2 = R d ∇φ(xe -t + √ 1 -e -2t y) 2 dγ(y) = P t ∇φ 2 (x).
Let us pose

S(t) =e -2t E E[ X -X s | X] + X 2 + e -4t 1 -e -2t E E[ (X -X) ⊗2 2s | X] -I d 2 + ∞ k=3 i∈{1,...,d} k-1 e -2kt H i 2 γ (sk!) 2 (1 -e -2t ) k-1 E E[(X -X) ⊗k i | X] 2 .
Applying Cauchy-Schwarz's inequality to Equation 5.3 yields

I γ (ν t ) ≤ S(t) 1/2 E[P t ∇v t (X) 2 ] 1/2 = S(t) 1/2 I γ (ν t ) 1/2 . (5.4)
We have thus bounded I γ (ν t ). Now, according to Equation 5.2, integrating our bound on I γ (ν t ) for t ∈ R + would yield a bound on W 2 (ν, γ). However, we encounter integrability issues for the higher order terms for small values of t. To circumvent this issue, we use a family of couplings (X, X t ) t≥0 interpolating between X 0 = X and X ∞ = X , ensuring the problematic terms are 0 at t = 0. Finally, for any discrete measure ν, ν t has finite Fisher information as long as the second moment of ν is finite (see Remark 2.1 [START_REF] Nourdin | Entropy and the fourth moment phenomenon[END_REF]). We are now ready to state the first result of this work.

Theorem 18. Let ν be a measure on R d with finite second moment and let X and (X t ) t≥0 be random variables drawn from ν. For any s > 0,

W 2 (ν, γ) ≤ ∞ 0 S(t)dt, with
S(t) =e -2t E E[ X t -X s | X] + X 2 + e -4t 1 -e -2t E E[ (X t -X) ⊗2 2s | X] -I d 2 + ∞ k=3 i∈{1,...,d} k-1 e -2kt H i 2 γ (sk!) 2 (1 -e -2t ) k-1 E E[(X t -X) ⊗k i | X] 2 .

General case

In general, (P t ) t≥0 does not admit a closed form formula so we cannot rely on a direct approach. Let us first apply Cauchy-Schwarz's inequality to Equation 5.3 in order to obtain

I µ (ν t ) ≤E E[X -X | X] -b(X) 2 a -1 (X) 1/2 E[ ∇P t v t (X) 2 a(X) ] 1/2 + E E[ (X -X) ⊗2 2 | X] -a(X) 2 a -1 (x) 1/2 E[ ∇ 2 P t v t (X) 2 a(X) ] 1/2 (5.5) + ∞ k=3 E E[ (X -X) ⊗k k! | X] 2 a -1 (x) 1/2 E[ ∇ k P t v t (X) 2 a(X) ] 1/2 .
Our objective is to bound

∇ k P t v t 2
a by a quantity involving P t ∇v t 2 a using the framework of Γ-calculus described in [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF]. This approach relies on the iterated gradients Γ i , defined recursively for any smooth functions f, g by

Γ 0 (f, g) = f g; Γ i+1 (f, g) = 1 2 [L µ (Γ i (f, g)) -Γ i (L µ f, g) -Γ i (f, L µ g)] .
The triple (E, µ, Γ 1 ) is called a Markov triple, a structure extensively studied in [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF]. In particular if there exists ρ ∈ R such that

Γ 2 ≥ ρΓ 1 ,
the Markov triple is said to satisfy a curvature-dimension inequality, or CD(ρ, ∞) condition, under which (P t ) t≥0 has many interesting properties.

For instance, it is known that, under a CD(ρ, ∞) condition, (P t ) t≥0 satisfies the following gradient bound (see e.g. Theorem 3.2.3 [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF])

∇P t f 2 a ≤ e -2ρt P t ( ∇f 2 a ),
Remark 19. Under a CD(ρ, ∞) condition, if ν = hdµ, then, according to Theorem 5.5.2 [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF],

I µ (ν t ) ≤ 2ρ 1 -e -2ρt (P t (h log h) -P t h log(P t h)) .
Thus, if ν has finite entropy with respect to µ for any > 0, then I µ (ν t ) is finite for any t > 0.

In the proof of Theorem 4.1 [START_REF] Ledoux | Stein's method, logarithmic sobolev and transport inequalities[END_REF], the authors show that, under a CD(ρ, ∞) condition for ρ > 0 and assuming there exists κ, σ > 0 such that Γ 3 ≥ κΓ 2 and Γ 2 ≥ σ ∇ 2 f a ,

∇ 2 P t f 2 a ≤ κ σ(e κt -1) P t ∇f 2 a . (5.6)
We could use a similar approach and suppose that for any k > 1 there exists some κ k and σ k such that Γ k+1 ≥ κ k Γ k and Γ k ≥ σ ∇ k f a in order to bound ∇ k P t f a . However, such assumptions would be quite restrictive in practice. Instead, we derive bounds relying on a simple CD(ρ, ∞) condition.

Proposition 20. Suppose that L satisfies a CD(ρ, ∞) condition for ρ ∈ R.

Then, for any k ∈ N , t > 0 and any smooth compactly supported function φ,

∇ k P t φ a ≤ f k (t) P t ∇φ 2 a , where
f k (t) =    e -ρt max(1,k/2) 2ρd e 2ρt/(k-1) -1 (k-1)/2 if ρ = 0 t (1-k)/2 if ρ = 0.
Unfortunately, our bound is not dimension-independent as one could expect from Equation 5.6. We believe this dependency to be an artifact of the proof. Nevertheless, by injecting these bounds in Equation 5.5, we obtain a bound on I µ (ν t ) 1/2 leading to the following result.

Theorem 21. Let ν be a measure on R d . Assume the entropy of ν with respect to µ is finite for any > 0 and let X and (X t ) t≥0 be random variables drawn from ν. If L µ satisfies a CD(ρ, ∞) condition for ρ ∈ R, then, for any s > 0, T > 0,

W 2 (ν, ν T ) ≤ T 0 e -ρt E E X t -X s | X -b(X) 2 a -1 1/2 dt + T 0 f 2 (t)E E (X t -X) ⊗2 2s | X -a(X) 2 a -1 1/2 dt + ∞ k=3 T 0 f k (t) sk! E[ E[(X t -X) ⊗k | X] 2 a -1 ] 1/2 dt,
where the functions (f k ) k≥1 are defined in Proposition 20.

If ρ > 0, we can set T to infinity to bound W 2 (ν, µ). On the other hand, if ρ ≤ 0, it is still possible to bound W 2 (ν, µ) as long as ν t converges exponentially fast to ν. Lemma 22. Suppose there exists κ such that for any measure η and any t > 0, we have W 2 (η t , µ) ≤ e -κt W 2 (η, ν).

Then, for any T > 0,

W 2 (ν, µ) ≤ W 2 (ν, ν T ) 1 -e -κT .
Proof. Indeed, we have

W 2 (ν, µ) ≤ W 2 (ν, ν t ) + W 2 (ν t , µ) ≤ W 2 (ν, ν t ) + e -κt W 2 (ν, µ).
Such an exponential convergence to µ can be verified under weaker conditions than a CD(ρ, ∞) inequality for ρ > 0. For example, if a is the identity matrix and b is the gradient of some potential V then this assumption is satisfied whenever V is strongly convex outside a bounded set C with bounded first and second order derivatives on C [START_REF] Guillin | Convergence to equilibrium in wasserstein distance for fokker-planck equations[END_REF], which is equivalent to satisfying a CD(ρ 1 , ∞) condition for some ρ 1 ∈ R and having Γ 2 ≥ ρ 2 Γ 1 with ρ 2 > 0 outside of C. An extension of this result for more general a and for manifolds is proposed in [START_REF] Wang | Exponential Contraction in Wasserstein Distances for Diffusion Semigroups with Negative Curvature[END_REF].

CHAPTER 5. STEIN'S METHOD FOR DIFFUSION APPROXIMATION

Gaussian measure in dimension one

The Stein kernel can also be used to bound the Wasserstein distance of order p ≥ 1 between a measure ν and the Gaussian measure γ under a stronger definition. Let X be a random variable drawn from ν, we say that τ ν is a strong Stein kernel for ν if E [-Xφ(X) + τ ν (X)∇φ(X)] = 0 for every compactly supported smooth function φ.

In dimension one, if τ ν is a Stein kernel for ν, then it satisfies the previous condition, hence we can expect our coupling approach to be able to replace the Stein kernel. Let µ = γ 1 be the one-dimensional Gaussian measure. For k ∈ N, we denote by H k the k-th Hermite polynomial,

H k = (-1) k e |x| 2 2 d k e -|x| 2 2 dx k .
First, a modification of the proof of Lemma 2 from [START_REF] Otto | Generalization of an inequality by talagrand and links with the logarithmic sobolev inequality[END_REF] yields the general estimate

d + dt W p (ν, ν t ) ≤ R |v t | p dν t 1/p . (5.7)
Let us provide a version of v t . Let (X, X ) be random variables drawn from ν and Z be a Gaussian random variable. For t > 0, let F t = e -t X + √ 1 -e -2t Z and consider the function ρ t defined for any x ∈ R as follows

ρ t (x) = E e -t X -X s + X + e -2t √ 1 -e -2t (X -X) 2 2s -1 H 1 (Z)|F t = x + E ∞ k=3 e -kt s √ 1 -e -2t k-1 (X -X) k k! H k-1 (Z)|F t = x .
For any compactly supported smooth function φ : R → R, we obtain, after successive integrations by parts with respect to Z,

E[ρ t (F t )φ(F t )] = E e -t Xφ(F t ) -e -2t φ (F t ) + E ∞ k=1 e -kt (X -X) k sk! φ (k-1) (F t ) .
Let Φ be a primitive function of φ, by the results of Section 5.

E ∞ k=1 e -kt (X -X) k sk! φ (k-1) (F t ) = 1 s E[Φ(e -t X + √ 1 -e -2t Z) -Φ(e -t X + √ 1 -e -2t Z)] = 0.
Therefore,

E[(ρ t (F t ) -F t )φ(F t )] = E[(-F t + e -t X)φ(F t ) -e -2t φ (F t )] = E[-(1 -e -2t )φ (F t ) -e -2t φ (F t )] = -E[φ (F t )].
Therefore, ρ t satisfies the characterization of v t presented in Equation 2.28 [START_REF] Nourdin | Entropy and the fourth moment phenomenon[END_REF]: it is thus a version of v t . We are thus able to bound Theorem 23. Let ν be a measure on R and let X and (X t ) t≥0 be random variables drawn from ν. We have, for any p ≥ 1, s > 0,

R |v t | p dν t 1/p = E[|ρ t (F t )| p ]
W p (ν, γ 1 ) ≤ ∞ 0 e -t E E X t -X s | X + X p 1/p dt + ∞ 0 e -2t H 1 p,γ 1 √ 1 -e -2t E E (X t -X) 2 2s | X -1 p 1/p dt + ∞ k=3 ∞ 0 e -kt H k-1 p,γ 1 s √ 1 -e -2t k-1 k! E E[(X t -X) k | X] p 1/p dt.
Remark 24. [START_REF] Larsson-Cohn | L p-norms of hermite polynomials and an extremal problem on wiener chaos[END_REF] gives the asymptotic of the p-norm of Hermite polynomials with respect to the Gaussian measure, more precisely there exist constants C(p) such that

H k p ≤ C(p) √ k!k -1/4 (1 + O(k -1 )) if 0 < p < 2 C(p) √ k!(p -1) k/2 (1 + O(k -1 )) if p > 2 66
CHAPTER 5. STEIN'S METHOD FOR DIFFUSION APPROXIMATION 5.5 Applications

Central Limit Theorem

Let X 1 , . . . , X n be i.i.d. random variablestaking values in R d such that E[X 1 ] = 0 and E[X ⊗2 1 ] = I d . Let ν n be the measure of S n = n -1/2 n i=1 X i . According to the Central Limit Theorem, ν n should converge to the Gaussian measure γ, our objective in this section is to provide a bound of W p (ν n , γ) for some p ≥ 2. Let X 1 , . . . X n be independent copies of X 1 , . . . , X n and let I be a uniform random variable on {1, . . . , n}. For any t > 0, we pose S n,t = S n + n -1/2 (X I -X I )1 X I , X I ≤ √ n(e 2t -1) .

By construction, for any t > 0, S n,t is drawn from ν n . Using this coupling and applying either Theorem 18 or Theorem 23 with timestep s = 1 n , see Section 5.6.2 for the detailed computations, we obtain the following result.

Theorem 25. Let X 1 , . . . , X n be i.i.d. random variables in R d with E[X 1 ] = 0 and E[X ⊗2 1 ] = I d . There exists a universal constant C > 0, such that if E[ X 1 2+m ] < ∞ for some m ∈ [0, 2], then, W 2 (ν n , γ) ≤ C n -m/4 E[ X 1 2+m ] 1/2 + o(n -m/4 ) if m < 2 n -1/2 E[X ⊗2 1 X 1 2 ] if m = 2 . Let p ≥ 2. If d = 1, there exists a universal constant C p such that if E[|X 1 | p+q ] < ∞ for some q ∈ [0, p], then taking m ≤ min(4, p + q) -2, W p (ν n , γ) ≤ C p n -m/4 (E[|X 1 | 2+m ] 1/2 + o(1 m<2 )) + n -1/2+(2-q)/2p E[|X 1 | p+q ] 1/p .
Remark 26. Taking d = 1, p ≥ 2 in the previous result, we have, using Hölder's inequality,

E[|X 1 | 4 ] 1/2 = E[X 2-4/p 1 X 2+4 1 ] 1/2 = E[(X 2 1 ) 1-2/p (|X 1 | p+2 ) p/2 ] 1/2 ≤ E[X 2 1 ] 1-2/p E[|X 1 | p+2 ] 1/p ≤ E[|X 1 | p+2 ] 1/p . Therefore, as long as E[|X 1 | p+2 ] < ∞, Theorem 25 gives W p (ν n , γ) ≤ C p n -1/2 E[|X 1 | p+2 ].
The one-dimensional result completes a result obtained by [START_REF] Rio | Upper bounds for minimal distances in the central limit theorem[END_REF] who considered the case 1 ≤ p ≤ 2, m = 2 and generalizes a result obtained by [START_REF] Sakhanenko | Estimates in the invariance principle[END_REF] treating the case p > 2, m = 0. [12] also recovered the case p = 2, m = 2 using an entropic approach and recently proved the case m = 2 for any p > 2 [START_REF] Sergey | Berry-esseen bounds and edgeworth expansions in the central limit theorem for transport distances[END_REF]. To our knowledge, the multidimensional result is new although the entropic approach from [START_REF] Sergey | Entropic approach to e. rios central limit theorem for w2 transport distance[END_REF] might be generalized to the multidimensional setting at the expense of stronger assumptions on the moments of the variables.

Diffusion approximation

Let µ be the invariant measure of the diffusion process with infinitesimal generator L µ = b.∇+ < a, ∇ 2 >. Consider a discretization of this diffusion process by a Markov chain M with transition kernel K and invariant measure π and let s be the timestep of this discretization. Let X be a random variable drawn from π and let ξ be a random jump from X. Then for any t > 0, T > 0, X t = X + 1 t≥T ξ and X follow the same law. Applying Theorem 21 using (X t ) t≥0 yields the following result.

Corollary 27. Under the assumptions Theorem 21, we have, for any

T 1 > T 2 > 0, W 2 (π, π T 1 ) ≤ T 2 0 e -ρt E[ b(X) 2 a -1 ] 1/2 + f 2 (t)dt + T 1 T 2 e -ρt E E ξ s | X -b(x) 2 a -1 1/2 dt + T 1 T 2 f 2 (t)E[ E ξ ⊗2 2s | X] -a(x) 2 a -1 1/2 dt + T 1 T 2 ∞ k=3 f k (t)E E[ ξ ⊗k k!s | X] 2 a -1 1/2 dt,
where the functions (f k ) k≥1 are defined in Proposition 20.

Remark the quantities involved in this Corollary seems natural as they are rather similar to the quantities appearing the Theorem 7 dealing with the convergence of Markov chains to diffusion processes.

Since, under some assumptions on µ, the measure of Y t converges to µ as t goes to infinity, one may want to sample points from µ by approximating Y t . Using the Euler-Maruyama approximation with timestep s, we discretize Y t using a Markov chain M with M 0 = 0 and transitions given by

M n+1 = M n -s∇u(M n ) + √ 2sN n ,
where N 1 , . . . , N n is a sequence of independent normal random variables with mean 0 and covariance matrix I d . If the timestep is small enough, the invariant measure π of the Markov chain, should be close to µ. Hence, for n large enough, the measure of M n should be close to its invariant measure and thus be close to µ. Approximate sampling for µ using this approach is known as the Langevin Monte-Carlo (LMC) algorithm [START_REF] Gareth | Exponential Convergence of Langevin Distributions and Their Discrete Approximations[END_REF].

One may then wonder how large n should be to achieve a given accuracy. Answering this question is linked to the choice of s as this parameter must satisfy some trade-off: large values lead to a poor approximation of µ by π, but the smaller s is, the larger the number of iterations required for the measure of M n to be close to π. Recently, [START_REF] Arnak | Theoretical guarantees for approximate sampling from a smooth and log-concave density[END_REF] proved that whenever µ is a strictly log-concave measure (i.e. satisfying a CD(ρ, ∞) condition for ρ > 0), the LMC algorithm can reach an accuracy in total variation distance in O( -2 (d 3 +d log(1/ )) steps. For the Wasserstein distance, this complexity was later improved to O( -1 √ d log(1/ )) by [START_REF] Durmus | Sampling from strongly log-concave distributions with the Unadjusted Langevin Algorithm[END_REF]. A second order discretization, called the Ozaki discretization, was also considered in [START_REF] Arnak | Theoretical guarantees for approximate sampling from a smooth and log-concave density[END_REF]. Under this scheme, the number of iterations required to achieve an accuracy in total variation distance is smaller than O( -1 dim(d+log(1/ )) 3/2 ). Here, we propose to do the opposite by considering an example of a smaller order scheme with non-normal increments. Let (B n ) n≥0 be independent multivariate Rademacher random variables, and consider the following scheme

M n+1 = M n -s∇u(M n ) + √ 2sB n . (5.8)
Let µ be a log-concave measure, i.e. dµ = e -u dλ and there exists ρ > 0 such that ∀x ∈ R d , < ∇u(x) -∇u(y), (x -y) >≥ ρ x -y 2 2 .

Taking Γ 1 (f, g) =< ∇f, ∇g >, this is equivalent to saying the Markov Triple (R d , µ, Γ 1 ) satisfies a CD(ρ, ∞) condition for ρ > 0. Moreover, as shown in Subsection 5.6.3, π has finite second moment which implies, by Theorem 5.1 [START_REF] Ambrosio | Existence and stability for fokkerplanck equations with log-concave reference measure[END_REF], that π has finite entropy with respect to µ for > 0.

Together with Remark 19 this implies π has finite Fisher information with respect to µ for any > 0. Let X be a random variable drawn from π and Proof. Let t > 0, for any 0 ≤ s ≤ t let Λ(s) = P s (Γ 0 (P t-s φ)), the first two derivatives of this function are Λ (s) = 2P s (Γ 1 (P t-s φ)); Λ (s) = 4P s (Γ 2 (P t-s φ)).

By our assumption, Λ (s) ≥ 2ρΛ (s). Hence, by Gronwall's Lemma, Λ (s) ≥ e 2ρs Λ (0). Now, we have

Γ 1 (P t φ) = 2ρ e 2ρt -1 t 0 e 2ρs Γ 1 (P t φ)ds = 2ρ e 2ρt -1 t 0 e 2ρs Λ (0)ds ≤ 2ρ e 2ρt -1 t 0 Λ (s)ds ≤ 2ρ e 2ρt -1 (P t (Γ 0 (φ)) -Γ 0 (P t φ)) ≤ 2ρP t (Γ 0 (φ)) e 2ρt -1 .
Let (e 1 , . . . , e d ) be an orthonormal basis of R d with respect to the ascalar product < ., . > a .

Lemma 31. For any smooth function φ and any k > 0, we have

∇ k φ a = sup α∈R d , α =1 d i=1 α i ∇ k-1 < ∇φ, e i > a .
Proof. By the duality of the a-norm, we have

∇ k φ a = sup h∈(R d ) ⊗k , h a=1 < ∇ k φ, h > a = sup α∈R d , α =1 d i=1 sup h∈(R d ) ⊗k-1 , h a=1 < ∇ k φ, α i e i ⊗ h > a = sup α∈R d , α =1 d i=1 sup h∈(R d ) ⊗k-1 , h a=1 α i < ∇ k-1 < ∇φ, e i > a , h > a = sup α∈R d , α =1 d i=1 α i ∇ k-1 < ∇φ, e i > a a .
Let us prove Proposition 20 by induction. Take x ∈ R d and let φ be a compactly supported smooth function. The inequality holds for k = 1 by Equation 5.9. Now, suppose it is true for some k ∈ N. By Lemma 31 we only need to bound

∇ k+1 < ∇P t φ, e i > a a = lim →0 ∇ k (P t φ(x + ae i ) -P t φ(x)) a
for any e i . Let > 0 and let (X t ) t≥0 and ( Xt ) t≥0 be two diffusion processes with infinitesimal generator L µ started respectively at x and x + ae 1 . Let t ≥ 0 and let π be a coupling between X t and Xt . We have

P t φ(x + ae 1 ) -P t φ(x) = P t φ • π -φ ,
Applying the induction hypothesis,

∇ k P t φ • π -φ 2 a ≤ e -ρt max(2,k) k-1 k 2ρd e 2ρdt/k -1 k-1 P t k-1 k ∇P t/k φ • π -φ 2 a
, and, applying Lemma 30,

∇ k P t φ • π -φ 2 a ≤ e -ρt(k-1) d k-1 2ρ e 2ρdt/k -1 k P t φ • π -φ 2 .
By Theorem 2.2 [START_REF] Kuwada | Duality on gradient estimates and wasserstein controls[END_REF], Equation 5.9 implies that we can take π such that, for any

y ∈ R d , sup y∈R d π (y) -id a -1 ≤ e -ρt + o( ), therefore lim →0 φ • π -φ = lim →0 < ∇φ, a -1 (π -id) > a +o( π -id ) ≤ e -ρt ∇φ a .
Since a similar result holds for any e i , we have, using Lemma 31,

∇ k+1 P t φ 2 a ≤ e -ρt(k+1) d k-1 2ρ e 2ρdt/k -1 k sup α∈R d , α =1 d i=1 α i P t ∇φ 2 2 .
Finally, since the supremum is obtained for Let k be a positive integer. For any x ∈ (R d ) ⊗k , we pose

α 1 = • • • = α d = 1 √ d , the proof is complete.
x p p = i∈{1,...,d} k |x i | p .
Let Z be a random variable in (R d ) ⊗k . For any l ∈ {1, . . . , d} k , we pose

(Z) l = Z l 1 ,...,l k .
Before starting the proof of Theorem 25, we first need to derive a multidimensional version of the Rosenthal inequality.

Lemma 32. Let k > 0, p ≥ 2 and suppose Z 1 , . . . , Z n are independent random variables taking values in (R d ) ⊗k , then

E   n i=1 Z i p p   1/p ≤ C p n E[Z] p + n 1/2 E[ Z 2 p ] 1/2 + n 1/p E[ Z p p ] 1/p ≤ C p n E[Z] + n 1/2 E[ Z 2 ] 1/2 + n 1/p E[ Z p ] 1/p .
Proof. By definition, we have

E   n i=1 Z i p p   = l∈{1,...,d} k E n i=1 (Z i ) l p .
We pose Z = Z 1 . For any l ∈ {1, . . . , d} k , we know by Rosenthal's inequality (see [START_REF] Boucheron | Concentration inequalities : a nonasymptotic theory of independence[END_REF]) that there exists C p > 0 such that

E n i=1 (Z i ) l p ≤ C p n p |E[(Z) l ]| p + n p/2 E[(Z) 2 l ] p/2 + nE[|(Z) l | p ] .
Hence, denoting by Z 2 the random variables taking values in

(R d ) ⊗k such that (Z 2 ) l 1 ,...,l k = (Z) 2 l 1 ,...,l k , E   n i=1 Z i p p   ≤ C p n p E[Z] p p + n p/2 E[Z 2 ] p/2 p/2 + nE[ Z p p ] .
Using Jensen's inequality, we have

E[Z 2 ] p/2 ≤ E[ Z 2 p/2 ] ≤ E[ Z 2 p ]
. Finally, we conclude the proof by remarking that . p ≤ . . We are now ready to start the proof of Theorem 25. Let us pose X = X 1 , X = X 1 , and α(t) = e 2t -1. In the remainder of this proof, we are going to show there exist C > 0, C p > 0 such that

• ∞ 0 e -t E[ E[n(S n,t -S n ) | S n ] + S n p p ] 1/p dt, • ∞ 0 e -2t √ 1-e -2t E E n (S n,t -Sn) ⊗2 2 | S n -I d p p 1/p dt, • and ∞ k=3 H k p,γ k! ∞ 0 e -kt √ 1-e -2t k-1 E[ E[n(S n,t -S n ) ⊗k | S n ] p p ] 1/p dt,
are bounded by

C p n -1/2+(2-q)/2p E[ X p+q ] 1/p + n -m/4 E[ X 2+m ] 1/2 +            max(n -m/2 , n -1/2 ) E[X ⊗2 X m ] log n √ d E[X ⊗2 X m ] if n ≤ E[X ⊗2 X m ] √ d e C/(1-m) 1 1-m n -m/4 E[X ⊗2 X m ] 1/2 2 else if m < 1 1 1-m √ d 1-1/m n -m/4 E[X ⊗2 X m ] 1/2 2/m otherwise - .
Theorem 25 is then obtained using these bounds in either Theorem 18 or Theorem 23 and remarking that

E[ X 2+m ] = E    i∈{1,...,d} (
X) 2 i   j∈{1,...,d} (
X) 2 j   m/2    = i∈{1,...,d} E    (X) 2 i   j∈{1,...,d} (
X) 2 j   m/2    ≤ d 1/2    i∈{1,...,d} E    (X) 2 i   j∈{1,...,d} (
X) 2 j   m/2    2    1/2 ≤ d 1/2    i,k∈{1,...,d} E    (X) i (X) k   j∈{1,...,d} (
X) 2 j   m/2    2    1/2 , leads to E[ X 2+m ] ≤ d 1/2 E[X ⊗2 X m ] .
(5.10)

PROOFS

Remark 33. For d > 1 and p > 2, these bounds are not optimal. For instance, whenever p is an even integer, one can replace all 2-norms . by p-norms . p by taking

S n,t = S n + n -1/2 (X I -X I )1 X I p, X I p≤ √ n(e 2t -1) .
In the remainder of this proof, C p denotes a generic constant depending only on p and C a generic universal constant. For any t ≥ 0, we have, by definition of S n,t ,

S n,t -S n = 1 √ n (X I -X I )1 X I , X I ≤ √ nα(t) .
Moreover, since I is independent from S n , then, for any integer k > 0,

E[n(S n,t -S n ) ⊗k | S n ] = E n 1-k/2 E I [(X I -X I )1 X I , X I ≤ √ nα(t) ] | S n = n -k/2 E n i=1 (X i -X i ) ⊗k 1 X i , X i ≤ √ nα(t) | S n .
Hence,

E[n(S n,t -S n ) | S n ] + S n = E[n(S n,t -S n ) + S n | S n ] = 1 √ n E n i=1 (X i -X i )1 X i , X i ≤ √ nα(t) + X i | S n . Let us pose Z = E[(X -X)1 X , X ≤ √ nα(t) + X]. Since X is independent from S n , E[X | S n ] = E[X ] = 0. Hence, E[X 1 X , X ≤ √ nα(t) | S n ] = -E[X 1 max X , X ≥ √ nα(t) | S n ]. Therefore E[Z | S n ] = E[(X -X )1 max X , X ≥ √ nα(t) | S n ],
and

E[ E[n(S n,t -S n ) | S n ]+S n p p ] 1/p = n -1/2 E   E n i=1 (X i -X i )1 max X i , X i ≥ √ nα(t) | S n p p   1/p .

CHAPTER 5. STEIN'S METHOD FOR DIFFUSION APPROXIMATION

Applying Jensen's inequality to get rid of the conditional expectation,

E[ E[n(S n,t -S n ) | S n ]+S n p p ] 1/p ≤ n -1/2 E   n i=1 (X i -X i )1 max X i , X i ≥ √ nα(t) p p   1/p . Let us pose Y = (X -X )1 max X , X ≥ √ nα(t) . Since the (X i ) 1≤i≤n , (X i ) 1≤i≤n are i.i.d. random variables, so are the ((X i - X i )1 max X i , X i ≥ √ nα(t) ) 1≤i≤n
. Hence, we can apply Lemma 32 to obtain

E[ E[n(S n,t -S n ) | S n ] + S n p p ] 1/p ≤ C p (n 1/2 E[Y ] + E[ Y 2 ] 1/2 + n 1/p-1/2 E[ Y p ] 1/p ).
Since X and X follow the same law, E[Y ] = 0. On the other hand, we have

E[ Y p ] 1/p = E[ X -X p 1 max X , X ≥ √ nα(t) ] 1/p ≤ 2E[ X p 1 max X , X ≥ √ nα(t) ] 1/p ≤ 2E[ X p 1 X ≥ √ nα(t) ] 1/p ≤ 2(nα(t)) -q/2p E[ X p+q ] 1/p ,
and, similarly,

E[ Y 2 ] 1/2 ≤ 2(nα(t)) -m/4 E[ X 2+m ] 1/2 .
Overall, we obtained

E[ E[n(S n,t -S n ) | S n ] + S n p p ] 1/p ≤ C p n -m/4 α(t) -m/4 E[ X 2+m ] 1/2 + n -1/2+(2-q)/2p α(t) -q/2p E[ X p+q ] 1/p .
Finally, using the bound α(t) ≥ 2t in the following integral,

∞ 0 e -t E[ E[n(S n,t -S n ) | S n ] + S n p p ] 1/p dt ≤ C p n -m/4 E[ X 2+m ] 1/2 + n -1/2+(2-q)/2p E[ X p+q ] 1/p .
Let us now tackle the second order term. We have

E n (S n,t -S n ) ⊗2 2 | S n -I d = E (X I -X I ) ⊗2 2 1 X I , X I ≤ √ nα(t) | S n -I d = 1 n E n i=1 (X i -X i ) ⊗2 2 1 X i , X i ≤ √ nα(t) -I d | S n . 5.6. PROOFS 77 Again, taking Y = (X -X) ⊗2 2 1 X , X ≤ √ nα (
t) -I d and using a combination of Jensen's inequality and Lemma 32, we obtain

E E n (S n,t -S n ) ⊗2 2 | S n -I d p p 1/p ≤ C p E [Y ] + n -1/2 E Y 2 1/2 + n 1/p-1 E [ Y p ] 1/p . First, since E [X ⊗2 ] = E [X ⊗2 ] = I d , E [Y ] = E (X -X) ⊗2 2 1 max X , X ≥ √ nα(t) .
For two x, y ∈ R d ⊗k , we denote by < x, y > the corresponding Hilbert-Schmidt scalar product between x and y. Letting Z and Z be two random variables such that X, X , Z, Z are i.i.d., we have

E [Y ] = E (X -X) ⊗2 1 max X , X ≥ √ nα(t) , E (Z -Z) ⊗2 1 max Z , Z ≥ √ nα(t) = E (X -X) ⊗2 , (Z -Z) ⊗2 1 max X , X ≥ √ nα(t) 1 max Z , Z ≥ √ nα(t) = E (X -X), (Z -Z) 2 1 max X , X ≥ √ nα(t) 1 max Z , Z ≥ √ nα(t) ≤ C E < X, Z > 2 1 max X , X ≥ √ nα(t) 1 max Z , Z ≥ √ nα(t) ≤ C(nα(t)) -m/2 E [< X, Z > 2 max( X , X ) m max( Z , Z ) m ] ≤ C(nα(t)) -m/2 E [< X, Z > 2 ( X m + X m + Z m + Z m )] ≤ C(nα(t)) -m/2 E[X ⊗2 ( X m + X m )] ≤ C(nα(t)) -m/2 ( E[X ⊗2 X m ] + E[X ⊗2 X m ] )
Since X and X are independent,

E[X ⊗2 X m ] = √ dE[ X m ] ≤ d -1/2 E[ X 2 ]E[ X m ] ≤ d -1/2 E[ X 2+m ] 2/(2+m) E[ X 2+m ] m/(2+m) ≤ d -1/2 E[ X 2+m ],
and, since we know by Equation 5.10 that E

[ X 2+m ] ≤ √ d E[X ⊗2 X m ] , we obtain E [Y ] ≤ C(nα(t)) -m/2 E[X ⊗2 X m ] .
Let us remark that this causes integration issues when m ≥ 1, as

e -2t √ 1 -e -2t α(t) -m/2 = 1 α(t) (m+1)/2 ∼ t→0 1 (2t) (m+1)/2 .
In order to deal with this problem, we remark that, replacing m by 0 in the previous bound, we can also obtain

E [Y ] ≤ C E[X ⊗2 ] ≤ C √ d.
Then, taking some 0

< t 0 < 1, ∞ 0 e -2t √ 1 -e -2t E [Y ] dt ≤ t 0 0 C √ de -2t √ 1 -e -2t dt+Cn -m/2 E[X ⊗2 X m ] E[X ⊗2 X m ] ∞ t 0 α(t) -(m+1)/2 .
Let m = 1. Since α(t) ≥ 2t and α(t) ≥ e t for t ≥ 1, we can decompose the previous bound further:

∞ t 0 α(t) -(m+1)/2 ≤ 1 t 0 (2t) -(m+1)/2 dt + ∞ 1 e -t dt ≤ C 1 + 1 -t (1-m)/2 0 1 -m .
At this point, there are three possibilities:

• If t (1-m)/2 0 ≤ 1/2, then ∞ t 0 α(t) -(m+1)/2 ≤ C 1-m . • If t (1-m)/2 0 ≥ 3/2, then ∞ t 0 α(t) -(m+1)/2 ≤ Ct (1-m)/2 0 1-m . • If not, then | log(1/t 0 )(m -1)| ≤ C and |1 -t (1-m)/2 0 | = |1 -e 1-m 2 log(t 0 ) | ≤ C|(m -1) log(1/t 0 )|. Thus 1 -t (1-m)/2 0 1 -m ≤ log(1/t 0 ). 5.6. PROOFS 79
Therefore, taking t

0 = 1 n E[X ⊗2 X m ] √ d 2/m , there exists C > 0 such that ∞ 0 e -2t √ 1 -e -2t E [Y ] dt ≤ C        max(n -m/2 , n -1/2 ) E[X ⊗2 X m ] log n √ d E[X ⊗2 X m ] if n ≤ E[X ⊗2 X m ] √ d e C/(1-m) 1 1-m n -m/4 E[X ⊗2 X m ] 1/2 2 else if m < 1 1 1-m √ d 1-1/m n -m/4 E[X ⊗2 X m ] 1/2 2/m otherwise .
Let us now deal with the moments of Y . We have

E[ Y p ] ≤ 2 p (E[ (X -X) ⊗2 2 p ] + I d p ) ≤ 2 p (E[ X p + d) ≤ 2 p (E[ X 2p 1 X ≤ √ nα(t) ] + E[ X 2 ]) ≤ 2 p (1 + (nα(t)) (p-q)/2 )E[ X p+q ]. and E[ Y 2 ] ≤ 4(1 + (nα(t)) m-2 )E[ X 2+m ].
Putting everything together,

∞ 0 e -2t √ 1 -e -2t E E n (S n,t -S n ) ⊗2 2 | S n -I d p p 1/p dt ≤ C p n -1/2+(2-q)/2p E[ X p+q ] + n -m/4 E[ X 2+m ] 1/2 +        max(n -m/2 , n -1/2 ) E[X ⊗2 X m ] log n √ d E[X ⊗2 X m ] if n ≤ E[X ⊗2 X m ] √ d e C/(1-m) 1 1-m n -m/4 E[X ⊗2 X m ] 1/2 2 else if m < 1 1 1-m √ d 1-1/m n -m/4 E[X ⊗2 X m ] 1/2 2/m otherwise .
We are now left with dealing with the higher order terms. For k

> 2, let Y = E[(X -X) ⊗k 1 X , X ≤ √ nα(t) | S n ].
Then, by a combination of Jensen's inequality and Lemma 32,

E[ E[n(S n,t -S n ) ⊗k | S n ] p p ] 1/p ≤ n 1-k/2 E[Y ] + n 1/2-k/2 E[ Y 2 ] 1/2 + n 1/p-k/2 E[ Y p ] 1/p . First, we have E[ Y p ] ≤ E[ X -X kp 1 X , X ≤ √ nα(t) ] ≤ 2 kp E[ X kp 1 X ≤ √ nα(t) ] ≤ 2 kp (nα(t)) ((k-1)p-q)/2 E[ X p+q ],
and

E[ Y 2 ] ≤ 4 k (nα(t)) k-1-m/2 E[ X 2+m ].
Then, since X and X are i.i.d., E[Y ] = 0 for odd values of k. Let us now consider an even integer k > 2. Denoting by Z and Z two random variables such that X, X , Z, Z are i.i.d. Following the computations performed to bound the second order term, we obtain

E[Y ] = E < X -X, Z -Z > k 1 X , X ≤ √ nα(t) 1 Z , Z ≤ √ nα(t) 1/2 ≤ 2 k E < X, Z > k 1 X , Z ≤ √ nα(t) 1/2 ≤ 2 k E < X, Z > 2 X k-2 Z k-2 1 X , Z ≤ √ nα(t) 1/2 ≤ 2 k (nα(t)) (k-m-2)/2 E < X -X, Z -Z > 2 X m Z m 1/2 ≤ 2 k (nα(t)) (k-m-2)/2 E[X ⊗2 X m ] ,
and, similarly,

E[Y ] ≤ 2 k (nα(t)) (k-2)/2 E[X ⊗2 ] ≤ 2 k (nα(t)) k/2-1 √ d.
Then, using the same integration procedure we used to bound the second order term, we obtain

∞ 0 e -kt √ 1 -e -2t k-1 E[ E[n(S n,t -S n ) ⊗k | S n ] p p ] 1/p dt ≤ C p 2 k n -1/2+(2-q)/2p E[ X p+q ] + n -m/4 E[ X 2+m ] 1/2 +        max(n -m/2 , n -1/2 ) E[X ⊗2 X m ] log n √ d E[X ⊗2 X m ] if n ≤ E[X ⊗2 X m ] √ d e C/(1-m) 1 1-m n -m/4 E[X ⊗2 X m ] 1/2 2 else if m < 1 1 1-m √ d 1-1/m n -m/4 E[X ⊗2 X m ] 1/2
2 k H k p,γ k! < ∞, ∞ k=0 H k p,γ k! ∞ 0 e -kt √ 1 -e -2t k-1 E[ E[n(S n,t -S n ) ⊗k | S n ] p p ] 1/p dt ≤ C p n -1/2+(2-q)/2p E[ X p+q ] + n -m/4 E[ X 2+m ] 1/2 +        max(n -m/2 , n -1/2 ) E[X ⊗2 X m ] log n √ d E[X ⊗2 X m ] if n ≤ E[X ⊗2 X m ] √ d e C/(1-m) 1 1-m n -m/4 E[X ⊗2 X m ] 1/2 2 else if m < 1 1 1-m √ d 1-1/m n -m/4 E[X ⊗2 X m ] 1/2 2/m otherwise k=0
, which is the last bound required to conclude the proof.

Proof of Proposition 29

By construction,

• E[ ξ s -∇u(X) | X] = 0; • E[ E[ ξ ⊗2 2s -I d | X] 2 ] 1/2 = s 2 E[ ∇u(X) 4
] 1/2 ; Since ∇u(0) is assumed to be 0 and Lipschitz continuous, we have ∇u(X) ≤ L 1 X . Let us bound E[ X 2 ]. Since X and X + ξ have the same law,

E[ X 2 ] = E[ X + ξ 2 ] = E[ X + s∇u(X) 2 ] + 2ds ≤ E[ X 2 + 2sX.∇u(X) + s 2 ∇(u)(X) 2 ] + 2ds.
And, since µ is log-concave,

E[ X 2 ] ≤ (1 -2sρ + L 2 1 s 2 )E[ X 2 ] + 2ds, therefore E[ X 2 ] ≤ 2ds 2sρ -L 2 1 s 2 ≤ d ρ + O(s).
Now, since µ is strongly log-concave and by construction of our increments, X <

√ 2 ρ √ sd . Therefore there exists C > 0 such that E[ ∇u(X) 4 ] 1/2 ≤ d s 1/2 . Let B be a multivariate Rademacher random variable, for k ≥ 3, E[|E[(ξ) ⊗k ] | X| 2 ] 1/2 = k j=0 k j 2 j/2 s k-j/2 E[ ∇u(X) 2(k-j) ] 1/2 E[B ⊗j ] 84
CHAPTER 6. TOPOLOGICAL POOLING ter accuracy. In the Sparse Coding approach, the one we use in this paper, W and C are computed on the training set following min

(C i ) i∈[1,M ] ,W M i=1 x∈V i F i (x) -W C i (x) 2 2 + λ C i (x) 1 ,
with constraint w i ≤ 1 and regularization parameter λ. During the testing phase, the optimization is only performed on C with the codebook already computed. The pooling step aims at summarizing properties of the family (C i ) i∈[1,M ] and representing them through vectors (P i ) i∈[1,M ] which can then be used in standard learning algorithms such as SVM (Support Vector Machine). Usually, the pooling method depends on the coding scheme used. For Vector Quantization, one traditionally uses the mean of the word functions, an approach called sum-pooling

P i = ( x∈V i (C i (x)) 1 |V i | , ..., x∈V i (C i (x)) K |V i | ).
The other traditional pooling scheme, called max-pooling, was introduced along the Sparse Coding scheme by Yang et al. in [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF]. With this pooling technique, word functions are summarized by their maxima

P i = (max x∈V i (C i (x)) 1 , ..., max x∈V i (C i (x)) K ).
Several works have highlighted the improvement obtained using maxpooling rather than sum-pooling, both in terms of accuracy and, since it can be used with a linear kernel in learning algorithms, of computational scalability [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF][START_REF] Boureau | Learning mid-level features for recognition[END_REF]. The strength of max pooling is due in part to its remarkable robustness properties as it is invariant with respect to many transformations a shaper can undergo such that translations, rotations or changes of scale. On the other hand, the information captured by this pooling procedure is rather restricted.

One of the main assumptions made in designing and studying the bagof-words approach is that the values of the word functions are i.i.d. random variables. Refinements of the max-pooling scheme have been proposed under this assumption: for instance [START_REF] Liu | In defense of softassignment coding[END_REF] proposed to consider the k highest values for each words. However, the independence assumption of the word functions is unrealistic: the values of the word functions on close vertices of the mesh of a 3D-shape tend to be similar, as illustrated in Figure 6.1. Thus, in this example, the generalization proposed by [START_REF] Liu | In defense of softassignment coding[END_REF] ends up capturing the same feature multiple times and providing multiple redundant values. On the other hand, an important enhancement of the pooling procedure called Spatial pyramid matching [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] was proposed in the image processing literature. The idea behind this improvement was to perform pooling separately on different parts, quadrants, stripes, etc. of an image thus gaining some information regarding the spatial distribution of the word functions. This approach has drastically improved the performance of the bag-of-words procedures on multiple datasets, contradicting the identically distributed assumption. Let us note there exist adaptations of this technique to 3D shape [START_REF] Javier Lpez-Sastre | Evaluating 3d spatial pyramids for classifying 3d shapes[END_REF][START_REF] Li | Intrinsic spatial pyramid matching for deformable 3d shape retrieval[END_REF], but they are not as efficient as the original Spatial pyramid matching for images.

As we have seen, instead of considering word functions as an unordered collection of independent random values, it seems more reasonable to consider them as random functions defined on the vertices of a graph. We thus propose to use the 0-dimensional persistent homology to capture information regarding the global structure of the word functions which is not available for the traditional max-pooling approach. In this work, we aim at being able to use classification algorithms such as SVM or logistic regression requiring a Hilbert space structure, which the space of persistence diagrams lacks. One approach to tackle this issue is to make use of the "kernel trick" by using a positive-definite kernel in order to map the persistence diagrams into a Hilbert space. As recently shown by Reininghaus et al. [START_REF] Reininghaus | A Stable Multi-Scale Kernel for Topological Machine Learning[END_REF], one cannot rely on natural distances such as the Wasserstein distance to build traditional distance-based kernels. This led the authors to propose a new non-linear. But using a non-linear kernel increases the computational complexity of classification procedures leading to scalability issues. Another approach to directly embed persistence diagrams into a Hilbert Space was proposed in [START_REF] Bubenik | Statistical topology using persistence landscapes[END_REF] but this embedding is highly memoryconsuming as it maps a single diagram into a set of functions. It is thus not appropriate for dealing with large datasets.

In this work, we propose to perform pooling by computing the persistence diagrams of each word function. We then map these persistence diagrams into R d for some reasonable value of d -< 20-by considering the peaks with highest prominence. Since we provide a direct mapping of persistence diagrams into R d , we can use it for the pooling stage for the bag-of-words procedure and achieve good performance with respect to the classification phase. We call this pooling approach Topological Pooling. Since it relies on persistence diagrams, this method is stable with respect to most transformations the shape can undergo: translations, rotations, etc., as long as the descriptors used in input are also invariant to these transformations. Moreover, we show that this pooling approach is robust to perturbations of the descriptors. Finally we demonstrate the validity of our approach compared to both sum-pooling and max-pooling by performing pose recognition on the SHREC 2014 dataset.

Using persistence diagrams for pooling

Given a persistence diagram ∆, let us recall that the prominence p of a point (b, d) ∈ ∆ is defined by p = b -d. Given a function f on a graph G, we define the infinite-dimensional Topological Pooling vector of f with i -th coordinate given by T opoP ool(f ) i = p i (∆ f ), where p i (∆ f ) is the i-th highest prominence of the points of ∆ f if there is at least i points in ∆ f and 0 otherwise. The stability of persistence diagrams given in Equation 4.2 implies the stability of our our pooling scheme.

Proposition 34. Let G be a graph and f and g two real-valued functions on the vertices V of a graph G. Then, for any integer i > 0,

|T opoP ool(f ) i -T opoP ool(g) i | ≤ 2 sup x∈V |f (x) -g(x)|
Of course, in practice we cannot use an infinite-dimensional vector so we simply consider a truncation of this vector keeping the first n coordinates, we denote such a truncated pooling vector by "TopoPool-n". Using the notations of Section 6.1, given some n > 0, the pooling vectors (P i ) 1≤i≤M are vectors of dimension nK defined by P i = (TopoPool-n((C i ) 1 ), ..., TopoPool-n((C i ) K )).

Experiments

In this section we evaluate the sum-pooling, the max-pooling and our topological pooling approaches on the SHREC 2014 dataset "Shape Retrieval of Non-Rigid 3D Human Models" [START_REF]Shrec'14 track: Shape retrieval of non-rigid 3d human models[END_REF], which we modify by applying a random rotation to each shape. The dataset is composed of 400 meshes corresponding to 40 subjects taking 10 different poses and we wish to classify each of these meshes with respect to the pose taken by the subject. We consider both SIHKS features [START_REF] Michael | Scale-invariant heat kernel signatures for non-rigid shape recognition[END_REF] and curvature-based features corresponding to the unary features from [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF] and composed of 64. We use Sparse Coding [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF] for the coding step and the computation are performed using the SPAMS toolbox [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF]. Finally, the classification is performed using a Support Vector Machine. We use 3 shapes per class for the training set, 2 for the validation set and 5 for the testing set. We compare the traditional sum-pooling with our TopoPool-n with different values for n -remark that n = 1 is equivalent to max-pooling-and under different codebook sizes. As a baseline, we also display the results obtained using a rigid Iterated Closest Point (ICP) [START_REF] Besl | A method for registration of 3-d shapes[END_REF] along with a 1-nearest neighbour classification, which aims at iteratively minimizing the distance between two point clouds through rigid deformations. In our case it corresponds to finding the correct rotation to align the shapes as two shapes in a similar pose are close, however the approach can fail if it gets stuck in a local minimum and is not able to recover the correct rotation. We run the experiment a hundred times, selecting the training and testing sets at random. We display the mean accuracy over the multiple runs in Table 6.1.

Overall, and especially for the SIHKS features, the Topological Pooling scheme outperforms both max-pooling and to the sum-pooling. In the case of curvature features, Topological Pooling and sum-pooling gives similar accuracy results for large codebooks but in the case of smaller codebooks, Topological pooling gives much better results. It is interesting to notice that the gap between the different pooling scheme decreases as the size of the codebook increases. Indeed, the smaller the codebook is, the richer each CHAPTER 6. TOPOLOGICAL POOLING word function are in terms of topology -and thus the richer the corresponding persistence diagrams are-.

Chapter 7

Perspectives

In this thesis, we have mainly dealt with using and studying the convergence of random walks on random geometric graphs to diffusion processes.

In this context, we first designed a new soft clustering algorithm for the mode seeking framework using such random walks and we provided a way to bound the 2-Wasserstein distance between the invariant measure of random walks on random geometric graphs and the invariant measure of the limiting diffusion process. Yet, there are still many questions left unanswered, either linked to the algorithm we have proposed or regarding the converge of random walks itself.

Soft-clustering algorithm. There are two main issues regarding our soft clustering algorithm. The first one is related to the choice of the temperature parameter β. While we have shown that the evolution of the fuzziness of the clustering through the clustering entropy can give some intuition regarding interesting values of β, it is not clear whether this approach would be efficient for more complicated datasets. Finding a way to automatically select β would prove extremely useful. The second shortcoming of our algorithm is linked to the construction of the cluster cores: our definition is rather ad hoc and it would be interesting to find a more canonical one.

Pointwise convergence of the invariant measure of random walks on random geometric graphs. In this thesis, we have obtained bounds in terms of Wasserstein distance for the convergence of the invariant measures of random walks on random geometric graphs to the invariant measures of diffusion processes. However, this result is still far from the pointwise convergence that would be required to prove we can compute a density estimator from the invariant measures of random walks on random geometric graphs. As highlighted by [START_REF] Tatsunori | Metric recovery from directed unweighted graphs[END_REF], weak convergence or 2-Wasserstein 90 CHAPTER 7. PERSPECTIVES distance can be turned into pointwise convergence as long as the invariant measure is sufficiently regular. This sounds reasonable as the structure of random geometric graphs itself is rather regular. Yet, it is unclear how such a result could be obtained.

Stochastic homogenization.

Among the multiple open questions regarding the convergence of random walks on random geometric graphs, finding the minimal assumptions required for this convergence to hold is of first importance. As we have seen multiple times in this thesis, for the convergence to hold, the graph must be built in a certain way. Theorem 11 requires the window size h(n) to satisfy h n → 0 and nh d+2 n log n → 0. But, if we consider the convergence of the invariant measures on an -graph, with = h n , it is sufficient that h n → 0 and nh d n log n → 0 for the invariant measure to converge. Similarly, while most results regarding the convergence of the spectrum of graph Laplacians also requires the stronger assumption on the window size, it has been shown in [START_REF] García Trillos | A variational approach to the consistency of spectral clustering[END_REF] the weaker assumption was sufficient for this convergence to hold. Hence, one may wonder whether our results as well as other standard results regarding the convergence of random walks on random geometric graphs hold under the weaker assumption on the window size. In order to answer this question, it may be interesting to look into other approaches used to study random walks in random environments in general. For instance, results of stochastic homogenization [START_REF] Gloria | Qualitative and quantitative results in stochastic homogenization[END_REF] are of particular interest.

Stein's method and spectral convergence. It would also be interesting to see if Stein's method could be used to provide other results for the convergence of random walks to diffusion processes. For instance, let us consider the unidimensional Ornstein-Uhlenbeck semigroup (P t ) t≥0 and let L γ be its infinitesimal generator. Let L ν be the generator of a Markov chain with invariant measure ν and let ψ be the eigenvector corresponding to the first non-zero eigenvalue of L ν . The approach Chapter 5 relies on the fact that, for any test function φ, P t φ converges, as t goes to infinity, to φdγ. Now, let us recall that the first non-zero eigenvalue of L γ is 1 and the corresponding eigenfunction is the identity. For any φ such that φdγ = 0 and any x ∈ R, e t P t φ(x) converges, as t goes to infinity, to x( φydµ(y)). One may wonder whether it is possible to use this property to derive an interpolation scheme between ψ and x and obtain a bound on the distance between these two functions. More generally, we could wonder whether an approach similar to Stein's method could be used to prove the convergence of the spectra of a family of Markov chains to the spectrum of a diffusion process. For random walks on random geometric graphs, such a result may be used to obtain new bounds in the spectral convergence of the graph Laplacian.

1. 1 . MOTIVATION 3 Figure 1 . 1 :

 1311 Figure 1.1: Deux composantes fortement connectées liée par une seule arête.

Figure 2 . 1 :

 21 Figure 2.1: Two highly connected components linked by a single edge.

Figure 4 . 1 :

 41 Figure 4.1: Soft-clustering output for an unbalanced mixture of Gaussian measures. Red colors corresponds to the right cluster, blue to the left one, hence green points have similar membership to both clusters.

  n→∞ (n) = 0 while lim n→∞ (n) d+2 n log n = ∞.Suppose the density estimator fn satisfies, for any compact set U ⊂ R d and any η > 0,

  (a) The data. (b) Output of ToMATo. (c) Output for β = 0.2. (d) Output for β = 1. (e) Output for β = 2. (f) Evolution of H with respect to β.

Figure 4 . 2 :

 42 Figure 4.2: Output of our algorithm on a simple dataset composed of two overlapping clusters. For soft clustering, green corresponds to an equal membership to both clusters.

( a )

 a Output for β = 1. (b) Output for β = 0.28.(c) soft Spectral Clustering.

Figure 4 . 3 :

 43 Figure 4.3: Experiments on a cluttered spirals dataset.

Figure 4 . 4 :

 44 Figure 4.4: From left to right: (a) the dataset projected on the Ramachadran plot, (b) ToMATo output, (c) second highest membership obtained with our algorithm for β = 0.2

54 CHAPTER 5 .

 545 STEIN'S METHOD FOR DIFFUSION APPROXIMATION that, for any test function (i.e. compactly supported smooth function) φ, (xφ(x) -∇φ) γ(dx) = 0, (5.1)

3 . 1 ,

 31 E[Φ(F t ) | X = x] = P t Φ(x)is real analytic. Hence, since X and X have the same 5.4. GAUSSIAN MEASURE IN DIMENSION ONE 65 measure we have

Figure 6 . 1 :

 61 Figure 6.1: Example of a word function obtained on two different people in the same pose (left and middle) and on the same person in two different poses (middle and right).

Figure 6 . 2 :

 62 Figure 6.2: The real SHREC 2014 dataset

  |H k | p dγ 1 .Injecting this bound in Equation5.7, we are able to bound W p (ν, γ 1 ).

	1/p
	using the L p (γ 1 )-norm of the Hermite polynomials H k	p p,γ 1 =

R

Table 6 .

 6 1: Mean accuracy obtained on the SHREC 2014 dataset.

Sic.

Alias "Jules-de-chez-Smith-en-face".

Victime d'une aversion inexpliquée envers les poireaux, vraisemblablement causée par un ancien traumatisme.

Ceci n'est pas un anglicisme. i

Remerciements

Je souhaiterais tout d'abord remercier Frédéric Chazal pour son encadrement, et surtout sa patience envers ma prose, lors de ces années de thèse. Merci à Giovanni Peccati et Mikhail Belkin pour leur intért envers mes travaux et pour avoir pris le temps de rapporter cette thèse. Je remercie aussi Guillaume Charpiat, Jérôme Dedecker et Laurent Deucreusefond pour leur participation au jury de thèse. Je remercie également Steve Oudot, avec qui ce fut un plaisir de travailler. Je souhaite remercier Michel Ledoux et Yvik Swan pour les discussions enrichissantes que j'ai eu avec eux au sujet de mes travaux sur la méthode de Stein. Un grand merci aussi à Christine Biard pour m'avoir guidé au travers des méandres administratifs.

Ces trois années chez 1 Inria n'auraient sans doute pas été les même sans les autres membres de l'équipe et assimilés, notamment Etienne 2 mais aussi Ilaria 3 , Clément, Mathieu, Dorian, Eddie, Claire, Mickal et tous les autres. Sur un autre registre, je voudrais remercier Terry Pratchett dont les livres, et leur traduction par Patrick Couton, auront réussi à rendre agréable mes nombreuses heures de trajets en RER et de qui je garderai un goût prononcé pour les notes de bas de page. Enfin, un petit mot pour Adélaïde qui m'a supporté 4 lors de la rédaction du présent manuscrit.

CHAPTER 5. STEIN'S METHOD FOR DIFFUSION APPROXIMATION

Density approximation on k-nearest neighbor graphs

Let X 1 , . . . , X n be i.i.d. random variables on the flat torus T = (R/Z) d drawn from a measure µ with smooth density f . Let π be the invariant measure of a random walk on a k-nearest neighbor graph built on X n = X 1 , . . . , X n . As we have seen in Section 3.3, the random walk on the knearest neighbor graph converges to a diffusion process with generator

which admits a reversible measure with density proportional to f 1+2/d . The corresponding approximation timestep is

While T is not a domain of R d , the arguments used in Theorem 21 still hold, let us check its assumptions. As T is compact and f is smooth and strictly positive, f -2/d ∇ log f and f -2/d are smooth, hence, a CD(ρ, ∞) condition is verified for some ρ ∈ R. Moreover, for any > 0, π is a measure with strictly positive smooth density and thus finite Fisher information with respect to μ. Finally, the assumption of Lemma 22 is verified thanks to Corollary 2.2 [START_REF] Wang | Exponential Contraction in Wasserstein Distances for Diffusion Semigroups with Negative Curvature[END_REF].

Using Lemma 12 and Corollary 27 along with Lemma 22, we obtain the following result.

Proposition 28. There exists C > 0 such that, with probability

Analysis of lower order schemes for the Langevin Monte Carlo algorithm

Quite often in Bayesian statistics, one is interested in sampling points from a probability measure dµ = e -u dx on R d . Many Monte-Carlo algorithms have been proposed and analyzed to solve this task. We want to show how our result can be used to study the convergence rate of a simple Monte-Carlo algorithm.

The measure µ is a reversible measure for the diffusion process with infinitesimal generator L µ = -∇u.∇ + ∆.

CHAPTER 5. STEIN'S METHOD FOR DIFFUSION APPROXIMATION

ξ be an increment from state X. By computations of Subsection 5.6.3, if µ is log-concave and ∇u is Lipschitz continuous, then there exists C > 0 such that

Let us note that, using the coarse Ricci curvature framework introduced in [START_REF] Ollivier | Ricci curvature of markov chains on metric spaces[END_REF], it is possible to show that M n converges exponentially fast to π. Hence, using our result, it is possible to show that O( -2 d 4 log(1/ )) iterations are required to achieve an accuracy in Wasserstein distance between the measure sampled by the LMC algorithm and µ. We believe our result to be suboptimal due to the dependency on the dimension of the function f k defined in Proposition 20, we conjecture the correct complexity to be O( -2 d 2 log(1/ )).

Proofs

Proof of Proposition 20

By Theorem 3.2.4 [START_REF] Bakry | Analysis and Geometry of Markov Diffusion operators[END_REF], under a CD(ρ, ∞), we have for any compactly supported smooth function φ, ∇P t φ a ≤ e -ρt P t ∇φ a .

(5.9)

In order to prove the Proposition, we need to find an equivalent to the integration by parts used in the Gaussian case.

Lemma 30. Suppose L satisfies a CD(ρ, ∞) condition, then for all compactly supported smooth function φ, and any t > 0,

PROOFS

For j > 0, we have

and, for j < k 2 , taking

completes the proof.

Chapter 6 Topological Pooling

In this Chapter, we incorporate the concept of 0-dimensional persistence presented in Section 4.1.2 in the bag-of-words framework to perform shape recognition. This work was done in collaboration with Maks Ovsjanikov, Steve Oudot and Frédéric Chazal and was the subject of a publication in the 6th International Workshop on Computational Topology in Image Context [START_REF] Bonis | Persistence-based pooling for shape pose recognition[END_REF].

The bag-of-words pipeline

The bag-of-words approach consists of three main steps: feature extraction, coding and pooling. We assume that the input to the pipeline is a set of M 3D-shapes (G i ) i∈[1,M ] represented as triangle meshes with vertices

Feature extraction aims at deriving a meaningful representation of the shape: the feature function denoted as F i : V i → R N . These functions are usually obtained by computing local descriptors (such as HKS [START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF], SIHKS [START_REF] Michael | Scale-invariant heat kernel signatures for non-rigid shape recognition[END_REF], WKS [START_REF] Bay | Speeded-up robust features (surf)[END_REF], Shape-net features [START_REF] Masci | Shapenet: Convolutional neural networks on noneuclidean manifolds[END_REF], etc.) on each vertex of the mesh.

The purpose of coding is to decompose the values of the functions F i by projecting them on a set of points W = (w k ) k∈[|1,K|] ∈ R N called a codebook. This allows to replace each feature function by a family of functions (C i :

, called the word functions. In other words, for a coding procedure Coding and codebook W , the C i are defined through

There exist various coding methods, such as Vector Quantization [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF], Sparse Coding [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF], Locally Constrained Linear Coding [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], Fisher Kernel [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] or Supervector [START_REF] Zhou | Image classification using super-vector coding of local image descriptors[END_REF]. The codebook is usually computed using K-means but supervised codebook learning methods [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], [START_REF] Boureau | Learning mid-level features for recognition[END_REF] generally achieve bet-Titre : Algorithmes d'apprentissage statistique pour l'analyse géométrique et topologique de données Mots clés : Graphes géométriques aléatoires, marche aléatoires, partitionnement de données ou, méthode de Stein, homologie persistante, sac-de-mots Résumé : Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diusion.

Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données ou de type recherche de modes. Dans cet algorithme, on dénit les paquets en utilisant les propriétés d'un certain processus de diusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données.

Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite.

Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante an d'améliorer l'étape de "pooling" dans l'approche sac-de-mots" pour la reconnaissance de formes 3D.

Title: Statistical learning algorithms for geometric and topological data analysis Keywords: Random geometric graphs, random walks, soft clustering, Stein's method, persistent homology, bag-of-words Abstract: In this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diusion processes.

In the rst part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to dene clusters using the properties of a diusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its eciency on both real and synthetic data.

We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diusion process, we can expect their invariant measures to converge to the invariant measure of this diusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem.

In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes.