Extra Seminar Mathematics - Dr. A.Kirichenko

Title: Function estimation on large graphs

Abstract:
In recent years there has been substantial interest in high-dimensional estimation and prediction problems in the context of relational data. These can in many cases be viewed as high-dimensional or nonparametric regression or classification problems in which the goal is to learn a "smooth" function on a given graph. We present a mathematical framework that allows to study the performance of nonparametric function estimation methods on large graphs and derive the minimax convergence rates within the framework. We consider graphs that satisfy an assumption on their "asymptotic geometry", formulated in terms of the graph Laplacian. We also introduce a Sobolev-type smoothness condition on the target function using the graph Laplacian to quantify smoothness. Finally, we present Bayesian estimation procedures and show how they achieve (asymptotically) optimal regularization.