Asymptotic behavior of ${\ell }_p$-based Laplacian regularization in semi-supervised learning

Abstract

Given a weighted graph with $N$ vertices, consider a real-valued regression problem in a semi-supervised setting, where one observes $n$ labeled vertices, and the task is to label the remaining ones. We present a theoretical study of ${\ell }_p$-based Laplacian regularization under a $d$-dimensional geometric random graph model. We provide a variational characterization of the performance of this regularized learner as $N$ grows to infinity while $n$ stays constant, the associated optimality conditions lead to a partial differential equation that must be satisfied by the associated function estimate $\hat{f}$. From this formulation we derive several predictions on the limiting behavior the $d$-dimensional function $\hat{f}$, including (a) a phase transition in its smoothness at the threshold $p=d+1$, and (b) a tradeoff between smoothness and sensitivity to the underlying unlabeled data distribution $P$. Thus, over the range $p\le d$, the function estimate $\hat{f}$ is degenerate and "spiky," whereas for $p\ge d+1$, the function estimate $\hat{f}$ is smooth. We show that the effect of the underlying density vanishes monotonically with $p$, such that in the limit $p=\infty$, corresponding to the so-called Absolutely Minimal Lipschitz Extension, the estimate $\hat{f}$ is independent of the distribution $P$. Under the assumption of semi-supervised smoothness, ignoring $P$ can lead to poor statistical performance, in particular, we construct a specific example for $d=1$ to demonstrate that $p=2$ has lower risk than $p=\infty$ due to the former penalty adapting to $P$ and the latter ignoring it. We also provide simulations that verify the accuracy of our predictions for finite sample sizes. Together, these properties show that $p=d+1$ is an optimal choice, yielding a function estimate $\hat{f}$ that is both smooth and non-degenerate, while remaining maximally sensitive to $P$.

References in corpus (2)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• An easy proof of Jensen's theorem on the uniqueness of infinity harmonic functions

Cited by in corpus (15)

• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• A Sampling Theory Perspective of Graph-based Semi-supervised Learning
• Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
• Uniform Convergence Rates for Lipschitz Learning on Graphs
• Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
• On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms
• On the Duality between Network Flows and Network Lasso
• A continuum limit for the PageRank algorithm
• Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing
• High-dimensional semi-supervised learning: in search for optimal inference of the mean
• Nonlocal $p$-Laplacian Variational problems on graphs
• Variational limits of k-NN graph based functionals on data clouds
• Learning phase transitions by siamese neural network
• Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning
• Fourier-domain Variational Formulation and Its Well-posedness for Supervised Learning