Improved Regret Bounds for Tracking Experts with Memory
Abstract
We address the problem of sequential prediction with expert advice in a non-stationary environment with long-term memory guarantees in the sense of Bousquet and Warmuth [4]. We give a linear-time algorithm that improves on the best known regret bound [27]. This algorithm incorporates a relative entropy projection step. This projection is advantageous over previous weight-sharing approaches in that weight updates may come with implicit costs as in for example portfolio optimization. We give an algorithm to compute this projection step in linear time, which may be of independent interest.
Cite
Text
Robinson and Herbster. "Improved Regret Bounds for Tracking Experts with Memory." Neural Information Processing Systems, 2021.Markdown
[Robinson and Herbster. "Improved Regret Bounds for Tracking Experts with Memory." Neural Information Processing Systems, 2021.](https://mlanthology.org/neurips/2021/robinson2021neurips-improved/)BibTeX
@inproceedings{robinson2021neurips-improved,
title = {{Improved Regret Bounds for Tracking Experts with Memory}},
author = {Robinson, James and Herbster, Mark},
booktitle = {Neural Information Processing Systems},
year = {2021},
url = {https://mlanthology.org/neurips/2021/robinson2021neurips-improved/}
}