Skip to Main content Skip to Navigation
Conference papers

Online Learning in Adversarial Lipschitz Environments

Odalric Maillard 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
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(λ)}) where d is the dimension of the search space, T the time horizon, and λ 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Rémi Munos Connect in order to contact the contributor
Submitted on : Friday, August 20, 2010 - 11:50:13 AM
Last modification on : Thursday, January 20, 2022 - 4:16:20 PM
Long-term archiving on: : Tuesday, October 23, 2012 - 12:32:35 PM


Files produced by the author(s)


  • HAL Id : inria-00510674, version 1



Odalric Maillard, Rémi Munos. Online Learning in Adversarial Lipschitz Environments. European Conference on Machine Learing, 2010, Barcelone, Spain. ⟨inria-00510674⟩



Les métriques sont temporairement indisponibles