Escaping the Curse of Dimensionality with a Tree-based Regressor

By Samory Kpotufe. 2009

21 citations recorded by the source corpus.

We present the first tree-based regressor whose convergence rate depends only on the intrinsic dimension of the data, namely its Assouad dimension. The regressor uses the RPtree partitioning procedure, a simple randomized variant of k-d trees.

Citations in the corpus

• k-NN Regression Adapts to Local Intrinsic Dimension (2011, methodology): “This has recently been shown to indeed be the case for methods such as kernel regression [6], tree-based regression [7] and variants of these methods [8].”
• Fast, smooth and adaptive regression in metric spaces (2009, background): “Later, [2] showed that a regressor based on the RPtree of [8] (a hierarchical partitioning procedure) is not only fast to evaluate, but is adaptive to Assouad dimension, a measure which captures notions such as manifold dimension and data sparsity.”