Rates of Convergence for Regression with the Graph Poly-Laplacian

2022/09/06 by Trillos, Nicolás García, Murray, Ryan, Thorpe, Matthew · 1 citation
#Analysis of PDEs (math.AP) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2209.02305

Abstract

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 \x_i\_i=1ⁿ and a set of noisy labels \y_i\_i=1ⁿ⊂ℝ we let u_n:\x_i\_i=1ⁿ→ℝ be the minimiser of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When y_i = g(x_i)+ξ_i, for iid noise ξ_i, and using the geometric random graph, we identify (with high probability) the rate of convergence of u_n 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.

Cited by

• Higher-Order Regularization Learning on Hypergraphs

Related

• Asymptotic behavior of ℓ_p-based Laplacian regularization in semi-supervised learning
• A maximum principle argument for the uniform convergence of graph Laplacian regressors
• Minimax Optimal Regression over Sobolev Spaces via Laplacian\n Regularization on Neighborhood Graphs
• Estimating a smooth function on a large graph by Bayesian Laplacian regularisation
• Analysis of p-Laplacian Regularization in Semi-Supervised Learning