Matthieu Geist
email: matthieu.geist@centralesupelec.fr

Matthieu Geist Centralesupélec

The standard multi-class classification risk, based on the binary loss, is rarely directly minimized. This is due to (i) the lack of convexity and (ii) the lack of smoothness (and even continuity). The classic approach consists in minimizing instead a convex surrogate. In this paper, we propose to replace the usually considered deterministic decision rule by a stochastic one, which allows obtaining a smooth risk (generalizing the expected binary loss, and more generally the cost-sensitive loss). Practically, this (empirical) risk is minimized by performing a gradient descent in the function space linearly spanned by a base learner (a.k.a. boosting). We provide a convergence analysis of the resulting algorithm and experiment it on a bunch of synthetic and realworld data sets (with noiseless and noisy domains, compared to convex and non-convex boosters).

Introduction

The ideal multi-class classification task can be defined as the minimization (over some hypothesis space) of the expected binary loss (or equivalently, as minimizing the probability of predicting a wrong label). However, this risk is rarely directly minimized, notably because of (i) its lack of smoothness (and even continuity) and (ii) its lack of convexity. The classical approach consists in minimizing instead a convex (and possibly smooth) surrogate, such as the hinge loss (used in Support Vector Machines [START_REF] Schölkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF]), the exponential loss (used notably in AdaBoost [START_REF] Freund | A desicion-theoretic generalization of on-line learning and an application to boosting[END_REF], as shown for example in [START_REF] Mason | Boosting algorithms as gradient descent in function space[END_REF]) or the logit loss (for example used in [START_REF] Friedman | Additive logistic regression: a statistical view of boosting[END_REF]), among others. If using such surrogates does not come without guarantees [START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF], we propose an alternative approach in this article, focusing directly on the primary loss of interest.

The aforementioned classification methods are based on a deterministic decision rule. Here, we propose to use instead a stochastic decision rule. This does not provide a convex optimization problem, but at least we gain smoothness. The resulting (empirical) risk has then to be minimized. In order to ease the choice of the hypothesis space, we minimize this risk by performing a gradient descent in the function space linearly spanned by a base (or weak) learner. This is indeed a boosting [START_REF] Schapire | Boosting: Foundations and algorithms[END_REF] approach (seen as a functional gradient descent [START_REF] Mason | Boosting algorithms as gradient descent in function space[END_REF][START_REF] Grubb | Generalized boosting algorithms for convex optimization[END_REF], which is not the sole nor the original view of boosting). To sum up, this article introduces a boosting approach that directly minimizes the expected (cost-sensitive) binary loss.

The paper is organized as follows. Sec. 2 states the problem and introduces and motivates the considered risk, that generalizes strictly the usual expected (cost-sensitive) binary loss. Sec. 3 shows how this risk can be minimized using a boosting approach and introduces the related algorithm, named sm-boost (for soft-max boosting). The proposed method is analyzed in Sec. [START_REF] Freund | Boosting a weak learning algorithm by majority[END_REF]. We show mainly that the algorithm converges to a solution such that the related functional gradient is null, at a given rate. We also discuss informally the quality of the related solution (easy formal response being not available due to the lack of convexity). In Sec. 5, we discuss the choice of meta-parameters for smboost and present briefly AdaBoost.MH and SAMME, two efficient multi-class generalizations of AdaBoost which are natural competitors to sm-boost. We then compare all algorithms on a bunch of synthetic and real-world data sets. We also compare sm-boost to another non-convex booster, MartiBoost, on a challenging (for convex boosters) noisy toy problem. Eventually, we open some perspectives in Sec. 6.

Problem statement

Let D N = {(x i , y i ) 1≤i≤N } be a data set, with x i ∈ X , a compact subset of R d , and y i ∈ Y, a finite set of labels. The inputs x i are sampled according to some unknown distribution ρ(x) and the outputs y i are provided by an oracle (formally an unknown conditional distribution P(y|x)). Let c ∈ R X ×Y 2 + be a (bounded) cost function: c(x i , y i , y) is the cost (or loss) for choosing the label y instead of the oracle response y i for the input x i . This encompasses notably the classical binary loss, on which we will focus in the experimental section (Sec. 5): c(x i , y i , y) = I {y =yi} = 1 if y = y i 0 else .

Let G be a subset of (deterministic) functions mapping inputs to labels (that is, deterministic decision rules), G ⊂ Y X . The "ideal" (possibly cost-sensitive) multi-class classification problem may be defined as the minimization of the risk related to the above defined cost: min g∈G R(g) with R(g) = X y∈Y c(x, y, g(x))P(y|x)ρ(x)dx

= E X,Y [c(X, Y, g(X))]. (1)
The input and oracle distributions being only known through the data set, practically the related empirical risk is considered:

R N (g) = 1 N N i=1 c(x i , y i , g(x i )).
Notably, specialized to the binary loss, this gives:

R N (g) = 1 N N i=1 I {yi =g(xi)} .
There are two major issues with this risk. First, it is not convex, many local minimum may exist. Second, it is not smooth (or even continuous here), which may prevent to practically minimize it. The classical approach to overcome this problem consists in minimizing a convex (and possibly smooth) surrogate to this risk (for example, exponential or logit loss instead of the binary one).

Here, we propose an alternative approach: we replace the deterministic decision rule by a stochastic one, parameterized through a soft-max distribution. By doing so, we do not gain convexity, but we gain smoothness. We also strictly generalize the "ideal" risk (deterministic decision rules being a special case of stochastic ones). What we argue in the sequel is that minimizing directly the risk of interest is a viable alternative to standard approaches.

Proposed risk

Let Ψ be a subset of R X ×Y . A function ψ ∈ Ψ can be understood as a score function, ranking different labels for a given input. In classification, it is quite usual to define a deterministic decision rule as g ψ (x) = argmax y∈Y ψ(x, y).

Here, we propose instead to build a stochastic decision rule based on a softmax conditional distribution. Let ∆ Y be the set of distributions over Y. For ψ ∈ Ψ , we define the decision rule g ψ ∈ ∆ X Y as: ,y) z∈Y e ψ(x,z) .

