Christophe Denis

M Gilles Blanchard

Mme Béatrice

Mme Sara Van De Geer

M Antoine Chambaz

Mme Fabienne Comte

M Stéphane Gaïffas

Mme Adeline

Leclercq Samson

Some contributions to multi-class learning

Avant-propos

Ce mémoire d'habilitation est une synthèse de mon travail de recherche réalisé depuis l'obtention de mon poste de Maître de conférences à l'Université Gustave Eiffel en 2013. Ma recherche s'inscrit dans le domaine de l'apprentissage statistique. Plus particulièrement, elle s'articule autour de deux thématiques: l'apprentissage supervisé sous contrainte et l'apprentissage pour des données à dépendance temporelle.

Ce manuscrit présente mes contributions à l'apprentissage multi-classes. Il se décompose en quatre chapitres. Un premier chapitre est consacré à une introduction à la classification multi-classes et introduit les notions importantes. Ce chapitre est aussi l'occasion d'exposer les enjeux et motivations des résultats présentés dans ce manuscrit. Les deux chapitres suivants sont consacrés à l'exposé de résultats obtenus en apprentissage sous contrainte, tandis que le dernier chapitre traite de la classification pour des données trajectorielles.

Une partie importante de mes travaux de recherche porte sur la classification sous contrainte. Au sein de cette thématique, j'ai principalement exploré deux sujets de recherche. D'une part la classification supervisée par ensemble (set-valued classification) sous contrainte de taille, dont je présente les résultats obtenus en collaboration avec E. Chzhen (LMO) et M. Hebiri (LAMA) au Chapitre 2. D'autre part, je m'intéresse à l'apprentissage sous contrainte d'équité (fairness) qui est un sujet d'importance croissante au sein de la communauté de l'apprentissage statistique. Mes travaux portant sur l'équité algorithmique sont issues en grande partie d'une collaboration avec E. Chzhen, M. Hebiri, L. Oneto (DIBRIS, University of Genoa), et M. Pontil (Istituto Italiano di Tecnologia et Université College London). Les résultats issus de cette collaboration s'inscrivent dans le cadre de la régression et de la classification binaire. Une extension au cadre de la classification multi-classes est présentée au Chapitre 3. Ce travail est le fruit d'une collaboration avec R. Elie (DeepMind), M. Hebiri et F. Hue (ENSAE). L'un des points communs aux procédures décrites dans le Chapitre 2 et le Chapitre 3 est que les méthodes d'apprentissage proposées peuvent tirer parti d'un cadre d'observation semi-supervisé.

En apprentissage multi-classes l'objectif est de prédire à partir de l'observation d'une variable X, dite covariable, sa classe d'appartenance Y (ou étiquette). L'apprentissage multi-classes est une thématique qui a été très étudiée au cours des deux dernières décénies, son potentiel applicatif irriguant toutes les branches de notre société. Due à CONTENTS leur complexité croissante, de nombreux jeux de données multi-classes présentent une forte ambiguité; différentes étiquettes pouvant alors correspondre à la covariable X observée. Ce type de difficulté est notamment rencontré dans les problèmes d'annotation d'image comme pour la base de données PlantNet (voir [START_REF] Göeau | LifeCLEF plant identification task 2015[END_REF]. Dans ces situations, l'approche classique qui consiste à ne prédire qu'au moyen d'une seule classe, n'est plus adaptée. En effet, prédire une seule étiquette parmi une grande liste de candidates peut s'avérer très peu informatif. Dans ce cas, une alternative est de considérer la classification par ensemble. C'est-à-dire que l'on va prédire une liste de classes candidates plutôt qu'une unique classe. Le Chapitre 2 présente mes contributions à cette thématique de recherche.

L'apprentissage sous contrainte d'équité (fairness) est un sujet de plus en plus prégnant dans les applications de l'apprentissage statistique. En effet, l'objectif de la fairness est de "corriger" le biais dans les données observées afin que les algorithmes d'apprentissage répondent à des contraintes éthiques. Une des idées sous-jacente est qu'un algorithme d'apprentissage ne doit pas être discriminant vis-vis d'une variable dite sensible tel que le genre ou l'ethnie. L'étude de la fairness s'inscrit ainsi au coeur des débats qui animent actuellement nos sociétés modernes. L'objectif du statisticien étant de comprendre les mécanismes pouvant induire ces biais. Le Chapitre 3 résume une contribution à ce problème dans le cadre de l'apprentissage multi-classes.

La classification de données à dépendance temporelle est un domaine important de recherche en Statistique, les récentes avancées technologiques (notament l'utilisation de capteurs) rendant très facile la collecte de ce type de données. Une partie de mon travail de recherche s'inscrit dans ce cadre. Durant ma thèse, j'ai travaillé sur la mise en place de méthodes de classification pour des données de maintien postural. Les troubles du maintien postural sont susceptibles d'entraîner une chute qui est l'une des premières causes de mortalité chez les personnes âgées. Les objectifs à plus long terme sont la mise au point de protocoles d'identification de troubles du maintien postural et l'adaptation au cas par cas des protocoles de rééducation fonctionnelle. L'une des spécificités de ce travail est l'exploitation d'une modélisation des données trajectorielles comme solutions d'équations différentielles stochastiques.

Une des perspectives soulevée par ces travaux de thèse a été l'étude d'un point de vue théorique et méthodologique de procédures de classification dans le cas où les variables explicatives sont solutions d'une équation différentielle stochastique. Au Chapitre 4, je présente les contributions obtenues en collaboration avec C. Dion-Blanc (LPSM) et M. Martinez (LAMA) et apportant une réponse à ce problème. Les résultats ont été obtenus pour des trajectoires unidimensionnelles et dans un cadre d'estimation paramétrique. Ce travail a ouvert de nombreuses perspectives de recherche. En particulier, la question de l'extension de ces résultats au cadre non-paramétrique et pour des trajectoires multidimensionnelles fait partie d'un projet de recherche actuellement en cours. Les premiers résultats obtenus dans cette direction sont également présentés au Chapitre 4 et la suite du projet est l'objet du travail de thèse d'Eddy Ella-Mintsa (LAMA) que je co-encadre avec C. Dion-Blanc et V.C. Tran (LAMA).

Chapter 1

Introduction to multi-class classification problem

Multi-class classification is one of the most studied statistical frameworks, arising in many fields which range from medical applications to social studies (e.g., medical diagnosis, image recognition, text categorization to name a few). For a general introduction to this topic, we refer for instance to the well-established book by [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]. This chapter is dedicated to the presentation of main notions which are at the core of this manuscript. In particular, we introduce the general multi-class classification framework in Section 1.1. In Section 1.2, we sketch the main estimation techniques in multi-class classification. Section 1.3 introduces mixture models which are widely used to model multi-class classification problems. Finally, in Section 1.4 we present some modern challenges that are addressed in this manuscript.

General framework

In multi-class classification, a generic observation is a pair of random variables (X, Y) such that the feature vector X belongs to some space X and the label Y takes its values in Y = {1, . . . , K}, with K ≥ 2, and indicates the associated class to X. The distribution of (X, Y), denoted by P, is assumed to be unknown to the statistician. In this setting, a classifier g is a measurable function which maps X onto Y. Hence, a classifier is viewed as a prediction of the associated label Y. Throughout this manuscript, for a given classifier g, we consider the misclassification risk R(g) = P(g(X) = Y) as the measure of the performance of a classifier g. The set of all classifiers is denoted by G. Note that we often refer to multi-class (or multi-category) classification when K ≥ 3. The specific case when K = 2 refers to the binary classification setting and is the most studied classification problem in the machine learning community. We distinguish this case from the general multi-class classification framework where K ≥ 3 even though these two problems share some similarities in nature. However, important technical differences also exist making the multi-class setting as a case study per se. We will discuss this point later.

Bayes classifier

At this step, a natural object to consider is a classifier g * which achieves the minimum risk g * ∈ arg min g∈G R(g).

(1.1)

An elementary, yet important result in classification context is the characterization of the optimal rule g * , namely the Bayes classifier , expressed for all x ∈ X as g * (x) ∈ arg max k∈Y p k (x), with p k (x) = P(Y = k|X = x).

Clearly, since the distribution of (X, Y) is unknown, we do not have access to the Bayes classifier. Hence, an objective in multi-class classification is to build, based on a learning sample, an empirical classifier which mimics the Bayes classifier.

In view of the form of the optimal classifier, it is worth noting that the conditional probabilities p k will play a central role in the estimation of g * . If we consider the binary case (K = 2, and Y = {0, 1}) the Bayes classifier can also be expressed simply as a thresholding of the conditional probability p 1 g * (x) = 1 {p 1 (x)≥1/2} . This is in fact a specificity of the binary classification that eases the statistical analysis in this framework. This property does not hold in the multi-class setting and makes a major difference between the two settings.

As we have seen above, the optimal classifier achieves the minimum risk. Therefore, it is natural that the performance of a given classifier g is evaluated through its excess risk which is defined as E (g) = R(g) -R(g * ).

In particular, we can show a closed form of this excess risk.

Proposition 1.1. For any g ∈ G, the following holds

E (g) = E X K ∑ k=1 ∑ j =k
|p k (X)p j (X)|1 {g(X)=j, g * (X)=k} .

Interestingly, the above expression of the excess risk in the multi-class setting is a straightforward but important generalization of the binary case which can be written as

E (g) = E X |2p 1 (X) -1|1 {g * (X) =g(X)} .
Next step consists in building an estimator of Bayes classifier and provides some theoretical insights, such as a control of its excess risk. This is the purpose of the following section. In particular, Section 1.2 can be viewed as a road-map for the study of classification procedures in multi-class framework.

Estimation strategy

In multi-class classification, the construction of a classification procedure relies on a learning sample D n = {(X i , Y i ), i = 1, . . . , n} of i.i.d. copies of (X, Y). Hence, a classification procedure or an empirical classifier is a measurable (classifier-valued) function of the learning sample D n . Following the standard practice, we will often use the general notation ĝ to denote an empirical classifier and drop the explicit dependency on the learning sample. The excess risk of a empirical classifier ĝ is then a random variable (or, rather a random element, since ĝ is classifier-valued, but we omit this benign distinction) that depends on D n . One basic and fundamental property that we expect from a good empirical classifier ĝ is its point-wise consistency w.r.t. some class P of joint distributions P of (X, Y) lim n→+∞ E [E ( ĝ)] = 0, for P ∈ P, which ensures that the classifier ĝ is asymptotically as good as the Bayes classifier (note that at this stage we are not aiming at characterizing rates of convergence, since the above guarantee is not sufficient for this purpose). In principle, there are two main ways to build a consistent classifier, both of which are relying on the definition and the characterization of the Bayes classifier. The first strategy involves the estimation of the conditional probabilities and relies on the plug-in principle. The second one takes advantage of Equation (1.1) and relies on the empirical risk minimization principle.

Plug-in approach

Provided the characterization of the Bayes classifier, the most intuitive way to build consistent classification procedures relies on the construction of consistent estimators of the conditional probabilities p k for all k ∈ {1, . . . , K}. More precisely, the first step consists in building estimators pk of the p k 's based on the sample D n . We do not focus on this step which is rather well studied (van de [START_REF] Van De Geer | Martingale estimation functions for discretely observed diffusion processes[END_REF][START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]Wegkamp and van de Geer, 1996;Tsybakov, 2009a); let us, however, mention that standard estimation methods can be used for this task such as the Kernel estimators or the k-Nearest Neighbor estimators (see Devroye, Györfi, and Lugosi, 1996, for instance).

Then, the empirical classifier is defined for all x ∈ X by ĝ(x) ∈ arg max k∈Y pk (x).

This approach is motivated by the following result, which links the classification excess risk to its regression counterpart.

Proposition 1.2. We have that

E [E ( ĝ)] ≤ 2E K ∑ k=1 | pk (X) -p k (X)| .
The above proposition ensures that the consistency of the pk 's implies the consistency of the plug-in classifier ĝ. Furthermore, one can also note that rates of convergence for the excess risk can trivially be deduced from the rates of convergence of the estimators pk w.r.t. the L 1 -norm. Importantly, the properties of the plug-in classifier ĝ are inherited from the properties of the estimators pk . We refer to [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF][START_REF] Yang | Minimax nonparametric classification: Rates of convergence[END_REF][START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]Tsybakov, 2009a) for more details.

Empirical risk minimization procedure

In this section, we describe another way to build consistent empirical classifiers. It relies on the empirical risk minimization principle which has been widely studied in the context of supervised learning.

Consider a set of classifiers G ⊂ G, we define the empirical risk of a given classifier

g ∈ G by R(g) = 1 n n ∑ i=1 1 {g(X i ) =Y i } ,
and we naturally set the empirical risk minimizer (E.R.M.) ĝ over the set G

ĝ ∈ arg min g∈G R(g).
From the definition of ĝ, we deduce that

E [E ( ĝ)] = E [R( ĝ) -R( ḡ)] + E [R( ḡ) -R(g * )] ,
where ḡ ∈ arg min G R(g). Hence, the excess risk of the empirical risk minimizer is classically decomposed into two terms. The first one is the variance term which is usually studied using tools from the empirical process theory and depends on complexity assumptions imposed on the set G . In particular, assumptions on the entropy of the set G are considered [START_REF] Van De Geer | Empirical Processes in M-Estimation[END_REF]. The second one is the bias term and also depends on the complexity assumptions on G and on the assumptions on the joint distribution of (X, Y). In this case, the properties of ĝ are inherited from the properties of G . We refer to [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]Vapnik, 1998;[START_REF] Massart | Risk bounds for statistical learning[END_REF] for the statistical property of the E.R.M. estimator. Nevertheless, due to the non-convexity of the minimization problem defined by Equation (1.2.2), the estimator ĝ is in general not computable. Although, the E.R.M. ĝ offers appealing properties, it cannot be considered in this form for practical purposes. To avoid this issue, convex surrogates have been provided in the statistical literature. In particular, we refer to the work by [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF], Vapnik (1998), [START_REF] Friedman | Additive logistic regression: a statistical view of boosting[END_REF], [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF], [START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF], [START_REF] Tewari | On the consistency of multiclass classification methods[END_REF], and [START_REF] Yuan | Classification methods with reject option based on convex risk minimization[END_REF] for a complete study. Hereafter, we present the convexification of the problem (1.2.2) in the case of the square loss with the one-versus-all approach [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF]. We consider this case for simplicity but also to highlight the link between classification and regression. Of course, other choices of loss functions can be considered and we refer to [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF][START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF] for more details.

Convexification: from regression to classification.

A particular feature of convexification is that it relies on a score function

f(•) = ( f 1 (•), . . . , f K (•))
, that is, a measurable mapping from X to R K . Each of these score functions results in an associated classifier g f defined as

g f (x) ∈ arg max k∈Y f k (x).
Even though, the score function is not well tailored for the classification task (it does not take values in a discrete set) we can, nevertheless, consider its L 2 -risk as

R 2 (f) = E K ∑ k=1 (Z k -f k (X)) 2 , with Z k = 2 • 1 {Y=k} -1.
Hence, the risk R 2 is simply the sum over all k ∈ Y of the L 2 -risks associated to the regression problems of Z k onto X. Interestingly, this formulation can be viewed as the generalization of the regression problems associated to K separate binary classification problems where for each k ∈ Y, we focus on the classification problem Y = k against Y = k. From this perspective, we can see this formulation as a one-versus-all problem.

Here again, we can define the optimal score function f

* w.r.t. R 2 f * ∈ arg min f R 2 (f), (1.2)
where the infimum is taken over all measurable functions. Hence, for each k ∈ Y, we have that

f * k (X) = E [Z k |X] = 2p k (X) -1.
From the definition of f * , one can establish Zhang's Lemma (see [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF]) which connects the regression problem defined by Equation (1.2) to the multi-class problem.

Lemma 1.1. Let f a score function, then the following holds

E [R(g f ) -R(g * )] ≤ 1 √ 2 (E [R 2 (f) -R 2 (f * )]) 1/2 .
The immediate consequence of this result is that the properties of the classifier g f can be studied through the properties of the score function f. In view of this result, it is then natural to consider empirical risk minimizer estimator w.r.t. L 2 -risk. More precisely, we define for a given score function f its empirical risk

R2 (f) = 1 n n ∑ i=1 K ∑ k=1 ( f k (X i ) -Z i k ) 2 , where Z i k = 2 • 1 {Y i =k} -1.
Therefore for a set F of score functions, the empirical risk minimizer f is then defined as

f ∈ arg min f∈F R2 (f).
Theoretical guarantees of f are then obtained through complexity assumptions imposed on the set F . Note that, the resulting estimator f can be also interpreted as a plugin classifier. Indeed, in view of the form the optimal score function f * , estimators of conditional probabilities may be simply deduced by setting pk = fk +1 2 .

The case of the mixture model

In Section 1.2, we provide a high-level description of general methods to estimate the Bayes classifier. Of course, the theoretical properties of these procedures depend on the assumption on the joint distribution of (X, Y). In this section, we consider the particular case where the distribution of (X, Y) comes from a mixture model. For simplicity, we assume that X = R d and present the mixture model for multi-class classification in the parametric setting.

Let Θ ⊂ R p . We assume that Y is distributed according to (π k ) k∈Y . Conditional on Y = k, we assume that X admits a density

f θ k (•) = f (θ k , •) w.r.t. the Lebesgue measure.
Note that the function f is supposed to be known while for each k the parameter θ k is unknown. In this case, the marginal density of X is given for all x ∈ R d by

f X (x) = K ∑ k=1 π k f θ k (x).
Hence, under this parametric assumption, the classes are simply discriminated by the parameters (θ k ) k∈Y . Thanks to the Bayes formula, we easily deduced that

p k (x) = π k f θ k (x) f X (x) 1 { f X (x) =0} .
In other words, in the considered parametric setting, the Bayes classifier is known up to the parameter (θ k ) k and the marginal distribution of the label. Even though restrictive, such a modelling can be appealing from the computational and statistical perspectives, leading to faster algorithms and better statistical rates. Indeed, the distribution of Y can be estimated by the empirical frequencies πk while estimator θk of parameter θ k can be obtained by standard parametric methods, which are typically reduced to convex optimization problems. Naturally, given estimators πk and θk , we consider the plug-in classifier ĝ defined by

pk (x) = πk f θk (x) fX (x) 1 { fX (x) =0} .
Apart from their appealing computational and statistical properties, mixture models and the described methodology results in classifiers which are easily interpretable, which should be contrasted with general "black box" algorithms (e.g. neural networks). It goes without saying that the numerical performance of this estimation procedure strongly depends on the considered model and requires an important modeling effort.

Overview of the results

In the last decade, several challenges have emerged in multi-class classification. In particular, modern multi-class datasets are often heterogeneous, complex, and also large scale, leading to multi-class datasets which may involve a large number of observations, of variables, and/or of classes. In the present manuscript, we will try to address some of these characteristics providing a specific answer adapted to the problem in hand.

Due to the high ambiguity between classes inherent in large scale multi-class datasets, single-output algorithms often exhibit poor performance. As an illustration, the error rate of state-of-the art methods is around 20% on the ImageNet dataset [START_REF] Xie | Aggregated residual transformations for deep neural networks[END_REF]. In this context, we may question the relevance and value of single-output predictions. It is precisely within these high ambiguity problems that we benefit from the set-valued classification approach. Indeed, set-valued predictors, which allow to output a set of possible class candidates rather than an single class, are dedicated to handle the ambiguity in multi-class classification. In Chapter 2, we present a statistical analysis of plug-in and empirical risk minimization methods in the framework of set-valued classification with controlled expected size.

Mitigating bias in data is an active research field in the machine learning community. This is premised on the fact that learning algorithms may inherit bias in the data during the training process, leading to undesired knock-on effect on future decisions. In particular, severe conflicts may arise with ethical criteria of the modern society using algorithms that only have a purpose of prediction accuracy. Algorithmic fairness, which has been emerging in the last few years, try to give a solution to the problem of mitigating the bias in data. In Chapter 3, we provide results obtained in fairness in the context of multi-class classification.

The recent advance of modern technologies has generated a large number of datasets which can be modeled as functional data. In this context, a major challenge is to provide learning algorithms that are designed to handle temporal data. Many methods have been developed to treat such type of data (see [START_REF] Ramsay | Applied functional data analysis: methods and case studies[END_REF] for an overview). In Chapter 4, we present a contribution to this research area by considering the specific case where the feature is modeled as a diffusion sample path. More precisely, results provided in Chapter 4 focus on the multi-class problem where the data come from a solution of a mixture of stochastic differential equations, and can be viewed as an extension of the mixture model presented in Section 1.3 dedicated to functional data classification.

Chapter 2

Set-valued classification

In this chapter, I present results obtained for set-valued classification. This setting is motivated by the fact that modern multi-class datasets can be extremely ambiguous due to the large variety of label candidates. In this kind of situation, single-output classifier can lead to wrong and unsatisfactory predictions. In contrast, set-valued classifiers allow to predict multiple candidate labels and provide an alternative that may improve the prediction accuracy. In the set-valued classification framework, a predictor is allowed to predict not only a single label, but a set of candidates labels. Hence, it offers a natural way to work with the ambiguity.

Based on previously obtained results in (Denis and Hebiri, 2020) in the context of classification with reject option, we propose in [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF] the set-valued approach, where the size of the output (e.g. the number of the predicted labels) can be controlled in expectation by the practitioner. Up to our knowledge, that was the first work dealing with this framework at that time. We refer to this new setting as setvalued classification with control expected size. This approach shares some similarities with the top-k procedure which always outputs k candidate labels [START_REF] Lapin | Top-k multiclass SVM[END_REF]. In particular, by controlling the size of the output, both approaches ensures the interpretability of the output. However, in contrast to the top-k procedure, controlling the size in expectation of the predictor offers the opportunity of handling the heterogeneity of the feature space. That is to say, the size of the output is adaptive w.r.t. the marginal distribution of X.

In Section 2.3, we present a general procedure which is the result of several works. In particular, this procedure can leverage unlabeled data to satisfy the size constraint in expectation. We then show that consistent set-valued predictors under expected size constraint can be obtained in a semi-supervised way. Interestingly, the proposed methodology can be generalized to other learning problems under constraint. As an important development, we extend it to algorithmic fairness (Chzhen et al., 2020a,b). In [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF], we propose an empirical risk minimization procedure which is presented in Section 2.4. In light of this work, we propose in (Chzhen, Denis, and Hebiri, 2021) a minimax analysis of the set-valued classification with controlled expected size setting. Importantly, this work highlights the relevance of the semi-supervised approach in the set-valued classification framework. A part of these results are presented in Section 2.5.

General framework

In this section, we introduce main definitions and notations. A set-valued classifier Γ is a (measurable) function which maps X onto 2 Y . The set of all set-valued classifiers is denoted by Γ. Naturally, two parameters arise in this framework: the error rate and the (expected) size of a set-valued which are defined as

P (Γ) = P (Y / ∈ Γ(X)) error , S (Γ) = E |Γ(X)| size .
These two notions appear as fundamental and they have different names depending on the community and the field (for instance, the error rate is often called coverage, recall, or risk). The balance between the set size and the error rate is a common denominator between all set-valued classifiers, and depending on the application they should be considered in a different way. Hence different framework of set-valued classification are studied in the literature. In the following section we present the most considered set-valued settings and try to give some of their characteristics.

Set-valued approaches

Arguably the most natural set-valued classifier is the one that outputs a fixed amount of candidate labels for each instance. This type of set-valued classification strategies is called top-k prediction [START_REF] Lapin | Top-k multiclass SVM[END_REF][START_REF] Oh | Top-k hierarchical classification[END_REF], where k is the amount of candidate labels predicted. For an observation x, the optimal way to output k candidates is to select those that correspond to k highest conditional probabilities p 1 (x), . . . , p K (x). For instance, top-5 prediction is the one chosen for the ImageNet dataset [START_REF] Russakovsky | One-dimensional empirical measures, order statistics and Kantorovich transport distances[END_REF]. One of the advantage of this approach is that the interpretability of the output is controlled through the parameter k. Indeed, The top-k procedure is then defined as

Top-k: Γ * top(s) ∈ arg min P(Y / ∈ Γ(X)) : ∀x ∈ R d |Γ(x)| = s ,
with some s ∈ Y. One of the drawback of this approach is that it does not take into account inhomogeneous structure of the problem. Roughly speaking, there is no reason to always predict the same amount of labels all the time. As a remedy, we propose to replace the hard constraint on the size of the output by a constraint on the expected size.

More formally, for a given s ∈ (0, K), we consider the following constraint problem s-Oracle:

Γ * s ∈ arg min{P (Y ∈ Γ(X)) : E X |Γ(X)| ≤ s}. (2.1)
Interestingly, while this formulation generalizes the top-k approach, it also preserve its main characteristic. Indeed, since the parameter s ∈ (0, K) is fixed before hand, by considering this approach we also control the interpretability and stability of the outcome. Yet another way to define a set-valued classification framework is proposed by Vovk (2002a,b) and [START_REF] Vovk | Algorithmic learning in a random world[END_REF] and statistically addressed by [START_REF] Sadinle | Least ambiguous set-valued classifiers with bounded error levels[END_REF], where for a fixed α ∈ (0, 1), they define Γ * α as

Controlled error-rate:

Γ * α ∈ arg min {E|Γ(X)| : P(Y / ∈ Γ(X)) ≤ α} ,
that is, Γ * α is the "smallest" set-valued classifier with controlled probability of error. Even though this framework is intuitive, this apporach does not allow to control the size of the output. In certain situations it suffers from the lack of interpretability and the lack of stability w.r.t. the parameter α. In (Chzhen, Denis, and Hebiri, 2021;Chzhen et al., 2021), we illustrate this phenomena. Other approach based on the control of the point-wise error, P(Y / ∈ Γ(X)|X = x) are recently investigated in the literature [START_REF] Gyöfi | Nearest neighbor based conformal prediction[END_REF]Romano, Sesia, and Candès, 2020).

