# Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles

arXiv: https://arxiv.org/abs/2108.06411 · HTML: https://mlsanity.com/paper/2108.06411/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 48 references that are in the map.
- First posted on arXiv 13 Aug 2021.

## Builds on (most cited first, 6 of 6)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [Sequential Outlier Detection based on Incremental Decision Trees](https://mlsanity.com/paper/1803.03674/) (2018)
- [Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments](https://mlsanity.com/paper/2009.09249/) (2020)

## Built on by (most cited first, 10 of 10)

- [Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection](https://mlsanity.com/paper/2109.04809/) (2021)
- [A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization](https://mlsanity.com/paper/2109.07882/) (2021)
- [Smoothing with the Best Rectangle Window is Optimal for All Tapered Rectangle Windows](https://mlsanity.com/paper/2203.02997/) (2022)
- [A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization](https://mlsanity.com/paper/2203.05618/) (2022)
- [Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses](https://mlsanity.com/paper/2109.13786/) (2021)
- [Second Order Regret Bounds Against Generalized Expert Sequences under Partial Bandit Feedback](https://mlsanity.com/paper/2204.06660/) (2022)
- [An Auto-Regressive Formulation for Smoothing and Moving Mean with Exponentially Tapered Windows](https://mlsanity.com/paper/2206.14749/) (2022)
- [A 2-opt Algorithm for Locally Optimal Set Partition Optimization](https://mlsanity.com/paper/2303.08219/) (2023)
- [Formulation of Weighted Average Smoothing as a Projection of the Origin onto a Convex Polytope](https://mlsanity.com/paper/2303.11958/) (2023)
- [A Note On Nonlinear Regression Under L2 Loss](https://mlsanity.com/paper/2303.17745/) (2023)

## Abstract (arXiv)

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.