Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates

• URL: http://arxiv.org/abs/2006.02765v1
• Date: Thu, 4 Jun 2020 10:46:01 GMT
• Title: Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates
• Authors: Jeff Calder, Dejan Slep\v{c}ev and Matthew Thorpe
• Abstract summary: We study graph-based Laplacian semi-supervised learning at low labeling rates. At very low label rates, Laplacian learning becomes degenerate and the solution is roughly constant with spikes at each labeled data point.
• Score: 3.867363075280544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study graph-based Laplacian semi-supervised learning at low labeling rates. Laplacian learning uses harmonic extension on a graph to propagate labels. At very low label rates, Laplacian learning becomes degenerate and the solution is roughly constant with spikes at each labeled data point. Previous work has shown that this degeneracy occurs when the number of labeled data points is finite while the number of unlabeled data points tends to infinity. In this work we allow the number of labeled data points to grow to infinity with the number of labels. Our results show that for a random geometric graph with length scale $\varepsilon>0$ and labeling rate $\beta>0$, if $\beta \ll\varepsilon^2$ then the solution becomes degenerate and spikes form, and if $\beta\gg \varepsilon^2$ then Laplacian learning is well-posed and consistent with a continuum Laplace equation. Furthermore, in the well-posed setting we prove quantitative error estimates of $O(\varepsilon\beta^{-1/2})$ for the difference between the solutions of the discrete problem and continuum PDE, up to logarithmic factors. We also study $p$-Laplacian regularization and show the same degeneracy result when $\beta \ll \varepsilon^p$. The proofs of our well-posedness results use the random walk interpretation of Laplacian learning and PDE arguments, while the proofs of the ill-posedness results use $\Gamma$-convergence tools from the calculus of variations. We also present numerical results on synthetic and real data to illustrate our results.

Related papers

• Convergence rates for Poisson learning to a Poisson equation with measure data [2.7961972519572447]
  We prove discrete to continuum convergence rates for Poisson Learning, a graph-based semi-supervised learning algorithm. We show how to regularize the graph Poisson equation via mollification with the graph heat kernel. We obtain convergence rates that scale up to logarithmic factors, like $O(varepsilonfrac1d+2)$ for general data distributions, and $O(varepsilonfrac2-sigmad+4)$ for uniformly distributed data.
  arXiv  Detail & Related papers  (2024-07-09T11:54:34Z)
• Hypergraph $p$-Laplacian regularization on point clouds for data interpolation [3.79830302036482]
  Hypergraphs are widely used to model higher-order relations in data. We define the $varepsilon_n$-ball hypergraph and the $k_n$-nearest neighbor hypergraph on a point cloud. We prove the variational consistency between the hypergraph $p$-Laplacian regularization and the $p$-Laplacian regularization in a semi-supervised setting.
  arXiv  Detail & Related papers  (2024-05-02T09:17:32Z)
• Continuum limit of $p$-biharmonic equations on graphs [3.79830302036482]
  The behavior of the solution is investigated when the random geometric graph is considered and the number of data points goes to infinity. We show that the continuum limit is an appropriately weighted $p$-biharmonic equation with homogeneous Neumann boundary conditions.
  arXiv  Detail & Related papers  (2024-04-30T16:29:44Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm? [73.80001705134147]
  We provide an exact characterization of the expected generalization error (gen-error) for semi-supervised learning (SSL) with pseudo-labeling via the Gibbs algorithm. The gen-error is expressed in terms of the symmetrized KL information between the output hypothesis, the pseudo-labeled dataset, and the labeled dataset.
  arXiv  Detail & Related papers  (2022-10-15T04:11:56Z)
• Rates of Convergence for Regression with the Graph Poly-Laplacian [3.222802562733786]
  Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. We consider graph poly-Laplacian regularisation in a fully supervised, non-parametric, noise corrupted, regression problem.
  arXiv  Detail & Related papers  (2022-09-06T08:59:15Z)
• Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise [10.418647759223965]
  Bi-stochastic normalization provides an alternative normalization of graph Laplacians in graph-based data analysis. We prove the convergence of bi-stochastically normalized graph Laplacian to manifold (weighted-)Laplacian with rates. When the manifold data are corrupted by outlier noise, we theoretically prove the graph Laplacian point-wise consistency.
  arXiv  Detail & Related papers  (2022-06-22T21:08:24Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels. When restricting labels $x_i$ to binary values, the problem is NP-hard. We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
  arXiv  Detail & Related papers  (2021-06-03T07:22:48Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.