Regression-tree tuning in a streaming setting

Samory Kpotufe; Francesco Orabona

Regression-tree tuning in a streaming setting

Samory Kpotufe
, Francesco Orabona

Operations Research & Financial Engineering

Research output: Contribution to journal › Conference article › peer-review

8 Scopus citations

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 Õ (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.

Original language	English (US)
Journal	Advances in Neural Information Processing Systems
State	Published - 2013
Event	27th Annual Conference on Neural Information Processing Systems, NIPS 2013 - Lake Tahoe, NV, United States Duration: Dec 5 2013 → Dec 10 2013

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@article{88be771ab1774cc59a8418a821aa0246,

title = "Regression-tree tuning in a streaming setting",

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.",

author = "Samory Kpotufe and Francesco Orabona",

year = "2013",

language = "English (US)",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

publisher = "Neural information processing systems foundation",

note = "27th Annual Conference on Neural Information Processing Systems, NIPS 2013 ; Conference date: 05-12-2013 Through 10-12-2013",

}

TY - JOUR

T1 - Regression-tree tuning in a streaming setting

AU - Kpotufe, Samory

AU - Orabona, Francesco

PY - 2013

Y1 - 2013

N2 - 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 Õ (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.

AB - 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 Õ (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.

UR - https://www.scopus.com/pages/publications/84899011776

UR - https://www.scopus.com/pages/publications/84899011776#tab=citedBy

M3 - Conference article

AN - SCOPUS:84899011776

SN - 1049-5258

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

T2 - 27th Annual Conference on Neural Information Processing Systems, NIPS 2013

Y2 - 5 December 2013 through 10 December 2013

ER -

Regression-tree tuning in a streaming setting

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this