In the rest of this chapter, we present the results obtained in [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF]Chzhen, Denis, and Hebiri, 2021) for the statistical problem induced by Equation (2.1).

Set-valued classification with controlled expected size

Let s ∈ Y. This section establishes the important properties of the optimal set-valued predictor with controlled expected size Γ * s . We recall its definition here.

s-Oracle:

Γ * s ∈ arg min {P (Γ) : Γ ∈ Γ s.t. S(Γ) ≤ s} ,

Properties of s-Oracle.

Let us start by the following mild continuity assumption which is assumed throughout this chapter.

Assumption 1 (Continuity of CDF). For all k ∈ Y the cumulative distribution function (CDF) F p k (•) := P X (p k (X) ≤ •) of p k (X) is continuous on (0, 1).
Continuity Assumption 1 is central. It allows to express the s-Oracle set-valued classifier Γ * s in the form of thresholding and to highlight the relation of the constrained minimization with its unconstrained counterpart.

Proposition 2.1. Let the function G : [0, 1] → [0, K] be defined for all t ∈ [0, 1] as G(t) := K ∑ k=1 1 -F p k (t) = K ∑ k=1 P X (p k (X) > t) ,
then under Assumption 1, for s ∈ (0, K), the s-Oracle set-valued classifier Γ * s can be obtained for all x as

Γ * s (x) = k ∈ Y : p k (x) ≥ G -1 (s) , (2.2)
where we denote by G -1 the generalized inverse of G defined for all s ∈ (0, K) as G -1 (s

) := inf {t ∈ [0, 1] : G(t) ≤ s}.
Note that the threshold G -1 (s) depends on the joint distribution P and thus, is unknown beforehand. Furthermore, under Assumption 1, the considered framework is well posed in the sense that the s-Oracle set-valued classifier Γ * s is unique up to changes on sets of P X zero measure.

Theorem 2.1. For every s ∈ (0, K), under Assumption 1 the s-Oracle set-valued classifier Γ * s defined in Proposition 2.1 is unique up to changes on P X zero measure. That is, for all set-valued classifier such that S(Γ) ≤ s either of the following conditions hold

• P(Γ) > P(Γ * s ), • Γ(x) = Γ * s (x) for almost all x ∈ R d w.r.t. P X .
Under Assumption 1, we can also provide another characterization of the s-Oracle set-valued classifier. The next proposition establishes that s-Oracle can be obtained via an unconstrained minimization, which trades-off the error and the size. Proposition 2.2. Let s ∈ (0, K), and assume that Assumption 1 is fulfilled, then the s-Oracle defined in Equation (2.2) is a minimizer over Γ of the following risk

R s (Γ) = P(Γ) + G -1 (s) S(Γ) .
Consequently, the accuracy of a set-valued classifier Γ can be quantified according to its excess risk

R s (Γ) -R s (Γ * s ) = K ∑ k=1 E P X |p k (X) -G -1 (s)|1 {k∈Γ(X) Γ * s (X)} , ( 2.3)
One can already observe that the above excess risk of any set-valued classifier Γ relies on the behavior of the conditional probabilities p k around the threshold G -1 (s).

Measures of performance.

Let us conclude this section by introducing performance measures that we will study in the context of set-valued classification with controlled expected size. Of course, the objective is to measure the "distance" w.r.t. the oracle set-valued classifier. Let s ∈ (0, K) and Γ a set-valued classifier. The most intuitive measure of performance is the Hamming distance, which is a suitable way to quantify the distance between two sets. The Hamming risk of Γ is defined as

H (Γ) = E X [|Γ(X) Γ * s (X)|]
. Hence, since stands for the symmetric difference, we then have that H(Γ) ≥ 0 and that H(Γ) = 0 implies that Γ(x) = Γ * s (x) almost surely w.r.t. P X . In view of Proposition 2.2, another natural measure of performance is the excess risk R s (Γ) -R s (Γ * s ). Note that the excess risk is bounded by the Hamming risk, and consistency w.r.t. to the Hamming risk implies consistency w.r.t. the risk R s .

Plug-in set-valued classifier

In this section, we present a general data-driven procedure which relies on the plug-in principle. Let us point out that the feasible set {Γ ∈ Γ : S(Γ) ≤ s} of the above problem is distribution dependent. It implies that a priori we cannot decide whether a given set-valued classifier is feasible. However, this set only depends on the marginal distribution P X of the features, which motivates us to introduce unlabeled sample in the observational model. Hence, we are interested in the semi-supervised setup of this problem. That is, in what follows it is assumed that two independent samples are provided, a labeled one

