# Best of many worlds: Robust model selection for online supervised learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2018.

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

- [Personalized Federated Learning with Mixture of Models for Adaptive Prediction and Model Fine-Tuning](https://mlsanity.com/paper/2410.21547/) (2024)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [ChaCha for Online AutoML](https://mlsanity.com/paper/2106.04815/) (2021)
- [Model Selection for Production System via Automated Online Experiments](https://mlsanity.com/paper/2105.13420/) (2021)
- [Budgeted Online Model Selection and Fine-Tuning via Federated Learning](https://mlsanity.com/paper/2401.10478/) (2024)

## Abstract (arXiv)

We introduce algorithms for online, full-information prediction that are competitive with contextual tree experts of unknown complexity, in both probabilistic and adversarial settings. We show that by incorporating a probabilistic framework of structural risk minimization into existing adaptive algorithms, we can robustly learn not only the presence of stochastic structure when it exists (leading to constant as opposed to O(√T) regret), but also the correct model order. We thus obtain regret bounds that are competitive with the regret of an optimal algorithm that possesses strong side information about both the complexity of the optimal contextual tree expert and whether the process generating the data is stochastic or adversarial. These are the first constructive guarantees on simultaneous adaptivity to the model and the presence of stochasticity.