A partir de ces relations, il est aussi possible de lier la complexité de Rademacher à la dimension combinatoire en passant par les nombres de recouvrement. Une relation réciproque existe également.

Un type particulier de résultat, une décomposition de mesure de capacité, borne la capacité d'une classe composite à partir des capacités de ses classes composantes. Dans le cadre de la discrimination multi-classe, ce type de borne permet d'estimer une mesure de capacité multiclasse à partir d'un ensemble de capacités bi-classes, et ainsi de rendre explicite la dépendance au nombre de catégories. Les relations entre les mesures de capacité et leurs décompositions sont au coeur de la théorie des bornes sur l'erreur de généralisation dans ce contexte.

La performance en classification d'un modèle est évaluée à partir d'une fonction de perte.

Que ce soit dans le cas binaire ou multi-classe, lorsque la fonction de perte est l'indicatrice de mauvais classement classique, la convergence uniforme est bien étudiée. Mais lorsque la fonction de perte possède une certaine régularité, comme la continuité lipschitzienne, certaines questions restent ouvertes. Dans cette thèse, nous nous concentrons sur les fonction de perte à marge lipschitziennes. Indépendamment de la fonction de perte utilisée, les bornes de généralisation de base impliquent deux types de mesures de capacité : les nombres de recouvrement et la complexité de Rademacher. Les premiers résultats sur les nombres de recouvrement pour le problème classique de Glivenko-Cantelli remontent aux travaux de Pollard [68]. Bartlett et Long [12] ont amélioré le résultat de Pollard concernant les classes de fonctions à valeurs réelles et fourni l'estimation de la complexité de l'échantillon, c'est-à-dire la taille de l'échantillon suffisante pour que la convergence uniforme ait lieu. Dans le cas multi-classe, lorsque la fonction de perte est lipschitzienne, contrôler la déviation uniforme directement par un nombre de recouvrement est une question ouverte. Contrairement aux nombres de recouvrement, la complexité de Rademacher fut introduite relativement récemment en théorie de l'apprentissage. Pour les classifieurs multi-classes à marge, Koltchinskii et Panchenko [47] fournissent une borne sur l'erreur dans laquelle ils décomposent la complexité de Rademacher pour obtenir une dépendance explicite au nombre de catégories. Kuznetsov et al. [53], ainsi que Maurer [57], améliorent la dépendance quadratique de ces travaux vi schéma (4), les résultats obtenus au niveau de la fat-shattering dimension se propagent via la borne combinatoire et le chaînage. Dans cette thèse, nous étudions tous ces cheminements et niveaux de décomposition en suivant le plan ci-dessous. Dans le Chapitre 1, nous introduisons le cadre théorique de nos travaux. Plus précisément, nous décrivons le cadre probabiliste de l'apprentissage, donnons les définitions formelles des classifieurs multi-classes à marge, des fonctions de perte, des performances empiriques et en généralisation et des mesures de capacité discutées ci-dessus. Quelques connections entre les théorèmes limites classiques et ces mesures sont aussi présentées. Le Chapitre 2 s'attache ensuite à borner la probabilité de déviation uniforme entre la performance empirique et celle en généralisation en fonction d'un nombre de recouvrement. La taille de l'échantillon permettant d'obtenir la convergence uniforme est aussi ici estimée. Ce travail correspond à l'extension au cas multi-classe des travaux de Bartlett et Long [12]. Le Chapitre 3 donne une revue de la littérature sur les bornes de généralisation impliquant une complexité de Rademacher. Les résultats de décomposition pour cette mesure de capacité y sont ici mis en valeur et discutés au regard de l'impact qu'ils ont sur les dépendances aux paramètres d'intérêt. Le Chapitre 4 relie la complexité de Rademacher à l'entropie métrique et considère la décomposition de cette dernière. En particulier, nous étudions comment le choix de la métrique influence le chaînage en termes de dépendance aux paramètres d'intérêt. Nous montrons ici que dans le cas extrême de la métrique L ∞ , il est possible d'améliorer la dépendance à C par rapport à l'état de l'art, cependant au dépend d'une légère détérioration de la dépendance à la taille de l'échantillon m. Ensuite, une nouvelle borne combinatoire est dérivée et nous montrons comment celle-ci permet d'améliorer la dépendance à C sans modifier celles à m et au paramètre de marge γ. Le Chapitre 5 se concentre quant-à lui sur la décomposition au dernier niveau : celui de la fat-shattering dimension. Deux types de bornes sur cette mesure de capacité sont obtenus. En premier lieu, nous relions la fat-shattering dimension à la complexité de Rademacher et discutons les bornes sur cette dernière dédiées à certaines familles de classifieurs spécifiques. Dans un second temps, nous décomposons la fat-shattering dimension en passant par l'entropie métrique. Une nouvelle borne combinatoire est dérivée à partir de cette décomposition pour permettre d'améliorer encore la dépendance à C par rapport aux résultats du Chapitre 4 basés sur une décomposition au niveau des entropies métriques. Cependant, cette amélioration conduit à une légère détérioration de la dépendance à m. Le dernier chapitre résume l'ensemble de nos travaux et conclue en particulier que dans ix Résumé le contexte du schéma (4), il existe une interaction entre les dépendances à C et à m. Bien qu'il soit possible d'amliorer progressivement la dépendance à C en décomposant au niveau des entropies métriques ou de la fat-shattering dimension, cela implique une légère baisse du taux de convergence par rapport à m. Enfin, la thèse se conclut par quelques directions de recherche envisageables à la suite de ces travaux.

x

Résumé

Cette thèse s'intéresse à la théorie de la discrimination multi-classe. Nos travaux ont un intérêt particulier dans le contexte de la classification extrême. Celle-ci est de plus en plus rencontrée à l'ère du "big data" et consiste à associer un objet à une (ou plusieurs, dans les tâches à étiquettes multiples) catégorie parmi des dizaines de milliers, voire des millions [START_REF] Samy | Extreme Classification (Dagstuhl Seminar 18291)[END_REF]. Ainsi, il devient essentiel d'établir des garanties sur les performances qui "passent à l'échelle" en ce qui concerne le nombre de catégories. Une autre application possible de nos travaux concerne la sélection de modèle.

Dans cette thèse, nous nous concentrons sur la dérivation de garanties sur les performances sous des hypothèses minimales sur le modèle de prédiction aussi bien que les données.

Nos travaux sont basés sur la théorie statistique de l'apprentissage fondée par Vapnik et Chervonenkis à la fin des années soixante [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. Cette théorie fournit un cadre pour l'analyse qualitative et quantitative des performances en généralisation des modèles prédictifs. Les modèles prédictifs considérés ici sont des classifieurs multi-classes à marge. Ceux-ci incluent la plupart des classifieurs les plus populaires comme les réseaux de neurones [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF], les machines à vecteurs supports [START_REF] Cortes | Support-vector networks[END_REF] ou les plus proches voisins [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF]. Un classifieur multi-classe à marge implémente un ensemble de fonctions à valeurs vectorielles, avec une composante à valeur réelle par catégorie.

Un tel classifieur associe un objet à la catégorie pour laquelle la sortie de la fonction composante correspondante est la plus grande. Les sorties à valeurs réelles permettent de déterminer la performance d'un classifieur à partir des différences de fonctions composantes. Pour ces classifieurs, nous nous intéressons aux bornes sur la probabilité de mauvais classement et à leurs dépendances au nombre de catégories C, à la taille de l'échantillon m et au paramètre de marge γ. Ces bornes reposent d'une part sur la performance empirique du classifieur et d'autre part sur la notion de mesure de capacité.

La mesure de capacité d'un classifieur contrôle le taux de convergence uniforme de la performance empirique vers la performance en généralisation [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. Plus la capacité d'un classifieur est grande, plus la convergence sera lente. Dans cette thèse, nous travaillons avec des mesures de capacité sensibles à l'échelle : la complexité de Rademacher, les nombres de ------------→ dimension combinatoire [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF] la décomposition peut être reléguée aux niveaux suivants.

Plusieurs résultats de décomposition existent pour les nombres de recouvrement. Les décompositions de Zhang [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF] et Duan [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF] concernent des nombres de recouvrement basés sur une métrique spécifique, alors que celle de Guermeur [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF] est la généralisation de [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF] à toute métrique L p . Cette décomposition d'un nombre de recouvrement multi-classe conduit à un produit de nombres de recouvrement bi-classes : nombre de recouvrement (multi-classe)

décomposition ---------→ C k=1
k-ème nombre de recouvrement (5)

Guermeur [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF] a démontré qu'en combinant cette décomposition avec la borne combinatoire de Mendelson et Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], il est possible d'améliorer la dépendance au nombre de catégories jusqu'à une dépendance sous-linéaire.

En suivant toujours le chemin (4), une autre possibilité consiste à décomposer au dernier niveau : celui de la dimension combinatoire. La dimension combinatoire d'intérêt dans cette thèse est la "fat-shattering dimension". Les résultats de décomposition pour cette mesure de capacité sont dus à Bartlett [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF] et Duan [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF]. Le résultat de Duan concerne la fat-shattering dimension d'un produit de classes de fonctions composantes indépendantes et son extension au cas multi-classe est directe. Cependant, l'application de ce résultat dans le chaînage conduit à une borne avec une dépendance (super) linéaire au nombre de catégories. En fait, la décomposition de la fat-shattering dimension dans le contexte de la discrimination multi-classe et son impact sur les bornes de généralisation ne sont pas encore bien étudiés.

Dans cette thèse, notre but est de répondre à ces questions ouvertes et d'améliorer les garanties existantes. En particulier, dans le cadre du chemin (4), nous cherchons à améliorer la dépendance au nombre de catégories par rapport aux résultats de l'état de l'art mentionnés ci-dessus. Une part importante de ce travail concerne l'analyse de l'équilibre qui existe entre les dépendances à C et à m. Les principales contributions sont basées sur le raisonnement suivant.

vii

Résumé

Les nombres de recouvrement sont des quantités liées aux espaces métriques. Ainsi, la manière dont nous bornons ces mesures de capacité avec une borne combinatoire, ainsi que les résultats de décomposition, dépendent de la métrique utilisée. Dans cette thèse, nous travaillons principalement avec le logarithme des nombres de recouvrement, correspondant à l'entropie métrique.

Pour cette quantité, la relation [START_REF] Babbar | Machine Learning Strategies for Large-scale Taxonomies[END_REF] donne un schéma impliquant une somme : L'entropie métrique croît lorsque son échelle décroît. Sous différentes métriques, les échelles des entropies métriques bi-classes sont altérées de différentes manières par rapport au nombre de catégories. Plus la métrique est "forte", plus l'échelle est grande, et donc plus l'entropie métrique est petite. En particulier, dans le cas extrême de la métrique L ∞ , la dépendance à C de l'échelle disparaît. Une fois décomposée, nous relions chaque entropie métrique bi-classe à la fat-shattering dimension via une borne combinatoire :

k-ème entropie métrique à l'échelle borne combinatoire ------------→ k-ème fat-shattering dimension [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF] Pour chaque choix de métrique, nous avons une borne combinatoire différente. Ainsi, à ce niveau, le but est d'utiliser au mieux l'influence de la métrique sur la décomposition et la borne combinatoire. L'influence du choix de la métrique se propage ensuite au travers du chaînage pour impacter les dépendances à C, m et γ de la complexité de Rademacher dans le cadre du schéma [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF].

Si la décomposition est reléguée au niveau de la fat-shattering dimension, alors elle peut être réalisée grâce à la relation réciproque : il est possible de borner la fat-shattering dimension en fonction des autres mesures de capacité. En fait, il est plus aisé de dériver ces relations réciproques puisqu'elles s'obtiennent simplement à partir des définitions des mesures de capacité (dans le cas de l'entropie métrique, cela est vrai pour une métrique spécifique, la métrique L ∞ ) :

fat-shattering dimension définitions ------→     
entropie métrique complexité de Rademacher Dans le cas de l'entropie métrique, il est ensuite possible d'obtenir une décomposition de la fatshattering dimension par application des schémas (6) et [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]. En se basant sur cette chaîne d'inégalités, on remarque que le choix de la métrique impacte la décomposition de la fatshattering dimension. Il est aussi possible de relier la fat-shattering dimension à la complexité de Rademacher en combinant leurs définitions. Cela permet par la suite d'utiliser des bornes efficaces sur la complexité de Rademacher pour certains classifieurs spécifiques. A la vue du

Introduction

This thesis deals with the theory of multi-category pattern classification. Our work is especially relevant in the context of extreme classification. Extreme classification is a phenomenon of the big data era where the goal is to assign an object to one (or to multiple, in the multi-labelling tasks) of tens of thousands, possibly millions of categories [START_REF] Samy | Extreme Classification (Dagstuhl Seminar 18291)[END_REF]. Thus, it is of essential interest to derive performance guarantees that scale well with the number of categories. Another possible application of our work is in the model selection procedures. In the present thesis, we focus on deriving performance guarantees under minimal assumptions regarding the predictive model, as well as, the data.

Our work is based on the statistical learning theory founded by Vapnik and Chervonenkis in the late sixties [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. This theory provides a framework for qualitative and quantitave analysis of generalization performance of predictive models. The predictive models considered here are multi-category margin classifiers. These include most well-known classifiers such as neural networks [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF], support-vector machines [START_REF] Cortes | Support-vector networks[END_REF] and nearest neighbours [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF]. A multi-category margin classifier implements a set of vector-valued functions, with one real-valued component per category. Such a classifier assigns a pattern to the category for which the output of the corresponding function is the highest. The real-valued outputs allow one to assess the classification performance of a classifier based on the differences of component functions. For these classifiers, we are interested in the bounds on the probability of misclassification with explicit dependencies on the number C of categories, the sample size m and the margin parameter γ. These bounds rely on the empirical performance of a classifier as well as on the notion of capacity measure.

The capacity measure of a classifier controls the rate of uniform convergence of the empirical performance to the generalization one [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. The higher the capacity of the classifier, the slower the convergence. In this thesis, we deal with scale-sensitive capacity measures and consider the following ones: the Rademacher complexity, the covering numbers and combinatorial dimensions.

These measures are closely related: we can bound one in terms of another. Particularly, the following relationships are possible thanks to the chaining method and a combinatorial bound:

Rademacher complexity chaining -----→ covering numbers [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] covering number combinatorial bound ------------→ combinatorial dimension [START_REF] Samy | Extreme Classification (Dagstuhl Seminar 18291)[END_REF] From these relationships one can see that the Rademacher complexity can be related to the combinatorial dimension through the covering number. The converse relationships also exist.

A specific kind of result, a decomposition of capacity measure, upper bounds the capacity of a composite class in terms of that of component classes. In the multi-category classification setting, this kind of bound allows one to estimate the multi-class capacity measure from a set of bi-class ones thus making explicit the dependency on the number of classes. The relationships between the capacity measures as well as their decompositions are at the core of the theory of error bounds.

The classification performance of a model is assessed based on the use of a loss function.

Be it in the binary or multi-category classification setting, when the loss function used is the classical indicator loss function, the uniform convergence problem is well studied. On the other hand, when the loss function possesses some regularity, for instance, the Lipschitz continuity,

there still remain open questions. In this thesis, we focus on the Lipschitz continuous margin loss functions. Irrespective of the loss function used, the basic generalization bounds involve two types of capacity measures: the covering number and the Rademacher complexity.

Covering number result for the classical Glivenko-Cantelli problem can be traced back to the work of Pollard [START_REF] Pollard | Convergence of Stochastic Processes[END_REF]. Bartlett and Long [12] improved the covering number result of Pollard concerning the classes of real-valued functions, and provided the sample complexity estimate, i.e., the sample size sufficient for the uniform convergence to take place. In the multi-category case, when the loss function used is a Lipschitz continuous margin loss function, controlling the uniform deviation directly by a covering number is an open question.

Unlike the covering number, the Rademacher complexity has been introduced into the learning theory relatively recently. For multi-category margin classifiers, Koltchinskii and Panchenko [START_REF] Koltchinskii | Empirical margin distributions and bounding the generalization error of combined classifiers[END_REF] provide an error bound where they decompose the Rademacher complexity to obtain an explicit dependency on the number of categories. Kuznetsov et al. [START_REF] Kuznetsov | Multi-class deep boosting[END_REF], and Maurer [START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF] improve the quadratic dependency of the previous authors to a linear one. Indeed, in the general case with independent component functions, their decomposition result yields:

(multi-class) Rademacher complexity

the decomposition could be postponed to the subsequent levels.

Several decomposition results exist for covering numbers. The decompositions of Zhang [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF] and Duan [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF] concern covering numbers with specific metrics, while that of Guermeur [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF] is the generalization of [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF] to all L p -metrics. This decomposition of a multi-class covering number produces a product of bi-class ones:

(multi-class) covering number decomposition ---------→ C k=1 k-th covering number.

Guermeur [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF] demonstrated that combining this decomposition with the combinatorial bound of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], one can improve the dependency on the number of classes to a sub-linear one.

Still following the pathway (4), another possibility is to postpone the decomposition to the last level: that of a combinatorial dimension. The combinatorial dimension of interest in this thesis is the fat-shattering dimension. The decomposition results for this capacity measure are due to Bartlett [7] and Duan [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF]. Duan's result concerns the fat-shattering dimension of a product of independent function classes and its extension to the multi-class setting is straightforward. However, the application of this result in the chaining leads to a bound with a (super) linear dependency on the number of categories. In fact, the decomposition of the fat-shattering dimension in the context of multi-category classification and its impact on the error bounds are not well studied.

In this thesis, our goal is to fill in these gaps, and provide improved learning guarantees.

Particularly, in the context of the pathway (4), our goal is to improve the dependency on the number of categories over the aforementioned state-of-the-art results. An important part of this work is the analysis of the trade-off that exists between the dependencies on C and m. The main contributions are based on the following reasoning.

The covering number is a quantity related to metric spaces. Thus, the way we upper bound this capacity measure, i.e., a combinatorial bound, as well as the decomposition result depend on the metric used. In this thesis, we mainly work with the logarithm of the covering number which is the metric entropy. For this quantity, the relationship (5) turns into the following schema involving a sum:

(multi-class) entropy at scale decomposition ---------→ C k=1 k-th entropy at scale . (6)
The metric entropy grows as its scale decreases. Under different metrics, the scales of bi-class metric entropies are altered in different ways with respect to the number of categories. The "stronger" the metric the larger the scale of the metric entropy, consequently, the smaller the metric entropy. Particularly, in the extreme case of the L ∞ -metric, the dependency on C in the scales vanishes. Once decomposed, we relate each bi-class metric entropy to the fat-shattering dimension through a combinatorial bound:

k-th entropy at scale combinatorial bound ------------→ k-th fat-shattering dimension (7)
Now, for each choice of metric we have a different combinatorial bound. Thus, at this level, our aim is to make the best use of the influence of the metric on the decomposition and the combinatorial bound. The result of this choice then propagates through the chaining bound affecting the dependencies on C, m and γ of the Rademacher complexity as per schema 4.

If we postpone the decomposition to the level of the fat-shattering dimension, then, it can be realized thanks to the following converse relationships: one can upper bound the fat-shattering dimension in terms of the other two measures. In fact, deriving the converse relationships is simpler because they are obtained based on the definitions of these capacity measures (in the case of the metric entropy it is true for a specific metric, the L ∞ -metric):

fat-shattering dimension definitions ------→      metric entropy

Rademacher complexity

In the case of the metric entropy, one can obtain a decomposition of the fat-shattering dimension following the schemas ( 6) and [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]. Based on this chain of bounds, one can see that the choice of the metric influences the decomposition of the fat-shattering dimension. Similarly, one can relate the fat-shattering dimension to a Rademacher complexity based on the interplay between their definitions. We can then make use of the efficient upper-bounds on the Rademacher complexity for specific classifiers. In view of schema (4), the results obtained at the level of the fat-shattering dimension then propagates through the combinatorial bound and the chaining method. In this thesis, we study all these pathways and the levels of decomposition with the following outline.

In Chapter 1, we introduce the theoretical framework of our work. More precisely, we describe the probabilistic setting of learning, give formal definitions of margin multi-category classifiers, xiv loss function, empirical and generalization performances. We outline the connections between the classical limit theorems and the capacity measures.

In Chapter 2, we upper bound the probability of the uniform deviation between the empirical performance and generalization one in terms of a covering number. We then estimate the sample size required for the uniform convergence. This work corresponds to the multi-class generalization of that of Bartlett and Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF].

In Chapter 3, we give a literature review of generalization bounds involving a Rademacher complexity. We highlight the decomposition results for this capacity measure and discuss the impact they have on the dependencies on the basic parameters.

Chapter 4 relates the Rademacher complexity to the metric entropy and considers the decomposition of the latter capacity measure. Particularly, we study how the choice of the metric influences the chaining method in terms of the dependencies on the basic parameters. We show that in the extreme case of the L ∞ -metric, one can obtain a better than the state-of-the-art dependency on C, by slightly worsening that on the sample size m. Then, we derive a new combinatorial bound which, when applied in the chaining, improves the dependency on C over the state of the art, while not worsening those on m and the margin parameter γ.

In Chapter 5, we focus on the decomposition at the last level: that of the fat-shattering dimension. We obtain two kinds of upper bounds on this capacity measure. First, we relate the fat-shattering dimension to the Rademacher complexity and focus on the upper bounds on this capacity measure for specific families of classifiers. Second, we decompose the fat-shattering dimension by relating it to the metric entropy and estimating the last quantity. We derive a new combinatorial bound based on this decomposition of the fat-shattering dimension. We demonstrate that when applied in the chaining, this result improves the dependency on C over those obtained by the decomposition at the level of the metric entropy (the results of Chapter 4).

However, this is achieved at the cost of slightly deteriorating the dependency on m.

The final chapter summarizes our work. Particularly, this work concludes that in the context of schema (4), there is an interaction between the dependencies on C and m: although one can progressively improve the dependency on C through the decomposition of the metric entropy or the fat-shattering dimension, this slightly deteriorates the one on the sample size. We conclude the thesis by giving possible directions for future research.

Chapter 1

Preliminaries

This chapter deals with the mathematical framework of the present thesis. In Section 1.1, we introduce the notations used throughout. Section 1.2 describes the probabilistic setting. In Section 1.3, we give the formal definitions of margin multi-category classifiers, loss functions, empirical and generalization performances. The capacity measures used in this work are introduced in Section 1.4. Section 1.5 discusses the crucial relations between the statistical limit theorems and capacity measures.

Notation

R + denotes the set of strictly positive reals, and N * the set N \ {0}. For any t = (t i )

1 i d ∈ R d , t p = d i=1 |t i | p 1 p with p ∈ R + , and t ∞ = max 1 i d |t i |. l 2 is the space of all sequences t = (t i ) i 1 , t i ∈ R, such that i |t i | 2 < ∞. [ [ i, j ]
] stands for the set of integers from i to j. 1 A is the indicator function of an event A such that 1 A = 1 if A occurs and 0 otherwise. δ ij denotes the Kronecker delta function such that δ ij = 1 if i = j and 0 otherwise. t is the greatest integer less than or equal to t, t is the smallest integer greater than or equal to t. h • f denotes the composition of functions h and f . We distinguish the sample size m from the generic notation n which stands for a number of points in a set that need not be a realization of a random sample.

Probabilistic Framework

We denote the description space by X , and

Y = [ [ 1, C ]
] with C > 2 stands for the finite set of categories. We assume that X is a Polish space, that is, a separable completely metrizable topological space. Let A X and A Y be σ-algebras on X and Y, respectively. Let (X × Y, A X ⊗ A Y ) be a measurable product space, and let Z = X × Y. Assume that Z = (X, Y ) ∈ Z is a ran-dom pair with the law P on A X ⊗ A Y . P completely characterizes the pattern recognition problem. In the context of learning, the only available information about P is in an m-sample

Z m = (Z i ) 1 i m = ((X i , Y i )) 1 i m , a sequence of m independent copies of Z (distributed ac- cording to P m ).
In the sequel, (T , A T ) denotes the generic measurable space with probability measure P T on it. The empirical measure associated with P T is defined as follows.

Definition 1 (Empirical measure) For any t ∈ T , let δ t be the Dirac measure on A T such that

∀A ∈ A T , δ t (A) =      1, if t ∈ A; 0, otherwise.
Let a random variable T be an identity map on (T , A T , P T ). Let (T i ) 1 i n be a sequence of n copies of T . The empirical measure P n is the linear combination of Dirac measures concentrated on T i :

P n = 1 n n i=1 δ T i .
To sidestep the complications that might arise from the measurability of a supremum of an uncountable set, we need the following property.

Definition 2 (Image admissible Suslin [START_REF] Dudley | A course on empirical processes[END_REF]) A measurable space (T , A T ) is called a Suslin space if there is a Borel-measurable map from some Polish space onto T . A set F of real-valued functions on (T , A T ) is image admissible Suslin if (T , A T ) is a Suslin space and there exists a Suslin space (F , A F ) and a mapping F from this space onto F such that (t, f

) → F (f )(t) is measurable on (T × F , A T ⊗ A F ) .
In the following, F stands for a set of (A T , B R )-measurable functions f : T → R:

∀B ∈ B R , f -1 [B] = {t ∈ T : f (t) ∈ B} ∈ A T .
We assume that F and all classes of real-valued functions considered in the thesis are image admissible Suslin.

Margin Multi-category Classifiers

We consider margin multi-category classifiers that take their decisions based on a score per category and focus on those that implement classes of functions with values in a hypercube of

Margin Multi-category Classifiers

R C . Most well-known classifiers, such as neural networks [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF][START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF], multi-category support vector machines [START_REF] Guermeur | A generic model of multi-class support vector machine[END_REF][START_REF] Doğan | A unified view on multi-class support vector classification[END_REF], and nearest neighbors [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF] are margin multi-category classifiers, since they satisfy the following definition.

Definition 3 (Margin multi-category classifiers [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF])

Let G = C k=1 G k be a class of func- tions from X to [-M G , M G ] C with M G ∈ [1, +∞). For each g = (g k ) 1 k C ∈ G, dr g is a multi-category margin classifier such that for all x ∈ X , dr g (x) = argmax 1 k C g k (x), breaking
ties with a dummy category * .

Given g ∈ G, dr g misclassifies (x, y) if dr g (x) = y. The goal of the learning process is to minimize the probability of misclassification P (dr g (X) = Y ) over G. To characterize the classification performance of margin classifiers, we introduce the following functions that make use of the realvalued outputs of the component functions of g ∈ G. This definition could be traced back to the work of Koltchinskii and Panchenko [START_REF] Koltchinskii | Empirical margin distributions and bounding the generalization error of combined classifiers[END_REF].

Definition 4 (Class F G of margin functions) Let G be as in Definition 3. For any g ∈ G, the margin function

f g : Z → [-M G , M G ] is defined as follows: ∀(x, y) ∈ Z, f g (x, y) = 1 2 g y (x)-max k =y g k (x) .
We define F G = {f g : g ∈ G} .

Then, the misclassification probability is equal to P (f g (X, Y ) 0). Using the standard {0, 1}loss function the goal of learning can be reformulated based on the following definition.

Definition 5 (Risk L) Let G be as in Definition 3. Let φ : R → {0, 1} be the standard indicator loss function defined as φ(t) = 1 {t 0} . For any g ∈ G, its risk L(g) is

L(g) = E [φ (f g (Z))] = Z φ (f g (z)) dP (z) = P (dr g (X) = Y ) .
Clearly, to minimize the risk over G requires the knowledge of the distribution P . As P is unknown, one way to address this problem is to use the following simple induction principle [START_REF] Vapnik | Statistical Learning Theory[END_REF]:

instead of the risk L, minimize its empirical version L m evaluated on the basis of Z m . We obtain L m by replacing the law P in Definition 5 with its empirical counterpart P m .

Definition 6 (Empirical risk L m ) Let G be as in Definition 3 and φ be as in Definition 5. Let P m be the empirical measure supported on Z m . Then, the empirical risk of any g ∈ G is defined as:

L m (g) = Z φ (f g (z)) dP m (z) = 1 m m i=1 φ (f g (Z i )) .
Note that the standard indicator loss function has no sensitivity to the values of f g except for their signs. The loss functions introduced below, on the other hand, allow us to capture the nature of margin classification, and derive generalization bounds characterized through the margin parameter.

∀t ∈ R, φ γ (t) = 1 {t 0} + 1 - t γ 1 {t∈(0,γ]} .
Clearly, for a fixed γ ∈ (0, 1], φγ dominates φ γ which in its turn dominates the standard loss function. Moreover, φ γ is Lipschitz continuous with constant 1 γ . We observe that when φ γ is applied to f g , the values of the latter strictly above γ and below zero become irrelevant to the estimation of the classification accuracy. Taking benefit from this fact, we introduce truncated margin functions f g,γ by restricting the codomain of f g to [0, γ] for all g ∈ G.

Definition 8 (Class F G,γ of truncated margin functions [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]) Let F G be a class of functions satisfying Definition 4. Fix γ ∈ (0, 1]. For any f g ∈ F G , we define f g,γ : Z → [0, γ] as ∀(x, y) ∈ Z, f g,γ (x, y) = max (0, min (γ, f g (x, y))) ,

and F G,γ = {f g,γ : g ∈ G}.

A margin risk and its empirical counterpart are obtained by replacing φ by φ γ in Definitions 5 and 6. In these risks, we will use f g,γ instead of f g . The latter substitution does not affect the margin risk, but it leads to more efficient results due to the restricted codomain.

Definition 9 (Margin risk L γ , Empirical margin risk L γ,m [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]) For any g ∈ G, its margin risk is defined as

L γ (g) = E Z [φ γ (f g,γ (Z))] ,
and its empirical margin risk as

L γ,m (g) = 1 m m i=1 φ γ (f g,γ (Z i )) .
Note that the margin risk does not represent the probability of error. Indeed, based on the relationship between the standard loss and the truncated hinge loss functions addressed above we have that for all g ∈ G and for all γ ∈ (0, 1], L(g) L γ (g). A similar relationship holds for the empirical versions of these risks.

The question of the convergence of the empirical risk to the true one uniformly over the function class has been studied by Vapnik et Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. The conditions under which this happens is based on the notion of capacity measure which we introduce below.

Capacity Measures

This section gives the definitions of the capacity measures used in the thesis: the covering/packing numbers, the Rademacher complexity and the fat-shattering dimension. We also give several crucial results used in the sequel.

Covering/Packing Numbers

The first capacity measure-and historically the oldest one-we introduce is close to the notion of size of a set. An -cover of a set in a (pseudo-)metric space is a set of balls of radius that completely covers this set. The idea to characterize the "largeness" of sets in terms of their minimal covers emerged in the works of Soviet mathematicians in the late 40s. Much work has been dedicated to the study of this notion by Babenko [START_REF] Babenko | On the entropy of a class of analytic functions[END_REF], Kolmogorov [START_REF] Kolmogorov | Certain asymptotic characteristics of completely bounded metric spaces[END_REF], Vitushkin [START_REF] Vitushkin | The absolute ε-entropy of metric spaces[END_REF] and Tikhomirov [START_REF] Tikhomirov | Certain asymptotic characteristics of completely bounded metric spaces[END_REF] in the 50s. These studies have been set forth in a systematic manner by Kolmogorov and Tikhomirov [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF]. The following definitions are due to them.

Definition 10 (Covering numbers, metric entropy, packing numbers [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF]) Let (T , ρ) be a (pseudo-)metric space. Let B (t) = {t ∈ T : ρ(t , t) < } be the open ball of radius > 0 centered at t ∈ T . For any T ⊂ T , if there is a set T ⊂ T such that

T ⊂ t∈ T B (t), (1.1)
then {B (t) : t ∈ T } is an -cover of T and T is an -net of T . The -covering number N ext ( , T , ρ) of T is the cardinality of a minimal set T for which (1.1) is true. If an -net belongs to T then the corresponding covering number is a proper one denoted by N ( , T , ρ).

The (base 2 or base e) logarithm of a covering number is called metric entropy.

T ⊂ T is -separated with respect to the metric ρ if for any two distinct elements t 1 , t 2 ∈ T ,

ρ(t 1 , t 2 )
. The -packing number M ( , T , ρ) of T is the maximal cardinality of its -separated subsets.

An -net of a set T can also be thought of as its -approximation with respect to the metric ρ, in the sense that for any element t in T there exists t in its -net with ρ(t, t ) < .

The following relationship follows from the triangle inequality.

Lemma 1 (After Theorem 4 in [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF]) For any > 0,

N ext , T , ρ N , T , ρ N ext 2 , T , ρ . (1.2)
The covering and packing numbers are related to each other as follows.

Lemma 2 (After Theorem 2 in [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF]) For any > 0,

M 2 , T , ρ N ext , T , ρ N , T , ρ M , T , ρ . (1.3)
From Definition 10, it is clear that the size of an -net grows (more presicely, does not decrease) as → 0. If for any > 0, there is a finite -net in T for its subset T , then T is called a totally bounded set. In an Euclidean space, the definition of total boundedness coincides with that of boundedness: a bounded set is a set that can be completely included in a ball. From Definition 3 it follows that any component class G k is totally bounded.

To specify the metrics used for covering/packing numbers, we first introduce the following space of (equivalence classes of) functions.

Definition 11 (Set L p (T )) Let F denote the set of all real-valued measurable functions on (T , A T , P T ). For all p ∈ N * , L p (T ) is the space of p-integrable functions defined as

L p (T ) = f ∈ F : f Lp = T |f (t)| p dP T (t) 1 p < ∞ , and L ∞ (T ) is L ∞ (T ) = f ∈ F : f L∞ = ess sup t∈T |f (t)| < ∞ .
The following relationship holds between the L p -norms.

Lemma 3 Let p, q ∈ [1, ∞] with p q. Then, for any f ∈ L q (T ),

f Lp f Lq . (1.4)
Replacing P T with an empirical measure P n supported on a sequence t n = (t i ) 1 i n ∈ T n gives rise to an empirical (semi-)norm.

Definition 12 (Empirical (semi-)norm • Lp(tn) ) Let t n = (t i ) 1 i n ∈ T n and p ∈ N * ∪ ∞.
For any f ∈ F, we define its empirical (semi-)norm f Lp(tn) supported on t n as

∀p ∈ N * , f Lp(tn) = 1 n n i=1 |f (t i )| p 1 p and f L∞(tn) = max 1 i n |f (t i )| .
Hereafter, the L p -norm will stand for the empirical norm defined as above. This norm induces the following empirical (pseudo-)metrics.

Definition 13 (Empirical (pseudo-)metric d p,tn ) Let t n = (t i ) 1 i n ∈ T n . For any f, f ∈ F, the empirical pseudo-metric d p,tn is defined as

∀p ∈ N * , d p,tn (f, f ) = 1 n n i=1 f (t i ) -f (t i ) p 1 p and d ∞,tn (f, f ) = max 1 i n f (t i ) -f (t i ) .
Clearly, the relationship (1.4) carries over to the empirical metrics. This implies that for any

> 0 and p, q ∈ [1, ∞] with p q, N ( , F, d p,tn ) N ( , F, d q,tn ) , (1.5)
since an -net of F with respect to the d q,tn distance is also an -net with respect to the d p,tn distance.

Definition 14 (Restriction F| T ) Let T ⊆ T . Then F| T is the set of functions in F restricted to the domain T .

For any t n ∈ T n , we have that

   N ( , F, d p,tn ) = N ( , F| T , d p,tn ) M ( , F, d p,tn ) = M ( , F| T , d p,tn )
.

(1.6)

Under the empirical metrics, one can define the uniform version of covering numbers as

N p ( , F, n) = sup tn∈T n N ( , F, d p,tn ) ,
and similarly for packing numbers.

Combinatorial Dimensions

Roughly speaking, a combinatorial dimension of a set functions is the maximum number of points on which the functions output in all possible ways around fixed levels. The first combinatorial dimension, called theVC-dimension, originated in the seminal work of Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF][START_REF] Vapnik | Statistical Learning Theory[END_REF]. This dimension concerns a set of {0, 1}-valued functions. The VC-dimension has been generalized to classes of real-valued functions in several ways. The first such generalization is due to Pollard [START_REF] Pollard | Empirical processes: theory and applications[END_REF]. By introducing the scale parameter, Kearns and Schapire generalized the dimension of Pollard to a scale-sensitive one called the fat-shattering dimension.