D L n = {(X 1 , Y 1 ), . . . , (X n , Y n )} i.i.d.
∼ P and an unlabeled sample

D U N = {X n+1 , . . . , X n+N } i.i.d.
∼ P X both being independent from (X, Y). Based on the learning samples, the statistical goal is then to build an empirical setvalued classifier Γ :

(R d × Y ) n × (R d ) N → Γ, which mimics the behavior of Γ * s .
In particular one of the desired property of Γ is that the expected size of the empirical set-valued classifier satisfy the size constraint. However, as noticed above, since the constraint on the size depends on the marginal distribution P X , we relax this constraint and focus on empirical set-valued for which E S( Γ) → s.

Construction of the estimator

The expression of the optimal set-valued classifier provided Equation (2.2) naturally suggests a plug-in approach. The proposed procedure is two-step procedure. In a first step, based on the labeled sample, we build preliminary estimators pk of the posterior probabilities p k . In order to build the plug-in estimator, we consider for all t ∈ (0, 1)

G(t) = K ∑ k=1 P X ( pk (X) ≥ t|D n ) ,
and then consider the pseudo-oracle set valued classifier defined for all x ∈ X as

Γ(x) = {k ∈ Y, pk (x) ≥ G-1 (s)}.
Before to go further, it is important to note that, as for the s-Oracle classifier, the continuity of G is required. Assumption 2. For all k ∈ Y, conditionally on the data, the cumulative distribution function F pk (t) := P X ( pk (X) ≤ t) of pk (X) is continuous on (0, 1).

The above assumption is important since it ensures that

E S( Γ) = s.
A key point of our study is that it is always possible to ensure that this assumption is satisfied by introducing a random perturbation. Let (ζ 1 , . . . , ζ K ) be K i.i.d. random variables distributed according to a uniform distribution on [0, u] (u > 0) and independent from all other variables. For each k ∈ Y, we introduce the randomized estimator pk (X,

ζ k ) = pk (X) + ζ k , and Gu (t) = K ∑ k=1 P X,ζ k ( pk (X, ζ k ) ≥ t|D n ).
Then, the function Gu is continuous and the resulting randomized set-valued classifier satisfies the size constraint. Since the distribution of Gu depends on the distribution of X and (ζ k ) k∈Y , in a second step, based on the unlabeled dataset D U N and (ζ i k ) i.i.d. from a Uniform distribution on [0, u] and independent from all other random variable, we define its empirical counterpart for all t ∈ (0, 1)

Ĝu (t) = 1 N N ∑ i=1 K ∑ k=1 1 { pk (X n+i ,ζ i k )≥t} .
The resulting set-valued classifier is then defined as

Γu (X, ζ) = {k ∈ Y, pk (X, ζ k ) ≥ G-1 u (s)}.
Note that this approach is not explicitly presented in [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF]Chzhen, Denis, and Hebiri, 2021), but rigorous presentation of this construction can be found in [START_REF] Denis | Regression with reject option and application to kNN[END_REF] in the context of regression with reject option. Of course, if the size of the unlabeled N = 0, we simply split the labeled sample into two independent samples. Then, one sample is used to estimate the posterior probabilities while the second one is used to calibrate the threshold. Interestingly, the proposed procedure is general and we successfully extend this methodology to other learning problem under constraint (Chzhen et al., 2020b;[START_REF] Denis | Regression with reject option and application to kNN[END_REF]Denis et al., 2021). In particular, we show an application of this methodology in Chapter 3.

Theoretical properties

In this section, we establish the first properties of the plug-in set-valued classifier.

Universal expected size guarantee. The first result is a distribution-free result which shows that the set-valued classifier Γu meets, asymptotically, the expected size constraint. Theorem 2.2. Let s ∈ Y, and u > 0, there exists a universal constant such that for any distribution of (X, Y) and any estimators pk of p k , it holds that

E E ζ S( Γu ) -s ≤ C √ N .
Interestingly, this result highlights that the proposed post-processing procedure satisfies the expected size constraint up to a reminder term of order N -1/2 and an rely on any off-the-shell estimator of the posterior probabilities p k . Importantly, only unlabeled data are required to calibrate the threshold.

Consistency. We now establish, under mild assumptions, the consistency of Γu and then show that the proposed set-valued classifier mimics the oracle one both in term of error and expected size.

Theorem 2.3. Let s ∈ Y. Assume that u = u n → 0 and that for each k ∈ Y, we have E [| pk (X) -p k (X)] → 0. Under Assumption 1, it holds that lim n,N→+∞ E H Γu n = 0.
This result ensures that asymptotically Γu = Γ * s provided that the perturbation u is sufficiently small and that estimators pk are consistent w.r.t. to L 1 -risk. As an immediate consequence of the above result, we also have that Γu is consistent with respect to the risk R s . Note that we only establish the consistency of the plug-in set-valued classifier. In Section 2.5, we also show that plug-in classifier can achieve optimal rates of convergence.

Numerical evaluation

In this section, we illustrate the numerical properties of the plug-in set-valued classifier. One of our primary objectives is to provide experimental evidences that highlight the importance of the assumptions involved in our framework. In particular, we focus on Assumption 2 that is required from p1 , . . . , pK and moreover, in case N = 0, we highlight the importance of data splitting for construction of p1 , . . . , pK and estimation of G. To this end, we compare the performance of the set-valued classifier Γu against several natural alternatives: a) classifier that violates the continuity Assumption 2: exploits an estimator pk of the regression functions p k so that Assumption 2 is violated; b) classifier that violates the independence between samples D L n and D U N : uses the X i 's used for training the regression functions pk to also estimate G function. We consider the MNIST dataset (LeCun et al., 1998) which is composed of images of handwritten digits from 0 to 9. The goal is to predict which digit is present on the image. For the base estimator pk we select the random forest method [START_REF] Breiman | Random Forests[END_REF] which does not satisfy the continuity Assumption 2.

We fix u = 10 -6 for the construction of Γu (in the sequel, the dependency w.r.t. u is dropped) while we do not add the random perturbation when we evaluate the plug-in set-valued classifier in the case where Assumption 2 is not satisfied. Note that in the last case, the construction of the set-valued classifier is the same as Γu . We simply replace pk by pk .

Consequently, we compare the performance of the following set-valued classifier Γ+c that the error of the corresponding single-output classifier (random forest without the calibration step) is 0.140 and then the use of the set-valued classifier is relevant already for moderate values of the size as s = 2. In this case, P( Γ+c2 ) equals 0.014 -the error is 10 times lower.

Continuity of the estimator.

As it was mentioned in the beginning of this section, the random forest classifier does not satisfy Assumption 2. Our goal here is to understand the importance of this assumption. Figure 2.1-left-bottom demonstrates that in the absence of the continuity Assumption 2, the set-valued classifier Γ-c s (Not continuous) which does not modify p1 , . . . , pK has a systematic bias in terms of the size across a wide range of N. Meanwhile, Γ+c s (Continuous) successfully captures the prescribed size in average, see Figure 2.1-right. We also note that in both cases the variance of the outcome reduces with the growth of the unlabeled data N. Finally, we highlight that the error of Γ-c s is slightly lower than that of Γ+c s . However, this is attributed to the larger output size and not its superior performance.

Data splitting.

The second important conclusion we report deals with the relevance of the independence condition between the dataset used to estimate the regression functions and the dataset used to estimate the function G. (Without splitting) consistently over-estimates the size. By time, the expected size can even be twice as large as the desired size. In contrast, the size of the set-valued classifier Γ+sp s (With splitting) follows the diagonal line illustrating again that the proposed construction succeeds to satisfy the size constraint. According to the error, we can see from Figure 2.2-left that the set-valued classifier without splitting outperforms slightly the set-valued classifier with splitting. However, this should be tempered by the fact that the size of the former is larger. In addition this could be related to the fact that we used more data to estimate the p k 's for the method without splitting. Which sizes do we get? We end this section by a thiner description of the size of the set-valued classifier Γ+c s (Continuous). For a single outcome of the experiment we report on Figure 2.3 the distribution of the size of the set-valued classifier for s = 1, 2. One draw the following conclusion. First of all we note that setting s = 1 is not equivalent to the set-up of the single-output classification. Indeed, the plot on top-left of Figure 2.3 shows that even though most of the times the corresponding set-valued classifier outputs only one candidates, there are situations where no labels or two predicted label candidates are provided. Moreover, the error of Γ+c 1 (with s = 1) is 0.105, while the error of the corresponding single-output classifier (pure random forest without the second step) is 0.14. Hence, set-valued classifiers can improve the performance even in the case of s = 1. Besides, note that for values of s = 2 the corresponding set-valued classifier significantly improves the error, while having small size in average. Finally, we highlight how the setvalued classifier with the controlled expected size is different from the top-s procedure.

Empirical risk minimization for set-valued classification

In the previous section, we provide a general procedure to build set-valued classifier based on any estimators of the posterior probabilities. Furthermore, we have shown that from the numerical point of view, this method , which is easily implementable, exhibits good performance. Now, the question of the aggregation of set-valued classifier is then legitimate. This is one of the motivation of [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF]. In this work, we study set-valued classifier based on empirical risk minimization technique. Similarly to Section 1.2.2 in Chapter 1, due to the non convexity of the problem, we focus on convex surrogate of the initial problem that is tailored for the set-valued classification problem. In view of Equation (2.2), we propose a two-step procedure. In a first step we build, based on a proper convex loss, a vector f of score functions. In a second step, as for the plug-in procedure, we calibrate a threshold to satisfy the expected size constraint. Hence, the main question is which convex loss suits for set-valued classifier. Note that throughout this chapter, we assume that Assumption 1 is fulfilled.

Convexification of the initial problem

Let f = ( f 1 , . . . , f K ) : X → R K be a score function and G f (•) = ∑ K k=1 (1 -F f k (•))
, where F f k is the CDF of f k (X). Analogously to Assumption 1, let us assume the continuity of G f . This allows us to write that for any s ∈ (0, K), there exists δ ∈ R, such that G f (-δ) = s. The set-valued classifier Γ f,δ associated to f and δ is defined by

Γ f,δ (X) = {k ∈ Y : f k (X) ≥ -δ}.
The definition of parameter δ, implies that S (Γ f,δ ) = s. The excess risk formula provided in Equation ( 2.3) suggests the one-versus-all approach (see Section 1.2.2 in Chapter 1). For simplicity, we present the proposed method for the L 2 -risk. We refer to [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF] for a study of general loss functions.

We recall that for a score function f, its associated L 2 -risk is defined as

R 2 (f) = E K ∑ k=1 (Z k -f k (X)) 2 , with Z k = 2 1 {Y=k} -1, k = 1, . . . , K.
Let F a convex set of score function , we aim at solving

f ∈ arg min f∈F R 2 (f) optimal over F , f * ∈ arg min f R 2 (f) overall optimal
, for the purpose of building the optimal set-valued classifiers Γ¯f ,δ and Γ f * ,δ respectively.

The following result show that the square loss is set-valued calibrated [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF][START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF][START_REF] Yuan | Classification methods with reject option based on convex risk minimization[END_REF].

Proposition 2.1. Let s ∈ (0, K). There exists δ * ∈ R such that

Γ f * ,δ * = Γ * s ,
The property of calibration means that the set-valued classifier based on f * , the minimizer of the L 2 -risk, is the s-Oracle Γ * s . Roughly speaking, minimizing the Ł 2 -risk is the same as minimizing the risk R s .

Data-driven procedure

Recall that we have in hand a labeled D L n and an unlabeled D U N datasets. Similarly to the construction of plug-in set-valued classifier, the labeled dataset is used to build f the minimizer of the empirical L 2 -risk.

f ∈ arg min f∈F R2 (f) with R2 (f) = 1 n n ∑ i=1 K ∑ k=1 (Z i k -f k (X i )) 2 ,
where Z i k = 2 1 {Y i =k} -1 for all k = 1, . . . , K and F is a convex set of score functions. At this stage, we need to specify the δ > 0 such that S(Γ f,δ ) = s. For simplicity, we assume that the conditional distribution function of the score function fk are continuous. As in Section 2.3 this condition on the estimator can be satisfied using randomization of the functions fk without changing the statistical performance of the resulting set-valued predictor. Then, based on D U N , we define the empirical set-valued classifier

Γ(x) = k ∈ Y : fk (x)) ≥ Ĝ-1 (s) with Ĝ(•) = 1 N ∑ X∈D U N K ∑ k=1 1 { fk (X)≥•} .
(2.4)

Theoretical guarantees

Now we investigate rates of convergence for the empirical set-valued classifiers Γ w.r.t. the risk R s . Note that the distribution-free result provided in Section 2.3 holds for Γ. The rate of convergence of the set-valued classifier Γ is obtained under the classical margin assumption [START_REF] Hoffmann | Estimating equations based on eigenfunctions for a discretely observed diffusion process[END_REF].

Assumption 3 (α-margin assumption). We say that the distribution P of the pair (X, Y) ∈ R d × Y satisfies α-margin assumption if there exists C 1 > 0 and t 0 ∈ (0, 1) such that for every positive t ≤ t 0

P X 0 < p k (X) -G -1 (s) ≤ t ≤ C 1 t α .
The exponent α will directly specify the rates of convergence and the classification problem gets easier with the growth of this parameter. It is important to note that since we assume that the distribution functions of p k (X) are continuous for each k, we have

P X 0 < |p k (X) -G -1 (s)| ≤ t → 0 with t → 0.
Therefore, the margin condition only specifies the rate of this decay to 0. We can now state our error control for the empirical set-valued classifiers defined by (2.4).

Theorem 2.4. Assume that f ∞ ≤ B for all f ∈ F . Let M n = N (1/n, L ∞ , F ) be the covering number of F w.r.t. L ∞ -norm with closed balls with radius 1/n. Grants Assumptions 1 and 3 E R s ( Γ) -R s (Γ * s ) inf f∈F (R 2 (f) -R 2 ( f * )) + log(M n ) n α/(α+2) + 1 √ N ,
where the leading constant depends only on L, B, and α.

The rate of convergence for the excess error is of order

log(M n ) n α/(α+2) + 1 √ N
. In particular, it establishes the consistency of the procedure provided that α > 0. Besides, same results holds for the Hamming distance. At the time it was proved, this result is the first, up to our knowledge, that provides a bound on the excess risk for set-valued classifiers in multi-class setting. Compared to the literature, the exponent α/(α + 2) is not classical and it is not clear whether it is improvable. Indeed, in the standard multi-class framework, this exponent is of order (α + 1)/(α + 2) (see [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF]). The second part of the rates which is of order N -1/2 relies on the estimation of the function

G(t) = ∑ K k=1 (1 -F fk (t))
, which serves as a pseudo-oracle CDF that knows the marginal distribution P X .

Numerical experiments

According to the developed methodology, we propose an aggregation procedure based on the cross-validation principle. Formally, the procedure is applied in the case where F is the convex hull of a finite family of score functions (we refer to [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF] for more details). Here, we consider a family of 4 score functions based respectively on the random forest, the softmax regression, the support vector machines, and the k nearest neighbors (with k = 11) procedures. Note that the numerical results are presented for the boosting loss for which Theorem 2.4 apply.

We evaluate the performance of the procedure on two real datasets: the Forest type mapping dataset and the one-hundred plant species leaves dataset coming from the UCI database. We refer to these two datasets as Forest and Plant respectively. The Forest dataset consists of K = 4 classes and 523 labeled observations In the Plant dataset, there are K = 100 classes and 1600 labeled observations.

