  Mixability has been shown to be a powerful tool to obtain algorithms with
optimal regret. However, the resulting methods often suffer from high
computational complexity which has reduced their practical applicability. For
example, in the case of multiclass logistic regression, the aggregating
forecaster (Foster et al. (2018)) achieves a regret of $O(\log(Bn))$ whereas
Online Newton Step achieves $O(e^B\log(n))$ obtaining a double exponential gain
in $B$ (a bound on the norm of comparative functions). However, this high
statistical performance is at the price of a prohibitive computational
complexity $O(n^{37})$.