Definition 15 (Fat-shattering dimension [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF]) Let γ ∈ R + . A non-empty subset T of T is said to be fat-shattered or γ-shattered by F if there is a level function v : T → R such that for any subset T ⊆ T , there is a function f in F satisfying

     ∀t ∈ T , f (t) v(t) + γ, ∀t ∈ T \ T , f (t) v(t) -γ.
The fat-shattering dimension of F at scale γ, γ-dim (F), is the maximal cardinality of a subset of T γ-shattered by F. If F γ-shatters sets of unbounded finite sizes, then γ-dim (F) = ∞.

The strong dimension is used as an auxilary quantity in the proofs of results involving the fat-shattering dimension. This dimension concerns classes of integer-valued functions.

Definition 16 (Strong dimension [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]) Let F be a set of functions from T to a finite set B of integers. A non-empty subset T of T is said to be strongly shattered by F if there is a level function v : T → B such that for any T ⊆ T , there is a function f ∈ F satisfying

     ∀t ∈ T , f (t) v(t) + 1, ∀t ∈ T \ T , f (t) v(t) -1.
The strong dimension of F is the maximal cardinality of a subset of T strongly shattered by F .

If F strongly shatters sets of unbounded finite sizes, then its strong dimension is infinity.

The generalization of the VC-dimension to classes of {0, 1, . . . , n}-valued functions, with finite n, is due to Natarajan [START_REF] Natarajan | On learning sets and functions[END_REF]. For such classes of functions, Ben-David et al. [START_REF] Ben-David | Characterizations of learnability for classes of 0,..., n-valued functions[END_REF] provide a family of dimensions called Ψ-dimensions unifying the generalizations of the VC-dimension. It includes the Natarajan and the graph dimensions [START_REF] Dudley | Universal Donsker classes and metric entropy[END_REF][START_REF] Natarajan | On learning sets and functions[END_REF] as special cases. Guermeur [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF][START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF] extended the Ψ-dimensions to the scale-sensitive setting, i.e., to classes of real-valued functions. We give the definitions of the scale sensitive versions of the Natarajan and the graph dimensions below.

In these definitions, γ ∈ R + and F stands for a set of real-valued functions on Z.

Definition 17 (Margin Natarajan dimension [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF])

A subset Z = {(x i , y i )} n i=1 of Z is said to be γ-N shattered by F, if there is a level function v : Z → R and a vector (c i ) 1 i n ∈ Y n satisfying c i = y i for all i, such that for any I ⊆ I = {1, . . . , n}, there is a function f ∈ F satisfying      ∀i ∈ I , f (x i , y i ) γ + v(z i ), ∀i ∈ I \ I , f (x i , c i ) γ -v(z i ).
The margin Natarajan dimension of F, γ-N -dim (F), is the maximal cardinality of a subset of Z γ-N -shattered by F. If F γ-N -shatters sets of unbounded finite sizes, then γ-N -dim (F) = ∞. Definition 18 (Margin graph dimension [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]) A subset Z = {(x i , y i )} n i=1 of Z is said to be γ-G shattered by F, if there is a level function v : Z → R such that for any I ⊆ I = {1, . . . , n},

there is a function f ∈ F satisfying      ∀i ∈ I , f (x i , y i ) γ + v(z i ), ∀i ∈ I \ I , max k =y i f (x i , k) γ -v(z i ).
The margin graph dimension of F, γ-G-dim (F), is the maximal cardinality of a subset of Z γ-G-shattered by F. If F γ-G-shatters sets of unbounded finite sizes, then γ-G-dim (F) = ∞.

According to Proposition 1 in [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF], the fat-shattering dimension of the margin class F G dominates the margin Natarajan and the margin graph dimensions:

∀γ ∈ (0, M G ], γ-N -dim (F G ) γ-G-dim (F G ) γ-dim (F G ) .
(1.7)

Rademacher/Gaussian Complexity

The last capacity measure considered in this thesis is closely related to the notion of stochastic process. Let S be some set. A stochastic process is an indexed collection G = {G s : s ∈ S} of random variables defined on the same probability space (T , A T , P T ) such that for any s ∈ S,

G s : T → R is (A T , B R )-measurable.
In the learning theory, S is usually a set of functions, and one deals with a particular type of stochastic process: an empirical process. In the following definitions, T is a random variable taking values in (T , A T , P T ) and T n = (T i ) 1 i n is a sequence of n independent copies of T .

Definition 19 (Empirical process [START_REF] Ledoux | Probability in Banach Spaces: Isoperimetry and Processes[END_REF][START_REF] Van Der Vaart | Weak Convergence and Empirical Processes, With Applications to Statistics[END_REF][START_REF] Pollard | Convergence of Stochastic Processes[END_REF]) Let L 1 (T ) be as in Definition 11. The (centered) empirical process G n,F indexed by a set F ⊂ L 1 (T ) is as follows:

G n,F = 1 n n i=1 f (T i ) -E [f (T )] : f ∈ F .
For a fixed γ ∈ (0, 1], the set {L γ (g) -L γ,m (g) : g ∈ G} of deviations central to this thesis is an empirical process. Whether the classical limit theorems hold for empirical processes is the major question in the theory of empirical processes. It has been shown by Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF],

Giné and Zinn [START_REF] Giné | Some limit theorems for empirical processes[END_REF], that these theorems can be proven for the "symmetrized" versions of these processes. This is based on the use of a Rademacher variable σ, symmetric Bernoulli random variable taking values 1 and -1 with equal probability, and a standard Gaussian random variable.

This calls for the definition of the Rademacher and Gaussian processes. Let σ n = (σ i ) 1 i n be a sequence of n independent copies of a Rademacher variable σ, and let o n = (o i ) 1 i n be an orthogaussian sequence, i.e., a sequence of n independent copies of a standard Gaussian random variable.

Definition 20 (Rademacher process) The Rademacher process R n indexed by F is an empirical process conditioned on T n :

R n,F = 1 n n i=1 σ i f (T i ) : f ∈ F .
In this definition, replacing the Rademacher sequence with an orthogaussian one yields a Gaussian process. The use of suprema of these processes as capacity measures of the class by which they are indexed is relatively recent. This work was started by Koltchinskii [START_REF] Koltchinskii | Rademacher penalties and structural risk minimization[END_REF], Bartlett and co-authors [START_REF] Bartlett | Model selection and error estimation[END_REF] and Bartlett and Mendelson [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF].

Definition 21 (Rademacher complexity, Gaussian complexity) The empirical Rademacher complexity of F given T n is defined as

Rn (F) = E σn sup f ∈F 1 n n i=1 σ i f (T i ) T n .
The Rademacher complexity of F is

R n (F) = E Tn Rn (F) = E Tnσn sup f ∈F 1 n n i=1 σ i f (T i ) .
The empirical Gaussian complexity Ĝn (F), and the Gaussian complexity G n (F) are defined in the same way by substituting o n for σ n .

One way to interpret the Rademacher complexity of a class F is to think of it as the degree of imitation of F of the Rademacher noise σ n (likewise for the Gaussian complexity). For some

M F > 0, let F be a class of functions from T to [-M F , M F ]. Let s n = (s i ) 1 i n ∈ {-1, 1} n . If
for any s n , there exists a function f ∈ F such that s i f (t i ) = M F , then the class F agrees well with the Rademacher noise σ n . Note also that according to Jensen's inequality and by definition of a Rademacher variable,

Rn (F) sup f ∈F 1 n n i=1 E [σ i f (t i )] = 0.
Several properties of the Rademacher complexity (the proofs of which are gathered in Appendix A) will be useful in the sequel. The first important result is the contraction principle due to

Talagrand: it allows one to switch from the Rademacher complexity of the composition of a

Lipschitz function with a class to the Rademacher complexity of this class.

Limit Theorems and Capacity Measures

Lemma 4 (After Theorem 4.12 in [START_REF] Ledoux | Probability in Banach Spaces: Isoperimetry and Processes[END_REF]) Let ψ : R → R be an L-Lipschitz function and let

ψ • F = {ψ • f : f ∈ F}. Then, Rn (ψ • F) L Rn (F). (1.8)
The Rademacher complexity does not change when one takes the convex hull of a class.

Lemma 5 Let conv (F) = N j=1 α j f j : N ∈ N * , α j 0, N j=1 α j = 1, f j ∈ F . Then, Rn (F) = Rn (conv (F)) .
Remark 1 The classical definition of the Rademacher complexity involves the supremum of the absolute value of the sum n i=1 σ i f (T i ) (see, for instance, [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF]). In this case, thanks to the presence of the absolute value, one has Rn (F) = Rn (conv (F)) = Rn (absconv (F)) where

absconv (F) =    N j=1 α j f j : N ∈ N * , α j ∈ R, N j=1 |α j | 1, f j ∈ F    .
These two definitions agree if for any f in F, -f is also in F.

The Gaussian complexity dominates the Rademacher complexity as follows.

Lemma 6 (After Lemma 3.2.10 in [START_REF] Talagrand | Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems[END_REF]) For all n ∈ N,

Rn (F) π 2 Ĝn (F)

Limit Theorems and Capacity Measures

The seminal work of Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF] demonstrated that there is a connection between the law of large numbers and a capacity measure of the class. More precisely, in Theorem 4 in [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF], the authors give the necessary and sufficient conditions for the uniform convergence of the empirical risk to the true one in terms of the growth rate of the "metric entropy". The connections between the classical limit theorems and the capacity measures have been later developed by Koltchinskii [START_REF] Koltchinskii | On the central limit theorem for empirical measures[END_REF], Gine and Zinn [START_REF] Giné | Some limit theorems for empirical processes[END_REF], Talagrand [START_REF] Talagrand | The Glivenko-Cantelli problem, ten years later[END_REF], Dudley [START_REF] Dudley | Uniform central limit theorems[END_REF] and Alon et al. [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]. In this section, we give the formal definitions of classes that satisfy the strong law of large numbers and the central limit theorem, i.e., Glivenko-Cantelli and Donsker classes, respectively, and the necessary and sufficient conditions for these classes.

Let T be a real-valued random variable with a law P T , and (T i )

P ∞ T sup m n sup f ∈F 1 m m i=1 f (t i ) -E [f (T )] > = 0.
If F is a Glivenko-Cantelli class for any probability measure P T on A T , then it is called a universal Glivenko-Cantelli class. F is called a uniform Glivenko-Cantelli class if and only if for all > 0, lim n→∞ sup

P T P ∞ T sup m>n sup f ∈F 1 m m i=1 f (t i ) -E[f (T )] > = 0.
For the empirical process { √ n (F n (t) -F (t)) : t ∈ R}, the multivariate central limit theorem asserts that the law of any finite subset { √ n (F n (t i ) -F (t i )) : 1 i l} with l ∈ N * converges to the zero-mean Gaussian distribution with a covariance function min (F (t i ),

F (t j )) -F (t i )F (t j ).
The convergence in distribution of an empirical process indexed by a function class has been addressed by Donsker [START_REF] Dudley | Uniform central limit theorems[END_REF]. The following definition of a Donsker class is from van der Vaart and Wellner [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes, With Applications to Statistics[END_REF].

Definition 23 (Donsker class [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes, With Applications to Statistics[END_REF]) Let L 2 (T ) be as in Definition 11. Let G F be a zero-mean Gaussian process indexed by F ⊂ L 2 (T ) with a covariance function

E[f 1 (T )f 2 (T )] -E[f 1 (T )]E[f 2 (T )],
for any

f 1 , f 2 ∈ F. Let G n,
lim n→∞ ln N p ( , F, n) n = 0. (1.9)
Similarly, the following theorem gives the necessary and sufficient conditions for Donsker class.

Theorem 2 (Dudley [START_REF] Dudley | Uniform central limit theorems[END_REF])

Let L ∞ (T ) be as in Definition 11. A class F ⊂ L ∞ (T ) is a uni- versal Donsker class if ∞ 0 sup n∈N * ln N 2 ( , F, n)d < ∞. (1.10)
If F is a universal Donsker class, then there exists a constant K > 0, such that for any > 0,

sup n∈N * ln N 2 ( , F, n) K 2 .
Based on the bounds which relate the covering number (or metric entropy) of a class to one of its combinatorial dimension, which we call combinatorial bounds, the Glivenko-Cantelli and Donsker classes can be characterized in terms of their combinatorial dimensions. The first such bound related the growth function of {0, 1}-valued function classes to their VC-dimensions [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF][START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Vapnik | Statistical Learning Theory[END_REF].

The result relating the L 1 -norm metric entropy of such classes to their VC-dimensions is due to Haussler [START_REF] Haussler | Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension[END_REF]; this was generalized to L p -norms with p ∈ N * by Van der Vaart and Wellner [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes, With Applications to Statistics[END_REF].

These results give sufficient conditions both for Glivenko-Cantelli and Donsker theorems: the classes with finite VC-dimension, the VC-classes, are both Glivenko-Cantelli and Donsker. For classes of real-valued functions, on the other hand, the combinatorial bound of Alon et al. [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] involves a scale-sensitive generalization of the VC-dimension: the fat-shattering dimension.

Theorem 3 (After Theorem 2.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]) Let L ∞ (T ) be as in Definition 11. A class F ⊂ L ∞ (T ) is a uniform Glivenko-Cantelli class if and only if the fat-shattering dimension of F is finite at every scale .

Due to the fact that the fat-shattering dimension is scale-sensitive, the finiteness of this dimension is not sufficient for Donsker theorem as it is the case for the VC-dimension. In fact, it is the growth rate of the fat-shattering dimension that determines whether a class obeys Donsker theorem. As it was noted by Mendelson [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF], if the fat-shattering dimension of a class is O(

-α ) for 0 < α < 2,
then it is a Donsker class.

In this thesis, we make the assumption that the component classes G k are uniform Glivenko-Cantelli, i.e., their fat-shattering dimensions are finite. For the results of Chapter 4 and Chapter 5, a stronger assumption is made: the fat-shattering dimensions of the classes G k grow no faster than polynomially with the inverse of their scales.

Chapter 2

Controlling Uniform Convergence by a

Covering Number

In this chapter, our goal is to control the uniform deviation of the risk and the empirical margin risk in terms of an L 1 -norm covering number.

Inspired by the seminal work of Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF], Bartlett [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF] established an error bound for margin bi-category classifiers on the basis of the margin indicator loss function.

The capacity measure appearing in his error bound is the L ∞ -norm covering number. This work has been extended to the multi-category setting by Guermeur [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF][START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. Our work is based on the use of the truncated hinge loss function. For this loss function, the uniform deviation of interest can be handled based on Pollard's method [START_REF] Pollard | Convergence of Stochastic Processes[END_REF], as well as the result of Bartlett and

Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF]. Pollard derived the rate of convergence for the classical Glivenko-Cantelli problem based on the L 1 -norm approximation of the set. He also extended it to classes of real-valued functions. For these classes, based on Pollard's method, Bartlett and Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF] derived a faster rate of convergence. They translated this result into a sample complexity estimate, i.e., given , δ ∈ (0, 1), a minimum sample size needed for the uniform deviation to be at most with probability at least 1 -δ. This result was based on the L 1 -norm generalization of the bound of Alon et al. [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF], Lemma 8 in [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF]. Apart from and δ, this sample complexity estimate also depends on the fat-shattering dimension of the function class.

In Section 2.1, we generalize their uniform convergence result, Lemma 10 combined with Lemma 11 in [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF], to the multi-category setting. In Section 2.2, we derive several sample complexity estimates using the L 1 and L 2 -norm combinatorial bounds [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF][START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF][START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. These bounds include the one that depend on the sample size and the ones that do not, i.e., dimension-free bounds. Our estimates obtained based on the L 1 -norm combinatorial bounds match with that of Bartlett and Long. Particularly, we demonstrate that using the dimension-free L 1 -norm bound does not improve the sample size estimate. The dimension-free L 2 -norm bound of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], on the other hand, improves the dependency on at the cost of deteriorating the scale parameter of the fat-shattering dimension.

L 1 -norm Covering Number Bound

Given a fixed γ ∈ (0, 1] and a fixed ∈ (0, 1), our goal is to upper bound the probability

P m sup g∈G (L(g) -L γ,m (g)) > (2.1)
in terms of the L 1 -norm covering number of F G,γ . This corresponds to a multi-category extension of Lemma 10 combined with Lemma 11 of Bartlett and Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF]. We derive the following bound where the scale of the covering number involves the margin parameter γ due to the use of a margin loss function.

Theorem 4 Fix ∈ (0, 1) and γ ∈ (0, 1]. Then for m > 2 2 , P m sup g∈G (L (g) -L γ,m (g)) > 2N 1 γ 8 , F G,γ , 2m exp - m 2 32 . (2.2)
Proof The proof consists of the following steps: i) apply the symmetrization technique of Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF] which allows one to switch from the original problem (deviation between the margin risk and the empirical one) to the symmetrized one (deviation between two empirical margin risks); ii) thanks to step (i), switch to a finite class, i.e., to an -approximation of the class F G,γ ; iii) perform the second symmetrization to introduce a Rademacher sequence which allows one to condition on the sample (the distribution of which we do not know) and work with a Rademacher sequence instead; and iv) thanks to steps (ii)-(iii), apply the union bound and a concentration inequality which gives Inequality (2.2).

