Mixability of a loss is known to characterise when constant regret bounds are achievable in games of prediction with expert advice through the use of the aggregating algorithm [Vovk, 2001]. We provide a new interpretation of mixability via convex analysis that highlights the role of the Kullback-Leibler divergence in its definition. This naturally generalises to what we call �-mixability where the Bregman divergence D� replaces the KL divergence. We prove that losses that are �-mixable also enjoy constant regret bounds via a generalised aggregating algorithm that is similar to mirror descent.
The starting point for mixability and the aggregating algorithm is the work of . The general setting of prediction with expert advice is summarised in [Chapters 2 and 3] Cesa-Bianchi:2006 . There one can find a range of results that study diffferent aggregation schemes and different assumptions on the losses (exp-concave, mixable). Variants of the aggregating algorithm have been studied for classically mixable losses, with a tradeoff between tightness of the bound (in a constant factor) and the computational complexity . Weakly mixable losses are a generalisation of mixable losses. They have been studied in @cite_1 where it is shown there exists a variant of the aggregating algorithm that achives regret @math for some constant @math . [in .2] Vovk:2001 makes the observation that his Aggregating Algorithm reduces to Bayesian mixtures in the case of the log loss game. See also the discussion in [page 330] Cesa-Bianchi:2006 relating certain aggregation schemes to Bayesian updating.
@cite_1
2059590802
This paper resolves the problem of predicting as well as the best expert up to an additive term of the order o(n), where n is the length of a sequence of letters from a finite alphabet. We call the games that permit this weakly mixable and give a geometrical characterisation of the class of weakly mixable games. Weak mixability turns out to be equivalent to convexity of the finite part of the set of superpredictions. For bounded games we introduce the Weak Aggregating Algorithm that allows us to obtain additive terms of the form Cn.