Optimal Stragies and Minimax Lower Bounds for Online Convex Games
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.
Cite
Text
Abernethy et al. "Optimal Stragies and Minimax Lower Bounds for Online Convex Games." Annual Conference on Computational Learning Theory, 2008.Markdown
[Abernethy et al. "Optimal Stragies and Minimax Lower Bounds for Online Convex Games." Annual Conference on Computational Learning Theory, 2008.](https://mlanthology.org/colt/2008/abernethy2008colt-optimal/)BibTeX
@inproceedings{abernethy2008colt-optimal,
title = {{Optimal Stragies and Minimax Lower Bounds for Online Convex Games}},
author = {Abernethy, Jacob D. and Bartlett, Peter L. and Rakhlin, Alexander and Tewari, Ambuj},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2008},
pages = {415-424},
url = {https://mlanthology.org/colt/2008/abernethy2008colt-optimal/}
}