First Symmetrization

The idea of the first symmetrization is to use an independent copy Z m of Z m which is usually referred to as a "ghost sample" and bound the tail probability in terms of the probability of events involving the empirical risks only. As it has been pointed out in Chapter 1, the truncated hinge loss function dominates the standard indicator loss function and thus, for any γ ∈ (0, 1] and for any g ∈ G, L(g) L γ (g).

L 1 -norm Covering Number Bound

Then, it follows that

P m sup g∈G (L(g) -L γ,m (g)) > P m sup g∈G (L γ (g) -L γ,m (g)) > .
This allows us to make use of Lemma 35 in Appendix C. Applying it to the right-hand side gives:

P m sup g∈G (L(g) -L γ,m (g)) > 2P 2m sup g∈G 1 m m i=1 φ γ f g,γ Z i - 1 m m i=1 φ γ (f g,γ (Z i )) 2 = 2 Z 2m 1 sup g∈G 1 m m i=1 φ γ f g,γ z i - 1 m m i=1 φ γ (f g,γ (z i )) 2 dP 2m (z 2m ), (2.3)
where z 2m is the concatenation of

z m = (z i ) 1 i m ∈ Z m and z m = (z i ) 1 i m ∈ Z m .
Denote the integral by I. To keep the notation simple, for the rest of the proof, let

φ g = φ γ (f g,γ ).
Maximal Inequality At this point, we approximate F G,γ by its finite cover with respect

to d 1,z 2m . Let Ḡ be a subset of G so that F Ḡ,γ is an γ 8 -net of F G,γ of minimal cardinality N γ 8 , F G,γ , d 1,z 2m : ∀g ∈ G, ∃ḡ ∈ Ḡ, 1 2m m i=1 |f ḡ,γ (z i ) -f g,γ (z i ) | + f ḡ,γ z i -f g,γ z i < γ 8 .
Using the 1 γ -Lipschitz property of φ γ , we get:

1 2m m i=1 |φ ḡ (z i ) -φ g (z i ) | + φ ḡ z i -φ g z i 1 2mγ m i=1 |f ḡ (z i ) -f g (z i ) | + f ḡ z i -f g z i < 8 .
On the other hand,

1 m m i=1 φ ḡ(z i ) -φ ḡ z i + φ g z i -φ g (z i ) 1 m m i=1 |φ ḡ (z i ) -φ g (z i ) | + φ ḡ z i -φ g z i < 4 .
It follows that

1 m m i=1 φ g z i -φ g (z i ) 2 =⇒ 1 m m i=1 φ ḡ z i -φ ḡ (z i ) > 4 .
(2.4) Thus,

I Z 2m 1 max ḡ∈ Ḡ 1 m m i=1 φ ḡ z i -φ ḡ(z i ) > 4 dP 2m (z 2m ).
In the subsequent steps, we bound the right-hand side thanks to the introduction of a Rademacher sequence.

Second Symmetrization Since Z i and Z i are independent copies of Z, for any measurable

function s on Z, s (Z i ) -s (Z i ) is distributed in the same way as s (Z i ) -s (Z i ) for any i ∈ [ [ 1, m ] ]. Thus, s (Z i ) -s (Z i ) is a symmetric random variable. It implies that for any s m = (s i ) 1 i m ∈ {-1, 1} m , I Z 2m 1 max ḡ∈ Ḡ 1 m m i=1 s i φ ḡ z i -φ ḡ (z i ) > 4 dP 2m (z 2m ).
It follows that

I 1 2 m sm∈{-1,1} m Z 2m 1 max ḡ∈ Ḡ 1 m m i=1 s i φ ḡ z i -φ ḡ (z i ) > 4 dP 2m (z 2m ) = E σm Z 2m 1 max ḡ∈ Ḡ 1 m m i=1 σ i φ ḡ z i -φ ḡ (z i ) > 4 dP 2m (z 2m ) ,
where σ m is a Rademacher sequence. Here, Tonelli's theorem applies and we can change the order of integration:

I Z 2m E σm 1 max ḡ∈ Ḡ 1 m m i=1 σ i φ ḡ z i -φ ḡ (z i ) > 4 dP 2m (z 2m ) = Z 2m P σm max ḡ∈ Ḡ 1 m m i=1 σ i φ ḡ z i -φ ḡ (z i ) > 4 dP 2m (z 2m ). (2.5)
Concentration inequality Now, the integrand on the right-hand side of (2.5) calls for the application of the union-bound:

I Z 2m ḡ∈ Ḡ P σm 1 m m i=1 σ i φ ḡ z i -φ ḡ (z i ) > 4 dP 2m (z 2m ). (2.6)
For a fixed z 2m ∈ Z 2m and for a fixed ḡ ∈ Ḡ, we can bound the tail probability

P σm 1 m m i=1 σ i φ ḡ z i -φ ḡ (z i ) > 4 using Hoeffding's inequality (B.6) in Appendix B. Note that ∀i ∈ [ [ 1, m ] ] , σ i φ ḡ z i -φ ḡ (z i ) ∈ [-1, 1],
almost surely. Thus,

P σm 1 m m i=1 σ i φ ḡ z i -φ ḡ (z i ) > 4 exp - m 2 32 .

Sample Complexity

Substituting the last bound into (2.6) and taking into account that the cardinality of Ḡ is

N γ 8 , F G,γ , d 1,z 2m
, we obtain:

I exp - m 2 32 Z 2m N γ 8 , F G,γ , d 1,z 2m dP 2m (z 2m ) exp - m 2 32 N 1 γ 8 , F G,γ , 2m . (2.7)
Taking this bound into account in (2.3) concludes the proof.

In the following, we translate our result, Theorem 4, into a sample complexity estimate, i.e., the minimum sample size required for the right-hand side of (2.1) to be at most δ ∈ (0, 1).

Sample Complexity

We derive several sample complexity estimates based on the L 1 and L 2 -norm combinatorial bounds. Our starting point is the following L 1 -norm combinatorial bound obtained using Lemmas 9-11 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. It depends on the sample size.

Lemma 7 Let F be a class of functions from T to [-M F , M F ] with M F ∈ R + . Let d ( ) = -dim (F) be finite for all ∈ (0, M F ]. Fix ∈ (0, 2M F ]. Then, provided that n d 8 , N 1 ( , F, n) 2 1+3 log 2 36M F 36M F en d 8 3d( 8 ) log 2 36M F
.

Proof Let T n = {t i : 1 i n} be a finite subset of T and t n = (t i ) 1 i n . Let F be an -separated with respect to the pseudo-metric d p,tn subset of F of maximal cardinality. For any η ∈ R + , let Fη be a discretized set:

Fη = f : f (t i ) = η f (t i ) + M F η , i ∈ [ [ 1, n ] ] , f ∈ F | Tn .
By Lemma 9 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF],

∀η ∈ (0, ) , M ( , F| Tn , d 1,tn ) M -η 2 , Fη , d 1,tn . (2.8)
Next, we apply Lemma 11 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] to the right-hand side of Inequality (2.8). To this end, we set

η = 2M F N for N ∈ N satisfying N > 14M F . Then, by this lemma, M ( , F| Tn , d 1,tn ) 2 1+3 log 2 N en (N -1) d 1 3d 1 log 2 N , (2.9)
where

d 1 = 1 4 -14M F N -dim F 2M F N
. Next, we switch from the fat-shattering dimension of

F 2M F N
to that of F. We set N = 36M F . Since the fat-shattering dimension is a non-increasing function, we have

d 1 11 72 -dim     F  2M F 36M F       .
Applying Lemma 10 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF], i.e.,

-dim Fη - η 2 -dim (F) ,
to the right-hand side, we get

d 1 8 -dim (F| Tn ) .
On the other hand,

8 -dim (F| Tn ) 8 -dim (F) = d 8 ,
and thus Based on this relation and assuming that n d 8 , we can use Inequality (2.10) in (2.9).

d 1 d 8 . ( 2
Combining this result with Equality (1.6) produces

M ( , F, d 1,tn ) 2 3 log 2 36M F +1 36M F en d 8 3d( 8 ) log 2 36M F .
The proof follows by taking supremum over t n ∈ T n from both sides and using Inequality (1.3).

This bound gives us the following sample complexity estimate.

Lemma 2 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] generalizes this bound to all p ∈ N * as follows.

Lemma 9 (After Lemma 2 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]) Let F be a class of functions from 45) .

T into [-M F , M F ] with M F ∈ R * + . Let d ( ) = -dim (F) for ∈ (0, M F ]. Then for any ∈ (0, 2M F ], N p ( , F, n) 2 2(K (p)+1) 6272eK (p) 3 2M F 2p+1 2K (p)d(
The application of this bound with p = 1 gives us the following sample complexity estimate. Proof Applying Lemma 9 with p = 1 to N 1 γ 8 , F G,γ , 2m yields:

Theorem 6 Fix , δ ∈ (0, 1) and fix γ ∈ (0, 1]. For ∈ (0, γ], let d ( ) = -dim (F G,γ
N 1 γ 8 , F G,γ , 2m 12544 • 16 3 eK γ 8 (1) 3 3 2K
γ 8 (1)d( γ 360 ) , (2.12)
where K γ The following formula summarizes the sample complexity results up to a ln(2/δ) term that we obtained based on different combinatorial bounds: where the asterisk indicates the sample-size dependent combinatorial bound. One can see that the L 1 -norm dimension-free bound does not provide better sample complexity result: on the contrary, it worsens the constants. The results obtained based on the L 1 -norm combinatorial bounds provide the matching dependency on with that in Inequality (5) of Bartlett and Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF]. On the other hand, using the L 2 -norm bound of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], one can improve the dependency on by a factor of ln 1 3 ln 1 . This, however, decreases the scale of the fat-shattering dimension, thus increasing the dimension itself. In all cases, the fat-shattering dimensions that appear in our sample complexity results involve the margin parameter γ in their scales. This is the main difference with the work of Bartlett and Long.

m 32 2                10d γ 64

Conclusions

This chapter focused on bounding the probability of the uniform deviation sup

g∈G (L(g) -L γ,m (g))
in terms of an L 1 -norm covering number. The technique to control the uniform deviation between the true and empirical means in the L 1 -metric is due to Pollard [START_REF] Pollard | Convergence of Stochastic Processes[END_REF]. Based on Pollard's work, Bartlett and Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF] derived a faster rate of convergence for the uniform deviation.

They obtained a sample complexity estimate for the uniform convergence based on the L 1 -norm generalization of the bound of Alon et al. [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]. We generalized their uniform deviation result, Lemma 10 combined with Lemma 11 in [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF], to the multi-category case. Then, we derived several sample complexity estimates using the L 1 and L 2 -norm bounds [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF][START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] which included dimension-free ones and the one depending on the sample-size. We observed that the dimension free L 1 -norm bound does not provide smaller (thus better) sample complexity estimate. In fact,

Basic Generalization Inequality

Before the use of the Rademacher complexity as a capacity measure in learning theory, Talagrand [START_REF] Talagrand | New concentration inequalities in product spaces[END_REF] established a far-reaching concentration inequality for the suprema of empirical processes.

According to his result, the supremum of an empirical process indexed by a uniformly bounded function class is concentrated around its expectation as follows.

Theorem 8 (After Theorem 4.1 in [START_REF] Talagrand | New concentration inequalities in product spaces[END_REF]) Let F be a class of functions from

T to [-M F , M F ]
with M F > 0. Let a random variable T be an identity map on (T , A F , P T ) and let

(T i ) 1 i n be a sequence of n independent copies of T . Let F = sup f ∈F n i=1 f (T i ) and v = E sup f ∈F n i=1 f 2 (T i ) .
Then, for any > 0,

P n T (F -E [F ] ) K exp - 1 K M F ln 1 + M F v ,
where K and K are constants.

In fact, Talagrand's result answered affirmatively the once long-standing question regarding the existence of the functional form of Bernstein's inequality (Inequality (B.8) in Appendix B). The quest to make the constants in his concentration inequality explicit led to modified versions of this inequality. This line of work has been started by Massart (see Theorem 3 in [START_REF] Massart | Some applications of concentration inequalities to statistics[END_REF]). Below is a more refined version due to Bartlett, Bousquet and Mendelson [START_REF] Bartlett | Local Rademacher complexities[END_REF] where the Rademacher complexity appears thanks to the use of the symmetrization for expectation technique [START_REF] Giné | Some limit theorems for empirical processes[END_REF] (see also Section 2.3 of [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes, With Applications to Statistics[END_REF]).

Theorem 9 (After Theorem 2.1 in [START_REF] Bartlett | Local Rademacher complexities[END_REF]) Let F be a class of functions from

T to [-M F , M F ]
with M F > 0. Let a random variable T be an identity map on (T , A F , P T ) and let (T i ) 1 i n be a sequence of n independent copies of T . Assume that there is v > 0 such that for any f ∈ F, var(f (T )) v almost surely. Fix δ ∈ (0, 1). Then, with probability

P n T at least 1 -δ, for all f ∈ F, E [f (T )] 1 n n i=1 f (T i )+ inf α 0 2(1 + α)R n (F) + 2v n ln 1 δ + 2M F 1 3 + ln 1 δ 1 nα .
Notice that this bound emphasizes the role of the variance of functions in a class, thus it is only useful when subsets of functions with small variance are considered. probability

P m at least 1 -δ, ∀g ∈ G, L (g) L γ,m (g) + 2 γ R m (F G,γ ) + ln 1 δ 2m . (3.1)
Now, the question of interest is to elaborate the dependency of the Rademacher complexity on the number of categories and the sample size to which the upcoming sections are dedicated.

Decomposition of the Rademacher Complexity

To the best of our knowledge, the first decomposition result for the Rademacher complexity goes back to the work of Koltchinskii and Panchenko [START_REF] Koltchinskii | Empirical margin distributions and bounding the generalization error of combined classifiers[END_REF]. Assuming that all component classes are the same (which is usually the case), their bound admits a quadratic dependency on the number of categories.

Lemma 10 (After a partial result in the proof of Theorem 11 in [START_REF] Koltchinskii | Empirical margin distributions and bounding the generalization error of combined classifiers[END_REF]) Let G be a class of functions satisfying Definition 3, and let F G be the class of functions deduced from G according to Definition 8. Then,

R m (F G ) C 2 C k=1 R m (G k ) . (3.2) Proof It holds that R m (F G ) = 1 2m E σm sup g∈G m i=1 σ i g y i (x i ) -max k =y i g k (x i ) = 1 2m E σm sup g∈G m i=1 C k=1 σ i g k (x i ) -max q =k g q (x i ) 1 {k=y i } 1 2m C k=1 E σm sup g∈G m i=1 σ i g k (x i ) -max q =k g q (x i ) i 2 + 1 2 , (3.3)
where i = 21 {k=y i } -1. Denote the k-th summand in the right-hand side of (3.3) by I k . Note that since i ∈ {-1, 1}, σ i and i σ i follow the same distribution. Thus, for all k,

I k 1 2 E σm sup g∈G m i=1 σ i i g k (x i ) -max q =k g q (x i ) + 1 2 E σm sup g∈G m i=1 σ i g k (x i ) -max q =k g q (x i ) = E σm sup g∈G m i=1 σ i g k (x i ) -max q =k g q (x i ) .
Next, by sub-additivity of supremum and Lemma 29 in Appendix A,

I k E σm sup g∈G m i=1 σ i g k (x i ) + E σm sup g∈G m i=1 σ i max q =k g q (x i ) E σm sup g∈G m i=1 σ i g k (x i ) + q =k E σm sup g∈G m i=1 σ i g q (x i ) = C q=1 E σm sup g∈G m i=1 σ i g q (x i ) .
Substituting this bound into (3.3) concludes the proof.

This decomposition was refined by Kuznetsov et al. [START_REF] Kuznetsov | Multi-class deep boosting[END_REF] by partially truncating the co-domain of F G , i.e., truncating all values above γ ∈ (0, 1], which improved the quadratic dependency of Lemma 10 to a linear one. This gain is based on the following line of reasoning. Since

E σm sup g∈G m i=1 σ i g y i (x i ) -max k =y i g k (x i ) E σm sup g∈G m i=1 σ i g y i (x i ) +E σm sup g∈G m i=1 σ i max k =y i g k (x i ) ,
the first term can be upper bounded by C k=1 Rm (G k ) as in the proof above with g y i (x i )max k =y i g k (x i ) replaced by g y i (x i ). Now, to get a similar upper bound on the second term, one needs to take the maximum over all component functions so as using Lemma 29 to obtain

E σm sup g∈G m i=1 σ i max 1 k C g k (x i ) C k=1 E σm sup g∈G m i=1 σ i g k (x i ) .
Now, this is precisely where the usefulness of truncating the co-domain of F G lies. This leads to the following bound involving the class F G,γ .

Lemma 11 (After a partial result in the proof of Theorem 3 in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]) Let G be a class of functions satisfying Definition 3. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from

G according to Definition 8. Then R m (F G,γ ) C k=1 R m (G k ) . (3.4)
Proof For any g ∈ G and for any γ ∈ (0, 1], the functions f g,γ can be re-written as follows:

∀(x, y) ∈ Z, f g,γ (z) = max 0, 1 2 g y (x) -max 1 k C g k (x) -2γ1 {k=y} . Note that max(0, •) is a 1-Lipschitz function: ∀t, t ∈ R, max(0, t) -max(0, t ) max 0, t -t t -t .
Then, according to Lemma 4 and by sub-additivity of the supremum function,

Rm (F G,γ ) = 1 2m E σm sup g∈G m i=1 σ i max 0, g y i (x i ) -max 1 k C g k (x i ) -2γ1 {k=y i } 1 2m E σm sup g∈G m i=1 σ i g y i (x i ) -max 1 k C g k (x i ) -2γ1 {k=y i } 1 2m E σm sup g∈G m i=1 σ i g y i (x i ) + 1 2m E σm sup g∈G m i=1 σ i max 1 k C g k (x i ) -2γ1 {k=y i } . (3.5)

Decomposition of the Rademacher Complexity

Denote the terms in the right-hand side of (3.5) by T 1 and T 2 , respectively. T 1 can be bounded as follows:

T 1 = 1 2m E σm sup g∈G m i=1 C k=1 σ i g k (x i ) 1 {k=y i } 1 2m C k=1 E σm sup g∈G m i=1 σ i g k (x i ) 1 {k=y i } 1 2m C k=1 E σm sup g∈G m i=1 σ i g k (x i ) i 2 + 1 2 1 4m C k=1 E σm sup g∈G m i=1 σ i i g k (x i ) + E σm sup g∈G m i=1 σ i g k (x i ) 1 2 C k=1 Rm (G k ) , (3.6)
where we used the fact that σ i and i σ i follow the same distribution. Now, the term T 2 can be bounded using Lemma 29 and the fact that Rademacher variables are centered:

T 2 C k=1 1 2m E σm sup g∈G m i=1 σ i g k (x i ) -2γ1 {k=y i } = 1 2 C k=1 Rm (G k ) .
(t i ) i 1 ∈ l 2 , i 1 t 2 i 1 2 K p E σ i 1 σ i t i p 1 p .
To apply Maurer's result in the context of our work, we make use of the following result that replaces the required Lipschitz property.

Lemma 13 (After Lemma A.3 in [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF])

Fix (x, y) ∈ X × [ [ 1, C ] ].
Let G be as in Definition 3.

Then, for any g, g ∈ G and for any p ∈ N * ,

f g (x, y) -f g (x, y) g(x) -g (x) p .
Since the functions max(0, •) and min(γ, •) are 1-Lipschitz, Lemma 13 also holds for truncated margin functions. Thus, Maurer's result remains unchanged when one switches from the class

F G to F G,γ .
Particularly, the following bound holds (the proof is given in Appendix A):

Lemma 14 (After Corollary 1 in [START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF]) Let G be a class of functions satisfying Definition 3.

For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 8. Let

σ Cm = (σ i ) 1 i Cm denote a Rademacher sequence of length C × m. Then, R m (F G,γ ) √ 2 m E σ Cm sup g∈G m i=1 C k=1 σ C(i-1)+k g k (x i ).
Maurer's result is an improvement over that of Lei et al. [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF] whose decomposition is in terms of the Gaussian complexity:

Theorem 11 (After Theorem 5 in [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF]) Let G be a class of functions satisfying Definition 3.

For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 8. Let

o Cm = (o j ) 1 j Cm be an orthogaussian sequence of length C × m. Then R m (F G,γ ) 1 m π 2 E o Cm sup g∈G m i=1 C k=1 o C(i-1)+k g k (x i ) . (3.7)
The advantage of Lemma 14, which also holds true for Theorem 11), over Lemma 11 is that it allows the coupling between the component functions g k to be taken into account. In particular, for linear classifiers, employing a specific coupling assumption leads to a generalization bound with a sublinear dependency on the number of categories (see Chapter 4). If no coupling is assumed, as it is the case for the main contributions of the present thesis, then one recovers Lemma 11 up to a constant factor.

To elaborate the dependency on the sample size, one could specify the component classes G k and upper bound the corresponding Rademacher complexity. The following section demonstrates the technique due to Bartlett and Mendelson [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF] to upper the Rademacher complexity of linear and kernel classifiers. This technique can be used to upper bound that of feedforward neural networks with multiple layers.

Dependency on the Sample Size: Standard Classifiers

For several well-known classifiers, such as support vector machines [START_REF] Cortes | Support-vector networks[END_REF], feedforward neural networks [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF], decision trees [START_REF] Breiman | Classification and regression trees[END_REF][START_REF] Quinlan | Induction of decision trees[END_REF], the Rademacher/Gaussian complexity bounds have been derived

by Bartlett and Mendelson [13], one of the early works promoting the use of these measures in 3.3. Dependency on the Sample Size: Standard Classifiers learning theory. These results admit the optimal, O m -1 2 , dependency on the sample size.

In particular, the lemma below is an upper bound on the Rademacher complexity of linear and kernel methods. It can be used as the basis to derive Rademacher complexity bounds for function classes that can be expressed as combinations of functions from simpler classes, such as feedforward neural networks.

Lemma 15 (After Lemma 2 in [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF]) Let κ : X × X → R be a reproducing kernel and let H κ , • Hκ be the corresponding reproducing kernel Hilbert space (RKHS) [START_REF] Berlinet | Reproducing Kernel Hilbert Spaces in Probability and Statistics[END_REF]: for any x ∈ X ,

κ x = κ(•, x) ∈ H κ , and for any h ∈ H κ , h(x) = h, κ x . Let Λ X , Λ ∈ R + . Assume that sup x∈X κ x Hκ Λ X . Let B Λ (H κ ) = h ∈ H κ : h Hκ Λ .
Then,

R n (B Λ (H κ )) ΛΛ X √ n .
Proof For any (x i ) 1 i n ∈ X n , by Cauchy-Schwarz and Jensen's inequalities,

E σn sup h∈B Λ (Hκ) n i=1 σ i h(x i ) = E σn sup h∈B Λ (Hκ) n i=1 σ i h, κ x i sup h∈B Λ (Hκ)
h Hκ E σn i,j

σ i σ j κ x i , κ x j Λ E σn i,j σ i σ j κ x i , κ x j Λ n i=1 κ x i , κ x i √ nΛΛ X .
Theorem 18 in [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF] provides an upper bound on the Gaussian complexity of the class of twolayer neural networks. By using the lemma above and the contraction principle, Lemma 4, one can upper bound the Rademacher complexity of the class of deep networks with the • 1 -norm constraints on weights [START_REF] Zhang | On the learnability of fully-connected neural networks[END_REF]. This bound exhibits an exponential dependency on the number of layers and the optimal dependency on the sample size.

Lemma 16 (After Lemma 2 in [START_REF] Zhang | On the learnability of fully-connected neural networks[END_REF])

Let Λ X , Λ ∈ R + . Let X ⊂ R d with sup x∈X x 2 Λ X . For any j ∈ [ [ 1, l ] ] with l 2, let W (j) be a d j × d j-1 weight matrix with d 0 = d and d l = 1. Fix j ∈ [ [ 1, l ] ] and assume that for all r ∈ [ [ 1, d j ] ], W (j) r. 1 = d j-1 q=1 W (j) rq Λ, where W (j)
r. denotes the r-th row of W (j) . Let α : R → [-M, M ] with M > 0 be an L-Lipschitz function. For any

t = (t i ) 1 i d j ∈ R d j , let α (j) : t → α(t 1 ), . . . , α(t d j )
T . Define the class of l-layer networks as 1) . . . α (1) W (1) x . . .

H l = x → α (l) W (l) α (l-1) W (l-
: x ∈ R d , W (j) r. 1 Λ .
Then,

R n (H l ) L l Λ l Λ X √ n .
Proof For l = 2, we have

H 2 = {x → α (2) W (2) α (1)
W (1) x }. Then, by the contraction lemma (Lemma 4) and Lemma 15, we have

E σn sup h∈H 2 n i=1 σ i α (2) W (2) α (1) W (1) x i LE σn sup h∈H 2 n i=1 σ i W (2) α (1) W (1) x i LE σn sup h∈H 2 n i=1 σ i d 1 j=1 W (2) 1j α   d q=1 W (1) jq x (q) i   LE σn sup h∈H 2 d 1 j=1 W (2) 1j n i=1 σ i α   d q=1 W (1) jq x (q)
i   . Since W (2) 1 = d 1 j=1 W (2) 1j
Λ, it follows that

E σn sup h∈H 2 n i=1 σ i α (2) W (2) α (1) W (1) x i nΛL E σn sup h∈H 1 1 n n i=1
σ i α W (1) x i Rn(H1)

√ nL 2 Λ 2 Λ X .
Now, assume that the claim holds for l -1 layers. Then proving it for l layers following the reasoning above is straightforward: 1) . . . α (1) W (1) x i . . . 1) . . . α (1) W (1) x i . . .

