Learning the Switching Rate by Discretising Bernoulli Sources Online

Steven Rooij, Tim Erven
Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, PMLR 5:432-439, 2009.

Abstract

The expert tracking algorithm Fixed-Share depends on a parameter alpha, called the switching rate. If the final number of outcomes $T$ is known in advance, then the switching rate can be learned with regret $\frac{1}{2} \log T + O(1)$ bits. The current fastest method that achieves this, Learn-alpha, is based on optimal discretisation of the Bernoulli distributions into $O(\sqrt{T})$ bins and runs in $(T\sqrt{T})$ time; however the exact locations of these points have to be determined algorithmically. This paper introduces a new discretisation scheme with the same regret bound for known $T$, that specifies the number and positions of the discretisation points explicitly. The scheme is especially useful when $T$ is not known in advance: a new fully online algorithm, Refine-Online, is presented, which runs in $O(T \sqrt{T} \log T)$ time and achieves a regret of $\frac{1}{2} \log 3 \log T + O(\log \log T)$ bits.

Cite this Paper

BibTeX
@InProceedings{pmlr-v5-rooij09a, title = {Learning the Switching Rate by Discretising Bernoulli Sources Online}, author = {Rooij, Steven and Erven, Tim}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {432--439}, year = {2009}, editor = {van Dyk, David and Welling, Max}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/rooij09a/rooij09a.pdf}, url = {https://proceedings.mlr.press/v5/rooij09a.html}, abstract = {The expert tracking algorithm Fixed-Share depends on a parameter alpha, called the switching rate. If the final number of outcomes $T$ is known in advance, then the switching rate can be learned with regret $\frac{1}{2} \log T + O(1)$ bits. The current fastest method that achieves this, Learn-alpha, is based on optimal discretisation of the Bernoulli distributions into $O(\sqrt{T})$ bins and runs in $(T\sqrt{T})$ time; however the exact locations of these points have to be determined algorithmically. This paper introduces a new discretisation scheme with the same regret bound for known $T$, that specifies the number and positions of the discretisation points explicitly. The scheme is especially useful when $T$ is not known in advance: a new fully online algorithm, Refine-Online, is presented, which runs in $O(T \sqrt{T} \log T)$ time and achieves a regret of $\frac{1}{2} \log 3 \log T + O(\log \log T)$ bits.} }
Endnote
%0 Conference Paper %T Learning the Switching Rate by Discretising Bernoulli Sources Online %A Steven Rooij %A Tim Erven %B Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-rooij09a %I PMLR %P 432--439 %U https://proceedings.mlr.press/v5/rooij09a.html %V 5 %X The expert tracking algorithm Fixed-Share depends on a parameter alpha, called the switching rate. If the final number of outcomes $T$ is known in advance, then the switching rate can be learned with regret $\frac{1}{2} \log T + O(1)$ bits. The current fastest method that achieves this, Learn-alpha, is based on optimal discretisation of the Bernoulli distributions into $O(\sqrt{T})$ bins and runs in $(T\sqrt{T})$ time; however the exact locations of these points have to be determined algorithmically. This paper introduces a new discretisation scheme with the same regret bound for known $T$, that specifies the number and positions of the discretisation points explicitly. The scheme is especially useful when $T$ is not known in advance: a new fully online algorithm, Refine-Online, is presented, which runs in $O(T \sqrt{T} \log T)$ time and achieves a regret of $\frac{1}{2} \log 3 \log T + O(\log \log T)$ bits.
RIS
TY - CPAPER TI - Learning the Switching Rate by Discretising Bernoulli Sources Online AU - Steven Rooij AU - Tim Erven BT - Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-rooij09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 432 EP - 439 L1 - http://proceedings.mlr.press/v5/rooij09a/rooij09a.pdf UR - https://proceedings.mlr.press/v5/rooij09a.html AB - The expert tracking algorithm Fixed-Share depends on a parameter alpha, called the switching rate. If the final number of outcomes $T$ is known in advance, then the switching rate can be learned with regret $\frac{1}{2} \log T + O(1)$ bits. The current fastest method that achieves this, Learn-alpha, is based on optimal discretisation of the Bernoulli distributions into $O(\sqrt{T})$ bins and runs in $(T\sqrt{T})$ time; however the exact locations of these points have to be determined algorithmically. This paper introduces a new discretisation scheme with the same regret bound for known $T$, that specifies the number and positions of the discretisation points explicitly. The scheme is especially useful when $T$ is not known in advance: a new fully online algorithm, Refine-Online, is presented, which runs in $O(T \sqrt{T} \log T)$ time and achieves a regret of $\frac{1}{2} \log 3 \log T + O(\log \log T)$ bits. ER -
APA
Rooij, S. & Erven, T.. (2009). Learning the Switching Rate by Discretising Bernoulli Sources Online. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:432-439 Available from https://proceedings.mlr.press/v5/rooij09a.html.

Related Material