g ψ (y|x) = e ψ(x
(

) 2
Then, what we propose to do is to consider directly the ideal risk provided in Eq. ( 1), and to minimize it over stochastic decision rules of the form given in Eq. ( 2), instead of minimizing it over deterministic decision rules:

R(g ψ ) = E X,Y [E Z∼g ψ (.|X) [g ψ (Z|X)c(X, Y, Z)]] = E X,Y [ z∈Y g ψ (z|X)c(X, Y, z)] (3) = X y∈Y z∈Y c(x, y, z)g ψ (z|x)P(y|x)ρ(x)dx.
As the input and oracle distributions are only known through the data, we consider the following empirical risk:

min ψ∈Ψ R N (ψ) with R N (ψ) = 1 N N i=1 E y∼g ψ (.|xi) [c(x i , y i , y)] (4) = 1 N N i=1 y∈Y g ψ (y|x i )c(x i , y i , y).

Motivation

As said before, the common technique in classification consists in minimizing a convex surrogate to the risk of interest. The resulting optimization problem becomes tractable, but one may wonder if minimizing such a convex proxy still results in a good accuracy. This is known as the problem of calibration, which studies how small the suboptimality gap, measured in term of the surrogate risk, should be to achieve a suboptimality gap, measured in term of the risk of interest, of a given size. This has been studied in the binary cost-insensitive case [START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF], in the binary cost-sensitive case [START_REF] Steinwart | How to compare different loss functions and their risks[END_REF] and in the cost-sensitive multiclasse case [START_REF] Pires | Cost-sensitive Multiclass Classification Risk Bounds[END_REF], for the convex surrogate proposed in [START_REF] Lee | Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data[END_REF]. However, it has also been advocated recently that a surrogate loss function should be guess-averse [START_REF] Beijbom | Guess-Averse Loss Functions For Cost-Sensitive Multiclass Boosting[END_REF], in the sense that the loss should encourage more correct classifications than arbitrary guesses. If all popular binary surrogate losses are guess averse, things become less clear in the cost-sensitive multi-class case. Notably, it shown in [START_REF] Beijbom | Guess-Averse Loss Functions For Cost-Sensitive Multiclass Boosting[END_REF] that the convex surrogate of [START_REF] Lee | Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data[END_REF] based on the exponential function, shown to be calibrated in [START_REF] Pires | Cost-sensitive Multiclass Classification Risk Bounds[END_REF], is not guess averse (and the question remains open for this surrogate based on other convex functions).

To sum up, choosing the right convex surrogate to the cost-sensitive multiclass risk of Eq. ( 1) is no an easy task. Moreover, in the case of boosting, it has been shown that convex boosters are necessarily sensitive to noise [START_REF] Long | Random Classification Noise Defeats All Convex Potential Boosters[END_REF] (this point will be further addressed in Sec. 5.5). What we propose here is to minimize directly the risk of interest, given in Eq. ( 1), but parameterized by the stochastic decision rule of Eq. ( 2) instead of the classical deterministic one, which provides the risk of Eq. (3). As deterministic decision rules are a special case of stochastic one, this is a generalization of the risk of interest rather than a surrogate. Moreover, the resulting optimization problem is smooth (see Sec. 4), and is thus tractable.

Yet, one may still wonder if this changes the problem at hand. Notably, as the decision rule is stochastic, one may think that risk (3) ultimately estimates conditional probabilities (of labels conditioned on inputs) and thus that it is a kind of logistic regression. This is not the case: ultimately, risk (3) provides the same solution as risk (1), as formalized below.

Proposition 1 Assume that the cost function corresponds to a single label problem, in the sense that:

Card argmin y∈Y E[c(X, Y, y)|X] = 1 almost surely.
Assume also that there exists a measurable function g * ∈ Y X such that

g * (x) = argmin y∈Y E[c(X, Y, y)|X = x], which is the minimizer of R(g) = E X,Y [c(X, Y, g(X))] over g ∈ Y X . Then, the minimizer of R(g ψ ) = E X,Y [ z∈Y g ψ (z|X)c(X, Y, z)] over g ψ ∈ ∆ X Y is: g * ψ (y|x) = I {y=g * (x)} .
Proof Assume that R admits a minimizer

g ψ = g * ψ . Write c(x, y) the expected cost for choosing y in x, c(x, y) = E[c(X, Y, y)|X = x],
and U the set of points where the minimizers disagree:

U = {x ∈ X |g ψ (.|x) = g * ψ (.|x)}.
If P(U ) = 0, the minimizers are equal almost surely. Else, for all x ∈ U we have:

z∈Y c(x, z)g ψ (z|x) = c(x, g * (x))g ψ (g * (x)|x) + z =g * (x) c(x, z)g ψ (z|x) > c(x, g * (x)){g ψ (g * (x)|x) + z =g * (x) g ψ (z|x)} = c(x, g * (x)) = z∈Y c(x, z)g * ψ(z|x) almost surely.
Therefore, R(g ψ ) > R(g * ψ ) and g ψ is not a minimizer.

We have just shown that, in the single label case, minimizing the risk over stochastic decision rules does not change the solution. In the multi-label case, the stochastic minimizer can distribute its probability masses over minimizers of the expected cost E[c(X, Y, z)|X = x] without changing the risk, which is better than choosing a single label (as would do the deterministic minimizer). Now that we have motivated the use of this risk, it will be shown how its empirical counterpart can be minimized and what guarantees it might offer.

A boosting approach

In this section, we minimize the risk defined in Eq. ( 4) using a boosting approach. To do so, we frame boosting as a functional gradient descent [START_REF] Mason | Boosting algorithms as gradient descent in function space[END_REF] to derive the proposed sm-boost (soft-max boosting) algorithm. First, we introduce the relevant related Hilbert space, following [START_REF] Grubb | Generalized boosting algorithms for convex optimization[END_REF].

Relevant Hilbert space

With a slight abuse of notations, we will see equivalently a function from R X ×Y as a function from (R Y ) X . Notably, we will write:

ψ(x) = (ψ(x, y)) y∈Y ∈ R Y and g ψ (x) = (g ψ (y|x)) y∈Y ∈ ∆ Y ⊂ R Y .
Let ., . be the Euclidian inner product in R Y and . be the associated norm. Assume that the input space X is measurable and let µ be a probability measure. The function space L 2 (X , R Y , µ) is the set of all equivalence classes of functions ψ ∈ (R Y ) X such that the Lebesgue integral X ψ(x) 2 dµ is finite. This Hilbert space has a natural inner product:

ψ, φ µ = X ψ(x), φ(x) dµ = X y∈Y ψ(x, y)φ(x, y)dµ.
As the quantity of interest is the empirical risk, the natural probability measure to be considered is ρ, involved by the data set D N . We write ., . N the related inner product, defined as:

ψ, φ N = 1 N N i=1 ψ(x i ), φ(x i ) = 1 N N i=1 y∈Y ψ(x i , y)φ(x i , y).
We also adopt the following notation for the cost c, evaluated in the training points:

c i = (c(x i , y i , y)) y∈Y = (c i (y)) y∈Y ∈ R Y . ( 5
)
This way, the considered empirical risk (defined in Eq. ( 4)) can be written as follows:

R N (ψ) = 1 N N i=1 c i , g ψ (x i ) = 1 N N i=1 y∈Y c i (y)g ψ (y|x i ).
We will compute a decision rule g ψ by performing a gradient descent on R N (ψ) (according to ψ). However, to do so, one has to compute the gradient of functionals over the Hilbert space L 2 (X , R Y , ρ). We consider here the Fréchet derivative. Let J : L 2 (X , R Y , ρ) → R be a functional (practically, it will be R N ), its (Fréchet) derivative is the linear operator ∇J(ψ) satisfying

lim φ→0 J(ψ + φ) -J(ψ) -∇J(ψ), φ N φ N = 0.
It can also be implicitly defined as

J(ψ + φ) = J(ψ) + ∇J(ψ), φ N + o( φ N ).

Restricted gradient descent

The issue with functions representing the functional gradient is that they are hard to manipulate and do not generalize well to new inputs. Instead of being directly followed, the gradient is projected on a restriction set of allowable directions (practically, the set of hypotheses generated by a weak learner). This is termed as restricted gradient descent in [START_REF] Grubb | Generalized boosting algorithms for convex optimization[END_REF]. Let H ⊂ R X ×Y be the hypothesis space generated by a weak learner. The closest function h to a gradient ∇J(ψ) along a candidate direction h is given by the vector projection:

h = ∇J(ψ), h N h 2 N h.
The function h * minimizing the resulting projection error actually maximises the projected length:

h * = argmax h∈H ∇J(ψ), h N h N . ( 6
)
This projection operation, proposed in [START_REF] Grubb | Generalized boosting algorithms for convex optimization[END_REF], generalizes the one of [START_REF] Mason | Boosting algorithms as gradient descent in function space[END_REF] to functions other than classifiers (yet, this is the case we will consider practically). Boosting can be seen as a gradient descent in a function space, the functional gradient being projected on the hypothesis space generated by a base (or weak) learner. This is summarized in Alg. 1 for the minimization of a functional J.

The softmax boosting algorithm

The functional we are interested in here is R N (ψ), provided in Eq. [START_REF] Freund | Boosting a weak learning algorithm by majority[END_REF]. A first thing to do is to compute its functional gradient, which is done below. Proposition 2 Let e y ∈ R Y be a vector such that all components are set to 0, except the one corresponding to y which is set to 1. Define ∆ ψ c i (y) as the centered cost according to the probability measure g ψ induced by ψ, for the input x i (the notation c i (y) being defined in Eq. ( 5)):

∆ ψ c i (y) = c i (y) - z∈Y g ψ (z|x i )c i (z) = c i (y) -E z∼g ψ (.|xi) [c i (z)].
The functional gradient of R N (ψ) is the set

∇R N (ψ) =    φ ∈ (R Y ) X : φ(x i ) = y∈Y g ψ (y|x i )∆ ψ c i (y)e y    .
Proof Recall that the considered gradient is defined according to the inner product under the empirical measure ρ. Therefore, only the values taken in the data points x i do matter. Let φ ∈ ∇R N (ψ), we have:

φ(x i ) = ∇ c i , g ψ (x i ) = y∈Y c i (y)∇g ψ (y|x i ).
Using a log-trick and the definition of g ψ (see Eq. ( 2)):

∇g ψ (y|x) = g ψ (y|x)∇ ln g ψ (y|x) = g ψ (y|x)∇{ψ(x, y) -ln z∈Y e ψ(x,z) } = g ψ (y|x)(∇ψ(x, y) -z∈Y e ψ(x,z) ∇ψ(x, z) z∈Y e ψ(x,z) ) = g ψ (y|x)(∇ψ(x, y) - z∈Y g ψ (z|x)∇ψ(x, z)).
Therefore, we have:

φ(x i ) = y∈Y c i (y)g ψ (y|x i )(∇ψ(x i , y) - z∈Y g ψ (z|x i )∇ψ(x i , z)) = y∈Y c i (y)g ψ (y|x i )(e y - z∈Y g ψ (z|x i )e z ) = y∈Y c i (y)g ψ (y|x i )e y -( y∈Y c i (y)g ψ (y|x i ))( z∈Y g ψ (z|x i )e z ) = y∈Y g ψ (y|x i )e y (c i (y) - y∈Y c i (y)g ψ (y|x i )) = y∈Y g ψ (y|x i )e y ∆ ψ c i (y).
This concludes the proof.

Thanks to this result, the inner product between a function h ∈ H and the functional gradient ∇R N (ψ) is given by:

∇R N (ψ), h N = 1 N N i=1 φ(x i ), h(x i ) , with φ ∈ ∇R N (ψ) = 1 N N i=1 y∈Y g ψ (y|x i )∆ ψ c i (y)h(x i , y).
For the rest of this paper, we will focus on hypothesis spaces generated by binary classifiers as weak learners, that is:

H ⊂ {-1, +1} X ×Y .
Let K = |Y| denote the cardinal of the finite set Y. For binary classifiers, we have:

∀h ∈ H, h 2 N = 1 N N i=1 y∈Y h(x i , y) 2 = K.
Therefore, projecting the gradient onto H reduces to maximizing ∇R N (ψ), h :

h * ∈ argmax h∈H 1 N N i=1 y∈Y g ψ (y|x i )∆ ψ c i (y)h(x i , y).
Consequently, using the proposed approach (projected functional gradient descent on R N ), the initial (possibly cost-sensitive) multi-class classification problem is reduced to a series of weighted binary classification problems.

Yet, it has been shown that introducing randomization in a boosting procedure can improve the estimation accuracy [START_REF] Friedman | Stochastic gradient boosting[END_REF]. The inner product to be maximized is indeed an expectation:

∇R N (ψ), h N = 1 N N i=1 y∈Y g ψ (y|x i )∆ ψ c i (y)h(x i , y) = E x,y∼ ρ(x)g ψ (y|x) [∆ ψ c i (y)h(x i , y)]. (7)
So, to introduce randomization, we propose to sample M inputs {(x j , z j ) 1≤j≤M } from the distribution ρ(x)g ψ (z|x) (the probability of a couple (x j , z j ) being thus 1 N g ψ (z j |x j )). The candidate direction is then computed as:

h * ∈ argmax h∈H R M (h) with R M (h) = 1 M M j=1 ∆ ψ c j (z j )h(x j , z j ). ( 8
)
This is a weighted binary classification problem with inputs (x j , y j ) 1≤j≤M , weights |∆ ψ c j (z j )| and outputs sgn(∆ ψ c j (z j )).

Algorithm 2: Softmax boosting (sm-boost)

Inputs; Data set {(x i , y i ) 1≤i≤N } ; Weak learner (H) ; Learning rates (α k ) k>0 ;
Number of samples to be drawn for projection M ;

Initialization;

Initialize ψ 0 = 0 ; for t = 1, 2, . . . T do Draw M inputs for the weighted binary classif. ; (x j , z j ) 1≤j≤M ∼ ρ(x)g ψ t-1 (z|x) ;

Solve h * t as the solution of the weighted binary classification problem with ; inputs: (x j , z j ) 1≤j≤M ; weights:

(|∆ ψ t-1 c j (z j )|) 1≤j≤M ; outputs: (sgn(∆ ψ t-1 c j (z j )) 1≤j≤M ; Update the score function ; ψt = ψ t-1 -αt ∇R N (ψ t-1 ),h * t N h * t 2 N h * t ;
Output the final hypothesis g ψ T ;

The proposed approach is summarized in Alg. 2. Choosing ψ 0 = 0 is a natural default initialization, as it corresponds to a uniform decision rule (equiprobability for each label). There are three meta-parameters: the weak learner (H), the learning rates ((α t ) t>0 ) and the number of samples to be drawn at each iteration (M ). We will discuss them in Sec. 5, partly based on the analysis to be done in the next section (Sec. 4). Before, it may be useful to provide a quick and intuitive explanation of the rationale behind the algorithm.

At step t, the algorithm has already computed a stochastic decision rule g ψt-1 (y|x). For a given input x i , using this decision rule, we pay an average cost (or loss) of E y∼g ψ t-1 (.|xi) [c i (y)]. For a given label y, if the cost c i (y) is higher than the expected cost, then the binary classifier will have a target of +1, with a weight proportional to the absolute difference between the label cost and the payed averaged cost (that is, |∆ ψt-1 c j (y)|). Ideally, we have h * t (x i , y) = +1. Given the update rule, this means that the probability of choosing this label will decrease in the next decision rule, g ψt . Similarly, if the cost c i (y) is lower than the expected cost, then the probability of choosing this label will increase.

We also discuss briefly the computational cost of this algorithm. At each iteration, the decision rule must be updated, for all labels and inputs of the data set, which can be done in O(N K). Drawing the M inputs can be done by performing a binary search of M random samples (uniform distribution) in the cumulative sum of computed probabilities, which has a cost of O(N K + M log(N K)). Computing the weights and outputs used by the base learners has a cost of O(M K). The cost for training the weak learner depends on the weak learner. For example, constructing a decision tree (the base learner considered in this paper) with M samples has roughly a cost of O(M log(M )) [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]. Here, we train K weak learners, each with M i data points (satisfying

K i=1 M i = M ). As K i=1 M i log(M i ) = M log(M )+ K i=1 M i log( Mi M ) ≤ M log(M ),

the cost would be of O(M log(M )) (practically, less than training one classifier with all data points). This gives a rough total cost per iteration of

O(N K + M log(M N K)).

Analysis

Using a stochastic decision rule allows gaining some smoothness, as shown in the next lemma. However, it does not transform the related optimization problem (minimization of R N (ψ)) into a convex one. Smoothness will allow showing that the norm of the functional gradient tends to 0 (at a given rate), but the lack of convexity prevents from providing easily stronger results. Nevertheless, we will also discuss informally the quality of the computed solution.

Lemma 1 Without loss of generality, assume that

c ∈ [0, 1] X ×Y 2 . The func- tional R N (ψ) defined in Eq. (4) is 1-Lipschitz-smooth: ∀ψ, φ ∈ L 2 (X , R Y , ρ), ∇R N (ψ) -∇R N (φ) N ≤ ψ -φ N .
Proof To prove this result, we will first study the function F ∈ (R) R K defined as

F (u) = K k=1 α k f k (u) with α k ∈ [0, 1] and f k (u) = e u e k K l=1 e u e l .
We will show that F is 1-Lipschitz-smooth. To do so, we first compute its gradient (resp. to u ∈ R K ). Similarly to the proof of Prop. 2, we have:

∇F (u) = K k=1 f k (u) α k - K l=1 α l f l (u) e k = K k=1 f k (u) (α k -F (u)) e k .
Next, we compute its Hessian H(u) = ∇∇ F (u):

H(u) = ∇{ K k=1 f k (u)(α k -F (u))e k } = K k=1 (α k -F (u))(∇f k (u))e k - K k=1 f k (u)(∇F (u))e k = K k=1 (α k -F (u))f k (u)(e k - K l=1 f l (u)e l )e k - K k=1 f k (u)( K l=1 f l (u)(α l -F (u))e l )e k = K k=1 (α k -F (u))f k (u)(1 -f k (u))e k e k - K k=1 (α k -F (u))f 2 k (u)e k e k = K k=1 f k (u)(1 -2f k (u))(α k -F (u))e k e k .
From this expression, one can see that the convexity of F is far from being guaranteed (H being a diagonal matrix with possibly negative elements). Let v ∈ R K , we have

H(u)v 2 = v H(u) H(u)v = K k=1 f 2 k (u)(1 -2f k (u)) 2 (α k -F (u)) 2 v 2 i ≤ K k=1 v 2 i = v 2 .
Therefore, the induced norm of the Hessian satisfies H(u) ≤ 1, for all u ∈ R K . This shows that F is 1-Lipschitz-smooth, so

∇F (u) -∇F (v) = K k=1 {f k (u)(α k -F (u)) -f k (v)(α k -F (v))}e k ≤ u -v .
Going back to the functional of interest, we have (through Prop. 2):

∇R N (ψ)-∇R N (φ) 2 N = 1 N N i=1 y∈Y {g ψ (y|x i )∆ ψ c i (y)-g φ (y|x i )∆ φ c i (y)}e y 2 .
Thanks to the preceding result (u plays the role of ψ(x i ), v of φ(x i ), α y of c i (y)), we have for all 1 ≤ i ≤ N :

y∈Y {g ψ (y|x i )∆ ψ c i (y) -g φ (y|x i )∆ φ c i (y)}e y ≤ ψ(x i ) -φ(x i ) .
Therefore:

∇R N (ψ) -∇R N (φ) 2 N ≤ 1 N N i=1 ψ(x i ) -φ(x i ) 2 = ψ -φ 2 N .
This concludes the proof.

This smoothness result is a key to show that sm-boost converges to a solution such that the (functional) gradient is null. For that, we must do some assumption on the capability of the hypothesis space H to approximate well the projected gradient.

Definition 1

The hypothesis space H has an edge γ ∈]0, 1[ if for every gradient ∇R N (ψ), there exists a function h ∈ H such that:

∇R N (ψ), h N ≥ γ ∇R N (ψ) N h N .
This definition of edge has been introduced in [START_REF] Grubb | Generalized boosting algorithms for convex optimization[END_REF]. For example, if H is a space of binary classifier that is able to do (strictly) better than random guessing for the provided data set and for any associated weights, then H has an edge γ > 0 (see Th. 1 and related discussion in [START_REF] Grubb | Generalized boosting algorithms for convex optimization[END_REF] for more details).

The proposed convergence result can now be provided.

Theorem 1

Assume that H has an edge γ > 0. Without loss of generality, assume also that c ∈ [0, 1] X ×Y 2 . Let (ψ t ) t≥0 be the sequence of functions computed by the sm-boost algorithm for the learning rate α t = 1 (for all t > 0). We have that:

lim t→∞ ∇R N (ψ t ) N = 0.
Moreover, we have the following convergence rate:

min 1≤t≤T +1 ∇R N (ψ t ) N ≤ 1 γ 2 T .
Proof The proof is basically an adaptation of the convergence of standard gradient descent for a smooth minimized function (e.g., see [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]). Thanks to the smoothness result of Lemma 1, we have that for any ψ, φ ∈ L 2 (X , R Y , ρ) (again, see [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF] for example):

|R N (φ) -R N (ψ) -∇R N (ψ), φ -ψ N | ≤ 1 2 φ -ψ 2 N .
Notably, for ψ t and ψ t-1 :

R N (ψ t ) ≤ R N (ψ t-1 ) + ∇R N (ψ t-1 ), ψ t -ψ t-1 N + 1 2 ψ t -ψ t-1 2 N .
From the update rule, we have:

ψ t -ψ t-1 = -α t ∇R N (ψ t-1 ), h * t N h * t 2 N h * t .
Therefore, we have:

R N (ψ t ) ≤ R N (ψ t-1 ) -α t (1 - α t 2 ) ∇R N (ψ t-1 ), h * t N h * t N 2 .
The quantity α t (1 -αt 2 ) is maximized for α t = 1 and the edge assumption im-

plies that ∇R N (ψ t-1 ), h * t N ≥ γ ∇R N (ψ t-1 ) N h * t N
. Therefore, we have:

R N (ψ t ) ≤ R N (ψ t-1 ) - γ 2 2 ∇R N (ψ t-1 ) 2 N ⇔ R N (ψ t-1 ) -R N (ψ t ) ≥ γ 2 2 ∇R N (ψ t-1 ) 2 N .
Summing this last inequality over t, we get

γ 2 2 T -1 t=0 ∇R N (ψ t ) 2 N ≤ R N (ψ 0 ) -R N (ψ T ) ≤ 1.
The last (rightmost) inequality results from the assumption that the cost is positive and bounded by 1. This allows concluding with bot results:

lim t→∞ ∇R N (ψ t ) N = 0 and min 1≤t≤T +1 ∇R N (ψ t ) N ≤ 1 γ 2 T .
This concludes the proof.

This result tells us that sm-boost will converge to a decision rule such that the functional gradient is null. However, it is rather weak as it does not tell anything about the quality of the solution. We can end up in a local minima, or even just in a stationary point. Indeed, without convexity, it might be difficult to tell more. Moreover, this result does not tell anything about the generalization capability of the computed estimator (a question we will address experimentally in this paper, but not theoretically).

Yet, some informal insights regarding the computed solution can be gained by looking at the norm of the gradient (which we know to ultimately go to zero). We have (again according to Prop. 2):

∇R N (ψ) 2 N = 1 N N i=1 y∈Y (g ψ (y|x i )∆ ψ c i (y)) 2 .
For the gradient to be small, each term y∈Y (g ψ (y|x i )∆ ψ c i (y)) 2 has to be small. Let fix x i . This in turn means that for any y, either ∆ ψ c i (y) is small, or g ψ (y|x i ) is small. For simplicity, we identify here Y with {1, . . . , K}. For the cost-insensitive multi-class classification case, and without loss of generality, assume that the correct label is 1:

c i = 0 1 . . . 1 .
Let η 1 = g ψ (1|x i ) be the probability of choosing the right label (and similarly, η j = g ψ (j|x i )). In this case, the expected cost is y∈Y g ψ (y|x i )c i (y) = 1 -η 1 .

As a result, we have

∆ ψ c i (1) = -(1-η 1 ) and ∆ ψ c i (k > 1) = η 1 . Consequently, we can write y∈Y (g ψ (y|x i )∆ ψ c i (y)) 2 = η 2 1   (1 -η 1 ) 2 + K j=2 η 2 j   .
For this quantity to be small, we should have either η 1 ≈ 1 or η 1 ≈ 0. In the first case, the right label is chosen. The second case is more problematic: the probabilities are distributed among any combination of labels, except the good one. However, let ψ be a function in the neighborhood of ψ, such that η 1 = η 1 + , all other things being equal (notably, the probabilities do not change for other inputs). Then, we have that

R N (ψ ) = R N (ψ) - N .
This means that ψ cannot be a local minimum, as an arbitrarily small perturbation can lead to a lower risk. This let hope that η 1 ≈ 1 is more likely to happen and that sm-boost computes a good solution. This has to be confirmed experimentally.

Experimental results

In this section, we provide experimental results on both synthetic (Sec. 5.3) and real-world (Sec. 5.4) data sets. The proposed approach will be compared to AdaBoost.MH [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF], a state-of-the-art boosting algorithm that uses the same type of base learner, and to SAMME [START_REF] Zhu | Multi-class AdaBoost[END_REF] (Stagewise Additive Modeling using a Multi-Class Exponential loss function), a more recent multi-class extension of AdaBoost, to be briefly presented in Sec. 5.2. It will appear that sm-boost is less sensitive to noise. Yet, it is known that convex boosters (what are AdaBoost.MH and SAMME) are not noise-tolerant [START_REF] Long | Random Classification Noise Defeats All Convex Potential Boosters[END_REF]. Therefore, sm-boost will be compared to another non-convex booster, MartiBoost [START_REF] Long | Martingale Boosting[END_REF] (Martingale Boosting) on a challenging toy problem [START_REF] Long | Martingale Boosting[END_REF] in Sec. 5.5. First, we discuss the choice of meta-parameters for sm-boost.

Meta-parameters

There are three meta-parameters to be chosen in sm-boost: the base learner (H), the learning rate (α i ) and the number of samples to be drawn for each projection (M ). When using binary classifiers as base learners, sm-boost reduces (costsensitive) multi-class classification to weighted binary classification. However, the inputs of those intermediate steps are a concatenation of original inputs and labels, sampled in the set {(x i , y) 1≤i≤N,y∈Y }. There are multiple solutions to this. For example, labels can be considered as they are, or they can be binarized. However, a standard classifier will more likely handle inputs from X , the original input set. Let F ⊂ {-1, +1} X be the hypothesis space generated by such a base learner, we will consider H = F Y . More precisely, writing δ y the Dirac in y ∈ Y, we consider:

H = {h(x, y) = z∈Y δ z (y)f z (x) such that ∀z ∈ Y, f z ∈ F}.
The binary classification objective function [START_REF] Friedman | Stochastic gradient boosting[END_REF] can thus be written as:

R M (h) = 1 M M j=1 ∆ ψ c j (z j )h(x j , z j ) = y∈Y R M,y (f y ) with R M,y (f ) = 1 M M j=1 δ y (z j )∆ ψ c j (z j )f (x j ).
Therefore, computing h * amounts to solving K weighted binary classification problems:

argmax h∈H R M (h) = argmax f ∈F R M,y (f ) y∈Y .
There remains to choose F. In all forthcoming experiments, we consider classification trees (the CART algorithm [START_REF] Breiman | Classification and regression trees[END_REF] provided in the scikit-learn library [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]), growth in a best-first fashion to a maximum of 12 leafs.

The second meta-parameter to be chosen is the learning rate. Recall that Th. 1 holds for the simple choice α t = 1, for all t > 0. Yet, we will practically consider a more aggressive (yet still simple) learning rate. Recall that the "global" learning rate is

α t ∇R N (ψ t-1 ), h * t N h * t 2 N
.

First, for binary classifiers, we have h * t 2 N = K. In order to be insensitive to the number of classes, we choose α t to be proportional to the number of classes. Second, recall that theoretically h * t is computed to maximize ∇R N (ψ t-1 ), h N , which is indeed an expectation, see Eq. [START_REF] Friedman | Additive logistic regression: a statistical view of boosting[END_REF]. In order to introduce randomization, we have replaced this expectation by the Monte Carlo estimate R M (see Sec. 3.3). Therefore, it is natural to consider R M (h * t ) instead of ∇R N (ψ t-1 ), h * t N (this initial inner product being somehow more conservative). To sum up, in all forthcoming experiments the learning rate will be

α t = K R M (h * t ) ∇R N (ψ t-1 ), h * t N ⇔ α t ∇R N (ψ t-1 ), h * t N h * t 2 N = R M (h * t ) = 1 M M j=1 ∆ ψt-1 c j (z j )h * t (x j , z j ),
with (x j , z j ) 1≤j≤M the samples drawn at the t th iteration. The last meta-parameter is M , the number of samples to be drawn for training the weak learner at each iteration. With a default initialization ψ 0 = 0, the initial decision rule is uniformly random and N K samples are candidate for sampling. Asymptotically, the decision rule is likely to become deterministic (at least for single-label multi-class classification, as seen in Sec. 4), so there will be N candidate samples for sampling. Therefore, M = N seems to be a good default choice, corresponding roughly to an adaptive subsampling. In all forthcoming experiments, we set M = N .

Competitors

We present briefly the algorithms to which sm-boost will be compared, namely AdaBoost.MH [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF] and SAMME [START_REF] Zhu | Multi-class AdaBoost[END_REF]. The presentation of MartiBoost [START_REF] Long | Martingale Boosting[END_REF], that can handle only binary classification problems, is postponed to Sec. 5.5.

The AdaBoost.MH algorithm

AdaBoost, introduced in [START_REF] Freund | A desicion-theoretic generalization of on-line learning and an application to boosting[END_REF], is the first boosting algorithm, dedicated to the binary classification problem. It has been shown [START_REF] Mason | Boosting algorithms as gradient descent in function space[END_REF][START_REF] Friedman | Additive logistic regression: a statistical view of boosting[END_REF] that AdaBoost is indeed a functional gradient descent minimizing the expected exponential loss (so, a convex surrogate to the risk based on the binary loss), with a learning rate computed using an exact line search (which is analytically possible in this case, contrary to sm-boost). AdaBoost.MH [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF] is a multi-class generalization of AdaBoost based on Hamming loss.

There are indeed many generalizations of AdaBoost to the multi-class setting. However, AdaBoost.MH provides competitive results [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF][START_REF] Kégl | The return of AdaBoost.MH: multi-class Hamming trees[END_REF] and it has been argued that with large samples, it has optimal classification performance [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF]. Moreover, the underlying mechanistic of sm-boost is very close to the one of AdaBoost.MH (training weak learners on re-weighted samples of the original data set) and both algorithms are based on the same type of weak learners (H ⊂ {-1, +1} X ×Y ), which makes comparisons easier and more reasonable.

AdaBoost.MH is summarized in Alg. 3, using the same notations as smboost to ease the comparison. Here, the cost c belongs to {-1, +1} X ×Y 2 (instead of {0, +1} X ×Y 2 for the binary loss considered so far):

c(x i , y i , y) = 2I y =yi -1 (instead of I y =yi ).
The algorithm also maintains a distribution w used to train successive weak learners, this distribution being updated according to the related results.

Initialization;

Initialize ψ 0 = 0 ; Set the initial distribution: There are strong similarities between AdaBoost.MH and sm-boost. Both algorithms re-weight samples of the original data set to train similar weak classifiers. Consider the (global) learning rate of sm-boost,

w 0 (x i , y) = 1 N K , 1 ≤ i ≤ N , y ∈ Y ; for t =
1 M M j=1 ∆ ψt-1 c j (z j )h * t (x j , z j ),
it is also an edge (as the sum of weighted prediction-target products). Moreover, for a small edge γ (one can easily show that γ ∈]0, 1] for a weak binary classifier doing better than random guessing), one has 1 2 ln 1+γ 1-γ = γ + o(γ 2 ). Therefore, both algorithms share a similar learning rate when the edge is small. There are also strong differences. The weighting scheme, as well as the targets for intermediate binary classifiers, are different (the target being adaptive for sm-boost, contrary to AdaBoost.MH), and they output different decision rule (respectively deterministic and stochastic). This was to be expected, as both approaches attempt to minimize different risks.

