Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
From MaRDI portal
Abstract: We study the consistency of Lipschitz learning on graphs in the limit of infinite unlabeled data and finite labeled data. Previous work has conjectured that Lipschitz learning is well-posed in this limit, but is insensitive to the distribution of the unlabeled data, which is undesirable for semi-supervised learning. We first prove that this conjecture is true in the special case of a random geometric graph model with kernel-based weights. Then we go on to show that on a random geometric graph with self-tuning weights, Lipschitz learning is in fact highly sensitive to the distribution of the unlabeled data, and we show how the degree of sensitivity can be adjusted by tuning the weights. In both cases, our results follow from showing that the sequence of learned functions converges to the viscosity solution of an -Laplace type equation, and studying the structure of the limiting equation.
Recommendations
- Continuum limit of Lipschitz learning on graphs
- Analysis of p-Laplacian regularization in semisupervised learning
- The game theoretic p-Laplacian and semi-supervised learning with few labels
- On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms
- Large data and zero noise limits of graph-based semi-supervised learning algorithms
Cites work
- A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions
- A PDE-based approach to nondominated sorting
- A tour of the theory of absolutely minimizing functions
- Advanced Lectures on Machine Learning
- Analysis of p-Laplacian regularization in semisupervised learning
- Concentration inequalities. A nonasymptotic theory of independence
- Continuum limit of total variation on point clouds
- Distance-based classification with Lipschitz functions
- Estimating Densities of Functions of Observations
- Finite difference methods for the infinity Laplace and \(p\)-Laplace equations
- Game theoretical methods in PDEs
- Graph Laplacians and their convergence on random neighborhood graphs
- scientific article; zbMATH DE number 1188557 (Why is no real title available?)
- scientific article; zbMATH DE number 1181255 (Why is no real title available?)
- Learning Theory
- Limits of Solutions ofp-Laplace Equations aspGoes to Infinity and Related Variational Problems
- Nonlinear elliptic partial differential equations and \(p\)-harmonic functions on graphs.
- Notes on the Stationary p-Laplace Equation
- On local \(U\)-statistic processes and the estimation of densities of functions of several sample variables
- Statistical Analysis and Modelling of Spatial Point Patterns
- The Euler equation and absolute minimizers of \(L^\infty\) functionals
- The game theoretic p-Laplacian and semi-supervised learning with few labels
- Tug-of-war and the infinity Laplacian
- Tug-of-war with noise: a game-theoretic view of the \(p\)-Laplacian
- Uniqueness of Lipschitz extensions: Minimizing the sup norm of the gradient
- User’s guide to viscosity solutions of second order partial differential equations
- Vector-valued optimal Lipschitz extensions
- Weighted nonlocal Laplacian on interpolation from sparse data
Cited in
(31)- Gromov-Hausdorff limit of Wasserstein spaces on point clouds
- Properly-weighted graph Laplacian for semi-supervised learning
- Iterative surrogate model optimization (ISMO): an active learning algorithm for PDE constrained optimization with deep neural networks
- Analysis and algorithms for \(\ell_p\)-based semi-supervised learning on graphs
- Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs
- Boundary estimation from point clouds: algorithms, guarantees and applications
- Function approximation via the subsampled Poincaré inequality
- Data-driven method to learn the most probable transition pathway and stochastic differential equation
- Rates of convergence for Laplacian semi-supervised learning with low labeling rates
- Continuum limit of Lipschitz learning on graphs
- The game theoretic p-Laplacian and semi-supervised learning with few labels
- Lipschitz regularity of graph Laplacians on random data clouds
- A continuum limit for the PageRank algorithm
- Multiscale elliptic PDE upscaling and function approximation via subsampled data
- On the convergence of physics informed neural networks for linear second-order elliptic and parabolic type PDEs
- Analysis of p-Laplacian regularization in semisupervised learning
- Convergence of Physics-Informed Neural Networks Applied to Linear Second-Order Elliptic Interface Problems
- Solving an inverse source problem by deep neural network method with convergence and error analysis
- Poisson Reweighted Laplacian Uncertainty Sampling for Graph-Based Active Learning
- The infinity Laplacian eigenvalue problem: reformulation and a numerical scheme
- Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
- Ratio convergence rates for Euclidean first-passage percolation: applications to the graph infinity Laplacian
- Manifold filter-combine networks
- The graph -Laplacian eigenvalue problem
- Numerical solution of a PDE arising from prediction with expert advice
- Hypergraph p-Laplacian regularization on point clouds for data interpolation
- Fast algorithms for _p-regression
- Discrete-to-continuum rates of convergence for nonlocal p-Laplacian evolution problems
- Improved multi-scale fusion network for solving non-smooth elliptic interface problems with applications
- An operator-splitting algorithm for the hypergraph p-Laplacian with applications to missing data recovery
- A note on absolutely minimal extensions in finite metric spaces
This page was built for publication: Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5025772)
