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 $\varphi$-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.

References in corpus (6)

• Fast learning rates in statistical inference through aggregation
• PAC-Bayesian Bounds for Randomized Empirical Risk Minimizers
• Optimal Bounds between $f$-Divergences and Integral Probability Metrics
• PAC-Bayes Analysis Beyond the Usual Bounds
• On the Robustness to Misspecification of $\alpha$-Posteriors and Their Variational Approximations
• Optimal Posteriors for Chi-squared Divergence based PAC-Bayesian Bounds and Comparison with KL-divergence based Optimal Posteriors and Cross-Validation Procedure

Cited by in corpus (2)

• Meta-strategy for Learning Tuning Parameters with Guarantees
• Risk-Monotonicity in Statistical Learning