Online Learning in the Random Order Model
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912626011799552 |
|---|---|
| author | Bernasconi, Martino Celli, Andrea Colini-Baldeschi, Riccardo Fusco, Federico Leonardi, Stefano Russo, Matteo |
| author_facet | Bernasconi, Martino Celli, Andrea Colini-Baldeschi, Riccardo Fusco, Federico Leonardi, Stefano Russo, Matteo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02820 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Learning in the Random Order Model Bernasconi, Martino Celli, Andrea Colini-Baldeschi, Riccardo Fusco, Federico Leonardi, Stefano Russo, Matteo Machine Learning Data Structures and Algorithms 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. |
| title | Online Learning in the Random Order Model |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.02820 |