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

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-19

February 22, 2008

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},
    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