To get an indication of the statistical significance of the aggregated procedure (referred as CV) we compare it to the set-valued classifiers that result from each component of the library in terms of empirical error and empirical expected size. Without going in deep details, we mention that we split the dataset in three: As a benchmark, we notify that the misclassification errors of the best classifier from the library for the Forest dataset is evaluated at 0.15 , whereas in the Plant dataset, it is evaluated at 0.40. Note that The performance of the classical methods is rather weak in the latter dataset.

The results are reported in Table 2.1, and confirm our expectations. A general observation is that the size constraint is quite well satisfied for all of the methods. Also, moderate level of constraint s leads to drastic improvement in terms of errors as compared to our benchmarks. Moreover, we observe that the risk gets drastically better with moderate s as compared to the best misclassification risk. For instance, for the Plant, the error rate of the set-valued classifier with s = 2 based on random forests is 0. the misclassification error rate of the best component in the library is 0.40. Interestingly the aggregated set-valued classifier (CV) outperforms all components of the library in all of the experiments. A last observation that motivates the use of aggregation procedure.

Optimal rates of convergence

In this section, we focus on the study of optimal rates of convergence for set-valued classifiers with controlled expected size. We exploit classical non-parametric theory tools to derive upper and lower bounds on the excess-risk (Mammen and [START_REF] Hoffmann | Estimating equations based on eigenfunctions for a discretely observed diffusion process[END_REF][START_REF] Yang | Minimax nonparametric classification: Rates of convergence[END_REF]Györfi et al., 2002;[START_REF] Massart | Risk bounds for statistical learning[END_REF][START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]. From the technical point of view, our work is close in spirit to the one by [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] who study the statistical performance of plug-in classification rules under assumptions which involve the smoothness of the regression function and the margin condition 3. They derive fast rates of convergence (faster than n -1/2 ) for plug-in classifiers based on local polynomial estimators [START_REF] Stone | Robust reconstruction of functions by the local-approximation method[END_REF]Tsybakov, 1986;[START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] and show their optimality in the minimax sense.

The motivation of this section is two folds Q1. What is a minimax setup in this problem and what are the minimax rates of convergence?

Q2. Can we statistically justify the introduction of the unlabeled data D U N from the minimax perspective? To be more precise, we would like to understand whether the rates of convergence are affected by N -the size of the unlabeled sample.

Neither of these natural questions have been considered and answered in the previous literature. For simplicity, we only present the result obtained in (Chzhen, Denis, and Hebiri, 2021) w.r.t. the measure of risk R s .

The central notion we manipulate in this section is the minimax rate of convergence in the semi-supervised setting. Let us denote by P a family of joint distribution of (X, Y), and let Γ be an estimator based on D L n and D U N . We introduce the maximal risk

Ψ n,N Γ, P = sup P∈P E D L n ,D U N R s ( Γ) -R s (Γ * s ) .
The minimax rate of convergence is then defined as follows.

Definition 2.1 (Minimax rate of convergence). For a given family P of joint distributions on R d × Y the minimax rates are defined as

E n,N (P ) := inf Γ Ψ n,N Γ, P ,
where the infimum is taken over all set-valued classifiers based on D L n and D U N . The sequence E n,0 (P ) corresponds to the supervised regime, while the sequence E n,N (P ) for N ≥ 1 corresponds to the semi-supervised regime.

Assumptions

In this part we state all the assumptions used in this work and state the family of distributions P which drives the minimax rates. The first assumption is the margin assumption Assumption 3 that we already introduced in the previous Section 2. [START_REF] Chzhen | Fair Regression with Wasserstein Barycenters[END_REF].

The second assumption restricts the set of possible marginal distributions of the feature vectors. Following [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF], we first introduce the notion of regular set. Let c 0 and r 0 be two positive constants. We say that a Borel set

A ⊂ R d is a (c 0 , r 0 )-regular set if Leb (A ∩ B(x, r)) ≥ c 0 Leb (B(x, r)) ,
∀r ∈ (0, r 0 ], ∀x ∈ A .

Definition 2.2 (Strong density).

We say that the probability measure P X on R d satisfies the (µ min , µ max , c 0 , r 0 )-strong density assumption if it is supported on a compact (c 0 , r 0 )-regular set A ⊂ R d and has a density µ w.r.t. the Lebesgue measure such that µ(x) = 0 for all x ∈ R d \ A and

0 < µ min ≤ µ(x) ≤ µ max < ∞, ∀x ∈ A .
Let us mention, that there are various ways to relax this assumption. For instance, it is possible to get rid of the lower bound on the density [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF][START_REF] Kpotufe | Marginal Singularity, and the Benefits of Labels in Covariate-Shift[END_REF]. Besides, the compactness of the support can also be relaxed and replaced by a proper tail condition [START_REF] Gadat | Classification in general finite dimensional spaces with the k-nearest neighbor rule[END_REF]. This type of relaxations are not altering our conclusions about the effect of unlabeled data and thus, for simplicity, we provide the analysis under the strong density assumption.

The next assumption is standard in non-parametric statistics, and states that the conditional distribution of Y is smooth. Definition 2. 3 (Hölder class, Tsybakov, 2009a). We say that a function h : R d → R is (β, L)-Hölder for β > 0 and L > 0 if h is β times continuously differentiable and ∀x, x ∈ R d we have

h(x ) -h x (x ) ≤ L x -x β ,
where h x (•) is the Taylor polynomial of degree β of h(•) at the point x ∈ R d . The set of all functions from R d to R satisfying the above conditions is called (β, L, R d )-Hölder and is denoted by H(β, L, R d ).

Finally, we are in position to define the family of distributions P that governs the rates of convergence. Definition 2.4. We denote by P (L, β, α) the set of joint distributions on R d × Y which satisfy the following conditions

• the marginal P X satisfies the (µ min , µ max , c 0 , r 0 )-strong density,

• for all k ∈ Y the k th regression function p k (

•) = P(Y = k | X = •) belongs to the (β, L, R d )-Hölder class, that is, p k ∈ H(β, L, R d ) for all k ∈ Y,
• for all k ∈ Y the regression function p k satisfy the (C 1 , t 0 , α)-Margin assumption,

• for all k ∈ Y, the cumulative distribution function F p k of p k (X) is continuous.

The family of distributions P (L, β, α) resembles the one considered in [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] in the context of binary classification. The major difference is the continuity Assumption 1, which poses certain restrictions and does not allow to re-use in a straightforward way their construction for lower bounds.

Lower bound

In this section we establish minimax lower bounds on the introduced risk measures. Our rates highlight the benefit of the semi-supervised approaches in the context of the set-valued classification with controlled expected size.

Theorem 2.5. Let K ≥ 3, s ≤ K/2 -1. If 2α β 2 ≤ d, then for all n, N ∈ N it holds that E n,N (P (L, β, α)) n -(1+α)β 2β+d (n + N) -1/2 .
The above lower bound imply that the best rate in the supervised regime is n -1/2 across all the risk. Therefore, even if the margin assumption is very strong (α 1) supervised methods (N = 0) cannot achieve fast rates. This fact is the major difference with classical setups where the value of threshold is known (such as classification and level set estimation). Indeed, under the same assumptions on the family of distributions, without the continuity Assumption 1, the minimax rate in those frameworks is n -(1+α)β/(2β+d) as proved for instance in [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF][START_REF] Rigollet | Optimal rates for plug-in estimators of density level sets[END_REF] and unlabeled data cannot improve it. In contrast, this limitation can be neglected in the semi-supervised regime. Indeed, for sufficiently large unlabeled sample, the dominant term in the lower bound is of order n -(1+α)β/(2β+d) , which can be faster than n -1/2 . More precisely, the following relations are necessary to get fast rates of convergence

(n + N) -1/2 = o n -(1+α)β/(2β+d) , n -(1+α)β/(2β+d) = o(n -1/2 ) .
The condition on the left hand side ensures that we have enough unlabeled data to eliminate the impact of not knowing threshold G -1 (s) in Equation (2.2). Whereas, the condition on the right hand side ensures that the classification problem with "known" threshold admits fast rates. The above discussion suggests that the lack of knowledge of the threshold G -1 (s) is significant, and the considered framework is more difficult from the statistical perspective than its more classical counterparts.

Finally, Note that the second part of the rate in all three cases is (n + N) -1/2 instead of N -1/2 . Actually, if n N, from purely minimax perspective it is impossible to obtain a lower bound with N -1/2 instead of (n + N) -1/2 . Indeed, one can always split the labeled sample erasing labels from one of them. Such splitting artificially augments the size of unlabeled sample N by some fraction of n. Of course, the regime n N is not particularly interesting, since, despite the fact that N = 0, still corresponds to the essentially supervised setup.

Upper bound

In this section, we build a set-valued classifier that achieves (up to a log factor) the lower bound stated in Theorem 2.5. We first establish the obtained upper bound and then present the construction of the estimator.

Theorem 2.6. Let K ∈ N, s ∈ (0, K), then there exists an estimator Γ such that for all n, N ∈ N we have

Ψ n,N Γ, P (L, β, α) n log n -(1+α)β 2β+d (n + N) -1/2 .
As an immediate consequence, from the above result is that the lower bound of Theorem 2.5 are achievable.

Construction of the estimator. The construction of the set-valued classifier is similar to the one described in Section 2.3 with technical modifications for matching the obtained lower bound. In particular, in order to get the rate (n + N) 1/2 , we do use the whole labeled sample to build estimators of the posterior probability. These estimators pk are constructed using an arbitrary half D n/2 of the labeled dataset D L n and the following assumption is required.

Assumption 4 (Exponential concentration).

There exist estimators pk for all k ∈ Y based on D n/2 and positive constants C 1 , C 2 and δ 0 ≥ 0 such that for all k ∈ Y and all n ≥ 2 we have for all δ > δ 0 n -β/(2β+d) sup P∈P (L,β,α)

P (| pk (x) -p k (x)| ≥ δ) ≤ C 1 exp -C 2 n 2β 2β+d δ 2 ,
for almost all x ∈ R d w.r.t. P X .

Assumption 5 (Continuity of CDF). For all k ∈ Y, conditionally on the data, the cumulative distribution function F pk (t) := P X ( pk (X) ≤ t) of pk (X) is almost surely P ⊗ n/2 continuous on (0, 1). First let us point out that Assumption 4 induces that for all n ≥ 2 and all α > 0 sup

P∈P (L,β,α) E p -p 1+α ∞,P X n log n -(1+α)β 2β+d ,
where p(•) = (p 1 (•), . . . , p K (•)) and p(•) = ( p1 (•), . . . , pK (•)) . Assumption 4 is commonly used in the statistical community when we deal with rates of convergence in the classification settings [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF][START_REF] Lei | Classification with confidence[END_REF][START_REF] Sadinle | Least ambiguous set-valued classifiers with bounded error levels[END_REF]. It is for instance satisfied by the locally polynomial estimator [START_REF] Stone | Robust reconstruction of functions by the local-approximation method[END_REF]Tsybakov, 1986;[START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] with δ 0 = 0. As already seen, Assumption 5 can always be satisfied by slightly processing any estimator p. In (Chzhen, Denis, and Hebiri, 2021), we propose to perturb the estimator with a deterministic perturbation to fit with the minimax framework.

Finally, To make our presentation mathematically correct we introduce the following notation D L n = D n/2 D n/2 , where D n/2 is the dataset used to build the estimators pk for k ∈ Y. Now, all the labels are removed from D n/2 . That is, D n/2 consists of n/2 i.i.d. samples from P X . Consequently, the semi-supervised estimator of G(•) is defined as Ĝ

(•) = 1 n/2 + N ∑ X∈D U N D n/2 K ∑ k=1 1 { pk (X)>•} .
Finally, the set-valued classification procedure Γ is defined point-wise as

Γ(x) = k ∈ Y : pk (x) ≥ Ĝ-1 (s) .
Sketch of proof. Now, we briefly discuss about the log factor obtained in Theorem 2.6. We introduce an intermediate quantity G(•) = ∑ K k=1 P X ( pk (X) > •), and the associated set-valued classifier, which we refer to as the pseudo Oracle classifier given for all

x ∈ R d by Γ(x) = {k ∈ Y, pk (x) ≥ G-1 (s)}.
The set-valued Γ assumes knowledge of the marginal distribution P X , it is seen as an idealized version of Γ, and formally corresponds to the case N = +∞. Besides, thanks to Assumption 2, this pseudo Oracle satisfies the size constraints, that is S( Γ) = s almost surely. Now, we start with the following decomposition

R s ( Γ) -R s (Γ * s ) = R s Γ -R s Γs + R s ( Γ) -R s (Γ * s ) (1) (2)
The first term (1) in the r.h.s. of the above inequality is relies on a C.D.F. estimation problem. For the second term ( 2), we observe that

k ∈ (Γ * s (X) ∆ Γs (X)) ⇒ p k (X) -G -1 (s) ≤ |G -1 (s) -G-1 (s)| + | pk (X) -p k (X)| (2.5)
Now, the crucial step of our analysis is the following lemma, that bounds the difference between G-1 (s) and G -1 (s) in terms of the difference between pk 's and p k 's.

Lemma 2.1 (Upper bound on the thresholds). Let Assumption 1 be satisfied, then for all s ∈ (0, K)

G -1 (s) -G-1 (s) ≤ p -p ∞,P X , almost surely P ⊗n ⊗ P ⊗N X .
The difference |G -1 (s) -G-1 (s)| resembles the Wasserstein infinity distance which gives an alternative approach to prove Lemma 2.1, see (Bobkov and Ledoux, 2016). Lemma 2.1 explains the extra log n factor that appears in the upper bound, as the minimax estimation in sup norm contains the log n factor, see for instance [START_REF] Stone | Robust reconstruction of functions by the local-approximation method[END_REF][START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF]. From Equation (2.5) and Assumption 3,

R s ( Γ) -R s (Γ * s ) ≤ 2 max k pk -p k ∞ K ∑ k=1 P X p k (X) -G -1 (s) ≤ 2 max k pk -p k ∞ ≤ C max k pk -p k 1+α ∞ .
It is intuitively clear that if, on top of Lemma 2.1, we manage to control the difference | G-1 (s) -Ĝ-1 (s)| then the proof of the upper bound would simply follow the arguments of [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]. Yet, such a control is not feasible under our assumptions. To see this, notice that conditionally on D n the quantity | G-1 (s) -Ĝ-1 (s)| resembles the deviation of quantile from its empirical version. However, classical result 1 on asymptotic normality of sample quantiles (Ma and Robinson, 1998, Theorem 2) tells that in order to have a central limit theorem with (n + N) -1/2 rate it is necessary and sufficient to require G ( G-1 (s)) > 0. From the minimax perspective, this condition cannot be satisfied since we do not require any lower bound on the derivative of G(•).

In (Chzhen, Denis, and Hebiri, 2021) we demonstrate that the upper bound can be improved if we assume that the derivative of G(•) is uniformly lower bounded, that is, G -1 (•) has some regularity.

Conclusion

In this chapter, we studied the set-valued classification problem with a controlled expected size. The theoretical analysis started with a setting that allowed us to get distribution free results and then we added some assumptions to build a minimax analysis where we emphasized the unlabeled data as a key feature to get fast rate of convergence in some situations. From this perspective, our analysis wants to be a promotion for semisupervised methods that can be exploited in several fields such as the fairness problem that we described in Chapter 3. We paid a particular attention to understand the meaning and the implications of the continuity assumption we imposed on the conditional probability CDF. One of our main challenges was the study and the control of differences of quantiles, the function G -1 being in the center of our attention, through tools from empirical processes, rank statistics and non parametric theory.

In [START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF]Chzhen, Denis, and Hebiri, 2021), the dependency in the number of labels K has not been considered. Yet, set-valued classification can face extreme classification scenarios. The prediction ability of set-valued classifiers should be investigated in a context where the number of labels is large, as well as the number of observations and features. By step, the first consideration should be to tackle the question of large number of labels. Techniques from high dimensional statistic should be used, in particular, one could think of a new notion of sparsity assumption adapted to the set-valued classification. A possible direction is to introduce a margin assumption that involves a number s * K which reflects, in the set-valued framework, the optimal size s. In this case, one may expect only logarithmic deflation of the rate in terms of K, and maybe linear (or surperlinear) in terms of the sparsity level s * . This line of research might also be related to multi-label classification where this kind of behaviors have already been obtained for instance in [START_REF] Jain | Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications[END_REF] and in a previous work [START_REF] Chzhen | On the benefits of output sparsity for multi-label classification[END_REF].

