Interior-Point Methods for Full-Information and Bandit Online Learning

Author

Abernethy, Jacob D. ; Hazan, Elad ; Rakhlin, Alexander

Author_Institution

Dept. of Comput. Sci., Univ. of California Berkeley, Berkeley, CA, USA

Volume

58

Issue

7

fYear

2012

fDate

7/1/2012 12:00:00 AM

Firstpage

4164

Lastpage

4175

Abstract

We study the problem of predicting individual sequences with linear loss with full and partial (or bandit) feed- back. Our main contribution is the first efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal Õ(√(T)) regret. In addition, for the full-information setting, we give a novel regret minimization algorithm. These results are made possible by the introduction of interior-point methods for convex optimization to online learning.

Keywords

convex programming; decision making; iterative methods; learning (artificial intelligence); bandit online learning; bandit setting; convex optimization; efήcient algorithm; full-information; full-information setting; individual sequences prediction problem; interior-point methods; online linear optimization; regret minimization algorithm; Convex functions; Decision making; Ellipsoids; Minimization; Newton method; Optimization; Vectors; Bandit feedback; interior-point methods; online convex optimization; online learning;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2012.2192096

Filename

6191328