Online Learning in the Random Order Model
This work addresses the challenge of adapting online learning algorithms to handle non-stationary random-order inputs, which is incremental as it builds on existing stochastic and adversarial models to improve performance in specific scenarios.
The paper tackles the problem of online learning in the random-order model, where non-stationarity can hinder stochastic algorithms, by proposing a general template to adapt stochastic algorithms to this model without substantially affecting regret guarantees, resulting in improved bounds for tasks like prediction with delays and online classification where learnability is characterized by VC dimension rather than Littlestone dimension.
In the random-order model for online learning, the sequence of losses is chosen upfront by an adversary and presented to the learner after a random permutation. Any random-order input is \emph{asymptotically} equivalent to a stochastic i.i.d. one, but, for finite times, it may exhibit significant {\em non-stationarity}, which can hinder the performance of stochastic learning algorithms. While algorithms for adversarial inputs naturally maintain their regret guarantees in random order, simple no-regret algorithms exist for the stochastic model that fail against random-order instances. In this paper, we propose a general template to adapt stochastic learning algorithms to the random-order model without substantially affecting their regret guarantees. This allows us to recover improved regret bounds for prediction with delays, online learning with constraints, and bandits with switching costs. Finally, we investigate online classification and prove that, in random order, learnability is characterized by the VC dimension rather than the Littlestone dimension, thus providing a further separation from the general adversarial model.