Chapter 3

Multi-class classification under demographic parity constraint

In this chapter, I present a contribution for multi-class classification under fairness constraint. Algorithmic fairness has become very popular during the last decade [START_REF] Calders | Building classifiers with independency constraints[END_REF][START_REF] Schmisser | Penalized nonparametric drift estimation for a multidimensional diffusion process[END_REF][START_REF] Lum | A statistical framework for fair predictive algorithms[END_REF][START_REF] Zafar | Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment[END_REF][START_REF] Agarwal | A reductions approach to fair classification[END_REF][START_REF] Donini | Empirical risk minimization under fairness constraints[END_REF][START_REF] Agarwal | Fair Regression: Quantitative Definitions and Reduction-Based Algorithms[END_REF][START_REF] Barocas | Fairness and Machine Learning[END_REF][START_REF] Chzhen | Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification[END_REF]Chiappa et al., 2020). It helps addressing an important social problem: mitigating historical bias contained in the data. This is a crucial issue in many applications such as loan assessment, health care, or even criminal sentencing. The common objective in algorithmic fairness is to reduce the influence of a sensitive attribute on a prediction.

In recent years, various authors and communities have been proposing different formal definition of the notion of fairness, equality, and justice. An attractive formalism relies on the idea that a prediction must not discriminate based on some characteristics of an instance (sensitive feature) such as the gender or the ethnicity. We refer the interested reader to [START_REF] Barocas | Fairness and Machine Learning[END_REF][START_REF] Mehrabi | Review of Mathematical frameworks for Fairness in Machine Learning[END_REF] for a general introduction to the problem of fair prediction and to (Barrio, Gordaliza, and Loubes, 2020;[START_REF] Oneto | Fairness in Machine Learning[END_REF] for a review of the most recent theoretical advances.

In [START_REF] Chzhen | Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification[END_REF], we investigated the binary classification and regression settings under fairness constraints. One of the major contribution of these works is to provide a closed form of the oracle predictors and derive post-processing estimation procedures which are able to leverage unlabeled data and exhibit good numerical performance. In the same spirit, we investigate in (Denis et al., 2021) the fair multi-class classification framework. Imposing fairness constraint in the multi-class problem has only been briefly discussed in [START_REF] Ye | Unbiased Subdata Selection for Fair Classification: A Unified Framework and Scalable Algorithms[END_REF] by considering Support Vector Machine (SVM) fair prediction. Our contribution provides a deeper analysis of the problem.

Fair multi-class classification

In this section, we introduce the general framework and also define and discuss the notion of fairness that we consider. In addition, we exhibit a closed form of the optimal fair predictor in Section 3.1.3.

Statistical setting

In fair multi-class classification, compared to the usual multi-class setting, we assume that the input feature is a couple (X, S) where X corresponds to the vector of covariates and S is the sensitive feature (e.g. gender, ethnicity, qualification, birth place, . . .). For simplicity, we assume that S ∈ {-1, 1}. The distribution of the sensitive feature S is denoted by (π s ) s∈S , and we assume that min s∈S π s > 0. A complete observation is of the form (X, S, Y) where Y ∈ Y is the label associated to (X, S). In this context, a classification rule g is a function mapping X × {-1, 1} onto Y, whose performance is again evaluated through the misclassification risk

R(g) = P (g(X, S) = Y) .
For k ∈ Y, p k (X, S) denotes the conditional probability P (Y = k|X, S). Recall that a Bayes classifier minimizes the misclassification risk and is defined as g * (x, s) ∈ arg max k∈Y p k (x, s) , for all (x, s) ∈ X × S .

Multi-class classification with demographic parity

Several notion of fairness have been studied in the binary classification framework, such as Equalized-Odds, Equality of Opportunity, or Demographic Parity. We refer for instance to (Hardt, Price, and Srebro, 2016;[START_REF] Barocas | Fairness and Machine Learning[END_REF] for an overview of these notions. In this chapter, we consider muti-class classification problems under Demographic Parity (DP) fairness constraint [START_REF] Calders | Building classifiers with independency constraints[END_REF], that requires the independence of the prediction function from the sensitive feature S. The DP constraint is perhaps the most intuitive notion of fairness which is common to the classification and regression setting. DP constraint has a recognized interest in various applications; this constraint could be typically imposed in loan agreement without gender attributes or in the context of crime prediction without ethnicity discrimination. Formally, we define DP constraint as follows Definition 3.1 (Demographic parity). We say that a classifier g ∈ G (and write g ∈ G fair ) with respect to the distribution P on X × S × Y if P (g(X, S) = k|S = 1) = P (g(X, S) = k|S = -1) , ∀k ∈ Y .

The above definition naturally extends to the multi-class setting the DP considered in binary classification [START_REF] Agarwal | Fair Regression: Quantitative Definitions and Reduction-Based Algorithms[END_REF][START_REF] Gordaliza | Obtaining fairness using optimal transport theory[END_REF][START_REF] Jiang | Wasserstein fair classification[END_REF][START_REF] Mehrabi | Review of Mathematical frameworks for Fairness in Machine Learning[END_REF]Chiappa et al., 2020) .

Intuitively, when fairness is required, two important aspects of a classifier g need to be controlled: its misclassification risk R(g) and its unfairness, which we define below. Definition 3.2 (Unfairness measure). The unfairness of a classifier g ∈ G is quantified by

U (g) := K ∑ k=1 |P (g(X, S) = k|S = 1) -P (g(X, S) = k|S = -1)| .
Naturally, taking into account the definition above, a classifier g is fair if and only if U (g) = 0.

Alternative measures of unfairness could be considered. For instance, once can replace the summation by a maximum over k in the above definition. However, summing over all possible labels is more informative and appears more naturally when controlling the prediction risk (see Theorem 3.2).

Optimal fair classifier

In this section, we provide an explicit formulation of the optimal fair classifiers w.r.t. the misclassification risk under DP constraint. An optimal fair classifier is a solution of min g∈G fair

R(g).

The difficulty of obtaining an optimal fair classifier consists in properly balancing the misclassification risk together with the fairness criterion. Let g be a classifier and λ = (λ 1 , . . . , λ K ) ∈ R K the Lagrange multiplier of the above minimization problem. We introduce a risk measure, referred as fair-risk, which provides a trade-off between the accuracy of g and its unfairness

R λ (g) := R(g) + K ∑ k=1 λ k [P (g(X, S) = k|S = 1) -P (g(X, S) = k|S = -1)] .
In order to be able to derive a characterization of the optimal fair classifier, we require the following assumption on the random variables p k (X, s). Assumption 6. The mapping t → P p k (X, S)p j (X, S) ≤ t|S = s is assumed continuous, for any k, j ∈ Y and s ∈ S.

This assumption requires that the distribution of the differences p k (X, S)p j (X, S) has no atoms. Note that this assumption is similar to Assumption 1. In fact, it plays the same role and is specific to the multi-class framework. In particular, we observe that in the binary case (K = 2), the above assumption simply boils down to the one considered in [START_REF] Chzhen | Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification[END_REF] that requires the continuity of t → P (p k (X, S) ≤ t|S = s). It is, however, clear that in the general case K ≥ 3 these two conditions describe different sets of distributions.

From Assumption 6, we deduce a characterization of the optimal fair classifier.

Proposition 3.1. Let Assumption 6 be satisfied and define λ * ∈ R K by

λ * ∈ arg min λ∈R K ∑ s∈S E X|S=s max k (π s p k (X, s) -sλ k ) .
Then, g * fair ∈ arg min g∈G fair R(g) if and only if g * fair ∈ arg min g∈G R λ * (g).

In other words, the optimum of the risk R(g) over the class of fair classifiers is also maximizing the fair-risk R λ * . By construction, R λ * is a risk measure which optimally balances both classification accuracy and unfairness. Proposition

3.1 directly implies that R λ * (g) ≥ R λ * (g * fair ) = R(g * fair ) ≥ 0, for g ∈ G.
We now quantify the performance of any classifier g ∈ G through its excess fair-risk

E fair (g) := R λ * (g) -R λ * (g * fair ).
Furthermore, Proposition 3.1 directly implies a closed form expression of optimal fair classifiers, which is the bedrock of our procedure. Any optimal fair classifier is simply maximizing scores, which are obtained by shifting the original conditional probabilities in a optimal manner.

Corollary 3.1. Under Assumption 6, an optimal fair classifier is characterized by

g * fair (x, s) ∈ arg max k (π s p k (x, s) -sλ * k ) , (x, s) ∈ X × S .
Note that a similar characterization of a optimal fair predictor is obtained in (Chzhen et al., 2020a)

General estimation procedure

In this section, we provide now a plug-in estimator for the optimal fair classifier g * fair . The proposed procedure is inspired from the methodology described in Section 2.3 of Chapter 2. In particular, we propose an algorithm that enjoys strong theoretical guarantees both in terms of fairness and risk. In particular, we exhibit in Section 3.2.2 distribution-free fairness guarantee.

Plug-in estimator

We are given two datasets. The first labeled one D n = {(X i , S i , Y i ), i = 1, . . . , n} consists of i.i.d. samples from the distribution P. This is the classical dataset used for training estimators ( pk ) k of the conditional probabilities (p k ) k , e.g., Random Forest, SVM, etc. The second unlabeled dataset D N consists of N i.i.d. copies of (X, S). the sample D N is collected and split in the following way: we set (S 1 , . . . , S N ) the i.i.d. sample of sensitive features used to compute empirical frequencies ( πs ) s∈S for estimating (π s )) s∈S . The number of observations corresponding to S = s is denoted N s , for s ∈ S. Of course N -1 + N 1 = N. For s ∈ S, the feature vector in D N denoted X s 1 , . . . , X s N s is composed by i.i.d. data from P X s , the distribution of X|S = s. All samples are assumed independent.

In order to derive consistency results on the excess fair-risk and the unfairness of our plug-in rule, we require continuity conditions on the random variables pk (X, S), in the spirit of Assumption 2 (conditional on the learning sample). However, such property is automatically satisfied whenever perturbing the ( pk ) k with a small random noise. To this end, we introduce pk (X, S,

ζ k ) := pk (X, S) + ζ k , for a given uniform perturbation ζ k on [0, u].
Given (ζ k ) k∈Y and (ζ s k,i ) independent copies of a Uniform distribution on [0, u], we define the randomized fair classifier ĝ as ĝ(x, s) = arg max

k∈Y πs pk (x, s, ζ k ) -s λk , for all (x, s) ∈ X × S , with λ ∈ R K given as λ ∈ arg min λ ∑ s∈S 1 N s N s ∑ i=1 max k∈Y πs pk (X s i , s, ζ s k,i ) -sλ k . ( 3.1)
Note that the construction of the plug-in rule ĝ relies on (x, s) but also on the perturbations ζ and ζ s k,i for k ∈ Y, i ∈ N s and s ∈ S. Note that the objective function in Equation (3.1) is convex but non smooth due to the evaluation of the function (hard) max. In (Denis et al., 2021), we provide an alternative algorithm based on soft-max regularization. Finally, as for the procedure provided in Section 2.3 of Chapter 2, the proposed estimator relies on a post-processing approach. In a first step, preliminary estimators of p k are builded while in a second step these estimators are re-calibrated to meet fairness criterion.

Statistical guarantees

We are now in position to derive fairness and consistency guarantees of the plug-in procedure.

Universal fairness guarantee. We first focus on fairness assessment and prove that the plug-in estimator ĝ is asymptotically fair. The convergence rate on the unfairness to zero is parametric with the number of unlabeled data N. Notably, as in set-valued classification, the fairness guarantee is distribution-free and holds for any estimators of the conditional probabilities. Theorem 3.1. For any distribution P, there exists a constant C > 0 which only depends on K and min s∈S π s , such that for any estimators pk we have,

E [U ( ĝ)] ≤ C √ N .
Consistency of the excess fair-risk. We now consider the excess risk of the estimator ĝ.

We define the L 1 -norm in R K between the estimator p := ( p1 , . . . , pK ) and the vector of the conditional probabilities p := (p 1 , . . . , p K ) as p -

p 1 = ∑ k∈Y | pk (X, S) -p k (X, S)| .
Theorem 3.2. Let Assumption 6 be satisfied, then the following holds

E [E fair ( ĝ)] ≤ C E [ p -p 1 ] + ∑ s∈S E [| πs -π s |] + E [U ( ĝ)] + u .
The above result highlights that the excess fair-risk of ĝ depends on 1) the quality of the estimators of the conditional probabilities through its L 1 -risk; 2) the quality of the estimators of (π s ) s∈S ; 3) the unfairness of the classifier; and 4) the upper-bound u on the regularizing perturbations. Consequently, ĝ is consistent w.r.t. the excess-fair risk as soon as the estimator p is consistent in L 1 -norm.

Corollary 3.2. If E [ p -p 1 ] → 0 and u = u n → 0 when n → ∞, we have E [E fair ( ĝ)] → 0, as n, N → ∞ .
We emphasize that Theorem 3.1 and Corollary 3.2 directly imply that ĝ performs asymptotically as well as g * fair in terms of both fairness and accuracy.

Numerical experiments

In this section, we discuss several numerical aspects of the proposed algorithm. As a benchmark, we introduce an alternative approach that enforces fairness on each individual score in Section 3.3.1. Then, we illustrate efficiency of our procedure on real datasets in Section 3.3.2.

Alternative strategy for fair multi-class classification

The procedure developed in Section 3.2 enforces the score maximizer to be fair. An alternative approach suggested in [START_REF] Ye | Unbiased Subdata Selection for Fair Classification: A Unified Framework and Scalable Algorithms[END_REF] consists in imposing fairness at the level of each posterior probability instead of their maximizer. That is to say, we require that the posterior probabilities are DP fair. However, Ye and Xie, 2020 does not provide any theoretical analysis of this approach. In (Chzhen et al., 2020b), we provide a solution of the regression problem under DP constraint. Following this idea, we consider the L 2risk defined in Chapter 1 and using the same notations, we consider a score function f for which we define the DP constraint Definition 3.3. We say that f : X × {-1, 1} → R K is score-fair in demographic parity if each coordinate of f is fair w.r.t. the demographic parity notion of fairness (Chzhen et al., 2020b).

