Yann Guermeur
email: yann.guermeur@loria.fr

L p -norm Sauer-Shelah Lemma for Margin Multi-category Classifiers

Keywords: Sauer-Shelah Lemma for Margin Multi-category Classifiers margin multi-category classifiers, guaranteed risks, -entropy, γ-dimension, generalized Sauer-Shelah lemmas Mathematics Subject Classification: 68Q32, 62H30

In the framework of agnostic learning, one of the main open problems of the theory of multi-category pattern classification is the characterization of the way the complexity varies with the number C of categories. More precisely, if the classifier is characterized only through minimal learnability hypotheses, then the optimal dependency on C that an upper bound on the probability of error should exhibit is unknown. We consider margin classifiers. They are based on classes of vector-valued functions with one component function per category, and the classes of component functions are uniform Glivenko-Cantelli classes. For these classifiers, an L p -norm Sauer-Shelah lemma is established. It is then used to derive guaranteed risks in the L ∞ and L 2 -norms.

These bounds improve over the state-of-the-art ones with respect to their dependency on C, which is sublinear.

Introduction

During a long period, the theory of multi-category pattern classification was considered as a topic of limited importance. Two connected reasons can be put forward to explain this phenomenon. On the one hand, the theory dedicated to dichotomies was making rapid strides, on the other hand, decomposition methods were seen as efficient solutions to tackle polytomies. An obvious drawback of this line of reasoning is to neglect the specificities of the multi-category case, such as the dependency of the complexity of the task on the number C of categories. In recent years, several studies addressed this question, by deriving upper bounds on the probability of error of multi-category classifiers, especially margin ones. However, most of these guaranteed risks were dedicated to specific families of classifiers, let them be kernel machines [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF][START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF], neural networks [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF], decision trees [START_REF] Kuznetsov | Multi-class deep boosting[END_REF] or nearest neighbors classifiers [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF]. This article deals with margin classifiers. They are based on classes of vector-valued functions with one component function per category, and the classes of component functions are uniform Glivenko-Cantelli classes. For these classifiers, an L p -norm Sauer-Shelah lemma is established. It is then used to derive guaranteed risks in the L ∞ and L 2 -norms. These bounds improve over the state-of-the-art ones with respect to their dependency on C, which is sublinear. Thus, they pave the way for the characterization of the optimal dependency on C that could be obtained in the framework of agnostic learning, under minimal learnability/measurability hypotheses regarding the classes of functions involved.

The organization of the paper is as follows. Section 2 deals with the theoretical frame-1 work and the margin multi-category classifiers. Section 3 is devoted to the derivation of the L p -norm Sauer-Shelah lemma. The bound based on the L ∞ -norm and that based on the L 2 -norm are respectively established in Section 4 and Section 5. At last, we draw conclusions and outline our ongoing research in Section 6. To make reading easier, basic results from the literature and technical lemmas have been gathered in appendix.

Margin multi-category classifiers

The theoretical framework for the margin multi-category classifiers has been introduced in [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF]. It is summarized below.

Theoretical framework

We consider the case of C-category pattern classification problems [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF] with

C ∈ N \ [ [ 0, 2 ] ].
Each object is represented by its description x ∈ X and the set Y of the categories y can be identified with the set of indices of the categories:

[ [ 1, C ] ].
We assume that (X , A X ) and (Y, A Y ) are measurable spaces and denote by A X ⊗ A Y the tensor-product sigma algebra on the Cartesian product X × Y. We make the hypothesis that the link between descriptions and categories can be characterized by an unknown probability measure P on the measurable space (X × Y, A X ⊗ A Y ). Let Z = (X, Y ) be a random pair with values in Z = X × Y, distributed according to P . The single knowledge source on P available is an m-sample Z m = (Z i ) 1 i m = ((X i , Y i )) 1 i m made up of independent copies of Z (in short Z m ∼ P m ). The theoretical framework is thus that of agnostic learning [START_REF] Kearns | Toward efficient agnostic learning[END_REF]. To simplify reasoning, in the sequel, the hypothesis m > C is made.

We add an hypothesis to that framework: the fact that the classifiers considered are based on classes of vector-valued functions with one component function per category, and the classes of component functions are uniform Glivenko-Cantelli. The definition of this property calls for the introduction of an intermediate definition.

Definition 1 (Empirical probability measure) Let (T , A T ) be a measurable space and let T be a random variable with values in T , distributed according to a probability measure P T on (T , A T ). For n ∈ N * , let T n = (T i ) 1 i n be an n-sample made up of independent copies of T . The empirical measure supported on this sample, P Tn , is given by

P Tn = 1 n n i=1 δ T i ,
where δ T i denotes the Dirac measure centered on T i . and P Tn be defined as in Definition 1. Let F be a class of measurable functions on T . Then

F is a uniform Glivenko-Cantelli class if for every ∈ R * + , lim n-→+∞ sup P T P sup n n sup f ∈F E T ∼P T n f T -E T ∼P T [f (T )] > = 0,
where P denotes the infinite product measure P ∞ T .

Henceforth, we shall refer to uniform Glivenko-Cantelli classes by the abbreviation GC classes. GC classes must be uniformly bounded up to additive constants (see for instance Proposition 4 in [START_REF] Dudley | Uniform and universal Glivenko-Cantelli classes[END_REF]). For notational convenience, we replace this property by a stronger one: the vector-valued functions take their values in a hypercube of R C . The definition of a margin multi-category classifier is thus the following one.

Definition 3 (Margin multi-category classifiers) Let G = C k=1 G k be a class of func- tions from X into [-M G , M G ] C with M G ∈ [1, +∞). The classes G k of component func-
tions are supposed to be GC classes. For each function g = (g k ) 1 k C ∈ G, a margin multi-category classifier on X is obtained by application of the operator dr from G into (Y { * }) X named decision rule and defined as follows:

∀x ∈ X ,      argmax 1 k C g k (x) = 1 =⇒ dr g (x) = argmax 1 k C g k (x) argmax 1 k C g k (x) > 1 =⇒ dr g (x) = *
where |•| returns the cardinality of its argument and * stands for a dummy category.

In words, dr g returns either the index of the component function whose value is the highest, or the dummy category * in case of ex aequo. In the case when the g k (x) are class posterior probability estimates, then dr is simply Bayes' estimated decision rule [START_REF] Richard | Neural network classifiers estimate Bayesian a posteriori probabilities[END_REF]. The qualifier margin refers to the fact that the generalization capabilities of such classifiers can be characterized by means of the values taken by the differences of the corresponding component functions. The use of the dummy category to avoid breaking ties is not central to the theory. Its main advantage rests in the fact that it keeps the reasoning and formulas as simple as possible.

With this definition at hand, the aim of the learning process is to minimize over G the probability of error P (dr g (X) = Y ). This probability can be reformulated in a handy way thanks to the introduction of additional functions. tion 3. For all g ∈ G, the function

f g from X × [ [ 1, C ] ] into [-M G , M G ] is defined by: ∀ (x, k) ∈ X × [ [ 1, C ] ] , f g (x, k) = 1 2 g k (x) -max l =k g l (x) .
Then, the class F G is defined as follows:

F G = {f g : g ∈ G} .
Definition 5 (Expected risk L) Let G be a class of functions satisfying Definition 3 and let φ be the standard indicator loss function given by:

∀t ∈ R, φ (t) = 1l {t 0} .
The expected risk of any function g ∈ G, L (g), is given by:

