This talk comprises two parts. In the first part, we revisit the problem of pointwise semi-supervised learning (SSL). Working on random geometric graphs (a.k.a point clouds) with few “labeled points”, our task is to propagate these labels to the rest of the point cloud. Algorithms that are based on the graph Laplacian often perform poorly in such pointwise learning tasks since minimizers develop localized spikes near labeled data. We introduce a class of graph-based higher order fractional Sobolev spaces (H^s) and establish their consistency in the large data limit, along with applications to the SSL problem. A crucial tool is recent convergence results for the spectrum of the graph Laplacian to that of a weighted Laplace-Beltrami operator in the continuum.
Obtaining optimal convergence rates for such spectra has so-far been an open question in stochastic homogenization. In the rest of the talk, we answer this question by obtaining optimal, state-of-the-art results for the case of a Poisson point cloud on a bounded domain in Euclidean space with Dirichlet or Neumann boundary conditions.
The first half is joint work with Dejan Slepcev (CMU), and the second half is joint work with Scott Armstrong (Courant).