NEWTRON: An efficient bandit algorithm for online multiclass prediction

Elad Hazan; Satyen Kale

NEWTRON: An efficient bandit algorithm for online multiclass prediction

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

Abstract

We present an efficient algorithm for the problem of online multiclass prediction with bandit feedback in the fully adversarial setting. We measure its regret with respect to the log-loss defined in [AR09], which is parameterized by a scalar α. We prove that the regret of NEWTRON is O(log T) when α is a constant that does not vary with horizon T, and at most O(T ^2/3) if α is allowed to increase to infinity with T. For α = O(log T), the regret is bounded by O( √T), thus solving the open problem of [KSST08, AR09]. Our algorithm is based on a novel application of the online Newton method [HAK07]. We test our algorithm and show it to perform well in experiments, even when α is a small constant.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 24
Subtitle of host publication	25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
Publisher	Neural Information Processing Systems
ISBN (Print)	9781618395993
State	Published - 2011
Externally published	Yes
Event	25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 - Granada, Spain Duration: Dec 12 2011 → Dec 14 2011

Publication series

Name	Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

Other

Other	25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
Country/Territory	Spain
City	Granada
Period	12/12/11 → 12/14/11

All Science Journal Classification (ASJC) codes

Information Systems

Cite this

Hazan, E., & Kale, S. (2011). NEWTRON: An efficient bandit algorithm for online multiclass prediction. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011). Neural Information Processing Systems.

Hazan, Elad ; Kale, Satyen. / NEWTRON : An efficient bandit algorithm for online multiclass prediction. Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Neural Information Processing Systems, 2011. (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011).

@inproceedings{a285ad972225486aaf5ac330752a5e7b,

title = "NEWTRON: An efficient bandit algorithm for online multiclass prediction",

abstract = "We present an efficient algorithm for the problem of online multiclass prediction with bandit feedback in the fully adversarial setting. We measure its regret with respect to the log-loss defined in [AR09], which is parameterized by a scalar α. We prove that the regret of NEWTRON is O(log T) when α is a constant that does not vary with horizon T, and at most O(T 2/3) if α is allowed to increase to infinity with T. For α = O(log T), the regret is bounded by O( √T), thus solving the open problem of [KSST08, AR09]. Our algorithm is based on a novel application of the online Newton method [HAK07]. We test our algorithm and show it to perform well in experiments, even when α is a small constant.",

author = "Elad Hazan and Satyen Kale",

year = "2011",

language = "English (US)",

isbn = "9781618395993",

series = "Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011",

publisher = "Neural Information Processing Systems",

booktitle = "Advances in Neural Information Processing Systems 24",

note = "25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 ; Conference date: 12-12-2011 Through 14-12-2011",

}

Hazan, E & Kale, S 2011, NEWTRON: An efficient bandit algorithm for online multiclass prediction. in Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011, Neural Information Processing Systems, 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011, Granada, Spain, 12/12/11.

NEWTRON: An efficient bandit algorithm for online multiclass prediction. / Hazan, Elad; Kale, Satyen.
Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Neural Information Processing Systems, 2011. (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011).

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

TY - GEN

T1 - NEWTRON

T2 - 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

AU - Hazan, Elad

AU - Kale, Satyen

PY - 2011

Y1 - 2011

N2 - We present an efficient algorithm for the problem of online multiclass prediction with bandit feedback in the fully adversarial setting. We measure its regret with respect to the log-loss defined in [AR09], which is parameterized by a scalar α. We prove that the regret of NEWTRON is O(log T) when α is a constant that does not vary with horizon T, and at most O(T 2/3) if α is allowed to increase to infinity with T. For α = O(log T), the regret is bounded by O( √T), thus solving the open problem of [KSST08, AR09]. Our algorithm is based on a novel application of the online Newton method [HAK07]. We test our algorithm and show it to perform well in experiments, even when α is a small constant.

AB - We present an efficient algorithm for the problem of online multiclass prediction with bandit feedback in the fully adversarial setting. We measure its regret with respect to the log-loss defined in [AR09], which is parameterized by a scalar α. We prove that the regret of NEWTRON is O(log T) when α is a constant that does not vary with horizon T, and at most O(T 2/3) if α is allowed to increase to infinity with T. For α = O(log T), the regret is bounded by O( √T), thus solving the open problem of [KSST08, AR09]. Our algorithm is based on a novel application of the online Newton method [HAK07]. We test our algorithm and show it to perform well in experiments, even when α is a small constant.

UR - http://www.scopus.com/inward/record.url?scp=85162453290&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85162453290&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85162453290

SN - 9781618395993

T3 - Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

BT - Advances in Neural Information Processing Systems 24

PB - Neural Information Processing Systems

Y2 - 12 December 2011 through 14 December 2011

ER -

Hazan E, Kale S. NEWTRON: An efficient bandit algorithm for online multiclass prediction. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Neural Information Processing Systems. 2011. (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011).

NEWTRON: An efficient bandit algorithm for online multiclass prediction

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this