Consequently, a possible way to tackle fair multi-class classification is to consider the following minimization problem

f * score-fair ∈ arg min {R 2 ( f ) : f is score-fair} .
While this approach seems to be rather natural, let us emphasize that score-fair DP does not imply DP for the score maximizer, since the maximum, unlike thresholding, operation does not preserve the DP property. Optimal score-fair functions rely on the L 2 -risk and be easily characterized following the approach in (Chzhen et al., 2020b;[START_REF] Gouic | Projection to Fairness in Statistical Learning[END_REF]. In particular, Theorem 2.3 in (Chzhen et al., 2020b) identifies the distribution of score-fair classifier f * score-fair as solutions of a Wasserstein barycenter problem. We refer to (Denis et al., 2021) for the details of the estimation procedure of f * score-fair .

Application to real datasets

In this section, we illustrate the performance of our method argmax-fair, the alternative approach score-fair, and the classifier builded without fairness constraint (unfair), for both linear and non-linear multi-class classification. For linear models, we consider the oneversus-all logistic regression (reglog) and the SVM with linear kernel (linearSVC); for non-linear models: SVM model with Gaussian kernel (GaussSVC) and Random Forests algorithm (RF).

Datasets. The performance of our method is evaluated on four benchmark datasets for which we provide a short description.

Communities&Crime (CRIME) dataset contains socio-economic, law enforcement, and crime data about communities in the US with 1994 examples. The task is to predict the number of violent crimes per 10 5 population which, we divide into K = 7 balanced classes based on equidistant quantiles. Following [START_REF] Calders | Controlling attribute effect in linear regression[END_REF]Chzhen et al., 2020c the binary sensitive feature is the percentage of black population. METHOD DATA CRIME, K = 7 LAW, K = 4 WINE, K = 5 CMC, K = 3 Accuracy Unfairness Accuracy Unfairness Accuracy Unfairness Accuracy Unfairness reglog + unfair 0.34 ± 0.02 1.12 ± 0.07 0.43 ± 0.01 0.89 ± 0.05 0.54 ± 0.01 0.47 ± 0.05 0.52 ± 0.02 0.78 ± 0.16 reglog + score-fair 0.33 ± 0.01 0.78 ± 0.09 0.42 ± 0.01 0.09 ± 0.02 0.54 ± 0.01 0.08 ± 0.03 0.51 ± 0.02 0.25 ± 0.1 reglog + argmax-fair 0.28 ± 0.01 0.26 ± 0.07 0.42 ± 0.01 0.05 ± 0.02 0.54 ± 0.02 0.04 ± 0.01 0.52 ± 0.02 0.19 ± 0.1 linearSVC + unfair 0.36 ± 0.02 1.12 ± 0.07 0.43 ± 0.01 0.97 ± 0.07 0.53 ± 0.01 0.27 ± 0.05 0.51 ± 0.02 0.63 ± 0.22 linearSVC + score-fair 0.31 ± 0.02 0.88 ± 0.05 0.42 ± 0.01 0.1 ± 0.03 0.53 ± 0.01 0.1 ± 0.07 0.53 ± 0.02 0.26 ± 0.16 linearSVC + argmax-fair 0.29 ± 0.02 0.25 ± 0.08 0.42 ± 0.01 0.04 ± 0.02 0.53 ± 0.01 0.06 ± 0.04 0.52 ± 0.02 0.2 ± 0.12 GaussSVC + unfair 0.36 ± 0.02 1.4 ± 0.13 0.43 ± 0.01 1.04 ± 0.04 0.53 ± 0.01 0.28 ± 0.06 0.51 ± 0.02 1.0 ± 0.17 GaussSVC + score-fair 0.35 ± 0.02 1.02 ± 0.07 0.42 ± 0.01 0.16 ± 0.04 0.55 ± 0.01 0.12 ± 0.04 0.51 ± 0.02 0.16 ± 0.09 GaussSVC + argmax-fair 0.3 ± 0.02 0.22 ± 0.05 0.42 ± 0.01 0.10 ± 0.03 0.55 ± 0.01 0.06 ± 0.03 0. Law School Admissions (LAW) dataset [START_REF] Wightman | LSAC national longitudinal bar passage study[END_REF] presents national longitudinal bar passage data and has 20649 examples. The task is to predict a students GPA divided into K = 4 classes based on equidistant quantiles. The sensitive attribute is the race (white versus non-white).

Wine Quality (WINE) dataset [START_REF] Cortez | Modeling wine preferences by data mining from physicochemical properties[END_REF] reports the description of 6497 wines and the task is to predict the quality graded by the experts. The quality is between 3 (bad) and 9 (good) but we consider only K = 5 classes (4 to 8) due to a too low frequency of the class 3 and 9 (resp. 5 and 30 examples). The sensitive attribute is the color (red versus white).

Contraceptive Method Choice (CMC) dataset is about 1987 National Indonesia Contraceptive Prevalence Survey. The problem is to predict the contraceptive method choice of a woman (no use, long-term or short-term methods) based on her demographic and socio-economic characteristics. The sensitive feature is the religion (Islam versus Non-Islam).

Performance. Results are presented in Table 3.1 and highlight the effectiveness of our method. As an example, for the LAW dataset and the GaussSVC with argmax-fair, the unfairness is divided by almost 25 (0.97 to 0.04). Furthermore, the argmax-fair procedure outperforms the unfair and the score-fair algorithms for the datasets CRIME, LAW and WINE in terms of unfairness: However, we observe a small decrease of the models accuracy (relatively small compared to the gain in fairness). Note that for the dataset CMC, score-fair and argmax-fair achieve similar performance.

Conclusion

In the multi-class classification framework, we provide an optimal fair classification rule under DP constraint and derive misclassification and fairness guarantees of the as-sociated plug-in fair classifier. Our approach achieves distribution-free fairness and can be applied on top of any probabilistic base estimator. We illustrate the proficiency of our procedure on various synthetic and real datasets, notably in comparison to the score-fair approach suggested in [START_REF] Ye | Unbiased Subdata Selection for Fair Classification: A Unified Framework and Scalable Algorithms[END_REF]. The efficiency of our algorithm in terms of fairness is particularly salient for datasets with large historical bias.

However, our numerical study also outlines the downside of fairness proficiency in terms of classification accuracy. One should hereby be very cautious when using classifiers with strong fairness guarantee, as it possibly degrades the classification quality. This calls for an analysis of classification problems with fairness constraints from a multiobjective perspective and paves the way for characterizing the Pareto front between fairness and accuracy objectives. An interesting approach to handle both fairness and accuracy in the multi-class setting will be to consider set-valued classification under fairness constraint.

Chapter 4

Multi-class classification for diffusion paths

In this chapter, I present a generalization of the mixture model described in Chapter 1 to the case where the feature consists of observations of a diffusion process, that is solution of a stochastic differential equation (s.d.e.), observed over a fixed time interval [0, T]. As a consequence, the drift function of the s.d.e. in this model depends on the label of the observation. While mixture models are widely studied from a statistical learning perspective, the presented results are among the first that deal with the s.d.e. framework and constitute a new contribution to the functional data learning field.

Usually, in the context of parameters estimation of a diffusion process, the only available data consists of a single observation (continuous or discrete) of a diffusion path. Within this context, T → +∞ and ergodicity properties of the diffusion are used in force to handle this problem. One of the specificity of the model we study in this chapter is that the horizon time T is fixed and the ergodicity of the diffusion process is not required. However, in the multi-class setting, this framework can be considered since a learning sample of independent copies of (X, Y) is available. The asymptotic in T is then replaced by the asymptotic w.r.t. the sample size. Throughout this chapter, we assume that data are collected at discrete times.

Up to our knowledge, the work of Cadre ( 2013) is the first one that tackles the problem of classification in the s.d.e. framework. There, the authors focus on binary classification for continuous observations and provide an estimation procedure relying on the empirical risk minimization strategy. However, this method cannot be implemented for practical purpose since the proposed procedure does not consider E.R.M. estimator based on convex surrogate of the misclassification risk (see Section 1.2.2 in Chapter 1). More recently, the work of [START_REF] Gadat | Optimal functional supervised classification with separation condition[END_REF] provides a minimax analysis of a much simpler mixture model where the input feature is modeled as a solution of a white noise equation.

In [START_REF] Denis | Consistent procedures for multiclass classification of discrete diffusion paths[END_REF], we extend the results obtained by [START_REF] Cadre | Supervised classification of diffusion paths[END_REF] 51 to discrete time observations in the multi-class framework. In the parametric setting, we provide theoretical guarantees for different estimation procedures which are easily implementable. A part of these results are presented in Section 4.3.

In addition, we also investigate in [START_REF] Denis | Consistent procedures for multiclass classification of discrete diffusion paths[END_REF] the parametric estimation of the drift function in our specific framework. Motivated by the extension of our results to the nonparametric case, a second line of results presented in this chapter focuses on the estimation of the drift function in the context of i.i.d. repeated observations. This part is developed in [START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF] where we propose a novel constrained estimator relying on a ridge type constraint. This procedure offers appealing properties and can be viewed as an alternative strategy to the cutoff procedure developed in [START_REF] Comte | Nonparametric drift estimation for i.i.d. paths of stochastic differential equations[END_REF] studied in the context of continuous observations. The construction of the procedure and its main properties are provided in Section 4.4.

Model and assumptions

In this chapter, the feature X is a mixture of Brownian motion with drift. More precisely, X takes its value in X := (C([0, T]), C) the set of real valued continuous functions with its corresponding σ-algebra endowed by the uniform topology. Given a starting point x 0 ∈ R, the process X = (X t ) t∈[0,T] is assumed to come from the following diffusion model

X 0 = x 0 dX t = b * Y (X t )dt + σ(X t )dW t , (4.1)
where (W t ) t≥0 denotes a standard Brownian motion on some probability space (Ω, F , P) and such that the label Y is independent of (W t ) t≥0 with known distribution under P given by (π k ) k∈Y . The function b * = (b * 1 , . . . , b * K ) is a vector of K unknown Borel real functions. The real-valued function σ is assumed to be known. In the sequel, (F X t ) t≥0 := {σ(X s : s ≤ t) ; t ≥ 0} denotes the natural filtration of the process X.

Assumptions

Throughout this chapter, we make the following assumptions.

Assumption 7 (Ellipticity and regularity).

There exist strictly positive constants σ 0 , σ 1 such that

0 < σ 0 ≤ σ(x) ≤ σ 1 , ∀x ∈ R.
There exists a positive constant L 0 such that

sup i∈Y |b * i (x) -b * i (y)| + |σ(x) -σ(y)| ≤ L 0 |x -y|, ∀(x, y) ∈ R 2 .
Assumption 7 ensures the existence and uniqueness of a strong solution for Equation (4.1) and that E[sup t∈[0,T] |X t | q ] < ∞ for any integer q ≥ 1. Furthermore, it implies that

sup i∈Y |b * i (x)| ≤ C 0 (1 + |x|). (4.2)
Finally, b * satisfies the following condition.

Assumption 8 (Novikov condition).

E exp 1 2 T 0 b * 2 i σ 2 (X s )ds < +∞, ∀i ∈ Y.
Here Novikov's condition (Assumption 8) is sufficient to apply Girsanov's theorem (Revuz and Yor, 2013)

Bayes Classifier

The Bayes classifier g * is then defined as

g * (X) ∈ arg max k∈Y p k (X), p k (X) := P Y = k|F X T .
The following proposition, which is an extension of the one obtained in [START_REF] Cadre | Supervised classification of diffusion paths[END_REF] in the context of binary classification, provides a closed form of the Bayes classifier. This result relies on the application of the Girsanov's theorem.

Proposition 4.1. For all t ∈ (0, T) and each i ∈ Y we define

F k := T 0 b * k σ 2 (X s )dX s - 1 2 T 0 (b * k ) 2 σ 2 (X s )ds.
The sequence of conditional probabilities satisfies

p k (X) = P Y = k|F X T = ϕ k (F) P -a.s
where F = (F 1 , . . . , F K ), and ϕ k : (x 1 , . . . , x K ) → p k e x k ∑ K j=1 p j e x j are the softmax functions.

Estimation strategy

Let (X t ) t∈[0,T] be the solution of (4.1). We assume that the observation consists of a single discretized sample path X(ω) := (X k∆ (ω)) k∈{0,...,n} with T = n∆. Note that while we assume that T is fixed, we consider the asymptotic n → +∞. As we assume that observations are collected at discrete times, the learning sample D N consists in i.i.d. observations (X (j) , Y (j) ) j=1,...,N of (X, Y).

Discrete observations classifier

Hereafter, we define a set of classifiers which are based on the discrete time observations (X k∆ ) k∈{0,...,n} . We refer these classifiers as discrete observations classifiers. In particular, we provide a control of the excess risk of these classifiers.

For a trajectory X and b = (b 1 , . . . , b K ) a vector of K Borel real functions, we define for i ∈ Y the discrete version of F based on (X k∆ ) k∈{0,...,n} and b:

F i b := n-1 ∑ k=0 b i σ 2 (X k∆ )(X (k+1)∆ -X k∆ ) - ∆ 2 b 2 i σ 2 (X k∆ ) , F b := (F 1 b , . . . , F K b ). Then we set p k b (X) := ϕ k (F b ), k = 1, . . . , K.

Comparison inequality

The following proposition establish a bound for the excess risk of some discrete observations classifier g b , and highlights its link with a suitable distances between b and b * . We introduce the norm . T defined for a real valued function f and a process X from model (4.1):

f 2 T := sup t∈[0,T] E[| f (X t )| 2 ].
≥ 1 such that sup i∈Y |b i (x)| ≤ C b (1 + |x|) γ . Then, the following holds K ∑ i=1 E X pi b (X) -p i (X) ≤ C   √ ∆ + K ∑ i=1 E X 1 n n-1 ∑ k=0 b i -b * i ) 2 (X k∆ ) 1/2   ≤ C 1 √ ∆ + b -b * T .
where C, C 1 are positive constants which depend on T, K, C b and on the constants in the Assumptions 7, 8.

Therefore, if we manage to build consistent estimator b of b * w.r.t. . T , the resulting plug-in classifier ḡb is also consistent. In [START_REF] Denis | Consistent procedures for multiclass classification of discrete diffusion paths[END_REF], we investigate the parametric setting and provide theoretical guarantees for estimator of the drift defined as the minimizer of a contrast function based on the Gaussian log-likelihood approximation. We will discuss the extension to the nonparametric case later (see Section 4.3.3). In the next section, we present results obtained for classifiers defined as empirical risk minimizers which take advantage of Proposition 4.2.

Classification procedure based on emprirical risk minimization

In [START_REF] Cadre | Supervised classification of diffusion paths[END_REF], the empirical risk minimization procedure is used in the context of binary classification where the features come from continuous diffusion sample paths and are discriminated by their drift. Following the same idea, we investigate the case where the estimator of b * is defined as an empirical risk minimizer. To this end, we assume that b * belongs to a set of functions B. Besides, for b ∈ B, we introduce the empirical risk of a discrete observations classifier g b by

