Interior-point methods for full-information and bandit online learning

Jacob D. Abernethy; Elad Hazan; Alexander Rakhlin

doi:10.1109/TIT.2012.2192096

Interior-point methods for full-information and bandit online learning

Jacob D. Abernethy, Elad Hazan, Alexander Rakhlin

Research output: Contribution to journal › Article › peer-review

47 Scopus citations

Abstract

We study the problem of predicting individual sequences with linear loss with full and partial (or bandit) feedback. Our main contribution is the first efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal Õ(√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.

Original language	English (US)
Article number	6191328
Pages (from-to)	4164-4175
Number of pages	12
Journal	IEEE Transactions on Information Theory
Volume	58
Issue number	7
DOIs	https://doi.org/10.1109/TIT.2012.2192096
State	Published - 2012
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Bandit feedback
interior-point methods
online convex optimization
online learning

Access to Document

10.1109/TIT.2012.2192096

Cite this

@article{692e54fdac4b4146a6e79bb7a9d68f92,

title = "Interior-point methods for full-information and bandit online learning",

abstract = "We study the problem of predicting individual sequences with linear loss with full and partial (or bandit) feedback. 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 = "Bandit feedback, interior-point methods, online convex optimization, online learning",

author = "Abernethy, {Jacob D.} and Elad Hazan and Alexander Rakhlin",

note = "Funding Information: Manuscript received May 04, 2011; revised November 17, 2011; accepted November 26, 2011. Date of publication April 27, 2012; date of current version June 12, 2012. This work was supported in part by the Defense Advanced Research Projects Agency under Grant FA8750-05-2-0249 and in part by the National Science Foundation under Grant DMS-0707060. This paper was presented at the 21st Annual Conference on Learning Theory, Helsinki, Finland, July 2008.",

year = "2012",

doi = "10.1109/TIT.2012.2192096",

language = "English (US)",

volume = "58",

pages = "4164--4175",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

T1 - Interior-point methods for full-information and bandit online learning

AU - Abernethy, Jacob D.

AU - Hazan, Elad

AU - Rakhlin, Alexander

N1 - Funding Information: Manuscript received May 04, 2011; revised November 17, 2011; accepted November 26, 2011. Date of publication April 27, 2012; date of current version June 12, 2012. This work was supported in part by the Defense Advanced Research Projects Agency under Grant FA8750-05-2-0249 and in part by the National Science Foundation under Grant DMS-0707060. This paper was presented at the 21st Annual Conference on Learning Theory, Helsinki, Finland, July 2008.

PY - 2012

Y1 - 2012

N2 - We study the problem of predicting individual sequences with linear loss with full and partial (or bandit) feedback. Our main contribution is the first efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal Õ(√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.

AB - We study the problem of predicting individual sequences with linear loss with full and partial (or bandit) feedback. Our main contribution is the first efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal Õ(√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.

KW - Bandit feedback

KW - interior-point methods

KW - online convex optimization

KW - online learning

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

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

U2 - 10.1109/TIT.2012.2192096

DO - 10.1109/TIT.2012.2192096

M3 - Article

AN - SCOPUS:84862535425

SN - 0018-9448

VL - 58

SP - 4164

EP - 4175

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

M1 - 6191328

ER -

Interior-point methods for full-information and bandit online learning

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this