Home Page

Papers

Submissions

News

Scope

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

Learning the Switching Rate by Discretising Bernoulli Sources Online

Steven de Rooij, Tim van Erven; JMLR W&CP 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 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(√T) bins and runs in O(T√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 on-line algorithm, Refine-Online, is presented, which runs in O(T√T log T) time and achieves a regret of 1/2 log 3 log T + O(log log T) bits.



Home Page

Papers

Submissions

News

Scope

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

Page last modified on Fri Apr 3 20:30:46 BST 2009.

Copyright @ JMLR 2000. All rights reserved.