Overblog Follow this blog
Edit post Administration Create my blog
February 28 2013 5 28 /02 /February /2013 19:05

By Alexandra Carpentier and Odalric-Ambrym Maillard.
In Proceedings of the 25th conference on advances in Neural Information Processing Systems, NIPS '12, 2012.


In the setting of active learning for the multi-armed bandit, where the goal of a learner is to estimate with equal precision the mean of a finite number of arms, recent results show that it is possible to derive strategies based on finite-time confidence bounds that are competitive with the best possible strategy. We here consider an extension of this problem to the case when the arms are the cells of a finite partition P of a continuous sampling space X \subset \Real^d. Our goal is now to build a piecewise constant approximation of a noisy function (where each piece is one region of P and P is fixed beforehand) in order to maintain the local quadratic error of approximation on each cell equally low. Although this extension is not trivial, we show that a simple algorithm based on upper confidence bounds can be proved to be adaptive to the function itself in a near-optimal way, when |P| is chosen to be of minimax-optimal order on the class of \alpha-Hölder functions.


You can dowload the paper from the NIPS website (here) or from the HAL online open depository* (here).


  title = {Online allocation and homogeneous partitioning for piecewise constant mean-approximation.},
  author = {Carpentier, Alexandra and Maillard, Odalric-Ambrym},

  booktitle = {Advances in Neural Information Processing Systems 25},
  editor = {P. Bartlett and F.C.N. Pereira and C.J.C. Burges and L. Bottou and K.Q. Weinberger},
  pages = {1970-1978},
  year = {2012}




* The HAL open-access online archive system seeks to make research results available to the widest audience, independently of the major publisher, and cooperates with other large international archives like arXiv.

Share this post

Repost 0
Published by Odalric-Ambrym Maillard - in Discussing articles
write a comment





Senior Researcher



The Technion
Faculty of Electrical Engineering,
Fishbach Bldg, Rm. 462
32000 Haifa, ISRAEL
Tel: +972 (0)48293638