Optimal and Efficient Algorithms for General Mixable Losses against
  Switching Oracles
  We investigate the problem of online learning, which has gained significant
attention in recent years due to its applicability in a wide range of fields
from machine learning to game theory. Specifically, we study the online
optimization of mixable loss functions in a dynamic environment. We introduce
online mixture schemes that asymptotically achieves the performance of the best
dynamic estimation sequence of the switching oracle with optimal regret
redundancies. The best dynamic estimation sequence that we compete against is
selected in hindsight with full observation of the loss functions and is
allowed to select different optimal estimations in different time intervals
(segments). We propose two mixtures in our work. Firstly, we propose a
tractable polynomial time complexity algorithm that can achieve the optimal
redundancy of the intractable brute force approach. Secondly, we propose an
efficient logarithmic time complexity algorithm that can achieve the optimal
redundancy up to a constant multiplicity gap. Our results are guaranteed to
hold in a strong deterministic sense in an individual sequence manner.
