Timezone: »
Poster
Fast, smooth and adaptive regression in metric spaces
Samory Kpotufe
It was recently shown that certain nonparametric regressors can escape the curse of dimensionality in the sense that their convergence rates adapt to the intrinsic dimension of data (\cite{BL:65, SK:77}). We prove some stronger results in more general settings. In particular, we consider a regressor which, by combining aspects of both tree-based regression and kernel regression, operates on a general metric space, yields a smooth function, and evaluates in time $O(\log n)$. We derive a tight convergence rate of the form $n^{-2/(2+d)}$ where $d$ is the Assouad dimension of the input space.
Author Information
Samory Kpotufe (Princeton University)
More from the Same Authors
-
2018 Poster: PAC-Bayes Tree: weighted subtrees with guarantees »
Tin Nguyen · Samory Kpotufe -
2017 : Modal-sets, and density-based Clustering »
Samory Kpotufe -
2016 Workshop: Adaptive and Scalable Nonparametric Methods in Machine Learning »
Aaditya Ramdas · Arthur Gretton · Bharath Sriperumbudur · Han Liu · John Lafferty · Samory Kpotufe · Zoltán Szabó -
2014 Workshop: Modern Nonparametrics 3: Automating the Learning Pipeline »
Eric Xing · Mladen Kolar · Arthur Gretton · Samory Kpotufe · Han Liu · Zoltán Szabó · Alan Yuille · Andrew G Wilson · Ryan Tibshirani · Sasha Rakhlin · Damian Kozbur · Bharath Sriperumbudur · David Lopez-Paz · Kirthevasan Kandasamy · Francesco Orabona · Andreas Damianou · Wacha Bounliphone · Yanshuai Cao · Arijit Das · Yingzhen Yang · Giulia DeSalvo · Dmitry Storcheus · Roberto Valerio -
2014 Poster: Optimal rates for k-NN density and mode estimation »
Sanjoy Dasgupta · Samory Kpotufe -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2013 Poster: Regression-tree Tuning in a Streaming Setting »
Samory Kpotufe · Francesco Orabona -
2013 Poster: Adaptivity to Local Smoothness and Dimension in Kernel Regression »
Samory Kpotufe · Vikas K Garg -
2013 Spotlight: Regression-tree Tuning in a Streaming Setting »
Samory Kpotufe · Francesco Orabona -
2012 Poster: Gradient Weights help Nonparametric Regressors »
Samory Kpotufe · Abdeslam Boularias -
2012 Oral: Gradient Weights help Nonparametric Regressors »
Samory Kpotufe · Abdeslam Boularias -
2011 Poster: k-NN Regression Adapts to Local Intrinsic Dimension »
Samory Kpotufe -
2011 Oral: k-NN Regression Adapts to Local Intrinsic Dimension »
Samory Kpotufe