Competing With Strategies

Wei Han, Alexander Rakhlin, Karthik Sridharan
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:966-992, 2013.

Abstract

We study the problem of online learning with a notion of regret defined with respect to a set of strategies. We develop tools for analyzing the minimax rates and for deriving regret-minimization algorithms in this scenario. While the standard methods for minimizing the usual notion of regret fail, through our analysis we demonstrate existence of regret-minimization methods that compete with such sets of strategies as: autoregressive algorithms, strategies based on statistical models, regularized least squares, and follow the regularized leader strategies. In several cases we also derive efficient learning algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Han13, title = {Competing With Strategies}, author = {Han, Wei and Rakhlin, Alexander and Sridharan, Karthik}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {966--992}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Han13.pdf}, url = {https://proceedings.mlr.press/v30/Han13.html}, abstract = {We study the problem of online learning with a notion of regret defined with respect to a set of strategies. We develop tools for analyzing the minimax rates and for deriving regret-minimization algorithms in this scenario. While the standard methods for minimizing the usual notion of regret fail, through our analysis we demonstrate existence of regret-minimization methods that compete with such sets of strategies as: autoregressive algorithms, strategies based on statistical models, regularized least squares, and follow the regularized leader strategies. In several cases we also derive efficient learning algorithms. } }
Endnote
%0 Conference Paper %T Competing With Strategies %A Wei Han %A Alexander Rakhlin %A Karthik Sridharan %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Han13 %I PMLR %P 966--992 %U https://proceedings.mlr.press/v30/Han13.html %V 30 %X We study the problem of online learning with a notion of regret defined with respect to a set of strategies. We develop tools for analyzing the minimax rates and for deriving regret-minimization algorithms in this scenario. While the standard methods for minimizing the usual notion of regret fail, through our analysis we demonstrate existence of regret-minimization methods that compete with such sets of strategies as: autoregressive algorithms, strategies based on statistical models, regularized least squares, and follow the regularized leader strategies. In several cases we also derive efficient learning algorithms.
RIS
TY - CPAPER TI - Competing With Strategies AU - Wei Han AU - Alexander Rakhlin AU - Karthik Sridharan BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Han13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 966 EP - 992 L1 - http://proceedings.mlr.press/v30/Han13.pdf UR - https://proceedings.mlr.press/v30/Han13.html AB - We study the problem of online learning with a notion of regret defined with respect to a set of strategies. We develop tools for analyzing the minimax rates and for deriving regret-minimization algorithms in this scenario. While the standard methods for minimizing the usual notion of regret fail, through our analysis we demonstrate existence of regret-minimization methods that compete with such sets of strategies as: autoregressive algorithms, strategies based on statistical models, regularized least squares, and follow the regularized leader strategies. In several cases we also derive efficient learning algorithms. ER -
APA
Han, W., Rakhlin, A. & Sridharan, K.. (2013). Competing With Strategies. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:966-992 Available from https://proceedings.mlr.press/v30/Han13.html.

Related Material