Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm
Abstract
We present an adaptive variant of the exponentiated gradient algorithm. Leveraging the optimistic learning framework of Rakhlin & Sridharan (2012), we obtain regret bounds that in the learning from experts setting depend on the variance and path length of the best expert, improving on results by Hazan & Kale (2008) and Chiang et al. (2012), and resolving an open problem posed by Kale (2012). Our techniques naturally extend to matrix-valued loss functions, where we present an adaptive matrix exponentiated gradient algorithm. To obtain the optimal regret bound in the matrix case, we generalize the Follow-the-Regularized-Leader algorithm to vector-valued payoffs, which may be of independent interest.
Cite
Text
Steinhardt and Liang. "Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm." International Conference on Machine Learning, 2014.Markdown
[Steinhardt and Liang. "Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm." International Conference on Machine Learning, 2014.](https://mlanthology.org/icml/2014/steinhardt2014icml-adaptivity/)BibTeX
@inproceedings{steinhardt2014icml-adaptivity,
title = {{Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm}},
author = {Steinhardt, Jacob and Liang, Percy},
booktitle = {International Conference on Machine Learning},
year = {2014},
pages = {1593-1601},
volume = {32},
url = {https://mlanthology.org/icml/2014/steinhardt2014icml-adaptivity/}
}