# Non-exponentially weighted aggregation: regret bounds for unbounded loss functions

arXiv: https://arxiv.org/abs/2009.03017 · HTML: https://mlsanity.com/paper/2009.03017/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2020.

## Built on by (most cited first, 18 of 18)

- [A Rigorous Link between Deep Ensembles and (Variational) Bayesian Methods](https://mlsanity.com/paper/2305.15027/) (2023)
- [On the Robustness to Misspecification of α-Posteriors and Their Variational Approximations](https://mlsanity.com/paper/2104.08324/) (2021)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?](https://mlsanity.com/paper/2307.14642/) (2023)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [Meta-strategy for Learning Tuning Parameters with Guarantees](https://mlsanity.com/paper/2102.02504/) (2021)
- [Practical and Matching Gradient Variance Bounds for Black-Box Variational Bayesian Inference](https://mlsanity.com/paper/2303.10472/) (2023)
- [Equivalence of the Empirical Risk Minimization to Regularization on the Family of f-Divergences](https://mlsanity.com/paper/2402.00501/) (2024)
- [Asymmetry of the Relative Entropy in the Regularization of Empirical Risk Minimization](https://mlsanity.com/paper/2410.02833/) (2024)
- [Federated Generalised Variational Inference: A Robust Probabilistic Federated Learning Framework](https://mlsanity.com/paper/2502.00846/) (2025)
- [Fenchel-Young Variational Learning](https://mlsanity.com/paper/2502.10295/) (2025)
- [A Dual Optimization View to Empirical Risk Minimization with f-Divergence Regularization](https://mlsanity.com/paper/2508.03314/) (2025)
- [Adaptive Bayesian Online Learning via Expert Aggregation](https://mlsanity.com/paper/2607.20239/) (2026)
- [Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces](https://mlsanity.com/paper/2502.14790/) (2025)
- [Empirical Risk Minimization with f-Divergence Regularization](https://mlsanity.com/paper/2601.13191/) (2026)
- [Hedging Memory Horizons for Non-Stationary Prediction via Online Aggregation](https://mlsanity.com/paper/2605.06541/) (2026)
- [Fast rates in Bayesian online learning with approximate posteriors](https://mlsanity.com/paper/2608.25706/) (2026)

## Abstract (arXiv)

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 √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 φ-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.