Risk bounds for random regression graphs

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations


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


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