L (g) = E (X,Y )∼P [φ • f g (X, Y )] = P (dr g (X) = Y ) .
Its empirical risk measured on the m-sample Z m is:

L m (g) = E Z ∼Pm φ • f g Z = 1 m m i=1 φ • f g (Z i ) .
In order to take benefit from the fact that the classifiers of interest are margin ones, the sample-based estimate of performance which is actually used (involved in the different guaranteed risks) is obtained by substituting to φ a (dominating) margin loss/cost function.

In this study, the definition used for those functions is the following one.

Definition 6 (Margin loss functions) A class of margin loss functions φ γ parameterized by γ ∈ (0, 1] is a class of nonincreasing functions from R into [0, 1] satisfying:

1. ∀γ ∈ (0, 1] , φ γ (0) = 1 ∧ φ γ (γ) = 0; 2. ∀ (γ, γ ) ∈ (0, 1] 2 , γ < γ =⇒ ∀t ∈ (0, γ) , φ γ (t) φ γ (t).
Remark 1 The qualifier dominating is appropriate since we have for all (γ, t) ∈ (0, 1]×R,

φ γ (t) φ (t).
The second property is especially useful to derive guaranteed risks holding uniformly for all values of γ. This can be achieved by means of Proposition 8 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]. It is noteworthy that these losses are not convex. They can even be discontinuous (whereas the definition used by Koltchinskii and Panchenko in [21] (Section 2) includes the Lipschitz property).

Definition 7 (Margin risk L γ ) Let G be a class of functions satisfying Definition 3. For every (ordered) pair (g, γ) ∈ G × (0, 1], the risk with margin γ of g, L γ (g), is defined as:

L γ (g) = E Z∼P [φ γ • f g (Z)] .
L γ,m (g) designates the corresponding empirical risk, measured on the m-sample Z m :

L γ,m (g) = E Z ∼Pm φ γ • f g Z = 1 m m i=1 φ γ • f g (Z i ) .
Taking our inspiration from [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], we use margin loss functions in combination with a piecewise-linear squashing function. In short, the idea is to restrict the available information to what is relevant for the assessment of the prediction accuracy (the value of the margin loss is not affected), so as to optimize the way the introduction of the margin parameter γ is taken into account.

Definition 8 (Piecewise-linear squashing function π γ ) For γ ∈ (0, 1], the piecewiselinear squashing function π γ is defined by:

∀t ∈ R, π γ (t) = t1l {t∈(0,γ]} + γ1l {t>γ} .
This definition actually satisfies the aforementioned specification since we have:

∀γ ∈ (0, 1] , φ γ • π γ = φ γ .
Definition 9 (Class of functions F G,γ ) Let G be a class of functions satisfying Definition 3 and F G the class of functions deduced from G according to Definition 4. For every

pair (g, γ) ∈ G × (0, 1], the function f g,γ from X × [ [ 1, C ] ] into [0, γ] is defined by: f g,γ = π γ • f g .
Then, the class F G,γ is defined as follows:

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

Scale-sensitive capacity measures

The guaranteed risks are ordinarily obtained in several main steps, corresponding to a basic supremum inequality and successive upper bounds on the capacity measure it involves, each of which corresponds to a change of capacity measure. Although the measures which are central to this study are covering numbers, we start by giving the definition of the Rademacher complexity since it is the measure appearing first in the case of the L 2 -norm.

For n ∈ N * , a Rademacher sequence σ n is a sequence (σ i ) 1 i n of independent random signs, i.e., independent and identically distributed random variables taking the values -1 and 1 with probability 1 2 (symmetric Bernoulli or Rademacher random variables).

Definition 10 (Rademacher complexity) Let (T , A T ) be a measurable space and let T be a random variable with values in T , distributed according to a probability measure P T on (T , A T ). For n ∈ N * , let T n = (T i ) 1 i n be an n-sample made up of independent copies of T and let σ n = (σ i ) 1 i n be a Rademacher sequence. Let F be a class of real-valued functions with domain T . The empirical Rademacher complexity of F is

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 ) .
Remark 2 The fact that the functional classes F of interest can be uncountable calls for a specification. We make use of the standard convention (see for instance Formula (0.2) in [START_REF] Talagrand | The Generic Chaining: Upper and Lower Bounds of Stochastic Processes[END_REF]). Let (T s ) s∈S be a stochastic process. Then,

E sup s∈S T s = sup { S⊂S: | S|<+∞} E max s∈ S T s .
The concept of covering number ( -entropy), as well as the underlying concepts of -cover and -net, can be traced back to [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF].

Definition 11 ( -cover, -net, covering numbers, and -entropy) Let (E, ρ) be a pseudometric space, E ⊂ E and ∈ R *

+ . An -cover of E is a coverage of E with open balls of radius the centers of which belong to E. These centers form an -net of E . A proper -net of E is an -net of E included in E . If E has an -net of finite cardinality, then its covering number N ( , E , ρ) is the smallest cardinality of its -nets:

N , E , ρ = min E : E ⊂ E ∧ ∀e ∈ E , ρ e, E < .
If there is no such finite net, then the covering number is defined to be infinite. The corresponding logarithm, log 2 (N ( , E , ρ)), is called the minimal -entropy of E , or simply the -entropy of E . N (p) ( , E , ρ) will designate a covering number of E obtained by considering proper -nets only. In the finite case, we have thus:

N (p) , E , ρ = min E : E ⊂ E ∧ ∀e ∈ E , ρ e, E < .
There is a close connection between covering and packing properties of bounded subsets in pseudo-metric spaces.

Definition 12 ( -separation and packing numbers [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF]) Let (E, ρ) be a pseudo-metric space and ∈ R * + . A set E ⊂ E is -separated if, for any distinct points e and e in E , ρ (e, e )

. The -packing number of E ⊂ E, M ( , E , ρ), is the maximal cardinality of an -separated subset of E , if such maximum exists. Otherwise, the -packing number of E is defined to be infinite.

In this study, the functional classes met are endowed with empirical (pseudo-)metrics derived from the L p -norm.

Definition 13 (Pseudo-distance d p,tn ) Let F be a class of real-valued functions on T .

For

n ∈ N * , let t n = (t i ) 1 i n ∈ T n . Then, ∀p ∈ N * , ∀ f, f ∈ F 2 , d p,tn f, f = f -f Lp(µ tn ) = 1 n n i=1 f (t i ) -f (t i ) p 1 p and ∀ f, f ∈ F 2 , d ∞,tn f, f = f -f L∞(µ tn ) = max 1 i n f (t i ) -f (t i ) ,
where µ tn denotes the uniform (counting) probability measure on {t i : 1 i n}.

