Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions
Abstract
We tackle the problem of online optimization with a general, possibly unbounded, loss function. It is well known that when the loss is bounded, the exponentially weighted aggregation strategy (EWA) leads to a regret in $\sqrt{T}$ after $T$ steps. In this paper, we study a generalized aggregation strategy, where the weights no longer depend exponentially on the losses. Our strategy is based on Follow The Regularized Leader (FTRL): we minimize the expected losses plus a regularizer, that is here a $\phi$-divergence. When the regularizer is the Kullback-Leibler divergence, we obtain EWA as a special case. Using alternative divergences enables unbounded losses, at the cost of a worst regret bound in some cases.
Cite
Text
Alquier. "Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions." International Conference on Machine Learning, 2021.Markdown
[Alquier. "Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions." International Conference on Machine Learning, 2021.](https://mlanthology.org/icml/2021/alquier2021icml-nonexponentially/)BibTeX
@inproceedings{alquier2021icml-nonexponentially,
title = {{Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions}},
author = {Alquier, Pierre},
booktitle = {International Conference on Machine Learning},
year = {2021},
pages = {207-218},
volume = {139},
url = {https://mlanthology.org/icml/2021/alquier2021icml-nonexponentially/}
}