Center for Nonlinear Analysis
CNA Home
People
Seminars
Publications
Workshops and Conferences
CNA Working Groups
CNA Comments Form
Summer Schools
Summer Undergraduate Institute
PIRE
Cooperation
Graduate Topics Courses
SIAM Chapter Seminar
Positions
Contact |
Publication 17-CNA-012
Dejan Slepčev Matthew Thorpe Abstract: We investigate a family of regression problems in a semi-supervised setting. The task is
to assign real-valued labels to a set of n sample points, provided a small training subset of N
labeled points. A goal of semi-supervised learning is to take advantage of the (geometric) structure
provided by the large number of unlabeled data when assigning labels. We consider a random
geometric graph, with connection radius $\varepsilon (n)$, to represent the geometry of the data set. We study
objective functions which reward the regularity of the estimator function and impose or reward the
agreement with the training data. In particular we consider discrete p-Laplacian regularization.
We investigate asymptotic behavior in the limit where the number of unlabeled points increases
while the number of training points remains fixed. We uncover a delicate interplay between
the regularizing nature of the functionals considered and the nonlocality inherent to the graph
constructions. We rigorously obtain almost optimal ranges on the scaling of $\varepsilon (n)$ for the asymptotic
consistency to hold. We discover that for standard approaches used thus far there is a restrictive
upper bound on how quickly $\varepsilon (n)$ must converge to zero as $n \rightarrow \infty$. Furthermore we introduce a
new model which overcomes this restriction. It is as simple as the standard models, but converges
as soon as $\varepsilon (n) \rightarrow$ 0 as $n \rightarrow \infty$.Get the paper in its entirety as 17-CNA-012.pdf |