Optimal Strategies and Minimax Lower Bounds for Online Convex Games

Authors:
Abernethy, Jacob Duncan
Bartlett, Peter
Rakhlin, Alexander
Tewari, Ambuj
Technical Report Identifier: EECS-2008-19
February 22, 2008
EECS-2008-19.pdf

Abstract: A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction x from a convex set, the environment plays a loss function f, and the learner's long-term goal is to minimize regret. Algorithms have been proposed by Zinkevich, when f is assumed to be convex, and Hazan et al., when f is assumed to be strongly convex, that have provably low regret. We consider these two settings and analyze such games from a minimax perspective, proving minimax strategies and lower bounds in each case. These results prove that the existing algorithms are essentially optimal.