%0 Journal Article
%T Competing With Strategies
%A Wei Han
%A Alexander Rakhlin
%A Karthik Sridharan
%J Computer Science
%D 2013
%I arXiv
%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.
%U http://arxiv.org/abs/1302.2672v1