# Rates of Convergence for Regression with the Graph Poly-Laplacian

arXiv: https://arxiv.org/abs/2209.02305 · HTML: https://mlsanity.com/paper/2209.02305/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 81 references that are in the map.
- First posted on arXiv 6 Sep 2022.

## Builds on (most cited first, 22 of 22)

- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon](https://mlsanity.com/paper/1812.11167/) (2018)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [A variational approach to the consistency of spectral clustering](https://mlsanity.com/paper/1508.01928/) (2015)
- [Continuum limit of total variation on point clouds](https://mlsanity.com/paper/1403.6355/) (2014)
- [The game theoretic p-Laplacian and semi-supervised learning with few labels](https://mlsanity.com/paper/1711.10144/) (2017)
- [Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithms](https://mlsanity.com/paper/1805.09450/) (2018)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates](https://mlsanity.com/paper/2006.02765/) (2020)
- [Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/1603.00564/) (2016)
- [Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data](https://mlsanity.com/paper/1710.10364/) (2017)
- [A maximum principle argument for the uniform convergence of graph Laplacian regressors](https://mlsanity.com/paper/1901.10089/) (2019)
- [Mumford-Shah functionals on graphs and their asymptotics](https://mlsanity.com/paper/1906.09521/) (2019)
- [The SPDE Approach to Mat'ern Fields: Graph Representations](https://mlsanity.com/paper/2004.08000/) (2020)
- [From graph cuts to isoperimetric inequalities: Convergence rates of Cheeger cuts on data clouds](https://mlsanity.com/paper/2004.09304/) (2020)
- [On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms](https://mlsanity.com/paper/1710.07702/) (2017)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme](https://mlsanity.com/paper/1304.4679/) (2013)
- [Continuum Limit of Posteriors in Graph Bayesian Inverse Problems](https://mlsanity.com/paper/1706.07193/) (2017)
- [Adaptive Non-Parametric Regression With the K-NN Fused Lasso](https://mlsanity.com/paper/1807.11641/) (2018)
- [Consistency of modularity clustering on random geometric graphs](https://mlsanity.com/paper/1604.03993/) (2016)

## Built on by (most cited first, 4 of 4)

- [Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression](https://mlsanity.com/paper/2311.00140/) (2023)
- [Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps](https://mlsanity.com/paper/2402.14985/) (2024)
- [Nonparametric regression on random geometric graphs sampled from submanifolds](https://mlsanity.com/paper/2405.20909/) (2024)
- [Higher-Order Regularization Learning on Hypergraphs](https://mlsanity.com/paper/2510.26533/) (2025)

## Abstract (arXiv)

In the (special) smoothing spline problem one considers a variational problem with a quadratic data fidelity penalty and Laplacian regularisation. Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. The methodology is readily adapted to graphs and here we consider graph poly-Laplacian regularisation in a fully supervised, non-parametric, noise corrupted, regression problem. In particular, given a dataset xii=1n and a set of noisy labels yii=1nsubsetℝ we let un:xii=1n→ℝ be the minimiser of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When yi = g(xi)+xii, for iid noise xii, and using the geometric random graph, we identify (with high probability) the rate of convergence of un to g in the large data limit n→∞. Furthermore, our rate, up to logarithms, coincides with the known rate of convergence in the usual smoothing spline model.