R(g b ) = 1 N N ∑ j=1 1 {g b (X (j) ) =Y (j) } .
Now, assume that there exists an ε-net B ε ⊆ B with respect to the norm . T . We define the estimator b

ε = ( b ε 1 , . . . , b ε K ) as b ε ∈ arg min b∈B ε R(g b ). (4.3)
As mentioned in Chapter 1, this estimator can not be considered in practice. One of the contribution provided in [START_REF] Denis | Consistent procedures for multiclass classification of discrete diffusion paths[END_REF] is to bypass this issue by proposing a procedure which involves a convex surrogate of the minimization problem defined in Equation ( 4.3). The procedure is described in Section 4.3.1. However, from a theoretical perspective it is always interesting to study the properties of b ε , at least as a benchmark. The following theorem establishes the rates of convergence of the classification procedure g b ε w.r.t. its excess risk.

Theorem 4.1. Assume that there exists u > 2+u) . The empirical risk minimizer satisfies

0, C > 0 such that log(Card(B ε )) ≤ Cε -u . Let ∆ = O N -2/(2+u) and ε ∝ N -1/(
E E (g b ε ) ≤ C N 1/(2+u) .
where C is a positive constant which depends on T, K, and on the constants in the Assumptions 7 and 8.

The proof of this result relies on Proposition 4.2 and classical tools of empirical process. It shows that, provided that the time step ∆ is sufficiently small, the obtained rates of convergence is the same to the one obtained when the feature X belongs to R. This rate of convergence is obtained in [START_REF] Cadre | Supervised classification of diffusion paths[END_REF]

F β = b ∈ C β , ∀j ∈ Z, i = 0, . . . , β sup [j,j+1[ d i b dx i ≤ ψ(|j|), |b(x)| ≤ ψ(x) .
Application of the result given in [START_REF] Van Der Vaart | Consistency for the least squares estimator in nonparametric regression[END_REF] (see the proof of Theorem 2.7.1) shows that Theorem 4.1 can be applied with B = (F β ) K with u = 1/β. In this case, we obtain that the rate of convergence of the empirical risk minimizer is of order of N -β/2β+1 where β is the smoothness of drift functions b * i . Hence, we obtain similar rate as in the classical classification setting [START_REF] Yang | Minimax nonparametric classification: Rates of convergence[END_REF].

One-versus-All approach

In this section, we focus on the case where the set B is a parametric family of drift functions. The set B is defined as follows

B = {(b(θ i , .)) i∈Y , ∀i ∈ Y, θ i ∈ Θ} ,
where Θ ⊂ R d is compact and for each θ ∈ Θ, x → b(θ, x) is a real valued function which satisfies Assumptions 7, 8. Moreover, we assume that the function b is known. For each i ∈ Y, we denote the drift functions by b *

i (x) := b(θ * i , x), θ * i ∈ Θ (and π * = π b θ * ). Furthermore, for θ = (θ 1 , . . . , θ K ) ∈ Θ K , we denote the vector (b(θ i , .)) i∈Y by b θ = (b θ 1 , . . . , b θ K ).
Finally, for θ ∈ Θ K , we also define θ = max i∈Y θ i ∞ . We consider the following assumption Assumption 9. Function b is Lipschitz-continuous with respect to θ ∈ Θ:

|b(θ, x) -b(θ , x)| ≤ C (1 + |x|) θ -θ ∞ .
This assumption implies that for θ, θ ∈ Θ, we have

b(θ, •) -b(θ , •) T ≤ C θ -θ ∞ ,
for a constant C depending on T. •

model 3 Polynomial b(θ, x) = -(x -θ) 3 -(x + θ) 3 , x 0 = 4 • model 4 Hyperbolic b(θ, x) = -θx/ √ 1 + x 2 , x 0 = 4
We compare the results on the design: θ * = {1, 2, 4} for model 1, 2, 4, and θ * = {1/4, 1/2, 1} for model 3. The models 1 and 2 are widely used in practical applications, and they satisfy all the assumptions required for our theoretical results, while the model 3 does not fulfill the Assumption 7, illustrating the robustness of the classification procedure. The model 4 is widely used in mathematical finance to model log-returns of assets prices in stock markets. Figure 4.1 displays some trajectories generated according to the model 1 (Additive). At first sight, without the knowledge of the labels, it seems to be difficult to assign a class to each trajectory. It illustrates the difficulty of this classification problem (see Table 4.

1).

As a benchmark, we also evaluate the procedure provided in [START_REF] Denis | Consistent procedures for multiclass classification of discrete diffusion paths[END_REF] based on the contrast estimation which is referred as MLE. This procedure relies on the parametric estimation of parameter θ k . The procedure based on the one-versus-all strategy is referred as OVA g θ with θ given in Equation (4.4). We fix n ∈ {50, 250}, ∆ = 1/n, N = 500 For each model we provide an evaluation of the misclassification risk of the two classification procedures by using the Monte-Carlo method over 100 repetitions. Furthermore, the risk of the Bayes rule is evaluated independently with a sample of size 10000. The results are summarized in Table 4.1 .

Note that under the considered assumptions, the process (X t ) t∈[0,T] admits a transition density (t, x) → p(t, x 0 , x).

Finally, we assume that N ∈ N * independent discrete observations X 1) , . . . , X

(N)

coming from independent solutions X (1) , . . . , X (N) of (4.1) are available. We refer to the vector of observations X 1) , . . . , X N) as the learning sample.

We introduce some additional notations and then give key result on the transition density p. For a real valued function h defined on R, we denote h n,b the empirical integrated norm defined as:

h 2 n,b := E X 1 n n-1 ∑ k=0 h 2 (X k∆ ) ,
where E X is the expectation with respect to the law P X of the discrete path X defined by (4.5). Its standard L 2 -norm is denoted by h . Let us also introduce the following empirical norm

h 2 N,n := 1 Nn N ∑ j=1 n-1 ∑ k=0 h 2 X (j) k∆ .
The following lemma highlights the connection between the norms . n,b and .

Lemma 4.1. Under assumptions 7, and 10, there exists π 1 > π 0 > 0, such that for all y ∈ [0, 1] and n ≥ 4, we have

π 0 ≤ 1 n n-1 ∑ k=1 p(k∆, x 0 , y) ≤ π 1 .
This result is one the main tool for the study of the rates of convergence. Notably, for a function h such that supp(h) ⊆ [0, 1], we have h 2 ≤ 1 π 0 h 2 n,b .

Ridge estimator for drift function

In this section, we describe our regularized procedure which relies on a projection estimator based on the B-spline basis.

B-spline basis

. Let K N ∈ N * , A N , B N ∈ R, A N < B N , and M ∈ N * . Let us introduce the sequence of knots u = (u -M , . . . , u K N +M ) such that for i = 0, . . . , K N u i = A N + i (B N -A N ) K N , u -M = . . . = u -1 = u 0 = A N , and u K N = u K N +1 = . . . = u K N +M = B N .
We consider the B-splines functions (B i,M,u ) i=-M,...,K N -1 of degree M associated to the knot vector u. The B-splines functions are defined as follows (see for instance Györfi et al., 2006, and references therein).

where for h ∈ S K N ,L N ,M ,

