Online Learning of Non-stationary Sequences

Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)

Bibtex Metadata Paper

Authors

Claire Monteleoni, Tommi Jaakkola

Abstract

We consider an online learning scenario in which the learner can make predictions on the basis of a fixed set of experts. We derive upper and lower relative loss bounds for a class of universal learning algorithms in- volving a switching dynamics over the choice of the experts. On the basis of the performance bounds we provide the optimal a priori discretiza- tion for learning the parameter that governs the switching dynamics. We demonstrate the new algorithm in the context of wireless networks.