Analysis and algorithms for $\ell_p$-based semi-supervised learning on graphs. (arXiv:1901.05031v3 [math.NA] UPDATED)

This paper addresses theory and applications of $\ell_p$-based Laplacian
regularization in semi-supervised learning. The graph $p$-Laplacian for $p>2$
has been proposed recently as a replacement for the standard ($p=2$) graph
Laplacian in semi-supervised learning problems with very few labels, where
Laplacian learning is degenerate.

In the first part of the paper we prove new discrete to continuum convergence
results for $p$-Laplace problems on $k$-nearest neighbor ($k$-NN) graphs, which
are more commonly used in practice than random geometric graphs. Our analysis …

algorithms analysis arxiv graphs learning math semi-supervised learning supervised learning