Non-exponentially weighted aggregation: regret bounds for unbounded loss functions
This addresses a limitation in online learning for scenarios with unbounded losses, though it is incremental as it extends existing methods.
The paper tackles online optimization with unbounded loss functions by generalizing the exponentially weighted aggregation strategy using Follow The Regularized Leader with φ-divergence regularizers, resulting in a worst-case regret bound.
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 $φ$-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.