E σn sup h∈H l n i=1 σ i α (l) W (l) α (l-1) W (l-
ΛLE σn sup h∈H l n i=1 σ i W (l) W (l) 1 α (l-1) W (l-1) . . . α (1) W (1) x i . . . nΛL E σn sup h∈H l-1 1 n n i=1 σ i α W (l-
Rn(Hl-1) (ΛL) • √ nL l-1 Λ l-1 Λ X = √ nL l Λ l Λ X .
Although much work is dedicated to the study of the generalization performance of deep neural networks [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF][START_REF] Neyshabur | Exploring generalization in deep learning[END_REF][START_REF] Neyshabur | A PAC-Bayesian approach to spectrallynormalized margin bounds for neural networks[END_REF], the analysis of the Rademacher complexities of networks with particular architectures, such as convolutional neural networks [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], is an open question.

Conclusions

This The chaining method allows one to control the supremum of a stochastic process in terms of the sum of the metric entropies of its index set. This method was pioneered by Kolmogorov, and extended to an abstract setting by Dudley in the late sixties [START_REF] Talagrand | Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems[END_REF]. Dudley's result applies to a (centered) stochastic process G S = {G s : s ∈ (S, ρ)} indexed by a subset of a (pseudo-)metric space (S, ρ) which satisfies the following increment condition:

∀ > 0, P T (|G s -G s | > ) 2 exp - 2 2ρ 2 (s, s ) . ( 4.1)
This result can be formulated as follows:

∀δ > 0, E sup ρ(s,s ) δ |G s -G s | K δ 0 ln N ( , S, ρ)d , (4.2)
where K is a universal constant. In the particular case when G S is a symmetric process, such as a Gaussian process, it holds that

E sup s,s |G s -G s | = 2E sup s G s .
Then, Inequality (4.2) can be re-written in a handy way as

E sup s G s K diam(S) 0 ln N ( , S, ρ)d , (4.3)
where diam (S) = sup s,s ∈S ρ (s, s ) and the constant K is different from that in Inequality (4.2).

A Rademacher process is a sub-Gaussian process (see Appendix B), and thus its supremum can be controlled by Dudley's entropy integral (4.3).

As we discussed in Section 1.5, whether one can compute the integral in Inequality (4.3) is determined by the growth rate of the metric entropy as → 0. Instead, we will make use of the following bound on the empirical Rademacher complexity of F ⊂ L 1 (T ) derived in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] (which can be bounded by the entropy integral (4.3)):

∀t n ∈ T n , Rn (F) h(N ) + 2 N j=1 (h(j) + h(j -1)) ln N (h(j), F, d 2,tn ) n , (4.4)
where N ∈ N * and h : N → R + is a decreasing function with h(0) greater than the diameter of F. In other words, N is the number of steps taken to construct the chaining and h(j) is the radius of (open) balls that cover F at step j. Note the freedom one has in the choice of the value of N and the function h. Although there is no clear justification for a particular choice of h in the literature, in the sequel we will stick to geometrically decreasing functions.

With this introduction, we can formulate the goal of the present chapter as follows: i) apply the chaining formula (4.4) to F G,γ , ii) switch from the metric entropy of F G,γ to that of component classes G k , and iii) upper bound the obtained chaining formula under the choice of different combinatorial bounds and study the impact on the parameters of interest, particularly, the number C of categories.

To switch from the metric entropy of F G,γ to that of G k , we use the following decomposition formula due to Guermeur [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. This result is the generalization of Proposition 6.2 of Duan [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF] to L p -norms.

Lemma 17 (Lemma 1 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]) Let G be a class of functions satisfying Definition 3. Let F G and F G,γ be derived from G according to Definitions 4 and 8, respectively. Then, for any p ∈ [1, ∞] and for any > 0,

N ( , F G,γ , d p,zn ) N ( , F G , d p,zn ) C k=1 N C 1 p , G k , d p,xn , (4.5)
where z n ∈ Z n and x n ∈ X n .

Since the chaining is constructed in the L 2 -metric, only the values of p in [2, ∞] are of relevance in the decomposition formula (4.5).

The second step is based on the following considerations. First, to develop the chaining, we make the assumption that the component classes G k have polynomially growing fat-shattering dimensions:

Assumption 1 Let G be a class of functions satisfying Definition 3. We assume that there exists

a pair (K G , d G ) ∈ R 2 + such that ∀ ∈ (0, M G ] , max 1 k C -dim (G k ) K G -d G .
This assumption is not restrictive, since it holds true for many well-known classifiers: support vector machines with d G = 2 (Theorem 4.6 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF]), feedforward neural networks with d G = 2l

for l layers (Corollary 27 in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]), and in general, Lipschitz classifiers on metric spaces, such as nearest neighbours (Corollary 4 in [START_REF] Gottlieb | Efficient classification for metric data[END_REF]).

For [0, 1]-valued function classes with polynomial fat-shattering dimensions, i.e., -dim (F) [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF][START_REF] Mendelson | A few notes on statistical learning theory[END_REF] derived the following result:

K F -d F with ∈ (0, 1], Mendelson
R m (F) K √ m            1, if 0 < d F < 2, ln 3 2 m, if d F = 2, m 1 2 -1 d F ln 1 d F (m), if d F > 2,
where the constant K depends on the growth rate d F , and K F . One can notice that the chaining bound is developed into three cases based on the rate of growth of the fat-shattering dimension.

In other words, the capacity of the function class dictates the computation of the chaining bound.

The author rightly so calls this phenomenon the phase transition to underline the abrupt change with respect to the dependency on the sample size m when d F = 2. This result has been extended

to the multi-class setting by Guermeur [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] by combining the decomposition formula (4.5) with p = 2 and the combinatorial bound of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. In this extension, the phase transition is also observed with respect to the number of categories and the margin parameter γ:

Theorem 12 (After Theorem 7 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]) Let G be a class of functions satisfying Assumption 1. For γ ∈ (0, 1], let F G,γ be class of functions deduced from G according to Definition 8.

Then, there is a constant K that depends on d G and K G such that

R m (F G,γ ) K √ m                    C d G +2 4 γ 1-d G 2 ln 1 2 √ C γ , if 0 < d G < 2, C log 2 m C ln 1 2 √ m γC 1 4 , if d G = 2, C 2+d G 2d G γ 1-d G 2 m 1 2 -1 d G ln 1 2 1 γ m C 1 d G , if d G > 2.
This result improves the dependency of the Rademacher complexity on C over the one obtained via the direct decomposition of this capacity measure in Chapter 3. The bounds that we obtain in the present chapter are similar to Theorem 12. Particularly, we demonstrate that one can further improve the dependency on the number of classes. In Section 4.1, we develop chaining bounds in the L ∞ -norm for which the decomposition formula ( 17) is optimized with respect to C.

This yields a radical dependency on C irrespective of the growth rate d G , but slightly worsens the one on m. Our main contribution is in Section 4.2, where we derive new combinatorial bounds (dimension-free and not) by generalizing that of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] to L p -norms with p ∈ N * \{1, 2}. These bounds allow us to adapt to the phase-transition phenomenon and improve the dependency on C over that in Theorem 12 without worsening the ones on m and γ.

L ∞ -norm Metric Entropy

The decomposition formula, Inequality (4.5), is optimized with respect to C as p gets larger, and for p = ∞, C disappears altogether from the scales of the covering numbers:

N ( , F G,γ , d ∞,zn ) C k=1 ln N ( , G k , d ∞,xn ) . (4.6)
Notice that the the chaining formula (4.4) involves the covering numbers in the L 2 -norm, and to apply the decomposition (4.6) to it, we will use the norm ordering of the covering numbers, Inequality (1.5). For any sample z m = ((x i , y i )) 1 i m ∈ Z m , this gives:

Rm (F G,γ ) h(N ) + 2 N j=1 (h(j) + h(j -1)) C k=1 ln N ( , G k , d ∞,xm ) n . (4.7)
Below, we first derive a chaining bound for general function classes. Then, we consider classes of linear functions, for which we show that by using the corresponding metric entropy results leads to the chaining bound with a better convergence rate.

General Case

For classes of real-valued functions, Alon and co-authors [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] derived the following L ∞ -norm combinatorial bound generalizing the classical Sauer-Shelah lemma [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Shelah | A combinatorial problem; stability and order for models and theories in infinitary languages[END_REF]:

Lemma 18 (After Lemma 3.5 in [1]) Let F be a class of functions from T to [-M F , M F ] with M F ∈ R + . For ∈ (0, M F ], let d( ) = -dim (F). Then, for all ∈ (0, 2M F ], N ∞ ( , F, n) 2 16M 2 F n 2 d( 4 ) log 2 4M F en d ( 4 )
.

L ∞ -norm Metric Entropy

Notice that, in terms of metric entropy, this bound grows as O(ln 2 n). Theorem 4.4 of Rudelson and Vershynin [START_REF] Rudelson | Combinatorics of random processes and sections of convex bodies[END_REF] addresses the conjecture made in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] concerning the question whether the exponent 2 could be reduced to 1. Their result, which is based on the comparison of the covering number of a set to the number of integer cells contained in it and its projections, reduces this exponent to some value in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF][START_REF] Samy | Extreme Classification (Dagstuhl Seminar 18291)[END_REF]. Since this is achieved at the cost of deteriorating the fatshattering dimension, in this thesis we will use Lemma 18. Applying it in the chaining formula (4.7) leads to the following bound on the Rademacher complexity:

Theorem 13 Let G be as in Definition 3 and, for any γ ∈ (0, 1], let F G,γ be deduced from G as in Definition 8. Then, under Assumption 1, there is a constant K that depends only on d G and

K G such that R m (F G,γ ) K C m                  γ 1-d G 2 ln m γ , if 0 < d G < 2, ln 2 m γ 2 3 , if d G = 2, γ 1-d G 2 m 1 2 -1 d G ln m γ , if d G > 2.
Proof We set h(j) = γ2 -j in the chaining bound (4.7):

Rm (F G,γ ) γ2 -N + 6γ N j=1 2 -j C k=1 ln N (γ2 -j , G k , d ∞,xm ) m . (4.8) Let d ( ) = max 1 k C -dim(G k ).
Then, applying Lemma 18 to G k , we have that for all ∈ (0, 2M G ],

ln

N ( , G k , d ∞,xm ) d 4 log 2 4M G em d 4 ln 32M 2 G m 2 .
Applying this bound in (4.8) and using the fact that ln(2a) 2 ln a for all a 2 result in

Rm (F G,γ ) γ2 -N + 6γ N j=1 2 -j 2Cd( γ2 -j 4 ) log 2 4M G em2 j d(γ2 -j-2 )γ ln 16M 2 G m2 2j γ 2 m .
Using the fact that d(γ2

-j-2 ) 1 for all j ∈ [ [ 1, N ] ] and that √ m < em gives Rm (F G,γ ) γ2 -N + 12γ N j=1 2 -j log 2 4M G em2 j γ ln(2)Cd( γ2 -j 4 ) m .
Next, under the polynomial growth assumption, Assumption 1,

Rm (F G,γ ) γ2 -N + 3γ 1-d G 2 2 d G +2 CK G m N j=1 2 j d G 2 -1 log 2 4M G em2 j γ . (4.9)
Now, the way we bound the right-hand side of the above inequality is determined by the value of d G . For d G ∈ (0, 2), we can let N → ∞ and upper bound the sum in (4.9) by the corresponding integral. For d G 2, on the other hand, one has freedom in the choice of the value of N . It could be set in such a way so as to optimize the right-hand side of (4.9) with respect to the dependencies on C, m and γ. Thus, we have the following cases.

First case: d G ∈ (0, 2). This is the only case for which the chaining bound (4.9) can be computed in the integral form:

Rm (F G,γ ) γ2 -N + 3γ 1-d G 2 2 d G +2 CK G m × N j=1 2 -j 2-d G 2 log 2      4M G em γ 2 -j 2-d G 2 2 2-d G      3γ 1-d G 2 2 d G +2 1 -2 d G -2 2 CK G m 2 d G -2 2 0 log 2 4M G em γ 2 2-d G d . (4.10)
The computation of the improper integral gives

2 d G -2 2 0 log 2 4M G em γ 2 2-d G d = 2 d G -2 2 log 2 8M G em γ + 2 d G 2 ln 2 (2 -d G ) 3 • 2 d G 2 log 2 8M G em γ 2 -d G .
Plugging this into (4.10) gives

Rm (F G,γ ) 2 3d G 2 +6 γ 1-d G 2 (2 -d G ) 1 -2 d G -2 2 log 2 8M G em γ CK G m .
Second case: d G 2. In this case, we can bound the right-hand side of (4.9) as:

Rm (F G,γ ) γ2 -N + 3γ 1-d G 2 2 d G +2 CK G m log 2 4M G em2 N γ j∈J 2 j d G 2 -1 We set N = log 2 m 1 d G . Then, Rm (F G,γ ) γ m 1 d G + 3 • 2 2+d G γ 1-d G 2 log 2   8M G em 1+ 1 d G γ   CK G m N j=1 2 j d G 2 -1 . (4.11)
If d G = 2, then:

Rm (F G,γ ) γ √ m + 48 log 2 2 8M G em 3 2 γ CK G m .
Otherwise, we can bound the geometric sum in (4.11) by

N j=1 2 j d G 2 -1 = 2 d G 2 -1 (N +1) -2 d G 2 -1 2 d G 2 -1 -1 < 2 d G 2 -1 (N +1) 2 d G 2 -1 -1
, which finally gives

Rm (F G,γ ) γ m 1 d G + 3 • 2 2d G γ 1-d G 2 2 d G 2 -1 -1 log 2   8M G em 1+ 1 d G γ   √ CK G m 1 d G .
To complete the proof, in all cases we take expectation with respect to the sample.

While having the matching dependency on the margin parameter γ with that of Theorem 12, Theorem 13 improves the dependency on C to a radical one irrespective of the capacity of the function class. This, however, is achieved at the expense of the extra logarithmic factor involving the sample size. Below we demonstrate that specifying a classifier improves upon this sample-size dependency.

Linear Classifiers

We switch from the general case to a specific one involving linear classifiers. To the best of our knowledge, the only metric entropy bounds for linear classifiers have been derived by Bartlett [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF], Williamson et al. [START_REF] Williamson | Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators[END_REF] and Zhang [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF]. At the basis of the L 2 -norm bound of Bartlett, Lemma 22 in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF], lies Maurey's lemma (Lemma 33 in Appendix A), and Theorem 3 of Zhang [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF] generalizes his result. The L ∞ -norm bound of Zhang, Theorem 4 in [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF], on the other hand, relies on the mistake bound due to Grove et al. [START_REF] Grove | General convergence results for linear discriminant updates[END_REF], and it is comparable to that of Williamson and coauthors obtained based on the operatory theory methods. We first demonstrate the extension of this bound to balls of a RKHS. To this end, we appeal to a special case of the mistake bound of Grove et al.: the well known perceptron's convergence theorem [START_REF] Rosenblatt | The perceptron: a probabilistic model for information storage and organization in the brain[END_REF][START_REF] Minsky | The perceptron: Principles of computational geometry[END_REF] extended to a Hilbert space. Then, we consider a particular RKHS: the Gaussian RKHS. Finally, the chaining bounds are developed based on these metric entropy bounds and compared.

Unspecified Kernel

We extend Theorem 4 of Zhang [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF] to an RKHS. This relies on the convergence result of the perceptron algorithm applied to the data living in a Hilbert space which is the direct sum of the RKHS H κ and R (Proposition 4 in Appendix D).

Lemma 19 Let κ : X × X → R be a reproducing kernel and let (H κ , • Hκ ) be the corresponding

RKHS. Let Λ X , Λ ∈ R + . Suppose that sup x∈X κ x Hκ Λ X . Let B Λ (H κ ) = h ∈ H κ : h Hκ Λ .
Then, for any > 0,

log 2 N ext ∞ ( , B Λ (H κ ) , n) 26Λ 2 Λ 2 X 2 log 2 2n 4Λ X Λ + 2 + 1 .
Proof Let H = H κ ⊕ R be the Hilbert space direct sum of H κ and R with an inner product

•, • H defined as

∀(f 1 , f 2 ) ∈ H 2 κ , ∀(r 1 , r 2 ) ∈ R 2 , (f 1 , r 1 ), (f 2 , r 2 ) H = f 1 , f 2 Hκ + r 1 r 2 .
For any

x n = (x i ) 1 i n ∈ X n , let B Λ (H κ ) | xn = {(f (x i )) 1 i n = ( f, κ x i ) 1 i n : f ∈ B Λ (H κ )} ⊆ [-Λ X Λ, Λ X Λ] n . Divide the interval -Λ X Λ -2 , Λ X Λ + 2 into l = 2 (2Λ X Λ + ) sub-intervals, each of length
no greater than /2. Let (θ j ) 0 j l be the boundaries of these sub-intervals with θ j+1 -θ j /2,

0 j l -1. Fix f ∈ B Λ (H κ ). For any i ∈ [ [ 1, n ] ],
choose maximum and minimum indices,

j1 (i, f ) ∈ [ [ 0, l -1 ] ] and j2 (i, f ) ∈ [ [ 1, l ] ],
respectively, so that

f (x i ) -θ j1(i,f ) /2 and -f (x i ) + θ j2(i,f ) /2. (4.12)
Now we want to find an -approximation of f in the d ∞,xn metric. Based on (4.12), a function

f ∈ B Λ (H κ ) with ∀i ∈ [ [ 1, n ] ] , f (x i ) -θ j1(i,f ) > 0 and -f (x i ) + θ j2(i,f ) > 0, (4.13)
satisfies

max 1 i n f (x i ) -f (x i ) < .
To find such a function we will use Proposition 4. First, we need to design a new dataset for the perceptron. Rewrite (4.12) as

(f, Λ), (κ x i , -θ j1(i,f ) /Λ) H /2 and (4.14) (f, Λ), (-κ x i , θ j2(i,f ) /Λ) H /2. Let h i = (κ x i , -θ j1(i,f ) /Λ) and h n+i = (-κ x i , θ j2(i,f ) /Λ) for 1 i n. Let D = ((h i , y i )) 1 i 2n ∈ (H × {-1, +1}
) 2n be an input for the perceptron with all y i = +1. According to (4.14), the function w, • H with w = (f, Λ) ∈ H, yields a margin γ 2 on D. Thus, using Inequality (D.1), the number n of updates is upper bounded as:

n w 2 H max 1 k m h i k 2 H γ 2 4 2 f 2 Hκ + Λ 2 Λ 2 X + Λ X + 2Λ 2 4 2 • 2Λ 2 • Λ 2 X + Λ 2 X + Λ X Λ + 2 4Λ 2 8Λ 2 2 • 2Λ 2 X + Λ 2 X Λ Λ + Λ 2 X Λ 2 4Λ 2 26 ΛΛ X 2 . (4.15)
The function the algorithm converges to is of the form:

(f * , zΛ), • H = m k=1 h i k , • H = n i=1 α i κ x i , -θ j1(i,f ) /Λ + n i=1 β i -κ x i , θ j2(i,f ) /Λ , • H , (4.16)
where α i , β i ∈ N indicate the number of times h i and h n+i , respectively, appear in the updates of the perceptron with n i=1

(α i + β i ) = n . According to Proposition 4 (in Appendix D), for all i ∈ [ [ 1, n ] ],
(f * , zΛ), (κ x i , -θ j1(i,f ) /Λ) H > 0 and (f * , zΛ), (-κ x i , θ j2(i,f ) /Λ) H > 0.

(4.17)

Note that this ensures that z > 0. Now, rewriting (4.13) as

( f , Λ), (κ x i , -θ j1(i,f ) /Λ) H > 0 and ( f , Λ), (-κ x i , θ j2(i,f ) /Λ) H > 0,
one can see that the function f can be constructed as f = f * /z. Thus, the covering number of B Λ (H κ ) is no greater than the number of functions that can be expressed as (4.16) and that satisfy (4.17). Estimating this number calls for the introduction of the following notation: let

S 1 = ((κ x i , -θ j /Λ)) 1 i n,0 j l-1 ∈ H nn ,
and

S 2 = ((-κ x i , θ j /Λ)) 1 i n,1 j l ∈ H nn .
Let n i,j , m i,j be non-negative integers that indicate the number of times the elements of S 1 and S 2 , respectively, appear in the updates of the perceptron. Denote the right-hand side of Inequality (4.15) by M = 26 ΛΛ X

2

. Then, the covering number of B Λ (H κ ) is no greater than the number s of non-negative integer solutions of

n i=1   l-1 j=0 n i,j + l j=1 m i,j   M.
The number of terms on the left hand side is

|S 1 | + |S 2 | = 2nl. Let k = 2nl. Using Lemma 42
in Appendix G, we get

s 1 + M l=1 k l (k + 1) M .
Consequently, we obtain

ln N ext ∞ ( , B Λ (H κ ) , n) M ln (k + 1) .
Substituting the values of M and k in the right-hand side gives the desired bound.

Clearly, this result is an improvement over that of Alon et al., Lemma 18 applied to linear classifiers, by a factor ln 1 , and this gain is propagated through the chaining bound:

Theorem 14 (After Lemma 19 in [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF]) Let G = B Λ (H κ ) C . For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 8. Suppose

sup x∈X κ x Hκ Λ X . Then R m (F G,γ ) γ √ m + 62ΛΛ X C m log 2 2 √ m ln 2m 16ΛΛ X γ √ m + 2 + 1 .
Proof Set h(j) = γ 2 j in the chaining formula (4.4) applied to F G,γ :

Rm (F G,γ ) γ2 -N + 6γ √ m N j=1 2 -j ln (N (γ2 -j , F G,γ , d 2,zm )).
Apply in sequence the norm ordering of covering numbers (1.5), the decomposition formula (4.5)

and Inequality (1.2) to the metric entropy:

ln N γ2 -j , F G,γ , d 2,zm ln N γ2 -j , F G,γ , d ∞,zm C ln N γ2 -j , B Λ (H κ ) , d ∞,xm C ln N ext γ2 -(j+1) , B Λ (H κ ) , d ∞,xm .
Thus,

Rm (F G,γ ) γ2 -N + 6γ C m N j=1 2 -j ln N ext γ2 -(j+1) , B Λ (H κ ) , d ∞,xm .
Applying Lemma 19 yields

R m (F G,γ ) γ2 -N + 62ΛΛ X C m N j=1 ln 2m 8ΛΛ X γ 2 j + 2 + 1 .
Finally, setting N = 1 2 log 2 (m) and upper bounding the sum in a straightforward way give the desired result.

Since according to Theorem 4.6 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF], the growth rate d G of the class G of Theorem 14 is 2, then we can compare this result with the corresponding case of Theorem 13, our contribution.

Notice that both results provide the same dependency on C, but Theorem 14 yields a sharper dependency on the sample size: O ln

3 2 (m) √ m instead of O ln 2 (m) √ m .

Gaussian Kernel

We now specify the kernel and focus on the most common choice: the Gaussian kernel defined as

∀σ > 0, ∀x, x ∈ R d , κ σ x, x = exp -σ -2 x -x 2 2 ,
where σ is the width of the kernel κ σ and • 2 denotes the Euclidean norm. Note that Lemma 19 is insensitive to the specifics of the RKHS induced by a particular kernel. The specification of the kernel calls for a dedicated approach: be it of interest in the probability or the learning theory literature, much work has been dedicated to the entropy estimates of balls in Gaussian RKHSs [START_REF] Goodman | Some probability and entropy estimates for Gaussian measures[END_REF][START_REF] Kuelbs | Metric entropy and the small ball problem for gaussian measures[END_REF][START_REF] Williamson | Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators[END_REF][START_REF] Zhou | The covering number in learning theory[END_REF][START_REF] Guo | Covering numbers for support vector machines[END_REF][START_REF] Kühn | Covering numbers of Gaussian reproducing kernel Hilbert spaces[END_REF][START_REF] Steinwart | Fast rates for support vector machines using Gaussian kernels[END_REF][START_REF] Steinwart | Support vector machines[END_REF]. Particularly, Farooq and Steinwart [START_REF] Farooq | Learning rates for kernel-based expectile regression[END_REF] derived the following result based on a result by van der Vaart and van Zanten [START_REF] Van Der Vaart | Adaptive Bayesian estimation using a Gaussian random field with inverse gamma bandwidth[END_REF].

Theorem 15 (After Theorem 5 in [START_REF] Farooq | Learning rates for kernel-based expectile regression[END_REF]) Let H κσ be a Gaussian RKHS over X ⊂ R d . Let B Λ (H κσ ) denote a ball of radius Λ ∈ R + in H κσ . Then, there exists a constant K > 0 which depends on X , such that for all ∈ (0, Λ/2) and all p ∈ (0, 1] ,

ln N ext ( , B Λ (H κσ ) , d ∞ ) KΛ p σ d p d + 1 ep d+1 , (4.18)
where d ∞ denotes the metric induced from the supremum norm.

One can notice how the width parameter σ comes into play in the entropy bound. From this result it follows that the balls of the Gaussian RKHSs satisfy Pollard's entropy condition:

∞ 0 ln N ext ( , B Λ (H κσ ) , d ∞ )d KΛ p σ d d + 1 ep d+1 Λ/2 0 -p 2 d = 2 2 -p Λ 2 2-p 2 KΛ p σ d d + 1 ep d+1 (4.19) < ∞.
Thus, according to Theorem 2, they are universal Donsker classes, and the corresponding chaining bound is computed in a straightforward manner as demonstrated below.

Theorem 16 Let G = B Λ (H κσ ) C . For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 8. There exists a constant K which depends on X such that for all

p ∈ (0, 1], R m (F G,γ ) 24 2 -p (2Λ) p K σ d d + 1 ep d+1 γ 2 2-p • C m .
Proof For the proof we use the integral form of the chaining formula (4.3) with K = 8 √ 2 (see Bartlett's lecture notes):

Rm (F G,γ ) 8 √ 2 γ/2 0 ln N ( , F G,γ , d 2,zm ) m d . (4.20)
Using the same chain of inequalities as in the proof of Theorem 14, as well as the fact that for

all f, f ∈ F, d ∞,tn (f, f ) d ∞ (f, f ), we obtain: ln N ( , F G,γ , d 2,zm ) C ln N ext 2 , B Λ (H κσ ) , d ∞ .
To conclude the proof, we apply the last inequality to the right-hand side of (4.20), then use

Rm (F G,γ ) 8 √ 2 γ/2 0 C ln (N ext ( /2, B Λ (H κσ ) , d ∞ )) m d 8 √ 2 (

L p -norm Combinatorial Bound

In the preceding section, we saw that for general function classes using the decomposition re- Theorem 17 Let F be a class of functions from

T to [-M F , M F ] with M F ∈ [1, +∞). For ∈ (0, M F ], let d ( ) = -dim (F). For all values of p ∈ N * \ {1, 2} and ∈ (0, M F ], (a) if n d 15p , then ln N p ( , F, n) 2d 15p ln   15epnM F d 15p   ; (b) ln N p ( , F, n) 10p d 36p ln 7p 1 7 M F .
Proof Let T n = {t i : 1 i n} ⊂ T and t n = (t i ) 1 i n . Let F be a subset of F of maximal cardinality -separated with respect to the pseudo-metric d p,tn . We distinguish three major steps in the proof: i) discretize the functions in the set F | Tn , ii) demonstrate that the set of discretized functions is separated, and iii) upper bound the cardinality of the discretized set. The purpose of discretization is to reduce the original problem to the one that can be addressed by combinatorial means: we upper bound the packing number of the discretized set which is then related to that of the original set via the step (ii). obtained by discretizing the ones in F | Tn as follows:

