Timezone: »

Regression-tree Tuning in a Streaming Setting
Samory Kpotufe · Francesco Orabona

Sat Dec 07 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor #None
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