The only meta-parameter of AdaBoost.MH is the base learner. In all forthcoming experiments, we use the same weak learner as for sm-boost. Notice that AdaBoost.MH has a higher computational cost: sm-boost requires training K classifiers with M = N samples divided up among those classifiers, while Ad-aBoost.MH requires training K classifiers with N samples each.

The SAMME algorithm

SAMME [START_REF] Zhu | Multi-class AdaBoost[END_REF] is a more recent multi-class extension of AdaBost, that does no reduce to multiple two-class problems. It is obtained as a forward stagewise additive modeling approach that minimizes an exponential loss for multiclass classification. In other words, the considered weak learners have to solve weighted multi-class classification problems. SAMME is summarized in Alg. 4 (and is exactly AdaBoost for the case K = 2). The only meta-parameter of SAMME is the base learner. As for sm-boost and AdaBoost.MH, we consider classification trees. Yet, recall that these al-gorithms have to train one weak learner per class (with tress growth in a best-first fashion to a maximum of 12 leafs), while SAMME trains only one weak learner per iteration (that performs multi-class classification rather than binary classification). Therefore, to have a fair comparison, the base learner is here a classification tree growth to a maximum of (K -1) • 12 leafs 1 .

Algorithm 4: SAMME

Inputs; Data set {(x i , y i ) 1≤i≤N } ; Weak learner (H) ; Initialization; Initialize ψ 0 = 0 ; Set the initial distribution: w 0 (x i ) = 1 N , 1 ≤ i ≤ N ; for t = 1,

