Online Learning in the Random-Order Model
Authors: Martino Bernasconi, Andrea Celli, Riccardo Colini Baldeschi, Federico Fusco, Stefano Leonardi, Matteo Russo
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. Discussion. On a theoretical level, our results have two main implications: (i) the minimax regret rates for random-order and the stochastic model are typically the same, and (ii) it is fairly easy to construct the desired random-order algorithm starting from a stochastic one. |
| Researcher Affiliation | Collaboration | 1Department of Computing Sciences, Bocconi University, Milan, Italy 2Central Applied Science, Meta, London, UK 3Department of Computer, Control and Management Engineering Antonio Ruberti , Sapienza University, Rome, Italy. |
| Pseudocode | Yes | Algorithm 1 * Input: stochastic algorithm A for i = 0, 1, 2, . . . , log T do (i) iid-ify past data Construct a distribution on past data Di (ii) Train A on a simulated past Run algorithm A over 2i i.i.d. samples of Di (iii) Test over new data Let ni(a) be the times that A plays action a on Di for t = 2i + 1, 2i + 2, . . . , 2i+1 do Play action at (ni(1)/2i, . . . , ni(k)/2i) end for The SIMULATION Template |
| Open Source Code | No | The information is insufficient. The paper does not explicitly provide a link to source code, state that code is available in supplementary materials, or make an unambiguous statement of code release for the methodology described. |
| Open Datasets | No | The information is insufficient. The paper is theoretical and focuses on mathematical models and proofs rather than empirical evaluation on specific datasets. It defines problem settings using abstract concepts like 'loss vectors' or 'tuples' but does not refer to any concrete, named datasets, nor does it provide access information for any data. |
| Dataset Splits | No | The information is insufficient. The paper is theoretical and does not report on empirical experiments using specific datasets, therefore, there is no discussion or mention of dataset splits (e.g., training, validation, test sets). |
| Hardware Specification | No | The information is insufficient. The paper is theoretical and does not report on any empirical experiments. Therefore, there are no details provided regarding specific hardware used for running experiments. |
| Software Dependencies | No | The information is insufficient. The paper is theoretical and does not report on any empirical experiments. Therefore, it does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The information is insufficient. The paper is theoretical and focuses on algorithm design and mathematical analysis of regret bounds. It does not describe any empirical experiments or provide concrete hyperparameter values or training configurations. |