Fη = f : f (t i ) = f (t i ) + M F η , i ∈ [ [ 1, n ] ] , f ∈ F | Tn .
We claim that with such a discretization, for any f1 , f2 ∈ Fη , d p,tn f1 , f2

. Using | a - b | p (max(0, |a -b| -1)) p for all a, b ∈ R + , d p,tn f1 , f2 = 1 n n i=1 f 1 (t i ) + M F η - f 2 (t i ) + M F η p 1 p 1 n i∈I 1 η |f 1 (t i ) -f 2 (t i )| -1 p 1 p
, where I denotes the set of indices such that

1 η |f 1 (t i ) -f 2 (t i )| 1.
Next, by the inverse triangle inequality, d p,tn (f 1 , f 2 ) d p,tn (f 1 , 0) -d p,tn (f 2 , 0) for all f 1 , f 2 ∈ F, the right-hand side of the above inequality can be bounded as

d p,tn f1 , f2 1 η 1 n i∈I |f 1 (t i ) -f 2 (t i )| p 1 p - |I| n 1 p 1 η 1 n i∈I |f 1 (t i ) -f 2 (t i )| p 1 p -1. (4.21)
Let I c denote the complement of I. Now, by definition of F ,

1 n i∈I |f 1 (t i ) -f 2 (t i )| p + 1 n i∈I c |f 1 (t i ) -f 2 (t i )| p p .

It follows that

p 1 n i∈I |f 1 (t i ) -f 2 (t i )| p + |I c |η p n 1 n i∈I |f 1 (t i ) -f 2 (t i )| p + η p =⇒ ( p -η p ) 1/p 1 n i∈I |f 1 (t i ) -f 2 (t i )| p 1/p .
Applying the last inequality to (4.21) and using

((a -b) + b) ((a -b) 1/p + b 1/p ) p with a, b ∈ R +
and a b (where we set a = ( + 2) p and b = 1), we get

d p,tn f1 , f2 1 η ( p -η p ) 1/p -1 = ( + 2) p -1 1/p -1 .
This proves our claim. Then, it follows that

M ( , F , d p,tn ) M( , Fη , d p,tn ) = | Fη |. (4.22)
The major step that remains to perform to obtain the claimed bound is to upper bound the right-hand side of (4.22). To this end, we will appeal to Proposition 7 in Appendix E. Let d s be the strong dimension of Fη . By part (1) of Lemma 3.2 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF],

d s η 2 -dim( F | Tn ) = 8(4K p ) 1/p + 4 -dim( F | Tn ).
By Lemma 1 and the fact that p 3, on the other hand, we have

8(4K p ) 1/p + 4 < 8 • 4 1/p p + 4 < 15p.
We can substitute this result in the upper bound on d s based on the fact that the fat-shattering dimension is a non-increasing function of the scale:

d s 15p -dim( F | Tn ) 15p -dim(F) = d 15p .
Now, according to Proposition 7,

| Fη |   eN n d 15p   2d 15p   en d 15p 2M F η   2d 15p   en d 15p 8M F (4K p ) 1/p + 4M F   2d 15p . (4.23)
Applying Lemma 1 to the right-hand side of (4.23) and simplifying we get

| Fη |   15enM F p d 15p   2d 15p . (4.24)
We apply the relation (4.22) and Lemma 2 in sequence to the left-hand side of (4.24), and take the supremum over t n ∈ T n of both sides to obtain the claimed result.

(b) To derive a dimension-free combinatorial bound we use the L p -norm generalization of the probabilistic extraction principle: Lemma 8 of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. According to this lemma, there exists a subset

T q = {t i k : 1 k q} of T n of cardinality q 112 (2M F ) 2p ln (|F |) 3 2p , ( 4.25)
such that F is 1 = /2 p+1 p -separated with respect to d p,tq , with t q = (t i k ) 1 k q . Let F | Tq denote the class F whose domain is restricted to T q . We have

|F | = M 1 , F , d p,tq = M 1 , F | Tq , d p,tq = | F | Tq |. (4.26) Let η = 1 + 2
. We discretize F | Tq in a similar way as in part (a):

Fη = f : f (t i k ) = f (t i k ) + M F η , k ∈ [ [ 1, q ] ] , f ∈ F | Tq .
Applying the same procedure as in part (a), we obtain that for any f1 , f2 ∈ Fη , d p,tq f1 , f2 , and hence Next, we bound d s using part (1) of Lemma 3.2 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] and Lemma 1:

M 1 , F , d p,tq M( , Fη , d p,tq ) = | Fη |. ( 4
d s η 2 -dim( F | Tq ) = 2 4p+1 p (4K p ) 1/p + 2 3p+1 p -dim( F | Tq ) 16 • 2 3 p p + 8 • 2 1 p -dim( F | Tq ) 36p -dim( F | Tq ).
Substituting the last inequality in (4.29) and applying Lemma 36 to K p , we obtain

ln (|F |) 4d 36p ln 2576 • 2 2p+1 eM 2p+1 F 4 1/p p 3 2p+1 10p d 36p ln 7p 1 7 M F .
Assumption 1, there is a constant K that depends only on d G and K G such that for all C > 4,

R m (F G,γ ) K C m                        γ 1-d G 2 (ln(C)) d G 2 + 1 2 ln 1 2 ln 1 7 C γ , if 0 < d G < 2, ln(C) ln m C ln 1 2 m 3 2 ln C γ √ C , if d G = 2, γ 1-d G 2 m 1 2 -1 d G (ln(C)) d G 2 -2 ln 1 2   m 1+ 1 d G γ ln(C)   , if d G > 2 and m C 1.2 .
Compared to Theorem 12, one can see that in all three cases, we have the matching dependencies on m and γ, but the dependency on C is improved: the powers of C are replaced by powers of ln(C). It is interesting to note that, in the third case, when d G 4, which is true for instance for feedforward neural networks (see Corollary 27 in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]), the dependency on C is slightly better than radical. This is, however, at the cost of the constant factor d

d G G .
Proof [Proof of Theorem 18] For all j ∈ N, we set h(j) = γ2 -α(d G )j where α(d G ) > 0 for all

d G ∈ R * + in (4.4) applied to F G,γ : Rm (F G,γ ) γ2 -α(d G )N + 2 N j=1 γ2 -α(d G )j + γ2 -α(d G )(j-1) ln N γ2 -α(d G )j , F G,γ , d 2,zm m , (4.32)
First case: d G ∈ (0, 2). Apply Inequalities (1.5) and (4.31) in sequence to the right-hand side of (4.32) and use Assumption 1 to get

Rm (F G,γ ) γ2 -α(d G )N + 2 10C log 2 (2C) m N j=1 γ2 -α(d G )j + γ2 -α(d G )(j-1) ×   d γ2 -α(d G )j 72 log 2 (2C) ln   14M G log 1 7 2 (2C) γ2 -α(d G )j     1/2 γ2 -α(d G )N +2 10C log 2 (2C)K G m (72 log 2 (2C)) d G 2 γ 1-d G 2 1 + 2 α(d G ) × N j=1 2 -α(d G ) 1- d G 2 j ln 1 2   14M G log 1 7 2 (2C) γ2 -α(d G )j   . Letting α(d G ) = 2 2 -d G , we obtain Rm (F G,γ ) γ2 -2 2-d G N +2 10C log 2 (2C)K G m (72 log 2 (2C)) d G 2 γ 1-d G 2 1 + 2 2 2-d G × N j=1 2 -j ln 1 2   14M G log 1 7 2 (2C) γ2 -2 2-d G j   = γ2 -2 2-d G N + 4 10C log 2 (2C)K G m (72 log 2 (2C)) d G 2 γ 1-d G 2 1 + 2 2 2-d G × N j=1 2 -j -2 -j-1 ln 1 2   14M G log 1 7 2 (2C) γ2 -2 2-d G j   .
Taking N → ∞, we can upper bound the last expression as

Rm (F G,γ ) 4 10C log 2 (2C)K G m (72 log 2 (2C)) d G 2 γ 1-d G 2 1 + 2 2 2-d G × 1/2 0 ln 1 2   14M G log 1 7 2 (2C) γ 2 2-d G   d . Denote K = 14M G log 1 7
2 (2C) /γ and let us now compute the integral

L = 1/2 0 ln 1 2 K/ 2 2-d G d = 2 2 -d G 1/2 0 ln 1 2   K 2-d G 2   d . Set = K 2-d G 2
e -t 2 . Then,

L = 2 2 -d G K 2-d G 2 ∞ ln 1 2 2K 2-d G 2 t • (2te -t 2 )dt.
Applying the integration by parts formula, we obtain

L = 2 2 -d G K 2-d G 2    ln 1 2 2K 2-d G 2 2K 2-d G 2 + ∞ ln 1 2 2K 2-d G 2 e -t 2 dt    1 2(2 -d G )   ln 1 2 2K 2-d G 2 + 1 2 ln 1 2 2K 2-d G 2    .
Consequently,

Rm (F G,γ ) 4 10 • 72 d G • K G 2(2 -d G ) • √ C(log 2 (2C)) 1/2+d G /2 √ m γ 1-d G 2 1 + 2 2 2-d G ×   ln 1 2 2K 2-d G 2 + 1 2 ln 1 2 2K 2-d G 2    .
Second case: d G 2. In this case, we apply Inequalities (1.5) and (4.30) to (4.32) and use Assumption 1 to get

Rm (F G,γ ) γ2 -α(d G )N + 2 2C m N j=1 γ2 -α(d G )j + γ2 -α(d G )(j-1) × d γ2 -α(d G )j 30 log 2 (2C) ln 30emM G log 2 (2C) γ2 -α(d G )j 1/2 γ2 -α(d G )N + 2 2CK G m (30 log 2 (2C)) d G /2 γ 1-d G 2 1 + 2 α(d G ) × N j=1 2 α(d G ) d G -2 2 j ln 1 2 30emM G log 2 (2C) • 2 α(d G )j γ . (4.33)
Unlike the first case, we now control the number of steps N in (4.33) through C and m. The aim is to optimize the dependencies on them while making sure that (i) N is a strictly positive integer, and (ii) as m → ∞, N → ∞.

Now, if d G = 2, set α(d G ) = 1.
Thus, from (4.33), we have

Rm (F G,γ ) γ2 -N + 180 2CK G m log 2 (2C) N j=1 ln 1 2 30emM G log 2 (2C) • 2 j γ .
Setting N = log 2 m C and bounding the series, we obtain

Rm (F G,γ ) γ C m + 180 2CK G m log 2 (2C) N j=1 ln 1 2 30emM G log 2 (2C) • 2 j γ < γ C m + 180 2CK G m log 2 (2C) log 2 m C ln 1 2 60em 3/2 log 2 (2C) M G γ √ C .
For the final case,

d G > 2, we set α(d G ) = 2 d G -2
in (4.33) and bound the geometric series:

Rm (F G,γ ) γ2 -2 d G -2 N +2 2CK G m (30 log 2 (2C)) d G /2 γ 1-d G 2 (1 + 2 2 d G -2 ) × N j=1 2 j ln 1 2   30emM G log 2 (2C) • 2 2 d G -2 j γ   γ2 -2 d G -2 N +4 • 2 N 2CK G m (30 log 2 (2C)) d G /2 γ 1-d G 2 (1 + 2 2 d G -2 ) × ln 1 2   30emM G log 2 (2C) • 2 2 d G -2 N γ   . (4.34) Now, let N =     d G -2 2d G log 2   m log 2d G 2 (2C) 1 d G      
. Note that, with the assumption m C

Rm (F G,γ ) γ log 2 2 (2C) 1 d G m 1 d G + 8 2K G • 30 d G /2 d d G -2 G γ 1-d G 2 (1 + 2 2 d G -2 ) × √ C (log 2 (2C)) 2-d G /2 m 1 d G ln 1 2   60ed 2 G m 1+ 1 d G M G γ log 2 (2C)   .

Conclusions

In this chapter, we related the Rademacher complexity to the metric entropy via the chaining method, and performed the decomposition at the level of the latter measure. We studied what impact different combinatorial bounds, the results that relate the metric entropy to the fatshattering dimension, have on the dependencies of the Rademacher complexity on C, m and γ.

As in [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF][START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF], we assumed that the fat-shattering dimensions of the component classes grow no faster than polynomially with the inverse of their scales. The combinatorial bound considered in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] is the L 2 -norm one of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. When applied in the chaining, this gives a sublinear (but still close to a linear) dependency on C, and the dependency on the sample size matches with that in [START_REF] Mendelson | A few notes on statistical learning theory[END_REF].

The fact that the decomposition result is optimized with respect to C in the L ∞ -norm motivated us to use the combinatorial bound of Alon et al. [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] in the chaining. It led to a better (radical) dependency on C, irrespective of the growth rate of the fat-shattering dimension. However, the O(ln2 (m)) dependence of this combinatorial bound propagated through the chaining and deteriorated the convergence rate in m. Yet, we demonstrated that by specifying a classifier, and thus making use of the corresponding metric entropy bound in the chaining, the dependency on the sample size could be improved. In particular, we extended the metric entropy bound of Zhang [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF] At the basis of this result lie the decomposition of the L 2 -norm metric entropy and Talagrand's bound on the fat-shattering dimension [START_REF] Talagrand | Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions[END_REF]. The extension of Duan's result to the multi-category classification setting is straightforward [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]. In Section 5.2, we present a new decomposition result for the fat-shattering dimension based on the L ∞ -norm metric entropy. This gives an improved dependency on the number C of categories compared to that based on Duan's result. We also consider the matrix covering bound of Bartlett and coauthors [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF]. The basic idea of this method is to collect the images of vector-valued functions into matrices and estimate the metric entropy of a set of matrices following the method of Zhang [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF]. The advantage over the standard metric entropy bounds (which are based on vectors) is that it allows one to exploit the interactions between the component functions, consequently, eliminating a linear factor C from the bounds (a linear dependency on C is usually a consequence of dealing with each component function independently). Using this bound gives a decomposition result with a logarithmic dependency on C. This, however, applies only to linear classifiers.

In Section 5.3, we decompose the fat-shattering dimension of yet another family of classifiers, Lipschitz classifiers on doubling spaces studied in [START_REF] Gottlieb | Efficient classification for metric data[END_REF]. The derivation of this result with a linear dependency on C is rather straightforward.

Decomposition via the Rademacher Complexity

Based on the argument made by Mendelson [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF], one can deduce the following relationship between the fat-shattering dimension and the Rademacher complexity of a class F of real-valued functions on T : if the worst-case empirical Rademacher complexity of F over n ∈ N * points is less than some > 0, then its fat-shattering dimension at scale is less than n. Thus, an efficient

s d = (s i ) 1 i d ∈ {-1, 1} d , there exists f s d in F such that d i=1 s i (f s d (t i ) -u(t i )) d .
It implies

∀s d ∈ {-1, 1} d , sup f ∈F d i=1 s i (f (t i ) -u(t i )) d .
Then,

1 2 d sn∈{-1,1} d sup f ∈F d i=1 s i (f (t i ) -u(t i )) d ,
which is equivalent to

E σ d sup f ∈F d i=1 σ i (f (t i ) -u(t i )) d .
Since Rademacher variables are centered, the above bound reduces to

1 d E σ d sup f ∈F d i=1 σ i f (t i ) .
It follows that if for some n ∈ N * ,

1 n sup tn∈T n E σn sup f ∈F n i=1 σ i f (t i ) , then d n.
Remark 2 Srebro et al. [START_REF] Srebro | Smoothness, low noise and fast rates[END_REF] upper bounded the fat-shattering dimension directly by the Rademacher complexity as follows:

d( ) 4n R2 n (F) 2 .
Given that this bound involves a factor 4 and that this Rademacher complexity is defined based on the absolute value of the sum n i=1 σ i f (t i ), using Lemma 20 one can get a slightly tighter bound on the fat-shattering dimension.

Our goal now is to make use of the efficient bounds on the Rademacher complexity of the margin class. As we pointed out in Chapter 3, the decomposition results of Lei et al. [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF],

and Maurer [START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF] allow one to employ interactions between the component functions, and as a consequence, for linear function classes these give bounds on the Rademacher complexity with as tight as a logarithmic dependency on C. Below, we compare these two approaches, and demonstrate the bounds they produce on the fat-shattering dimension. We start with the result of Lei et al. [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF] (the proof is given in Appendix F).

Theorem 19 (After Corollary 8 [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF]) Let κ : X × X → R be a reproducing kernel and let

(H κ , • Hκ ) be the corresponding RKHS. Let Λ X , Λ ∈ R + . Suppose that sup x∈X κ x Hκ Λ X . Let p 2. For any h = (h k ) 1 k C ∈ H C κ , let h Hκ,p = C k=1 h k p Hκ 1 p and let B p,Λ = h ∈ H C κ : h Hκ,p Λ .
For any γ ∈ (0, 1], let F B p,Λ ,γ be the margin class built from B p,Λ according to Definition 8. Then,

Rm F B p,Λ ,γ <        4 √ eπΛΛ X ln C √ m , if p = 1; 4 √ πΛΛ X C m , if p = 2.
(5.1)

Thanks to Lemma 20, we can take benefit from this result to bound the fat-shattering dimension of F B p,Λ ,γ as follows.

Corollary 2 Let F B p,Λ ,γ be as in Theorem 19. Fix ∈ (0, γ] and let d(

) = -dim F B p,Λ ,γ . Then, for n ∈ N * satisfying Rn F B p,Λ ,γ , d( )        16eπΛ 2 Λ 2 X ln 2 C 2 , if p = 1; 16πΛ 2 Λ 2 X C 2 , if p = 2.
Proof It suffices to set the right-hand side of (5.1) less than and solve for n.

With Maurer's approach, Lemma 14 in Chapter 3, the following bound holds.

Theorem 20 Let F B p,Λ ,γ be as in Theorem 19. Then,

Rm F B p,Λ ,γ <        2 √ eΛΛ X ln C m , if p = 1; 2ΛΛ X C m , if p = 2.
The proof (given in Appendix F) follows that of Theorem 19, with all orthogaussian sequences replaced by Rademacher ones. Switching from the Gaussian complexity to the Rademacher one results in the following improvement. Compared to Theorem 19, for p = 1, the gain is by a factor 2 √ π ln C and for p = 2, the gain is only in terms of a constant: 2 √ π. This has the following consequence on the growth of the fat-shattering dimension:

Corollary 3 Let F B p,Λ ,γ be as in Theorem 19. Fix ∈ (0, γ] and let d(

) = -dim F B p,Λ ,γ . Then, for n ∈ N * satisfying Rn F B p,Λ ,γ , d( )        4eΛ 2 Λ 2 X ln C 2 , if p = 1; 4Λ 2 Λ 2 X C 2 , if p = 2.
Remark 3 The bound of Corollary 3 can be compared to that on the margin Natarajan dimension of the multi-class support vector machines, i.e., the one established in Lemma 10 in [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]:

d N ( ) Λ 2 Λ 2 X C 2 .
Given that the fat-shattering dimension of the margin class dominates the margin Natarajan dimension (Inequality (1.7)), when p = 2, there is a very small gap between these two bounds: a factor of 4. Clearly, the gain provided in Corollary 3 with respect to the dependency on C corresponds to the case p = 1 for which it is O(ln C).

In the following, we show another approach to decompose the fat-shattering dimension which is based on the metric entropy.

Decomposition via the Metric Entropy

The decomposition of the fat-shattering dimension of a composite class in terms of that of component classes via the metric entropy are due to Bartlett [7] and Duan [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF]. Bartlett's result concerns a specific classifier: feedforward neural networks. For such a network with two layers, his decomposition can be viewed as that of the fat-shattering dimension of the absolutely convex hull of a bounded function class:

Theorem 21 (After Theorem 17 in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]) Let F be a class of functions from

T to [-M F , M F ] with M F ∈ R + . Let absconv(F) = N i=1 λ i f i : N ∈ N * , f i ∈ F, λ i ∈ R, N i=1 |λ i | 1 . For ∈ (0, M F ], let d( ) = -dim(F). Then, -dim(absconv(F)) KM F d 32 2 ln 2 M F d 32 ,
where K is a universal constant.

On the other hand, Duan's result, Theorem 6.2 in [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF], concerns the fat-shattering dimension of a function class obtained on the basis of a uniformly continuous function with a vector-valued domain. In the margin multi-category classification setting, his result takes the following form:

Lemma 21 (Lemma 6 in [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]) Let G be as in Definition 3 and F G be as in Definition 4. Let

d( ) = -dim(F G ) and let d G * ( ) = max 1 k C -dim(G k ). Then, for all ∈ (0, M G ], d ( ) 462Cd G * 96 √ C ln 24M G √ C . (5.2)
At the basis of this result lies the following chain of bounds: i) an upper bound on the fatshattering dimension by the L 2 -norm metric entropy due to Talagrand [START_REF] Talagrand | Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions[END_REF] (Proposition 1 below),

ii) the decomposition of the L 2 -norm metric entropy, Lemma 17, and finally iii) the L 2 -norm metric entropy bound of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. Notice how the number of categories appears in the scale of the fat-shattering dimension-this is due to the instantiation of Lemma 17 in the L 2 -norm. Now, for classes with polynomially growing fat-shattering dimensions, i.e., for the ones satisfying Assumption 1, the bound (5.2) exhibits a superlinear dependency on C:

d ( ) 462CK G 96 √ C d G ln 24M G √ C . (5.3)
For instance, for support vector machines, for which d G = 2, this result scales as a O C 2 ln √ C .

In the following subsections, we demonstrate two approaches with at most a linear (up to a logarithmic factor) dependency on C. The first one makes use of the fact that Lemma 17 is optimized with respect to C when instantiated in the L ∞ -norm, i.e., C disappears from the scales of covering numbers of the component classes G k . We also take benefit from the fact that there is a straightforward relationship between the fat-shattering dimension and the L ∞ -norm metric entropy, as Lemma 22 below demonstrates. The second approach uses the matrix covering bound developed by Bartlett and coauthors [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF] which employs a coupling assumption allowing one to get rid of a linear factor C. This approach, however, is dedicated to linear function classes. We start with the first one.

L ∞ -norm Metric Entropy

Bartlett et al. [START_REF] Bartlett | Covering numbers for real-valued function classes[END_REF] upper bounded the fat-shattering dimension in terms of the L 1 -norm metric entropy. Theorem 28 in Appendix A provides an optimized version of this bound under the assumption that the fat-shattering dimension at scale 2 is strictly greater than 4. Talagrand's result [START_REF] Talagrand | Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions[END_REF], Proposition 1 in Section 5.2.2, concerns the L 2 -norm metric entropy. Rudelson and

Vershynin [START_REF] Rudelson | Combinatorics of random processes and sections of convex bodies[END_REF], on the other hand, established a deeper connection, namely, the equivalence of the fat-shattering dimension and the L 2 -norm metric entropy under minimal regularity assumptions. If these results follow from non-trivial arguments, below we demonstrate that there is a rather straightforward connection between the fat-shattering dimension and the L ∞ -norm metric entropy.

Lemma 22 Let F be a class of functions from T to [-M F , M F ] with M F ∈ R + and let d( ) = -dim (F). Then, for all ∈ (0, M F ], d( ) log 2 N ∞ ( , F, d) .
Proof Let T d ⊂ T be the set of maximal cardinality d -shattered by F. Then, there is a subset

F ⊆ F of cardinality 2 d such that ∀f, f ∈ F , ∃t ∈ T d , f (t) -f (t) 2 .
This implies that max t∈T d |f (t) -f (t)| 2 . Consequently,

2 d M (2 , F, d ∞,t d ) M ∞ (2 , F, d) ,
and the claimed bound follows from

M ∞ (2 , F, d) N ∞ ( , F, d) .
Combining this result, the decomposition of the L ∞ -norm metric entropy and the L ∞ -norm combinatorial bound, Lemma 18 in Chapter 4, give us the following bound.

Theorem 22 Let G and F G be as in Definitions 3 and 8, respectively. For all ∈ (0, M G ], let

d( ) = -dim (F G ) and let d G * ( ) = max 1 k C -dim(G k ). Then, for all ∈ (0, M G ], d( ) 32Cd G * 4 ln 2 320CM 2 G 2 d G * 4 . (5.4)
Proof Let d = d( ). Based on Lemmas 22 and 17, we have

d C k=1 log 2 N ∞ ( , G k , d) . (5.5)
Next, we bound the right-hand side of Inequality (5.5) using Lemma 18:

d Cd G * 4 log 2 4M G ed d G * 4 log 2 20M 2 G d 2 Cd G * 4 log 2 2 20M 2 G d 2 ,
where the last inequality is due to the fact that d G * 4 1. Applying Lemma 41 in Appendix G to the right-hand side of the last inequality yields

d d 2 + 16Cd G * 4 ln 2 320CM 2 G 2 d G * 4
and the result follows.

Notice that compared to Inequality (5.3), the dependency on C in Theorem 22 remains unaffected under Assumption 1. On the other hand, the maximum component fat-shattering dimension appears inside a squared logarithmic term, similarly to Theorem 21.

Application to Linear Classes

The following lemma demonstrates that for linear function classes, using Lemma 19 in Inequality (5.5), instead of instantiating the fat-shattering dimension in the general formula (5.4), allows one to obtain a bound with a O (C ln C) dependence. It is an improvement over Theorem 5.4 by a factor ln C. Lemma 23 Let κ : X × X → R be a reproducing kernel and let (H κ , • Hκ ) be the corresponding

RKHS. Let Λ X , Λ ∈ R + . Suppose that sup x∈X κ x Λ X . Let B Λ = h ∈ H κ : h Hκ Λ , and let G = B C Λ . Let F G,γ be the class built from G as in Definition 8. Denote d( ) = -dim (F G,γ ). Then, for any ∈ (0, γ], d( ) 104CΛ 2 Λ 2 X 2 log 2 38CΛ 2 Λ 2 X 2 .
(5.6)

Proof Let d = d( ). Applying Lemma 19 in Chapter 4 to (5.5) we get:

d 26CΛ 2 Λ 2 X 2 log 2 2d 4Λ X Λ + 2 + 1 26CΛ 2 Λ 2 X 2 log 2 d + log 2 3 4Λ X Λ + 2 .
Next, we apply Lemma 40 in Appendix G to the first term on the right-hand side. To this end,

we set α = 2 52CΛ 2 Λ 2 X . Then 26CΛ 2 Λ 2 X log 2 d 2 d 2 + 26CΛ 2 Λ 2 X 2 log 2 52CΛ 2 Λ 2 X 2 ln 2 2 ,
and thus,

d d 2 + 26CΛ 2 Λ 2 X 2 log 2 38CΛ 2 Λ 2 X 2 + log 2 3 4Λ X Λ + 2 .
Solving for d and simplifying the bound yield the claimed result.