Synthetic problems

The first considered experiment are synthetic and randomly generated multiclass classification problems, inspired from [START_REF] Guyon | Design of experiments of the nips 2003 variable selection benchmark[END_REF] (Madelon data set) and whose implementation is provided in [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]. Sampling such a problem is parameterized by d info (the number of informative features), d red (the number of redundant features that are random linear combination of informative ones), d rep (the number of repeated features), d useless (the number of useless features, drawn at random), K (the number of classes), C K (the number of cluster per classes), β (the fraction of samples whose classes are randomly exchanged) and N (the number of training samples). With these parameters, a classification problem is sampled by creating clusters of points normally distributed (standard deviation of one) about vertices of a d info -dimensional hypercube and assigning an equal number of cluster to each class. Interdependences between these features are introduced and various type of further noise are added to the data, as described above. Moreover, the features are shifted by a random value drawn in [-1, 1] and scaled by another random value drawn in [START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF]100]. This provide a classification problem with d = d info + d red + d rep + d useless features and K classes.

Comparison to AdaBoost.MH

We generated 1000 such problems with d info ∼ U [START_REF] Beijbom | Guess-Averse Loss Functions For Cost-Sensitive Multiclass Boosting[END_REF][START_REF] Guyon | Design of experiments of the nips 2003 variable selection benchmark[END_REF] (U denotes the uniform distribution), [START_REF] Beijbom | Guess-Averse Loss Functions For Cost-Sensitive Multiclass Boosting[END_REF][START_REF] Freund | An adaptive version of the boost by majority algorithm[END_REF] , β ∼ U [0,0.25] and N ∼ U [300,3000] . For each problem, we also sampled N test = 10000 data points (with noiseless labels) to estimate the true risk (so, not used in the training set, of which we recall the size to be drawn randomly). For each such problem, we trained AdaBoost.MH and sm-boost for T = 1000 iterations.

