# Optimal Strategies and Minimax Lower Bounds for Online Convex Games

### Jacob Duncan Abernethy, Peter Bartlett, Alexander Rakhlin and Ambuj Tewari

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2008-19

February 22, 2008

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-19.pdf

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.

BibTeX citation:

@techreport{Abernethy:EECS-2008-19, Author = {Abernethy, Jacob Duncan and Bartlett, Peter and Rakhlin, Alexander and Tewari, Ambuj}, Title = {Optimal Strategies and Minimax Lower Bounds for Online Convex Games}, Institution = {EECS Department, University of California, Berkeley}, Year = {2008}, Month = {Feb}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-19.html}, Number = {UCB/EECS-2008-19}, 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.} }

EndNote citation:

%0 Report %A Abernethy, Jacob Duncan %A Bartlett, Peter %A Rakhlin, Alexander %A Tewari, Ambuj %T Optimal Strategies and Minimax Lower Bounds for Online Convex Games %I EECS Department, University of California, Berkeley %D 2008 %8 February 22 %@ UCB/EECS-2008-19 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-19.html %F Abernethy:EECS-2008-19