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
in Spotlight Session 6 »
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)

More from the Same Authors