Timezone: »

Efficient Online Bandit Multiclass Learning with O(sqrt{T}) Regret
Alina Beygelzimer · Francesco Orabona · Chicheng Zhang

Tue Aug 08 01:30 AM -- 05:00 AM (PDT) @ Gallery #9

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

Author Information

Alina Beygelzimer (Yahoo Research)
Francesco Orabona (Stony Brook University)
Francesco Orabona

Francesco Orabona is an Assistant Professor at Boston University. His background covers both theoretical and practical aspects of machine learning and optimization. His current research interests lie in online learning, and more generally the problem of designing and analyzing adaptive and parameter-free learning algorithms. He received the PhD degree in Electrical Engineering at the University of Genoa in 2007. He is (co)author of more than 60 peer reviewed papers.

Chicheng Zhang (UCSD)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors