Risk bounds for random regression graphs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

3 Scopus Citations
View graph of relations

Detail(s)

Original languageEnglish
Pages (from-to)495-528
Journal / PublicationFoundations of Computational Mathematics
Volume7
Issue number4
Publication statusPublished - Nov 2007
Externally publishedYes

Abstract

We consider the regression problem and describe an algorithm approximating the regression function by estimators piecewise constant on the elements of an adaptive partition. The partitions are iteratively constructed by suitable random merges and splits, using cuts of arbitrary geometry. We give a risk bound under the assumption that a "weak learning hypothesis" holds, and characterize this hypothesis in terms of a suitable RKHS. Two examples illustrate the general results in two particularly interesting cases. © 2007 Society for Foundations of Computational Mathematics.

Research Area(s)

  • Regression graph, Reproducing kernel Hilbert space, Risk bound, Weak learning hypothesis