Convergence rates for Poisson learning to a Poisson equation with measure data
This work provides theoretical guarantees for a semi-supervised learning algorithm, addressing a foundational mathematical challenge in machine learning.
The paper tackles the problem of proving discrete to continuum convergence rates for Poisson Learning, a graph-based semi-supervised learning algorithm, by analyzing it as a Poisson equation with measure data, and obtains convergence rates scaling as O(ε^(1/(d+2))) for general data distributions and O(ε^((2-σ)/(d+4))) for uniformly distributed data, up to logarithmic factors.
In this paper we prove discrete to continuum convergence rates for Poisson Learning, a graph-based semi-supervised learning algorithm that is based on solving the graph Poisson equation with a source term consisting of a linear combination of Dirac deltas located at labeled points and carrying label information. The corresponding continuum equation is a Poisson equation with measure data in a Euclidean domain $Ω\subset \mathbb{R}^d$. The singular nature of these equations is challenging and requires an approach with several distinct parts: (1) We prove quantitative error estimates when convolving the measure data of a Poisson equation with (approximately) radial function supported on balls. (2) We use quantitative variational techniques to prove discrete to continuum convergence rates on random geometric graphs with bandwidth $\varepsilon>0$ for bounded source terms. (3) We show how to regularize the graph Poisson equation via mollification with the graph heat kernel, and we study fine asymptotics of the heat kernel on random geometric graphs. Combining these three pillars we obtain $L^1$ convergence rates that scale, up to logarithmic factors, like $O(\varepsilon^{\frac{1}{d+2}})$ for general data distributions, and $O(\varepsilon^{\frac{2-σ}{d+4}})$ for uniformly distributed data, where $σ>0$. These rates are valid with high probability if $\varepsilon\gg\left({\log n}/{n}\right)^q$ where $n$ denotes the number of vertices of the graph and $q \approx \frac{1}{3d}$.