Random-Walk Perturbations for Online Combinatorial Optimization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Information Theory Année : 2015

Random-Walk Perturbations for Online Combinatorial Optimization

Résumé

We study online combinatorial optimization problems where a learner is interested in minimizing its cumulative regret in the presence of switching costs. To solve such problems, we propose a version of the follow-the-perturbed-leader algorithm in which the cumulative losses are perturbed by independent symmetric random walks. In the general setting, our forecaster is shown to enjoy near-optimal guarantees on both quantities of interest, making it the best known efficient algorithm for the studied problem. In the special case of prediction with expert advice, we show that the forecaster achieves an expected regret of the optimal order O(√ n log N) where n is the time horizon and N is the number of experts, while guaranteeing that the predictions are switched at most O(√ n log N) times, in expectation.
Fichier principal
Vignette du fichier
fpl_journal_final.pdf (355.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01214987 , version 1 (13-10-2015)

Identifiants

Citer

Luc Devroye, Gábor Lugosi, Gergely Neu. Random-Walk Perturbations for Online Combinatorial Optimization. IEEE Transactions on Information Theory, 2015, 61 (7), pp.4099 - 4106. ⟨10.1109/TIT.2015.2428253⟩. ⟨hal-01214987⟩
100 Consultations
369 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More