A Chaining Algorithm for Online Nonparametric Regression

Pierre Gaillard, Sébastien Gerchinovitz
Proceedings of The 28th Conference on Learning Theory, PMLR 40:764-796, 2015.

Abstract

We consider the problem of online nonparametric regression with arbitrary deterministic sequences. Using ideas from the chaining technique, we design an algorithm that achieves a Dudley-type regret bound similar to the one obtained in a non-constructive fashion by Rakhlin and Sridharan (2014). Our regret bound is expressed in terms of the metric entropy in the sup norm, which yields optimal guarantees when the metric and sequential entropies are of the same order of magnitude. In particular our algorithm is the first one that achieves optimal rates for online regression over Hölder balls. In addition we show for this example how to adapt our chaining algorithm to get a reasonable computational efficiency with similar regret guarantees (up to a log factor).

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Gaillard15, title = {A Chaining Algorithm for Online Nonparametric Regression}, author = {Gaillard, Pierre and Gerchinovitz, Sébastien}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {764--796}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Gaillard15.pdf}, url = {https://proceedings.mlr.press/v40/Gaillard15.html}, abstract = {We consider the problem of online nonparametric regression with arbitrary deterministic sequences. Using ideas from the chaining technique, we design an algorithm that achieves a Dudley-type regret bound similar to the one obtained in a non-constructive fashion by Rakhlin and Sridharan (2014). Our regret bound is expressed in terms of the metric entropy in the sup norm, which yields optimal guarantees when the metric and sequential entropies are of the same order of magnitude. In particular our algorithm is the first one that achieves optimal rates for online regression over Hölder balls. In addition we show for this example how to adapt our chaining algorithm to get a reasonable computational efficiency with similar regret guarantees (up to a log factor).} }
Endnote
%0 Conference Paper %T A Chaining Algorithm for Online Nonparametric Regression %A Pierre Gaillard %A Sébastien Gerchinovitz %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Gaillard15 %I PMLR %P 764--796 %U https://proceedings.mlr.press/v40/Gaillard15.html %V 40 %X We consider the problem of online nonparametric regression with arbitrary deterministic sequences. Using ideas from the chaining technique, we design an algorithm that achieves a Dudley-type regret bound similar to the one obtained in a non-constructive fashion by Rakhlin and Sridharan (2014). Our regret bound is expressed in terms of the metric entropy in the sup norm, which yields optimal guarantees when the metric and sequential entropies are of the same order of magnitude. In particular our algorithm is the first one that achieves optimal rates for online regression over Hölder balls. In addition we show for this example how to adapt our chaining algorithm to get a reasonable computational efficiency with similar regret guarantees (up to a log factor).
RIS
TY - CPAPER TI - A Chaining Algorithm for Online Nonparametric Regression AU - Pierre Gaillard AU - Sébastien Gerchinovitz BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Gaillard15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 764 EP - 796 L1 - http://proceedings.mlr.press/v40/Gaillard15.pdf UR - https://proceedings.mlr.press/v40/Gaillard15.html AB - We consider the problem of online nonparametric regression with arbitrary deterministic sequences. Using ideas from the chaining technique, we design an algorithm that achieves a Dudley-type regret bound similar to the one obtained in a non-constructive fashion by Rakhlin and Sridharan (2014). Our regret bound is expressed in terms of the metric entropy in the sup norm, which yields optimal guarantees when the metric and sequential entropies are of the same order of magnitude. In particular our algorithm is the first one that achieves optimal rates for online regression over Hölder balls. In addition we show for this example how to adapt our chaining algorithm to get a reasonable computational efficiency with similar regret guarantees (up to a log factor). ER -
APA
Gaillard, P. & Gerchinovitz, S.. (2015). A Chaining Algorithm for Online Nonparametric Regression. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:764-796 Available from https://proceedings.mlr.press/v40/Gaillard15.html.

Related Material