Interior-Point Methods for Full-Information and Bandit Online Learning
| Autor: | Alexander Rakhlin, Elad Hazan, Jacob Abernethy |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Mathematical optimization
Linear programming Iterative method Regret Library and Information Sciences Multi-armed bandit Computer Science Applications TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Convex optimization Minification Convex function Interior point method Information Systems Mathematics |
| Zdroj: | IEEE Transactions on Information Theory. 58:4164-4175 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2012.2192096 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|