Online Learning in Adversarial Lipschitz Environments

Odalric-Ambrym Maillard, Rémi Munos.
In ECML-PKDD’10, pages 305–320, 2010

[Download]

Abstract:

We consider the problem of online learning in an adversarial environment when the reward functions chosen by the adversary are assumed to be Lipschitz. This setting extends previous works on linear and convex online learning. We  provide a class of algorithms with cumulative regret upper bounded by O(\sqrt{dT ln(\lambda)}) where d is the dimension of the search space, T the time horizon, and \lambda the Lipschitz constant. Efficient numerical implementations using particle methods are discussed. Applications include online supervised learning problems for both full and partial (bandit) information settings, for a large class of non-linear regressors/classifiers, such as neural networks.

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

Bibtex:

@inproceedings{MaillardM10a, author = {{Odalric-Ambrym} Maillard and R\'{e}mi Munos}, title = {Online Learning in Adversarial Lipschitz Environments.}, booktitle = {Machine Learning and Knowledge Discovery in Databases, European Conference, {ECML} {PKDD} 2010, Barcelona, Spain, September 20-24, 2010, Proceedings, Part {II}}, year = {2010}, pages = {305–320}, editor = {Jos\'{e} L. Balc\`{a}zar and Francesco Bonchi and Aristides Gionis and Mich\`{e}le Sebag}, series = {Lecture Notes in Computer Science}, year = {2010}, volume = {6322}, publisher = {Springer} }