Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles
This work provides efficient algorithms for online optimization, addressing a specific problem in machine learning with incremental improvements in computational efficiency.
The paper tackles online learning with mixable loss functions in dynamic environments by introducing online mixture schemes that achieve optimal regret against switching oracles, proposing a polynomial-time algorithm matching brute-force optimal redundancy and a logarithmic-time algorithm with constant multiplicative gap.
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.