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

Jacob D. Abernethy, Elad Hazan, Alexander RakhlinIEEE Trans. Information Theory 2012 · OpenReview

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 Õ(√(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.
BibTeX
@article{abernethy2012interior,
  author = {Jacob D. Abernethy and Elad Hazan and Alexander Rakhlin},
  title = {{Interior-Point Methods for Full-Information and Bandit Online Learning}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  url = {https://openreview.net/forum?id=VIQ1WzBsL5b},
}

Loading related content...

Figure