Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
Abstract
We study algorithms for online linear optimization in Hilbert spaces, focusing on the case where the player is unconstrained. We develop a novel characterization of a large class of minimax algorithms, recovering, and even improving, several previous results as immediate corollaries. Moreover, using our tools, we develop an algorithm that provides a regret bound ofO U q T log(U p T log 2 T + 1) , where U is the L2 norm of an arbitrary comparator and both T and U are unknown to the player. This bound is optimal up to p log logT terms. When T is known, we derive an algorithm with an optimal regret bound (up to constant factors). For both the known and unknown T case, a Normal approximation to the conditional value of the game proves to be the key analysis tool.
Cite
Text
McMahan and Orabona. "Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations." Annual Conference on Computational Learning Theory, 2014.Markdown
[McMahan and Orabona. "Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations." Annual Conference on Computational Learning Theory, 2014.](https://mlanthology.org/colt/2014/mcmahan2014colt-unconstrained/)BibTeX
@inproceedings{mcmahan2014colt-unconstrained,
title = {{Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations}},
author = {McMahan, H. Brendan and Orabona, Francesco},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2014},
pages = {1020-1039},
url = {https://mlanthology.org/colt/2014/mcmahan2014colt-unconstrained/}
}