Learning the Switching Rate by Discretising Bernoulli Sources Online
Steven de Rooij, Tim van Erven · International Conference on Artificial Intelligence and Statistics · 2009
The expert tracking algorithm Fixed-Share depends on a parameter �, called the switching rate. The switching rate can be learned online with regret 1 logT + O(1) bits. The current fastest method to achieve this is based on optimal discretisation of the Bernoulli distributions into O( √ T) bins and runs in O(T √ T) time. However, the exact locations of these bins have to be determined algorithmically, and the final number of outcomes T must be known in advance. 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, however, when T is not known in advance: a new fully online algorithm is presented, which runs in O(T √ T logT) time and achieves a regret of 1 2 log3logT +O(loglogT) bits.