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