Timezone: »
We consider the learning task consisting in predicting as well as the best function in a finite reference set G up to the smallest possible additive term. If R(g) denotes the generalization error of a prediction function g, under reasonable assumptions on the loss function (typically satisfied by the least square loss when the output is bounded), it is known that the progressive mixture rule gn satisfies E R(gn) < min_{g in G} R(g) + Cst (logG)/n where n denotes the size of the training set, E denotes the expectation wrt the training set distribution. This work shows that, surprisingly, for appropriate reference sets G, the deviation convergence rate of the progressive mixture rule is only no better than Cst / sqrt{n}, and not the expected Cst / n. It also provides an algorithm which does not suffer from this drawback.
Author Information
JeanYves Audibert (Université Paris Est)
More from the Same Authors

2008 Session: Oral session 9: Sparse Learning and Ranking »
JeanYves Audibert 
2008 Poster: Algorithms for Infinitely ManyArmed Bandits »
Yizao Wang · JeanYves Audibert · Remi Munos 
2008 Spotlight: Algorithms for Infinitely ManyArmed Bandits »
Yizao Wang · JeanYves Audibert · Remi Munos