A tree-based regressor that adapts to intrinsic dimension

Samory Kpotufe, Sanjoy Dasgupta

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


We consider the problem of nonparametric regression, consisting of learning an arbitrary mapping f:X→Y from a data set of (x,y) pairs in which the y values are corrupted by noise of mean zero. This statistical task is known to be subject to a severe curse of dimensionality: if X⊂RD, and if the only smoothness assumption on f is that it satisfies a Lipschitz condition, it is known that any estimator based on n data points will have an error rate (risk) of Ω(n-2/(2+D)). Here we present a tree-based regressor whose risk depends only on the doubling dimension of X, not on D. This notion of dimension generalizes two cases of contemporary interest: when X is a low-dimensional manifold, and when X is sparse. The tree is built using random hyperplanes as splitting criteria, building upon recent work of Dasgupta and Freund (2008) [5]; and we show that axis-parallel splits cannot achieve the same finite-sample rate of convergence.

Original languageAmerican English
Pages (from-to)1496-1515
Number of pages20
JournalJournal of Computer and System Sciences
Issue number5
StatePublished - Sep 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Manifold
  • Nonparametric regression
  • Notions of dimension
  • Sparse data


Dive into the research topics of 'A tree-based regressor that adapts to intrinsic dimension'. Together they form a unique fingerprint.

Cite this