Open Problem: Second order regret bounds based on scaling time

Yoav Freund
29th Annual Conference on Learning Theory, PMLR 49:1651-1654, 2016.

Abstract

We argue that the second order bounds given in Cesa-Bianchi2006, which accumulate the square of the loss of each action separately, are loose. We propose a different form of a second order bound and conjecture the it is satisfied by NormalHedge ChaudhuriFrHs2009.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-freund16, title = {Open Problem: Second order regret bounds based on scaling time}, author = {Freund, Yoav}, booktitle = {29th Annual Conference on Learning Theory}, pages = {1651--1654}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/freund16.pdf}, url = {https://proceedings.mlr.press/v49/freund16.html}, abstract = {We argue that the second order bounds given in Cesa-Bianchi2006, which accumulate the square of the loss of each action separately, are loose. We propose a different form of a second order bound and conjecture the it is satisfied by NormalHedge ChaudhuriFrHs2009.} }
Endnote
%0 Conference Paper %T Open Problem: Second order regret bounds based on scaling time %A Yoav Freund %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-freund16 %I PMLR %P 1651--1654 %U https://proceedings.mlr.press/v49/freund16.html %V 49 %X We argue that the second order bounds given in Cesa-Bianchi2006, which accumulate the square of the loss of each action separately, are loose. We propose a different form of a second order bound and conjecture the it is satisfied by NormalHedge ChaudhuriFrHs2009.
RIS
TY - CPAPER TI - Open Problem: Second order regret bounds based on scaling time AU - Yoav Freund BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-freund16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 1651 EP - 1654 L1 - http://proceedings.mlr.press/v49/freund16.pdf UR - https://proceedings.mlr.press/v49/freund16.html AB - We argue that the second order bounds given in Cesa-Bianchi2006, which accumulate the square of the loss of each action separately, are loose. We propose a different form of a second order bound and conjecture the it is satisfied by NormalHedge ChaudhuriFrHs2009. ER -
APA
Freund, Y.. (2016). Open Problem: Second order regret bounds based on scaling time. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:1651-1654 Available from https://proceedings.mlr.press/v49/freund16.html.

Related Material