Following the Perturbed Leader for Online Structured Learning

Alon Cohen, Tamir Hazan
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1034-1042, 2015.

Abstract

We investigate a new Follow the Perturbed Leader (FTPL) algorithm for online structured prediction problems. We show a regret bound which is comparable to the state of the art of FTPL algorithms and is comparable with the best possible regret in some cases. To better understand FTPL algorithms for online structured learning, we present a lower bound on the regret for a large and natural class of FTPL algorithms that use logconcave perturbations. We complete our investigation with an online shortest path experiment and empirically show that our algorithm is both statistically and computationally efficient.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-cohena15, title = {Following the Perturbed Leader for Online Structured Learning}, author = {Cohen, Alon and Hazan, Tamir}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1034--1042}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/cohena15.pdf}, url = {https://proceedings.mlr.press/v37/cohena15.html}, abstract = {We investigate a new Follow the Perturbed Leader (FTPL) algorithm for online structured prediction problems. We show a regret bound which is comparable to the state of the art of FTPL algorithms and is comparable with the best possible regret in some cases. To better understand FTPL algorithms for online structured learning, we present a lower bound on the regret for a large and natural class of FTPL algorithms that use logconcave perturbations. We complete our investigation with an online shortest path experiment and empirically show that our algorithm is both statistically and computationally efficient.} }
Endnote
%0 Conference Paper %T Following the Perturbed Leader for Online Structured Learning %A Alon Cohen %A Tamir Hazan %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-cohena15 %I PMLR %P 1034--1042 %U https://proceedings.mlr.press/v37/cohena15.html %V 37 %X We investigate a new Follow the Perturbed Leader (FTPL) algorithm for online structured prediction problems. We show a regret bound which is comparable to the state of the art of FTPL algorithms and is comparable with the best possible regret in some cases. To better understand FTPL algorithms for online structured learning, we present a lower bound on the regret for a large and natural class of FTPL algorithms that use logconcave perturbations. We complete our investigation with an online shortest path experiment and empirically show that our algorithm is both statistically and computationally efficient.
RIS
TY - CPAPER TI - Following the Perturbed Leader for Online Structured Learning AU - Alon Cohen AU - Tamir Hazan BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-cohena15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1034 EP - 1042 L1 - http://proceedings.mlr.press/v37/cohena15.pdf UR - https://proceedings.mlr.press/v37/cohena15.html AB - We investigate a new Follow the Perturbed Leader (FTPL) algorithm for online structured prediction problems. We show a regret bound which is comparable to the state of the art of FTPL algorithms and is comparable with the best possible regret in some cases. To better understand FTPL algorithms for online structured learning, we present a lower bound on the regret for a large and natural class of FTPL algorithms that use logconcave perturbations. We complete our investigation with an online shortest path experiment and empirically show that our algorithm is both statistically and computationally efficient. ER -
APA
Cohen, A. & Hazan, T.. (2015). Following the Perturbed Leader for Online Structured Learning. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1034-1042 Available from https://proceedings.mlr.press/v37/cohena15.html.

Related Material