Efficient online bandit multiclass learning with Õ(√T) regret

Alina Beygelzimer; Francesco Orabona; Chicheng Zhang

Efficient online bandit multiclass learning with Õ(√T) regret

Alina Beygelzimer, Francesco Orabona, Chicheng Zhang

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

Abstract

We present an efficient second-order algorithm with Ō(1/η√T)¹ regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by η, for a range of η restricted by the norm of the competitor. The family of loss functions ranges from hinge loss (η = 0) to squared hinge loss (η = 1). This provides a solution to the open problem of (Abernethy, J. and Rakhlin, A. An efficient bandit algorithm for √T-regret in online multiclass prediction? In COLT, 2009). We test our algorithm experimentally, showing that it also performs favorably against earlier algorithms.

Original language	English (US)
Title of host publication	34th International Conference on Machine Learning, ICML 2017
Publisher	International Machine Learning Society (IMLS)
Pages	742-755
Number of pages	14
ISBN (Electronic)	9781510855144
State	Published - 2017
Externally published	Yes
Event	34th International Conference on Machine Learning, ICML 2017 - Sydney, Australia Duration: Aug 6 2017 → Aug 11 2017

Publication series

Name	34th International Conference on Machine Learning, ICML 2017
Volume	1

Other

Other	34th International Conference on Machine Learning, ICML 2017
Country/Territory	Australia
City	Sydney
Period	8/6/17 → 8/11/17

ASJC Scopus subject areas

Computational Theory and Mathematics
Human-Computer Interaction
Software

Cite this

Efficient online bandit multiclass learning with Õ(√T) regret. / Beygelzimer, Alina; Orabona, Francesco; Zhang, Chicheng.
34th International Conference on Machine Learning, ICML 2017. International Machine Learning Society (IMLS), 2017. p. 742-755 (34th International Conference on Machine Learning, ICML 2017; Vol. 1).

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

Beygelzimer, A, Orabona, F & Zhang, C 2017, Efficient online bandit multiclass learning with Õ(√T) regret. in 34th International Conference on Machine Learning, ICML 2017. 34th International Conference on Machine Learning, ICML 2017, vol. 1, International Machine Learning Society (IMLS), pp. 742-755, 34th International Conference on Machine Learning, ICML 2017, Sydney, Australia, 8/6/17.

@inproceedings{b6c6a78239a24ff5ac53fa6ebda3a1b1,

title = "Efficient online bandit multiclass learning with {\~O}(√T) regret",

abstract = "We present an efficient second-order algorithm with Ō(1/η√T)1 regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by η, for a range of η restricted by the norm of the competitor. The family of loss functions ranges from hinge loss (η = 0) to squared hinge loss (η = 1). This provides a solution to the open problem of (Abernethy, J. and Rakhlin, A. An efficient bandit algorithm for √T-regret in online multiclass prediction? In COLT, 2009). We test our algorithm experimentally, showing that it also performs favorably against earlier algorithms.",

author = "Alina Beygelzimer and Francesco Orabona and Chicheng Zhang",

note = "Publisher Copyright: {\textcopyright} 2017 International Machine Learning Society (IMLS). All rights reserved.; 34th International Conference on Machine Learning, ICML 2017 ; Conference date: 06-08-2017 Through 11-08-2017",

year = "2017",

language = "English (US)",

series = "34th International Conference on Machine Learning, ICML 2017",

publisher = "International Machine Learning Society (IMLS)",

pages = "742--755",

booktitle = "34th International Conference on Machine Learning, ICML 2017",

}

TY - GEN

T1 - Efficient online bandit multiclass learning with Õ(√T) regret

AU - Beygelzimer, Alina

AU - Orabona, Francesco

AU - Zhang, Chicheng

PY - 2017

Y1 - 2017

N2 - We present an efficient second-order algorithm with Ō(1/η√T)1 regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by η, for a range of η restricted by the norm of the competitor. The family of loss functions ranges from hinge loss (η = 0) to squared hinge loss (η = 1). This provides a solution to the open problem of (Abernethy, J. and Rakhlin, A. An efficient bandit algorithm for √T-regret in online multiclass prediction? In COLT, 2009). We test our algorithm experimentally, showing that it also performs favorably against earlier algorithms.

AB - We present an efficient second-order algorithm with Ō(1/η√T)1 regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by η, for a range of η restricted by the norm of the competitor. The family of loss functions ranges from hinge loss (η = 0) to squared hinge loss (η = 1). This provides a solution to the open problem of (Abernethy, J. and Rakhlin, A. An efficient bandit algorithm for √T-regret in online multiclass prediction? In COLT, 2009). We test our algorithm experimentally, showing that it also performs favorably against earlier algorithms.

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

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

M3 - Conference contribution

AN - SCOPUS:85048677545

T3 - 34th International Conference on Machine Learning, ICML 2017

SP - 742

EP - 755

BT - 34th International Conference on Machine Learning, ICML 2017

PB - International Machine Learning Society (IMLS)

T2 - 34th International Conference on Machine Learning, ICML 2017

Y2 - 6 August 2017 through 11 August 2017

ER -

Efficient online bandit multiclass learning with Õ(√T) regret

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this