Definition 14 (Uniform covering numbers [START_REF] Williamson | Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators[END_REF] and uniform packing numbers [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 real-valued functions on T and F ⊂ F. For p ∈ N * {+∞}, ∈ R * + , and n ∈ N * , the uniform covering number N p , F, n and the uniform packing number M p , F, n are defined as follows:

     N p , F, n = sup tn∈T n N , F, d p,tn M p , F, n = sup tn∈T n M , F, d p,tn .
We define accordingly N (p) p , F, n as:

N (p) p , F, n = sup tn∈T n N (p) , F, d p,tn .
Our Sauer-Shelah lemma relates covering/packing numbers to a scale-sensitive generalization of the Vapnik-Chervonenkis (VC) dimension [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]: the fat-shattering dimension [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF] also known as the γ-dimension.

Definition 15 (Fat-shattering dimension [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF]) Let F be a class of functions from

T into S ⊂ R. For γ ∈ R * + , a subset s T n = {t i : 1 i n} of T is said to be γ-shattered by F if there is a vector b n = (b i ) 1 i n ∈ S n such that, for every vector l n = (l i ) 1 i n ∈ {-1, 1} n , there is a function f ln ∈ F satisfying ∀i ∈ [ [ 1, n ] ] , l i (f ln (t i ) -b i ) γ.
The vector b n is called a witness to the γ-shattering. The fat-shattering dimension with margin γ of the class F, γ-dim (F), is the maximal cardinality of a subset of T γ-shattered by F, if such maximum exists. Otherwise, F is said to have infinite fat-shattering dimension with margin γ.

Remark 3 With the introduction of the set S (and the constraint b n ∈ S n ) in Definition 15, there is no need to make use of the strong dimension (Definition 3.1 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]). A difference with the definition used in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] regards the concept of shattering. As most of the authors (see for instance [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]), we do not adopt the convention consisting in considering that the empty set can be shattered. Using the terminology of Mendelson and Vershynin (see Section 2.2 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]), the trivial center is not involved in our computations.

Each of the generalized Sauer-Shelah lemmas in the literature is based on a main combinatorial result that involves a class of functions whose domain and codomain are finite sets.

The first property is simply obtained by application of a restriction of the domain to the data at hand. As for the finiteness of the codomain, if needed, it is obtained by application of a discretization operator. The present study makes use of the following one, already employed, for instance, in [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF].

Definition 16 (η-discretization operator) Let F be a class of functions from T into

[-M F , M F ] with M F ∈ R * + . For η ∈ R * + , define the η-discretization as an operator on F such that: (•) (η) : F -→ F (η) f → f (η) ∀t ∈ T , f (η) (t) = η f (t) + M F η
where the floor function • is defined by:

∀u ∈ R, u = max {j ∈ Z : j u} .
The finiteness of all the capacity measures considered in the sequel is ensured. Precisely, Theorem 2.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] (see also Theorem 2.4 in [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF]) tells us that the fat-shattering dimension of a GC class is finite for every positive value of γ, and a corollary of the generalized Sauer-Shelah lemma is that the finiteness of this dimension implies the total boundedness.

L p -norm Sauer-Shelah Lemma

Our master lemma is made up of two partial results. The first one, the decomposition lemma, relates the covering numbers of F G,γ to those of the classes of component functions

G k .
The second one is the actual generalized Sauer-Shelah lemma.

Master lemma

Lemma 1 (Decomposition lemma) Let G be a class of functions satisfying Definition 3 and F G the class of functions deduced from G according to Definition 4. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 9. Then, for ∈ R * + , m ∈ N * , and z m = ((x i , y i ))

1 i m = (z i ) 1 i m , ∀p ∈ N * {+∞} , N (p) ( , F G,γ , d p,zm ) N (p) ( , F G , d p,zm ) C k=1 N (p) C 1 p , G k , d p,xm , (1)
where

x m = (x i ) 1 i m .
Proof The left-hand side inequality in Formula (1) is trivially true for > γ. Otherwise, it is a direct consequence of the 1-Lipschitz property of the function π γ . Similarly, the proof of the right-hand side inequality is nontrivial only for 2M G . We first derive it for a finite value of p only. For every function g = (g k ) 1 k C ∈ G and every element

z = (x, y) ∈ X × [ [ 1, C ] ], let k (g, z) ∈ [ [ 1, C ] ] \ {y} be an index of category such that f g (z) = 1 2 g y (x) -g k(g,z) (x) . For all k ∈ [ [ 1, C ] ],
g = (g k ) 1 k C ∈ G, there exists a function ḡ = (ḡ k ) 1 k C ∈ Ḡ such that: ∀k ∈ [ [ 1, C ] ] , d p,xm (g k , ḡk ) < . (2)
By definition of the empirical pseudo-metric, for every k ∈ [ [ 1, C ] ] and every function

g k ∈ G k , d p,xm (g k , ḡk ) < ⇐⇒ 1 m m i=1 |g k (x i ) -ḡk (x i )| p 1 p < =⇒ ∀i ∈ [ [ 1, m ] ] , |g k (x i ) -ḡk (x i )| < m 1 p =⇒ (|g k (x i ) -ḡk (x i )|) 1 i m = m 1 p (θ ki ) 1 i m (3)
where

(θ ki ) 1 i m ∈ [0, 1) m . Furthermore, if g k(g,z i ) (x i ) ḡk(ḡ,z i ) (x i ), then g k(g,z i ) (x i ) -ḡk(ḡ,z i ) (x i ) = g k(g,z i ) (x i ) -ḡk(ḡ,z i ) (x i ) g k(g,z i ) (x i ) -ḡk(g,z i ) (x i ) g k(g,z i ) (x i ) -ḡk(g,z i ) (x i ) θ k(g,z i )i m 1 p . Symmetrically, g k(g,z i ) (x i ) ḡk(ḡ,z i ) (x i ) implies that g k(g,z i ) (x i ) -ḡk(ḡ,z i ) (x i ) θ k(ḡ,z i )i m 1 p . To sum up, ∀i ∈ [ [ 1, m ] ] , g k(g,z i ) (x i ) -ḡk(ḡ,z i ) (x i ) max θ k(g,z i )i , θ k(ḡ,z i )i m 1 p . (4)
For all k ∈ [ [ 1, C ] ], let θ k = (θ ki ) 1 i m .
Making use once more of (2) provides us with:

∀k ∈ [ [ 1, C ] ] , θ k p < 1. (5)
As a consequence,

d p,zm (f g , f ḡ) = 1 m m i=1 |f g (z i ) -f ḡ (z i )| p 1 p = 1 2 1 m m i=1 g y i (x i ) -g k(g,z i ) (x i ) -ḡy i (x i ) + ḡk(ḡ,z i ) (x i ) p 1 p 1 2 1 m m i=1 |g y i (x i ) -ḡy i (x i )| + g k(g,z i ) (x i ) -ḡk(ḡ,z i ) (x i ) p 1 p 1 2 m i=1 θ y i i + max θ k(g,z i )i , θ k(ḡ,z i )i p 1 p (6) m i=1 max 1 k C θ p ki 1 p C k=1 θ k p p 1 p < C 1 p . (7)
Inequality ( 6) is obtained by application of ( 3) and ( 4), and Inequality (7) springs from Inequality [START_REF] Bartlett | Covering numbers for real-valued function classes[END_REF]. We have established that the set of functions f ḡ is a proper C 1 p

-net of F G with respect to the pseudo-metric d p,zm . Since its cardinality is at most that of Ḡ,

∀z m ∈ (X × [ [ 1, C ] ]) m , N (p) C 1 p , F G , d p,zm C k=1 N (p) ( , G k , d p,xm ) .
The right-hand side inequality in Formula (1) then follows from performing a change of variable. The proof for the uniform convergence norm results from taking the limit when p goes to infinity.

The actual generalized Sauer-Shelah lemma is an extension of Lemma 3.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] and Lemma 8 in [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF]. In the case when p is finite, then the upper bound is dimension free (does not depend on the number n of points) thanks to the implementation of the probabilistic extraction principle described in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF].

