mlsanityData to 7 Oct 2026

Rates of Convergence for Regression with the Graph Poly-Laplacian

arXiv 2209.02305 ↗First posted 6 Sep 2022stat.ML cs.LG math.APcited by 4

Not on the map. Why?

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.

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

Builds on

22 of 81 references.

References · 22

  1. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  2. 2018Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operatorcited by 70
  3. 2018Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenoncited by 44
  4. 2017Analysis of p-Laplacian Regularization in Semi-Supervised Learningcited by 39
  5. 2015A variational approach to the consistency of spectral clusteringcited by 28
  6. 2014Continuum limit of total variation on point cloudscited by 24
  7. 2017The game theoretic p-Laplacian and semi-supervised learning with few labelscited by 22
  8. 2018Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithmscited by 22
  9. 2016Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smootherscited by 20
  10. 2020Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Ratescited by 18
  11. 2016Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learningcited by 16
  12. 2017Consistency of Lipschitz learning with infinite unlabeled data and finite labeled datacited by 15
10 more
  1. 2019A maximum principle argument for the uniform convergence of graph Laplacian regressorscited by 9
  2. 2019Mumford-Shah functionals on graphs and their asymptoticscited by 6
  3. 2020The SPDE Approach to Mat'ern Fields: Graph Representationscited by 6
  4. 2020From graph cuts to isoperimetric inequalities: Convergence rates of Cheeger cuts on data cloudscited by 6
  5. 2017On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithmscited by 5
  6. 2021Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphscited by 5
  7. 2013A Method Based on Total Variation for Network Modularity Optimization using the MBO Schemecited by 4
  8. 2017Continuum Limit of Posteriors in Graph Bayesian Inverse Problemscited by 4
  9. 2018Adaptive Non-Parametric Regression With the K-NN Fused Lassocited by 3
  10. 2016Consistency of modularity clustering on random geometric graphscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 1.

4 papers.

  1. 2023Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regressioncited by 5
  2. 2024Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmapscited by 2
  3. 2024Nonparametric regression on random geometric graphs sampled from submanifoldscited by 1
  4. 2025Higher-Order Regularization Learning on Hypergraphscited by 1