Since no coupling between the component functions is employed, Lemma 23 is inferioir to the one obtained based on Maurer's decomposition in Section 5.1. In the following, we consider yet another approach that allows one to exploit the interactions between the component functions and admits a O (ln C) dependence.

Matrix Covering Bound for Linear Classes

The matrix covering bound of Bartlett et al., Lemma 3.2 in [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF], is based on Theorem 3 of Zhang [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF] dealing with the L 2 -norm metric entropy of linear classifers. Dealing with matrices instead of vectors allows one to take benefit from the coupling assumption between the component functions. As a consequence, applying this approach to the class G from Definition 3 leads to the metric entropy bound with a O(ln C) dependence: an improvement over Lemma 17 of Zhang [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF] with a linear dependency on C. This implies the same dependency for the metric entropy of F G , since it can be controlled by that of G as demonstrated below.

Lemma 24 Let G be as in Definition 3 and let F G be as in Definition 4. For any g, g ∈ G, we define

∀x n = (x i ) 1 i n ∈ X n , d p,p,xn (g, g ) = 1 n n i=1 C k=1 g k (x i ) -g k (x i ) p 1 p .
Then, for all p 1,

N ( , F G , d p,zn ) N ( , G, d p,p,xn ) . (5.7)
Proof According to Lemma 13,

f g (z) -f g (z) p C k=1 g k (x) -g k (x) p .
This implies

1 n n i=1 f g (z i ) -f g (z i ) p 1 p 1 n n i=1 C k=1 g k (x i ) -g k (x i ) p 1 p
.

This means that an -cover of G with respect to the d p,p,xn metric is also an -cover for F G with respect to the d p,zn metric.

For a matrix G ∈ R n×d , we define the matrix norm G p,q as

G p,q = n i=1 G i. p q 1 p =    n i=1   d j=1 |G ij | q   p q    1 p
, where G i. denotes the i-th row of G. The following is the matrix covering bound that we use in the decomposition of the fat-shattering dimension. It corresponds to a special case of Lemma 3.2 in [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF] with the • 1,2 -norm on the weight matrix.

Theorem 23 Let X = [x 1 , . . . , x n ] T ∈ R n×d with X 2,2 = n i=1 x i 2 2 Λ X . Let G = g(x) = W x : W = [w 1 , . . . , w C ] T ∈ R d×C , W 1,2 = C k=1 w k 2 Λ and G = XW = [g(x i ), . . . , g(x n )] T ∈ R n×C : g ∈ G .
Let F G be a class built from G as in Definition 4. Then, for all ∈ (0, 2ΛΛ X ],

log 2 N ( , F G , d 2,zn ) Λ 2 Λ 2 X 2 log 2 (Cd + 1) . (5.8)
We need the following result in the proof of Theorem 23.

Lemma 25 Let (x i ) 1 i n ∈ X n . Let the class G be as in Definition 3. Let G = G ∈ R n×C : G ik = g k (x i ), g ∈ G .
Then, for all p 1,

N ( , G, d p,p,xn ) = N n 1 p , G, • p,p . Proof For any G, G ∈ G, G -G p,p = n i=1 C k=1 G ik -G ik p 1 p = n i=1 C k=1 g k (x i ) -g k (x i ) p 1 p . Then, G -G p,p = n i=1 C k=1 g k (x i ) -g k (x i ) p 1 p n 1 p
is equivalent to

1 n n i=1 C k=1 |g k (x i ) -g k (x i )| p 1 p
.

Proof [proof of Theorem 23] We denote by A j. and A .j the j-th row and the j-th column, respectively, of the matrix A. Let X and W be derived from X and W , respectively, based on the following normalization:

X .j = √ nΛΛ X X .j 2 X .j and W j. = X .j 2 √ nΛΛ X W j. .
Then, XW = X W . Now, we represent W as a column vector

w = [W T .1 , . . . , W T .C ] T ∈ R dC .
Then,

dC j=1 | wj | = 1 √ nΛΛ X C k=1 d j=1 X .j 2 |W jk |.
By Cauchy-Schwarz inequality it holds that

dC j=1 | wj | 1 √ nΛΛ X C k=1   d j=1 X .j 2 2     d j=1 |W jk | 2   √ nΛΛ X √ nΛΛ X 1. Let X =         X 0 . . . 0 0 X . . . 0 . . . . . . . . . . . . 0 0 . . . X         ∈ R nC×dC . We let K = Λ 2 Λ 2 X 2
. Then, by Maurey's lemma, Lemma 33 in Appendix G, for any

X w = dC j=1 |w j | X.j • sign(w j ) , one can find integers (k j ) 1 j dC such that dC j=1 |k j | K and X w - 1 K dC j=1 k j X.j 2 2 max 1 j dC X.j 2 2 dC j=1 | wj | K max 1 j d nΛ 2 Λ 2 X / X .j 2 2 • X .j 2 2 • 1 K nΛ 2 Λ 2 X K n 2 .
(5.9)

Note that

X w 2 = XW 2,2 .
Thus, an -covering number of the set A = { X w : w ∈ R dC } with respect to the • 2 norm is an -covering number of G with respect to the • 2,2 norm. From Inequality (5.9) it follows that the √ n-covering number of A is no greater than the number of integer solutions of dC j=1 |k j | K. According to Lemma 42 in Appendix G, this number is at most (Cd + 1) K . Then, we have

log 2 N √ n , G, • 2,2 Λ 2 Λ 2 X 2 log 2 (Cd + 1) .
Applying Lemma 25 and Lemma 24 in sequence to the left-hand side concludes the proof. Now, the dimensionality d in Inequality (5.8) can be replaced by the size n based on Corollary 3 in [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF]. This is useful when n d. The idea is to consider the subspace S spanned by {x i : 1 i n} whose dimensionality is at most n. Then, we can express each w k in Theorem 23 as a sum of projected and orthogonal to S components:

∀k ∈ [ [ 1, C ] ] , w k = w k + w ⊥ k ,
with w k ∈ S and w ⊥ k ∈ S ⊥ , and S ⊥ being the orthogonal complement of S. Clearly,

∀i ∈ [ [ 1, n ] ] , ∀k ∈ [ [ 1, C ] ] , w k , x i = w k , x i and C k=1 w k 2 C k=1 w k 2 Λ.

Multi-category Lipschitz Classifiers

We can collect all w k into a matrix W = X T B with B ∈ R n×C . Then, XW = XX T B.

Applying the reasoning in the proof above to X replaced now by XX T and W replaced by B gives:

log 2 N ( , F G , d 2,zn ) Λ 2 Λ 2 X 2
log 2 (Cn + 1) .

(5.10)

We will use the following result that estimates the fat-shattering dimension in terms of the L 2norm metric entropy. This result provides an explicit value for the constant in Proposition 1.4

of Talagrand [START_REF] Talagrand | Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions[END_REF].

Proposition 1 (After Proposition 5 in [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]) Let F be a class of functions from

T to [-M F , M F ] with M F ∈ R + . For any ∈ (0, M F ], let d = -dim (F). Then, d 16 log 2 N 2 2 , F, d .
Combining it with Inequality (5.10) gives:

Corollary 4 Let F G be the class given in Theorem 23. Let F G,γ be deduced from F G according to Definition 8. Let d ( ) = -dim (F G,γ ). For all ∈ (0, γ], d ( ) 32 4Λ 2 Λ 2 X 2 log 2 3C 4Λ 2 Λ 2 X 2 .
Proof By the left hand-side of Inequality (4.5), Inequality (5.10), and Proposition 1,

d ( ) 16 4Λ 2 Λ 2 X 2 log 2 (Cd( ) + 1) . Let K = 16 4Λ 2 Λ 2 X 2
and apply Lemma 40 in Appendix G to the right-hand side:

d ( ) K (log 2 (2C) + log 2 d( )) K log 2 2CK ln 2 + d( ) 2 .
Thus, d ( ) 2K log 2 2CK ln 2 and the result follows.

In the following section, we decompose the fat-shattering dimension of yet another family of classifiers: Lipschitz classifiers.

Multi-category Lipschitz Classifiers

This section considers Lipschitz classifiers, an example of which is the nearest neighbor [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF]. We also assume that the description space is a doubling space. A metric space (T , ρ) is said to be a doubling space if there exists a constant λ < ∞ such that every ball of radius r in T can be covered by at most λ balls of half the radius r/2. Then the smallest such value λ is said to be the doubling constant of T , and the doubling dimension D of T is D = log 2 λ. An example of a doubling space is a d-dimensional Euclidean space whose doubling dimension is roughly d [START_REF] Gupta | Bounded geometries, fractals, and low-distortion embeddings[END_REF].

It is a well-known fact that the fat-shattering dimension of a class of Lipschitz functions can be controlled via the packing number of their domain (see, for instance, Theorem 13 in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]). If the domain is a doubling space, then according to the following result, the doubling dimension has a direct impact on the fat-shattering dimension.

Lemma 26 (Lemma 1 in [START_REF] Gottlieb | Efficient classification for metric data[END_REF]) Let (T , ρ) be a metric space with doubling dimension D. Suppose S ⊂ T is finite and inf The upper bound on the fat-shattering dimension of Lipschitz classifiers is provided by Theorem 3 of Gottlieb et al. [START_REF] Gottlieb | Efficient classification for metric data[END_REF]. Our generalization of this result to the multi-category setting is straightforward. Indeed, it is obtained by using the Lipschitz property of component functions and an idea inspired from the proof of Lemma 4.2 of Bartlett and Shawe-Taylor [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF].

Lemma 27 Let (X , ρ) be a metric space with doubling dimension D. Suppose that sup (5.12)

For any such partition there exists g ∈ G satisfying

     ∀i ∈ I , 1 2 (g k (x i ) -max q =k g q (x i )) -u(x i , k) γ, ∀j ∈ I , 1 2
(-g k (x j ) + max q =k g q (x j )) + u(x j , k) γ.

Then, adding up both lines yields

∀(i, j) ∈ I × I , 1 2 (g k (x i ) -g k (x j )) + 1 2 (g l (x j ) -g l (x i )) -(u(x i , k) -u(x j , k)) 2γ,
where l = max q =k g q (x j ). By the assumption (5.12), it follows that

1 2 (g k (x i ) -g k (x j )) + 1 2 (g l (x j ) -g l (x i )) 2γ.
By the Lipschitz property on the other hand,

Lρ (x i , x j ) 2γ.
By considering all partitions satisfying the assumption (5.12), one can establish that any two elements in S k are 2γ L -separated. Therefore,

|I k | = M 2γ L , S k , ρ M 2γ L , S, ρ .
Now, the above relation holds trivially when S k is empty or contains one element. Then, repeating

this procedure for all k ∈ [ [ 1, C ] ], it follows that n = C k=1 |I k | CM 2γ L , S, ρ .
Applying Lemma 26 to the packing number yields the required result.

Application of the Decomposition Results

In this section, we focus on the application of the decomposition results, Theorem

New Combinatorial Bound

When it comes to the margin class, one can derive a sharper bound than that of Mendelson and Vershynin, Lemma 8 in Chapter 2, taking benefit from the following result involving the margin graph dimension, and the fact that the this dimension is dominated by the fat-shattering dimension, Inequality (1.7) in Chapter 1.

Lemma 28 (After Lemma 7 in [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF]) The particularity of this result lies in the fact that it is dimension-free and that there is no dependency on C in the scale of the fat-shattering dimension. In this sense, Corollary 6 represents the best of the two kinds of combinatorial bounds: the L 2 -norm bound, Lemma 8, and the L ∞norm bound, Lemma 18. On the downside, the fat-shattering dimension now appears also inside the logarithm, and we are dealing with O ln 3 1 as → 0.

For ∈ (0, M G ], let d G ( ) = -G-dim (F G ). Then, ln N 2 ( , F G,γ , n) 20d G 48 ln 6γ . ( 5
In the following sections, we focus on several applications of this combinatorial bound, as well as Corollary 5. Fix δ ∈ (0, 1) and let the right-hand side of the last inequality be at most δ. Solving for m yields the claimed bound.

This result can be compared to the one obtained via the decomposition of the L ∞ -norm metric entropy, and the use of the L ∞ -norm combinatorial bound, Lemma 18. Recall that the motivation to instantiate the decomposition in this norm is that the scales of the component covering numbers do not depend on C.

Theorem 25 Fix , δ ∈ (0, 1) and fix γ ∈ (0, 1].

For ∈ (0, M G ], let d ( ) = max 1 k C -dim(G k ).
Then, for sample size

m 32 2 9Cd γ 32 ln 2 942CM 2 G 2 γ 2 d γ 32 + ln 2 δ ,
the probability (2.1) is at most δ.

Proof The right hand-side of Lemma 18 can be upper bounded as follows:

ln N ( , G k , d ∞,xm ) 1.5d 4 ln 2 20M 2 G m 2 .
Then by decomposition of covering numbers, Lemma 17, and the norm ordering of covering numbers, the right hand-side of (2.2) can be upper bounded as

ln N 1 γ 8 , F G , 2m 1.5Cd γ 32 ln 2 2560M 2 G m 2 γ 2 .
Based on the fact that a 2 + b 2 2ab for any a and b, we have Finally, letting the right-hand side to be at most δ and solving for m conclude the proof.

ln N 1 γ 8 , F G ,
Although Theorem 25 is obtained using the sample-size dependent combinatorial bound, compared to Theorem 24, it provides a more efficient result in terms of the constants, the scale of the component fat-shattering dimension and the dependency on .

Chaining Bound

This section deals with the application of the combinatorial bounds, Corollary 6, and Corollary 5 combined with Lemma 27 (the decomposition result for the fat-shattering dimension of Lipschitz classifiers) in the chaining formula. We start with the first bound concerning general function classes.

General Function Classes

For general classes of functions (excluding Donsker classes for which the sample-size dependence is worse than that of Theorem 13), using Corollary 6 in the chaining gives the following bound on the Rademacher complexity. This bounds admits sharper than a radical dependency on C by slightly deteriorating that on m, which is comparable to Theorem 13 in Chapter 4.

Theorem 26 Let G be a class of functions as in Definition 3. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 8. Then, under Assumption 1, there is a constant K that depends only on d G and K G such that,

R m (F G,γ ) K C m              ln 3 2 m C ln m γ 2 C 1 2 , if d G = 2, γ 1-d G 2 m 1 2 -1 d G (ln(2C)) d G -2 ln 3 2   m 1 d G γ ln 2 (2C)   , if d G > 2 and m C 1.2 .
Proof To derive the bound we follow similar computations as in the proof of Theorem 18.

Apply Assumption 1 in Corollary 6 and take into account the obtained bound in the chaining formula (4.32):

Rm (F G,γ ) h(N ) + 2 640 • 192 d G CK G m × N j=1 h(j) + h(j -1) (h(j)) d G /2 ln 2 14 • 192 d G K G M 2 G C (h(j)) 2+d G ln 6γ h(j) .
For all j ∈ N, we set h(j) = γ2 -α(d G )j with α(d G ) > 0 for all d G ∈ R + . Then,

Rm (F G,γ ) γ2 -α(d G )N + 2 640 • 192 d G CK G m γ 1-d G 2 1 + 2 α(d G ) × N j=1 2 α(d G ) d G -2 2 j ln 2 14 • 192 d G K G M 2 G C (γ2 -α(d G )j ) 2+d G ln 6 • 2 α(d G )j . Now, if d G = 2, set α(d G ) = 1,

and thus

Rm (F G,γ ) γ2 -N + 6 640 • 192 2 CK G m N j=1 ln 2 14 • 192 2 2 4j K G M 2 G C γ 4 ln (6 • 2 j ).
Setting N = log 2 m C and bounding the series, we obtain

Rm (F G,γ ) γ C m + 6 640 • 192 2 CK G m log 2 m C ln 12 m C ln 2 18 • 192 2 K G M 2 G m 2 γ 4 C . For d G > 2, we set α(d G ) = 2 d G -2 and N =     d G -2 2d G log 2   m log 2d G 2 (2C) 1 d G       . Consequently, Rm (F G,γ ) γ log 2 2 (2C) 1 d G m 1 d G + 4 640 • 192 d G CK G m γ 1-d G 2 (1 + 2 2 d G -2 ) m d G -2 2d G log d G -2 2 (2C) 1 d G × ln 1 2   6 • 2 2 d G -2 d 2 G m 1 d G log 2 2 (2C)   ln    2 14 • 192 d G 2 2(2+d G ) d G -2 K G M 2 G γ 2+d G • m 1+ 2 d G log 2d G +4 2 (2C) 1 d G    .

Lipschitz Classifiers

We apply the combination of the decomposition result for Lipschitz classifiers, Lemma 27, and the combinatorial bound, Corollary 5, in the chaining bound. This result corresponds to a multi-category extension of Lemma 7 of Gottlieb and co-authors [START_REF] Gottlieb | Efficient classification for metric data[END_REF]. In particular, we obtain a matching dependency on the sample size up to a logarithmic factor, and a radical dependency on the number of categories. On the downside, this result is useful only when the sample size is much greater than the doubling dimension of the description space.

Theorem 27 Let (X , ρ) be a metric space with doubling dimension D and suppose that Applying this bound in the chaining formula (4.4) yields:

Rm (F G,γ ) h(N ) + 2 √ 20C √ m (48LΛ X ) D N j=1 h(j) + h(j -1) h(j) D 2 ln 1 2 6γ h(j) .
Let h(j) = γ2 -j and N = log 2 (m 1 D ) . Then, by a straightforwad computation it follows that

Rm (F G,γ ) γ m 1 D + 6 √ 20C γ D 2 -1 m 1 D (48LΛ X ) D log 2 (m 1
D
) ln Finally, we dedicated the chaining bound to Lipschitz classifiers and applied the corresponding decomposition of the-shattering dimension to generalize Lemma 7 of Gottlieb and coauthors [START_REF] Gottlieb | Efficient classification for metric data[END_REF] to the multi-category setting. This generalization yielded a radical dependency on C, and the matching with Lemma 7 dependency (up to a logarithmic factor) on m.

Chapter 6

Conclusions and Future Work

This thesis deals with the generalization performance of margin multi-category classifiers. We studied the uniform deviation of the empirical margin risk from the risk in terms of the basic parameters: the number C of classes, the sample size m and the margin parameter γ. The margin risk of a classifier is defined based on the margin loss function. Both in the bi-category and multi-category settings, the generalization performance is well studied for the indicator margin loss function. However, there still remain open questions when the margin loss function used is Lipschitz continuous.

One of the open questions is to control the uniform deviation between the margin risk and the empirical one by a covering number. Chapter 2 addressed this problem: under the assumption that the fat-shattering dimension of the margin class is finite, we upper bounded the deviation probability in terms of a L 1 -norm covering number. This result was then translated into a sample complexity estimate. For fixed , δ ∈ (0, 1), the sample complexity is the minimal sample size sufficient for the empirical risk to be close to the risk with probability at least 1 -δ. We derived several estimates appealing to different combinatorial bounds, the results that relate the covering number to a combinatorial dimension, which included a bound that depends on the sample-size and those that do not, i.e., the dimension-free bounds. This line of work corresponds to a multi-category extension of that of Bartlett and Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF]. The combinatorial bound they appealed to was their extension of the L ∞ -norm bound of Alon and coauthors [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] to the L 1 -norm.

We used the L 1 and L 2 -norm combinatorial bounds [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF][START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. Apart from , δ, the sample complexity is also characterized by a combinatorial dimension of the function class, in this thesis, as in [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF], the fat-shattering dimension. The sample complexity estimates that we obtained based on the L 1 -norm combinatorial bounds match with that of Bartlett and Long [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF] in terms of the dependency on and δ. On the other hand, we showed that the dimension-free L 2 -norm bound improves the dependency on , at the cost of degrading the scale of the fat-shattering dimension.

A particularity of our extension is that, due to the use of a margin loss function, our sample complexity estimates also involve the margin parameter γ. In these results, this parameter appears in the scale of the fat-shattering dimension, implying that the sample complexity increases more rapidly as γ → 0.

To make explicit the dependency of the sample complexity on the number of categories, we considered a particular kind of result, a decomposition result, that allows one to estimate In Chapter 3, we gave a literature review of the decomposition results for the Rademacher complexity and we discussed the way they impact the dependency on C. For independent component classes, the decompositions [START_REF] Kuznetsov | Multi-class deep boosting[END_REF][START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF] scale at best linearly with the number of categories.

Chapter 4 related the Rademacher complexity to the metric entropy via the chaining method, and performed the decomposition at this level. Guermeur [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] showed that postponing the decomposition to the level of the metric entropy opens up a possibility to improve the dependency on C to a sublinear one. This work was based on the use of the L 2 -norm metric entropy. We improved upon this result in two ways. First, since the decomposition result for the covering numbers is optimized with respect to C in the L ∞ -norm, one can obtain a chaining bound with a radical dependency on C using the combinatorial bound of Alon et al. [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF], and this is irrespective of the growth rate of the fat-shattering dimensions. The dependency on the sample size, however, is worsened. Second, by generalizing the combinatorial bound of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] to L p -norms for p between 2 and ∞, we could improve the dependency on C upon that in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF].

Although inferior to that in the L ∞ -norm, the use of combinatorial bound did not degrade the convergence rate in m (nor in the margin parameter γ). Our main results lead to the conclusion that there is a trade-off when optimizing the dependencies on the parameters of interest, particularly C and m: improving the dependency on C deteriorates the one on m. The basic question is how much milder these dependencies could be made.

We saw that for specific families of classifiers, exploiting a coupling assumption leads to an improved dependency of the metric entropy, and the Rademacher complexity on the number of categories. It is based on the fact that this kind of assumption allows one to eliminate the linear factor C from the bounds, the consequence of treating the component functions independently.

Whether one can take benefit from a coupling assumption for general function classes, rather than just for linear ones, is an essential open question.

Improving the dependency of the Rademacher complexity on the basic parameters, C, m and γ, could also be addressed at the level of the construction of the chaining. Since the choice of the function h, which gives the radius of balls of a minimal cover of a set, involves these parameters, optimizing it could lead to a tighter chaining bound. This concerns especially the optimization of the chaining bound with respect to γ which was not in the focus of this work. One possible approach would be based on the fact that γ constitutes the diameter of the truncated margin class for which the chaining bound is actually derived, and it is upper bounded by 1. Then, using the maximum value of γ when setting the function h would improve the growth rate of the chaining bound with respect to this parameter.

Regarding the dependency on the sample size, an important source for improvement lies in the combinatorial bound of Alon and coauthors [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]. As mentioned above, this bound concerns the covering numbers in the L ∞ -norm, for which the decomposition formula takes the optimal form with respect to the dependency on C, and this is precisely the reason why we obtained a tighter than radical dependency on C in Chapter 5. But because the mentioned bound grows as O(ln 2 (m)), the dependency on m is worsened. In fact, it has been questioned in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] whether the exponent 2 could be reduced to 1. This question has been addressed by Rudelson and Vershynin [START_REF] Rudelson | Combinatorics of random processes and sections of convex bodies[END_REF] by reducing the exponent 2 to any number larger than 1, at the cost of deteriorating the scale of the fat-shattering dimension. It appears, then, that to answer affirmatively the question posed by Alon and coauthors, without incurring any trade-off, is indeed a non-trivial endeavour.

As a matter of fact, if it were possible, then it would allow one to improve the dependency on the number of categories without degrading that on the sample size.

In the context of extreme classification, one interesting question is whether it is possible to exploit the unbalanced class distribution phenomenon (when some classes are overrepresented in data) [START_REF] Babbar | Machine Learning Strategies for Large-scale Taxonomies[END_REF] to derive dedicated generalization bounds with a better dependency on C. One possible approach, for instance, would be to handle the capacities of the component classes in a non-uniform way based on coupling constraints inspired from the approach of Maurer, and Lei and coauthors. The knowledge of the distribution of the classes would particularly help in constraining the component classes, thus leading to tighter bounds.

Appendix A

Capacity Measures

The present Appendix gathers some results related to the Rademacher/Gaussian complexity, metric entropy and the fat-shattering dimension.

Proof of Lemma 4 Let t n = (t i ) 1 i n ∈ T n . We have

Rn (ψ • F) = E σn sup f ∈F 1 n n i=1 σ i ψ(f (t i )) = E σ n-1 E σn sup f ∈F 1 n n i=1 σ i ψ(f (t i )) σ n-1 ,
where σ n-1 = (σ i ) 1 i n-1 . Then,

Rn (ψ • F) = 1 2 E σ n-1 sup f ∈F n-1 i=1 σ i ψ(f (t i )) + ψ(f (t n )) + 1 2 E σ n-1 sup f ∈F n-1 i=1 σ i ψ(f (t i )) -ψ(f (t n )) = 1 2 E σ n-1 sup f,f ∈F n-1 i=1 σ i ψ(f (t i )) + σ i ψ(f (t i )) + ψ(f (t n )) -ψ(f (t n )) .
Next, we make use of L-Lipschitz property of ψ:

Rn (ψ • F) 1 2 E σ n-1 sup f,f ∈F n-1 i=1 σ i ψ(f (t i )) + σ i ψ(f (t i )) + L f (t n ) -f (t n ) = 1 2 E σ n-1 sup f,f ∈F n-1 i=1 σ i ψ(f (t i )) + σ i ψ(f (t i )) + L f (t n ) -f (t n ) = 1 2 E σ n-1 sup f ∈F n-1 i=1 σ i ψ(f (t i )) + Lf (t n ) + 1 2 E σ n-1 sup f ∈F n-1 i=1 σ i ψ(f (t i )) -Lf (t n ) ,
where the first equality is due to the fact that the supremum is taken with respect to f, f from the same set and the last one is based on

sup f,f ∈F f (t) + f (t) = sup f ∈F f (t) + sup f ∈F f (t). (A.1)
Then,

Rn (ψ • F) E σn sup f ∈F n-1 i=1 (σ i ψ(f (t i ))) + σ n Lf (t n ) .
Repeating it for the remaining terms involving σ 1 , ..., σ n-1 yields the required result.

Proof of Lemma 5

The proof is based on the following reasoning. By the assumption we have that

∀f 1 , . . . , f N ∈ F, ∀t ∈ T , N j=1 α j f j (t) N j=1 α j f l (t) f l (t),
where l = argmax j f j (t). Consequently, sup α 1 ,...,α j N j=1 α j f j (t) = f l (t) is achieved for the configuration where α l = 1 and α j = 0 for all j = l. Then,

E σn sup f ∈conv(F ) 1 n n i=1 σ i f (t i ) = E σn   sup f 1 ,...,f N ∈F α 1 ,...,α N 1 n n i=1 σ i N j=1 α j f j (t i )   = E σn   sup f 1 ,...,f N ∈F α 1 ,...,α N N j=1 α j 1 n n i=1 σ i f j (t i )   = E σn   sup α 1 ,...,α N N j=1 α j sup f j ∈F 1 n n i=1 σ i f j (t i )   = E σn sup f ∈F 1 n n i=1 σ i f (t i ) ,
where the third equality holds thanks to the positivity of all α j .

