Nonparametric regression with graph Laplacians

Thu January 20th 2022, 4:30pm
Alden Green, Carnegie Mellon

Graph-based learning refers to a family of conceptually simple and scalable approaches, which can be applied across many tasks and domains. We consider methods for graph-based learning in a relatively classical setting: nonparametric regression with point-cloud data lying on a (possibly) low-dimensional data manifold embedded in Euclidean space. In this case, methods involving the Laplacian of an appropriately constructed neighborhood graph serve as discrete and computationally tractable approximations to “continuum methods” — that is, methods built with respect to continuous differential operators — that are well known to have excellent statistical properties. We derive theoretical guarantees showing that a pair of graph-based methods, Laplacian smoothing and Laplacian eigenmaps, inherit many of these properties: in particular, they achieve minimax optimal rates of convergence over natural smoothness classes. Indeed, perhaps surprisingly, we find that graph-based methods actually have superior properties than can be explained by tying them to standard continuum approaches. Motivated by this discrepancy, we propose new explanations that highlight some unusual properties of graph-based methods relative to more standard tools for regression.

Zoom Recording [SUNet/SSO authentication required]