Random-Walk Perturbations for Online Combinatorial Optimization

Devroye, Luc; Lugosi, Gábor; Neu, Gergely

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1109/TIT.2015.2428253

Titre :

Random-Walk Perturbations for Online Combinatorial Optimization

Auteur(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]

Titre de la revue :

IEEE Transactions on Information Theory

Pagination :

4099 - 4106

Éditeur :

Institute of Electrical and Electronics Engineers

Date de publication :

2015-06-12

ISSN :

0018-9448

Mot(s)-clé(s) en anglais :

Online learning
Online combinatorial optimization
Follow the Perturbed Leader
Random walk

Discipline(s) HAL :

Informatique [cs]/Apprentissage [cs.LG]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet Européen :

Composing Learning for Artificial Cognitive Systems

Collections :