Proof of Lemma 6 Based on the fact that a standard Gaussian random variable is symmetric and using Jensen's inequality, it holds that

E on sup f ∈F 1 n n i=1 o i f (t i ) = E σn E on sup f ∈F 1 n n i=1 σ i |o i |f (t i ) E σn sup f ∈F 1 n n i=1 σ i E|o i |f (t i ) = 2 π E σn sup f ∈F 1 n n i=1 σ i f (t i ) .
Proof of Theorem 11 It holds that

Rm (F G,γ ) = E σm sup g∈G 1 m m i=1 σ i f g,γ (z i ) = E σm sup g∈G 1 2m m i=1 σ i max 0, g y i (x)-max 1 k C g k (x i ) -2γ1 {k=y i } E σm sup g∈G 1 2m m i=1 σ i g y i (x)-max 1 k C g k (x i ) -2γ1 {k=y i } .
The last inequality is derived using the contraction principle, Lemma 4, since the max (0, •)

function is 1-Lipschitz. Next, based on the sub-additivity of the supremum and the symmetry of a Rademacher variable, we have

Rm (F G,γ ) E σm sup g∈G 1 2m m i=1 σ i g y i (x i ) + E σm sup g∈G 1 2m m i=1 σ i max 1 k C g k (x i )-2γ1 {k=y i } .
According to Lemma 6, we can upper bound both terms by the Gaussian complexity of the corresponding class:

Rm (F G,γ ) 1 2m π 2 E ôm sup g∈G m i=1 ôi g y i (x i ) + 1 2m π 2 E õm sup g∈G m i=1 õi max 1 k C g k (x i )-2γ1 {k=y i } ,
where ôm = (ô i ) 1 i m and õm = (o i ) 1 i m are orthogaussian sequences. Finally, applying a comparison result for Gaussian processes, Lemma 31, to both terms and based on the fact that a standard Gaussian random variable is centered (which eliminates the term 2γ1 {k=y i } for all i) conclude the proof.

Proof of Lemma 14 Clearly, the claim holds for n = 1. Let n = 2. Then, according to Lemma 30 it holds that

E σ 2 E σ 1 sup g∈G σ 1 f g (z 1 ) + σ 2 f g (z 2 ) σ 2 E σ 2 E σ C sup g∈G C k=1 √ 2σ k g k (x 1 ) + σ 2 f g (z 2 ) σ 2 = E σ C E σ 2 sup g∈G σ 2 f g (z 2 ) + C k=1 √ 2σ k g k (x 1 ) σ C √ 2E σ 2C sup g∈G 2 i=1 C k=1 σ C(i-1)+k g k (x i ),
where σ C = (σ k ) 1 k C . Assume now that n 3 and that the claim holds for n -1. Then,

E σn E σ n-1 sup g∈G n-1 i=1 σ i f g (z i ) + σ n f g (z n ) σ n E σ C(n-1) E σn sup g∈G σ n f g (z n ) + n-1 i=1 C k=1 √ 2σ C(i-1)+k g k (x i ) σ C(n-1) E σ C(n-1) E σC sup g∈G C k=1 √ 2σ k g k (x n ) + n-1 i=1 C k=1 √ 2σ C(i-1)+k g k (x i ) σ C(n-1) = √ 2E σ Cn sup g∈G n-1 i=1 C k=1 σ C(i-1)+k g k (x i ), where σC = (σ i ) 1 i C . Lemma 29 (After Lemma 2 in [47]) Let J ∈ N * . For any j ∈ [ [ 1, J ] ], let F j be a class of functions from T to [-M F , M F ] with M F ∈ R + . Let F be a class of functions from T to [-M F , M F ] defined as F = max 1 j J f j : (f j ) 1 j J ∈ J j=1 F j . Then, Rn (F) J j=1
Rn (F j ) .

Lemma 30 (After Lemma 7 in [START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF]) Let G be a class of functions satisfying Definition 3 and for any γ ∈ (0, 1], let F G,γ be a class of functions satisfying Definition 8. Let σ C = (σ i ) 1 i C be a Rademacher sequence and u : G → R. Then, for any fixed (x, y)

∈ X × [ [ 1, C ] ], E sup g∈G (σf g,γ (x, k) + u(g)) √ 2E σ C sup g∈G C k=1 σ k g k (x) + u(g) . (A.2)
Proof As the truncation of functions f g play no role to obtain the claimed bound (because of the Lipschitz continuity of f g,γ ), to keep the notation simple, we prove it for functions f g . By definition of a Rademacher variable and Lemma 13, it holds that

2E sup g∈G (σf g (x, k) + u(g)) sup g∈G (f g (x, k) + u(g)) + sup g∈G (-f g (x, k) + u(g)) sup g,g ∈G f g (x, k) -f g (x, k) + u(g) + u(g ) sup g,g ∈G g(x) -g (x) 2 + u(g) + u(g ) . (A.3)
Now, one can apply Khintchine's inequality, Lemma 12, to g(x) -g (x) 2 . For p = 1, the smallest value for the constant in this inequality is due to Szarek [START_REF] Szarek | On the best constants in the Khinchin inequality[END_REF]:

K 1 = √ 2.
Applying it in Inequality (A.3), then using Jensen's inequality, the fact that the supremum is with respect to two elements of the same set and the definition of a Rademacher variable, we derive According to a comparison theorem for Gaussian processes, Theorem 1 in [START_REF] Vitale | Some comparisons for Gaussian processes[END_REF], for the proof it suffices to demonstrate that for any g, g ∈ G,

E õn A g -A g 2 E o Cn B g -B g 2 . (A.4)
for some i ∈ [ [ 1, n ] ]. Thus, after m steps we have w (m) , w α mα.

(D.4)

The change in the squared norm after k steps; on the other hand, is

w (k) 2 H -w (k-1) 2 H = w (k-1) + y i h i 2 H -w (k-1) 2 H = w (k-1) 2 H + 2 w (k-1) , y i h i + h i 2 H -w (k-1) 2 H h i 2 H ,
where the inequality follows from w (k-1) , y i h i 0. Therefore, after m steps,

w (m) m k=1 h i k 2 H 1 2
.

Combining the above inequality with (D.4) using Cauchy-Schwarz inequality, we obtain mα w (m) , w α w (m)

H w α H w α H m k=1 h i k 2 H
(k + 1) k = k 0 k 0 + • • • + k k -1 k k-1 + k k k k = 1 + • • • + k • k k-1 + k k > 2k k .
Consequently, ψ k+1 (-2) < (k + 1) • (k + 1) k /2 = (k + 1) k+1 /2, where we used the convention that ∀k > n, n k = 0.

The results demonstrated hereafter are the generalizations of those in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. In the following, we denote K p = ∞ k=1 k p 2 k with p ∈ N * \ {1, 2}.

Lemma 37 (After Lemma 5 of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let X be a bounded random variable. Let M p (X) = (E|X| p ]) 1/p . Then, there exist numbers a ∈ R and β ∈ (0, 1/2], such that P X > a + M p (X) 4(2K p ) 1/p β 2 and P X < a -M p (X) 4(2K p ) 1/p 1 -β, or vice versa.

Proof The proof closely follows that of Lemma 5 of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] where the variance of X is replaced by its higher moments.

Divide R + into the intervals I k of length cM p (X) with Proof F can be viewed as a finite probability space (F, A, P F ) with a uniform probability measure P F (A) = |A|/|F| for any A ∈ A. Then, for any two random elements f, f ∈ F selected independently according to P F ,

E f,f ∼P F d p,tn f, f p = E f,f ∼P F 1 n n i=1 f (t i ) -f (t i ) p = 1 n n i=1 E f,f ∼P F f (t i ) -f (t i ) p .
By

E f ∼P F |f (t i )| p p 2 p+1 .
The rest of the proof is based on induction on the cardinality of F and is exactly as in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF],

except that the tree is now /4(4K p ) 1/p -separated. ] such that

∀(f + , f -) ∈ F+ , F-, f + (t i 0 ) > f -(t i 0 ) + 1.
It follows that ∃b ∈ B, ∀(f + , f -) ∈ F+ , F-,

     f + (t i 0 ) > b f -(t i 0 ) < b. (E.4)
If a pair is strongly shattered either by F+ or F-, then it is also strongly shattered by F. On the other hand, if a pair (S, v) is strongly shattered both by F+ and F-, then t i 0 ∈ S. Otherwise, there would exist (f + , f -) ∈ F+ , Fsatisfying f + (t i 0 ) v(t i 0 ) -1 and f -(t i 0 ) v(t i 0 ) + 1.

Combining it with (E.4) yields a contradiction:

b + 1 < v(t i 0 ) < b -1.
Now, consider a pair (S ∪ {t i 0 }, v ), where v (t i ) = v(t i ) for all t i ∈ S and v (t i 0 ) = b. This pair is shattered by F, but neither by F+ or F-. As S is shattered both by F+ and F-, then from (E.4) it follows that,

∀(s i ) 1 i n ∈ {-1, 1} n , ∃f + ∈ F+ ,      ∀i ∈ [ [ 1, n ] ] , s i (f + (t i ) -v(t i )) 1, f + (t i 0 ) b + 1, similarly, ∀(s i ) 1 i n ∈ {-1, 1} n , ∃f -∈ F-,      ∀i ∈ [ [ 1, n ] ] , s i (f -(t i ) -v(t i )) 1, f -(t i 0 ) b -1.
It proves the claim that F shatters the pair (S ∪ {t i 0 }, v ). Therefore, in both cases we get (E.3).

The next result is obtained by combining Propositions 5 and 6. where we used the convention that for all k > n, n k = 0.

Proof of Theorem 19 Let p q 2 and let f q (•) = 1 2

• 2 Hκ,q . Let q * denote the Hölder conjugate of q:

1 q + 1 q * = 1.

Then, the norm • Hκ,q * is the dual of • Hκ,q , and the function f q is β = 1 q * -strongly convex with respect to • Hκ,q . Now, in Inequality (3.7) in Chapter 3, instantiate G with B q,Λ . For all

f q (h) + m i=1 ∇f * (v 1:i-1 ) , λv i + λ 2 q * 2 m i=1 v i 2
Hκ,q * . Now, by the assumption, ∀h ∈ B q,Λ , f q (h) Λ 2 2 .

Then, based on this, as well as the fact that o Cm is an orthogaussian sequence and thus that Next, by Jensen's Inequality,

E õC C k=1 |õ k | q * 2 q * C k=1 E õC |õ k | q * 2 q * (CM q * ) 2 q * , (F.3)
where M q * = E |õ 1 | q * . Substituting the last result in (F.2) and using the fact that m i=1 k (x i , x i ) mΛ 2

X , give

m i=1 E o Cm v i 2 H,q * mΛ 2 X (CM q * ) 2 q * . (F.4)
Thus, from (F.1)-(F.4) we get:

Rm F B q,Λ ,γ ΛΛ X √ q * (CM q * ) 1 q * √ m π 2 . (F.5)
Now, the goal is to minimize the right-hand side of (F.5) with respect to q * . Note that while (M q * ) 1 q * is an increasing function of q * , √ q * C 1 q * attains its minimum at q * = 2 ln C. With this value of q * , we have Substituting these values in Inequality (F.5), we have that when p q 2 ln C 2 ln C -1 ,

Rm F B q,Λ ,γ 4 √ eπΛΛ X ln C √ m . (F.6)
On the other hand, when q * = 2 then according to Lemma 32,

(M 2 ) 1 2 (2 • 2) 2• 1 2 = 4
and thus for p = q = 2, Rm F B q,Λ ,γ 4 √ πΛΛ X C m .

To conclude the proof, note that based on the constraint p q 2, we have f p (h) f q (h) for all h ∈ H C and thus B p,Λ ⊆ B q,Λ . This implies Rm F B p,Λ ,γ Rm F B q,Λ ,γ .

Résumé

Cette thèse porte sur la théorie de la discrimination multi-classe à marge. Elle a pour cadre la théorie statistique de l'apprentissage de Vapnik et Chervonenkis. L'objectif est d'établir des bornes de généralisation possédant une dépendances explicite au nombre C de catégories, à la taille m de l'échantillon et au paramètre de marge γ, lorsque la fonction de perte considérée est une fonction de perte à marge possédant la propriété d'être lipschitzienne. La borne de généralisation repose sur la performance empirique du classifieur ainsi que sur sa "capacité". Dans cette thèse, les mesures de capacité considérées sont les suivantes : la complexité de Rademacher, les nombres de recouvrement et la dimension fat-shattering. Nos principales contributions sont obtenues sous l'hypothèse que les classes de fonctions composantes calculées par le classifieur ont des dimensions fat-shattering polynomiales et que les fonctions composantes sont indépendantes. Dans le contexte du schéma de calcul introduit par Mendelson, qui repose sur les relations entre les mesures de capacité évoquées plus haut, nous étudions l'impact que la décomposition au niveau de l'une de ces mesures de capacité a sur les dépendances (de la borne de généralisation) à C, m et γ. En particulier, nous démontrons que la dépendance à C peut être considérablement améliorée par rapport à l'état de l'art si la décomposition est reportée au niveau du nombre de recouvrement ou de la dimension fat-shattering. Ce changement peut affecter négativement le taux de convergence (dépendance à m), ce qui souligne le fait que l'optimisation par rapport aux trois paramètres fondamentaux se traduit par la recherche d'un compromis.

Mots-clés: apprentissage, théorie de l'apprentissage, discrimination multi-classe, risques garantis, classifieurs à marge

Abstract

This thesis deals with the theory of margin multi-category classification, and is based on the statistical learning theory founded by Vapnik and Chervonenkis. We are interested in deriving generalization bounds with explicit dependencies on the number C of categories, the sample size m and the margin parameter γ, when the loss function considered is a Lipschitz continuous margin loss function. Generalization bounds rely on the empirical performance of the classifier as well as its "capacity". In this work, the following scale-sensitive capacity measures are considered: the Rademacher complexity, the covering numbers and the fat-shattering dimension. Our main contributions are obtained under the assumption that the classes of component functions implemented by a classifier have polynomially growing fat-shattering dimensions and that the component functions are independent.

In the context of the pathway of Mendelson, which relates the Rademacher complexity to the covering numbers and the latter to the fat-shattering dimension, we study the impact that decomposing at the level of one of these capacity measures has on the dependencies on C, m and γ. In particular, we demonstrate that the dependency on C can be substantially improved over the state of the art if the decomposition is postponed to the level of the metric entropy or the fat-shattering dimension. On the other hand, this impacts negatively the rate of convergence (dependency on m), an indication of the fact that optimizing the dependencies on the three basic parameters amounts to looking for a trade-off.

Keywords: statistical learning theory, multi-category classification, risk bounds, margin classifiers

  recouvrement et v Résumé les dimensions combinatoires. Ces mesures sont très liées : il est possible de borner les unes à partir des autres. En particulier, la technique du chaînage et les bornes combinatoires rendent possibles les liens suivants : linéaire. Plus précisément, dans le cas général où les fonctions composantes sont indépendantes, leur résultat de décomposition donne le schéma : complexité de Rademacher (multi-classe) avec la complexité de Rademacher, il existe plusieurs options pour établir la dépendance à C, puisqu'à la vue du chemin complexité de Rademacher chaînage -----→ nombres de recouvrement borne combinatoire

  entropie métrique à l'échelle[START_REF] Babenko | On the entropy of a class of analytic functions[END_REF]

  decomposition ---------→ C k=1 k-th Rademacher complexity. (3) xii In fact, with the Rademacher complexity one has several options to elaborate the dependency on C, since, in view of the pathway Rademacher complexity chaining -----→ covering numbers combinatorial bound------------→ combinatorial dimension,

Definition 7 (

 7 Margin loss functions) For any γ ∈ (0, 1], define the margin indicator loss function φγ : R → {0, 1} as φγ (t) = 1 {t γ} , and the truncated hinge loss function φ γ : R → [0, 1] as

. 10 )

 10 Now, for any strictly positive u, a and b, with u 2 and b a,

8 ( 1 )Theorem 7 ( 2 . 1 )

 81721 = 3 log 2896 . Performing straightforward computations in the right-hand side of Inequality (2.12) and proceeding as in the proof of Lemma 5 yields the claimed bound. Now, we can as well make use of Lemma 8, based on the norm ordering of covering numbers, Inequality (1.5). It produces the following result. Fix , δ ∈ (0, 1) and fix γ ∈ (0, 1]. For ∈ (0, γ], let d ( ) = -dim (F G,γ ). is at most δ.

both combinatorial bounds led to a ln 1 ln 1 3 ln 1 3 ln 1 . 3

 113 dependency and this matches with that ofBartlett and Long. We demonstrated that making use of the dimension-free L 2 -norm combinatorial bound, one can improve the sample complexity estimate by as much as a factor ln 1 This, however, increases the fat-shattering dimension, thus deteriorating the bound. The main difference with the work of Bartlett and Long lies in the fact that the fatshattering dimensions in our sample complexity estimates involve the margin parameter γ. This is the consequence of the use of a margin loss function.In the next chapter, we consider the deviation of sup g∈G (L(g) -L γ,m (g)) from its expectation.Handling this question via a concentration inequality and the symmetrization technique leads to an error bound involving a Rademacher complexity. The next chapter takes the form of a literature review of error bounds where the dependency on the number of categories is elaborated via the decompositions of this capacity measure.ChapterBasic Generalization Bound with aRademacher ComplexityIn the preceding chapter, we controlled the uniform deviation between the risk and the empirical margin risk by a covering number. This chapter considers an upper bound on the deviation of interest by another capacity measure, the Rademacher complexity, and constitutes the starting point of scheme (4) given in Introduction:Rademacher complexity chaining -----→ metric entropy combinatorial bound ------------→ fat-shattering dimension.The focus of this and the following chapters is on the study of the dependencies of the Rademacher complexity on the basic parameters: the number C of categories, the sample size m and the margin parameter γ. The dependency on C is elaborated via a particular result, the decomposition result, that allows one to upper bound a capacity measure of the margin class in terms of that of component classes. In the present chapter, we give a review of the decomposition results in the literature for the Rademacher complexity. For the sample-size dependency, we discuss the Rademacher complexity bounds of several well-known classifiers.

  For the entire class, on the other hand, using a classical concentration inequality, i.e., McDiarmid's inequality (Inequality (B.9) in Appendix B), leads to a more efficient bound. In particular, for the empirical process of interest in this thesis, {L(g) -L γ,m (g) : g ∈ G} with fixed γ ∈ (0, 1], the application of Mc-Diarmid's inequality and the symmetrization for expectation technique gives the following basic generalization bound involving a Rademacher complexity: Theorem 10 (After Theorem 8.1 in [63]) Let G be as in Definition 3. For γ ∈ (0, 1], let F G,γ be the class of functions satisfying Definition 8. Fix δ ∈ (0, 1) and γ ∈ (0, 1]. Then, with

  Combining it with(3.6) in (3.5) yields the claimed bound. If the decomposition of Kuznetsov and coauthors is dedicated to truncated margin functions, the result recently introduced by Maurer [57] concerns a class of Lipschitz functions with vectorvalued domains. Apart from the Lipschitz property, his result makes use of the classical Khintchine's inequality: Lemma 12 (Khintchine's inequality, after Lemma 4.1 in [54]) Let p ∈ R + and let σ = (σ i ) i 1 be a Rademacher sequence. There exists a constant K p > 0 depending only on p, such that for any

O m -1 2 . 4 From

 24 chapter considered the basic generalization bound for margin multi-category classifiers involving a Rademachar complexity as capacity measure. It constitutes the starting point for the main body of work of the subsequent chapters where the focus is on optimizing the dependencies of the Rademacher complexity on C, m and γ. In this chapter, if the dependency on γ was made explicit through the well-known contraction lemma, the one on C was based on the use of a particular result, the decomposition result, that relates a capacity measure of the margin class to the ones of the component classes. The literature provides decomposition results for the Rademacher complexity that exhibit at best O(C) dependency when no coupling between the component functions is assumed, as it is the focus of this thesis. To make explicit the dependency on the sample size, after the decomposition, one could specify the classifier and bound the Rademacher complexity of the correspondig function class. For the classical classifiers, such as support vector machines and feedforward neural networks, the rate of convergence is optimal: In the next chapter, we relate the Rademacher complexity to the metric entropy and postpone the decomposition to the level of the latter quantity. We pose the same question: what are the forms of the dependencies on C, m and γ when one manipulates the metric entropy instead of the Rademacher complexity? Chapter Rademacher Complexity to Metric Entropy This chapter relates the Rademacher complexity to another capacity measure, the metric entropy (the logarithm of the covering number), and studies how the decomposition at the level of the metric entropy influences the dependencies on the basic parameters in the context of the following pathway: Rademacher complexity chaining -----→ metric entropy combinatorial bound ------------→ fat-shattering dimension.

  sult with p = ∞ and the metric entropy bounds in the L ∞ -norm, one can obtain a radical dependency on C. But it leads to a slightly worse convergence rate (which is especially true for Donsker classes) than the one in Theorem 12 which is based on the L 2 -norm. In this section, we consider the values of p between these two "extreme" ones: 2 and ∞. We extend the L 2 -norm combinatorial bound of Mendelson and Vershynin[START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] (Lemma 8 in Chapter 2) to L p -norms with p ∈ N * \ {1, 2}. Their bound does not depend on the sample size thanks to the use of the probabilistic extraction principle. We extend this bound in two ways: in one of them we keep the dependency on the sample size, and in the other, we remove it using the L p -norm generalization of the aforementioned principle. This allows us to optimize the dependency on C, while not degrading the ones on m and γ, by applying one or the other combinatorial bound in the chaining based on the value of d G .

(a) Let = 4 (

 4 4K p ) 1/p with K p = ∞ k=1 k p /2 k (this quantity arises in Lemma 37 in Appendix E), η = + 2 and N = 2M F /η . Define the class Fη of functions from T n to [ [ 0, N ] ]

Chapter 5

 5 Decomposition of the Fat-shattering DimensionThis chapter focuses on the decomposition of the last capacity measure appearing in scheme (4), the fat-shattering dimension:Rademacher complexity chaining -----→ metric entropy combinatorial bound ------------→ fat-shattering dimension.So far, we dealt with upper bounds on the metric entropy (via combinatorial bounds), and the Rademacher complexity (via the chaining method) in terms of the fat-shattering dimension.But the converse relationship also holds: the fat-shattering dimension can be controlled in terms of these capacity measures.An argument made byMendelson [59] leads to an upper bound on the fat-shattering dimension in terms of the Rademacher complexity. Thus, a tight upper bound on the Rademacher complexity implies one on the fat-shattering dimension. As discussed in Section 5.1, these results are dedicated to linear function classes.Decompositions of the fat-shattering dimension of a composite class in terms of that of component classes via the metric entropy are due toBartlett [7] and Duan[START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF]. Bartlett's result concerns a specific classifier: feedforward neural networks. For such a network with two layers, the decomposition can be viewed as that of the fat-shattering dimension of the convex hull of a bounded function class. On the other hand, Duan decomposed the fat-shattering dimension of a composite class built based on a unformly continuous function with a vector-valued domain.

Section 5 .

 5 4 derives a new combinatorial bound for the margin class using the decomposition of the fat-shattering dimension for general function classes. This result is in terms of the fatshattering dimensions of the component classes, and it can be compared to Corollary 1 of Chapter 4. The advantage of the new bound over Corollary 1 lies in the fact that it is dimension-free and that there is no dependency on C in the scales of the component fat-shattering dimensions. In Section 5.4.2, we use this result to derive the sample complexity estimate for the deviation probability (2.2) of Chapter 2 with an explicit dependency on C. We compare this result to the one obtained via the decomposition at the level of the L ∞ -norm metric entropy. Both yield a linear dependency on C up to a logarithmic factor. Section 5.4.3 applies the new combinatorial bound in the chaining formula (4.4) of Chapter 3, for which we obtain a better than radical dependency on C, the result comparable to Theorem 13 of Chapter 4. Lastly, we dedicate the chaining bound to Lipschitz classifiers considered in Section 5.3. Using the decomposition result of the fat-shattering dimension of these classifiers leads to a multi-class generalization of Lemma 7 of Gottlieb and coauthors [32].

5. 1 .

 1 Decomposition via the Rademacher Complexity bound on the Rademacher complexity implies one on the fat-shattering dimension. Lemma 20 Let F be a class of functions from T to [-M F , M F ] with M F ∈ R + . For ∈ (0, M F ], let d ( ) = -dim (F). For all ∈ (0, M F ], if sup tn∈T n Rn (F) for some n ∈ N * , then d ( ) n. Proof Let S = {t i : 1 i d} ∈ T be the set of maximal cardinality d -shattered by F. By definition of -shattering, for any

  s,s ∈S ρ(s, s ) = α > 0. Let diam(S) = sup s,s ∈S ρ(s, s ). Then the size of S is |S| 2diam(S) α D .

x, x 11 )

 x11 ∈Xρ(x, x ) Λ X . Let G be a class of functions given in Definition 3 and F G in Definition 4. We assume thatfor all k ∈ [ [ 1, C ] ], G k is a class of L-Lipschitz functions. Let d ( ) = -dim (F G ).Then, for all∈ (0, M G ],Proof Let S = {(x i , y i ) : 1 i n} be a set of n ordered pairs -shattered by F G and let u : X × Y → R be a witness to this shattering. Now, partition S into subsetsS k with k ∈ [ [ 1, C ] ]according to the value of y i in each pair. LetI k ⊆ [ [ 1, n ] ] be a set of indices of pairs in S k . First, assume that |S k | > 1.Then, consider a partitioning of I k into two subsets I and I so that I = ∅ and I = ∅ and ∀(i, j) ∈ I × I , u(x i , k) u(x j , k).

22 and Lemma 27 .

 27 The use of the former result leads to a new combinatorial bound for the class F G,γ in terms of the fat-shattering dimensions of the component classes G k . Then, we apply the new combinatorial bound in two contexts: in Section 5.4.2, we present a new sample complexity estimate for the deviation probability, Theorem 4, with an explicit dependency on C, and in Section 5.4.3, we apply the combinatorial bound in the chaining bound. Finally, we dedicate the chaining bound to Lipschitz classifiers considered in Section 5.3, where we make use of the corresponding decomposition result of the fat-shattering dimension, Lemma 27.