d red ∼ U [0,3] , d rep ∼ U [0,3] , d useless ∼ U [0,3] , K ∼ U [2,5] , C K ∼ U
By training error (an error being denoted generically in the following), we mean the empirical risk (with the binary loss) on training data, and by testing (or generalization) error we mean the estimation of the true risk (still 1 For the stochastic decision rule used in sm-boost, we have that, for any ϕ ∈ R X ,

g ψ (y|x) = e ψ(x,y) z∈Y e ψ(x,z) = e ψ(x,y)+ϕ(x) z∈Y e ψ(x,z)+ϕ(x)
.

Therefore, there is some redundancy among the K trained weak classifiers, and there is indeed K -1 degrees of liberty. That explains the choice of (K -1) • 12 leafs (rather than K • 12 leafs). with the binary loss, with noiseless labels here) based on testing data (sampled independently). In Fig. 1, we compare for both algorithms the training error (first row) and the testing error (second row) after respectively 10, 100 and 1000 iterations (first to third column). Each graph provides AdaBoost.MH in abscissa and sm-boost in ordinate. A point above the line y = x (in red) means that AdaBoost.MH < sm-boost (AdaBoost.MH is better), and a point under the line (in blue) means that AdaBoost.MH > sm-boost (sm-boost is better).

One can see on Fig. 1 that AdaBoost.MH provides almost always a lower training error. This might appear surprising, as sm-boost directly attempt to minimize this error, contrary to AdaBoost.MH. However, the exponential loss is a good surrogate to the binary one, the underlying optimization problem is convex (not the case for sm-boost), and the learning rate is computed by an exact line search (again, not the case for sm-boost). So, this is not such a big surprise. Yet, regarding the generalization error, sm-boost is competitive, and often better than AdaBoost.MH for large number of iterations (despite the lack of convexity and of an optimal learning rate).

To get more insights into the difference of performance, Fig. 2 provides histograms of the difference of errors, AdaBoost.MHsm-boost , for the same cases (training and testing error for T = 10, 100 and 1000 iterations). This confirms the above observations.

Comparison to SAMME

The same experience has been performed to compare SAMME and sm-boost (1000 problems were generated, with the same random laws for drawing problems meta-parameters, and both algorithms were trained for T = 1000 iterations, for each random problem). Results are provided in Fig. 3 (comparison of training and testing errors after respectively 10, 100 and 1000 iterations) and Fig. 4 (histograms of the difference of errors). The same conclusions can be drawn (higher training error and lower generalization error for sm-boost).

Real-world data sets

In this section, we show the results of running sm-boost on a collection of data sets from the libsvm repository2 (these data sets coming from various repositories, such as UCI or Statlog for example). Each data set comes with pre-specified training and testing sets and is summarized in Table 1.

We compare AdaBoost.MH, SAMME and sm-boost using these pre-specified sets, and provide results after respectively T = 10, T = 100 an T = 1000 iterations (or trees) in Table 2. It can be seen that AdaBoost.MH or SAMME almost always provide a lower error, and that the difference of errors tends to decrease with the number of iterations (but still in disfavor of sm-boost). To get a larger picture of what happens for this testing error (as well as for the learning one), we ran 25 independent runs (shuffled data, using the same train and test sizes). Fig. 5 provides the learning (left subfigures) and testing (right) errors (mean ± standard deviation represented) as a function of the number of iterations, for each data set. The trend of Table 2 is confirmed: consistently lower AdaBoost.MH or SAMME error and usually diminishing difference of errors. This also provides some insight on the learning error: the ones of AdaBoost.MH and SAMME diminishe more rapidly to a lower value.

Recall the results of the synthetic experiments (Sec. 5.3). If learning errors have a similar behavior, it is not the case for testing errors (sm-boost is generally better, for a large number of iterations, in the synthetic experiments). However, recall that various type of noises were introduced in the data in Sec. 5.3, which is not the case for real data (at least, not willingly).

Therefore, we corrupted the real-world data sets by randomly exchanging labels of 20% of samples. We provide results after respectively T = 10, T = 100 an T = 1000 iterations (or trees) in Table 3, recalling in parentheses the noiseless results from Table 2. We also provide a larger picture of what happens with Fig. 6 (similar to Fig. 5, but with noisy data). The trend regarding the learning errors is the same, but the trend regarding the testing error is reversed: now, sm-boost provides almost always lower errors.

To summarize these experimental results, sm-boost appears to be competitive with AdaBoost.MH and SAMME. It provides higher generalization errors for the considered standard real-world data set, but it is more robust to noisy data (real data sets and synthetic experiments). Also, there might exist better choices for the learning rate or the number of samples to be drawn at each iteration, for sm-boost. This algorithm is also slower to train (as seen on the train error curves), and increasing the number of iterations could improve the generalization error. If sm-boost is clearly not the ultimate classification algorithm, these experiments show that minimizing directly the risk of interest is a viable alternative to more standard approaches.

About non-convex boosters

Previous experiments have shown that sm-boost is less sensitive to noise than AdaBoost.MH and SAMME. However, it has been shown in [START_REF] Long | Random Classification Noise Defeats All Convex Potential Boosters[END_REF] that convex potential boosters (what are AdaBoost and its generalizations, among others, and what is not sm-boost) are defeated by random classification noise. There exist non-convex boosters (e.g. [START_REF] Freund | Boosting a weak learning algorithm by majority[END_REF][START_REF] Freund | An adaptive version of the boost by majority algorithm[END_REF][START_REF] Kalaia | Boosting in the presence of noise[END_REF][START_REF] Long | Martingale Boosting[END_REF]). Yet, as far as we know, these algorithms are dedicated to the cost-insensitive binary classification problem, and cannot be extended easily to the cost-sensitive multi-class problem. Nevertheless, we compare in this section sm-boost to another non-convex booster, MartiBoost [START_REF] Long | Martingale Boosting[END_REF] (Martingale Boosting), that comes with theoretical guarantees (notably regarding tolerance to noise). Algorithms (sm-boost, MartiBoost and SAMME, that results in AdaBoost in the binary case) will be compared on the challenging (for convex problem) toy problem proposed in [START_REF] Long | Random Classification Noise Defeats All Convex Potential Boosters[END_REF].

Martingale Boosting

MartiBoost [START_REF] Long | Martingale Boosting[END_REF] constructs a branching program with L + 1 layers in a grid graph structure, where layer l has l nodes (see Fig. 7, left). Each node of the first L layers corresponds to a weak learner (therefore, there is a total of T = L(L+1) 2 weak learners). Once trained, prediction is done as follows. A new input x is presented to the top root node. The corresponding weak learner predicts the label, +1 or 0, which results in routing the example x respectively to the right or to the left in the next layer. This procedure is repeated until the sample reaches the last layer. If the last node is in the right part of the last layer (if its index is greater than L 2 ), then the final prediction is +1, else it is 0.

Training such a branching program assumes the availability of a two-sided weak learner (roughly, a weak learner that provides the same accuracy for both positive and negative examples). The program is trained layer by layer. The empirical distribution (corresponding to the training set) is filtered until reaching an untrained node (samples being routed through already trained nodes). Then this filtered distribution is used to train the two-sided weak learner. However, usual weak learners are one-sided (they try to minimize the expected binary loss). Yet, such a weak learner can be used to simulate a twosided one. To do so, the filtered distribution is balanced (such that positive and negative samples have the same cumulated probability masses) before training, and the resulting decision rule is randomized (such that it outputs each label equally often). For more details, see [START_REF] Long | Martingale Boosting[END_REF].

