Minimax lower bounds for function estimation on graphs

DOI10.1214/18-EJS1407zbMATH Open1388.62097arXiv1709.06360WikidataQ130192967 ScholiaQ130192967MaRDI QIDQ1746533FDOQ1746533

Authors: Alisa A. Kirichenko, Harry van Zanten 

Publication date: 25 April 2018

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: We study minimax lower bounds for function estimation problems on large graph when the target function is smoothly varying over the graph. We derive minimax rates in the context of regression and classification problems on graphs that satisfy an asymptotic shape assumption and with a smoothness condition on the target function, both formulated in terms of the graph Laplacian.

Full work available at URL: https://arxiv.org/abs/1709.06360

Recommendations

• Estimating a smooth function on a large graph by Bayesian Laplacian regularisation
• Low rank estimation of smooth kernels on graphs
• Lower bounds in estimation at a point under multi-index constraint
• Optimal Bayesian smoothing of functional observations over a large graph
• Low rank estimation of similarities on graphs

zbMATH Keywords

minimax lower boundsfunction estimation on graphs

Mathematics Subject Classification ID

Density estimation (62G07) Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Kernels and regularization on graphs.
• Statistical analysis of network data. Methods and models
• Introduction to nonparametric estimation
• An introduction to the theory of graph spectra
• Laplacian graph eigenvectors
• Estimating a smooth function on a large graph by Bayesian Laplacian regularisation
• On the effectiveness of Laplacian normalization for graph semi-supervised learning
• Learning Theory
• Nonparametric Bayesian label prediction on a graph
• Uncertainty quantification in graph-based classification of high dimensional data

Cited In (5)

• Graph theoretic uncertainty and feasibility
• Low rank estimation of similarities on graphs
• A common variable minimax theorem for graphs
• Optimal Bayesian smoothing of functional observations over a large graph
• Error analysis for denoising smooth modulo signals on a graph

This page was built for publication: Minimax lower bounds for function estimation on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1746533)