γ N,n (h) := 1 N n N ∑ j=1 n-1 ∑ k=0 Z (j) k∆ -h(X (j) k∆ ) 2 , Z (j) k∆ := X (j) (k+1)∆ -X (j) k∆ ∆ .
Note that the resulting estimator is then defined as b N,n (. .) where the vector a = t ( â-M , . . . , a K N -1 ) ∈ R K N +M is the ridge estimator (see [START_REF] Hastie | LAN property for ergodic diffusions with discrete observations[END_REF]: a = arg min

) = ∑ K N -1 i=-M a i B i,M,u (
a 2 2 ≤(K N +M)L N Z -Ba 2 2 ,
where the vector Z = t (Z (j) ∆ , . . . , Z

n∆ , j = 1, . . . n) belongs to R Nn and the matrix B = (B i,M,u (X j )) j,i ∈ R (Nn)×(K N +M) , with X j = t (X (j) ∆ , . . . , X (j) n∆ ). This problem has a unique solution which ensures that the resulting estimator b N,n is always well defined. Moreover, this procedure offers attractive numerical properties.

Optimal rates of convergence

This section is dedicated to the study of the rates of convergence of the estimator b N,n . We assume that x 0 ∈ (0, 1). The rate of convergence of the estimation procedure is studied over the class of Hölder functions. Upper bound. In order to derive optimal rate of convergence, we consider a slightly modified version of the estimator defined in Equation (4.7). The truncated estimator is defined as follow

b L N N,n (x) := b N,n (x) if | b N,n (x)| ≤ √ L N , sgn( b N,n (x)) √ L N if | b N,n (x)| > √ L N .
We remind the reader that L N is the multiplicative factor that controls the bound on the Euclidean norms of the parameter coefficients a for all functions belonging to S K N ,L N ,M (see Equation The proof of the Theorem follows the same lines of Theorem 2.8 in [START_REF] Tsybakov | Introduction to nonparametric estimation[END_REF] except for the control of the Kullback-Leibler divergence. In Theorem 4.4, this control relies on the Girsanov formula. Hence, Theorem 4.4 and Equation (4.8) establish that the estimator b L N N,n is optimal in the minimax sense. However, the choice of K N depends on the regularity β of the function b which is unknown in practice.

Adaptive estimator. We propose an adaptive estimator based on a penalized contrast. To alleviate the notations, the parametes K N is denoted by K. Besides, in order to highlight the dependency on K, the estimator b L N N,n is denoted b K (and we choose L N = log(N)). Our adaptive procedure relies on the dyadic B-splines. That is to say, we assume that K belongs to K = {2 p , p = 0, . . . , p max } with 2 p max ≤ N/ log 2 (N). Hence, this particular choice ensures that the spaces S K,M,u are nested (for K < K , S K,M,u ⊂ S K ,M,u ) which is an important property in light of the proof of Theorem 4.5. We define the following estimator K = arg min K∈K γ N,n ( b K ) + pen(K) , (4.9) and then consider the estimator b K defined as the minimizer of a penalized contrast. To penalize the complexity of S K,L,M , we choose a penalty term pen(K) ≥ 44 log 2 (N)(K+M)

N for N large enough. Now, we state the following result

+ pen(K) + C N ,
where C is a positive constant depending on σ 1 , π 0 , T, M and R.

This result shows that the estimator b K achieves the bias-variance compromise over the model collection (S K,L,M ) K∈K . In particular, whenever b ∈ Σ(β, R), with β ≤ M + 1, the estimator b K reaches the optimal rate up to a logarithmic factor. Note that the penalty term can be chosen equal to 44 log 2 (N)(K+M) N . However, in practice it is better to consider pen(K) = c log(N) 2 (K+M)

N

where the constant c is calibrated through numerical experiments.

Numerical experiments

In this Section, we briefly illustrate the performance of the proposed estimator. We choose n∆ = T = 1 with n = 100. The sample size N is fixed to 1000. Our estimators are based on the cubic (M = 3) B-spline basis. We restrict our investigation to the set K = {2 p , p = 0, 1, 2, 3, 4, 5} (thus dim(S K,M,u ) = 2 p + 3, p = 0, [START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF][START_REF] Chzhen | Minimax semi-supervised confidence sets multi-class classification[END_REF][START_REF] Denis | Regression with reject option and application to kNN[END_REF][START_REF] Chzhen | Fair Regression with Wasserstein Barycenters[END_REF][START_REF] Chzhen | Fair Regression via Plug-in Estimator and Recalibration via Statistical Guarentees[END_REF]. Finally, according to our theoretical results, the constant coefficient L N is chosen equal to log(N). After numerical investigations which are detailed in [START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF], we fix c = 0.01.

We consider the three following models to illustrate the accuracy of the estimator. 4.2 displays ten realizations of the estimators b K on the three models. We can see that these estimates perform quite well. Regarding the chosen dimension, for models 1,2 the value K = 1 is mostly chosen while K = 8 is mostly selected for model 3. This is not surprising since the drift functions of model 1,2 are quite simple whereas the multimodal aspect of the drift function of model 3 requires to select larger K. Hence, for model 3 the estimation of b is more challenging.

Note that, we also investigate in [START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF] the estimation of b without restriction on the estimation interval. In this case, it is natural to build our procedure on the random interval defined as min ( X1 , . . . , XN , max ( X1 , . . . , XN . In this case, we also show that the estimation procedure has good performance.

Discussion and perspectives

In Section 4.4, we provide a new procedure to estimate the drift function of homogeneous diffusion process in the i.i.d. framework. It is the starting point of the study of a plug-in classification procedure for the mixture model defined by Equation (4.1) in the nonparametric setting. This work is a part of the Ph.D. thesis of E. Ella Mintsa whom I co-supervise with C. Dion-Blanc and V.C. Tran.

Let me briefly present the main idea of the strategy followed by E. Ella-Mintsa. Considering the result obtained in Proposition 4.2, a first step consists in the construction of Indeed, when the s.d.e. is driven by b * j with j = k, the estimator bk may be not consistent. Furthermore, our result holds only for the estimation of the drift function over a compact interval. To bypass these difficulties, the strategy is to obtained a similar result as Lemma 4.1 for a compact interval [-A N , A N ], with A N → +∞. Importantly, the dependency of the constants π 0 and π 1 w.r.t. A N should be carefully evaluated. In this case, for each t ∈ [0, T], P (|X t | ≥ A N ) is easily controlled by the Markov Inequality, and then one can obtain the following bound on the excess risk

E E ( ḡb ) ≤ C √ ∆ + R A N + C A N K ∑ k=1 E bk -b * k [-A N ,A N ] ,
where R A N → 0 and C A N is a positive constant depending on π 0 and π 1 . Hence, the control of C A N will allow to derive the consistency of the plug-in classifier.

The other line of the extension of the results provided in this chapter is to consider the case where the distribution of Y and the coefficient diffusion σ are unknown. While the estimation of the weights of the mixture is not really a difficult task as it can be easily handled by considering the empirical distribution of Y, the estimation of σ is more intricate. To tackle this problem, E. Ella Mintsa proposes a version of the estimator described in Section 4.4 dedicated to the estimation of σ.

Another extension is to investigate a classification procedure based on the empirical risk minimization principle. In this case, we can consider a similar procedure as the one described in Section 4.3.1 where the minimization is performed over the set S K N ,L N ,M defined in Equation (4.6).

An important part of the study of these procedures will be also to evaluate their numerical performance. In particular, a comparison with other classification procedures for functional data such as depth classification or recurrent neural networks will highlight the relevance of the proposed approach.

Lastly, the generalization of the initial model is an important guideline for further research. The extension to the case of inhomogeneous diffusions as well as considering the case of multidimensional diffusions will cover a broader class of possible applications.

Figure 2 . 2 :

 22 Figure 2.2: Importance of splitting in case D U N = ∅. Set-valued classifier Γ-sp s uses the same labeled data twice. Set-valued classifier Γ+sp s splits labeled data to force independence.

  Figure 2.2-right displays that the setvalued classifier Γ-sp s

2 Figure 2 . 3 :

 223 Figure 2.3: Distribution of the size of Γ+c s in a single outcome of the experiments across various values of s.

  the labeled D L n and an unlabeled D U N datasets of size n and N respectively to train the set-valued classifiers. A third labeled dataset of size M is used to compute error and size. We set the sizes of the samples as n = 200, N = 100 and M = 223 for the Forest dataset, and n = 1000, N = 200 and M = 400 for the Plant one. The empirical error and expected size is computed by cross-validation.

Proposition 4 . 1

 41 is a key result and is the bedrock of the classification procedures presented in this chapter. Indeed, it highlights the dependency of the Bayes classifier w.r.t. the unknown function b * . It naturally suggests that consistent classification rule can be derived from estimator of b * .

  Finally, for any function b, we then naturally define the discrete observations classifier g b by g b (X) := arg max

Proposition 4 . 2 .

 42 Moreover, for a function b = (b 1 , . . . , b K ), we set b T := max i∈Y b i T . Let b = (b 1 , . . . , b K ). Assume that there exists C b > 0 and γ

Figure 4 . 1 :

 41 Figure 4.1: Illustration of the classification problem with 3 classes (blue, green and magenta) for the three different values of θ * ) for model Additive with n = 100, N = 100.

Assumption 11 .

 11 For β ∈ [1, M + 1], and R > 0, the restriction b := b |[0,1] of b to [0, 1] belongs to the Hölder ball Σ(β, R): the function b is l = β times differentiable on (0, 1) and its derivative b(l) satisfies ∀x, y ∈ (0, 1), b(l) (x) -b(l) (y) ≤ R |x -y| β-l .

Theorem 4 . 4 . 2 ≥ c 1 N

 4421 (4.6)). First, forN large enough, since b is bounded, b ∞ ≤ √ L N which implies bb L N N,n b ≤ bb N,n b . Therefore, the consistency of b N,n implies the consistency of b L N N,n . Moreover, let us notice that b N,n ∞ < (K N + M)L N while the truncated estimator b L N N,n satisfies b L N N,n ∞ < √ L N .This property is particularly important in Theorem 4.3 to reduce the order of the variance term with respect to K N . Grant Assumptions 7, an 10, and 11. There exists two constants c 1 , c 0 > 0 such that for N large enough and b constructed from (X 1 , . . . , X N ), sup b : b∈Σ(β,R) E bb -2β/(2β+1) ,

Theorem 4 . 5 .

 45 GrantAssumptions 7,[START_REF] Denis | Confidence sets with expected sizes for Multiclass Classification[END_REF][START_REF] Ouni | Contextual ranking by passive safety of generational classes of light vehicles[END_REF] Assume that L N = log(N) and∆ = O(1/N). The estimator b K of b satisfies E b Kb 2 ≤ 2 inf

• model 1

 1 b(x) = 1x, σ(x) = 1 • model 2 b(x) = (1x 2 )(-2atanh(x)x), σ(x) = 1x 2 • model 3 b(x) = 0.1(-sin(2πx) + cos(2πx) + 16 sin(3πx) -5 cos(3πx)), σ(x) = 1The first model is widely used diffusion models. The model 2 possess a non constant diffusion coefficient and do not satisfy the ellipticity assumption 7. Finally, The model 3 has a multimodal drift function. It requires to explore more possible values of K (larger dimension).We focus on the estimation of b = b1[-1,1] . Note that for model 2 we have b = b.

Figure

Figure 4 . 2 :

 42 Figure 4.2: The three graphs show the three models 1-2-3 (top to bottom) and on each of them the true drift function in blue (dark) and 10 estimates b K in green (light grey), on the compact interval [-1, 1]

  . For each set-valued classifier, the empirical error rate P ( Γs ) and empirical expected size S( Γs ) are evaluated by crossvalidation. It satisfies all the required assumptions and hence Theorem 2.2 is applicable to this classifier. Figure2.1-right-bottom displays the expected size of Γ+c s for s = 2. It highlights that even with a moderate unlabeled sample size N, the set-valued classifier has the prescribed expected size. In addition, when we compare the values of the errors P( Γ+c

	s	(builded by using the splitting of the sample), and	Γ-sp s	(without splitting). Note
	that the randomization is used to build	Γ+sp s	and	Γ-sp
	General observations. Let us focus on the set-valued Γ+c s	(Continuous) which is the
	semi-supervised method presented in Section 2.3.1.

s (builded with the random perturbation), Γ-c s (builded without the random perturbation), Γ+sp s s ) in all the boxes in Figure 2.3, we observe that this error is indeed decreasing w.r.t. s. It is important to notice

  18 whereas

				Forest (K = 4)
					s-set
	s		rforest	softmax reg	svm	kknn	CV
	2 P	0.02 (0.02)	0.06 (0.02)	0.02 (0.01) 0.05 (0.03) 0.02 (0.01)
		S	2.00 (0.09)	2.00 (0.08)	2.00 (0.09) 2.00 (0.08) 2.00 (0.08)
				Plant (K = 100)
					s-set
	s		rforest	softmax reg	svm	kknn	CV
	2	P	0.18 (0.03)	0.77 (0.02)	0.32 (0.04) 0.20 (0.03) 0.17 (0.03)
		S	2.00 (0.09)	2.02 (0.18)	1.99 (0.10) 2.00 (0.08) 2.00 (0.08)
	10 P	0.02 (0.01)	0.42 (0.04)	0.03 (0.02) 0.08 (0.03) 0.02 (0.01)
		S	9.95 (0.38)	10.06 (0.58)	9.98 (0.22) 9.98 (0.23) 9.96 (0.37)

Table 2 . 1 :

 21 For each dataset, we derive the estimated error P and size S of the different set-valued classifiers w.r.t. s. We compute the means and standard deviations (between parentheses) over the repetitions. For each s, the set-valued classifiers are based onfrom left to right-rforest, softmax reg and svm, kknn and CV which are respectively the random forest, the softmax regression, support vector machines, k nearest neighbors and the aggregation procedure. Top: the dataset is the Forest -the dataset is the Plant.

Table 3 . 1 :

 31 Performance (accuracy & unfairness) of the methods for all datasets and classifiers. We report the means and standard deviations over the 30 repetitions. Colored values highlight fairness.

  in the context of binary classification with continuous time observations. Hereafter, we provide an example of set B for which Theorem 4.1 applies. Define ψ(x) := C 1 (1 + |x|) and C 1 ≥ C 0 (with C 0 given in Equation (4.2)). Let β ≥ 1 and consider

We can arrive to a similar conclusion from (Bobkov and Ledoux,

2016, Theorem 5.11)

Classification procedure. We derive a classification procedure based on the one-versusall approach. It involves a convex surrogate of the minimization problem defined in Equation (4.3). Hence, we consider the square loss and apply the methodology described in Chapter 1. Let f(•) = ( f 1 (•), . . . , f k (•) a score function, its associated L 2 risk is

In this case, we recall that

In view of the form of the optimal score function f * , we naturally define the estimator θ of the true parameter θ * θ ∈ arg min

with R 2 the empirical counterpart of R 2 . The following theorem establishes the consistency of the proposed procedure.

Theorem 4.2. Assume that Θ = [0, 1] d and that there exists α ≥ 2 such that ∆ ∝ O(N -α ).

Under Assumption 9, the classification procedure g b θ given by (4.4) satisfies,

We can note that up to the logarithmic factor, we obtain the usual parametric rate of convergence which is of order of N -1/2 . Interestingly, if we consider θ ∈ arg min

with Θ N a 1/N-net of Θ K , one can show that the rate of convergence is also of order N -1/2 . Hence, from a theoretical point of view, the use of convex surrogate does not degrade the performance of the classification procedure when α ≥ 2.

Numerical evaluation

In this section, we provide a short simulation study to evaluate the performance of the procedure described in Section 4.3.1. Let us describe the models under consideration for our numerical experiments. We fix K = 3, π k = 1/K and σ = 1. We consider the following examples First of all, note that model 1 and model 4 seem to be more tricky for the misclassification risk. This is due to the fact that the classes generated by θ * 1 and θ * 2 are much overlapped. On the contrary, the classification problem involved by model 2 is more easier. Second, all the classification procedures perform well. Indeed, the evaluation of the misclassification risk are closed to the Bayes risk with small variances. Furthermore the two procedures have similar performance.

A first conclusion

This section is dedicated to a preliminary discussion regarding the presented results. The contribution of [START_REF] Denis | Consistent procedures for multiclass classification of discrete diffusion paths[END_REF] should be viewed as a first step of the study of the problem defined by Equation (4.1). Notably, we show that standard techniques of statistical learning can be successfully apply to the mixture diffusion model. We establish, provided that the time step ∆ is sufficiently small, that the classification procedure presented in Section 4.3 achieves standard rates of convergence. However, results provided in [START_REF] Denis | Consistent procedures for multiclass classification of discrete diffusion paths[END_REF] mainly focus on the parametric setting and require that the weights of the mixture as well as the diffusion coefficient are known.

A second step of our research on this topic has been to focus on the study of plugin procedures in the nonparametric setting including the estimation of the weights and the diffusion coefficient in the procedure. In light of this, the objective is to study a procedure where drift functions b k are separately estimated by a nonparametric method. Naturally, the first challenge is to focus on the estimation of the drift function within the i.i.d. framework. Indeed, this problem is usually tackled in the setting where the observation consists in a single path. In this context, an estimator of the drift function is evaluated when the horizon time T tends to infinity and under the assumption that the underlying process is ergodic. On the contrary, in our framework the horizon time is fixed and we do not require ergodicity property. The asymptotic w.r.t. T is then replaced by the asymptotic with respect to the learning sample. Clearly, these two settings are different and classical approaches can not be considered for the estimation of the drift function under the i.i.d. framework.

Estimation of the drift function under i.i.d. framework: a first step toward the plug-in procedure

In this section, we focus on the following model

where x 0 ∈ R is known, and (W t ) t≥0 denotes a standard Brownian motion.

The estimation of the drift function of a diffusion process from a single path is a well known problem (see for instance [START_REF] Kutoyants | Statistical Inference for Ergodic Diffusion Processes[END_REF]. More precisely, one can cite, (Yoshida, 1992;Gobet, 2002) for the case of continuous ergodic diffusions, (Bibby and Sørensen, 1995;Kessler, Sørensen, et al., 1999) for martingale estimation functions, (Gobet, Hoffmann, Reiß, et al., 2004) in the low frequency context, and [START_REF] Hoffmann | Estimating equations based on eigenfunctions for a discretely observed diffusion process[END_REF][START_REF] Dalalyan | Sharp adaptive estimation of the drift function for ergodic diffusions[END_REF][START_REF] Comte | Penalized nonparametric mean square estimation of the coefficients of diffusion processes[END_REF][START_REF] Schmisser | Penalized nonparametric drift estimation for a multidimensional diffusion process[END_REF] in the nonparametric context. In the Bayesian literature, the asymptotic properties of minimum contrast estimators are studied for example in [START_REF] Meulen | Consistent nonparametric Bayesian inference for discretely observed scalar diffusions[END_REF][START_REF] Gugushvili | Consistent non-parametric Bayesian estimation for a time-inhomogeneous Brownian motion[END_REF][START_REF] Koskela | Consistency of Bayesian nonparametric inference for discretely observed jump diffusions[END_REF].

Nevertheless, it seems that very few works investigate the estimation of the drift function from a sample of i.i.d. observations (diffusion paths) when the horizon time T is assumed to be fixed. In fact, up to our knowledge, only [START_REF] Comte | Nonparametric drift estimation for i.i.d. paths of stochastic differential equations[END_REF] and Della Maestra and Hoffmann (2021) deals with this framework. However, the work of Della Maestra and Hoffmann (2021) focuses on the more general setting of stochastic system of N interacting particles and does not directly handle the i.i.d. framework. The closest contribution to ours is provided in [START_REF] Comte | Nonparametric drift estimation for i.i.d. paths of stochastic differential equations[END_REF] where the authors consider a least squares contrast estimator (based on continuous observations). In order to ensure the stability of the estimator, the authors propose to insert a cutoff function. More precisely, the estimator is set to the zero function according to some threshold which depends on the dimension of the considered space of approximation. This procedure may reduce the dimension of the spaces of approximation on which the resulting estimator is non trivial and can lead to some limitations in practice. As an alternative strategy, we propose in [START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF] to build a regularized estimator based on a ridge constraint.

Assumptions and notations

We present results obtained in [START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF] for the estimation of the drift function on a compact interval that we assume to be [0, 1] for simplicity. That is to say, we focus on the estimation of b(.) = b(.)1 [0,1] (.).

We consider the assumptions detailed in Section 4.1. We also assume that Assumption 10. σ belongs C 2 b (R).

Definition 4.1. the B-spline function of degree with knots vector u is recursively defined for all x ∈ R by, B i, ,u (x) = 1 [u i ,u i+1 ) (x), for = 0, and i = -M, . . . , K N + M -1, and

for = 0, . . . , M -1, and i = -M, . . . , K N + Ml -2. We use the convention 0/0 = 0.

Note that the B-spline functions are positive functions. According to the choice of the knot vector u, the B-spline functions are zero outside [A N , B N ]. Besides, these functions are linearly independent even though their supports are not disjoint. The main advantage of these piecewise polynomial functions is that they satisfy some global smoothness conditions. This kind of attractive property is particularly interesting when we want to build smooth estimates. Finally, the B-spline space S K N ,M,u is defined as

Constrained estimation based on the B-spline basis. Since we focus on the estimation of b on [0, 1], we set A N = 0, and B N = 1. For L N > 0, we define the constrained subspace

i=-M a i B i,M,u for which we ensure uniform boundedness on the coefficients a i . Then, in view of the properties of the Bspline, functions of S K N ,L N ,M are bounded w.r.t. • ∞ and • . Note that the choice of the tuning parameter in the constraint ensures a control of the bias term. Indeed, assume that b ∞ ≤ √ L N , then there exists h ∈ S K N ,L N ,M such that

We consider the estimator b N,n defined as the minimizer of a least square contrast b N,n ∈ arg min

Proposition 4.3. Grant Assumptions 7, and 11. For N large enough, the following holds

where C > 0 is a constant depending only on σ 1 , π 0 , T, M, and R.

The obtained bound is composed of three terms. The first one, which relies on the spline approximation properties, gives the order of the bias under the assumption that the function b is Hölder. The second is the variance term which is of order (K N + L N )/N. Note that the bound on the variance term relies on the equivalence between the empirical norm and the L 2 -norm over [0,[START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF]. In [START_REF] Denis | A ridge estimator of the drift from discrete repeated observations of the solution of a stochastic differential equation[END_REF], it is shown that without the ellipticity assumption the control of the variance term is of order ((K N + L N )/N)

where C > 0 is a constant depending only on σ 1 , T, M and R.

From this result, one can see that the rate of convergence is, up to a logarithmic factor, the optimal nonparametric rate in the regression setting [START_REF] Tsybakov | Introduction to nonparametric estimation[END_REF]. Indeed, since β ≥ 1, for K N = N/log 2 (N)

1/(2β+1)

∈ K N , we obtain

. (4.8) This inequality shows that, regarding to the L 2 -risk, the problem of estimating the drift function on a compact set based on repeated observations is equivalent to the estimation of a function in the regression setting (provided that the time step ∆ is small enough).

Let us comment the logarithm factors. The first log(N) is due to the fact that there is no prior knowledge on the bound of b ∞ . The second one is due to the control of the supremum of an empirical process over the subset S K N ,L N ,M .

Lower bound. We establish a lower bound on the L 2 -risk for the Hölder class of functions Σ(β, R) with regularity parameter β, defined in Assumption 11.