nips nips2013 nips2013-269 nips2013-269-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Samory Kpotufe, Francesco Orabona
Abstract: We consider the problem of maintaining the data-structures of a partition-based regression procedure in a setting where the training data arrives sequentially over time. We prove that it is possible to maintain such a structure in time O (log n) at ˜ any time step n while achieving a nearly-optimal regression rate of O n−2/(2+d) in terms of the unknown metric dimension d. Finally we prove a new regression lower-bound which is independent of a given data size, and hence is more appropriate for the streaming setting. 1
[1] Y. Ben-Haim and E. Tom-Tov. A streaming parallel decision tree algorithm. Journal of Machine Learning Research, 11:849–872, 2010.
[2] A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbors. ICML, 2006.
[3] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, New York, NY, USA, 2006.
[4] K. Clarkson. Nearest-neighbor searching and metric space dimensions. Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, 2005.
[5] P. Domingos and G. Hulten. Mining high-speed data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 71–80, 2000.
[6] H. Gu and J. Lafferty. Sequential nonparametric regression. ICML, 2012.
[7] L. Gyorfi, M. Kohler, A. Krzyzak, and H. Walk. A Distribution Free Theory of Nonparametric Regression. Springer, New York, NY, 2002.
[8] A. Kalai and S. Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research, 3:423–440, 2002.
[9] S. Kpotufe. k-NN Regression Adapts to Local Intrinsic Dimension. NIPS, 2011.
[10] R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’04, pages 798–807, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.
[11] B. Pfahringer, G. Holmes, and R. Kirkby. Handling numeric attributes in hoeffding trees. In Advances in Knowledge Discovery and Data Mining: Proceedings of the 12th Pacific-Asia Conference (PAKDD), volume 5012, pages 296–307. Springer, 2008.
[12] S. Schaal and C. Atkeson. Robot Juggling: An Implementation of Memory-based Learning. Control Systems Magazine, IEEE, 1994.
[13] C. J. Stone. Optimal rates of convergence for non-parametric estimators. Ann. Statist., 8:1348– 1360, 1980.
[14] C. J. Stone. Optimal global rates of convergence for non-parametric estimators. Ann. Statist., 10:1340–1353, 1982.
[15] M. A. Taddy, R. B. Gramacy, and N. G. Polson. Dynamic trees for learning and design. Journal of the American Statistical Association, 106(493), 2011.
[16] S. Vijayakumar and S. Schaal. Locally weighted projection regression: An O(n) algorithm for incremental real time learning in high dimensional space. In in Proceedings of the Seventeenth International Conference on Machine Learning (ICML), pages 1079–1086, 2000. 9