Continuum Limit of Lipschitz Learning on Graphs

Abstract

Tackling semi-supervised learning problems with graph-based methods has become a trend in recent years since graphs can represent all kinds of data and provide a suitable framework for studying continuum limits, e.g., of differential operators. A popular strategy here is $p$-Laplacian learning, which poses a smoothness condition on the sought inference function on the set of unlabeled data. For $p<\infty$ continuum limits of this approach were studied using tools from $\Gamma$-convergence. For the case $p=\infty$, which is referred to as Lipschitz learning, continuum limits of the related infinity-Laplacian equation were studied using the concept of viscosity solutions. In this work, we prove continuum limits of Lipschitz learning using $\Gamma$-convergence. In particular, we define a sequence of functionals which approximate the largest local Lipschitz constant of a graph function and prove $\Gamma$-convergence in the $L^{\infty }$-topology to the supremum norm of the gradient as the graph becomes denser. Furthermore, we show compactness of the functionals which implies convergence of minimizers. In our analysis we allow a varying set of labeled data which converges to a general closed set in the Hausdorff distance. We apply our results to nonlinear ground states, i.e., minimizers with constrained $L^p$-norm, and, as a by-product, prove convergence of graph distance functions to geodesic distance functions.

arXiv comment39 pages, added acknowledgement, corrected typos

References in corpus (9)

• Consistency of spectral clustering
• Continuum limit of total variation on point clouds
• Gamma-convergence of graph Ginzburg-Landau functionals
• Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates
• Algorithms for Lipschitz Learning on Graphs
• Asymptotic Profiles of Nonlinear Homogeneous Evolution Equations of Gradient Flow Type
• Uniform Convergence Rates for Lipschitz Learning on Graphs
• Structural analysis of an $L$-infinity variational problem and relations to distance functions
• The Infinity Laplacian eigenvalue problem: reformulation and a numerical scheme

Cited by in corpus (7)

• Uniform Convergence Rates for Lipschitz Learning on Graphs
• On a Class of Nonlocal Continuity Equations on Graphs
• Gradient Flows and Nonlinear Power Methods for the Computation of Nonlinear Eigenfunctions
• Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning
• The Infinity Laplacian eigenvalue problem: reformulation and a numerical scheme
• Ratio convergence rates for Euclidean first-passage percolation: Applications to the graph infinity Laplacian
• Limits and consistency of non-local and graph approximations to the Eikonal equation