. 13 )Corollary 5 Corollary 6

 1356 Applying the right-hand side of Inequality (1.7) to the above bound gives:For ∈ (0, M G ], let d ( ) = -dim (F G ). Then, for any ∈ (0, γ], ln N 2 ( , F G,γ , n) 20d 48 ln 6γ . (5.14) Notice that, compared to Lemma 8 applied to F G,γ the scale of the fat-shattering dimension (of F G ) is increased which decreases the dimension tightening the bound. Applying the decomposition of the fat-shattering dimension, Theorem 22, to Inequality (5.14) yields the following result. For ∈ (0, M G ], let d( ) = max 1 k C -dim(G k ). Then, for any γ ∈ (0, 1] and for any ∈ (0, γ], ln N 2 ( , F G,γ , n)

5. 4 . 2

 42 Sample Complexity: Explicit Dependency on C In Chapter 2, we derived several sample complexity estimates in terms of the fat-shattering dimension of the margin class F G,γ . Below we derive sample complexity estimates with explicit dependencies on the number of categories scaling as a O(C ln 2 C). Using the new combinatorial bound we get: Theorem 24 Fix , δ ∈ (0, 1) and fix γ ∈ (0, 1]. For ∈ (0, M G ], let d ( ) = max 1 k C -dim(G k ).

.

  sup x,x ∈X ρ(x, x ) Λ X . Let G be as in Definition 3, where for all k ∈ [ [ 1, C ] ], G k is a class of L-Lipschitz functions. Let F G,γ be derived from G as in Definition 4. Then, for any ln m D, Rm (F G,γ ) Proof Substitute Inequality (5.11) in the right-hand side of Inequality (5.14) to obtain ln N 2 ( , F G,γ , m) 20C 48LΛ X D ln 6γ .

  number. For the latter, we considered the L ∞ -norm covering number, since under this norm, the decomposition for the covering numbers is optimized with respect to C.Although both sample complexity estimates scale as a O(C ln 2 C), the result based on the new combinatorial bound degrades the dependency on .In the context of the chaining, on the other hand, the application of the new combinatorial bound improved the dependency on C to a sharper than radical one. As expected, the appearance of the fat-shattering dimension inside a squared logarithmic term slightly deteriorated the convergence rate in m compared to Theorem 18 of Chapter 4. Overall, this bound is comparable to Theorem 13 of Chapter 4 displaying a O √ C dependence.

a

  capacity of the margin class in terms of that of the component classes. We derived sample complexity estimates with explicit dependencies on C in two ways via the decomposition at the level of the L ∞ -norm covering number or of the fat-shattering dimension. Both results exhibit the same O(C ln 2 C) dependence.Another open question concerns the generalization bound for margin multi-category classifiers involving a Rademacher complexity. More precisely, we were interested in optimizing the dependencies on C and m of this capacity measure under the following very general assumptions: i) no interactions are assumed between the component functions, and ii) the fat-shattering dimensions of the component classes grow no faster than polynomially with the inverse of their scales. In the bi-class setting, under the aforementioned polynomial growth assumption, Mendelson[START_REF] Mendelson | A few notes on statistical learning theory[END_REF] elaborated the convergence rate by relating the Rademacher complexity to another capacity measure, the metric entropy, and the latter to the fat-shattering dimension. Implementing this pathway in the multi-class setting, one has a choice to decompose at the level of any of these capacity measures to elaborate the dependencies on the basic parameters, especially C. We addressed this question as follows.

Finally, Chapter 5

 5 considered the decomposition at the last level: that of the fat-shattering dimension. The decomposition at this level was based on the converse relationships between the fat-shattering dimension and the other two capacity measures. Our decomposition results based on the Rademacher complexity concerned only classes of linear functions. For such classes, Lei et al. [55], and Maurer [57] obtained a sublinear dependency on C of the Rademacher complexity by employing a rather natural coupling assumption between the component functions. Particularly, the decomposition of the fat-shattering dimension based on Maurer's result yields a O(ln C)dependency. For the decomposition via the metric entropy, on the other hand, we considered both specific and general function classes. For linear classes, using the matrix covering of Bartlett et al.[START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF], which also exploits a coupling assumption, led to a logarithmic dependency on C, similar to the one based on Maurer's approach. For general classes of functions, under no coupling assumption, which was the main focus of this thesis, this dependency worsens. Yet, appealing to the L ∞ -norm metric entropy, we could obtain a decomposition result with a growth rate no more than O(C ln 2 C), independently of the capacities of the component classes. Using this decomposition, we derived a new combinatorial bound for the margin class in terms of the fat-shattering dimensions of the component classes. This result is dimension-free and there is no dependency on C in the scale of the fat-shattering dimension, an improvement over our decomposition of L p -norm metric entropies in Chapter 4. This gain propagates in the chaining yielding a better than radical dependency on C, which is comparable to the L ∞ -norm result of Chapter 4 (obtained through the decomposition of the metric entropy).

σ

  k g k (x) -g k (x) + u(g) + u(g )√ 2E σ C sup g,g ∈G C k=1 σ k g k (x) -g k (x) + u(g) + u(g ) g k (x) + u(g)) .Lemma 31 (After Lemma 4 in[START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF]) Let G be a class of functions given in Definition 3 and let ôn = (ô i ) 1 i n , õn = (õ i ) 1 i n and o Cn = (o j ) 1 j Cn be orthogaussian sequences. ThenE ôn sup g∈G n i=1 ôi g y i (x i ) E o Cn sup i-1)+k g k (x i ) .Proof Consider the following Gaussian processes:A g = n i=1ôi g y i (x i ) : g ∈ G and i-1)+k g k (x i ) : g ∈ G .

mR 2 1 .<

 21 and Inequality (D.2), on the other hand, from (D.3).ψ k (-2) < k k /2. Then, 2)!(k -(j + 2))! = k! (j + 1)!(k -(j + 2))! • k -(j + 1) (k -(j + 1))(j + 2)Applying it in (E.1), we obtainψ k+1 (-2) < (k + 1)k k /2 + (k + 1)k k /2 + (k + 1)ψ k (-2) < (k + 1)k k .Now, by the binomial theorem, for all k > 1,

1 2 (and J 2 =0 j k- 1 ( 1 β 2 and p 2 1 -

 221121 2K p ) 1/p < c < 1 (2K p ) 1/pby settingI k = (cM p (X)k, cM p (X)(k + 1)], k 0.Assume the lemma does not hold and let (β i ) i 0 be a non-increasing sequence of non-negative numbers such thatP{X > 0} = β 0 1/2 and P{X ∈ I k } = β k -β k+1 , k 0.For the conclusion of the lemma to fail it should hold that ∀k 0,β k+1 β k /2. (E.2)Now, assume that for some k, β k+1 > β k /2 and consider intervalsJ 1 = (-∞, 0] ∪ (0, cM p (X)k] = (-∞, 0] (cM p (X)(k + 1), ∞). Then, P{X ∈ J 1 } = (1 -β 0 ) + β j -β j+1 ) = 1 -β k and P{X ∈ J 2 } = j k+1 (β j -β j+1 ) = β k+1 .Lemma 38 (After Lemma 6 of[START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let F be a finite class of functions from T to [0, M F ] with M F ∈ R + and |F| > 1. Assume that for some ∈ (0, M F ], F is -separated in the pseudometric d p,tn . Then there existi ∈ [ [ 1, n ] ], a ∈ R and β ∈ (0, 1/2] such that f ∈ F : f (t i ) > a + 8(4K p )1/p p 1 |F| f ∈ F : f (t i ) < a -8(4K p ) 1/p p 2 |F| , with p β or vice versa.

Proposition 6 (

 6 After Proposition 10 in[START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let F be a class of functions from T to a finite set B of integers. Let S ⊆ T and let v : S → B. The number of pairs (S, v) strongly shattered by F is at least the number of leaves in any 1-separating tree of F.Proof The proof follows exactly the one of Proposition 10 in[START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], with a few minor technical changes. Let F be a node in a 1-separating tree of F. Let N (A) denote the number of pairs strongly shattered by a set A. For the proof it suffices to show that if F+ and Fare two sons of F, thenN ( F) N ( F+ ) + N ( F-). (E.3)By definition of the 1-separating tree, there exists i 0 ∈ [[ 1, n ]

Corollary 7 (.

 7 After Corollary 11 in[START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let F be a class of functions from T to a finite setB of integers. Let S ⊆ T and let v : S → B. If F is 4(4K p )1/p -separated in the pseudo-metric d p,tn , then it strongly shatters at least |F| 1/2 pairs (S, v) . Proposition 7 (After Proposition 12 in [61]) Let F be a class of functions from T to [ [ 0, b ] ]. Let d s = S-dim(F). Assume F is 4(4K p ) 1/p -separated in the pseudo-metric d p,tn . Then for any d d s , |F| ebn d 2d Proof By Corollary 7, F strongly shatters at least |F| 1/2 pairs (S, v). On the other hand, the total number of such pairs for which the cardinality of S is at most d s is bounded above by To see this, note that there are at most n k number of sets S of size k and for each such S the number of functions h is bounded above by b k . Therefore, The proof is completed by bounding the right-hand side of the above inequality in a standard way as follows:

  m ] ], let v i = o C(i-1)+k κ x i 1 k C . Fix λ > 0.Then, applying Lemma 39 to the right-hand side of Inequality (3.7),

EoE o Cm v i 2 E o Cm v i 2 Hκ,q * . (F. 1 ) 2 Hκ,q * . It follows that m i=1 E o Cm v i 2 Hκ|õ k | q * 2 q

 2212i=122 Cm ∇f * (v 1:i-1 ) , λv i = 0, Hκ,q * . Minimizing the right-hand side with respect to λ yieldsE o Cm sup h∈B qi-1)+k h k (x i ) Λ q * m i=1The goal now is to control the termm i=1 E o Cm v i * m i=1 κ (x i , x i ) , (F.2)where the last equality is obtained based on the fact that∀i ∈ [ [ 1, m ] ] , E o Cm C k=1 o C(i-1)+k = E õC C k=1 |õ k | .

  F be an empirical process indexed by F as in Definition 19. F is called a P T -Donsker class if and only if G F is a tight Borel-measurable element of the space of all uniformly bounded functions from F to R and G n,F converges in distribution to G F . F is called a universal Donsker class if F is P T -Donsker for any any probability measure P T on A T . Let L ∞ (T ) be as in Definition 11. A class F ⊂ L ∞ (T ) is a uniform Glivenko-Cantelli class if and only if for any > 0 and for any p ∈ N

	Theorem 1 (After Theorem 6 [27])
	For the uniform convergence of the empirical risk to the true one, it is assumed that a class is
	a Glivenko-Cantelli class. According to Slutsky's lemma (Example 1.4.7 in [86]), on the other
	hand, all Donsker classes are Glivenko-Cantelli, and thus much more happens for such classes
	(i.e., faster rate of convergence). Whether a (uniformly bounded) class F is a Glivenko-Cantelli
	or Donsker class depends on the growth-rate of the metric entropy of F.

* ∪ {∞},

  1.2 ,

	m > log	2d G 2 (2C)	1 d G for all d G > 2 and thus, N is a strictly positive integer. Applying it to (4.34),
	we get

  for linear classes to RKHSs. Its application led to a bound in O ln

	to the O	ln 2 (m)

√ m rate obtained with the bound of Alon and coauthors. Focusing on Gaussian RKHSs, we could improve it further to O 1 √ m at the cost of introducing new parameters: the

  Now, the event that the realizations of f and f are different elements in F happens with probability 1 -1/|F|. Then, by the separation assumption on F we haveE f,f ∼P F d p,tn f, f -1/|F|) p (1 -1/2) p = p /2.

	Thus,
	1 n	n i=1	E f ∼P F |f (t i )| p	p 2 p+1 .

the Minkowski inequality, for any i ∈ [

[ 1, n ]

],

E f,f ∼P F f (t i ) -f (t i ) p (E f ∼P F |f (t i )| p ) 1/p + E f ∼P F -f (t i ) p 1/p p = (E f ∼P F |f (t i )| p ) 1/p + E f ∼P F f (t i ) p 1/p p = 2 p E f ∼P F |f (t i )| p .

Taking it into account in the formula above, we obtain,

E f,f ∼P F d p,tn f, f p 2 p n n i=1 E f ∼P F |f (t i )| p . p (

1

It

means that there exists i ∈ [ [ 1, n ] ], such that

(m) √ m compared

Sample Complexity

Theorem 5 Fix , δ ∈ (0, 1) and fix γ ∈ (0, 1]. For ∈ (0, γ], let d ( ) = -dim (F G,γ We apply it to the right-hand side of (2.2): To conclude the proof, it suffices to upper bound the right-hand side by δ and solve for m.

Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] provide the following dimension-free bound in the L 2 -norm:

Lemma 8 (After Theorem 1 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let F be a class of functions from T to [-M F , M F ] with M F ∈ R + . Let d ( ) = -dim (F). Then, for all ∈ (0, 2M F ],

N 2 ( , F, n) 14M F 20d( 96 ) .

(2.11)

The claim follows from the fact that |F | = M( , F, d p,tn ), the application of Lemma 1.3 and taking the supremum over t n ∈ T n of both sides of the bound.

From the decomposition formula (4.5) one can see that, based on C 1 p = 2 1 p log 2 (C) , the dependency on C in the scale of covering numbers can be eliminated for all p log 2 (C). Thus, we combine Inequality (4.5) with Theorem 17 using p = log 2 (C) for C > 4. It yields the following corollary:

Corollary 1 Let G be a class of functions as in Definition 3. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 8. For ∈ (0,

and

Proof Inequality (4.30) follows from the application of Inequality (4.5) and part (a) of Theorem 17 (where we drop d( ) from the denominator inside the logarithm as it is greater than one), along with the fact that C 1/ log 2 (C) < 2 and log 2 (C) < log 2 (2C). We obtain Inequality (4.31) in a similar way using part (b) of Theorem 17.

Chaining Bound

The availability of two kinds of combinatorial bounds allows us to adapt to the phase transition in the chaining in the following manner. For d G ∈ (0, 2), the formula (4.4) can be upper bounded by the corresponding integral, and the use of the dimension-free bound (4.31) leads to the optimized result with respect to the number of classes without losing in m and γ. For d G 2, such a result is obtained from the application of the bound (4.30) in (4.4). As it was explained before, the second case can also be characterized by the fact that there is a freedom in the choice of the number N of steps to construct the chaining. To optimize this construction when d G > 2, we make the non restrictive assumption that m is greater than a small power of C.

Theorem 18 (Theorem 3 in [START_REF] Musayeva | Rademacher complexity and generalization performance of multi-category margin classifiers[END_REF]) Let G be a class of functions as in Definition 3. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 8. Then, under dimensionality of the description space and the bandwith parameter.

For general classes, to find a good trade-off between the dependencies on C and m, we extended the L 2 -norm metric entropy bound of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] to L p -norms with p ∈ N * \ {1, 2} in two ways: in one we kept the dependency on the sample size, and in the other, we removed it by means of the probabilistic extraction principle. The application of these bounds in the chaining gave us a radical dependency on C up to logarithmic factors without worsening those on m and γ: a uniform improvement upon the result of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF].

So far, we considered decomposing at the level of the Rademacher complexity (in Chapter 3), and the metric entropy (in this chapter), and the way these decompositions affect the dependencies on the basic parameters. The case that remains to be studied is the decomposition at the last level of scheme (4): that of the fat-shattering dimension. This is the subject of the next chapter.

Conclusions

In this chapter, we employed several approaches to decompose the fat-shattering dimension of the margin class in terms of that of the component classes. The first approach was based on an argument made by Mendelson [59] that allows one to upper bound the fat-shattering dimension of a class via its Rademacher complexity. The literature provides efficient upper bounds on the Rademacher complexity of linear classifiers: the bound of Lei et al. [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF], and its improvement due to Maurer [START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF]. Particularly, using Maurer's approach we could upper bound the fat-shattering dimension with as sharp as a O(ln C) dependence.

The second approach was based on the fact that there exists a converse relation between the fat-shattering dimension and the metric entropy, the line of work due to Bartlett et al. [START_REF] Bartlett | Covering numbers for real-valued function classes[END_REF] in the L 1 -norm, and Talagrand [START_REF] Talagrand | Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions[END_REF] in the L 2 -norm. In this chapter, we demonstrated that there is rather a straightforward relation between the fat-shattering dimension and the L ∞norm metric entropy. Then, appealing to the combinatorial bound of Alon et al. [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] and using the decomposition result for the covering numbers in the L ∞ -norm, produced a decomposition growing as a O(C ln 2 (C)). For classes of linear functions, this dependence could be improved to a O(C ln(C)) if one appeals to the metric entropy bound of Zhang [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF]. The extension of this entropy bound to matrices by Bartlett and co-authors [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF], allows one to make use of a coupling assumption between the component functions, and eliminate the linear factor C. Consequently, we obtained a decomposition result scaling as a O(ln C), similar to the case with Maurer's approach.

We also considered the decomposition of the fat-shattering dimension of yet another family of classifiers: Lipschitz classifiers on doubling spaces [START_REF] Gottlieb | Efficient classification for metric data[END_REF]. We generalized the bound on the fatshattering dimension, Corollary 4 in [START_REF] Gottlieb | Efficient classification for metric data[END_REF], to the multi-category case in a rather straightforwad fashion with a linear dependency on C.

Combining the decomposition of the fat-shattering dimension of general function classes and

the combinatorial bound of Guermeur [START_REF] Guermeur | Combinatorial and Structural Results for gamma-Psi-dimensions[END_REF], Lemma 7, led to a new combinatorial bound for the margin class involving the fat-shattering dimensions of the component classes. Comparing to a similar result, Corollary 1 of Chapter 4, the advantage of the new bound is that it is dimensionfree, and there is no dependency on C in the scale of the fat-shattering dimension involved. The latter, however, now also appears inside a squared logarithmic term, which is the price to pay for this gain. This result was applied in two contexts.

First, we were interested in elaborating the dependency on the number of categories of the sample complexity for the deviation probability (2.2) of Chapter 1. To this end, we used the new combinatorial bound, and for a comparison, we considered decomposing directly at the level Based on the definition of an orthogaussian sequence, we have that

Similarly,

From (A.5) and (A.6) it follows that Inequality (A.4) holds.

The second inequality is proved similarly based on the fact that

õi max

the right-hand side being less than (A.6).

Theorem 28 (After Theorem 2 in [START_REF] Bartlett | Covering numbers for real-valued function classes[END_REF]) Let F be a class of functions from

Then, for all ∈ (0, M F ],

if and only if

Thenf, the number N f of functions f -close to f can be computed by the following combinatorial formula:

This can be upper bounded according to Chernoff-Okamoto inequality [START_REF] Dudley | Uniform central limit theorems[END_REF]:

where p 1/2 and m np. Let p = 1/2. Then,

Applying it to the right-hand side of Inequality (A.8), we obtain

Substitute it in the upper bound on d f , f to obtain

Since there are 2 d functions in F | S , the ratio

To switch to the covering number of F, we use the triangle inequality which gives

Finally, the claim follows from

Lemma 32 (Lemma B.2 in [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF]) Let T be a standard Gaussian random variable. For any p > 0, the p-th moment of T can be bounded as

Lemma 33 (After Lemma 1 in [START_REF] Zhang | Covering number bounds of certain regularized linear function classes[END_REF]) Let H denote a Hilbert space with the norm • H . Let h ∈ H be as N j=1 α j h j , where each α j 0 and N j=1 α j 1. Then, for any K 1, there exist non-negative integers

Appendix B

Basic Concentration Inequalities

Concentration inequalities are the results dealing with the deviation of a random variable from its expected value, and they are indispensable tools in the learning theory. This Appendix presents several basic concentration inequalities that we refer to in the main text. In the following,

T stands for a non-negative real-valued random variable with law P T , and we assume that

Theorem 29 (Chebyshev's inequality) For all > 0,

Suppose that T has a moment generating function

for all λ > 0. The application of Markov's bound to exp (λ (T -ET )) gives the following result.

Theorem 30 (Chernoff 's inequality)

This result can be expressed as an optimization problem:

When T is a standard Gaussian random variable, substituting its moment generating function

into (B.3) gives:

Taking derivative from the right-hand side and making it equal to zero we get λ = . Thus, for a standard Gaussian random variable the Chernoff bound takes the following form:

Thus:

Proposition 2 (Gaussian tail probability) For all > 0,

The moment generating function of a Rademacher random variable is dominated by that of a standard Gaussian random variable as shown below.

Proposition 3 For any λ > 0,

Thus, a Rademacher variable is said to be a sub-Gaussian random variable and the tail probability Combining this result with Chebyshev's inequality leads to the tail bound for the sum of independent and identically distributed random variables.

Theorem 31 (Hoeffding's inequality, Theorem 2 in [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]) Let (T i ) 1 i n be a sequence of independent and identically distributed random variables such that

Then for all > 0,

If all T i takes their values in [-a, a] with a > 0 almost surely, then (B.6) becomes

In the case when the variance of T i is much less than a, Bernstein's inequality provides a tighter control on the tail probability.

Theorem 32 (Bernstein's inequality [START_REF] Bernstein | The Theory of Probabilities[END_REF]) Let a > 0 and let T be a random variable taking its values in an interval [-a, a] almost surely. Let var(T ) denote the variance of T . Let (T i ) 1 i n be a sequence of n independent copies of T and let T = 1 n n i=1 T i . Then for all > 0,

Hoeffding's bound can be generalized to a more complex setting. The following result applies to a function of independent random variables under the condition that it varies no more than a constant c i when the value of the i-th random variable changes.

Theorem 33 (McDiarmid's inequality [START_REF] Mcdiarmid | On the method of bounded differences[END_REF]) Let f :

T i , we obtain Hoeffding's inequality as the special case.

Appendix C

Symmetrization

The following result is the symmetrization for probability. Its proof is based on that of Lemma 2 of Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF].

be a sequence of independent random variables having the same distribution as Z. Let Z m = (Z i ) 1 i m be an independent copy of Z m . Fix > 0 and

According to Tonelli's theorem, it holds that

We now focus on the probability

Since for all i ∈ [ [ 1, m ] ], Z i admits the same distribution as Z, we have

and thus the tail probability

can be bounded using a concentration inequality. Chebyshev's inequality (B.1) yields a tighter bound. Since the variance of φ γ (f g * ,γ (Z)) has a bounded range, [0, 1], by Popoviciu's inequality [START_REF] Popoviciu | Sur les équations algébriques ayant toutes leurs racines réelles[END_REF] we obtain

Consequently, under the assumption that m > 2 2 ,

.

Substituting it into (C.5) and taking into account that

we get the desired result.

Appendix D

Perceptron Mistake Bound

The following is the perceptron mistake bound extended to a Hilbert space.

Proposition 4 Let F of a set of functions from a Hilbert space (H,

Let (i k ) 1 k m be a sequence of indices of examples on which the perceptron makes an update before converging to f * . Then, m is bounded by

and the function f * takes the form

Proof The perceptron loops over all examples and makes an update

with a learning rate µ ∈ (0, 1] and the initial condition w (0) = 0, whenever sign w (k-1) , h i = y i . We set µ = 1 and combine the changes in the inner product w (m) , w α and the squared norm

H after m steps. By our assumption, after k steps,

Here we have gathered the results used in the proof of our extension of the L 2 -norm combinatorial bound of Mendelson and Vershynin [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF].

Proof By Formula (8.5) in [17, page 119],

where ψ p (u) = p-1 j=0 (-1) j p j+1 (u + 1) j ψ (p-1)-j (u) is an Eulerian polynomial in u of degree p -1 with ψ 0 (u) = ψ 1 (u) = 1 (see page 116 in [START_REF] Berndt | Ramanujan's Notebooks, Part I[END_REF] for explicit form of this polynomial for smaller values of p). Thus for u = 2,

We now show by induction that for all p > 2, ψ p (-2) < p p 2 . By definition,

For the base case, p = 3, it is easily seen that ψ 3 (-2) < 3 3 /2. Now, assume for k > 3, By definition of (β i ) i 0 and by our assumption, 1/2 β 0 β k β k+1 > β k /2 0, which means that β k ∈ (0, 1/2]. Now, let a be the middle point between the intervals J 1 and J 2 and let β = β k . We have that

Thus, the lemma holds. This proves (E.2). Now, by induction from (E.2) we get that

We use it in the computation of M p p (X). By definition,

By construction, whenever

By a similar procedure, it can be proved that

This produces a contradiction M p p (X) < M p p (X)/2 + M p p (X)/2 = M p p (X) proving the lemma.

In the following, T = {t i : 1 i n} is a finite set and t n = (t i ) 1 i n .

Next, we apply Lemma 37 to the random element f and take into account that

Then, it follows that

and, similarly,

Finally, the claim follows from the definition of P F .

The results given in the sequel call for the introduction of the definition of the -separating tree.

Definition 24 Let F be a class of functions on T . A tree T (F) is a finite collection of subsets of F, such that its any two elements are either disjoint or one of them contains the other. A son of F ∈ T (F) is its maximal (with respect to inclusion) proper subset. An element of T (F) with no sons is called a leaf. Let > 0. If every F ∈ T (F) which is not a leaf has exactly two sons F+ , Fand

then T (F) is an -separating tree.

Proposition 5 (After Proposition 8 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let F be a finite class of functions from T to [0, M F ] with M F ∈ R + . Assume that for some ∈ (0, M F ], F is -separated in the pseudo-metric d p,tn . Then, there is a /4(4K p ) 1/p -separating tree of F with at least |F| 1/2 leaves.

Proof By Lemma 38, F has two subsets F + and

Appendix F

Rademacher Complexity Bounds for Linear Classifiers

The proof of Theorem 19 makes use of a result concerning the strong convexity and strong smoothness due to Kakade and coauthors [START_REF] Kakade | Regularization techniques for learning with matrices[END_REF]. To introduce it, we need to give several definitions.

Let R * = R ∪ {∞}. Let the metric space T be equipped with an inner product •, • and let f : T → R * be a convex function. Let β > 0. f is said to be β-strongly convex with respect to the • T -norm on T if for all t, t ∈ T and for all α ∈ (0, 1),

The dual

where σC = (σ k ) 1 k C is the Rademacher sequence. Consequently, Inequality (F.5) is replaced by

where the gain is by a factor M 1 q * q * π 4 . In the above inequality, substituting the value q * = 2 ln C for p 1 and using the fact that C Appendix G

Technical Results

This Appendix gathers several technical results used in the main text.

Lemma 40 (Lemma 3.14 in [START_REF] Anthony | Uniform convergence and learnability[END_REF]) For any α > 0 and for any x > 0, log a x log a 1 αa ln a + αx. Proof To estimate s we appeal to the classical formula of stars and bars [START_REF] Feller | An introduction to probability theory and its applications[END_REF]:

The right-hand side can be upper bounded as follows. For l > 0, we have l + n -1 n -1 = (l + n -1)! (n -1)!l! = l i=1 (i + n -1) l! .

Since for all i l, n + i -1 ni, we have

Thus,

n l (n + 1) M .