Timezone: »
Spotlight
Regression-tree Tuning in a Streaming Setting
Samory Kpotufe · Francesco Orabona
Sat Dec 07 11:52 AM -- 11:56 AM (PST) @ Harvey's Convention Center Floor, CC
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 $\tilde{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.
Author Information
Samory Kpotufe (Princeton University)
Francesco Orabona (Boston University)
Related Events (a corresponding poster, oral, or spotlight)
-
2013 Poster: Regression-tree Tuning in a Streaming Setting »
Sun. Dec 8th 03:00 -- 07:59 AM Room Harrah's Special Events Center, 2nd Floor
More from the Same Authors
-
2022 Poster: Robustness to Unbounded Smoothness of Generalized SignSGD »
Michael Crawshaw · Mingrui Liu · Francesco Orabona · Wei Zhang · Zhenxun Zhuang -
2021 Poster: Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers »
Jeffrey Negrea · Blair Bilodeau · Nicolò Campolongo · Francesco Orabona · Dan Roy -
2020 Poster: Temporal Variability in Implicit Online Learning »
Nicolò Campolongo · Francesco Orabona -
2019 Poster: Momentum-Based Variance Reduction in Non-Convex SGD »
Ashok Cutkosky · Francesco Orabona -
2019 Poster: Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration »
Kwang-Sung Jun · Ashok Cutkosky · Francesco Orabona -
2018 Poster: PAC-Bayes Tree: weighted subtrees with guarantees »
Tin Nguyen · Samory Kpotufe -
2017 : Modal-sets, and density-based Clustering »
Samory Kpotufe -
2017 Poster: Training Deep Networks without Learning Rates Through Coin Betting »
Francesco Orabona · Tatiana Tommasi -
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ó -
2016 Poster: Coin Betting and Parameter-Free Online Learning »
Francesco Orabona · David Pal -
2014 Workshop: Second Workshop on Transfer and Multi-Task Learning: Theory meets Practice »
Urun Dogan · Tatiana Tommasi · Yoshua Bengio · Francesco Orabona · Marius Kloft · Andres Munoz · Gunnar Rätsch · Hal Daumé III · Mehryar Mohri · Xuezhi Wang · Daniel Hernández-lobato · Song Liu · Thomas Unterthiner · Pascal Germain · Vinay P Namboodiri · Michael Goetz · Christopher Berlind · Sigurd Spieckermann · Marta Soare · Yujia Li · Vitaly Kuznetsov · Wenzhao Lian · Daniele Calandriello · Emilie Morvant -
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: Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning »
Francesco Orabona -
2014 Poster: Optimal rates for k-NN density and mode estimation »
Sanjoy Dasgupta · Samory Kpotufe -
2013 Workshop: New Directions in Transfer and Multi-Task: Learning Across Domains and Tasks »
Urun Dogan · Marius Kloft · Tatiana Tommasi · Francesco Orabona · Massimiliano Pontil · Sinno Jialin Pan · Shai Ben-David · Arthur Gretton · Fei Sha · Marco Signoretto · Rajhans Samdani · Yun-Qian Miao · Mohammad Gheshlaghi azar · Ruth Urner · Christoph Lampert · Jonathan How -
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: Dimension-Free Exponentiated Gradient »
Francesco Orabona -
2013 Spotlight: Dimension-Free Exponentiated Gradient »
Francesco Orabona -
2013 Poster: Adaptivity to Local Smoothness and Dimension in Kernel Regression »
Samory Kpotufe · Vikas K Garg -
2012 Poster: On Multilabel Classification and Ranking with Partial Feedback »
Claudio Gentile · Francesco Orabona -
2012 Poster: Gradient Weights help Nonparametric Regressors »
Samory Kpotufe · Abdeslam Boularias -
2012 Oral: Gradient Weights help Nonparametric Regressors »
Samory Kpotufe · Abdeslam Boularias -
2012 Spotlight: On Multilabel Classification and Ranking with Partial Feedback »
Claudio Gentile · Francesco Orabona -
2011 Poster: k-NN Regression Adapts to Local Intrinsic Dimension »
Samory Kpotufe -
2011 Oral: k-NN Regression Adapts to Local Intrinsic Dimension »
Samory Kpotufe -
2010 Poster: New Adaptive Algorithms for Online Classification »
Francesco Orabona · Yacov Crammer -
2010 Spotlight: Learning from Candidate Labeling Sets »
Jie Luo · Francesco Orabona -
2010 Poster: Learning from Candidate Labeling Sets »
Jie Luo · Francesco Orabona -
2009 Workshop: Learning from Multiple Sources with Applications to Robotics »
Barbara Caputo · Nicolò Cesa-Bianchi · David R Hardoon · Gayle Leen · Francesco Orabona · Jaakko Peltonen · Simon Rogers -
2009 Poster: Fast, smooth and adaptive regression in metric spaces »
Samory Kpotufe