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 (17)

• Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory
• Frequentist Consistency of Variational Bayes
• Practical Deep Learning with Bayesian Principles
• Online Learning: A Modern Introduction Using Convex Optimization
• Fast learning rates in statistical inference through aggregation
• Rényi Divergence Variational Inference
• Generalized Variational Inference: Three arguments for deriving new Posteriors
• Conjugate-Computation Variational Inference : Converting Variational Inference in Non-Conjugate Models to Inferences in Conjugate Models
• Consistency of Variational Bayes Inference for Estimation and Model Selection in Mixtures
• PAC-Bayesian Bounds for Randomized Empirical Risk Minimizers
• Simpler PAC-Bayesian Bounds for Hostile Data
• PAC-Bayes under potentially heavy tails
• 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
• Constant Regret, Generalized Mixability, and Mirror Descent
• 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