Optimal amortized regret in every interval

Rina Panigrahy, Preyas Popat
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:352-360, 2014.

Abstract

Consider the classical problem of predicting the next bit in a sequence of bits. A standard performance measure is regret (loss in payoff) with respect to a set of experts. For exam- ple if we measure performance with respect to two constant experts one that always predicts 0’s and another that always predicts 1’s it is well known that one can get regret O( $\sqrt{}$ T) with respect to the best expert by using, say, the weighted majority algorithm [LW89]. But this algorithm does not provide performance guaran- tee in any interval. There are other algorithms (see [BM07, FSSW97, Vov99]) that ensure regret O($\sqrt{}$x log T) in any interval of length x. In this paper we show a randomized algorithm that in an amortized sense gets a regret of O($\sqrt{}$x) for any interval when the sequence is partitioned into in- tervals arbitrarily. We empirically estimated the constant in the O() for T upto 2000 and found it to be small – around 2.1. We also experimentally evaluate the efficacy of this algorithm in predict- ing high frequency stock data. $*$This work was done while this author was at Microsoft Re- search.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-panigrahy14a, title = {Optimal amortized regret in every interval}, author = {Panigrahy, Rina and Popat, Preyas}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {352--360}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/panigrahy14a/panigrahy14a.pdf}, url = {https://proceedings.mlr.press/r12/panigrahy14a.html}, abstract = {Consider the classical problem of predicting the next bit in a sequence of bits. A standard performance measure is regret (loss in payoff) with respect to a set of experts. For exam- ple if we measure performance with respect to two constant experts one that always predicts 0’s and another that always predicts 1’s it is well known that one can get regret O( $\sqrt{}$ T) with respect to the best expert by using, say, the weighted majority algorithm [LW89]. But this algorithm does not provide performance guaran- tee in any interval. There are other algorithms (see [BM07, FSSW97, Vov99]) that ensure regret O($\sqrt{}$x log T) in any interval of length x. In this paper we show a randomized algorithm that in an amortized sense gets a regret of O($\sqrt{}$x) for any interval when the sequence is partitioned into in- tervals arbitrarily. We empirically estimated the constant in the O() for T upto 2000 and found it to be small – around 2.1. We also experimentally evaluate the efficacy of this algorithm in predict- ing high frequency stock data. $*$This work was done while this author was at Microsoft Re- search.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Optimal amortized regret in every interval %A Rina Panigrahy %A Preyas Popat %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-panigrahy14a %I PMLR %P 352--360 %U https://proceedings.mlr.press/r12/panigrahy14a.html %V R12 %X Consider the classical problem of predicting the next bit in a sequence of bits. A standard performance measure is regret (loss in payoff) with respect to a set of experts. For exam- ple if we measure performance with respect to two constant experts one that always predicts 0’s and another that always predicts 1’s it is well known that one can get regret O( $\sqrt{}$ T) with respect to the best expert by using, say, the weighted majority algorithm [LW89]. But this algorithm does not provide performance guaran- tee in any interval. There are other algorithms (see [BM07, FSSW97, Vov99]) that ensure regret O($\sqrt{}$x log T) in any interval of length x. In this paper we show a randomized algorithm that in an amortized sense gets a regret of O($\sqrt{}$x) for any interval when the sequence is partitioned into in- tervals arbitrarily. We empirically estimated the constant in the O() for T upto 2000 and found it to be small – around 2.1. We also experimentally evaluate the efficacy of this algorithm in predict- ing high frequency stock data. $*$This work was done while this author was at Microsoft Re- search. %Z Reissued by PMLR on 04 October 2026.
APA
Panigrahy, R. & Popat, P.. (2014). Optimal amortized regret in every interval. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:352-360 Available from https://proceedings.mlr.press/r12/panigrahy14a.html. Reissued by PMLR on 04 October 2026.

Related Material