The game theoretic p-Laplacian and semi-supervised learning with few labels

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

We study the game theoretic p-Laplacian for semi-supervised learning on graphs, and show that it is well-posed in the limit of finite labeled data and infinite unlabeled data. In particular, we show that the continuum limit of graph-based semi-supervised learning with the game theoretic p-Laplacian is a weighted version of the continuous p-Laplace equation. We also prove that solutions to the graph p-Laplace equation are approximately Hölder continuous with high probability. Our proof uses the viscosity solution machinery and the maximum principle on a graph.

Original languageEnglish (US)
Pages (from-to)301-330
Number of pages30
JournalNonlinearity
Volume32
Issue number1
DOIs
StatePublished - Jan 1 2019

Fingerprint

Semi-supervised Learning
Laplace equation
Supervised learning
games
P-Laplacian
learning
Labels
Game
maximum principle
P-Laplace Equation
Maximum principle
machinery
Graph in graph theory
Machinery
Viscosity
viscosity
continuums
Continuum Limit
Viscosity Solutions
Maximum Principle

Keywords

  • consistency
  • continuum limit
  • game theoretic p-Laplacian
  • maximum principle
  • probability
  • semi-supervised learning
  • viscosity solutions

Cite this

The game theoretic p-Laplacian and semi-supervised learning with few labels. / Calder, Jeffrey W.

In: Nonlinearity, Vol. 32, No. 1, 01.01.2019, p. 301-330.

Research output: Contribution to journalArticle

@article{268f98424766406bae81ec42aba5db40,
title = "The game theoretic p-Laplacian and semi-supervised learning with few labels",
abstract = "We study the game theoretic p-Laplacian for semi-supervised learning on graphs, and show that it is well-posed in the limit of finite labeled data and infinite unlabeled data. In particular, we show that the continuum limit of graph-based semi-supervised learning with the game theoretic p-Laplacian is a weighted version of the continuous p-Laplace equation. We also prove that solutions to the graph p-Laplace equation are approximately H{\"o}lder continuous with high probability. Our proof uses the viscosity solution machinery and the maximum principle on a graph.",
keywords = "consistency, continuum limit, game theoretic p-Laplacian, maximum principle, probability, semi-supervised learning, viscosity solutions",
author = "Calder, {Jeffrey W}",
year = "2019",
month = "1",
day = "1",
doi = "10.1088/1361-6544/aae949",
language = "English (US)",
volume = "32",
pages = "301--330",
journal = "Nonlinearity",
issn = "0951-7715",
publisher = "IOP Publishing Ltd.",
number = "1",

}

TY - JOUR

T1 - The game theoretic p-Laplacian and semi-supervised learning with few labels

AU - Calder, Jeffrey W

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We study the game theoretic p-Laplacian for semi-supervised learning on graphs, and show that it is well-posed in the limit of finite labeled data and infinite unlabeled data. In particular, we show that the continuum limit of graph-based semi-supervised learning with the game theoretic p-Laplacian is a weighted version of the continuous p-Laplace equation. We also prove that solutions to the graph p-Laplace equation are approximately Hölder continuous with high probability. Our proof uses the viscosity solution machinery and the maximum principle on a graph.

AB - We study the game theoretic p-Laplacian for semi-supervised learning on graphs, and show that it is well-posed in the limit of finite labeled data and infinite unlabeled data. In particular, we show that the continuum limit of graph-based semi-supervised learning with the game theoretic p-Laplacian is a weighted version of the continuous p-Laplace equation. We also prove that solutions to the graph p-Laplace equation are approximately Hölder continuous with high probability. Our proof uses the viscosity solution machinery and the maximum principle on a graph.

KW - consistency

KW - continuum limit

KW - game theoretic p-Laplacian

KW - maximum principle

KW - probability

KW - semi-supervised learning

KW - viscosity solutions

UR - http://www.scopus.com/inward/record.url?scp=85059930987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059930987&partnerID=8YFLogxK

U2 - 10.1088/1361-6544/aae949

DO - 10.1088/1361-6544/aae949

M3 - Article

AN - SCOPUS:85059930987

VL - 32

SP - 301

EP - 330

JO - Nonlinearity

JF - Nonlinearity

SN - 0951-7715

IS - 1

ER -