Learning with stochastic inputs and adversarial outputs

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 : Most of the research in online learning is focused either on the problem of adversarial classification (i.e., both inputs and labels are arbitrarily chosen by an adversary) or on the traditional supervised learning problem in which samples are independent and identically distributed according to a stationary probability distribution. Nonetheless, in a number of domains the relationship between inputs and outputs may be adversarial, whereas input instances are i.i.d. from a stationary distribution (e.g., user preferences). This scenario can be formalized as a learning problem with stochastic inputs and adversarial outputs. In this paper, we introduce this novel stochastic-adversarial learning setting and we analyze its learnability. In particular, we show that in a binary classification problem over an horizon of $n$ rounds, given a hypothesis space $\hypSpace$ with finite VC-dimension, it is possible to design an algorithm that incrementally builds a suitable finite set of hypotheses from $\hypSpace$ used as input for an exponentially weighted forecaster and achieves a cumulative regret of order $\bigO(\sqrt{n\VCdim(\hypSpace)\log n})$ with overwhelming probability. This result shows that whenever inputs are i.i.d. it is possible to solve any binary classification problem using a finite VC-dimension hypothesis space with a sub-linear regret independently from the way labels are generated (either stochastic or adversarial). We also discuss extensions to multi-class classification, regression, learning from experts and bandit settings with stochastic side information, and application to games.
Keywords :
Type de document :
Article dans une revue
Journal of Computer and System Sciences (JCSS), Elsevier, 2012, 78 (5), pp.1516-1537. 〈http://www.sciencedirect.com/science/article/pii/S002200001200027X〉

Littérature citée [24 références]

https://hal.inria.fr/hal-00772046
Contributeur : Alessandro Lazaric <>
Soumis le : jeudi 10 janvier 2013 - 11:25:11
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : samedi 1 avril 2017 - 02:53:54

Fichier

Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : hal-00772046, version 1

Citation

Alessandro Lazaric, Rémi Munos. Learning with stochastic inputs and adversarial outputs. Journal of Computer and System Sciences (JCSS), Elsevier, 2012, 78 (5), pp.1516-1537. 〈http://www.sciencedirect.com/science/article/pii/S002200001200027X〉. 〈hal-00772046〉

Métriques

Consultations de la notice

388

Téléchargements de fichiers