Considered toy problem

The toy problem we consider has been proposed in [START_REF] Long | Random Classification Noise Defeats All Convex Potential Boosters[END_REF]. Each training set consists of 4000 samples, divided into three groups: 1000 "large margin examples", 1000 "pullers" and 2000 "penalizers". Each labeled example (x, y) in the set is generated as follows. The label y is chosen randomly in {0, 1} (with equal

Results

We compare sm-boost to SAMME (so, AdaBoost in this binary case) and MartiBoost, for varying levels of noise (p varying from 0 to 0.5 by steps of 0.05). For all boosters, weak learners are decision stumps (classification trees with two leafs). SAMME and sm-boost are trained for T = 1000 iterations (thus T = 1000 weak learners). MartiBoost is trained for L = 300 stages (thus T = 45150 weak learners). For each level of noise, the experiment (generating a training set, as depicted before, to train all algorithms, and generating a testing set to evaluate them) is repeated 100 times. Results are presented in Fig. 7 (right), that shows for each algorithm the test error after training as function of the noise level (mean ± standard deviation represented).

Without noise, all boosters have a perfect accuracy. SAMME's performance degrades with as low as 5% of noise (and this result is consistent with the one in [START_REF] Long | Random Classification Noise Defeats All Convex Potential Boosters[END_REF]). MartiBoost accuracy decreases when the level of noise increases. Yet, the test error always remains below the noise level. On the other hand, smboost has a perfect accuracy for a large range of noise, that deteriorates to reach the accuracy of MartiBoost after 40% of corrupted labels.

Conclusion

This paper has introduced sm-boost, a boosting algorithm which directly minimizes the expected binary loss, considering a stochastic decision rule parameterized by a soft-max conditional distribution. Its convergence has been analyzed and discussed. The proposed approach has also been compared empirically to AdaBoost.MH and SAMME, and has been shown to be competitive, especially in the case of noisy data (AdaBoost.MH and SAMME remaining more efficient, regarding both learning and testing errors, for clean data). As it is known that convex boosters are sensitive to noise, we also compared smboost to another non-convex booster, MartiBoost. The proposed algorithm appears to be more robust to noise.

As said before, we argue that minimizing directly the risk of interest is a viable alternative to more standard approaches. It is all the more true that some interesting perspectives exist. First, the proposed algorithm can be directly applied to cost-sensitive and multi-label multi-class classification (through the definition of the cost function c), which is not so straightforward for usual convex surrogates, as discussed in Sec. 2.2. Empirical evaluations on such problems is an interesting perspective. The analysis we provide is somehow weak, notably due to the lack of convexity; it would be interesting to study to what extent it could be improved (notably based on a margin point of view). Especially, two aspect should be studied: the quality of the reached local minimum (a question to which we provided an informal answer) and the generalization capability of the proposed estimator (empirical results show that sm-boost has a good generalization capability, this should be studied theoretically). The introduced risk is minimized using a naive (functional) gradient descent. Other (more efficient) optimization techniques may be envisioned. From a more practical point of view, the considered weak learners are quite simple (as we train K classifiers at each iteration). It has been shown that using such base learners does not provide the best results for AdaBoost.MH [START_REF] Kégl | The return of AdaBoost.MH: multi-class Hamming trees[END_REF]. Therefore, sm-boost could be improved by using weak learners that take advantage of the particular inputs (original input-label tuple) [START_REF] Kégl | Boosting products of base classifiers[END_REF][START_REF] Kégl | The return of AdaBoost.MH: multi-class Hamming trees[END_REF]. Finally, extending this idea (minimizing directly the loss of interest through a stochastic decision rule) beyond boosting (for example to learning in Reproducing Kernel Hilbert Spaces) is worth being studied.

Algorithm 3 :

 3 AdaBoost.MH Inputs; Data set {(x i , y i ) 1≤i≤N } ; Weak learner (H) ;

Fig. 1

 1 Fig. 1 Synthetic problems, AdaBoost.MH versus sm-boost.

Fig. 2

 2 Fig. 2 Synthetic problems, histograms of AdaBoost.MHsm-boost .

Fig. 3

 3 Fig. 3 Synthetic problems, SAMME versus sm-boost.

Fig. 4

 4 Fig. 4 Synthetic problems, histograms of SAMMEsm-boost .

Fig. 5

 5 Fig. 5 Train and test error curves for the considered data sets.

Fig. 6

 6 Fig.[START_REF] Freund | A desicion-theoretic generalization of on-line learning and an application to boosting[END_REF] Train and test error curves for the considered data sets, with corrupted labels.

Fig. 7 (

 7 Fig. 7 (Left) the branching programm constructed by MartiBoost. (Right) results on the challenging noisy toy problem.

Algorithm 1: Basic boosting algorithm

	Inputs;
	Initial function ψ 0 ;
	Learning rates (αt) t>0 ;
	Hypothesis space H ;
	for t = 1, 2, . . . T do
	Compute the gradient ∇t = ∇J(ψ t-1 ) ;
	Project ∇t onto H (see Eq. (6)), finding nearest directions h * t ;
	Update ψ : ψt = ψ t-1 -αt	h * t ,∇ t N h * t 2 N	h * t ;

  1, 2, . . . T do Compute the edge γt and the learning rate αt ;

	Solve h * t as the solution of the weighted binary classification problem with ;
	inputs: (x i , y) 1≤i≤N,y∈Y ;
	weights: (w t-1 (x i , y)) 1≤i≤N,y∈Y ;
	outputs: (-c i (y)) 1≤i≤N,y∈Y ;
	γt = -	N i=1	y∈Y w t-1 (x i , y)h * t (x i , y)c i (y) ;
	αt = 1 2 ln 1+γ t 1-γ t

;

Update the distribution w, for all 1 ≤ i ≤ N , y ∈ Y ; wt(x i , y) = w t-1 (x i ,y)e α t c i (y)h * t (x i ,y) N j=1 z∈Y w t-1 (x j ,z)e α t c j (z)h * t (x j ,z) ;

Update the score function ; ψt = ψ t-1 + αth * t ; Output the final hypothesis ; the deterministic decision rule is x → argmax y∈Y (sgn(ψ T (x, y))) ;

  2, . . . T do Compute the error t and the learning rate αt ; Output the final hypothesis ; the deterministic decision rule is x → argmax y∈Y (ψ T (x, y)) ;

	Solve h * t as the solution of the weighted multi-class classification problem with ;
	inputs: (x i ) 1≤i≤N ;
	weights: (w t-1 (x i )) 1≤i≤N ;
	outputs: (y i ) 1≤i≤N ;
	t = αt = ln 1-t N i=1 w t-1 (x i )I {y i =h * t (x i )} ; t + ln(K -1) ;
	Update the distribution w, for all 1 ≤ i ≤ N ;
	wt(x i ) =	w t-1 (x i )e N j=1 w t-1 (x j )e α t I {y i =h * t	(x i )}

α t I {y j =h * t (x j )} ; Update the score function ; ψt(x, y) = ψ t-1 (x, y) + αtI {h * t (x)=y} ;

Table 1

 1 Benchmark data sets.

	Data set	# train # test # features # classes
	dna	2000	1186	180	3
	letter	15000	5000	16	26
	mnist	60000	10000	784	10
	pendigits	7494	3498	16	10
	satimage	4435	2000	36	6
	segment	210	2100	19	10
	splice	1000	2175	60	2
	vowel	528	462	10	11

Table 2

 2 Test error (%) rates on considered data sets.

			T = 10	T = 100 T = 1000
	dna	AdaBoost.MH	5.14	3.96	4.05
		SAMME	6.15	4.64	4.46
		sm-boost	6.49	4.89	4.13
	letter	AdaBoost.MH	15.0	3.72	2.34
		SAMME	13.0	3.68	2.84
		sm-boost	26.9	10.7	5.40
	mnist	AdaBoost.MH	12.7	4.14	1.76
		SAMME	10.8	3.72	2.52
		sm-boost	14.0	7.12	3.56
	pendigits AdaBoost.MH	4.86	2.43	2.17
		SAMME	3.03	2.49	2.29
		sm-boost	8.23	4.57	2.83
	satimage	AdaBoost.MH	13.0	10.0	9.20
		SAMME	13.7	9.85	8.8
		sm-boost	12.9	10.8	8.95
	segment	AdaBoost.MH	5.90	6.00	6.38
		SAMME	10.86	10.86	10.86
		sm-boost	9.19	6.95	6.19
	splice	AdaBoost.MH	2.94	2.71	2.53
		SAMME	5.75	3.17	2.71
		sm-boost	4.64	3.63	3.08
	vowel	AdaBoost.MH	49.4	44.6	42.9
		SAMME	47.8	39.4	38.3
		sm-boost	56.9	45.7	46.3

Table 3

 3 Test error (%) rates on considered data sets with corrupted labels (20% of samples have randomly exchanged labels). In parentheses we recall the noiseless results of Table2.

			T = 10	T = 100	T = 1000
	dna	AdaBoost.MH	8.26 (5.14)	7.67 (3.96)	7.25 (4.05)
		SAMME	13.8 (6.15)	10.5 (4.64)	8.85 (4.46)
		sm-boost	6.15 (6.49)	4.64 (4.89)	6.24 (4.13)
	letter	AdaBoost.MH	26.2 (15.0)	15.1 (3.72)	8.58 (2.34)
		SAMME	25.8 (13.0)	11.6 (3.68)	6.84 (2.84)
		sm-boost	29.2 (26.9)	13.2 (10.7)	6.98 (5.40)
	mnist	AdaBoost.MH	19.8 (12.7)	11.5 (4.14)	7.01 (1.76)
		SAMME	17.4 (10.8)	12.1 (3.72)	5.48 (2.52)
		sm-boost	14.1 (14.0)	6.96 (7.12)	3.78 (3.56)
	pendigits AdaBoost.MH	10.9 (4.86)	7.63 (2.43)	5.77 (2.17)
		SAMME	11.7 (3.03)	6.66 (2.49)	4.49 (2.29)
		sm-boost	9.06 (8.23)	3.97 (4.57)	3.06 (2.83)
	satimage	AdaBoost.MH	16.7 (13.0)	12.8 (10.0)	10.9 (9.20)
		SAMME	17.3 (13.7)	12.9 (9.85)	10.7 (8.8)
		sm-boost	13.8 (12.9)	11.8 (10.8)	10.4 (8.95)
	segment	AdaBoost.MH	15.6 (5.90)	13.8 (6.00)	13.9 (6.38)
		SAMME	17.0 (10.86) 14.0 (10.86) 13.0 (10.86)
		sm-boost	15.9 (9.19)	12.4 (6.95)	12.0 (6.19)
	splice	AdaBoost.MH	16.9 (2.94)	16.7 (2.71)	14.9 (2.53)
		SAMME	18.3 (5.75)	17.2 (3.17)	14.3 (2.71)
		sm-boost	9.15 (4.64)	10.7 (3.63)	13.1 (3.08)
	vowel	AdaBoost.MH	55.8 (49.4)	47.2 (44.6)	47.6 (42.9)
		SAMME	54.1 (47.8)	44.6 (39.4)	41.3 (38.3)
		sm-boost	52.8 (56.9)	48.9 (45.7)	43.7 (46.3)

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/


Matthieu Geist
email: matthieu.geist@centralesupelec.fr

Γ-UCB

Keywords:

We consider the stochastic multi-armed bandit problem where rewards are distributed according to Gamma probability measures (unknown up to a lower bound on the form factor). To handle this problem, we propose an UCB-like strategy where indexes are multiplicative (sampled mean times a scaling factor). An upper-bound for the associated regret is provided and the proposed strategy is illustrated on some simple experiments.

Introduction

We consider the stochastic multi-armed bandit problem where rewards are distributed according to Gamma laws. A random variable X follows a Gamma law, X ∼ Γ(a, b) with a > 0 the form parameter and b > 0 the scale parameter, if its probability density function satisfies

f (x) = x a-1 e -x b Γ(a)b a I R + (x),
where Γ is the Gamma function and I the indicator function. This encompasses as special cases the exponential distribution (which is of interest in a bandit setting for cognitive radio [START_REF] Jouini | Contribution to learning and decision making under uncertainty for Cognitive Radio[END_REF]), the Erlang distribution or the (scaled) Chi-squared distribution. Therefore, studying stochastic bandits in this setting might be of interest.

A classical approach for stochastic bandits is the so-called UCB (Upper Confidence bound) strategy [START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF], derived from the [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] inequality. This idea is generalized with the (α,ψ)-UCB strategy, which assumes that the cumulant generating functions (associated to rewards) are bounded by a convex function ψ [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF]. We follow a similar path in this paper. However, we take advantage of the specific structure of the cumulant generating function of a Gamma distribution to introduce a multiplicative form of the Hoeffding inequality, and we take advantage of the fact that the left tail is lighter than the right tail, from which the Γ-UCB(α,a 0 ) strategy is derived.

The proposed approach is actually a (slight) generalization of the MUCB(α) (Multiplicative UCB) strategy of [START_REF] Jouini | Channel selection with Rayleigh fading: A multiarmed bandit framework[END_REF], that handles exponentially distributed rewards (this being a special case of Gamma rewards, with a form factor a = 1). For this (exponential) case, the KL-UCB (Kullbach-Leibler UCB) strategy [START_REF] Garivier | The KL-UCB algorithm for bounded stochastic bandits and beyond[END_REF] or Thompson sampling [START_REF] Korda | Thompson sampling for 1dimensional exponential family bandits[END_REF] could be applied too, as they can generally be adapted to the setting where the rewards belong to the one-parameter canonical exponential family. However, Gamma distributions with unknown shape parameter do not belong to this family, so extension to the case studied in this paper is not direct.

Γ-UCB(α,a 0 )

We consider the basic stochastic multi-armed bandit problem. Each arm i ∈ {1, . . . , K} is associated to a Gamma probability measure ν i , ν i ∼ Γ(a i , b i ). The coefficients a i and b i are unknown (otherwise, the means would be known), but we assume that a lower bound a 0 on the form factors is known: a 0 ≤ min 1≤i≤K a i . At each time step t = 1, 2, . . . , the player chooses an arm I t ∈ {1, . . . , K} (based on past choices and observations) and receives a reward X It,t drawn from ν It , independently from the past. We write µ i the expectation of arm i and define: µ * = max 1≤i≤k µ i and i * ∈ argmax 1≤i≤K µ i . The ideal (but unreachable) strategy would consist in choosing systematically I t = i * . Therefore, the quality of a strategy can be measured with the regret, defined as the cumulative difference (in expectation) between the optimal arm and chosen arms:

R n = nµ * -E[ n t=1 µ It ].
Write T i (s) = s t=1 I It=i the number of times the player selected arm i on the first s rounds and ∆ i = µ *µ i the suboptimality of arm i. The regret can be written equivalently as

R n = K i=1 ∆ i E[T i (n)].
Therefore, a good strategy should control E[T i (n)], the (expected) number of time a suboptimal arm is played. Write μi,s the sample mean of rewards obtained by pulling arm i for s times: μi,s = 1 s s t=1 X i,t . Let also α > 0 be an input parameter. At time t, the proposed Γ-UCB(α,a 0 ) selects

I t ∈ argmax 1≤i≤K μi,T i (t-1) 1 - 2α ln t a 0 T i (t-1) +
, where (•) + = max(•, 0) and with the convention 1 0 = ∞. With a 0 = 1 (the form factor of an exponential distribution), we retrieve the MUCB(α) strategy of [START_REF] Jouini | Channel selection with Rayleigh fading: A multiarmed bandit framework[END_REF].

Regret

In this section, we study the regret encountered by the proposed strategy.

Theorem 1 (Regret bound for Γ-UCB(α,a 0 )) Define ρ i as the ratio between expectations of arms i and i * :

ρ i = µ i µ * .
For ρ ∈ (0, 1), define the function g as

g(ρ) = 3ρ + 1 -(ρ + 1) 1 + 4ρ -ρ 2 ρ 2 . ( 1
)
Assume that a 0 ≤ min 1≤i≤K a i and that α > 2. Then, the Γ-UCB(α,a 0 ) satisfies

R n ≤ µ * i:ρ i <1 α(1 -ρ i ) a 0 g(ρ i ) ln n + α(1 -ρ i ) α -2 .
To prove this, we will need a multiplicative Hoeffding bound for Gamma random variables.

Lemma 2 (A multiplicative bound for the Gamma case) Let X 1 , . . . , X n be i.i.d. (independent and identically distributed) random variables such that for all i, X i ∼ Γ(a, b). Let a 0 ≤ a. Write µ = E[X 1 ] the common expectation and µ n =1 n n i=1 X i the sample mean. Then, for any δ ∈ (0, 1), we have

P µ n (1 -) + < µ ≤ δ with = 2 ln 1 δ a 0 n and P µ n 1 + > µ ≤ δ with = 2 ln 1 δ a 0 n + ln 1 δ a 0 n .
Proof We start by studying the cumulant generating function of a Gamma random variable 1 , before applying a standard Chernoff argument. Let X ∼ Γ(a, b). The cumulant generative function of the centered random variable Xµ satisfies:

∀λ < 1 b , L X-µ (λ) = ln E[e λ(X-µ) ] = -a(ln(1 -λb) + λb) ≤ λ 2 ab 2 2(1 -λb) . (2)
In other words, Xµ is sub-gamma on the right tail with variance factor ab 2 and with scale factor b. As X is Gamma, its expectation satisfies µ = E[X] = ab. Therefore, we have

∀λ < 1 b , L X-µ ( λ µ ) ≤ 1 a λ 2 2(1 -λ a ) ≤ 1 a 0 λ 2 2(1 -λ a 0 ) . = ψ(λ). (3)
On the other hand, Xµ is sub-gaussian on the left tail with variance factor ab 2 :

∀λ > 0, L µ-X (λ) = ln E[e λ(µ-X) ] = -a(ln(1 + λb) -λb) ≤ λ 2 ab 2 2 .
Given that µ = ab, we have

∀λ > 0, L µ-X ( λ µ ) ≤ 1 a λ 2 2 ≤ 1 a 0 λ 2 2 . = ϕ(λ). (4)
We can now provide the desired bounds using a standard Chernoff argument. For the second one, we have for any 0 < λ < 1 b :

P ( µ n -µ µ > ) = P (e λ n i=1 X i -µ µ > e λn ) ≤ e -λn E[e λ n i=1 X i -µ µ ] (by the Markov's inequality) = e -λn E[e λ X 1 -µ µ ] n (by the i.i.d. assumption) = e -n(λ -L X 1 -µ ( λ µ )
) ≤ e -n(λ -ψ(λ)) (by Eq. ( 3)).

Write ψ * ( ) the Legendre-Fenchel transform of ψ,

ψ * ( ) = sup 0<λ< 1 b (λ -ψ(λ)) = a 0 1 + - √ 1 + 2 .
We therefore have:

P ( µ n -µ µ > ) = P ( µ n 1 + > µ) ≤ e -nψ * ( ) .
Writing δ = e -nψ * ( ) and using the fact that for x > 0,

ψ -1 * (x) = 2x a 0 + x a 0 , we get P µ n 1 + ψ -1 * ( 1 n ln 1 δ ) > µ ≤ δ,
which is the stated second bound.

For the first bound, the proof is similar. We have with the same Chernoff argument:

P ( µ -µ n µ > ) ≤ e -nϕ * ( ) ,
where ϕ * ( ) is the Fenchel-Legendre transform of ϕ(λ), the upper-bound of the cumulant generating function (on the left tail) defined in Eq. ( 4):

ϕ * ( ) = sup λ>0 (λ -ϕ(λ)) = a 0 2 2 .
On the other hand, ( ) . Therefore:

P ( µ-µn µ > ) = P (µ n < µ(1 -)). If 1 -< 0, then P (µ n < µ(1 -)) = P (µ n < 0) = 0 ≤ e -nϕ *
P (µ n < µ(1 -) + ) = P ( µ n (1 -) + < µ) ≤ e -nϕ * ( ) .
Writing δ = e -nϕ * ( ) and using the fact that ϕ -1 * (x) = 2x a 0 , we get the first stated bound:

P µ n 1 -ϕ -1 * ( 1 n ln 1 δ ) + > µ ≤ δ.
The first bound of Lemma 2 states that with probability at least 1δ, we have

µ n 1 - 2 ln 1 δ a 0 n + > µ,
which is the proposed strategy with δ = t -α (optimism in the face of uncertainty based on the upper confidence bound given by Lemma 2). We can now prove the main theorem.

Proof [Theorem 1] To bound the regret R n , we will bound the quantity E[T i (n)]. Assume without loss of generality that I t = i = i * . At least one of the tree following inequalities must be true : μi * ,T i * (t-1)

1 -

2α ln t a 0 T i * (t-1) + ≤ µ * (5) µ i,T i (t-1) 1 + 2α ln t a 0 T i (t-1) + α ln t a 0 T i (t-1) > µ i (6) T i (t -1) < α ln t a 0 g(ρ i ) , (7)
with g defined in Eq. ( 1). Actually, if all equations were false, we would have μi * ,T i * (t-1)

1 -

2α ln t a 0 T i * (t-1) + > µ * (by (5) false) = µ i ρ i (by definition) > µ i 1 + 2α ln t a 0 T i (t-1) + α ln t a 0 T i (t-1) 1 - 2α ln t a 0 T i (t-1) + (by (7) false) ≥ µ i,T i (t-1) 1 - 2α ln t a 0 T i (t-1) + (by (6) false).
This would mean that I t = i * = i, which is a contradiction. Now, define u as u = α ln n a 0 g(ρ i ) .

We have that

E[T i (n)] = E[ n t=1 I It=i ] ≤ u + n t=u+1
I It=i and ( 7) is false

≤ u + n t=u+1 I (5) or (6) is true ≤ u + n t=u+1
(P ((5) is true) + P ((6) is true)) .

Thus, we have to bound the probabilities of events ( 5) and ( 6), which can be done thanks to Lemma 2. Indeed:

P ((5) is true) = P   ∃s ≤ t : μi * ,s 1 -2α ln t a 0 s + < µ *    ≤ t s=1 P    μi * ,s 1 -2α ln t a 0 s + < µ *    ≤ t s=1 1 t α = 1 t α-1 .
Similarly, one can show that:

P ((6) is true) ≤ 1 t α-1 .
Therefore, we can bound the number of time arm i has been played:

E[T i (n)] ≤ u + 2 n t=u+1 1 t α-1 ≤ α ln n a 0 g(ρ i ) + 1 + ∞ 1 2dt t α-1 = α ln n a 0 g(ρ i ) + α α -2 . KL-UCB MUCB(α > 4) (α > 1,ψ)-UCB Γ-UCB(α > 1,1) lim n→∞ Rn µ * ln n i:ρ i <1 1-ρ i ρ i -1-ln ρ i i:ρ i <1 4α 1-ρ i i:ρ i <1 α(1-ρ i ) h(ρ i ) i:ρ i <1 α(1-ρ i ) g(ρ i )
Table 1: Comparison of bounds (exponential rewards).

Using the fact that

R n = K i=1 ∆ i E[T i (n)] and that ∆ i = µ * (1 -ρ i )
, we obtain the desired bound:

R n ≤ µ * i:ρ i <1 α(1 -ρ i ) a 0 g(ρ i ) ln n + α(1 -ρ i ) α -2 .
This proof is very similar to the one of (α,ψ)-UCB (Bubeck and Cesa-Bianchi, 2012, Ch. 2). The difference is that we consider different convex bounding functions on the left and right tail (regarding the cumulant generating function) and we use a multiplicative concentration inequality instead of an additive one.

Remark 3 (About the constant α) We have kept the proof simple. However, using a peeling argument instead of a simple union bound (as done by [START_REF] Bubeck | Bandits Games and Clustering Foundations[END_REF] for UCB) for bounding the probabilities of events (5) and (6) in the preceding proof should give the same result for any α > 1 (instead of α > 2, and with a different constant term).

Discussion

As far as we know, the sole alternative to Γ-UCB in the studied case is (α,ψ)-UCB (Bubeck and Cesa-Bianchi, 2012, Ch. 2), that we instantiate now for Gamma rewards. Recall the bound (2) on the cumulant generating function of a centered Gamma reward. We assume that upper-bounds on the two parameters are known: a ∞ ≥ max 1≤i≤K a i and b ∞ ≥ max 1≤i≤k b i . A convex function bounding cumulant generating functions of all rewards (on both the left and right tails) is

ψ(λ) = λ 2 a ∞ b 2 ∞ 2(1 -λb ∞ ) .
The associated Legendre-Fenchel transform and its inverse are

ψ * ( ) = a ∞ 1 + a ∞ b ∞ -1 + 2 a ∞ b ∞ and ψ -1 * (x) = b ∞ (x + √ 2a ∞ x).
The (α,ψ)-UCB is therefore For any α > 2 (α > 1 being possible, see remark 3), its regret satisfies

I t ∈ argmax 1≤i≤K μi,T i (t-1) + b ∞ α ln t T i (t -1) + 2αa ∞ ln t T i (t -1) . 0.0 0.2 0.4 0.6 0.8 1.0 ρ 10 -1 10 0 10 1 10 2 10 3 10 4 10 5 10 6 1-ρ ρ-1-ln ρ (KL-UCB) 16 1-ρ (MUCB) 1-ρ h(ρ) (ψ-UCB) (1-ρ) g(ρ) (Γ-UCB)
R n ≤ i:∆ i >0    α∆ i a ∞ 1 + ∆ i 2a∞b∞ -1 + ∆ i a∞b∞ ln n + α∆ i α -2    .
More strategies deal with the exponential case (that is, Gamma case with a = 1) such as KL-UCB [START_REF] Garivier | The KL-UCB algorithm for bounded stochastic bandits and beyond[END_REF] with a proper divergence or MUCB [START_REF] Jouini | Channel selection with Rayleigh fading: A multiarmed bandit framework[END_REF]. Therefore, we also compare our bound to their. More precisely, we compare their asymptotic rates in Table 1. For (α,ψ)-UCB, we take a ∞ = 1 and b ∞ = max 1≤i≤K b k = µ * (which is an optimistic setting, the largest mean is exactly known beforehand). In this case, the bound simplifies as

R n ≤ µ * i:ρ i <1 αρ i h(ρ i ) ln n + O(1) , with h(ρ) = 3 -ρ 2 -2 -ρ.
As comparing these analytical expressions is not straightforward, we plot on Fig. 1 (in log-scale) the main term of each bound, as a function of ρ, the ratio between expectations. One can see that KL-UCB provides the better bound. This is not a big surprise, as it matches the lower bound of [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF] [START_REF] Garivier | The KL-UCB algorithm for bounded stochastic bandits and beyond[END_REF]. Γ-UCB has a slightly better bound than MUCB (which is a consequence of the proof, as both strategies are identical for exponential rewards) and (α,ψ)-UCB. We also compare the ratio of these terms on Fig. 2, to see how much better is KL-UCB. This shows that for large enough values of ρ, the regret of Γ-UCB is no more than four times the one of KL-UCB. Notice also that we considered the exponential case to ease the comparison, but Γ-UCB and (α,ψ)-UCB apply more generally to Gamma rewards.

Experiments

In this section, we consider stochastic bandits with exponential rewards. We compare the Γ-UCB(α,1) strategy (therefore, the MUCB strategy) to KL-UCB (with the divergence corresponding to exponential rewards) and (1,ψ)-UCB. For Γ-UCB, we consider two values of α: α = 1 (limit of the theory) and α = 0.5 (beyond). For (1,ψ)-UCB, we take a ∞ = 1, b ∞ = µ * (the most optimistic setting). We consider two experiments. In the first one, arms have expectations {1, 2, 3, 4, 5} (results are provided in Fig. 3). In the second one, arms have expectations {5, 5, 5.1, 5, 5} (results are provided in Fig. 4). This case is harder, as the ratio of expectations ρ is closer to one. Each provided result is averaged over 10 3 independent runs. KL-UCB has a smaller regret than Γ-UCB(1,1), which is better than (1,ψ)-UCB, as predicted in Sec. 3. However, on these experiments, Γ-UCB(0.5, 1) has a smaller regret. If general conclusions cannot be drawn (as this is beyond the theory), this might be a viable empirical alternative.

Conclusion

In this paper, we have proposed a multiplicative UCB strategy for Gamma rewards, extending the original MUCB idea of [START_REF] Jouini | Channel selection with Rayleigh fading: A multiarmed bandit framework[END_REF]. We have derived a regret bound, rather close to the one of KL-UCB in the exponential case. We also experimented the strategy on two simple bandit problems with exponential rewards. With an optimistic choice of the α parameter, Γ-UCB provides a lower regret than KL-UCB on these examples.

Compared to (α,ψ)-UCB (the sole alternative in the Gamma case, as far as we know), the proposed strategy requires a lower bound on the form factor instead of upper bounds on both the form and scale factors, and it provides a better regret, both theoretically and empirically (on the studied exponential cases).

An interesting perspective would be to study if such a multiplicative strategy could be of interest for other kind of distributions (which would depend on the structure of the related cumulant generating function).

Figure 1 :Figure 2 :

 12 Figure 1: Main term of each bound.

Figure 4 :

 4 Figure 3: Exponential rewards with means {1, 2, 3, 4, 5}.

This is largely inspired fromBoucheron et al. (2013, Ch. 2).