Shifting Regret, Mirror Descent, and Matrices

Andras Gyorgy, Csaba Szepesvari
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2943-2951, 2016.

Abstract

We consider the problem of online prediction in changing environments. In this framework the performance of a predictor is evaluated as the loss relative to an arbitrarily changing predictor, whose individual components come from a base class of predictors. Typical results in the literature consider different base classes (experts, linear predictors on the simplex, etc.) separately. Introducing an arbitrary mapping inside the mirror decent algorithm, we provide a framework that unifies and extends existing results. As an example, we prove new shifting regret bounds for matrix prediction problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-gyorgy16, title = {Shifting Regret, Mirror Descent, and Matrices}, author = {Gyorgy, Andras and Szepesvari, Csaba}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2943--2951}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/gyorgy16.pdf}, url = {https://proceedings.mlr.press/v48/gyorgy16.html}, abstract = {We consider the problem of online prediction in changing environments. In this framework the performance of a predictor is evaluated as the loss relative to an arbitrarily changing predictor, whose individual components come from a base class of predictors. Typical results in the literature consider different base classes (experts, linear predictors on the simplex, etc.) separately. Introducing an arbitrary mapping inside the mirror decent algorithm, we provide a framework that unifies and extends existing results. As an example, we prove new shifting regret bounds for matrix prediction problems.} }
Endnote
%0 Conference Paper %T Shifting Regret, Mirror Descent, and Matrices %A Andras Gyorgy %A Csaba Szepesvari %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-gyorgy16 %I PMLR %P 2943--2951 %U https://proceedings.mlr.press/v48/gyorgy16.html %V 48 %X We consider the problem of online prediction in changing environments. In this framework the performance of a predictor is evaluated as the loss relative to an arbitrarily changing predictor, whose individual components come from a base class of predictors. Typical results in the literature consider different base classes (experts, linear predictors on the simplex, etc.) separately. Introducing an arbitrary mapping inside the mirror decent algorithm, we provide a framework that unifies and extends existing results. As an example, we prove new shifting regret bounds for matrix prediction problems.
RIS
TY - CPAPER TI - Shifting Regret, Mirror Descent, and Matrices AU - Andras Gyorgy AU - Csaba Szepesvari BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-gyorgy16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2943 EP - 2951 L1 - http://proceedings.mlr.press/v48/gyorgy16.pdf UR - https://proceedings.mlr.press/v48/gyorgy16.html AB - We consider the problem of online prediction in changing environments. In this framework the performance of a predictor is evaluated as the loss relative to an arbitrarily changing predictor, whose individual components come from a base class of predictors. Typical results in the literature consider different base classes (experts, linear predictors on the simplex, etc.) separately. Introducing an arbitrary mapping inside the mirror decent algorithm, we provide a framework that unifies and extends existing results. As an example, we prove new shifting regret bounds for matrix prediction problems. ER -
APA
Gyorgy, A. & Szepesvari, C.. (2016). Shifting Regret, Mirror Descent, and Matrices. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2943-2951 Available from https://proceedings.mlr.press/v48/gyorgy16.html.

Related Material