Alessandro Lazaric
email: alessandro.lazaric@inria.fr

Rémi Munos
email: remi.munos@inria.fr

Learning with Stochastic Inputs and Adversarial Outputs

Keywords:

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 binary classification, given a hypothesis space H with finite VC-dimension, it is possible to design an algorithm which incrementally builds a suitable finite set of hypotheses from H used as input for an exponentially weighted forecaster and achieves a cumulative regret of order O( nV C(H) 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 VCdimension hypothesis space with a sub-linear regret independently from the way labels are generated (either stochastic or adversarial). We also discuss extensions to multi-label classification, regression, learning from experts and bandit settings with stochastic side information, and application to games.

Introduction

Motivation and relevance. The problem of classification has been intensively studied both in the stochastic and adversarial settings. In the former, inputs and labels are jointly drawn from a stationary probability distribution, while in the latter no assumption is made on the way the sequence of inputlabel pairs is generated. Although the adversarial setting allows to consider a wide range of problems by dropping any assumption about the way data are generated, in many applications it is possible to consider an hybrid scenario in which inputs are independent and identically distribution (i.i.d.) from a distribution and labels are adversarially chosen. Let us consider a classification problem in which a company tries to predict whether a user is likely to buy an item or not (e.g., a new model of mobile phone, a new service) on the basis of a set of features describing her profile (e.g., sex, age, salary, etc.). In the medium-term, user profiles can be well assumed as coming from a stationary distribution. In fact, features such as age and salary are almost constant and their distribution in a sample set does not change in time. On the other hand, user preferences may rapidly change in an unpredictable way (e.g., because of competitors who released a new product). This scenario can be formalized as a classification problem with stochastic inputs and adversarial labels. Alternatively, the problem can be casted as a two-player games in which the structure of the game (i.e., the payoffs) is determined by a stochastic event x (e.g., a card, a dice). At each round both the learner and the adversary select a strategy h defined over all the possible events and plays the corresponding action h(x). In general, the resulting payoff for the two players is a function of the actions and the stochastic event x. The Nash equilibrium of such a game is a pair of mixed strategies (i.e., a probability distribution over the set of pure strategies) such that their expected payoff (where expectation is taken on strategies randomization and the event distribution) cannot be improved by unilateral deviations from equilibrium strategies. Definition of the general problem. More formally, we consider the general prediction problem summarized in the protocol in Figure 1. At each round t an input x t is drawn from a stationary distribution P (unknown to the learner) and revealed to both the learner and the adversary. Simultaneously, the adversary chooses a loss function t and the learner chooses a 1: for t = 1, 2, . . . do Learner predicts y t = h t (x t ) ∈ Y 5:

Learner observes the feedback:

t ( y t ) (in case of bandit information) or t (•) (in case of full information) 6:

Learner incurs a loss t ( y t ) 7: end for hypothesis h t in a hypothesis space H and predicts y t = h t (x t ). The feedback returned to the learner can be either the loss function t (i.e., full information) or just the loss t ( y t ) of the chosen prediction (i.e., bandit information). The objective of the learner is to minimize her regret, that is to incur a cumulative loss that is almost as small as the one obtained by the best hypothesis in H on the same sequence of inputs drawn from P and loss functions provided by the adversary. Formally, for any n > 0, the regret of an algorithm A is

R n (A) = n t=1 t (h t (x t )) -inf h∈H n t=1 t (h(x t )), (1)
where h t is the hypothesis chosen by A at time t.

Results so far. In the full information adversarial setting, many theoretical results are available for online learning algorithms with different hypothesis spaces.

Finite spaces. Given a finite set of N experts (i.e., hypotheses) as input, at each round the exponentially weighted forecaster (EWF) [START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Cesa-Bianchi | How to use expert advice[END_REF][START_REF] Vovk | A game of prediction with expert advice[END_REF] randomizes on experts' predictions with a probability concentrated on experts which had a good performance so far (i.e., low cumulative loss). Despite its simplicity, the EWF achieves a regret upper-bounded by O( √ n log N ), where n is the time horizon of the problem. Although the logarithmic dependency on the number of experts allows the use of a large number of experts, the EWF cannot be directly extended to the case of infinite sets of experts. Linear spaces. Many margin based algorithms with linear hypotheses have been proposed for adversarial classification [START_REF] Rosenblatt | The perceptron : A probabilistic model for information storage and organization in the brain[END_REF][START_REF] Weston | Support vector machines for multi-class pattern recognition[END_REF][START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF]. The simplest example of this class of algorithms is the perceptron [START_REF] Rosenblatt | The perceptron : A probabilistic model for information storage and organization in the brain[END_REF] in which a weight vector w is updated whenever a prediction mistake is made. The number of classification mistakes of the perceptron is bounded (see Theorem 12.1 in [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]) by L + D + √ LD where L is the cumulative loss and D is the complexity of any weight vector. In the linearly separable case (i.e., input-label pairs can be perfectly classified by a linear classifier, that is L = 0), the number of mistake is finite (for any time horizon n) and depends on the complexity D of the weight vector corresponding to the optimal classifier.1 General spaces. The agnostic online learning algorithm recently proposed by [START_REF] Ben-David | Agnostic online learning[END_REF] successfully merges the effectiveness of the EWF with the general case of an infinite hypothesis set H. Under the assumption that the Littlestone dimension [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF] of H is finite (Ldim(H) < ∞), it is possible to define a suitable finite subset of H such that the EWF achieves a regret of the order of O(Ldim(H) + nLdim(H) log n).

The problem of classification with partial information (also known as contextual bandit problem) is of major interest in applications in which the true label is not revealed and only the loss for the chosen label is returned to the learner (e.g., recommendation systems). This scenario is analyzed by [START_REF] Langford | The epoch greedy algorithm for contextual multi-armed bandits[END_REF] in the fully stochastic setting. They introduce an epoch-based online learning algorithm whose regret can be bounded by merging supervised sample bounds with bandit bounds. [START_REF] Kakade | Efficient bandit algorithms for online multiclass prediction[END_REF] propose a modification of the perceptron (i.e., the banditron) to solve the online multi-label classification problem in the fully adversarial case. In particular, they analyze the performance of the banditron in terms of mistake bounds with particular attention to the linearly separable case. Contributions. While all the previous approaches consider either the fully adversarial or fully stochastic setting, in this paper, we analyze the problem of prediction in case of stochastic inputs and adversarial loss functions. The main contributions of this paper can be summarized as follows: (i) introduction of the stochastic-adversarial learning setting, (ii) design of an online learning algorithm with polynomial complexity in n (with exponent the VCdimension of H) achieving a sub-linear regret, (iii) analysis of the learnability of the stochastic-adversarial setting revealing the same complexity measure as the fully stochastic setting, (iv) extension to other learning scenarios such as partial information, regression, and games. Outline. In Section 2, we consider a specific instance of the general problem of Figure 1, that is the problem of binary classification with full information. In Section 3 we drop any assumption about the distribution and the existence of auxiliary samples and devise an epoch-based algorithm that, given a hypothesis set H as input, incrementally builds a finite subset of H on the basis of the sequence of inputs experienced so far. At the beginning of each epoch, a new subset of H is generated and it is given as input to a EWF which is run until the end of the epoch. Because of the stochastic assumption about the generation of inputs, the complexity of the hypothesis space H can be measured according to the VC-dimension instead of the Littlestone dimension like in the agnostic online learning algorithm. As a result, the algorithm performance can be directly obtained by merging the EWF performance in the adversarial setting and usual capacity measures for hypothesis spaces in stochastic problems (e.g., their VC-dimension). The resulting algorithm is proved to incur a regret of order O( nV C(H) log n) with overwhelming probability. The computational complexity of the algorithm is discussed in Section 4. A number of extensions are then considered in Section 5 for multilabel prediction, regression, bandit information, and games with stochastic side information. Section 6 compares the proposed algorithm with existing online learning algorithms for the stochastic or adversarial setting. Finally, in Section 7 we draw conclusions.

The Problem

Notation. In this section, we formally define the problem of binary classification and we introduce the notation used in the rest of the paper. Let X be the input space, P a probability distribution defined on X , and Y = {0, 1} the set of labels. The learner is given as input a (possibly infinite) set H of hypotheses of the form h : X → Y, mapping each possible input to a label. Learner incurs a loss ( y t , y t ) = I { y t = y t } 7: end for We define the disagreement between two hypotheses h, h ∈ H as

∆(h, h ) = E x∼P [I {h(x) = h (x)}] , (2)
(where I {ξ} = 1 when event ξ is true, and 0 otherwise) that is, the probability that h and h make different predictions given inputs drawn from P .

The protocol. The on-line classification problem we consider is summarized in Figure 2. The main difference with the general setting (Figure 1) is that at each round t the adversary chooses a label y t 2 , and the learner incurs a loss ( y t , y t ) defined as I { y t = y t }. In the following, we will use the short form t (h) for (h(x t ), y t ) with h ∈ H. Since at the end of each round the true label y t is explicitly revealed (i.e., full information feedback), the learner can compute the loss for any hypothesis in H. The objective of the learner is to minimize regret (1). As it can be noticed, in general the loss t (h t ) is a random variable that depends on the (random) loss function t chosen by the adversary, the (randomized) algorithm, and the distribution P . In the following, we consider the case of oblivious adversaries, so that the sequence of functions t is fixed in advance. Thus, all the results presented in the paper will be stated in high-probability with respect to two sources of randomness: the algorithm and the samples. In the next section, we introduce the Epoch-based Stochastic Adversarial (EStochAd) forecaster for the classification problem with stochastic inputs and adversarial labels.

Hybrid Stochastic-Adversarial Algorithms

Finite hypothesis space

Before entering in details about the algorithm, we briefly recall the EWF with side information with a finite number of experts. Let the hypothesis space H contain N < ∞ hypotheses (i.e., experts). At time t, each hypothesis h i (i ∈ {1, . . . , N }) has a weight

w t i = exp -η t-1 s=1 s (h i ) (3)
where η is a strictly positive parameter. According to the previous definition, the smaller the cumulative loss the higher the weight for the hypothesis. At each step t, a loss function t is adversarially chosen and at the same time, the EWF randomly selects a hypothesis h t according to a distribution p t = (p t 1 , . . . , p t N ), where p t i =

w t i N j=1 w t j .
As a result, it incurs a loss t (h t ). At the end of each round, weights are recomputed according to (3) (or updated using an incremental version of (3)). The following result provides an upperbound on the regret for EWF .

Theorem 1. (see Cesa-Bianchi & Lugosi, 2006, pg. 72) Let : Y × Y → [0, 1] be a loss function. For any n, N ≥ 1, 0 ≤ β ≤ 1, η > 0 and w 1 i = 1, i ∈ {1, . . . , N } the exponentially weighted average forecaster satisfies

R n = n t=1 t (h t ) -min h∈H n t=1 t (h) ≤ log N η + nη 8 + n 2 log 1 β ,
with probability at least 1β. Optimizing the parameter η = 8 log N/n, the bound becomes

R n ≤ n log N 2 + n 2 log 1 β . (4) H N h 1 H h i h N H i H 1
Figure 3: The hypothesis space H can be partitioned into classes containing hypotheses with the same sequence of prediction on inputs {x t } n t=1 . The grid H n is obtained by selecting one hypothesis for each class of the partition.

The implicit assumption in the previous theorem is that the time horizon n is known in advance. As usual, it is possible to obtain an anytime result for the previous algorithm by setting the learning parameter η to be a decreasing function of t (see e.g. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]). As it can be noticed, the EWF has a logarithmic dependency on the number of experts, thus allowing to consider large sets of experts. Nonetheless, the EWF cannot be directly applied when H contains an infinite number of hypotheses. In next sections we show that when inputs are drawn from a fixed distribution and the hypothesis space has a finite VC-dimension, it is possible to incrementally define a finite subset of H that can be used as input for a EWF with a regret of the same order as in (4).

Infinite hypothesis space

Sequence of inputs known in advance. First we show that for any finite VC-dimension hypothesis space H and any sequence of inputs, it is possible to define in hindsight a finite subset H ⊂ H that contains hypotheses with exactly the same performance as those in the full set H. Let V C(H) = d < ∞ and {x t } n t=1 be a sequence of i.i.d. inputs drawn from P . On the basis of {x t } n t=1 , we define a partition P n = {H i } i≤N of H, such that each class H i contains hypotheses with the same sequence of predictions up to time n (i.e., ∀h, h ∈ H i , h(x s ) = h (x s ), ∀s ≤ n). From each class we pick an arbitrary hypothesis h i ∈ H i and we define the grid H n = {h i } i≤N . Since H has a finite VC-dimension, for any n > 0 the cardinality of H n is bounded by [START_REF] Sauer | On the densities of families of sets[END_REF]. The grid H n can also be incrementally refined as inputs are revealed. For instance, after observing x 1 , H is partitioned in two classes containing hypotheses which predict 0 in x 1 and those which predict 1 respectively. The set H 1 is obtained by choosing arbitrarily any two hypotheses from the two classes. As new inputs are observed each class may be further split (see Figure 3) and after n inputs the hypothesis space is partitioned into at most O(n d ) classes. Finally, H n is obtained by taking one hypothesis from each class. As a result, for any hypothesis in H there exists a corresponding hypothesis in H n which has exactly the same sequence of predictions on {x t } n t=1 and, thus, the very same performance.

N = |H n | ≤ en d d < ∞
Lemma 1. Let H n be the grid defined above, then

inf h∈H n t=1 t (h) = min h ∈Hn n t=1 t (h ), (5)
that is, the performance of the best hypothesis in H on {x t } n t=1 is exactly the same obtained by the best hypothesis in H n .

Proof. The statement follows by construction. In fact, by definition of H n , for any h ∈ H it is always possible to find a hypothesis h ∈ H n with exactly the same sequence of predictions on inputs {x t } n t=1 . According to the previous lemma, if the sequence of inputs is available before the learning to take place, then the regret defined in (1) (that compares the cumulative loss of the learner to the performance of the best hypothesis in the full set H) can be controlled by a EWF run on H n , thus obtaining exactly the same performance as in Theorem 1.

Lemma 2. Let the sequence of inputs x 1 , . . . , x n iid ∼ P be available before learning and let H n be the grid defined above, then

R n ≤ nd 2 log en d + n 2 log 1 β with probability 1 -β.
Proof. The lemma immediately follows from Lemma 1, Theorem 1, and N ≤ en d d from Sauer (1972)'s lemma.

It is interesting to notice that a similar result is derived in [START_REF] Kakade | From batch to transductive online learning[END_REF] for online transductive learning in which no assumption is made on the way inputs {x t } n t=1 are generated. Thus, the performance in the bound of Lemma 2 can be attained with both stochastic or adversarial inputs. As we show next this will be no longer the case when we move from the transductive (e.g., inputs known in advance) to the general setting (e.g., both inputs and labels are revealed online). Sequence of auxiliary inputs. In our case, the sequence of inputs {x t } n t=1 is not available beforehand, thus it is not possible to build H n before the actual learning process begins. Nonetheless, in the following we show that in case of stochastic inputs, the learner can take advantage of any sequence of inputs drawn from the same distribution P to build a grid H that can be used as input for a EWF . We will further show in Section 3.3 that we do not even need to know a sequence of auxiliary inputs beforehand and the mere assumption that inputs are drawn from a fixed (and unknown) distribution is sufficient to learn efficiently.

For now, let us assume an auxiliary sequence of n inputs {x t } n t=1 is available to the learner before the classification problem actually begins and let H n be the grid of H built on inputs {x t } n t=1 . The regret of EWF with experts in H n can be decomposed as

R n = n t=1 t (h t ) -inf h∈H n t=1 t (h) = n t=1 t (h t ) -min h ∈H n n t=1 t (h ) + min h ∈H n n t=1 t (h ) -inf h∈H n t=1 t (h) = R EW F + R H , (6)
where R EW F is the regret due to EWF and R H comes from the use of H n instead of the full hypothesis space H. While the first term can be bounded as in Theorem 1, the second term in general is strictly positive. In fact, since H n is different from the set H n that would be created according to the inputs {x t } n t=1 , equality (5) does not hold for H n . In particular, in the fully adversarial case, the sequence of inputs could be chosen so that hypotheses in H n have an arbitrarily bad performance when used to learn on {x t } n t=1 (e.g., if the learner is shown the same input for n steps, H n would contain only two hypotheses!). The situation is different in the stochastic-adversarial setting. In fact, since all the inputs are sampled from the same distribution P , H n is likely to contain hypotheses that are good to predict on any other sequence of inputs drawn from P . Therefore, under the assumption that n inputs can be sampled from P beforehand, we prove that the regret ( 6) is bounded by

O( √ nd log n ) with high probability. Let ∆ n (h, h ) = 1 n n t=1 I {h(x t ) = h (x t )} (7)
be the empirical disagreement between two hypotheses h, h ∈ H on a sequence of inputs {x t } n t=1 (and define similarly ∆ n (h, h ) as the empirical disagreement of h and h on inputs {x t } n t=1 ). The following result states the uniform concentration property of ∆ n around its expectation ∆.

Lemma 3. For any sequence of inputs x 1 , . . . , x n iid

∼ P sup (h,h )∈H 2 |∆ n (h, h ) -∆(h, h )| ≤ ε n = 2 2 2d log en d + log 4 β n ,
with probability 1β.

Proof. Let G = {g(x) = I {h(x) = h (x)} , h, h ∈ H}, with g ∈ {0, 1}.
As it can be noticed ∆ n (h, h ) and ∆(h, h ) are respectively the empirical average and expectation of g. Furthermore, it easy to show that

V C(G) = V C(H 2 ) ≤ 2V C(H) = 2d.
Using the VC-bound on space G (see e.g., [START_REF] Bousquet | Introduction to statistical learning theory[END_REF]) the statement follows.

Using the previous lemma, it is possible to bound the difference in performance between the best hypothesis in H n and the best in H, and bound the regret in (6).

Theorem 2. For any 0 < n ≤ n , let H n be a set of hypoheses built according to an auxiliary sequence of inputs x 1 , . . . , x n iid ∼ P . An EWF with experts in H n run on n new samples drawn from distribution P incurs a regret

R n ≤ c 1 nd 2 log en d + c 2 n 2 log 12 β (8)
with probability 1β, where

c 1 = 1 + 8 √ 2, c 2 = 9.
Proof. In (6) the regret is decomposed in two terms. By bounding the first term as in Theorem 1, we obtain

R n ≤ nd 2 log en d + n 2 log 1 β + min h ∈H n n t=1 t (h ) -inf h∈H n t=1 t (h) ,
with probability 1β , where the number of hypotheses in H n is bounded by |H n | ≤ (en /d) d . Since both (x 1 , . . . , x n ) and (x 1 , . . . , x n ) are drawn from the same distribution, the second term can be bounded as follows

R H = min h ∈H n n t=1 t (h ) -inf h∈H n t=1 t (h) = sup h∈H min h ∈H n n t=1 ( t (h ) -t (h)) (a) ≤ sup h∈H min h ∈H n n∆ n (h, h ) (b) ≤ sup h∈H min h ∈H n n∆(h, h ) + nε n w.p. 1 -β (c) ≤ sup h∈H min h ∈H n n∆ n (h, h ) + nε n + nε n w.p. 1 -2β (d) ≤ 0 + nε n + nε n (e) ≤ 4n
H 0 = ∅ with any h ∈ H for k = 0, 1, 2, . . . do Set t k = 2 k , t k+1 = 2 k+1 , N k = |H (k) |, and η k = 2 log N k /n k Initialize w t k i = 1, i ∈ {1, . . . , N } for t = t k to t k+1 -1 do Observe x t Sample h t ∼ p t , with p i = w t i /( N k j=1 w t j ) Predict y t = h t (

The Epoch-based Stochastic Adversarial (EStochAd) Forecaster

In the previous section we assumed a sequence of inputs (x 1 , . . . , x n ) could be sampled from P before starting the learning process. However, this assumption is often unrealistic when the distribution P is unknown and inputs are revealed only during the learning process. In this section we devise an epoch-based algorithm in which the hypothesis set is incrementally built in epochs according to the inputs experienced so far.

The algorithm works is epochs such that epoch k is n k = t k+1t k steps long, from time t = t k to t k+1 -1. At the beginning of epoch k, a grid H (k) is build on the basis of the sequence of inputs {x t } t k -1 t=1 and a EWF is run on H (k) until the end of epoch k. The resulting algorithm is summarized in Algorithm 1. As it can be noticed, EStochAd is an anytime algorithm since the time horizon n does not need to be known in advance. In fact, at epoch k the learning parameter η k is set as in the EWF according to the length n k of the epoch, independently from the value of n.

According to Theorem 2, whenever t k ≥ n k the regret of an EWF with experts in H (k) and parameter

η k = 2 log N k /n k in epoch k is R (k) = t k+1 -1 t=t k t (h t ) -inf h∈H t k+1 -1 t=t k t (h) ≤ c 1 n k d log et k d + c 2 n k 2 log 12 β (9)
with probability 1β.

The next theorem shows that if the length of each epoch is set properly, then the regret of the EStochAd algorithm is bounded by O √ nd log n with high probability.

Theorem 3. Let the length of the epochs be n k = 2 k , thus t k = 2 k . At the beginning of epoch k a hypothesis set H (k) is built according to all the inputs up to time t k -1 and the weight of each hypothesis is initialized to 1. Let H be a hypothesis space with finite VC-dimension d = V C(H) < ∞. For any n > 0, the EStochAd algorithm described above satisfies

R n ≤ c 3 nd log en d + c 4 n log 12( log 2 n + 1) α (10)
with probability 1α, where

c 3 = 18 + 17 √ 2 and c 4 = 9(2 + √ 2).
Proof. The theorem directly follows from Theorem 2 and from the definition of epochs. Given t k = n k = 2 k the regret for each epoch can be rewritten as

R (k) ≤ c 1 2 k d log e2 k d + c 2 2 k 2 log 12 β
Let K = log 2 n + 1 be the index of the epoch containing the step n and t K = min(2 K , n + 1). The total regret over all the K epochs can be bounded as follows

R n = n t=1 t (h) -inf h∈H n t=1 t (h) = K-1 k=0 t k+1 -1 t=t k t (h) -inf h∈H K-1 k=0 t k+1 -1 t=t k t (h) (a) ≤ K-1 k=0 t k+1 -1 t=t k t (h) -inf h∈H t k+1 -1 t=t k t (h) ≤ K-1 k=0 R (k) = log 2 n k=0 R (k) (b) ≤ c 1 d log en d + c 2 1 2 log 12 β log 2 n k=0 √ 2 k w.p. 1 -β( log 2 n + 1) ≤ c 1 d log en d + c 2 1 2 log 12 β √ 2n -1 √ 2 -1 (c) ≤ c 3 nd log en d + c 4 n log 12 β .
(a) the regret is upper-bounded by considering the best hypothesis in each epoch rather than on the whole horizon of n steps.

(b) The inner term in the summation is the regret for epoch k and is bounded as in ( 9). (c) Constants are obtained by setting

c 3 = c 1 (2 + √ 2) and c 4 = c 2 (2 + √ 2).
Finally, by using a union bound and setting α = β( log 2 n + 1) the result is obtained from the definition of the length of each epoch and some algebra.

We postpone a detailed analysis of this result and a comparison with other existing results to Section 6.

It is worth noting that, from an implementation point of view the set of hypotheses H (k) does not need to be regenerated from scratch at the beginning of each epoch k but it can be built incrementally as new inputs comes in. As a consequence, for each hypothesis h i already available at the previous epoch, its weight w i is initialized according to the cumulative loss up to end of the previous epoch. Similarly, new hypotheses can inherit the weight of hypotheses belonging to the same class before the refinement. Although no improvement in the bound can be proved, using the past performance to initialize the weight for new hypotheses is likely to have a positive impact in the actual performance.

h 3 x 1 h 1 h 2 h 4 x 2 h 5 h 8 h 7 h 6

Computational Complexity

Although the main focus of this paper is the introduction of the hybrid stochastic-adversarial setting and the analysis of its learnability, in this section we discuss the efficiency of the proposed algorithm. At each epoch k EStochAd is divided into two phases: a learning phase in which a EWF is run on N k experts and a phase in which the set of experts is updated accord-Algorithm 2 Algorithm to build a grid H (k+1) at the end of epoch k after observing t k -1 inputs (sketch).

Input: linear classifiers, {x t } t k -1 t=1 inputs, X = R d Initialize: H (k+1) = ∅ for all d-tuple {x i } d i=1 of inputs from {x t } t k -1 t=1 do Build the hyper-plane h passing through {x i } d i=1 for i = 1 to 2 d do
Transform h and generate the hyper-plane h Define the classifiers h 2i-1 and h 2i equal to h but with two different directions end for Add {h j } 2•2 d j=1 to H (k+1) end for ing to the inputs observed so far. By [START_REF] Sauer | On the densities of families of sets[END_REF]

's Lemma the number of experts N k is at most O(t d k )
where d is the VC-dimension of H. As a result, the computational complexity of the learning phase is polynomial in the time horizon n and exponential in d. In fact, at each round t the EWF updates the weights of each of the N k experts according to the loss they incur at time t. Thus the computational cost of each epoch

k is O(n k t d k )
where n k is the length of the epoch. By setting n k = t k = 2 k and K = log 2 n + 1, we obtain that learning phase has a total computation cost of order O(n d+1 ). The critical part now is to show whether it is possible to build the grid H (k) on the basis of the inputs {x t } t k-1 t=1 in an efficient way. The method to generate H (k) highly depends on the specific hypothesis space H at hand. In the following we propose a method for linear spaces with a polynomial complexity in the time horizon n.

Let the input space X = R d and t k the number of input points observed so far. Any tuple of d input points can be classified in at most 2 d ways. A set of linear classifiers generating all the possible combinations can be easily obtained by computing the hyper-plane passing through the d inputs first 3 and then transforming it through appropriate infinitesimal (i.e., without intersecting other inputs) translations and rotations in order to obtained all the 2 d possible classifications (see Figure 4 for an example in two dimensions). For each of the 2 d combinations we generate two classifiers, one for each of the two possible directions. This process should be repeated for any possible combination of d inputs among {x t } t k -1 t=1 . Let A be the cost of computing the hyper-plane and B the cost of each transformation on the hyper-plane, the total computational cost of the generation of

H (k+1) at the end of epoch k is cost(H k+1 ) = t k d A + 2 d 2B .
Using the bound on the binomial coefficient

t k d ≤ et k d d , t k = 2 k
, and taking the sum over the number of epochs, we obtain that the computational complexity of the update phase of the grid H (k) over epochs is of order O((A+ 2 d 2B)n d ). Although this method may generate redundant hypotheses (i.e., hypotheses having the same classification on points {x t } t k -1 t=1 ), its complexity is not worse than for the learning phase with the EWF, thus making the overall complexity of EStochAd with linear classifiers polynomial in n with exponent the VC-dimension d.

In the following lemma we prove that the procedure outlined in Algorithm 2 generates a grid H (k+1) containing hypotheses with the same predictions on inputs {x t } t k -1 t=1 as any hypothesis in H.

Lemma 4. For any h ∈ H there exist a hypothesis h i ∈ H (k+1) , where the grid H (k+1) is built according to Algorithm 2, such that the sequence of prediction of h and h i is the same on {x t } t k -1 t=1 .

Proof. The proof follows by construction of H (k+1) . Let h be any linear classifier in H (see Figure 5 for an example in 2-d). It is always possible to apply to h a transformation so that the resulting classifier h still has the same classification on the t k inputs and it passes through a subset of d points among {x t } t k -1 t=1 . Since Algorithm 2 enumerates all the possible hyperplanes passing through d points, h is used as a base classifier to generate the classifiers in H (k+1) . Thus, there always exists among the classifiers generated from h one having exactly the same classification as h.

Extensions

In this section, we discuss possible extensions of the proposed algorithm to different settings.

Multi-Label Classification

Although we analyzed the performance of EStochAd in the case of binary classification, the extension to the case of multi-label classification is straightforward. In order to measure the complexity of H we refer to the extension to multi-label classification of the VC-dimension proposed by [START_REF] Natarajan | On larning sets and functions[END_REF] 4 . The resulting algorithm is the same as in Algorithm 1 and still runs an EWF on a grid H (k) obtained by partitioning the space H into classes of hypotheses with the same sequence of predictions on past inputs.

Theorem 4. For any n > 0, let m > 0 be number of labels and H a hypothesis with finite Natarajan dimension d = N dim(H) < ∞. The EStochAd algorithm satisfies

R n ≤ c 5 nd log enm 2 2d + c 6 n log 3 log 2 n α , (11)
with probability 1α, with a universal constants c 5 and c 6 .

Proof. The proof follows the same steps as in Theorem 3. The main difference is that the number of hypotheses in H n is now bounded by [START_REF] Ben-David | Characterizations of learnability for classes of {0...n}-valued functions[END_REF] and that in Lemma 3 the N dim(H) is used instead of the VC-dimension.

|H n | ≤ ( enm 2 2d ) d (Ben-

Bandit Information

In the protocol in Figure 2 at the end of each episode the true label chosen by the adversary is explicitly revealed to the learner, thus defining a full information classification problem. However, in many applications (e.g., web advertisement systems) only the loss corresponding to the chosen hypothesis (bandit feedback) is available to the learner.

The EStochAd algorithm can be extended to solve the hybrid stochasticadversarial classification problem with bandit information simply by substituting the EWF with a bandit algorithm such as Exp4 [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], thus defining the so-called Bandit-EStochAd algorithm (Algorithm 3). Let us consider the more general case illustrated in Figure 1 in which instead of selecting a label, at each round t the adversary chooses a bounded loss function t : Y → [0, 1]. In the prediction phase, the original EStochAd Algorithm 3 The Bandit-EStochAd forecaster Input: hypothesis set H Initialize:

H 0 = ∅ with any h ∈ H for k = 0, 1, 2, . . . do Set t k = 2 k , t k+1 = 2 k+1 , N k = |H (k) |, and η k = 2 log N k /n k Initialize w t k i = 1, i ∈ {1, . . . , N } for t = t k to t k+1 -1 do Observe x t Sample h t ∼ p t , with p i = w t i /( N k j=1 w t j ) Sample y t ∼ q t ,
where

q t j = (1 -γ)I {j = h t (x t )} + γ m , j ∈ {1, . . . , m} Receive loss ( y t ) Define ˆ t (h i ) = ( yt) q t y t I {h i (x t ) = y t } , i ∈ {1, . . . , N k } Update weights w t+1 i = w t i exp -η k ˆ t (h i ) end for
Build H k+1 according to inputs {x 1 , . . . , x t k+1 -1 } end for algorithm is used to select a hypothesis h i in the grid H (k) built so far. According to Exp4 an additional randomization over all the possible m labels is introduced and a prediction y t is returned. At the end of each round t, the learner incurs a loss t (h t (x t )) (the only information available) for which an unbiased estimate of the loss ˆ t (h) for any hypothesis h is built. Finally, the weights of the hypotheses in H t are updated according to EStochAd. We can prove the following regret bound for Bandit-EStochAd.

Theorem 5. Let m > 0 be the number of arms (i.e., labels), H be a hypothesis set with finite Natarajan dimension d = N dim(H) < ∞, and be bounded in [0, 1]. For any n > 0, the Bandit-EStochAd algorithm satisfies

R n ≤ O nmd log nm 2 α + d log nm 2 α , (12)
with probability 1α.

Proof. In Theorem 2 the first part of the regret of EStochAd can be immediately derived from the bandit algorithm working on the set H n . For instance, for Exp4 with N experts and m labels it is possible to prove the high-probability regret bound

R n (Exp4) ≤ 4 nm log nN β + 8 log nN β ,
with probability 1β. As discussed in the previous section, in case of m labels the number of experts at time n is bounded by

N = |H n | ≤ ( enm 2 2d ) d .
Besides, the second term in ( 6) is not affected by the different feedback in full and bandit settings and remains unchanged. The only difference is in step (a) of Theorem 2. Indeed, when two hypotheses have the same prediction their loss is the same. On the other hand, if the predictions are different, the difference between the losses cannot be greater than 1. Thus,

t (h) -t (h ) ≤ I {h(x t ) = h (x t )}.
As a result, the leading term in the cumulative regret is due to Exp4 and the statement follows.

Regression

So far we considered classification problems in which H is a discretevalued space of functions, we now show that for some loss functions that analysis can be easily extended to the regression setting. We first recall the definition of pseudo-dimension of a space of real-valued functions.

Definition 1. Let F be a space of bounded real-valued functions f : X → [0, B] and {x t } n t=1 be a set of points in X . We say that the points {x t } n t=1 are pseudo-shattered by F if there are

{y t } n t=1 ∈ [0, B] n such that for any b ∈ {0, 1} n , there is a f b ∈ F such that f b (x t ) ≥ y t ⇔ b t = 1, 1 ≤ t ≤ n. ( 13
)
The largest n such that there exists a set {x t } n t=1 pseudo-shattered by F is the pseudo-dimension of F, denoted by V + F . We also need the definition of ( , 1)-covering number of F. Definition 2. Let F be a space of bounded real-valued functions f :

X → [0, B]. Every finite collection of functions f 1 , . . . , f N ∈ F is a ( , 1)-cover of F if for any f ∈ F there exist a f i (1 ≤ i ≤ N ) such that ||f -f i || 1 ≤ . ( 14
)
The ( , 1)-covering number of F is the smallest N such that f 1 , . . . , f N is a ( , 1)-cover of F, and we denote it by N 1 ( , F). Similar, let {x t } n t=1 be a set of points in X , a collection of functions

f 1 , . . . , f N ∈ F is an empirical ( , 1)-cover of F on {x t } n t=1 if for any f ∈ F there exist a f i (1 ≤ i ≤ N ) such that 1 n n t=1 |f (x t ) -f i (x t )| ≤ . ( 15
)
The ( , 1)-covering number of F is the smallest N such that f 1 , . . . , f N is an empirical ( , 1)-cover of F on {x t } n t=1 , and we denote it by N 1 ( , F, {x t } n t=1 ). Finally, we recall Pollard's inequality [START_REF] Pollard | Convergence of Stochastic Processes[END_REF].

Lemma 5. Let F a set of functions f : X → [0, B], and x 1 , . . . , x n be a sequence of i.i.d. samples from a distribution P . For any n > 0, > 0 then

P sup f ∈F 1 n n t=1 f (x t ) -E[f (x 1 )] ≥ ≤ 8E N 1 8 , F, x n 1 exp - n 2 128B 2 .
Equivalently, let V = V + F be the pseudo-dimension of F, then with probability

1 -β for all f ∈ F 1 n n t=1 f (x t ) -E[f (x 1 )] ≤ = 8B 2 Λ(n, V, β) n , ( 16
)
where Λ(n, V, β) = V log n + log e β + log 24( 9 2 e 2 ) V . Proof. We just report the proof of the second statement. It is sufficient to show that

8E N 1 8 , F, x n 1 exp - n 2 128B 2 ≤ β (17)
for the in ( 16). We first notice that Λ(n, V, β) > 1 and > 8B 2 n . Using the bound for covering numbers in [START_REF] Haussler | Decision theoretic generalizations of the pac model for neural net and other learning applications[END_REF], the definition of Λ(n, V, β), a = 24eB, b = (128B 2 ) -1 , and some algebra we obtain

8E N 1 8 , F, x n 1 exp - n 2 128B 2 ≤ 24 a 2 2 V exp(-bn 2 ) = 24(a 2 bn) V exp(Λ(n, V, β)) = 24(a 2 b) V n V n -V β e 1 24(a 2 b) V ≤ β.
We are now ready to define the extension of EStochAd to regression. We consider the general full information setting in which at round t the adversary chooses a bounded loss function t : Y → [0, M ], with Y = [0, B], and the learner chooses a function f t ∈ F. At the end of the round the learner incurs a loss t (f t (x t ) depending on the input x t drawn from a distribution P . Finally, the loss function t (•) is revealed to the learner. Similar to the classification case, the objective of the learner is to minimize the regret

R n = n t=1 t (f t (x t )) -inf f ∈F n t=1 t (f (x t )).
The structure of the algorithm is mostly the same as in Algorithm 1. Instead of a discrete-valued set of hypotheses H, we consider the space F of realvalued functions bounded in [0, B]. At the end of each epoch the grid of hypotheses H (k) is substituted by an ( , 1)-cover of F on inputs {x 1 , . . . , x t k -1 }, denoted by F (k) . It is possible to prove that this algorithm achieves the same performance as EStochAd in classification under suitable assumptions on the loss function making it possible to define a relationship between the space of loss functions and F. In particular, we prove the following. Theorem 6. Let F be a space of bounded real-valued functions f :

X → [0, B] with finite pseudo dimension V = V + F < ∞.
At each round t the adversary chooses a loss function t which is Lipschitz with constant L. The EStochAd algorithm for regression described above satisfies

R n ≤ c 7 LB   nV log n + n log 12e( log 2 n + 1) α + n log 24 9 2 e 2 V   (18)
with probability 1α, where c 7 = 49( √ 2 -1).

Proof. First we need to derive the equivalent of Theorem 2 in case of regression to bound the regret at each epoch. The regret R (k) can be decomposed as

R (k) = t k+1 -1 t=t k t (f t ) -inf f ∈F t k+1 -1 t=t k t (f ) = t k+1 -1 t=t k t (f ) -min f ∈F (k) t k+1 -1 t=t k t (f ) + min f ∈F (k) t k+1 -1 t=t k t (f ) -inf f ∈F t k+1 -1 t=t k t (f ) = R (k) EW F + R (k) F
where F (k) is an ( , 1)-cover of F on inputs {x 1 , . . . , x t k -1 }. The first component of the regret can still be bounded using the bound of the EWF.

Since [START_REF] Haussler | Decision theoretic generalizations of the pac model for neural net and other learning applications[END_REF], the following bound on the covering number holds

F (k) is an ( , 1)-cover of F, it contains N k = N 1 , F, x t k -1 1 experts. By
N 1 , F, x t k -1 1 ≤ 3 2eB log 3eB V ≤ 3 3eB 2V . Let = 8B 2Λ(t k ,V,β) t k
, as in Lemma 5 we notice that ≥ 8B 2 t k , thus the number of experts can be bounded as

N k ≤ 3 9e 2 128 t k V .
Thus, we can bound the first term R

(k)
EW F in the regret R (k) by the performance of the EWF on N k experts

R (k) ≤ LB 2 k 2 log N k + 2 k 2 log 1 β + R (k) F ,
where the multiplicative term LB is the bound over the loss function. In order to bound the second term we follow similar steps as in Theorem 2.

R (k) F = min f ∈F (k) t k+1 -1 t=t k t (f ) -inf f ∈F t k+1 -1 t=t k t (f ) = sup f ∈F min f ∈F (k) t k+1 -1 t=t k ( t (f ) -t (f )) (a) ≤ sup f ∈F min f ∈F (k) t k+1 -1 t=t k L (f (x t ) -f (x t )) (b) ≤ sup f ∈F min f ∈F (k) 2 k LE x∼P [f (x) -f (x)] + 2 k L w.p. 1 -β (c) ≤ L sup f ∈F min f ∈F (k) 2 k L t k -1 t=1 (f (x t ) -f (x t )) + 2L • 2 k w.p. 1 -2β (d) ≤ 3L • 2 k = 24LB 2 Λ(2 k , V, β) 2 k .
(a) By assumption that the loss is Lipschitz.

(b)-(c) We apply two times Lemma 5.

(d) The grid F (k) is obtained by building an -cover of F on the samples {x t } t k -1 t=1 . Thus, by definition 2 the closest function f ∈ F (k) to any function f ∈ F is not further than .

By joining the bound for R

EW F and R

F and some simplification, we obtain

R (k) ≤ 49 2 LB √ 2   2 k V log 2 k + 2 k log e β + 2 k log 24 9 2 e 2 V   .
Finally, we follow the same steps as in Theorem 3 and we obtain the final statement.

It is interesting to notice that the class of Lipschitz losses includes commonly used loss functions such as L 1 and squared loss. Let y t ∈ [0, B] be the output at time t, the L 1 loss is defined as t (y) = |yy t |. It is immediate to

1: for t = 1, 2, . . . do 2: Simultaneously, -A stochastic input x t is sampled i.i.d. from P -Player A selects strategy h A,t -Player B selects strategy h B,t 3: Player A (resp., B) plays action y A,t = h A,t (x t ) (resp., y B,t = h B,t (x t )) 4: Return feedback -A ( y A,t , y B,t , x t ) and B ( y A,t , y B,t , x t ) (bandit information) -or A (•, y B,t , x t ) and B ( y A,t , •, x t ) (full information) 5:
Player A (resp., B) incurs a loss A ( y A,t , y B,t , x t ) (resp., B ( y A,t , y B,t , x t )) 6: end for verify that this loss is a Lipschitz function with L = 1 and M = B. In case of a squared loss t (y) = (yy t ) 2 we have

| t (y 1 ) -t (y 2 )| = |(y 1 -y t ) 2 -(y 2 -y t ) 2 | = |y 2 1 -y 2 2 -2y t (y 1 -y 2 )| = |(y 1 -y 2 )(y 1 + y 2 -2y t )| ≤ 2B|y 1 -y 2 |.
Thus the squared loss is a Lipschitz functions with M = B 2 and L = 2B.

Application in Games

In this section we consider an extension of the stochastic-adversarial prediction problem to a two-player strategic repeated game with stochastic side information. Like in the general problem illustrated in Figure 1, the game could be either full or bandit information, depending on whether at the end of each round the learners receive the loss function A (•, y B,t , x t ) (resp. B ( y A,t , •, x t )) or only the loss they incurred. Our main contribution here is to show that in the case of a zero-sum game, if both players play according to the (Bandit-)EStochAd algorithm, then the empirical frequencies of the strategies converge to the set of Nash equilibria.

Theorem 7. Let losses A , B be bounded in [0, 1], H be a compact metric set. If both players run (Bandit-)EStochAd in a zero-sum game with stochastic side information as defined above, then

lim n→∞ 1 n n t=1 A (h A,t (x t ), h B,t (x t ), x t ) = V (20)
almost surely.

Proof. The proof is similar to the convergence proof for Hannan consistent strategies in zero-sum games [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. We first prove the following

lim n→∞ 1 n n t=1 A,t (h A,t ) ≤ V. (21)
We note that the regret for both players can be bounded exactly as in ( 12). In fact, losses A and B are a special case of the adversarial loss function considered in Section 5.2. As a result, we have

lim sup n→∞ 1 n n t=1 A,t (h A,t ) -inf h A ∈H 1 n n t=1 A,t (h A ) ≤ 0, (22)
with probability 1α, where A,t (h

A ) = A (h A , h B,t , x t ). Let g A (h B,t ) = A,t (h A ) -A (h A , h B,t )
. By definition of the expected loss and by noticing that the hypothesis h B,t selected by the algorithm at time t does not depend on the input x t , we have that g A (h B,t ) for any h A ∈ H

E xt∼P [g A (h B,t )|F t-1 ] = 0,
where F t-1 is the σ-algebra generated by all random variables up to time t -1 (i.e., past inputs and hypotheses for both players A and B). Thus,

g A (h B,1 ), • • • , g A (h B,n
) is a martingale difference sequence and we can apply Lemma 8. Thus we obtain that with probability 1β for any function g A induced by h A ∈ H, the empirical average 1 n n t=1 g A (h B,t ) asymptotically concentrates around 0. As a result, we have

lim sup n→∞ inf h A ∈H 1 n n t=1 A,t (h A ) -inf h A ∈H 1 n n t=1 A (h A , h B,t ) ≤ 0. ( 23
)
Now, since the mapping σ A → A (σ A , h B,t ) is linear, this function admits a pure strategy as minimum, and we have inf

h A ∈H 1 n n t=1 A (h A , h B,t )= inf σ A ∈D(H) 1 n n t=1 A (σ A , h B,t ) = inf σ A ∈D(H) A (σ A , σ n B )
where

σ n B (h) ∈ D(H) is defined for any h ∈ H as σ n B (h) = 1/n n t=1 I {h B,t = h}. Finally, we have inf σ A ∈D(H) A (σ A , σ n B ) ≤ sup σ B ∈D(H) inf σ A ∈D(H) A (σ A , σ B ), (24)
Putting together ( 22), ( 23), and (24) we obtain ( 21). The same result can be obtained for B . From the assumption A (•,

•) = -B (•, •), minimax the- orem (19)
, and since this result holds for any α, then we have (20) with probability 1.

From the previous theorem and the compactness property of D(H) it also follows that the empirical frequencies of the mixed strategies σ n A and σ n B converge to the set of Nash strategies. Finally, it is interesting to notice that in the case of multi-label classification (in which the loss function t (h) = I {h(x t ) = y t }), the convergence rate (i.e., the regret per round) to the set of Nash equilibria is of the order O( d/n log (nm 2 )) in the full information case, and O( (md)/n log (nm 2 )) in the bandit information case.

Related Works

To the best of our knowledge this is the first work considering the online learning problem with stochastic inputs and adversarial labels. A similar setting is analyzed by [START_REF] Ryabko | Pattern recognition for conditionally independent data[END_REF] for batch supervised learning where the sequence of labels is adversarial and inputs are conditionally independent and identically distributed (i.e., inputs are drawn from distributions conditioned to labels). In particular, they show that in such a scenario many learning bounds (derived in the pure stochastic setting) remain unchanged. The main difference with the setting illustrated in this paper is that we considered the problem of online learning instead of batch learning and inputs are i.i.d. and not conditioned to labels.

T V C(H) < ∞ Mistake Mn ≤ L + n 3/4 V C(H) log n Selective Sam- pling (Cesa- Bianchi et al., 2009) A/S Linear Exp- Regret E [Rn] ≤ n + O 1 2/κ + d 2 log n EStochAd [This paper ] S/A V C(H) < ∞ HP- Regret Rn ≤ nV C(H) log n + n log β -1
Table 1: Performance of algorithms for different classification scenarios. All the bounds are reported up to constant factors. In the setting column, the two letters specify how inputs and labels are generated, where A stands for adversarial, S for stochastic, and T for transductive. In the bound column HP stands for high-probability bound and Exp stands for bound in expectation. In the perceptron bound M n is the number of mistakes after n steps, L and D are the cumulative loss and the complexity of any weight matrix.

In selective sampling 0 ≤ κ ≤ 1 is a parameter of the algorithm, n is the number of steps with a margin less than , and the bound holds for any for any 0 < < 1. [START_REF] Cesa-Bianchi | Robust bounds for classification via selective sampling[END_REF] analyze a learning setting which is complementary to the hybrid setting introduced in this paper. They consider the selective sampling problem in which inputs are arbitrarily generated by an adversary while labels a noisy observations of a linear hypothesis. The main concern in this setting is to limit the number of queries, that is the number of times the algorithm asks for the true label corresponding to an input. In particular, they analyze a semi-supervised variant of regularized least squares which approaches the performance of a Bayes optimal classifier with a number of queries sublinear in the time horizon.

Cesa

From an algorithmic point of view, the use of previous inputs to update the set of hypotheses at the beginning of each epoch resembles the use of unsupervised samples in semi-supervised learning. Similar to the analysis in [START_REF] Kaariainen | Generalization error bounds using unlabeled data[END_REF], we decomposed the regret in a learning performance term, which depends on the actual sequence of labels, and in the approximation of the structure of the inputs marginal distribution term, which just depends on unlabeled instances.

The possibility to convert batch algorithms for the fully stochastic into learning algorithm for the transductive online learning scenario is studied in [START_REF] Kakade | From batch to transductive online learning[END_REF]. In transductive online learning the samples are adversarially generated and all the inputs are known to the learner beforehand. In this scenario, they prove that a batch algorithm can be efficiently translated into an online algorithm with a mistake bound of the order n 3/4 √ d log n with d the VC-dimension of the hypothesis set. The transductive setting is very similar to the preliminary scenario we described in Section 3.2 in which we assume the sequence of inputs to be known in advance to the learner. In the rest of the paper we showed that in order to move from a transductive setting to a fully online problem and preserve similar results we need to assume the inputs to be drawn independently from some fixed distribution even if this distribution is not known. [START_REF] Abernethy | A stochastic view of optimal regret through minimax duality[END_REF] compare adversarial on-line learning and statistical learning in online convex optimization. In particular, their analysis reveals that the optimal regret in online convex optimization can be written as the difference between a sum of minimal expected losses and the minimal empirical loss, where samples are generated by an adversarially chosen stochastic process. As a result, it is possible to derive upper and lower bounds for the optimal regret which exhibit several similarities to results for the fully stochastic setting. For instance, they derive an upper bound on the optimal regret in terms of the Rademacher averages of the space of loss functions induced by the space of functions F used by the learner.

A direct comparison of the performance of EStochAd with other algorithms for either fully adversarial or fully stochastic settings is difficult because of the different assumptions. Nonetheless, in the following we discuss similarities and differences between EStochAd and other existing algorithms for online prediction. In Table 6, we summarize the main approaches to the classification problem in both stochastic and adversarial settings. Unfortunately not all the bounds are immediately comparable. Some of the regret bounds are in expectation (with respect to either the distribution P or the randomized algorithm A), while others are high-probability bounds. Perceptron performance is stated in terms of mistake bound.

It is interesting to notice that EStochAd incurs exactly the same regret rate as an empirical risk minimization algorithm run online in the fully stochastic case (see Lemma 6). This means that under the assumption that inputs are i.i.d. from a fixed distribution P , the adversarial output does not cause any worsening in the performance with respect to a stochastic output. This result can be explained by the definition of the VC-dimension itself. In fact, while the definition of the VC-dimension requires samples to be generated from a distribution, no assumption is made on the way outputs are generated and any possible sequences of labels is considered. Therefore, it is not surprising that the VC-dimension can be used as a complexity measure for both the case of stochastic and adversarial classification. However, the situation is significantly different in the case of a fully adversarial setting where also inputs can be arbitrarily chosen by an adversary.

Both EStochAd and the Agnostic Online Learning (AOL) algorithm proposed by [START_REF] Ben-David | Agnostic online learning[END_REF] consider the problem of binary classification with adversarial outputs, an infinite number of hypotheses (experts), and they both build on the exponentially weighted forecaster [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. On the other hand, the main difference is that while with adversarial inputs it is necessary to consider the Littlestone dimension of H [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF], the stochastic assumption on the inputs allows ES-tochAd to refer to the VC-dimension which is a more natural measure of complexity of the hypothesis space. Moreover, the dependency of the two algorithms on the hypothesis space complexity is different (see Table 6). While AOL has a linear dependency on Ldim(H), in EStochAd the regret grows as V C(H). Furthermore, as proved by [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF], for any hypothesis space H, V C(H) ≤ Ldim(H). In the following we discuss an example showing how in some cases the difference between VC and Littlestone dimension

h x 4 0 x 2 x 3 x 1 1 x 4
Figure 7: Example of a sequence of inputs and labels such that the adversary can force any learning algorithm to incur a mistake at each round. Circles represent the labels predicted by the learner and crosses the labels revealed by the adversary. h x4 (in dotted-line) is an example of a hypothesis which perfectly classifies all the samples shown so far.

v 1 = 1/2 y 1 =1 y 1 =0 v 2 = 1/4 y 2 =1 y 1 =0 v 3 = 3/4 y 2 =1 y 1 =0 v 4 = 1/8 v 5 = 3/8 v 6 = 5/8 v 7 = 7/8
Figure 8: The mistake-tree is defined for any possible sequence of predictions. Double lines correspond to the example depicted in Figure 7.

may be arbitrarily large. Let consider a binary classification problem with X = [0, 1] and a hypothesis space H containing functions of the form

h ϑ (x) = 1 if x ≥ ϑ 0 otherwise, with ϑ ∈ [0, 1].
In the fully adversarial case the regret of AOL is linear in the time horizon (i.e., in the worst case it can make a mistake at each time step). In fact, it can be shown that the Littlestone dimension of H is infinite. According to [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF], the Littlestone dimension is the largest number of mistakes any learning algorithm could incur for any possible sequence of predictions in the realizable case when the adversary is allowed to choose the true label after observing the learner's prediction. Thus, the adversary selects inputs x t and labels y t so as to force the learner to make as many mistakes as possible given the condition that there exists a hypothesis h * in H such that h * (x t ) = y t , ∀t ≤ n. In order to determine the Littlestone dimension of H we sketch how to build a shattered mistake-tree of depth n, for any n > 0 (see Figure 8). Nodes of the mistake-tree represent the inputs revealed by the adversary depending on the sequence of learner's predictions. Let v 1 = 1 2 be the root of the mistake-tree, that is the first input x 1 revealed to the algorithm. Next, we label nodes v 2 and v 3 as the middle points of intervals [0, v 1 ] and [v 1 , 1] respectively. The second input shown to the learner depends on the prediction at time t = 1. If the prediction is y 1 = 15 , then the adversary selects a label y 1 = 0 and the next input point is set to x 2 = v 2 . If the algorithm predicts y 2 = 0 in x 2 , it is still possible to force the algorithm to incur a mistake by setting y 2 = 1 without violating the realizability condition. In fact, any hypothesis with x 2 ≤ ϑ < x 1 perfectly classifies both y 1 and y 2 . The next input x 3 is the middle point of interval [x 2 , x 1 ] and the algorithm is forced to make another mistake. The same process can be repeated at each round by choosing the next input to be the middle point of either the left or the right interval depending on the previous prediction and by revealing a label which is exactly the opposite of the one predicted by the learner. At each step the adversary can force the learner to make a mistake while guaranteeing that it is always possible to find a hypothesis in H that would make no mistakes (see Figure 7 for the sequence of inputs x 1 , x 2 , x 3 , x 4 ). As a result, Ldim(H) = ∞ and the AOL has a linear regret. On the other hand, when inputs cannot be arbitrarily chosen by an adversary but are sampled from a fixed distribution EStochAd can achieve a sub-linear regret. In fact, H could shatter at most one points, the VC-dimension of H is 1, thus leading a regret for EStochAd of order O( √ n log n). Therefore, even in very simple problems the possibility for the adversary to select the inputs may lead to an arbitrarily bad performance, while drawing inputs from a distribution allows the learner to achieve a sub-linear regret even if outputs are adversarial.

Conclusions

In this paper we introduced the hybrid stochastic-adversarial online prediction problem in which inputs are independently and identically generated and labels are arbitrarily chosen by an adversary. We devised an epochbased algorithm for the specific problem of binary classification with full information and analyzed its regret. In particular, we noticed that while the stochastic assumption on inputs allows to use the well-known VC-dimension as a measure of complexity for the hypothesis space, adversarial labels do not cause any worsening in the performance with respect to fully stochastic algorithms. We believe that this analysis, together with its relationship with the results for the fully adversarial case, sheds light on the similarities and differences between batch stochastic learning and adversarial online learning along the line of [START_REF] Kakade | From batch to transductive online learning[END_REF]. Finally, we discussed extensions to multi-label classification, regression, learning from experts and bandits settings with stochastic side information, and approximation of Nash equilibria in games.

In the following we summarize some of the open questions that we plan to investigate in the future.

• VC-learnability. The main result of this paper is that any learning setting in which inputs are stochastic is learnable using finite VCdimension hypothesis spaces independently from the way labels are generated. As noticed in [START_REF] Kakade | From batch to transductive online learning[END_REF] and [START_REF] Abernethy | A stochastic view of optimal regret through minimax duality[END_REF], strong connections between adversarial online learning and statistical learning can be drawn also in other settings, such as online convex optimization and online transductive learning. On the other hand, the analysis in [START_REF] Ben-David | Agnostic online learning[END_REF] clearly shows that in the fully adversarial case, the class of learnable problems is smaller than the set of finite VC-dimension spaces. What is the most general online learning setting with the same learnability as fully stochastic problems it is still an open question.

• Smoothed analysis. Given an algorithm A, the adversarial online learning setting is a worst-case analysis of the regret over both inputs and labels, while in the hybrid setting introduced in this paper the performance is evaluated according to a worst-case analysis for the labels and average-case for the inputs6 . Smoothed analysis [START_REF] Spielman | Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time[END_REF]) is an alternative to the standard worst-case and averagecase analyses in which the smoothed complexity of an algorithm is the maximum over its inputs of the expected performance under slight perturbations of that input. We plan to investigate the use of smoothedanalysis tools to derive a bound explaining both the hybrid and adversarial settings as extremes conditions on the perturbations on the inputs.

• Efficient algorithm. The analysis in Section 4 shows that, although polynomial in the time horizon, EStochAd has an exponential complexity w.r.t. the VC-dimension d. This dependency makes the algorithm inefficient both in terms of time and space complexity when the hypothesis space H has a high VC-dimension. Whether it is possible to obtain an efficient algorithm with the same regret is still an open question. We conjecture that a more numerically efficient algorithm may come at the cost of a worsening of the regret as in the transductive setting in [START_REF] Kakade | From batch to transductive online learning[END_REF].

Appendix A. Online Empirical Risk Minimizer

We report the lemma stating the regret of an empirical risk minimizer run online in the fully stochastic setting. (h(x s ), y s ).

Let h * be the expected loss minimizer, that is h * = arg inf h∈H ¯ (h). We prove the following sequence of inequalities.

E [R n ] = n t=1 ¯ (h t ) -¯ (h * ) (a) ≤ n t=1 ¯ (h t ) -ˆ t-1 (h t ) + ˆ t-1 (h * ) -¯ (h * ) (b) ≤ n t=1 2 sup h∈H ¯ (h) -ˆ t-1 (h) (c

  a loss function t : Y → [0, 1] -Learner chooses a hypothesis h t ∈ H 4:

Figure 1 :

 1 Figure 1: The protocol of the general stochastic-adversarial setting.

Figure 2 :

 2 Figure 2: The protocol of the fully information binary stochastic-adversarial classification problem.

Figure 4 :Figure 5 :

 45 Figure 4: In a two-dimensional binary classification problem, each pair of input points can be classified in four different ways using linear classifiers. The arrow indicates the half-space which is positively labeled.

Figure 6 :

 6 Figure 6: The two-player strategic repeated game with stochastic side information.

Lemma 6 .

 6 Let {x t , y t } n t=1 iid ∼ P be a sequence of i.i.d. input-label pairs drawn from a distribution P and H be a hypothesis space with finite VC-dimension d = V C(H) < ∞. At each round t the learner returns the hypothesis minimizing the cumulative lossh t = arg min h∈H t-1 s=1 (h s (x s ), y s ),For any n > 0, the learner achieves a regretE [R n ] = E (x,y)∼P [ (h(x), y)] ; ˆ t (h) = 1 t t s=1

  The minimum disagreement ∆ n (h, h ) is zero for any hypothesis h ∈ H. In fact, since H n is built according to the same inputs (x 1 , . . . , x n ) on which ∆

	2	2d log en d + log 4 β n
	(f) ≤ 4 4nd log	en d	+ 4 2n log	4 β	,
	(a) Two hypotheses have a different loss whenever their prediction is differ-
	ent, thus we use the definition of the empirical disagreement in (7).
	(b)-(c) We apply two times Lemma 3.
	(d)

n (h, h ) is measured, it is always possible to find a hypothesis h ∈ H n Algorithm 1 The Epoch-based Stochastic Adversarial (EStochAd) forecaster Input: hypothesis set H Initialize:

  x t ) Observe the true label y t Update weights w t+1 Build H k+1 according to inputs {x 1 , . . . , x t k+1 -1 } end for with exactly the same sequence of predictions as any h ∈ H. (e) By assumption n ≥ n and from the definition of ε n and ε n in Lemma 3.By joining the bound for R EW F and R H , and by setting β = 3β we obtain

	(f ) We apply for the EWF.	√	a + b ≤	√ a +	√	b to make the bound similar to the bound
	R n ≤	nd 2	log	en d	+	n 2	log	1 β	+ 4 8	nd 2	log	en d	+ 4 4	n 2	log	4 β
	and the final statement follows by setting c 1 = 1 + 8	√	2 and c 2 = 9.

j = w t j exp (-η k t (h j )) , j ∈ {1, . . . , N k } end for

  )

	≤ 2 √ (d) ≤ 2 √ 2 2 nd log n t=1	d t -1 2en d + 2 log √ 2e(t -1) d 2 n log	+ 2 β	.	1 t -1	log	2 β	w.p.1 -nβ

In particular, in the case of the perceptron the loss L is measured as the cumulative hinge loss of a vector u, and the complexity D depends on the

norm of u.

In the general case of a non-oblivious adversary, y t may depend on past inputs {x s } s<t , predictions { y s } s<t , and current input x t .

All the methods to compute the hyper-plane in R d passing through d points have a polynomial complexity in d.

For more details about complexity measures for m-values functions, we refer to[START_REF] Ben-David | Characterizations of learnability for classes of {0...n}-valued functions[END_REF].

The case y 1 = 0 is symmetric.

More precisely we provide a high-probability analysis.

Acknowledgments. This work has been supported by French National Research Agency (ANR) through COSINUS program (project EXPLO-RA nANR-08-COSI-004).

For sake of simplicity we consider the same set of strategies for both players. Let A and B be two players and H be the set of strategies h mapping an input x ∈ X to an action in Y = {1, . . . , m}. The repeated game between player A and B is sketched in Figure 6. At each round t, an input x t is drawn from P and, simultaneously, the players select strategies h A,t ∈ H and h B,t ∈ H. As a result, they incur losses A (h A,t (x t ), h B,t (x t ), x t ) and B (h A,t (x t ), h B,t (x t ), x t ) respectively ( A,t (h A,t ) and B,t (h B,t ) for short in the following). We define the expected loss for player A with respect to the input distribution P as

Let D(H) be the set of distributions on the set of pure strategies H. Given mixed strategies σ A and σ B in D(H) we define its corresponding expected loss (similarly for player B):

We say that a pair of strategies (σ

). Now we consider the problem of approximating a Nash equilibrium in the zero-sum case (i.e., A (•, •) = -B (•, •)). In order to define the value of the game and apply the minimax theorem we need D(H) to be compact [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. In the following, we assume that H is a compact metric space, which is a sufficient condition for D(H) to be compact (see e.g., [START_REF] Stoltz | Learning correlated equilibria in games with compact sets of strategies[END_REF]). Under this assumption, the minimax theorem (e.g., [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] holds

where V is the value of the game. The following theorem proves that if both players run either EStochAd or Bandit-EStochAd (in full information and bandit information respectively), then their performance converges to the value of the game and the empirical frequencies of their strategies converge to the set of Nash equilibria.

(a) By definition of h t it is the hypothesis minimizing the empirical loss, thus

(b) We take the supremum over all the hypotheses in H.

(c) An application of a VC-bound [START_REF] Bousquet | Introduction to statistical learning theory[END_REF].

(d) Result of the sum over n rounds.

The statement follows by setting β = nβ .

Appendix B. Functional Azuma's Inequality

In this section we prove an extension of the Azuma's inequality to a hypothesis space H. First we recall the definition of martingale difference sequence and the Hoeffding-Azuma's inequality. Definition 3. A sequence of random variables z 1 , z 2 , . . . is a martingale difference sequence with respect to a sequence of random variables

x t ] = 0, with probability 1 for any t > 0.

Proposition 1. Let z 1 , z 2 , . . . be a martingale difference sequence with respect to a sequence x 1 , x 2 , . . .. Assume furthermore that there exists a sequence of nonnegative constants c 1 , c 2 , . . . such that |z t | ≤ c t for any t > 0. Then for any > 0 and n

Now we extend the previous theorem to the functional case on a space of binary functions.

Lemma 7. Let H be a space of functions h : X → {0, 1} with finite VCdimension V C(H) = d < ∞. Assume that h(x 1 ), . . . , h(x n ) is a martingale difference sequence with respect to x 1 , . . . , x n for any h ∈ H. Then for any > 0 and n

Proof. The proof is a straightforward application of a union bound on the Azuma's inequality in Proposition 1. Let H x 1 ,...,xn be the space of vectors obtained by evaluating all the functions h ∈ H on points x 1 , . . . , x n . By definition of VC-dimension of H the cardinality of H x 1 ,...,xn is bounded by en d d [START_REF] Sauer | On the densities of families of sets[END_REF]. Thus, we obtain

where in the last step we used the Azuma's inequality in Proposition 1.

Lemma 8. Let F be a space of functions f :

x n be a sequence of i.i.d. samples from a distribution P and f (y

Assume that the sequence y 1 , . . . , y n is such that f (x 1 , y 1 ) -f (y 1 ) , . . . , f (x t , y t ) -f (y t ) is a martingale difference sequence with respect to x 1 , . . . , x n , y 1 , . . . , y n for any f ∈ F. Then for any > 0 and n

Proof. We divide the proof in two steps.

Step (i): Symmetrization Let x 1 , . . . , x n be a sequence of ghost samples i.i.d. from P . We use symmetrization to replace the average of the expectation f (y t ) with an empirical version over the ghost sample. Let f * ∈ F a function such that

Notice that f * is a random variable depending of samples x 1 , . . . , x n , y 1 , . . . , y n .

The following sequence of inequalities leads to the symmetrization result:

(a) We restrict the space of functions from F to the set of functions satisfying condition (B.6).

(b) We introduce the ghost sample.

(c) We write the joint probability as the expectation of the first event times the probability of the second even conditioned on the original sample x 1 , . . . , x n , y 1 , . . . , y n .

(d) The conditional probability can be lower-bounded as follows

where we used Chebyshev's inequality and the condition n 2 > 2. Thus we obtain

(f (x t , y t )f (x t , y t )) ≥

Step (ii): Azuma's inequality

We now use the functional Azuma's inequality in Lemma 7 to bound the last term. In fact, it easy to notice that f (x t , y t ) -f (y t )f (x t , y t ) -f (y t ) (B.7) is a martingale difference sequence ( f (x t , y t ) -f (y t ) is martingale difference sequence by assumption). Thus, we obtain

The final statement follows by putting together the two steps.