Random-Walk Perturbations for Online ...
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Random-Walk Perturbations for Online Combinatorial Optimization
Author(s) :
Devroye, Luc [Auteur]
McGill University = Université McGill [Montréal, Canada]
Lugosi, Gábor [Auteur]
Institució Catalana de Recerca i Estudis Avançats = Catalan Institution for Research and Advanced Studies [ICREA]
Universitat Pompeu Fabra [Barcelona] [UPF]
Neu, Gergely [Auteur]
Sequential Learning [SEQUEL]
McGill University = Université McGill [Montréal, Canada]
Lugosi, Gábor [Auteur]
Institució Catalana de Recerca i Estudis Avançats = Catalan Institution for Research and Advanced Studies [ICREA]
Universitat Pompeu Fabra [Barcelona] [UPF]
Neu, Gergely [Auteur]
Sequential Learning [SEQUEL]
Journal title :
IEEE Transactions on Information Theory
Pages :
4099 - 4106
Publisher :
Institute of Electrical and Electronics Engineers
Publication date :
2015-06-12
ISSN :
0018-9448
English keyword(s) :
Online learning
Online combinatorial optimization
Follow the Perturbed Leader
Random walk
Online combinatorial optimization
Follow the Perturbed Leader
Random walk
HAL domain(s) :
Informatique [cs]/Apprentissage [cs.LG]
English abstract : [en]
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-per ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
European Project :
Collections :
Source :
Files
- https://hal.inria.fr/hal-01214987/document
- Open access
- Access the document
- https://hal.inria.fr/hal-01214987/document
- Open access
- Access the document
- https://hal.inria.fr/hal-01214987/document
- Open access
- Access the document
- document
- Open access
- Access the document
- fpl_journal_final.pdf
- Open access
- Access the document
- document
- Open access
- Access the document
- fpl_journal_final.pdf
- Open access
- Access the document