On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms

Abstract

A popular approach to semi-supervised learning proceeds by endowing the input data with a graph structure in order to extract geometric information and incorporate it into a Bayesian framework. We introduce new theory that gives appropriate scalings of graph parameters that provably lead to a well-defined limiting posterior as the size of the unlabeled data set grows. Furthermore, we show that these consistency results have profound algorithmic implications. When consistency holds, carefully designed graph-based Markov chain Monte Carlo algorithms are proved to have a uniform spectral gap, independent of the number of unlabeled inputs. Several numerical experiments corroborate both the statistical consistency and the algorithmic scalability established by the theory.

References in corpus (5)

• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
• Continuum limit of total variation on point clouds
• On a generalization of the preconditioned Crank-Nicolson Metropolis algorithm
• Asymptotic behavior of ${\ell }_p$-based Laplacian regularization in semi-supervised learning
• Convergence of Laplacian spectra from random samples

Cited by in corpus (5)

• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Data-Driven Forward Discretizations for Bayesian Inversion
• Local Regularization of Noisy Point Clouds: Improved Global Geometric Estimates and Data Analysis
• Kernel Methods for Bayesian Elliptic Inverse Problems on Manifolds
• Variational limits of k-NN graph based functionals on data clouds