The Gain of Ordering in Online Learning

Neural Information Processing Systems 

We study fixed-design online learning where the learner is allowed to choose the order of the datapoints in order to minimize their regret (aka self-directed online learning).