Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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