Random-Walk Perturbations for Online Combinatorial Optimization

Luc Devroye 1 Gábor Lugosi 2, 3 Gergely Neu 4
4 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, 61 (7), pp.4099 - 4106. 〈10.1109/TIT.2015.2428253〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01214987
Contributeur : Gergely Neu <>
Soumis le : mardi 13 octobre 2015 - 14:23:15
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32
Document(s) archivé(s) le : jeudi 27 avril 2017 - 00:16:27

Fichier

fpl_journal_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Luc Devroye, Gábor Lugosi, Gergely Neu. Random-Walk Perturbations for Online Combinatorial Optimization. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, 61 (7), pp.4099 - 4106. 〈10.1109/TIT.2015.2428253〉. 〈hal-01214987〉

Partager

Métriques

Consultations de la notice

133

Téléchargements de fichiers

102