Yann Guermeur
email: yann.guermeur@loria.fr

Combinatorial and Structural Results for γ-Ψ-dimensions

Keywords: margin multi-category classiers, guaranteed risks, scale-sensitive combinatorial dimensions, γ-Ψ-dimensions Mathematics Subject Classication: 68Q32, 62H30

This article deals with the generalization performance of margin multi-category classiers, when minimal learnability hypotheses are made. In that context, the derivation of a guaranteed risk is based on the handling of capacity measures belonging to three main families: Rademacher/Gaussian complexities, metric entropies and scale-sensitive combinatorial dimensions. The scale-sensitive combinatorial dimensions dedicated to the classiers of this kind are the γ-Ψ-dimensions. We introduce the combinatorial and structural results needed to involve them in the derivation of guaranteed risks and establish the corresponding upper bounds on the metric entropies and the Rademacher complexity. Two major conclusions can be drawn:

1. the γ-Ψ-dimensions always bring an improvement compared to the use of the fat-shattering dimension of the class of margin functions; 2. thanks to their capacity to take into account basic features of the classier, they represent a promising alternative to performing the transition from the multiclass case to the binary one with covering numbers.

Introduction

One of the main open problems of the theory of margin multi-category pattern classication is the characterization of the way the condence interval of an upper bound on the probability of error should vary as a function of the three basic parameters which are the sample size m, the number C of categories and the margin parameter γ (see [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF], for a survey). When working under minimal learnability hypotheses, the derivation of such a guaranteed risk is based on the handling of capacity measures belonging to three main families: Rademacher/Gaussian complexities [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF], metric entropies [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF] and scale-sensitive combinatorial dimensions [START_REF] Kearns | Ecient distribution-free learning of probabilistic concepts[END_REF]. The scale-sensitive combinatorial dimensions dedicated to the classiers of interest are the γ-Ψ-dimensions [START_REF] Guermeur | VC theory of large margin multi-category classiers[END_REF]. Their usefulness to derive guaranteed risks rests on the availability of two types of results. Combinatorial results [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF][START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF][START_REF] Rudelson | Combinatorics of random processes and sections of convex bodies[END_REF][START_REF] Musayeva | Rademacher complexity and generalization performance of multi-category margin classiers[END_REF] connect them to metric entropies. Structural results [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF][START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF][START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classiers[END_REF] perform the transition from the multi-class case to the bi-class one. This article introduces such results for the two main γ-Ψ-dimensions and incorporate them in the derivation of upper bounds on the metric entropies and the Rademacher complexity. The dependence of the resulting guaranteed risks on m, C and γ is characterized. This establishes that in the theoretical framework of interest, introducing γ-Ψ-dimensions always brings an improvement compared to the use of the fat-shattering dimension of the class of margin functions. Furthermore, the margin Natarajan dimension appears very promising to take into account basic features of the classier. In practice, for many popular classiers, applying a structural result to this capacity measure rather than to covering numbers should improve the condence interval, primarily in its dependence on γ.

The organization of the paper is as follows. Section 2 introduces the theoretical framework. Section 3 highlights the need for new tools to improve the multi-class bounds. Section 4 establishes that switching from the fat-shattering dimension of the class of margin functions to the γ-Ψ-dimensions of the same class improves the combinatorial results. Sections 5 and 6 introduce and discuss the new combinatorial and structural results dedicated to these dimensions. The corresponding bounds on the metric entropies and guaranteed risks are derived in Section 7. At last, we draw conclusions in Section 8. To make reading easier, all technical lemmas and proofs have been gathered in appendix.

Margin Multi-category Classiers

We work under minimal assumptions on the data and the classiers, which exhibit one important feature: for each description, they return one score per category.

Theoretical Framework

Let n -; n + denote the set of integers ranging from n -to n + . We consider the case of Ccategory pattern classication problems with C ∈ N \ 0; 2 . X is the description space and Y = 1; C the set of categories. Their connection is utterly characterized by an unknown probability measure P . Let Z = (X, Y ) be a random pair with values in Z = X × Y, distributed according to P . We are given 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 classiers are based on classes of vector-valued functions with one component function per category. We add a basic learnability hypothesis: the classes of component functions are uniform Glivenko-Cantelli (uGC) [START_REF] Dudley | Uniform and universal Glivenko-Cantelli classes[END_REF]. Those classes must be uniformly bounded up to additive constants. We replace this property by a slightly stronger one: the vector-valued functions take their values in a hypercube of R C . To sum up, we make minimal hypotheses to ensure that all capacity measures met in the sequel are nite (none of the bounds formulated is trivial).

Denition 1 (Margin classier). Let G ⊂ C k=1 G k be a class of functions from X into [-M G , M G ] C with M G ∈ [1, +∞). The classes G k of component functions are supposed to be uGC classes. For each g = (g k ) 1 k C ∈ G, a margin multi-category classier on X is obtained by application of the decision rule dr from G into ∈ (Y { * }) X . This classier, dr g , returns either the index of the component function whose value is the highest, or the dummy category * in case of ex aequo.

The generalization capabilities of such classiers can be characterized by means of the values taken by the dierences of the component functions. This calls for the introduction of the class of margin functions, margin loss functions and the corresponding margin risks.

Denition 2 (Class ρ G of margin functions). Let G be a function class satisfying Definition 1. For every g ∈ G, the margin function ρ g from Z into [-M G , M G ] is dened by: ∀ (x, k) ∈ Z, ρ g (x, k) = 1 2 (g k (x) -max l =k g l (x)). Then, ρ G is dened as: ρ G = {ρ g : g ∈ G}.

The risk of g ∈ G is given by: L (g) = E (X,Y )∼P 1 {ρg(X,Y ) 0} = P (dr g (X) = Y ).

Denition 3 (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:      ∀γ ∈ (0, 1] , φ γ (0) = 1 and φ γ (γ) = 0 ∀ (γ, γ ) ∈ (0, 1] 2 , γ < γ =⇒ φ γ majorizes φ γ .

Given φ γ , the risk with margin γ of g, L γ (g), is dened as:

L γ (g) = E Z∼P [φ γ • ρ g (Z)].
L γ,m (g) designates the corresponding empirical risk, measured on Z m . When using φ γ , the behavior of the margin functions outside the interval [0, γ] is irrelevant to characterize the generalization performance. The idea to exploit this property by means of a squashing function can be traced back to [START_REF] Bartlett | The sample complexity of pattern classication with neural networks: The size of the weights is more important than the size of the network[END_REF]. The present study uses the function π γ .

Denition 4 (Squashing function π γ ). For γ ∈ (0, 1], the piecewise-linear squashing function π γ is dened by: ∀t ∈ R, π γ (t) = t1 {t∈(0,γ]} + γ1 {t>γ} . Thus, when possible, we replace the class ρ G with the class ρ G,γ .

Denition 5 (Class ρ G,γ of squashed margin functions). Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For every pair (g, γ) ∈ G × (0, 1], the function ρ g,γ from Z into [0, γ] is dened by: ρ g,γ = π γ • ρ g .

Then, the class ρ G,γ is dened as follows: ρ G,γ = {ρ g,γ : g ∈ G}.

The introduction of ρ G,γ , whose capacity is always bounded from above by that of ρ G (see Section 3.1), can narrow the condence interval of the guaranteed risk without aecting its data-t term (since ∀γ ∈ (0, 1] , φ γ • π γ = φ γ ). Thus, making the best of it is a major challenge.

Guaranteed Risks

In the theoretical framework of interest, the starting point of the derivation of a guaranteed risk is a supremum inequality taking the form:

P m sup g∈G (L * (g) -L γ,m (g)) > F i (m, γ, δ, cap (ρ G,γ )) δ, (1)
where L * is either L or L γ and the capacity measure cap (ρ G,γ ) involved in the expression of the function F i depends on the choice of φ γ . Then, the problem consists in upper bounding cap (ρ G,γ ) as a function of the basic parameters m, C and γ, so that eventually, with probability 1 -δ, the supremum of the empirical process of interest is bounded from above by a function F f of m, C, γ and δ only, i.e.,

sup g∈G (L * (g) -L γ,m (g)) F f (m, C, γ, δ) .
We introduce the three types of capacity measures considered in this study, using the notations of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classiers[END_REF]. Let (T , A T ) be a measurable space and let F ⊂ R T . Let T be a random variable with values in T , distributed according to a probability measure on (T , A T ) and let T n = (T i ) 1 i n be an n-sample made up of independent copies of T . The empirical Rademacher complexity of F given T n is denoted by Rn (F) and the Rademacher complexity of F is denoted by R n (F). The classes F considered here are endowed with empirical (pseudo-)metrics derived from the L p -norms. For n ∈ N * , let t n = (t i ) i.e., scale-sensitive extensions of the Ψ-dimensions [START_REF] Ben-David | Characterizations of learnability for classes of {0, . . . , n}-valued functions[END_REF].

1 i n ∈ T n . Then, ∀ (f, f ) ∈ F 2 , ∀p ∈ [1, +∞), 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 )|. Let F be a subset of F. For ∈ R * + , n ∈ N * and p ∈ [1, +∞], N , F, d p,
Denition 6 (γ-Ψ-dimensions, Denition 28 in [START_REF] Guermeur | VC theory of large margin multi-category classiers[END_REF]. Let F ⊂ R Z be such that:

∀f ∈ F, ∀x ∈ X , max 1 k<l C {f (x, k) + f (x, l)} = 0. Let Ψ be a family of mappings from Y into {-1, 0, 1}. For γ ∈ R * + , a subset s Z n = {z i = (x i , y i ) : 1 i n} of Z is said to be γ-Ψ-shattered by F if there is a vector ψ n = ψ (i) 1 i n ∈ Ψ n satisfying ψ (i) (y i ) 1 i n = 1 n , and a vector b n = (b i ) 1 i n ∈ R n + such that, for every vector s n = (s i ) 1 i n ∈ {-1, 1} n , there is a function f sn ∈ F satisfying ∀i ∈ 1; n , s i s i max {k: ψ (i) (k)=s i} f sn (x i , k) -b i γ.
(

) 2
The γ-Ψ-dimension of F, denoted by γ-Ψ-dim (F), is the maximal cardinality of a subset of Z γ-Ψ-shattered by F, if such maximum exists. Otherwise, F is said to have innite γ-Ψ-dimension.

Remark 1. Let us consider the degenerate case C = 2. Then, s i max {k:

ψ (i) (k)=s i} f sn (x i , k) = f sn (z i ), so that Formula (2) reduces to ∀i ∈ 1; n , s i (f sn (z i ) -b i ) γ,
and thus Denition 6 reduces to the denition of the main scale-sensitive combinatorial dimension, the fat-shattering or γ-dimension γ-dim [START_REF] Kearns | Ecient distribution-free learning of probabilistic concepts[END_REF], with a restricted domain for vector b n . Furthermore, if we dene the function class F 1 on X as follows:

F 1 = {f (•, 1) : f ∈ F}, then ∀γ ∈ R * + , γ-dim (F 1 ) = γ-dim (F) ,
provided that the denition of γ-dim (F 1 ) is the standard one (requiring only that b n ∈ R n ).

Thus, in the bi-class case, the constraint b n ∈ R n + of Denition 6 establishes the equivalence of the two denitions of the fat-shattering dimension, for the function class on Z (classier with two outputs) and the one on X (classier with one single output).

Denition 6 and Remark 1 suggest to adopt the following convention. The denition of any scale-sensitive combinatorial dimension of a class of functions with domain Z includes the restriction b n ∈ R n + . On the contrary, when the domain is X , then the standard hypothesis b n ∈ R n applies. The relevance of this choice will appear gradually (sometimes implicitly) in the sequel.

Denition 7 (Margin Graph dimension and margin Natarajan dimension). Let F be a function class dened as in Denition 6 and let γ ∈ R * + . The Graph dimension with margin γ of F, denoted by γ-G-dim (F), is the γ-Ψ-dimension of F corresponding to the following choice for Ψ:

Ψ G = ψ k : y → 1 {y=k} -1 {y =k} : k ∈ Y .
The Natarajan dimension with margin γ of F, denoted by γ-N-dim (F), is the γ-Ψdimension of F corresponding to the following choice for Ψ:

Ψ N = ψ k,l : y → 1 {y=k} -1 {y=l} : {k, l} ⊂ Y .
Remark 2. The instantiation of (2) associated with the margin Graph dimension is ob-

tained by setting ψ n = (ψ y i ) 1 i n so that ∀i ∈ 1; n ,      if s i = 1, f sn (x i , y i ) -b i γ if s i = -1, max k =y i f sn (x i , k) + b i γ .
In the case of the Natarajan dimension with margin γ, choosing ψ n is equivalent to choosing

a vector c n = (c i ) 1 i n ∈ Y n satisfying for every i ∈ 1; n , c i = y i . Then, ψ n is set equal to (ψ y i ,c i ) 1 i n , so that (2) becomes ∀i ∈ 1; n ,      if s i = 1, f sn (x i , y i ) -b i γ if s i = -1, f sn (x i , c i ) + b i γ .

Scheme of Derivation of the Guaranteed Risks

For all known instances of Formula (1), the scheme of derivation of function F f involving the families of capacity measures considered in this study is standard. It corresponds to the directed graph depicted in Figure 1.

Here, G 0 stands for a generic class of real-valued functions, computed by a binary classier whose nature varies with the context. The value of m is either m or 2m, when the derivation of Inequality (1) involves a ghost sample (Vapnik and Chervonenkis, 1971;[START_REF] Pollard | Convergence of Stochastic Processes[END_REF]. When following a path from the source to the target, two types of transitions are met. A rst group, the horizontal arrows, corresponds to a change of capacity measure.

The standard sequence (from left to right) consists in the chaining method [START_REF] Dudley | The sizes of compact subsets of Hilbert space and continuity of Gaussian processes[END_REF]Talagrand, 2014), to connect the Rademacher complexity to covering numbers, a transition through the corresponding packing numbers, and then a combinatorial result, to switch to a combinatorial dimension. The second group, the layer of vertical arrows, is that of the

F i (m, γ, δ, cap (ρ G,γ )) R m (ρ G,γ ) chaining -----→ N int p ( , ρ G,γ , m ) M p ( , ρ G,γ , m ) combinatorial result ------------→ -dim (ρ G )         structural results     R m (G 0 ) chaining -----→ N int p ( , G 0 , m ) M p ( , G 0 , m ) combinatorial result ------------→ -dim (G 0 )   direct computations F f (m, C, γ, δ)
Figure 1: Graph of the transitions between the functions F i and F f . structural results, performing the transition from the capacity of ρ G,γ to that of G 0 (i.e., from the multi-class case to the bi-class one). As an example, the paths in red are the ones explored in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classiers[END_REF].

Shortcomings of the State-of-the-Art Structural Results

The literature provides us with structural results for all three types of capacity measures considered. This section highlights their deciencies to optimize the condence interval with respect to C and γ.

State-of-the-Art Structural Results

The sharpest structural result for the Rademacher complexity of classes of vector-valued functions is due to [START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF]. It is an improvement of the one introduced in [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF].

Lemma 1 (Corollary 4 in [START_REF] Maurer | A vector-contraction inequality for Rademacher complexities[END_REF]. Let G be a function class satisfying Denition 1.

For n ∈ N * , let F = {f i : 1 i n} be a class of real-valued functions on [-M G , M G ] C
which are L F -Lipschitz continuous with respect to the 2 -norm. Then

E σn sup g∈G n i=1 σ i f i • g (x i ) √ 2L F E σ n,C sup g∈G n i=1 C k=1 σ i,k g k (x i ) ,
where σ n,C = (σ i,k ) 1 i n,1 k C is a Rademacher random matrix.

Let us apply Lemma 1 by dening the functions f i in such a way that ∀i ∈ 1; n ,

f i • g (x i ) = ρ g (z i ). Since they satisfy: ∀i ∈ 1; n , ∀ (g, g ) ∈ G 2 , ρ g (z i ) -ρ g (z i ) 1 2 g (x i ) -g (x i ) 2 ,
∀n ∈ N * , R n (ρ G,γ ) R n (ρ G ) 1 √ 2n E σ n,C sup g∈G n i=1 C k=1 σ i,k g k (x i ) .
It is noteworthy that under the assumption that there is no coupling between the outputs of the classier, Corollary 1 implies a result in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]:

∀n ∈ N * , R n (ρ G,γ ) CR n C
k=1 G k , whose proof does not hold true with ρ G,γ replaced with ρ G .

The counterpart of Corollary 1 dealing with covering numbers is the following structural result.

Lemma 2 (Lemma 1 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classiers[END_REF]. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. Then, for ∈ R * + , n ∈ N * , and z n = ((x i , y i ))

1 i n ∈ Z n , ∀p ∈ [1, +∞] , N int ( , ρ G,γ , d p,zn ) N int ( , ρ G , d p,zn ) C k=1 N int C -1 p , G k , d p,xn , where x n = (x i ) 1 i n .
The main method available to derive structural results for the γ-dimension (see for instance the proof of Lemma 6.2 in [START_REF] Duan | Bounding the fat shattering dimension of a composition function class built using a continuous logic connective[END_REF] consists in three main steps: upper bounding the dimension of interest in terms of a metric entropy of the same class, applying a decomposition (similar to Lemma 2), and applying a combinatorial result. When applied to the class ρ G,γ , it gives birth to the following Lemma.

Lemma 3. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. Then,

∀ ∈ 0, γ 2 , -dim (ρ G,γ ) -dim (ρ G ) 320 log 2 24M G √ C C k=1 96 √ C -dim (G k ) .
(3)

Discussion

We reviewed the state-of-the-art decomposition results associated with the three families of capacity measures involved in this study. None is utterly satisfactory. Under the assumption that there is no coupling between the classier outputs, the decomposition involving Rademacher complexities produces a function F f depending linearly on C, whereas the decomposition involving covering numbers is known to lead to a sublinear dependence (see for instance Theorem 3 in [START_REF] Musayeva | Rademacher complexity and generalization performance of multi-category margin classiers[END_REF]. Furthermore, Corollary 1 makes no use of the function π γ , which vanishes when using Lemma 1 since its Lipschitz constant is 1.

The same holds true for the decompositions involving covering numbers and fat-shattering dimensions. When delaying the decomposition at these levels, the function π γ is only exploited upstream, by the chaining formulas or the combinatorial result. Those limitations raise a question: can a change of combinatorial dimension (replacing -dim (ρ G ) with a γ-Ψ-dimension of ρ G ) improve the dependence of function F f on the basic parameters?

The answers should spring from exploring, in the graph of transitions (Figure 1), the paths highlighted in blue in Figure 2.

F i (m, γ, δ, cap (ρ G,γ )) R m (ρ G,γ ) chaining -----→ N int p ( , ρ G,γ , m ) M p ( , ρ G,γ , m ) combinatorial result ------------→      -dim (ρ G ) -Ψ-dim (ρ G )         structural results     R m (G 0 ) chaining -----→ N int p ( , G 0 , m ) M p ( , G 0 , m ) combinatorial result ------------→ -dim (G 0 )   direct computations F f (m, C, γ, δ) Figure 2: Paths from F i to F f involving combinatorial dimensions of ρ G .
The rst answers, of qualitative nature, are exposed in the following section.

Sharper Combinatorial Results with γ-Ψ-dimensions

We rst establish by elementary means that the combinatorial results involving the fatshattering dimension of the class ρ G of margin functions can always be improved by substituting to this dimension the margin Graph dimension of the same class.

Usefulness of the Margin Graph Dimension

This comparative study benets from the introduction of a new concept of margin operator.

Denition 8 (Class ρG of margin functions). Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For every g ∈ G,

the margin function ρg from Z into [-M G , M G ] is dened by: ∀ (x, k) ∈ Z, ρg (x, k) = -max l =k ρ g (x, l) = 21 {k∈argmax 1 l C ρg(x,l)} -1 max 1 l C ρ g (x, l) .
Then, ρG is dened as: ρG = {ρ g : g ∈ G}.

The class ρG,γ of squashed margin functions is dened accordingly as ρG,γ = {π γ • ρg : g ∈ G}.

With these two function classes at hand, the main result establishing the superiority of our approach over the canonical one is obtained as a combination of three basic properties of the scale-sensitive combinatorial dimensions.

Proposition 1. Let F be a real-valued function class. Then,

∀γ ∈ (0, 1] , ∀ ∈ 0, γ 2 , -dim (π γ • F) -dim (F) . (4)
Proposition 2. Let F be a function class dened as in Denition 6. Then,

∀γ ∈ R * + , γ-N-dim (F) γ-G-dim (F) γ-dim (F) . (5)
Proposition 3. Let G be a function class satisfying Denition 1 and ρ G , ρG , ρ G,γ and ρG,γ the corresponding classes of margin functions and squashed margin functions. Then,

∀γ ∈ R * + , ρG,γ = ρ G,γ (6a) γ-G-dim (ρ G ) = γ-dim (ρ G ) . ( 6b
)
Note that the assumption that the biases b i of both dimensions are nonnegative is mandatory for Equation (6b) to hold true. Let

M p ( , ρ G,γ , n) VC p n, γ, , -dim (ρ G,γ ) VC p n, γ, , -dim (ρ G ) (7)
represent the generic form taken by an L p -norm combinatorial result for ρ G,γ The righthand side inequality springs from Inequality (4), whose application is in agreement with the observation of [START_REF] Bartlett | The sample complexity of pattern classication with neural networks: The size of the weights is more important than the size of the network[END_REF] that in general, the introduction of a squashing operator does not improve the bounds on the fat-shattering dimension (see also the left-hand side inequality of Formula (3)). Then, applying in sequence (6a), ( 4) and (6b) gives:

M p ( , ρ G,γ , n) VC p n, γ, , -dim (ρ G,γ ) = VC p n, γ, , -dim (ρ G,γ ) VC p n, γ, , -dim (ρ G ) = VC p n, γ, , -G-dim (ρ G ) . ( 8
)
The superiority of Inequality (8) over Inequality (7) stems from Inequality (5 Example 1. Let G be a set of two functions g (1) and g

) ( -G-dim (ρ G ) -dim (ρ G )).
(2) from X = {x} into [-M G , M G ] 3 given by g (1) (x) = 3 4 , 1 4 , 0 T and g (2) (x) = 0, 1 2 , 1 2 T . Then, 1 4 -dim (ρ G ) = 1 and 1 4 -G-dim (ρ G ) = 0.
Indeed, ρ g (1) (x, k)

1 k 3 = 1 4 , -1 4 , -3 8 T , ρ g (2) (x, k) 1 k 3 = -1 4 , 0, 0 T , ρg (1) (x, k) 1 k 3 = 1 4 , -1 4 , -1 4 T and ρg (2) (x, k) 1 k 3 = (0, 0, 0) T , so that      ρ g (1) (x, 1) 1 4 -ρ g (2) (x, 1) 1 4 , i.e., the class ρ G 1 4 -shatters {(x, 1)} for b = 0. On the contrary, none of the three sin- gletons {(x, k)} is 1 4 -G-shattered by ρ G since max k =l ρ g (1) (x, k) + ρ g (2) (x, l) = 1 4 < 2 • 1 4 (or equivalently none of the three singletons {(x, k)} is 1 4 -shattered by ρG since max 1 k 3 ρg (1) (x, k) -ρg (2) (x, k) = 1 4 < 2 • 1 4 ).

From Margin Graph Dimension to Margin Natarajan Dimension

After highlighting the relationship between the γ-dimension and the margin Graph dimension, we do the same for the two γ-Ψ-dimensions, by stating a scale-sensitive counterpart of Theorem 10 in [START_REF] Ben-David | Characterizations of learnability for classes of {0, . . . , n}-valued functions[END_REF].

Lemma 4. Let F be a function class dened as in Denition 6. Suppose that γ ∈ R *

+ is such that γ-G-dim (F) is nite. Then, γ-G-dim (F) 32 log 2 2 (e (C -1)) γ-N-dim (F) α(C) , (9)
where α (C) = 1 +

1 4 ln(C-1)+2 .
With Ben-David's theorem in mind, it is noticeable that Lemma 4 holds true for uncountable function classes, the only constraint of niteness regarding γ-G-dim (F). When applied to ρ G , ( 9) is a non trivial bound in the sense that it no longer holds true with γ-G-dim (ρ G ) replaced with γ-dim (ρ G ). Once more, we can resort to Example 1 to establish this behavior. Indeed, it exhibits a pair (G, γ) for which γ-dim

(ρ G ) = 1 but γ-N-dim (ρ G ) = γ-G-dim (ρ G ) = 0.
We conclude the section with a property of the margin Natarajan dimension that will prove useful to upper bound it. Its formulation makes use of a standard convention: a function class

F is said to γ-N-shatter a triplet (s Z n , b n , c n ) if F γ-N-shatters s Z n and (b n , c n ) is
a witness to this shattering. The corresponding convention for the margin Graph dimension is also used. Proposition 4. Let F be a function class dened as in Denition 6. Suppose that for

γ ∈ R * + , the subset F of F γ-N-shatters the triplet ({(x i , y i ) : 1 i n} , b n , c n ). Then F also γ-N-shatters another triplet, ({(x i , y i ) : 1 i n} , b n , c n ), derived from the rst one as follows: ∀i ∈ 1; n ,      if y i < c i , y i = y i , b i = b i , c i = c i if y i > c i , y i = c i , b i = -b i , c i = y i .
As a consequence, the derivation of an upper bound on γ-N-dim (F) can make use of a stronger hypothesis on (y n , c n ): ∀i ∈ 1; n , y i < c i , provided that the hypothesis of nonnegativity of the biases b i is relaxed.

Combinatorial Results

The new results exposed in this section and the following one are the building blocks needed to derive upper bounds on the metric entropies of ρ G,γ , for p 2, following the blue paths of Figure 2. To keep the comparison with the literature simple, we focus on the two most popular options: p = ∞ and p = 2, but the generalization is straightforward using the ideas developed in the proof of Theorem 2 in [START_REF] Musayeva | Rademacher complexity and generalization performance of multi-category margin classiers[END_REF].

In view of the appealing properties of the margin Graph dimension exposed in Section 4.1, the combinatorial results involving this capacity measure are given rst.

Margin Graph Dimension

Lemma 5. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. For ∈ (0,

M G ], let d G ( ) = -G-dim (ρ G ). Then for ∈ (0, γ] and n ∈ N * such that n d G 4 , M ∞ ( , ρ G,γ , n) 6γn d G( 4 ) log 2 2γen d G ( 4 )
.

(10) Inequality ( 10) compares with the application to ρ G,γ of the state-of-the-art L ∞ -norm combinatorial result: Lemma 3.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]. The resulting formula is

M ∞ ( , ρ G,γ , n) < 2 4γ 2 n 2 d( 4 ) log 2 2γen d( 4 )
,

where d ( ) = -dim (ρ G ).
The main observation is that the gain exceeds the one already identied: the replacement of the fat-shattering dimension with the margin Graph dimension. The phenomenon appears especially clearly for = γ 2 , the case of practical interest as will be seen in Section 7.2. We now turn to the case p = 2.

Lemma 6. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. For ∈ (0,

M G ], let d G ( ) = -G-dim (ρ G ).
Then for ∈ (0, γ] and n ∈ N * , 24) .

M 2 ( , ρ G,γ , n) 5γ 20d G(
(11)

Inequality ( 11) compares with the formula obtained with the state-of-the-art L 2 -norm combinatorial result, Theorem 1 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]: 48) .

M 2 ( , ρ G,γ , n) 6γ 20d(
Here again, the improvement exceeds the sole replacement of the fat-shattering dimension with the margin Graph dimension. However, this statement must be qualied, since the benet is smaller, regarding constants only.

Margin Natarajan Dimension

As for the margin Natarajan dimension, with Lemma 4 at hand, Lemmas 5 and 6 also provide us with combinatorial results involving this capacity measure. However, sharper bounds should spring from following the direct path, i.e., working directly with this latter dimension (without involving the margin Graph dimension). We now state the corresponding combinatorial results (for p = ∞ then p = 2) and perform the comparison.

Lemma 7. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. For ∈ (0,

M G ], let d N ( ) = -N-dim (ρ G ).
Then for ∈ (0, γ] and n

∈ N * such that n d N 4 , M ∞ ( , ρ G,γ , n) 6γ √ C -1n d N ( 4 ) log 2 2γ(C-1)en d N ( 4 ) . ( 12
)
Lemma 8. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. For ∈ (0,

M G ], let d N ( ) = -N-dim (ρ G ).
Then for ∈ (0, γ] and n

∈ N * , M 2 ( , ρ G,γ , n) (C -1) 4γ 5 3 2 log 2 2( 14γ ) 2 (C-1) d N ( 28 ) . ( 13
)
As expected, as close to 1 as α (C) may be, Inequalities ( 12) and ( 13) are better than the bounds obtained by substitution of (9) in the formulas involving the margin Graph dimension: (10) and ( 11), respectively. Precisely, in both cases, the dependence on n is unchanged, while the dependences on C and are slightly improved. A quantitative characterization of the gain requires to make assumptions on the dependence of the margin Natarajan dimension on C and . This is done in Section 7.1 (see Hypothesis 1).

Structural Results

We have seen that the combination of Proposition 2 and Lemma 3 provides us with a structural result of reference for γ-G-dim (ρ G ). The proof of the Lemma makes use of the L 2 -norm. However, a signicant improvement stems from choosing p as a function of C.

γ-G-dim (ρ G ) 10K C log 2 (2C) log 2   48M G log 1 7 2 (2C) γ   C k=1 γ 144 log 2 (2C) -dim (G k ) , (14)
where

K C = min 4 C C-2 2 , 16 .
The obvious benet is an improved dependence on C.

Margin Natarajan Dimension

We now establish three structural results for γ-N-dim (ρ G ).

Lemma 10. Let G be a function class satisfying Denition 1 and ρ G the function class

deduced from G according to Denition 2. Let G 0 = 1 2 (g k -g l ) : g ∈ G, 1 k < l C . Then, ∀γ ∈ (0, M G ] , γ-N-dim (ρ G ) C 2 • γ-dim (G 0 ) (15)
and

∀γ ∈ (0, M G ] , γ-N-dim (ρ G ) 320 (C -1) log 2 24 √ 2M G γ C k=1 γ 96 √ 2 -dim (G k ) . (16)
Formula ( 15) can be used to derive a sharper structural result when the classier is such that the classes of component functions can be chosen so as to include the class G 0 .

Corollary 2. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. Suppose further that there exists a Hilbert space (H, •, • H ) such that for every function g ∈ G, there is a mapping f g from X into H and a vector (w g,k )

1 k C ∈ H C satisfying max 1 k C w g,k H Λ with Λ ∈ R * + such that ∀x ∈ X , g (x) = w g,k , f g (x) H 1 k C .
Let the classes G k of component functions be all dened as the class of all functions mapping

x ∈ X to w, f g (x) H , where w H Λ and g ∈ G. Then,

∀γ ∈ (0, M G ] , γ-N-dim (ρ G ) C 2 • γ-dim (G 1 ) . ( 17
)
The hypothesis of Corollary 2, is satised by classiers of reference such as the multilayer perceptrons (MLPs) [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF] with linear output units and the C-category support vector machines (SVMs) [START_REF] Do §an | A unied view on multi-class support vector classication[END_REF]. In the second case, the mapping f g does not depend on g, and f g (x) can be chosen to be κ x with κ being the kernel [START_REF] Berlinet | Reproducing Kernel Hilbert Spaces in Probability and Statistics[END_REF]. Then, H is the reproducing kernel Hilbert space (RKHS) spanned by κ. It is noticeable that such a simple hypothesis proved enough to sharpen signicantly the bound (replace Inequality ( 16) with Inequality ( 17)). Indeed, the major advantage of working with γ-N-dim (ρ G ) is the possibility to take benet from the specicities of the classier. Formula ( 17) exploits an algebraic property of the function class of interest. We now illustrate the gain resulting from taking into account more specically the coupling between the outputs, by extending the study of the case of the C-category SVMs. We base the denition of these machines on that of RKHS of R C -valued functions (Wahba, 1992).

Denition 9 (RKHS H κ,C ). Let κ be a real-valued positive type function on X 2 and let H κ , •, • Hκ be the corresponding RKHS. Let κ be the real-valued positive type function on Z 2 deduced from κ as follows:

∀ (z, z ) ∈ Z 2 , κ (z, z ) = δ y,y κ (x, x ), where δ is the Kronecker delta. For every z ∈ Z, let us dene the R C -valued function κ(C) z on X by the formula κ(C) z (•) = (κ (z, (•, k))) 1 k C . ( 18
)
The RKHS of R C -valued functions at the basis of a C-category SVM with kernel κ, H κ,C , •, • H κ,C , consists of the linear manifold of all nite linear combinations of functions of the form (18) and its closure with respect to the inner product:

∀ (z, z ) ∈ Z 2 , κ(C) z , κ(C) z H κ,C = κ (z, z ).
With Denition 9 at hand, the specication of the function class at the basis of a Ccategory SVM rests on the condition controlling the capacity through a coupling between the outputs. We consider the standard one, used for instance by [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF].

Denition 10 (Function class H Λ ). Let κ be a real-valued positive type function on X 2 and

let Λ ∈ R * + . Let H κ,C , •, • H κ,C
be the RKHS of R C -valued functions spanned by κ according to Denition 9. Then the function class H Λ associated with the C-category SVM parameterized by (κ, Λ) is:

H Λ = h = (h k ) 1 k C ∈ H κ,C : C k=1 h k = 0 Hκ and h H κ,C Λ .
Then, Lemma 11 provides a sharper bound on γ-N-dim (ρ H Λ ) than Lemma 10. Lemma 11. For Λ ∈ R * + , let H Λ be a function class satisfying Denition 10. Suppose that for every x ∈ X , κ x belongs to the closed ball of radius Λ X about the origin in H κ . Then,

∀γ ∈ (0, ΛΛ X ] , γ-N-dim (ρ H Λ ) C ΛΛ X 2γ 2 . ( 19
)
Loosely speaking, Furmula (19) tells us that γ-N-dim (ρ H Λ ) can be upper bounded by C times the standard upper bound on the γ-dimension of an SVM (Theorem 4.6 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classiers[END_REF]. Thus, taking into account the coupling between the outputs has turned the quadratic dependence of Formula ( 17) into a linear one.

7 Guaranteed Risks

Given the scheme adopted for the derivation of guaranteed risks, in most of the options considered (paths in the graph of Figure 1

Bounds on the Metric Entropies

For the rst formula, we use the standard hypothesis: that of polynomial γ-dimensions (van der Vaart and Wellner, 1996;[START_REF] Mendelson | A few notes on statistical learning theory[END_REF]. We have already seen that it is satised by SVMs. This is also the case for MLPs with linear output units (see for instance Theorem 14.19 in [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF]. The second formula is a generic one. It is designed to incorporate the hypothesis of polynomial γ-dimensions in a decomposition result taking benet from some knowledge on the function class G and a coupling between outputs. It is thus inspired by the structural results of the previous section, precisely Inequalities ( 17) and ( 19).

Hypothesis 1. We consider function classes G satisfying Denition 1 plus the fact that

there exists a quadruplet d G,C , d G,γ , K G 0 , K ρ G ∈ (0, 2] × R * + 3 such that ∀ ∈ (0, M G ] ,    max 1 k C -dim (G k ) K G 0 -d G,γ (20a)
-N-dim (ρ G ) K ρ G C d G,C -d G,γ . (20b)
Under Hypothesis 1, the combinatorial results dedicated to the margin Natarajan dimension (Lemmas 7 and 8) give birth to the following bounds on the metric entropies.

Theorem 1. Let G be a function class satisfying Hypothesis 1. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. For ∈ (0, γ] and n ∈ N * such

that n K ρ G C d G,C 4 d G,γ , log 2 N int ∞ ( , ρ G,γ , n) K ρ G C d G,C log 2 2 6γ (C -1) n 4 d G,γ . (21)
For ∈ (0, γ] and n ∈ N * ,

log 2 N int 2 ( , ρ G,γ , n) 3 2 K ρ G C d G,C log 2 2 (C -1) 4γ 5 28 d G,γ . ( 22
)
As expected, the main dierence between those two bounds regarding the dependence on the basic parameters is that the second one is dimension free (does not depend on the number n of points). They are signicantly better than the bounds obtained with the margin Graph dimension (and thus the fat-shattering dimension of ρ G ). In the latter sequence of transitions, the limiting factor is obviously the structural result: Lemma 9. (applied to the classes G k ), and nally Formula (20a). This corresponds to the red paths in Figure 1. The next section is devoted to the comparison. To make it more concrete, we use as touchstones the functions F i corresponding to the state-of-the art basic supremum inequalities associated with the two L p -norms favored in this study.

Comparative Study -Uniform Convergence Norm

To the best of our knowledge, the sharpest instance of Inequality (1) involving the L ∞norm is Formula (20) in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classiers[END_REF]. It is a multi-class extension of Lemma 4

in [START_REF] Bartlett | The sample complexity of pattern classication with neural networks: The size of the weights is more important than the size of the network[END_REF], with the rst symmetrization being derived from the basic lemma of Section 4.5.1 in Vapnik (1998). This bound corresponds to the following choices: L * = L and φ γ (t) = 1 {t<γ} , and produces:

F i (m, γ, δ, cap (ρ G,γ )) = 2 m ln N int ∞ γ 2 , ρ G,γ , 2m + ln 2 δ + 1 m .
In that case, (21

) becomes for m 1 2 K ρ G C d G,C 8 γ d G,γ : log 2 N int ∞ γ 2 , ρ G,γ , 2m K ρ G C d G,C log 2 2 (24 (C -1) m) 8 γ d G,γ . ( 23
)
On the other hand, applying the decomposition with covering numbers (Lemma 2) and Lemma 3.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] as combinatorial result yields for

m 1 2 K G 0 8 γ d G,γ : log 2 N int ∞ γ 2 , ρ G,γ , 2m C 1 + K G 0 log 2 2 128M 2 G m γ 2 8 γ d G,γ . (24)
Thus, the functions F f associated with Inequalities ( 23) and ( 24) exhibit the same dependence on m (a O ln(m) √ m ). As for the dependence on γ, the new formula induces a gain of a factor ln γ -1 . The dependence on C will also be improved for d G,C < 1 (the computations could take into account a strong coupling between the outputs).

7.3

Comparative Study -L 2 -norm Turning to the case of the L 2 -norm, the best instance of Inequality (1) involves the Rademacher complexity as capacity measure. It is a partial result in the proof of Theorem 8.1 in [START_REF] Mohri | Foundations of Machine Learning[END_REF] (with ρ G replaced with ρ G,γ ). Its margin loss function is given by φ γ (t) = 1 {t 0} + 1 -t γ 1 {t∈(0,γ]} (parameterized truncated hinge loss) and L * = L γ . The analytical expression of function F i is:

F i (m, γ, δ, cap (ρ G,γ )) = 2 γ R m (ρ G,γ ) + ln 1 δ 2m . (25)
In accordance with the graph of the transitions (Figures 1 and2), the Rademacher complexity is upper bounded as a function of the metric entropy by means of Dudley's chaining method. We use the following formula, whose degrees of freedom can be exploited to optimize the dependence on the basic parameters.

Theorem 2 (Theorem 9 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classiers[END_REF]. Let F be a class of bounded real-valued functions on T . For n ∈ N * , let t n ∈ T n and let diam (F) be the diameter of F with respect to the pseudo-metric d 2,tn . 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 int (h (j) , F, d 2,tn )) n . ( 26
)
To upper bound the metric entropy above, the formula of reference (obtained by combining the structural result dedicated to covering numbers with the combinatorial result of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]) is:

∀ ∈ (0, γ] , log 2 N int 2 ( , ρ G,γ , n) 20K G 0 C log 2 12M G √ C 48 √ C d G,γ . (27)
Using instead our new bound, Inequality ( 22), a substitution into (26) gives:

R m (ρ G,γ ) h (N ) + 4 F 1 (C) m j∈J h (j) + h (j -1) h (j) d G,γ 2 ln (C -1) 4γ h (j) 5 (28)
where

F 1 (C) = 28 d G,γ K ρ G C d G,C , (29)
with J = {j ∈ 1; N : h (j) γ}. With the last formula at hand, the derivation of the condence interval amounts to studying the phase transitions highlighted by Theorem 18 in [START_REF] Mendelson | A few notes on statistical learning theory[END_REF].

Theorem 3. Let G be a function class satisfying Hypothesis 1. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5.

If d G,γ ∈ (0, 2), then R m (ρ G,γ ) 4 1 + 2 2 2-d G,γ F 1 (C) m F 2 (C) γ 1- d G,γ 2 ,
where F 1 (C) is given by Equation ( 29) and F 2 (C) = ln (C -1) 4 5 + 10 1+ln(2)

2-d G,γ . If d G,γ = 2, then R m (ρ G,γ ) γ log 2 (m) √ m +12 F 1 (C) m log 2 √ m log 2 (m) ln (C -1) 4 5 + 5 2 ln 4 √ m log 2 (m) . At last, if d G,γ > 2, then R m (ρ G,γ ) γ log 2 (m) m 1 d G,γ ×   1 + 8 1 + 2 2 d G,γ -2 1 γ d G,γ 2 F 1 (C) log 2 (m) ln   (C -1) 4 m log 2 (m) 1 d G,γ 5     .
Comparing Theorem 3 with the result based on (27): Theorem 7 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classiers[END_REF] (see also Theorem 3 in [START_REF] Musayeva | Rademacher complexity and generalization performance of multi-category margin classiers[END_REF] produces the following observations. The growth of F f with the inverse of the margin parameter γ is now a O γ - ln (C) , implying that it is always sublinear except when d G,C takes its maximum value 2, i.e., when no coupling between the outputs can be exploited. The only prize to pay occurs for d G,γ 2 (complex classiers). Then, the dependence on the sample size m increases by a factor ln (m).

Conclusions

We have established that the guaranteed risks involving the fat-shattering dimension of the class of margin functions ρ G can always be simply improved by replacing this dimension with the margin Graph dimension of the same class (Lemmas 5 and 6). Currently, the gain is limited by the lack of malleability of the corresponding structural result: Lemma 9.

Fortunately, the use of another γ-Ψ-dimension, the margin Natarajan dimension, makes it possible to exploit basic features of the classier of interest (Formula ( 17) and Lemma 11).

The major consequence is an improved dependence of the condence interval on the margin parameter γ.

A Proofs of the Basic Results on the γ-Ψ-dimensions

This appendix gathers the proofs of the basic properties of the margin Graph dimension and the margin Natarajan dimension.

A.1 Margin Graph Dimension

The proof of Proposition 1 is the following one.

Proof. For γ ∈ (0, 1] and ∈ 0, γ 2 , let s T n = {t i : 1 i n} be a subset of T -shattered by the subset f sn

γ = π γ • f sn : s n ∈ {-1, 1} n of π γ •F and let b n = (b i ) 1 i n be a witness to this shattering. Obviously, b n ∈ [ , γ -] n . Consequently, f sn γ (t i ) -b i =⇒ f sn γ (t i ) 2 > 0 =⇒ f sn (t i ) f sn γ (t i ) =⇒ f sn (t i ) -b i . Similarly, -f sn γ (t i ) + b i =⇒ f sn γ (t i ) γ -2 < γ =⇒ f sn (t i ) f sn γ (t i ) =⇒ -f sn (t i ) + b i .
The proof of Proposition 2 is the following one.

Proof. For γ ∈ R * + , let s Z n = {z i = (x i , y i ) : 1 i n} be a subset of Z γ-N-shattered by {f sn : s n ∈ {-1, 1} n } ⊂ F and let (b n , c n ) be a witness to this shattering. To prove the left-hand side inequality of Formula (5), it suces to notice that for a given vector s n , the function f sn ∈ F satisfying ∀i ∈ 1; n ,

     if s i = 1, f sn (x i , y i ) -b i γ if s i = -1, f sn (x i , c i ) + b i γ also satises ∀i ∈ 1; n ,      if s i = 1, f sn (x i , y i ) -b i γ if s i = -1, max k =y i f sn (x i , k) + b i γ .
Keeping the notations above, proving the right-hand side inequality of Formula (5) boils down to establishing that max k =y i f sn (x i , k) -f sn (x i , y i ). Indeed, ∀f ∈ F, ∀x ∈ X , max

1 k<l C {f (x, k) + f (x, l)} = 0 =⇒ f sn (x i , y i ) + max k =y i f sn (x i , k) 0 =⇒ max k =y i f sn (x i , k) -f sn (x i , y i ) .
The proof of Proposition 3 is the following one.

Proof. Let g be any function in G. According to Denitions 2 and 8, a necessary condition for ρ g and ρg to dier on z ∈ Z is that ρ g (z) < 0. In that case, ρg (z) 0, so that for every γ ∈ R * + , ρ g,γ (z) = ρg,γ (z) = 0. Equation (6a) has been proved. For γ ∈ R * + , let s Z n = {z i = (x i , y i ) : 1 i n} be a subset of Z γ-G-shattered by {ρ g sn :

s n ∈ {-1, 1} n } ⊂ ρ G and let b n = (b i ) 1 i n ∈ R n
+ be a witness to this shattering.

ρ g sn (z i ) -b i γ =⇒ ρ g sn (z i ) > 0 =⇒ ρg sn (z i ) = ρ g sn (z i ) . Furthermore, max k =y i ρ g sn (x i , k) = -ρ g sn (x i , y i ) . To sum up, ∀i ∈ 1; n ,      if s i = 1, ρ g sn (x i , y i ) -b i γ if s i = -1, max k =y i ρ g sn (x i , k) + b i γ implies that ∀i ∈ 1; n , s i (ρ g sn (x i , y i ) -b i ) γ. We have established that γ-G-dim (ρ G ) γ-dim (ρ G ).
The complementary inequality is obtained in the same way (by making use of b n ∈ R n + ), which concludes the proof of Formula (6b).

A.2 Margin Natarajan Dimension

The proof of Lemma 4 is the following one.

Proof. Let us set d G = γ-G-dim (F) and d N = γ-N-dim (F). Formula ( 9) is trivially true for d G 1. Thus, we prove it under the assumption that d G 2. Let F 0 be a subset of

F of cardinality 2 d G that γ-G-shatters a subset s Z d G of Z of cardinality d G . For notational simplicity, we set s Z d G = {z i : 1 i d G }. Let the vector b d G = (b i ) 1 i d G ∈ R d G
+ be a witness to this shattering. For F ⊂ F 0 satisfying F 2, let S F be the set of the subsets s

(1)

Z r = z (1) i = x (1)
i , y

(1) i

: 1 i r of s Z d G such that: s (1) Z r ∈ S F ⇐⇒ ∀ f, f ⊂ F, ∃z i ∈ s (1) Z r :      f (z i ) -b i γ max k =y i f (x i , k) + b i γ or vice versa.
The meaning of the formula z i ∈ s

(1)

Z r is the obvious one, i.e., ∃z

(1) j ∈ s

(1)

Z r : z i = z (1) j .
Notice rst that s Z d G belongs to all the sets S F . For F ⊂ F 0 satisfying F 2 and s

(1)

Z r ∈ S F , let h F, s (1)
Z r be the number of triplets s

(2)

Z u , b (2)
u , c

(2) u satisfying:

                   s (2) Z u = z (2) i = x (2)
i , y

(2) i

: 1 i u ⊂ s (1) Z r ∀ (i, j) : 1 i < j u, z (2)
i , z

(2) j = (z v , z w ) =⇒ 1 v < w d G ∀ (i, j) ∈ 1; u × 1; d G , z (2)
i = z j =⇒ b (2) i = b j ∀i ∈ 1; u , c (2)
i ∈ Y \ y Inductive property Let F and s (1)

Z r be dened as above. By the pigeonhole principle, there exist z i 0 ∈ s

(1)

Z r , a value c i 0 ∈ Y \{y i 0 } and two subsets F+ and Fof F of cardinalities

F+ | F | 2 1 r and F- | F | 2 1 r 1 C-1 such that      ∀f + ∈ F+ , f + (z i 0 ) -b i 0 γ ∀f -∈ F-, f -(x i 0 , c i 0 ) + b i 0 γ . h F, s (1) Z r h F+ , s (2) Z r-1 + h F-, s (2) Z r-1 + 1. (30)
Termination property By denition of F, s (1) Z r and the Natarajan dimension with mar- gin γ, h F, s

(1) Z r 1.

(31) These two properties call for a reasoning based on a binary tree whose root is F 0,1 = F 0 and whose depth is d G . Its derivation utterly rests on the specication of two functions, z * and c * , respectively returning for each inner node the example and the category dening its two sons. For i ∈ 0; d G , the nodes of the tree at depth i are denoted F i,j . If |F i,j | 2 (F i,j is an inner node), then its two sons are F i+1,2j-1 and F i+1,2j . The values of z * (0, 1) and c * (0, 1) (dening the two sons, F 1,1 and F 1,2 , of F 0,1 ), are given by z * (0, 1) = z 1 , so that

F 1,1 = {f ∈ F 0,1 : f (z 1 ) -b 1 γ} . and c * (0, 1) = min argmax k =y 1 f ∈ F 0,1 \ F 1,1 : f (x 1 , k) = max l =y 1 f (x 1 , l) , so that F 1,2 = f ∈ F 0,1 \ F 1,1 : f (x 1 , c * (0, 1)) = max l =y 1 f (x 1 , l) . Note that ∀f ∈ F 1,2 , f (x 1 , c * (0, 1)) + b 1 γ, |F 1,1 | = 2 d G -1 , and according to the pigeonhole principle, |F 1,2 | 2 d G -1 C-1 . For i ∈ 1; d G -1 , if F i,
j is not a leaf, then the construction of its two sons depends on the value of j.

For j = 1, F i+1,1 and F i+1,2 are dened according to the same principle as F 1,1 and F 1,2 , i.e., z * (i, 1) = z i+1 , so that

F i+1,1 = {f ∈ F i,1 : f (z i+1 ) -b i+1 γ} , and c * (i, 1) is such that among the C -1 sets F i+1,2,k = f ∈ F i,1 \ F i+1,1 : f (x i+1 , k) = max l =y i+1 f (x i+1 , l) for k = y i+1 , F i+1,2 is a set of maximal cardinality. As in the original case, this implies that |F i+1,1 | = 2 d G -i-1 and |F i+1,2 | 2 d G -i-1 C-1 2 d G -i-1 C-1 .
For j > 1, the derivation of the sets F i+1,2j-1 and F i+1,2j follows that of the sets F+ and Fof the inductive property (z * (i, j) = z i 0 and c * (i, j)

= c i 0 ). As a consequence,      |F i+1,2j-1 | |F i,j | 3(d G -i) |F i+1,2j | |F i,j | 3(d G -i)(C-1)
.

The binary tree has been built in such a way that all the triplets (F i,j , F i+1,2j-1 , F i+1,2j ) satisfy (30) (whether j > 1 or not). Furthermore, any set which is not a leaf satises (31).

By combination of these two inequalities,

h (F 0,1 , s Z d G ) (F 0,1 ) -1, ( 32
)
where the function returns the number of leaves of the (sub)tree whose root is its argument. Thus, the next step of the proof consists in deriving a lower bound on (F 0,1 ). Since the assumption d G 2 has been made, a simple induction gives

(F 0,1 ) = (F d G ,1 ) + d G i=1 (F i,2 ) = 2 + d G -1 i=1 (F i,2 ) . ( 33
)
We now establish by induction that any node F i,j which is not a leaf satises:

(F i,j ) |F i,j | 1 log 2 (3 √ C-1(d G -i)) . ( 34
)
The induction is on the depth i of the node. Inequality (34) is obviously true for i = d G -1,

i.e., the node

F d G -1,1 , since (F d G -1,1 ) = |F d G -1,1 | = 2
. Suppose now that it holds true for all the nodes at depth ranging from i + 1 to d G -1. Then,

(F i,j ) = (F i+1,2j-1 ) + (F i+1,2j ) |F i,j | 3 (d G -i) 1 log 2 (3 √ C-1(d G -i)) + |F i,j | 3 (d G -i) (C -1) 1 log 2 (3 √ C-1(d G -i)) = 1 2 √ C -1 1 log 2 (3 √ C-1(d G -i)) + √ C -1 - 1 log 2 (3 √ C-1(d G -i)) |F i,j | 1 log 2 (3 √ C-1(d G -i)) 1 2 min t∈R * + t + 1 t |F i,j | 1 log 2 (3 √ C-1(d G -i)) = |F i,j | 1 log 2 (3 √ C-1(d G -i))
.

We thus get for the whole tree:

(F 0,1 ) 2 d G log 2 (3 √ C-1d G ) (35)
(the sharper bound provided by ( 33) does not bring any improvement here). Function h can be bounded from above in a classical way. Since d N 1, combinatorics produces

h (F 0 , s Z d G ) d N u=1 d G u (C -1) u ,
which gives birth to a handy formula thanks to a well-known computation (see for instance the proof of Corollary 3.3 in [START_REF] Mohri | Foundations of Machine Learning[END_REF]:

h (F 0 , s Z d G ) (C -1) ed G d N d N -1. ( 36
)
Combining the lower bound (Inequalities ( 32) and ( 35)) and the upper one (Inequality (36))

produces by transitivity

d G d N log 2 (C -1) ed G d N log 2 3 √ C -1d G 1 ln 2 (2) d N ln F (C) d G d N ln (F (C) d G ) , (37)
where F (C) = e (C -1). To bound from above the right-hand side of Inequality (37), we resort to the following statement:

∀ (u, u 0 ) ∈ [1, +∞) 2 , ln (u) 2u 0 u 1 4u 0 , (38)
with u 0 = ln (F (C)). We then obtain

     ln F (C) d G d N 2e 1 4 ln (F (C)) d G d N 1 4 ln(F (C)) ln (F (C) d G ) 2e 1 4 ln (F (C)) d 1 4 ln(F (C)) G .
By substitution into (37),

d G 4 √ e ln 2 (2) ln 2 (F (C)) d 1 2 ln(F (C)) G d 4 ln(F (C))-1 4 ln(F (C)) N = 4 √ e ln 2 (2) 2 ln(F (C)) 2 ln(F (C))-1 (ln (F (C))) 4 ln(F (C)) 2 ln(F (C))-1 d 4 ln(F (C))-1 4 ln(F (C))-2 N = 4 √ e ln 2 (2) 2 ln(F (C)) 2 ln(F (C))-1 (ln (F (C))) 2 2 ln(F (C))-1 ln 2 (2) log 2 2 (F (C)) d 4 ln(F (C))-1 4 ln(F (C))-2 N < 32 log 2 2 (F (C)) d 1+ 1 4 ln(F (C))-2 N .
The proof of Proposition 4 is the following one.

Proof. Without loss of generality, we assume that F is of minimal cardinality 2 n and set accordingly F = {f sn : s n ∈ {-1, 1} n }. Consider the following bijection on {-1, 1} n :

B : {-1, 1} n -→ {-1, 1} n s n → s n ∀i ∈ 1; n ,      if y i < c i , s i = s i if y i > c i , s i = -s i . Then, ∀i ∈ 1; n ,      if s i = 1, f s n (x i , y i ) -b i γ if s i = -1, f s n (x i , c i ) + b i γ =⇒ ∀i ∈ 1; n ,      if s i = 1, f s n (x i , y i ) -b i γ if s i = -1, f s n (x i , c i ) + b i γ . By denition, the triplet (s Z n , b n , c n ) is γ-N-shattered by F, which concludes the proof.

B Proofs of the Combinatorial Results

This appendix gathers the proofs of the four new combinatorial results. It starts with three lemmas which are common to all proofs.

B.1 Shared Technical Lemmas

Each of the combinatorial results in the literature is built upon a basic lemma that involves two (possibly identical) function classes whose domain and codomain are nite sets (so that their cardinalities are also nite). It upper bounds the cardinality of one of them in terms of a combinatorial dimension of the other. In the case of margin classiers, the combinatorial dimension of the basic lemma is a variant of the scale-sensitive dimension of the combinatorial result, variant designed to take benet from the aforementioned restrictions. The rst capacity measure of this kind is a variant of the γ-dimension: the strong dimension (Denition 3.1 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]. The strong Ψ-dimensions extend the γ-Ψ-dimensions according to the same principle.

Denition 11 (Strong Ψ-dimensions). Let F be a class of functions from Z = X × Y into -M F ; M F , where X is a nite subset of X and M F ∈ N * . F satises:

∀f ∈ F, ∀x ∈ X , max

1 k<l C {f (x, k) + f (x, l)} = 0.
Let Ψ be a family of mappings from Y into {-1, 0, 1}. A subset s Zn = {z i = (x i , y i ) : 1 i n} of Z is said to be strongly Ψ-shattered by F if there is a vector

ψ n = ψ (i) 1 i n ∈ Ψ n satisfying ψ (i) (y i ) 1 i n = 1 n , and a vector b n = (b i ) 1 i n ∈ 0; M F -1 n such that, for every vector s n = (s i ) 1 i n ∈ {-1, 1} n , there is a function f sn ∈ F satisfying ∀i ∈ 1; n , s i s i max {k: ψ (i) (k)=s i} f sn (x i , k) -b i 1.
The strong Ψ-dimension of F, denoted by S-Ψ-dim (F), is the maximal cardinality of a subset of Z strongly Ψ-shattered by F, if such maximum exists. Otherwise, F is said to

have innite strong Ψ-dimension.
In what follows, the niteness of the domain is simply obtained by application of a restriction to an appropriately chosen set of data points. As for the niteness of the codomain, it results from the application of the following discretization operator.

Denition 12 (η-discretization operator, Denition 33 in [START_REF] Guermeur | VC theory of large margin multi-category classiers[END_REF]. Let F be a class of functions from T into the interval [M F -, M F + ]. For η ∈ R * + , dene the ηdiscretization as an operator on F such that:

(•) (η) : F -→ F (η) f → f (η) ∀t ∈ T , f (η) (t) = sign (f (t)) • |f (t)| η .
The transitions from continuous functions to discrete ones and back are obtained by application of the two following lemmas.

Lemma 12. Let F be a class of functions from T into the interval [0,

M F ] with M F ∈ R * + .
For n ∈ N * , let t n = (t i ) 1 i n ∈ T n . Let N be a positive integer. For every ∈ (0, M F ]

and every η ∈ 0, N +1 , ∀ f, f ∈ F 2 , d 2,tn f, f =⇒ d 2,tn f (η) , f (η)
N,

with the consequence that if the subset F of F is -separated with respect to the pseudometric d 2,tn , then it is in bijection with the subset F(η) of F (η) , which is N -separated with respect to the same pseudo-metric. Similarly, for every ∈ (0, M F ] and every η ∈ 0, 2 ,

M ( , F, d ∞,tn ) M 2, F (η) , d ∞,tn . (40)
Proof. For f ∈ F and i ∈ 1; n , let us denote the Euclidean division of f (t i ) by η as follows:

∀i ∈ 1; n , f

(t i ) = ηf (η) (t i ) + r i .
With the notation introduced above,

d 2,tn f, f 2 = 1 n n i=1 η f (η) (t i ) -f (η) (t i ) + r i -r i 2 . For i ∈ 1; n , let δ i = f (η) (t i ) -f (η) (t i ) . d 2,tn f, f and η ∈ 0, N + 1 =⇒ 1 n n i=1 ηδ i + r i -r i 2 1 2 =⇒ 1 n n i=1 (δ i + 1) 2 1 2 η =⇒ 1 n n i=1 (δ i + 1) 2 1 2 N + 1 (41) =⇒ 1 n n i=1 δ 2 i 1 2 + 1 N + 1 (42) =⇒ d 2,tn f (η) , f (η)
N,

where the transition from (41) to ( 42) is provided by the triangle inequality. To sum up, we have established (39), i.e., the part of the lemma dealing with the L 2 -norm. To prove

(40), it is enough to observe that f (t) -f (t) =⇒ f ( 2 ) (t) -f ( 2 ) (t) 2.
Lemma 13. Let F be a function class dened as in Denition 6. Suppose further that the functions in F are dened on a nite subset Z = X × Y of Z and take their values in

[-M F , M F ] with M F ∈ R * + . For every η ∈ (0, M F ] and every ∈ 0, η 2 ,    S-G-dim F (η) -G-dim (F) (43a) S-N-dim F (η) -N-dim (F) . (43b)
Proof. To prove (43a), it is enough to establish that any set strongly G-shattered by F (η) is also G-shattered with margin η 2 by F. Suppose that the subset s Zn = {z i = (x i , y i ) : 1 i n} of Z is strongly G-shattered by F (η) . Then, according to Denitions 11 and 12, there exist

a vector b n = (b i ) 1 i n ∈ 0; M F η -1 n and a set {f sn : s n ∈ {-1, 1} n } ⊂ F such that ∀s n = (s i ) 1 i n ∈ {-1, 1} n , ∀i ∈ 1; n ,      if s i = 1, f (η) sn (x i , y i ) -b i 1 if s i = -1, max k =y i f (η) sn (x i , k) + b i 1 . As a consequence, a proof is obtained by exhibiting a vector b n = (b i ) 1 i n ∈ R n + such that ∀s n = (s i ) 1 i n ∈ {-1, 1} n , ∀i ∈ 1; n ,      if s i = 1, f sn (x i , y i ) -b i η 2 if s i = -1, max k =y i f sn (x i , k) + b i η 2 . A feasible
(g, g ) ∈ G 2 , γ ∈ (0, 1], η ∈ 0, γ 2 and z = (x, y) ∈ Z such that ρ (η) g,γ (z) -ρ (η) g ,γ (z) 2.
(44)

For every b ∈ ρ Proof. The rst assertion is obvious, since by denition of b,

(η) g ,γ (z) + 1; ρ (η) g,γ (z) -1 and c ∈ argmax k =y ρ (η) g (x, k), 1. the set ρ (η) g,γ , ρ (η)
     ρ (η) g,γ (z) -b 1 -ρ (η) g ,γ (z) + b 1 . It springs from (44) that ρ (η)
g,γ (z) > 0, which implies that ρ g (z) ρ g,γ (z) and thus ρ (η)

g (z) ρ (η) g,γ (z). Consequently, ρ (η) g (z) -b ρ (η) g,γ (z) -b 1. Furthermore, if ρ (η) g (z) 0, then ρ (η)
g ,γ (z) < γ η implies that ρ g (z) = ρ g ,γ (z), with the consequence that ρ (η)

g (z) = ρ (η) g ,γ (z). Then, max k =y ρ (η) g (x, k) = -ρ (η) g (z) = -ρ (η) g ,γ (z). Otherwise, max k =y ρ (η) g (x, k) 0 = -ρ (η) g ,γ (z). Thus, in both cases, max k =y ρ (η) g (x, k) -ρ (η) g ,γ (z), leading to max k =y ρ (η) g (x, k) + b -ρ (η) g ,γ (z) + b 1. (45)
The strong G-shattering of ({z} , b) by ρ Remark 3. It is noticeable that the proof of Lemma 14 makes use of the inequality

max k =y ρ (η) g (x, k) -ρ (η)
g ,γ (z) ,

and we have even

max k =y ρ g (x, k) -ρ g ,γ (z) ,
which is not intuitive since the key argument establishing that γ-G-dim

(ρ G ) γ-dim (ρ G ) is ∀g ∈ G, ∀z ∈ Z, max k =y ρ g (x, k) -ρ g (z)
.

B.2 Margin Graph Dimension -Uniform Convergence Norm

The proof of Lemma 5 borrows from the proofs of classical results, including the two state-of-the-art combinatorial results: Lemma 3.5 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] and Theorem 1 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. Central in this proof is the following basic combinatorial result.

Lemma 15. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. For G ⊂ G, s

Z n = {z i = (x i , y i ) : 1 i n} ⊂ Z, γ ∈ (0, 1] and η ∈ 0, γ 2 , let F γ = ρ G,γ s Z n (η) and let F = ρ G S(s Z n ) (η) with S (s Z n ) = {(x i , k) : (i, k) ∈ 1; n × 1; C }. If F γ is 2-separated in the pseudo-metric d ∞,zn , then |F γ | (3M γ n) log 2 (Σ) , (46)
where Σ = d G u=0 n u M u γ with M γ = γ η and d G is the maximal cardinality of a subset of s Z n strongly G-shattered by F.

Proof. Notice rst that Inequality ( 46) is trivially true for |F γ | = 1. Indeed, the minimal value of its right-hand side, corresponding to d G = 0, is 1. Thus, the rest of the proof makes use of the restriction |F γ | 2. A direct consequence is that according to Lemma 14, d G 1.

Since two examples z i and z j can be such that x i = x j (provided that y i = y j ), then it is

possible that |S (s Z n )| < Cn. Furthermore, s Z n ⊂ S (s Z n ) implies that d G S-G-dim (F). A subset of s Z n of cardinality u ∈ 1; n is denoted by s Z u = {z i : 1 i u}, with the convention ∀ (i, j) : 1 i < j u, z i , z j = (z v , z w ) =⇒ 1 v < w n.
For every subset Ḡ of G, denote by s Ḡ the number of pairs (s

Z u , b u ) with s Z u ⊂ s Z n and b u ∈ 1; M γ -1 u strongly G-shattered by F = ρ Ḡ S(s Z n ) (η)
(the convention above has been introduced to avoid handling duplicates). Since d G 1, combinatorics gives:

s G d G u=1 n u M u γ = Σ -1. (47)
In order to derive a lower bound on s G , we build a 2-separating tree of F γ (see Denition 3.4 in [START_REF] Rudelson | Combinatorics of random processes and sections of convex bodies[END_REF]. Let Fγ = ρ Ḡ,γ s Z n (η)

be one of its nodes such that Fγ 2 (inner node). Its two sons, Fγ,+ and Fγ,-, are built as follows. Split

f γ , f γ , nd z i ∈ s Z n such that f γ (z i ) -f γ (z i ) 2.
By the pigeonhole principle, the same example is picked for at least

| Fγ | 2 1 n
pairs. Let z i 0 be such an example, and let (f γ,+ , f γ,-) denote the corresponding pairs, whose components are reordered (when needed) so that

f γ,+ (z i 0 ) > f γ,-(z i 0 ) . Among the functions f γ,+ , at least | Fγ | 2 1 n 1 Mγ -1
take the same value at z i 0 . Let v (z i 0 ) be such a value. We dene Fγ,+ (resp. Fγ,-) to be the set of functions f γ,+ (resp. f γ,-) belonging to a pair associated with (z i 0 , v (z i 0 )). By construction, their common cardinality is bounded from below by: Fγ,+ = Fγ,-Fγ 3M γ n .

(48)

Let Ḡ+ and Ḡbe two subsets of Ḡ in bijection with Fγ,+ and Fγ,respectively, such that Fγ,+ = ρ Ḡ+ ,γ s Z n (η)

and Fγ,-= ρ Ḡ-,γ s Z n

(η)

. Let F+ = ρ Ḡ+ S(s Z n ) (η)

and

F-= ρ Ḡ-S(s Z n ) (η)
. According to Lemma 14, the sets F+ and Fsatisfy:

     ∀f + ∈ F+ , f + (z i 0 ) -b i 0 1 ∀f -∈ F-, max k =y i 0 f -(x i 0 , k) + b i 0 1 (49) with b i 0 = v (z i 0 ) -1. Let F = ρ Ḡ S(s Z n ) (η)
. Since F+ F-⊂ F, obviously, any pair strongly G-shattered by either F+ or Fis also strongly G-shattered by F.

where the function returns the number of leaves of the (sub)tree whose root is its argument. Thus, nishing the proof boils down to exhibiting the appropriate lower bound on Fγ . To that end, we proceed by induction on the depth of the node. The hypothesis is that Fγ Fγ

1 log 2 (3Mγ n) . (51)
It is obviously true for the leaves (which are of cardinality 1). Suppose now that it is true for the two sons of an inner node. Then, Inequality (48) gives:

Fγ = Fγ,+ + Fγ,- 2 Fγ 3M γ n 1 log 2 (3Mγ n) = Fγ 1 log 2 (3Mγ n) .
The induction hypothesis has been proved. Combining Inequalities (47), ( 50) and ( 51)

produces by transitivity:

|F γ | 1 log 2 (3Mγ n) Σ, or equivalently |F γ | Σ log 2 (3Mγ n) = (3M γ n) log 2 (Σ) ,
i.e., Inequality (46), the result announced.

With Lemma 15 at hand, the proof of Lemma 5 is straightforward.

Proof. Let us consider any vector z n ∈ Z n and let s Z n = {z i : 1 i n} be the smallest subset of Z containing all the components of z n . Note that its cardinality can be strictly inferior to n, in case that z n has two identical components. By denition,

M ( , ρ G,γ , d ∞,zn ) = M , ρ G,γ | s Z n , d ∞,zn .
Furthermore, setting η = 2 in (40), one obtains:

M , ρ G,γ | s Z n , d ∞,zn M 2, ρ G,γ | s Z n ( 2 ) , d ∞,zn . Let S (s Z n ) = {(x i , k) : (i, k) ∈ 1; n × 1; C }. The packing numbers of ρ G,γ | s Z n ( 2 )
can be upper bounded thanks to Lemma 15, leading to

M 2, ρ G,γ | s Z n ( 2 ) , d ∞,zn 6γn log 2 (Σ) (52)
where Σ =

d G u=0 n u 2γ u with d G being the maximal cardinality of a subset of s Z n strongly G-shattered by ρ G | S(s Z n ) ( 2 )
. According to (43a),

d G S-G-dim ρ G | S(s Z n ) ( 2 ) 4 -G-dim ρ G | S(s Z n ) d G 4 .
the hypothesis on the variance, is M -M T 2 and M T 2, we focus on it in the sequel.

Let us dene the sequences (β k ) k∈N * and (β k ) k∈N * as follows:

∀k ∈ N * ,      β k = P {T M T + k} β k = P {T M T -k} .
Note that by denition of M T , both β 1 and β 1 are inferior or equal to 1 2 . Assume that the conclusion of the lemma fails. We claim that

     ∀k ∈ 2; M -M T , β k max 2(M -M T )-k+1 (M -M T ) 3 , 1 2 k ∀k ∈ 2; M T , β k max 2M T -k+1 M 3 T , 1 2 k . Indeed, assume that β k > max 2(M -M T )-k+1 (M -M T ) 3 , 1 2 k
for some k ∈ 2; M -M T and let k 0 be the smallest such index. By construction,

β k 0 > max 1 2 β k 0 -1 , 1 (M -M T ) 2 (even for k 0 = 2 and k 0 = M -M T ), so that      P {T M T + k 0 } = β k 0 > max 1 2 β k 0 -1 , 1 M 2 P {T M T + k 0 -2} = 1 -P {T M T + k 0 -1} = 1 -β k 0 -1 . Since β k 0 -1 β k 0 > 1 M 2 and β k 0 -1 β 1 1 2 , so that β k 0 -1 ∈ 1 M 2 , 1
2 , this implies that the conclusion of the lemma would hold with α being M T + k 0 -1 and β = β k 0 -1 , which contradicts the assumption that the conclusion of the lemma fails. The inequality

β k max 2M T -k+1 M 3 T , 1 2 k
can be proved in a symmetrical way. As a consequence, upper bounding the maxima by the corresponding sums gives:

Var [T ] = Var [T -M T ] E (T -M T ) 2 = +∞ t=0 P (T -M T ) 2 > t = +∞ t=0 P T > M T + √ t + P T < M T - √ t = M -M T k=1 (2k -1) β k + M T k=1 (2k -1) β k < 2 +∞ k=1 2k -1 2 k + M -M T k=2 (2k -1) 2 (M -M T ) -k + 1 (M -M T ) 3 + M T k=2 (2k -1) 2M T -k + 1 M 3 T 6 + 2 max ∆∈N\{1,2} (8∆ + 11) (∆ -1) 6∆ 2 < 9.
(α, β) ∈ 1; M F -1 × 1 M 2 F , 1 2 such that      |{f ∈ F : f (t i 0 ) α + 1}| max 1 2 β, 1 M 2 F |F| |{f ∈ F : f (t i 0 ) α -1}| (1 -β) |F| or (α , β ) ∈ 1; M F -1 × 1 M 2 F , 1 2 such that      |{f ∈ F : f (t i 0 ) α + 1}| (1 -β ) |F| |{f ∈ F : f (t i 0 ) α -1}| max 1 2 β , 1 M 2 F |F| .
Proof. Let us endow F with the uniform (counting) measure. Then, the separation assumption on F can be used to derive a lower bound on E d 2 2,tn (f, f ) . Indeed, with probability 1 -|F| -1 we have f = f and, whenever this event occurs, d 2,tn (f, f ) 6. As a consequence,

E d 2 2,tn f, f 1 -|F | -1 36 18.
Furthermore,

E d 2 2,tn f, f = 1 n n i=1 E f (t i ) -f (t i ) 2 = 2 n n i=1 Var [f (t i )] .
Thus, there exists i 0 ∈ 1;

n such that Var [f (t i 0 )] 1 2 E d 2 2,tn f, f 9.
This implies that the random variable f (t i 0 ) satises the hypotheses of Lemma 16, and the conclusion then springs from the application of this lemma.

Lemma 17 will be used in the proof of the combinatorial result involving the margin Natarajan dimension: Lemma 8. However, we established it in this section, because its proof can be easily simplied to produce the following variant, appropriate the margin Graph Lemma 18. Let T = {t i : 1 i n} be a nite set and t n = (t i ) 1 i n . Suppose that F ⊂ Z T is of cardinality at least 2 and is 5-separated in the pseudo-metric d 2,tn . Then there exist an index i 0 ∈ 1; n and either (α, β)

∈ Z × 0, 1 2 such that      |{f ∈ F : f (t i 0 ) α + 1}| 1 2 β |F| |{f ∈ F : f (t i 0 ) α -1}| (1 -β) |F| or (α , β ) ∈ Z × 0, 1 2 such that      |{f ∈ F : f (t i 0 ) α + 1}| (1 -β ) |F| |{f ∈ F : f (t i 0 ) α -1}| 1 2 β |F| .
The following lemma is the basic combinatorial result underlying Lemma 6. Proof. The principle of the proof is the one of the proof of Lemma 15. Two of the three main formulas still apply: Inequalities (47) and (50). For |F γ | 2, the incidence of the change of pseudo-metric is concentrated in the derivation of the 2-separating tree of F γ , and thus the lower bound on (F γ ). Since the inner nodes Fγ are 5-separated in the pseudo-metric d 2,zn , then according to Lemma 18, for each of these nodes, we can ensure that there exists β ∈ 0, 1 2 such that the two sons Fγ,+ and Fγ,verify either Fγ,+ (1 -β) Fγ and Fγ,-1 2 β Fγ or vice versa (in place of (48)). As a consequence, the counterpart of (51) is:

Fγ Fγ (

) 55
where Σ = d N u=0 n u M u γ (C -1) u with M γ = γ η and d N is the maximal cardinality of a subset of s Z n strongly N-shattered by F.

Proof. Inequality (68) is trivially true for |F γ | = 1. Indeed, the minimal value of its righthand side, corresponding to d N = 0, is 1. Thus, the rest of the proof makes use of the restriction |F γ | 2. A direct consequence is that according to Lemma 14, d N 1. A subset of s Z n of cardinality u ∈ 1; n is denoted by s Z u = {z i : 1 i u}, with the convention ∀ (i, j) : 1 i < j u, z i , z j = (z v , z w ) =⇒ 1 v < w n. In order to derive a lower bound on the same quantity, we also build a 2-separating tree of F γ . Let Fγ = ρ Ḡ,γ s Z n (η) be one of its nodes such that Fγ 2 (inner node).

Its two sons, Fγ,+ and Fγ,-, are built by application of Lemma 17 and the pigeonhole principle. According to Lemma 17, we can ensure that there exist an index i 0 ∈ 1; n , Let Ḡ+ be a subset of Ḡ in bijection with Fγ,+ such that Fγ,+ = ρ Ḡ+ ,γ s Z n . Let Ĝbe a subset of Ḡ in bijection with Fγ,such that Fγ,-= ρ Ĝ-,γ s Z n (η)

and let F-= ρ Ĝ-S(s Z n ) (η)
. Setting b i 0 = α, it springs from Lemma 14 that 49) is obtained with Freplaced with F-. There comes the application of the pi- geonhole principle, to obtain Inequality (66). The derivation of the corresponding function classes is as follows. There exists c i 0 ∈ Y \ {y i 0 } such that among the functions g -in

     ∀f + ∈ F+ , f + (z i 0 ) -b i 0 1 ∀f -∈ F-, max k =y i 0 f -(x i 0 , k) + b i 0 1 , i.e., (
The transition between covering and packing numbers is provided by a well-known equivalence.

Lemma 22. Let (E, ρ) be a pseudo-metric space. For every bounded set E ⊂ E and ∈ R + , M (2 , E , ρ) N int ( , E , ρ) M ( , E , ρ).

The optimization of the dependence on C calls for the use of an extension of Theorem 1 in Mendelson and Vershynin holding for the L p -norms with p ∈ N \ {0, 1} (instead of simply p = 2): Theorem 10 in [START_REF] Mendelson | A few notes on statistical learning theory[END_REF]. The following lemma explicits the value of its constants (absolute or depending on p).

Lemma 23 (After Theorem 2 in [START_REF] Musayeva | Rademacher complexity and generalization performance of multi-category margin classiers[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 uGC class. For ∈ (0, M F ], let d ( ) = -dim (F). Then for ∈ (0, 2M F ], n ∈ N * and p ∈ N \ {0, 1},

M p ( , F, n) 12M F p 1 7 10pd 36p
.

With Proposition 5, Lemma 22 and Lemma 23 at hand, one single formula is needed to establish Lemma 9: a structural result for N int p ( , ρG , n). Proving that Lemma 2 still holds true with ρ G replaced with ρG is straightforward. Consequently, the proof of Lemma 9 is the following one. (83)

A of ( 83) into (82) then concludes the proof.

Upper Bound on the Rademacher Complexity

The proof of Theorem 3 is the following one.

Proof. In all three cases, the starting point is Inequality (28).

First case: d G,γ ∈ (0, 2)

This case is the only one for which the entropy integral exists. Setting for every j ∈ N,

h (j) = γ2 -2 2-d G,γ j , we obtain R m (ρ G,γ ) 8 1 + 2 2 2-d G,γ F 1 (C) m γ 1- d G,γ 2

  tn and M , F, d p,tn respectively denote the -covering number and the -packing number of F with respect to d p,tn . N p , F, n and M p , F, n are the corresponding uniform covering and packing numbers. N int and N int p are used to denote proper covering numbers. The binary logarithm of the covering number of a set is called its metric entropy. The scale-sensitive combinatorial dimensions used are γ-Ψ-dimensions,

  Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. Then for every γ ∈ (0, M G ],

  ), the central formula is the upper bound on the metric entropy. With the combinatorial and structural results of the preceding section at hand, two new formulas are required to compare the functions F f resulting from the use of the margin Natarajan dimension to those resulting from following a dierent path in the graph of Figure 1. The rst one is an upper bound on the γ-dimensions of the classes G k as a function of the scale parameter . The second one is an upper bound on the margin Natarajan dimension of ρ G as a function of C and .

  The possibility to sharpen it for specic classiers remains an open question. A partial conclusion emerges: as soon as some features of the classier of interest can be exploited, then the best guaranteed risks involving a scale-sensitive combinatorial dimension of ρ G (associated with a blue path of Figure2), are obtained with the margin Natarajan dimension (rather than the fat-shattering dimension or the margin Graph dimension). With this observation at hand, the last promising alternative is the use of the structural result involving covering numbers (Lemma 2), in conjunction with the state-of-the-art combinatorial results

  previous dependence was a O γ - d G,γ 2 ln (γ -1 ) . Regarding the dependence on the number C of categories, it is now a O C d G,C 2

  γ-N-shattered by F. The function h exhibits two major properties which play a central part in the derivation of the upper bound on d G .

  solution consists in setting b n = η b i + 1 2 1 i n . The same line of reasoning can be used to prove (43b). In short, if (b n , c n ) is a witness to the strong N-shattering, then (b n , c n ) is a witness to the η 2 -N-shattering, where the vector b n is deduced from b n as above and c n = c n . Lemma 14. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Denition 5. Suppose that there exist

  shatters the same pair and strongly N-shatters the triplets ({z} , b, c).

  . The strong Nshattering of ({z} , b, c) springs from (45) and the denition of c.

  What made possible this inversion of the inequality is the introduction of the squashing function π γ . This basic observation highlights the fact that this operator plays a central part in our thesis stating the usefulness of the γ-Ψ-dimensions. The denition of the bias b is coherent with the restriction of the domain of the vectors b n to the positive hyperoctant.

  possibly a function remaining alone). For each pair

  Furthermore, according to (49), F strongly G-shatters the pair ({z i 0 } , b i 0 ) which is strongly G-shattered by neither F+ nor F-. At last, let us consider any pair (s Z u , b u ) strongly G-shattered by both F+ and F-. Let the pair s Z u+1 , b u+1 be such that s Z u+1 = s Z u {z i 0 } and the vector b u+1 is deduced from b u by inserting the component b i 0 at the right place.Clearly, neither F+ nor Fstrongly G-shatters s Z u+1 , b u+1 , simply because they do not strongly G-shatter the pair ({z i 0 } , b i 0 ). On the contrary, it springs once more from (49) that s Z u+1 , b u+1 is strongly G-shattered by F. Summarizing, for each pair (s Z u , b u ) strongly G-shattered by both F+ and F-, we can exhibit by means of an injective mapping a pair s Z u+1 , b u+1 strongly G-shattered by F but not by F+ or F-. Collecting all terms,

Lemma 19 .

 19 Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function classdeduced from G according to Denition 5. For G ⊂ G, s Z n = {z i = (x i , y i ) : 1 i n} ⊂ Z, γ ∈ (0, 1] and η ∈ 0, γ 2 , let F γ = ρ G,γ s Z n (η) and let F = ρ G S(s Z n ) (η) with S (s Z n ) = {(x i , k) : (i, k) ∈ 1; n × 1; C }. If F γ is 5-separated in the pseudo-metric d 2,zn , then |F γ | Σ 2, γ with M γ = γ η and d G is the maximal cardinality of a subset of s Z n strongly G-shattered by F.

For

  every subset Ḡ of G, denote by s Ḡ the number of triplets (sZ u , b u , c u ) with s Z u ⊂ s Z n , b u ∈ 1; M γ -1 u and c u ∈ Y n (with ∀i ∈ 1; n , c i = y i ) strongly N-shattered by F = ρ Ḡ S(s Z n ) (η)(the convention above has been introduced to avoid handling duplicates).Since d N 1, Inequality (64) provides us once more with an upper bound on s G .

  subsets Fγ,+ and Fγ,of Fγ verifying either Fγ,+(1 -β) Fγ and Fγ,+ ∈ Fγ,+ , f γ,+ (z i 0 ) α + 1∀f γ,-∈ Fγ,-, f γ,-(z i 0 ) α -1.



  Proof. Applying in sequence Proposition 5, Lemma 22 (left-hand side inequality), Lemma 2 (applied to ρG ), Lemma 22 (right-hand side inequality) and Lemma 23 gives:∀γ ∈ (0, M G ] , γ-dim (ρ G ) 10K p p log 2 (G k ) . Let us set p = log 2 (C) (which is possible since C 3 implies p 2). Then, C 1 p 2, so that for every γ ∈ (0, M G ], γ-dim (ρ G )10K log 2 (C) log 2 (2C) log 2

  set h (j) = γ log 2 (m)

  . Talagrand. Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems. Springer-Verlag, Berlin Heidelberg, 2014. A.W. van der Vaart and J.A. Wellner. Weak Convergence and Empirical Processes, With

	Applications to Statistics. Springer Series in Statistics. Springer-Verlag, New York, 1996.
	V.N. Vapnik. Statistical Learning Theory. John Wiley & Sons, Inc., New York, 1998.
	V.N. Vapnik and A.Ya. Chervonenkis. On the uniform convergence of relative frequencies of
	events to their probabilities. Theory of Probability and its Applications, XVI(2):264280,
	1971.
	G. Wahba. Multivariate function and operator estimation, based on smoothing splines
	and reproducing kernels. In M. Casdagli and S. Eubank, editors, Nonlinear Modeling
	and Forecasting, SFI Studies in the Sciences of Complexity, volume XII, pages 95112.
	Addison-Wesley, 1992.

This holds true both with the L ∞ -norm (Inequality (

23

)) and the L 2 -norm (Theorem 3). As soon as it is possible to take into account the coupling between the component functions of the classier, i.e., for d G,C < 2, the dependence on the number C of categories becomes sublinear. The only drawback is that the convergence rate of the L 2 -norm bound can be worsened by a factor ln (m) when the underlying binary classiers are complex (large values of d G,γ ). The phenomenon is a direct consequence of the appearance of the logarithmic function of γ in the exponent of Inequality (13) (compared to Inequality (11)). Whether this term can be replaced with a logarithmic function of C only is an open question which is the subject of an ongoing research. Regarding the structural results, a promising idea for their improvement is the one recently developed by Kontorovich (see for instance

[START_REF] Kontorovich | Rademacher complexity of k-fold maxima of hyperplanes[END_REF]

. M

  This is in contradiction with the hypothesis that Var[T ] 9 and thus concludes the proof.Lemma 17. Let T = {t i : 1 i n} be a nite set and t n = (t i ) 1 i n . Let F be a class of functions from T into 0; M F with M F 2. Suppose that F is of cardinality at least 2 and is 6-separated in the pseudo-metric d 2,tn . Then there exist an index i 0 ∈ 1; n and either

Acknowledgements The author would like to thank R. Vershynin for his explanations on the proof of Theorem 1 in Mendelson and Vershynin (2003). This work was partly funded by a CNRS research grant (PEPS).

Let s

(2) Z r-1 = s

(1) Z r \ {z i 0 }. By construction, s

(2) Z r-1 ∈ S F+ S F-. Clearly, F γ-Nshatters all the triplets s

(3)

u , c

(3) u with s

(3)

Z r-1 γ-N-shattered by either F+ or Fplus ({z i 0 } , b i 0 , c i 0 ). Moreover, if the triplet s

(3)

u , c

(3) u is γ-N-shattered by both F+ and F-, then F γ-N-shatters the triplet s (4)

u+1 , c

u+1 deduced from s

(3)

u , c

(3) u by inserting the components of ({z i 0 } , b i 0 , c i 0 ) at the right place. Since by construction, s

Z u+1 ⊂ s

(1) Z r and s (4)

(2) Z r-1 , it follows that:

Since by hypothesis, n d G 4 , Σ can be bounded from above by replacing in its formula d G with d G 4 and resorting to Corollary 3.3 in Mohri et al. (2012), leading to:

where the standard convention that the last term takes the value 1 for d G 4 = 0 is made. Substituting (53) into ( 52) and taking the supremum over Z n concludes the proof of (10).

B.3

Margin Graph Dimension -L 2 -norm

The sketch of the proof of the two L 2 -norm combinatorial results, Lemma 6 and Lemma 8, is basically the same. Compared to the sketch of the proof of Lemma 5, it exhibits two major dierences. First, the construction of the 2-separating tree is more sophisticated, since it rests on a small deviation principle (in place of the sole pigeonhole principle). Second, one additional step is involved, which implements a probabilistic extraction principle. This additional step makes the result dimension free. We begin the proof with the formulation of the small deviation principle. This extension of Lemma 5 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] is tailored to our needs.

Lemma 16. Let T be a random variable taking values in 0; M with M 2. Suppose that Var [T ] 9. Then there exists either (α,

Proof. We rst note that the hypothesis Var [T ] 9 implies that M 6. Let M T be the smallest median of T belonging to 0; M . Then, several cases must be distinguished, according to the values of M T and M -M T . Since they can all be treated the same and the one implying the largest upper bound on the variance, i.e., the one from which springs Once more, the proof is an induction on the of the node. Inequality ( 55) is obviously true for the leaves are of cardinality 1). Suppose now that it is true for the two sons of an inner node. Then,

Finally, combining Inequalities ( 47), ( 50) and ( 55) produces ( 54) by transitivity.

The following lemma, a slight improvement of Lemma 13 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], implements the probabilistic extraction principle.

Lemma 20. Let T = {t i : 1 i n} be a nite set, Then, there exists a subvector t q of t n of size q r such that F is 2 -separated with respect to the pseudo-metric d 2,t q .

Proof. This proof uses an abuse of notation that will be repeated in the sequel: the symbol P designates dierent probability measures, some of which implicitly dened. We rst note that the statement is trivially true for r n (it suces to set t q = t n ). Thus, we proceed under the hypothesis r ∈

Then, by application of the -separation property, for every

Since by construction, for every i ∈

F with probability one, the right-hand side of (56) can be bounded from above thanks to Bernstein's inequality. Given that

Therefore, given the assumption on r, applying the union bound provides us with:

Moreover, if S 1 is the random set {i ∈ 1; n : i = 1}, then by Markov's inequality,

Combining ( 57) and ( 58) by means of the union bound provides us with

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 2 -separated with respect to the pseudo-metric d 2,t q , i.e., our claim.

The proof of Lemma 6 is the following one.

Proof. Let us consider any vector z n Z n and let s Z n = {z i : i n} be the smallest subset of Z containing all the components of z n . Note that its cardinality can be strictly inferior to n, in case that z n has two identical components. Let G be a subset of G of cardinality M ( , ρ G,γ , d 2,zn ) such that ρ G,γ s Z n is -separated with respect to d 2,zn and in bijection with G. By application of Lemma 20 with F = ρ G,γ s Z n

, corresponding to K e = 3 112γ 4 , there exists a subvector z q of z n of size

is 2 - separated with respect to the pseudo-metric d 2,z q . Applying (39) with F = ρ G,γ s Z q , N = 5 and the corresponding largest possible value for η, 12 , it appears that the set

is 5-separated with respect to the pseudo-metric d 2,z q . Consequently, Lemma 19 applies to this latter function class, whose cardinality is by construction that of G. It gives:

where d G is the maximal cardinality of a subset of s Z q strongly G-shattered by ρ G S(s Z q ) ( 12 )

.

A substitution of the upper bound on q provided by ( 59) into (60) gives:

, we resort once more to (38), this time with u 0 = 1. Thus,

, which makes it possible to apply Formula (43a),

By substitution of ( 62) into (61), we obtain that for every vector 24) .

(

At last, ( 63) implies ( 11) since its right-hand side does not depend on z n .

B.4 Margin Natarajan Dimension -Uniform Convergence Norm

The proof of Lemma 7 is essentially that of Lemma 5, with the main dierences being concentrated in the basic combinatorial result (the counterpart of Lemma 15). Thus, we only highlight these dierences.

In order to obtain the counterpart of (50), i.e.,

(49) must be replaced with

This calls for an additional application of the pigeonhole principle in the derivation of Fγ,and F-, so that the right-hand side of ( 48) is replaced Fγ,-Fγ 3M (C -1) n .

This implies that the counterpart of ( 51) is

Fγ Fγ

Once more, it is proved by induction on the depth of the node. Inequality ( 67) is obviously true for the leaves (which are of cardinality 1). Suppose now that it is true for the two sons of an inner node. Then,

Combining Inequalities (64), ( 65) and ( 67), the counterpart of Inequality ( 46) is

.

B.5

Margin Natarajan Dimension -L 2 -Norm

The main dierence between the proof of Lemma 8 and the proof of Lemma 6 is located in the small deviation principle (Lemma 17 replaces Lemma 18). Since the consequences of this change appear in the derivation of the basic combinatorial result, we provide this latter result with its full proof.

Lemma 21. Let G be a function class satisfying Denition 1 and ρ G the function class deduced from G according to Denition 2. For γ ∈ (0, 1], let ρ G,γ be the function class

Ĝ-, at least

We choose Ḡto be any such subset of Ĝand let Fγ,-= ρ Ḡ-,γ s Z n (η)

and

. With Inequality (66) at hand, Inequality ( 65) is also available. Thus, nishing the proof still boils down to deriving a lower bound on

Fγ . The originality rests on the fact that two cases must be considered, to take into account the two sources of asymmetry between the cardinalities of Fγ,+ and Fγ,-. Indeed, we have either Fγ,+ max 1 2 β, 1

Fγ,-

Fγ . The induction hypothesis is this time:

Once more, it is obviously true for the leaves. We prove it for the rst case (the other one is treated in the same way). Then,

Combining Inequalities (64), ( 65) and (69) produces by transitivity:

thus concluding the proof.

The proof of Lemma 8 is the following one.

Proof. The beginning of the proof is identical to the beginning of the proof of Lemma 6 up to the use of the basic combinatorial result (where Lemma 21 replaces Lemma 19).

where d N is the maximal cardinality of a subset of s Z q strongly N-shattered by ρ G S(s Z q ) ( 14 )

.

A substitution of the upper bound on q provided by ( 59) into (70) gives:

with K = 1568 3 e. In order to upper bound ln G

, we resort once more to (38), with

Due to the construction of ρ G S(s Z q ) ( 14 )

, which makes it possible to apply Formula (43b),

A substitution of ( 72) into ( 71) produces an upper bound on M ( , ρ G,γ , d 2,zn ) which does not depend on z n , thus concluding the proof.

C Proofs of the Structural Results

This appendix gathers the proofs the upper bounds on the combinatorial dimensions of ρ G (and ρG ) as a function of the fat-shattering dimensions of classes including the classes

), the proof of Lemma 9 is actually provided for the latter dimension. It makes use of three partial results which are now stated. Proposition 5 is an extension of Proposition 1.4 in [START_REF] Talagrand | Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions[END_REF] holding for the L p -norms with p ∈ N\{0, 1}

(instead of simply p = 2), that explicits the value of the constant.

Proposition 5. Let F be a class of real-valued functions on T . For every γ ∈ R *

a witness to this shattering. By denition, there exists a subset F = {f sn :

Let t n = (t i ) 1 i n . To prove the proposition, it suces to establish that

Then, making use of (73), we obtain that

, where H stands for the Hamming distance. Thus, a sucient condition for d p,tn f sn , f s n

p n . As a consequence, to prove (74), it suces to establish that there is a subset of the set of vertices of the hypercube

which is 1 2

p n -separated with respect to the Hamming distance (the separation is well-dened since 2

n Kp

2). To that end, a probabilistic approach similar to that of the proof of Lemma 20 is implemented. For q ∈ 2; 2 n , let q,n = ( j,i ) 1 j q,1 i n be a Bernoulli random matrix (its entries j,i are independent Bernoulli random variables with common expectation 1 2 ). Then, by application of the union bound, P ∃ j, j ∈ 1; q 2 : 1 j < j q and n i=1

where ( i ) 1 i n is a Bernoulli random vector. To upper bound the tail probability on the right-hand side, we resort to Hoeding's inequality, which gives

By transitivity, this implies that a sucient condition for P ∃ j, j ∈ 1; q 2 : 1 j < j q and n i=1

, which is precisely the value announced and thus concludes the proof.

C.2 Margin Natarajan Dimension of ρ G

The proof of Lemma 10 is the following one.

Proof. Suppose that for γ ∈ (0, M G ], the triplet (s Z , b n , c n is γ-N -shattered by ρ G . According to Proposition 4, in order to upper bound n, i.e., γ-N-dim (ρ G ), one can assume that for every i ∈ 1; n , y i < c i , and the biases can be negative. Let Ḡ = {g sn : s n ∈ {-1, 1} n } be a subset of G (of minimal cardinality) such that ρ Ḡ = {ρ g sn :

For every pair (k, l) ∈ 1; C 2 satisfying k < l, let S k,l be the subset of 1; n dened as follows:

S k,l = {i ∈ 1; n : y i = k and c i = l} and let n k,l ∈ 0; n be its cardinality. By construction, P = {S k,l : n k,l > 0} is a partition of 1; n . For every vector s n = (s i ) 1 i n ∈ {-1, 1} n , the function g sn satises:

∀i ∈ 1; n ,

For a xed S k,l ∈ P, this implies that ∀i ∈ S k,l , s i 1 2 g sn k (x i ) -g sn l (x i ) -b i γ.

Let D G,k,l = 1 2 (g k -g l ) : g ∈ G . By denition, we have established that its subset Summing over all the elements of the partition P gives

Proceeding as in the proof of Lemma 2, we get

To nish the proof of ( 16), it suces to apply Lemma 22 (right-hand side inequality) and Theorem 1 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. Indeed, this produces:

The proof of Lemma 11 makes use of that of Theorem 4.6 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classiers[END_REF].

Proof. This proof reuses the notations of the proof of Lemma 10, with G being instantiated by H Λ . By application of Lemma 4.3 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classiers[END_REF], there exists a

where the sets S + k,l and S - k,l are dened as follows:

∀S k,l ∈ P,

For a xed S k,l ∈ P, applying the reproducing property gives

Let us specify the vector s n in the following way: ∀i ∈ S k,l , s i = s i . By summation over i ∈ S k,l , it results from (77) that:

Conversely, consider any vector s n such that: ∀i ∈ S k,l , s i = -s i . Then,

As a consequence, if (82)