Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian

Abstract

In this paper we give a broad overview of the intersection of partial differential equations (PDEs) and graph-based semi-supervised learning. The overview is focused on a large body of recent work on PDE continuum limits of graph-based learning, which have been used to prove well-posedness of semi-supervised learning algorithms in the large data limit. We highlight some interesting research directions revolving around consistency of graph-based semi-supervised learning, and present some new results on the consistency of $p$-Laplacian semi-supervised learning using the stochastic tug-of-war game interpretation of the $p$-Laplacian. We also present the results of some numerical experiments that illustrate our results and suggest directions for future work.