Best of many worlds: Robust model selection for online supervised learning
This work addresses the challenge of adaptive online learning for practitioners needing robust model selection without prior knowledge of data characteristics, though it is incremental in combining existing frameworks.
The paper tackles the problem of robust model selection in online supervised learning by introducing algorithms that adapt to both the complexity of contextual tree experts and the nature of the data process, achieving regret bounds competitive with an optimal algorithm that has side information, including constant regret in stochastic settings.
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 $\mathcal{O}(\sqrt{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.