Regression-tree tuning in a streaming setting

Samory Kpotufe; Francesco Orabona

Regression-tree tuning in a streaming setting

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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)
Title of host publication	Advances in Neural Information Processing Systems
Publisher	Neural information processing systems foundation
State	Published - Jan 1 2013
Externally published	Yes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-25

Cite this

@inproceedings{31a0ef94cb604e1787c8df71b66e1eb0,

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

note = "Generated from Scopus record by KAUST IRTS on 2023-09-25",

year = "2013",

month = jan,

day = "1",

language = "English (US)",

booktitle = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

}

TY - GEN

T1 - Regression-tree tuning in a streaming setting

AU - Kpotufe, Samory

AU - Orabona, Francesco

N1 - Generated from Scopus record by KAUST IRTS on 2023-09-25

PY - 2013/1/1

Y1 - 2013/1/1

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 - http://www.scopus.com/inward/record.url?scp=84899011776&partnerID=8YFLogxK

M3 - Conference contribution

BT - Advances in Neural Information Processing Systems

PB - Neural information processing systems foundation

ER -

Regression-tree tuning in a streaming setting

Abstract

Bibliographical note

Other files and links

Fingerprint

Cite this