Optimal Strategies and Minimax Lower Bounds for Online Convex Games

Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, Ambuj Tewari

ScholarlyCommons (University of Pennsylvania) · 2008 · 105 citations · 5 references

Full text

Open access

Concepts

Abstract

A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction <i>x</i> from a convex set, the environment plays a loss function <i>f</i>, and the learner's long-term goal is to minimize regret. Algorithms have been proposed by Zinkevich, when <i>f</i> is assumed to be convex, and Hazan et al., when <i>f</i> 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.

References

5