Learning the Switching Rate by Discretising Bernoulli Sources Online

Steven Rooij; Tim Erven

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

Download PDF