Generalization bounds for function approximation from scattered noisy data
this paper we investigate the problem of providing error bounds for approximation of an unknown function from scattered, noisy data. This problem has particular relevance in the field of machine learning, where the unknown function represents the task that has to be learned and the scattered data represents the examples of this task. An obvious quantity of interest for us is the generalization error -- a measure of how much the result of the approximation scheme differs from the unknown function -- typically studied as a function of the number of data points. Since the data are randomly generated and noisy, the analysis of the generalization error necessarily involves statistical considerations in addition to the traditional approximation theoretic ones. In this paper, we show how the total generalization error can be decomposed into two parts: (1) an approximation component that exists due to the finite dimensionality of the manifold to which the approximating function belongs, and (2) an estimation component that is due to the finiteness of the randomly drawn data