Lemma 2 (Generalized Sauer-Shelah lemma) Let F be a class of functions from T into [-M F , M F ] with M F ∈ R * + . F is supposed to be a GC class. For ∈ (0, M F ], let d ( ) = -dim (F). Then for ∈ (0, 2M F ] and n ∈ N * , ∀p ∈ N * , M p ( , F, n) 2 2(K (p)+1) 6272eK (p) 3 2M F 2p+1 2K (p)d( 45 ) , (8)
where

K (p) = (p + 2) log 2 112M F
, and

M ∞ ( , F, n) 2 16M 2 F n 2 d( 4 ) log 2 4M F en d( 4 ) . (9)
Proof Since ( 9) is simply an instance of Lemma 3.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF], we only prove [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF]. By definition,

∀t n = (t i ) 1 i n ∈ T n , M ( , F, d p,tn ) = M , F| tn , d p,tn ,
where F| tn is the set of the restrictions to t n of the functions in F. Let F be, among the subsets of F| tn -separated with respect to the pseudo-metric d p,tn , a set of maximal cardinality. By definition,

|F | = M , F| tn , d p,tn = M ( , F , d p,tn ) .
At this level, two cases must be considered.

First case Suppose that |F | exp K e (p) n 2p where K e is the function of p defined in Lemma 6. In that case, Lemma 6 applies, and we can set r equal to the smallest admissible value, ln(|F |) Ke(p) 2p , where ln is the Neperian (or natural) logarithm. Consequently, there exists a subvector t q of t n of size

q ln (|F |) K e (p) 2p (10)
such that F is

M 4 , F | tq , d p,tq = M   4 p -(η) p 1 p 2 , F | tq (η) , d p,tq   M -4η 8 , F | tq (η) , d p,tq ,
where the inequality stems from the fact that

min p∈N * 4 p -(η) p 1 p = 4 -η. For N ∈ N satisfying N > 56M F , let us set η = 2M F N . Since F | tq 2M F N
is a class of functions whose domain has cardinality q and whose codomain is 2M F j N : 0 j N , Lemma 9 provides us with

|F | 2 (p+2) log 2 (N )+1 e (N -1) q d 1 (p+2) log 2 (N )d 1
where

d 1 = 1 16 -56M F N -dim F | tq 2M F N
. Thus, making use of the upper bound on q provided by [START_REF] Boucheron | Concentration Inequalities, a Nonasymptotic Theory of Independence[END_REF],

|F | 2 (p+2) log 2 (N )+1 e (N -1) ln (|F |) K e (p) 2p d 1 (p+2) log 2 (N )d 1 2 (p+2) log 2 (N )+1 ln (|F |) d 1 (p+2) log 2 (N )d 1 e (N -1) K e (p) 2p (p+2) log 2 (N )d 1 . ( 11
)
function h 1 is positive on its domain and for all r ∈ N * , h r (1) > 0. Since for all r 2, h r (u) = r u h r-1 (u), proceeding by induction, one establishes that all the functions h r are positive on their domain. Furthermore, for all r ∈ N * , 2 r-1 r! r r . Consequently, setting K N,p = (p + 2) log 2 (N ) , where the ceiling function • is defined by: ∀u ∈ R, u = min {j ∈ Z : j u} , we obtain

ln (|F |) d 1 (p+2) log 2 (N )d 1 = ln (p+2) log 2 (N ) |F | 1 d 1 d 1 ln K N,p |F | 1 d 1 d 1 < K K N,p d 1 N,p |F | 1 2 . ( 12
)
A substitution of the right-hand side of ( 12) into [START_REF] Cortes | Support-vector networks[END_REF] gives

|F | 2 2(K N,p +1) e (N -1) K N,p K e (p) 2p 2K N,p d 1 .
To bound from above d 1 , N can be set equal to 112M F . Then,

d 1 32 -dim     F | tq   2M F 112M F       (13)
  32 - M F 112M F   -dim F | tq (14) 32 - 112 -dim F | tq 45 -dim (F) .
This sequence of computations makes use three times of the fact that the fat-shattering dimension is a nonincreasing function of the margin parameter. The transition from [START_REF] Doğan | A unified view on multi-class support vector classification[END_REF] to ( 14) is provided by Lemma 8. As a consequence,

|F | 2 2 (p+2) log 2 112M F +1   112eM F (p + 2) log 2 112M F K e (p) 2p+1   2 (p+2) log 2 112M F d( 45 )
.

