Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions

Pierre Alquier
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:207-218, 2021.

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 this Paper

BibTeX
@InProceedings{pmlr-v139-alquier21a, title = {Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions}, author = {Alquier, Pierre}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {207--218}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/alquier21a/alquier21a.pdf}, url = {https://proceedings.mlr.press/v139/alquier21a.html}, 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.} }
Endnote
%0 Conference Paper %T Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions %A Pierre Alquier %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-alquier21a %I PMLR %P 207--218 %U https://proceedings.mlr.press/v139/alquier21a.html %V 139 %X 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.
APA
Alquier, P.. (2021). Non-Exponentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:207-218 Available from https://proceedings.mlr.press/v139/alquier21a.html.

Related Material