Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations

H. Brendan McMahan, Francesco Orabona
Proceedings of The 27th Conference on Learning Theory, PMLR 35:1020-1039, 2014.

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 of O(U \sqrtT \log( U \sqrtT \log^2 T +1)), where U is the L_2 norm of an arbitrary comparator and both T and U are unknown to the player. This bound is optimal up to \sqrt\log \log T 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 this Paper

BibTeX
@InProceedings{pmlr-v35-mcmahan14, title = {Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations}, author = {McMahan, H. Brendan and Orabona, Francesco}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {1020--1039}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/mcmahan14.pdf}, url = {https://proceedings.mlr.press/v35/mcmahan14.html}, 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 of O(U \sqrtT \log( U \sqrtT \log^2 T +1)), where U is the L_2 norm of an arbitrary comparator and both T and U are unknown to the player. This bound is optimal up to \sqrt\log \log T 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.} }
Endnote
%0 Conference Paper %T Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations %A H. Brendan McMahan %A Francesco Orabona %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-mcmahan14 %I PMLR %P 1020--1039 %U https://proceedings.mlr.press/v35/mcmahan14.html %V 35 %X 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 of O(U \sqrtT \log( U \sqrtT \log^2 T +1)), where U is the L_2 norm of an arbitrary comparator and both T and U are unknown to the player. This bound is optimal up to \sqrt\log \log T 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.
RIS
TY - CPAPER TI - Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations AU - H. Brendan McMahan AU - Francesco Orabona BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-mcmahan14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 1020 EP - 1039 L1 - http://proceedings.mlr.press/v35/mcmahan14.pdf UR - https://proceedings.mlr.press/v35/mcmahan14.html AB - 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 of O(U \sqrtT \log( U \sqrtT \log^2 T +1)), where U is the L_2 norm of an arbitrary comparator and both T and U are unknown to the player. This bound is optimal up to \sqrt\log \log T 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. ER -
APA
McMahan, H.B. & Orabona, F.. (2014). Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:1020-1039 Available from https://proceedings.mlr.press/v35/mcmahan14.html.

Related Material