A substitution into the right-hand side of the value of K e (p) produces for |F |, i.e., M ( , F, d p,tn ), the same upper bound as that announced for M p ( , F, n). Thus, to conclude the proof of (

By application of Lemma 7, for η ∈ (0, ),

|F | = M ( p -η p ) 1 p 2 , (F ) (η) , d p,tn M -η 2 , (F ) (η) , d p,tn . For N ∈ N satisfying N > 14M F , let us set η = 2M F N . Since (F ) 2M F N
is a class of functions whose domain has cardinality n and whose codomain is 2M F j N : 0 j N , Lemma 9 provides us with

|F | 2 (p+2) log 2 (N )+1 e (N -1) n d 2 (p+2) log 2 (N )d 2 where d 2 = 1 4 -14M F N -dim (F ) ( 2M F N )
. The substitution of the upper bound on n provided by [START_REF] Dudley | Uniform and universal Glivenko-Cantelli classes[END_REF] into this bound produces

|F | 2 2(K N,p +1) e (N -1) K N,p K e (p) 2p 2K N,p d 2 . (16)
To bound from above d 2 , N can be set equal to 28M F . Then, the line of reasoning used for d 1 leads to

d 2 12 -dim (F) .
By substitution into (16) of the value of N and this upper bound on d 2 , an upper bound on |F | is obtained which is smaller than that provided by Inequality (8).

Comparison with the state of the art

In order to limit the complexity of the formula corresponding to finite values of p (Inequality ( 8)), the constants have systematically been derived by considering the "worst" case: p = 1. This implies that better constants can be obtained by focusing on the value of p of interest. If the resulting gain is all the more important as this value is large, it is already noticeable for p = 2. The result that compares directly with Lemma 2 is Theorem 3.2 in [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF]. As Inequality [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF], the corresponding bound is dimension free. The main difference rests in the dependency on the fat-shattering dimension. Whereas Inequality (8) rem 3.2 in [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF] exhibits an additional logarithmic multiplicative factor. Focusing on results derived for a specific L p -norm, the literature provides us with one example of generalized Sauer-Shelah lemma based on the L 1 -norm: Lemma 1 in [START_REF] Bartlett | Covering numbers for real-valued function classes[END_REF] (whose basic combinatorial result is Lemma 8 in [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF]). However, this result is not dimension free (the growth rate of the -entropy with n is logarithmic). As for the L 2 -norm, the state of the art is provided by Theorem 1 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. Since its original formulation involves unspecified universal constants, to make comparison possible, it is given below with explicit constants.

Lemma 3 (After Theorem 1 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let F be a class of functions from

T into [-M F , M F ] with M F ∈ R * + . F is supposed to be a GC class. For ∈ (0, M F ], let d ( ) = -dim (F). Then for ∈ (0, 2M F ] and n ∈ N * , M 2 ( , F, n) 3584e 2M F 5 4d( 96 ) . ( 17
)
With this formulation at hand, it appears that even without optimizing the constants of Inequality (8) for the case p = 2, none of the two bounds is uniformly better than the other.

The choice between them should primarily be based on the behaviour of the fat-shattering dimensions of interest.

Bound based on the L ∞ -norm

The L ∞ -norm plays a central part in the theory of bounds. Indeed, one can consider that it is already at the core of the initial result of Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. Focusing on margin classifiers, it is the norm used in Bartlett's seminal article [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].

State of the art

To the best of our knowledge, the state-of-the-art result is precisely a multi-class extension of Bartlett's result: Theorem 40 in [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF]. It makes use of the same margin loss functions, defined as follows.

Definition 17 (Margin loss functions φ ∞,γ ) For γ ∈ (0, 1], the margin loss function φ ∞,γ is defined by:

∀t ∈ R, φ ∞,γ (t) = 1l {t<γ} .
The basic supremum inequality is a multi-class extension of Lemma 4 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], with the first symmetrization being derived from the basic lemma of Section 4.5.1 in [START_REF] Vapnik | Statistical Learning Theory[END_REF].

Theorem 1 (After Theorem 22 in [START_REF] Guermeur | VC theory of large margin multi-category classifiers[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 9. For a fixed γ ∈ (0, 1] and a fixed δ ∈ (0, 1), with P m -probability at least 1 -δ, uniformly for every function g ∈ G,

L (g) L γ,m (g) + 2 m ln N (p) ∞ γ 2 , F G,γ , 2m + ln 2 δ + 1 m , (18)
where the margin loss function defining the empirical margin risk is φ ∞,γ (Definition 17).

The pathway leading from this inequality to Theorem 40 in [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF] consists in relating the covering number of interest to a γ-Ψ-dimension (see Definition 28 in [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF]) of a class of vector-valued functions. The dependency on C varies with the choice of this dimension.

In the case of the dimension which is the easiest to bound from above (by application of the pigeonhole principle), the margin Natarajan dimension, it is superlinear.

Improved dependency on C

Instead of working with vector-valued functions as in [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF], it is more efficient to handle separately the classes of component functions. Starting from Inequality [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF] and applying in sequence Lemma 1 (for p = ∞), Lemma 5 and Lemma 2 (Lemma 3.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]) produces the master theorem in the uniform convergence norm.

Theorem 2 Let G be a class of functions satisfying Definition 3. For ∈ (0, M G ], let

d ( ) = max 1 k C -dim (G k ).
For a fixed γ ∈ (0, 1] and a fixed δ ∈ (0, 1), with P mprobability at least 1 -δ, uniformly for every function g ∈ G,

L (g) L γ,m (g) + 2 m 3Cd γ 8 ln 2 128M 2 G m γ 2 + ln 2 δ + 1 m .
Proof The sketch of the proof has been given at the beginning of the subsection. The detail makes use of the fact that

∀k ∈ [ [ 1, C ] ] , log 2 16M G em γ 8 -dim (G k ) γ 1 ln (2) ln 128M 2 G m γ 2 .
Thus,

L (g) L γ,m (g) + 2 m C k=1 ln N (p) ∞ γ 2 , G k , 2m + ln 2 δ + 1 m L γ,m (g) + 2 m 2 ln (2) ln 128M 2 G m γ 2 C k=1 γ 8 -dim (G k ) ln 16M G em γ 8 -dim (G k ) γ + ln 2 δ + 1 m L γ,m (g) + 2 m 3 ln 2 128M 2 G m γ 2 C k=1 γ 8 -dim (G k ) + ln 2 δ + 1 m L γ,m (g) + 2 m 3Cd γ 8 ln 2 128M 2 G m γ 2 + ln 2 δ + 1 m .

Discussion

Under the assumption that d ( ) does not depend on C, Theorem 2 provides a guaranteed risk whose control term varies with C and m as a O ln (m) C m . To sum up, the new bound exhibits the convergence rate of Theorem 40 in [START_REF] Guermeur | VC theory of large margin multi-category classifiers[END_REF], whereas its control term grows only as the square root of C. Note that Lemma 19 in [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF], which provides a bound with the same growth, holds for kernel multi-category classification methods only. We now establish an improvement of this kind with the L 2 -norm.

Bound based on the L 2 -norm

As in the case of the uniform convergence norm, the state-of-the-art result provides us not only with an element of comparison, but also with a starting point for the derivation of our guaranteed risk.

State of the art

The sharpest bound in the L 2 -norm is Theorem 3 in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]. The margin loss function involved in this result is a standard one, the parameterized truncated hinge loss (that satisfies both Definition 6 and the definition used by Koltchinskii and Panchenko in [21]).

Definition 18 (Parameterized truncated hinge loss φ 2,γ , Definition 4.3 in [START_REF] Mohri | Foundations of Machine Learning[END_REF]) For γ ∈ (0, 1], the parameterized truncated hinge loss φ 2,γ is defined by:

∀t ∈ R, φ 2,γ (t) = 1l {t 0} + 1 - t γ 1l {t∈(0,γ]} .
This guaranteed risk is built upon a basic supremum inequality which is a partial result in the proof of Theorem 8.1 in [START_REF] Mohri | Foundations of Machine Learning[END_REF] (with F G replaced with F G,γ ).

Theorem 3 (After Theorem 8.1 in [START_REF] Mohri | Foundations of Machine Learning[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 9. For a fixed γ ∈ (0, 1] and a fixed δ ∈ (0, 1), with P m -probability at least 1 -δ, uniformly for every function g ∈ G,

L (g) L γ,m (g) + 2 γ R m (F G,γ ) + ln 1 δ 2m
where the margin loss function defining the empirical margin risk is the parameterized truncated hinge loss (Definition 18).

Theorem 3 in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF] stems from Theorem 3 by application of the following lemma.

Lemma 4 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 9. Then

R m (F G,γ ) CR m C k=1 G k . ( 19
)
Many margin classifiers, including neural networks and kernel machines, satisfy the additional property that all the classes of component functions are identical, so that the growth with C of the upper bound on R m (F G,γ ) provided by ( 19) is linear. Furthermore, if the classifier is specifically a kernel machine, then it is well known that by combining the reproducing property with the Cauchy-Schwarz inequality, it is possible to obtain an upper bound on the Rademacher complexity which is a O m -1 2 (see for instance Lemma 22 in [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF]). Thus, for kernel machines, the control term of Kuznetsov's bound is a O C √ m . Kernel machines (with bounded range) satisfy Definition 3. This is easy to establish thanks to the characterization of the GC classes provided by Theorem 2.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]. The finiteness of the γ-dimension of a linear separator in a reproducing kernel Hilbert space is a well-known result, which appears, for instance, as a consequence of Theorem 4.6 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF]. To sum up, the state-of-the-art result is a guaranteed risk whose control term is at best a O C √ m , for a specific family of classifiers among those satisfying Definition 3.

Improved dependency on C

Several results are available to bound from above the expected suprema of empirical processes (see for instance Chapters 1, 2, and 6 of [START_REF] Massart | Concentration Inequalities and Model Selection: Ecole d'Eté de Probabilités de Saint-Flour XXXIII -2003[END_REF]). We resort to the standard approach, especially efficient in the case of Rademacher processes, the application of Dudley's chaining method [START_REF] Dudley | The sizes of compact subsets of Hilbert space and continuity of Gaussian processes[END_REF].

Theorem 4 (Chained bound on the Rademacher complexity of F G,γ ) 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 9. For ∈ (0,

M G ], let d ( ) = max 1 k C -dim (G k ).
Let h be a positive and decreasing function on N such that h (0) γ and h (1

) 2M G √ C.
Then for all

N ∈ N * , R m (F G,γ ) h (N ) + 4 5C m N j=1 (h (j) + h (j -1)) d h (j) 96 √ C ln 14M G √ C h (j) . (20)
Proof The initial part of the proof of Formula ( 20) is the application of Theorem 6. Note that diam (F G,γ ) γ, justifying the hypothesis on h (0). An advantage of working with F G,γ instead of F G (directly) has thus been highlighted. The end of the proof consists in applying in sequence Lemma 1 (for p = 2), Lemma 5 and Lemma 3 (with = h(j) √ C and 3584e bounded from above by 7 5 ).

Thanks to the choice h (j) = 2 -j √ Cγ, under the assumption that d ( ) does not depend on C, then Theorem 4 provides a guaranteed risk whose control term grows linearly with C, a dependency at least as good as that of Theorem 3 in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]. The improvement announced results from substituting to the hypothesis of GC classes a slightly stronger one.

Hypothesis 1 We consider classes of functions G satisfying Definition 3 plus the fact that there exists a pair

(d G , K G ) ∈ N * × R * + such that ∀ ∈ (0, M G ] , max 1 k C -dim (G k ) K G -d G . (21)
If Hypothesis 1 is satisfied, then the classes G k are universal Donsker classes [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF]. Theorem 4.6 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF] tells us that it is the case, with d G = 2, if each of the classes G k corresponds to the class of functions computed by a support vector machine (SVM) [START_REF] Cortes | Support-vector networks[END_REF]. As a consequence, this is the case (with d G = 2) if G is the class of functions computed by a multi-class SVM [START_REF] Guermeur | A generic model of multi-class support vector machine[END_REF][START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF][START_REF] Doğan | A unified view on multi-class support vector classification[END_REF].

Theorem 5 Let G be a class of functions satisfying Hypothesis 1. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 9.

If d G = 1, then R m (F G,γ ) 160 30K G γ m C 3 4 ln (F (C)) 2 + π 8 F (C) 1 -erf ln (F (C)) , (22)
where

F (C) = 2 14M G γ C 1 4
and erf stands for the error function, i.e., erf

(t) = 2 √ π t 0 e -u 2 du. If d G = 2, then R m (F G,γ ) γC 3 4 √ m + 1152 5K G m C 1 2 log 2 m C ln 14M G √ m γC 1 4 . At last, if d G > 2, then R m (F G,γ ) √ C γ C m 1 d G + 8 • 96 d G 2 2 2 d G -2 + 1 • γ 1-d G 2 5K G C m 1 d G ln 14M G γ m C 1 d G . (23)
Proof A substitution of Inequality (21) into Inequality [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF] provides:

R m (F G,γ ) h (N ) + 4 • 96 d G 2 5K G m C d G +2 4 N j=1 h (j) + h (j -1) h (j) d G 2 ln 14M G √ C h (j) . (24)
At this point, we distinguish three cases according to the value taken by d G .

First case: d G = 1 This case is the only one for which the entropy integral of Formula (29) exists. Setting for all j ∈ N,

h (j) = γ • 2 -2j , we obtain R m (F G,γ ) 160 30K G γ m C 3 4 1 2 0 ln 14M G √ C γ 2 d . (25)
The computation of the integral gives

1 2 0 ln 14M G √ C γ 2 d = ln (F (C)) 2 + F (C) √ 2 √ π 2 1 -erf ln (F (C)) . (26)
Inequality [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF] then results from a substitution of the right-hand side of ( 26) into [START_REF] Massart | Some applications of concentration inequalities to statistics[END_REF].

R m (F G,γ ) h (N ) + 384 5K G m C N j=1 h (j) + h (j -1) h (j) ln 14M G √ C h (j)
.

For N = 1 2 log 2 m C
, we set h (j) = γC > γ, and h (0) < 2γC

1 4 < 2M G √ C. Then, R m (F G,γ ) γC 3 4 √ m + 1152 5K G m C N j=1 ln 14M G √ m • 2 j-N γC 1 4 γC 3 4 √ m + 1152 5K G m C 1 2 log 2 m C ln 14M G √ m γC 1 4
.

Third case: d G > 2 For N = d G -2 2d G log 2 m C
, let us set h (j) = γC

1 2 + 1 d G m -1 d G 2 2 d G -2 (-j+N ) .
Obviously, the constraints on N and the function h are once more satisfied. By substitution into [START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF], we get:

R m (F G,γ ) √ C γ C m 1 d G + 4 • 96 d G 2 • γ 1-d G 2 5K G C m 1 d G ln 14M G γ m C 1 d G S N (27)
with

S N = N j=1 2 2 d G -2 (-j+N ) + 2 2 d G -2 (-j+1+N ) 2 d G d G -2 (-j+N )
. Now,

S N = 2 2 d G -2 + 1 N j=1 2 j-N < 2 2 2 d G -2 + 1 .
Inequality [START_REF] Kuznetsov | Multi-class deep boosting[END_REF] results from a substitution of this upper bound on S N into (27).

Discussion

The implementation of Dudley's chaining method under Hypothesis 1 highlights the phase transition already identified by Mendelson in [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF] (see also [START_REF] Mendelson | Geometric methods in the analysis of Glivenko-Cantelli classes[END_REF]). Besides this well-known phenomenon regarding the convergence rate, a parallel one can be noticed regarding the dependency on C. Indeed, if this dependency is always sublinear, as announced, it varies significantly between √ C and C, as a function of the value of d G . Its asymptotic value is √ C. It is noteworthy that the behaviours observed are highly sensitive to the choice of the function h. We have already noticed in the beginning of the section that setting h (j) = 2 -j √ Cγ has for consequence that the dependency on C is uniformly linear. Another example is instructive. In the case Our current work consists in continuing the unification of the approaches used to derive the bounds with respect to the different L p -norms. The aim is to make the comparison of the resulting guaranteed risks more straightforward, as a step towards the characterization of the intrinsic complexity of the computation of polytomies. We also look for improvements resulting from the use of new tools from the theory of empirical processes. In that respect, the recent developments of the implementation of the chaining method appear promising.

d G = 1, choosing h (j) = γ • 2 -j leads to R m (F G,γ ) 96 30K G m C γ 2 √ C 0 1 ln 14M G d .
Our results have been established under minimal assumptions regarding the pattern classification problem, the classifier and the margin loss function. Our future work will consist in assessing the benefit that one can derive from this study under different assumptions, such as those made in [START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF].

A Basic results and technical lemmas

Our formulation of Dudley's metric entropy bound, tailored for our needs, generalizes that established in transcripts of Bartlett's lectures which can be found online (see also [START_REF] Audibert | Combining PAC-Bayesian and generic chaining bounds[END_REF]).

The integral inequality appears as an instance of Corollary 13.2 in [START_REF] Boucheron | Concentration Inequalities, a Nonasymptotic Theory of Independence[END_REF].

Theorem 6 (Dudley's metric entropy bound) Let F be a class of bounded real-valued functions on T . For n ∈ N * , let t n = (t i ) 1 i n ∈ T n and let diam

(F) = sup (f,f )∈F 2 f -f L 2 (µ tn )
be the diameter of F in the L 2 (µ tn ) seminorm. Let h be a positive and decreasing function on N such that h (0) diam (F). Then for N ∈ N * ,

Rn (F) h (N ) + 2 N j=1 (h (j) + h (j -1)) ln N (p) (h (j) , F, d 2,tn ) n ( 28
)
and

Rn (F) 12 1 2 •diam(F ) 0 ln N (p) ( , F, d 2,tn ) n d . ( 29
)
Proof For j ∈ N * , let Fj be a proper h (j)-net of F with respect to d 2,tn such that Fj = N (p) (h (j) , F, d 2,tn ). We set F0 = f0 where f0 is any function in F. Note that since h (0) can be equal to diam (F), the construction of F0 does not ensure that this set is a proper h (0)-net of F with respect to d 2,tn (the minimum cardinality of such a net can be superior or equal to 2). The Rademacher process underlying the Rademacher complexity is centered, i.e.,

∀f ∈ F, E σn 1 √ n n i=1 σ i f (t i ) = 0.
Thus,

Rn (F) = E σn sup f ∈F 1 n n i=1 σ i f (t i ) -f0 (t i ) .
For each f ∈ F and each j ∈ N * , choose fj ∈ Fj such that f -fj L 2 (µ tn ) < h (j). Notice that

f -f0 = f -fN + N j=1 fj -fj-1 .
As a consequence, making use of the sub-additivity of the supremum function provides us with:

Rn (F) E σn sup f ∈F 1 n n i=1 σ i f (t i ) -fN (t i ) + N j=1 E σn sup f ∈F 1 n n i=1 σ i fj (t i ) -fj-1 (t i ) . (30)
To bound from above the first term of the right-hand side of (30), we can make use in sequence of the Cauchy-Schwarz inequality and the definition of h.

E σn sup f ∈F 1 n n i=1 σ i f (t i ) -fN (t i ) E σn   sup f ∈F    1 n n i=1 σ 2 i 1 2 1 n n i=1 f (t i ) -fN (t i ) 2 1 2      sup f ∈F f -fN L 2 (µ tn ) E σn   1 n n i=1 σ 2 i 1 2   < h (N ) . (31)
As for the second term of the right-hand side of (30), we make use of Massart's finite class lemma (Lemma 5.2 in [START_REF] Massart | Some applications of concentration inequalities to statistics[END_REF]). This calls for the derivation of an upper bound on

1 n fj (t i ) -fj-1 (t i ) 1 i n 2 = 1 √ n fj -fj-1 L 2 (µ tn ) for all j ∈ [ [ 1, N ]
]. This upper bound is obtained by application of Minkowski's inequality:

fj -fj-1 L 2 (µ tn ) = fj -f + f -fj-1 L 2 (µ tn ) fj -f L 2 (µ tn ) + f -fj-1 L 2 (µ tn ) < h (j) + h (j -1) . (32)
We can check that (32) still holds for j = 1 since

     f1 -f L 2 (µ tn ) < h (1) f -f0 L 2 (µ tn ) diam (F) h (0) =⇒ f1 -f L 2 (µ tn ) + f -f0 L 2 (µ tn ) < h (1)+h (0) .
Applying Lemma 5.2 in [START_REF] Massart | Some applications of concentration inequalities to statistics[END_REF] with [START_REF] Talagrand | The Generic Chaining: Upper and Lower Bounds of Stochastic Processes[END_REF] gives:

∀j ∈ [ [ 1, N ] ] , E σn sup f ∈F 1 n n i=1 σ i fj (t i ) -fj-1 (t i ) h (j) + h (j -1) √ n 2 ln Fj Fj-1 2 (h (j) + h (j -1)) ln Fj n . (33)
The substitution of ( 31) and ( 33) into (30) produces [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF]. Furthermore, setting for all j ∈ N, h (j) = 2 -j • diam (F), gives:

Rn (F) diam (F)   2 -N + 6 N j=1 2 -j ln N (p) (2 -j • diam (F) , F, d 2,tn ) n   diam (F)   2 -N + 12 N j=1 2 -j -2 -(j+1) ln N (p) (2 -j • diam (F) , F, d 2,tn ) n   (34) 2 -N • diam (F) + 12 1 2 •diam(F ) 1 2 N +1 •diam(F ) ln N (p) ( , F, d 2,tn ) n d . (35)
Inequality [START_REF] Williamson | Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators[END_REF] springs from Inequality (34) since a covering number is a nonincreasing function of (on the interval 2 29) is simply the asymptotic formulation of Inequality [START_REF] Williamson | Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators[END_REF] (for N going to infinity).

-(j+1) • diam (F) , 2 -j • diam (F) , N (p) 2 -j • diam (F) , F, d 2,tn N (p) ( , F, d 2,tn )). Inequality (
Lemma 5 (After Theorem IV in [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF]) Let (E, ρ) be a pseudo-metric space. For every totally bounded set E ⊂ E and ∈ R * + ,

N (p) , E , ρ M , E , ρ .
Lemma 6 (After Lemma 13 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) Let T = {t i : 1 i n} be a finite set and t n =

(t i ) 1 i n . Let F be a finite class of functions from T into [-M F , M F ] with M F ∈ R * + . Let p ∈ N * . Assume that for some ∈ (0, 2M F ], F is -separated with respect to the pseudo-metric d p,tn . If r ∈ [1, n] is such that |F| exp K e (p) r 2p with K e (p) = 3 112 (2M F ) 2p ,
then there exists a subvector t q of t n of size q r such that F is

F = f j -f j : 1 j < j |F| . The set D F has cardinality |D F | < 1 2 |F| 2 . Fix r ∈ [1, n]
satisfying the assumptions of the lemma and let ( i ) 1 i n be a sequence of n independent Bernoulli random variables with common expectation µ = r 2n . Then, by application of the -separation property, for every

δ f in D F , P 1 n n i=1 i |δ f (t i )| p < µ 2 p P 1 n n i=1 (µ -i ) |δ f (t i )| p > 1 - 1 2 p µ p P 1 n n i=1 (µ -i ) |δ f (t i )| p > 1 2 µ p . (36)
Since by construction, for all

i ∈ [ [ 1, n ] ], E [(µ -i ) |δ f (t i )| p ] = 0 and |µ -i | |δ f (t i )| p (2M F ) p (1 -µ) < (2M F
) p with probability one, the right-hand side of (36) can be bounded from above thanks to Bernstein's inequality [START_REF] Bernstein | The Theory of Probabilities[END_REF]. Given that This translates into the fact that there exists a subvector t q of t n of size q r such that the class F is

1 n n i=1 E (µ -i ) 2 δ f (t i ) 2p (2M F ) 2p µ (1 -µ) < (2M F ) 2p µ,
1 2 p+1 p
-separated with respect to the pseudo-metric d p,tq , i.e., our claim.

Lemma 7 Let F be a class of functions from T into [-M F , M F ] with M F ∈ R * + . For n ∈ N * , let t n = (t i ) 1 i n ∈ T n . For all ∈ (0, 2M F ], all η ∈ (0, ), and all p ∈ N * , if a subset of F is -separated in the pseudo-metric d p,tn , then the η-discretization operator acts on it as an injective mapping and the image obtained is a set ( p -η p ) To sum up, we have established (39), i.e., the lemma.

Lemma 8 Let F be a class of functions from T into [-M F , M F ] with M F ∈ R * + . For all ∈ (0, M F ] and all η ∈ (0, 2 ),

-dim F (η) - η 2 -dim (F) .
Proof To prove Lemma 8, it suffices to notice that

f (η) (t) -b =⇒ η f (t) + M F η -b =⇒ f (t) + M F -b =⇒ f (t) -b + η 2 -M F - η 2
and

f (η) (t) -b -=⇒ η f (t) + M F η -b - =⇒ f (t) + M F -η -b - =⇒ f (t) -b + η 2 -M F -- η 2 .
In the framework of this study, the main combinatorial result evoqued in Section 2.2 is the following lemma, which extends Lemma 8 in [START_REF] Bartlett | More theorems about scale-sensitive dimensions and learning[END_REF].

Proof First, note that

     d 1 M ( , F, d p,tn ) 2 =⇒      ∈ 6M F N , 2M F + 6M F N ∈ (0, 2M F ] =⇒      ∈ 6M F N , 2M F N > 3 . For q ∈ [ [ 1, d ]
], let the pair (s T q , b q ) be such that s T q is a subset of T of cardinality q and b q ∈ (S \ {0, 2M F }) q . Such a pair will be said to be γ-shattered by a subset of

- 2 p+1 p = 1 4 , 4 -

 244 separated with respect to the pseudo-metric d p,tq , and thus, since min p∈N * 1 separated with respect to the same pseudo-metric. As a consequence,|F | = M 4 , F , d p,tq = M 4 , F | tq , d p,tq = F | tq . For η ∈ 0, 4 , let F | tq (η)be the image of F | tq by the discretization operator (•) η .Since F | tq = M 4 , F | tq , d p,tq , by application of Lemma 7,

3 4 m -1 2 2

 32 -j+N . Note that these choices are feasible since N ∈ N * due to m > C, h (0) γC 1 4

6

  Conclusions and ongoing research An L p -norm Sauer-Shelah lemma dedicated to margin multi-category classifiers whose classes of component functions are uniform Glivenko-Cantelli classes has been established. Its use makes it possible to improve the dependency on the number C of categories of the state-of-the-art guaranteed risks based on the L ∞ -norm and the L 2 -norm. In both cases, this dependency becomes sublinear. Furthermore, in the favourable cases, the confidence interval can grow with C as slowly as a O √ C .

  the pseudo-metric d p,tq . Proof Let us set F = {f j : 1 j |F|} and D

ii 2 pi∧

 2 |δ f (t i )| p < µ 2 2M F ) 2p + (2M F ) p p   exp -3r 2p 56 (2M F ) 2p exp -2K e (p) r 2p .Therefore, given the assumption on r, applying the union bound provides us with:|δ f (t i )| p < µ |D F | • exp -2K e (p) r 2p < 1 2 exp 2 K e (p) r 2p • exp -2K e (p) r 2p S 1 is the random set {i ∈ [ [ 1, n ] ] : i = 1},then by Markov's inequality, P (|S 1 | > r) = P and (38) by means of the union bound provides us with P |δ f (t i )| p (|S 1 | r) > 0.

1 p 2 -p 2 , 2 ( p -η p ) 1 p 2 .

 12222 separated in the same pseudo-metric. As a consequence,∀p ∈ N * , M ( , F, d p,tn ) M ( p -η p ) 1 F (η) , d p,tn .Proof Proving Lemma 7 amounts to establishing that∀ (f 1 , f 2 ) ∈ F 2 , (d p,tn (f 1 , f 2 ) ) ∧ (η ∈ (0, )) =⇒ d p,tn f (39) For i ∈ [ [ 1, n ] ], let δ i = f

2 (

 2 i ) and δ i = f 1 (t i ) -f 2 (t i ) -δ i . By construction, there exists N i ∈ N such that |δ i | = ηN i , and |δ i | < η. If N i > 0, then |δ i | + |δ i | < 2 |δ i |, otherwise |δ i | + |δ i | < η, with the consequence that in all cases, (|δ i | + |δ i |) p < (2 |δ i |) p + η p . Thus, (d p,tn (f 1 , f 2 ) ) ∧ (η ∈ (0p -η p ) 1 p 2 .

Lemma 9

 9 Let T = {t i : 1 i n} be a finite set and t n = (t i ) 1 i n . Let F be a class offunctions from T into S = 2M F j N : 0 j N with M F ∈ R * + and N ∈ N \ [ [ 0, 3 ] ]. For ∈ 6M F N , 2M F , let d = 2 -3M F N -dim (F). Then ∀p ∈ N * , M ( , F, d p,tn ) < 2 (p+2) log 2 (N )+1 e (N -1) n d (p+2) log 2 (N )d.

  let Ḡk be a proper -net of G k with respect to the pseudo-metric d p,xm such that Ḡk is of cardinality N (p) ( , G k , d p,xm ). By construction, the cardinality of the class of functions Ḡ = C k=1 Ḡk is C k=1 N (p) ( , G k , d p,xm ), and for every function

  Second case Suppose conversely that |F | > exp K e (p) n 2p , i.e.,

	n <	ln (|F |) K

[START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF]

under the assumption that |F | exp K e (p) n 2p , it suffices to notice that this upper bound does not depend on t n (it is even dimension free). e (p) 2p .

-ln r (u). The

Acknowledgements The author would like to thank R. Vershynin for his explanations on the proof of Theorem 1 in [29] and A. Kontorovich for bringing to his attention the bounds in [30]. Thanks are also due to F. Lauer and K. Musayeva for carefully reading this manuscript. This work was partly funded by a CNRS research grant.

F if s T q is γ-shattered by this subset and b q is a witness to this shattering. Setting K = d j=0 n j (N -1) j , the number of such pairs is equal to d j=1 n j (N -1) j , i.e., to K -1. Fix ∈ 6M F N , 2M F and p ∈ N * . For each r ∈ [ [ 2, M ( , F, d p,tn ) ] ], let shat (r) be the maximum integer such that any subset of F of cardinality r which is -separated in the metric d p,tn 2 -3M F N -shatters at least shat (r) pairs (s T q , b q ). Obviously, the function shat is nondecreasing. We now establish that shat (2) 1. Indeed, let {f + , f -} be a subset of F -separated in the metric d p,tn . By definition,

, with the consequence that there exists

out loss of generality, we make the hypothesis that f

] and let F be a subset of F of cardinality r -separated in the metric d p,tn . Split F arbitrarily into r 2 pairs. For each such pair

29

Then

Thus, each pair

Applying the pigeonhole principle, there is at least one index i 0 such that at least rn

N , it is easy to establish that there are less than

Thus, applying once more the pigeonhole principle, there are at least

and the pair

) is the same. This implies that there is a quintuplet i 0 , s + , s -, F+ , F-

N , F+ and Fare two subsets of F of cardinality at least r N p+2 , and for each (f + , f -) ∈ F+ × F-, the ordered pairs (f + (t i 0 ) , f -(t i 0 )) and (s + , s -) are identical. Obviously, any two functions in F+ areseparated in the metric d p,tn , and the same holds true for F-. So, by definition, both

shattered by both sets, then the pair s T q+1 , b q+1 where s T q+1 = {t i 0 } s T q and b q+1 = b 0 b T q T is the vector deduced from b q by adding one component b 0 corresponding to 30 the point

Summarizing, for each pair (s T q , b q ) 2 -3M M ( , F, d p,tn ), shat 2N (p+2)u 2 u . Suppose now that we can set u = log 2 (K) . We

However, the number of pairs (s T q , b q ) that can be 2 -3M F N -shattered is trivially bounded from above by the total number of those pairs, i.e., K -1. We have thus established by contradiction that 2N (p+2) log 2 (K) > M ( , F, d p,tn ) . , and the last inequality is precisely Inequality (40).