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://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-19.html
%F Abernethy:EECS-2008-19