Khadija Musayeva

Fabien Lauer

Yann Guermeur

Rademacher Complexity and Generalization Performance of Multi-category Margin Classifiers

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Although the theory of binary pattern classification is well established [START_REF] Vapnik | Statistical Learning Theory[END_REF][START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF], the theory of multicategory classification is far from being complete. The research in this case addresses problems such as the sample-complexity analysis of empirical risk minimization algorithms [START_REF] Daniely | Multiclass learnability and the ERM principle[END_REF], or consistency analysis of multi-class loss functions and of specific families of classifiers [START_REF] Dogan | A unified view on multi-class support vector classification[END_REF]. Another open question is the optimal dependency of guaranteed risks of multi-category classifiers on the number C of categories and the sample size m. It is all the more the case for the problems that involve a large number of classes. When the considered classifiers are margin ones that take decision based on a score per category, the dependency on the margin parameter γ also becomes relevant to the characterization of their generalization performance. If this question has been mainly studied for specific families of classifiers, be it k-nearest neighbors [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF], kernel methods [START_REF] Zhang | Statistical analysis of some multi-category large margin classification methods[END_REF][START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF] and decision trees [START_REF] Kuznetsov | Multi-class deep boosting[END_REF], tackling it under minimal learnability assumptions remains a challenging task. This paper focuses on obtaining guaranteed risks under such assumptions.

The first step in the derivation of risk bounds is the choice of the margin loss function. Two families of margin loss functions can be distinguished: indicator margin loss functions and those that satisfy the Lipschitz condition. Deriving guaranteed risks with the optimal dependency on the parameters of interest is relatively straightforward in the first case [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. The family of Lipschitz continuous loss functions, on the other hand, offers a richer setting to this task. In this case, one can obtain a guaranteed risk whose control term involves a Rademacher complexity [START_REF] Koltchinskii | Empirical margin distributions and bounding the generalization error of combined classifiers[END_REF]. Then a sequence of transitions between capacity measures is performed. More precisely, using the chaining method one can control the Rademacher complexity of a function class through the sum of its metric entropies [START_REF] Talagrand | Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems[END_REF]. A combinatorial bound is then used to estimate the metric entropy of the class in terms of its combinatorial dimension. In this sequence of transitions, one can choose the capacity measure at the level of which to reduce the multi-class problem to an ensemble of bi-class ones, that is, to perform a decomposition. Performing a decomposition for Rademacher complexity, a linear dependency on C was obtained in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]. This dependency has been improved to a sublinear one in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] by postponing the decomposition to the level of metric entropy.

In this paper, we exactly follow the pathway of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. Our contribution is based on the following line of reasoning. Theorem 7 of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] provides a sublinear (but still close to linear) dependency on C using a decomposition result for metric entropies (Lemma 1 of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]) in L p -norm with p = 2 and the combinatorial metric entropy bound of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. On the other hand, using the decomposition result with p = ∞ and the L ∞ -norm metric entropy bound of [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF], one can obtain a radical dependency on C, this, however, at the expense of a degraded dependency on m. Hence, we consider the values of p in between these two extreme ones, and extend the L 2 -norm bound of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] to L p -norms with integer p > 2. When applied in the chaining, it results in an improved dependency on C over that of Theorem 7 of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. Specifically, we obtain a radical dependency on C (up to logarithmic factors) without worsening the dependencies on m and γ.

The organization of the paper is as follows. In the next section, we introduce the theoretical framework and describe the transitions between the capacity measures. Then, Section 3 gives the new combinatorial metric entropy bound, whose proof can be found in A. In Section 4, we demonstrate how this result can be applied in the chaining to derive an improved upper bound on the Rademacher complexity. Conclusions and ongoing research are highlighted in Section 5. All intermediate results used in the proofs are collected in B.

Notation

We denote the set of strictly positive reals by R + , and let

N * = N \ {0}. [ [ i, j ] ] stands
for the set of integers from i to j. 1 A stands for the indicator function for the event A such that 1 A = 1 if A occurs, and 0 otherwise. ⌊x⌋ is the greatest integer less than or equal to x, ⌈x⌉ is the smallest integer greater than or equal to x.

Theoretical Framework

We consider C-category pattern classification problems with C 3. Each object is represented by its description x ∈ X and the categories y belong to Y = [ [ 1, C ] ]. We assume that (X , A X ) and (Y, A Y ) are measurable spaces. Denote by A X ⊗ A Y the product sigma-algebra on X × Y.

We assume that the link between descriptions and categories can be characterized by an unknown probability measure P on the measurable space (X × Y, A X ⊗ A Y ). Let Z = (X, Y ) be a random pair with values in Z = X × Y, distributed according to P . The available information on P is

limited to an m-sample Z m = (Z i ) 1 i m = ((X i , Y i ))
1 i m distributed according to P m . In the following, we distinguish the sample size m from the generic notation n which stands for a number of points in a set that needs not be a realization of a random sample.

We consider multi-category margin classifiers that take their decisions based on a score per category and focus on those that implement classes of functions with values in a hypercube of R C (thus, in contrast to [START_REF] Lei | Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms[END_REF], no correlation assumption is made on the component functions).

Most well-known classifiers, such as neural networks [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF], support vector machines [START_REF] Dogan | A unified view on multi-class support vector classification[END_REF], and nearest neighbors [START_REF] Kontorovich | Maximum margin muliclass nearest neighbors[END_REF] are margin classifiers.

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

To sidestep the complications that might arise from the measurability of a supremum of an uncountable set, we assume that the classes G k , and in general, all sets of functions considered in the sequel satisfy the "image admissibility Suslin" condition [15, page 101].

The classification performance of margin classifiers can be characterized based on the following functions.

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

f g : Z → [-M G , M G ] is ∀(x, k) ∈ Z, f g (x, k) = 1 2 g k (x)-max l =k g l (x) .
Then, we define F G = {f g : g ∈ G} .

Given g ∈ G, dr g misclassifies (x, y) if dr g (x) = y, or equivalently, if f g (x, y) 0. The goal of the learning process is to minimize the probability of error or risk over G.

Definition 3 (Risk L). Let G be as in Definition 1. Let φ be the standard indicator loss function defined as

∀t ∈ R, φ(t) = 1 {t 0} .
For any g ∈ G, its risk L(g) is

L(g) = E Z [φ (f g (Z))] = P (dr g (X) = Y ) .
To make use of the values of functions f g (and not just of their signs) in the assessment of the classification performance, we appeal to the following margin loss function.

Definition 4 (Parameterized truncated hinge loss function φ γ ). For any γ ∈ (0, 1], the parameterized truncated hinge loss function φ γ is defined as

∀t ∈ R, φ γ (t) = 1 {t 0} + 1 - t γ 1 {t∈(0,γ]} .
It is clear from the definition that φ γ dominates the standard indicator loss function given in Definition 3 and that it is Lipschitz continuous. Observe that when this loss function is applied to f g , the values of the latter strictly above γ and below zero become irrelevant to the estimation of the classification accuracy. Taking benefit from this fact, we introduce functions f g,γ by restricting the codomain of f g to [0, γ] for all g ∈ G. In [START_REF] Kuznetsov | Multi-class deep boosting[END_REF], a partial restriction is the main source of improvement upon the result of [START_REF] Koltchinskii | Empirical margin distributions and bounding the generalization error of combined classifiers[END_REF] in terms of the dependency on C. The use of the set of functions f g,γ leads to even a finer bound, this time in terms of the diameter of the function class as we switch from 2M G to γ.

Definition 5 (Class F G,γ of truncated margin functions). Let F G be a class of functions satisfying Definition 2. Fix γ ∈ (0, 1]. For any f g ∈ F G , we define f g,γ : Z → [0, γ] as

∀(x, k) ∈ Z, f g,γ (x, k) = max(0, min (γ, f g (x, k))) ,
and F G,γ = {f g,γ : g ∈ G}.

For any g ∈ G, its risk, L(g) can be upper bounded by the margin risk L γ (g) obtained on the basis of the loss function φ γ . It is the m-sample Z m based estimate of L γ that appears in our guaranteed risk.

Definition 6 (Margin risk L γ and empirical margin risk L γ,m ). Let G be a class of functions satisfying Definition 1. Let φ γ be as in Definition 4. Then, for γ ∈ (0, 1], the margin risk L γ associated with any g ∈ G is

L γ (g) = E Z [φ γ (f g,γ (Z))] .
Its m-sample Z m based estimate is the empirical margin risk defined as

L γ,m (g) = 1 m m i=1 φ γ (f g,γ (Z i )) .
In what follows, we give the definitions of the capacity measures we use and outline the transitions between them, which are at the basis of the derivation of our result. We use F to denote a uniformly bounded class of functions on a generic measurable space (T , A T ). First, we recall the definition of the Rademacher complexity.

Definition 7 (Rademacher complexity). Let P T be a probability measure on (T , A T ) and T n = (T i ) 1 i n a sequence of independently distributed according to P T random variables with values in T . Let σ n = (σ i ) 1 i n be a Rademacher sequence, i.e.,a sequence of independent random variables uniformly distributed in {-1, +1}. Then, the empirical Rademacher complexity of F given T n is defined as

Rn (F ) = E σ n sup f ∈F 1 n n i=1 σ i f (T i ) T n
and its Rademacher complexity is R n (F ) = E Tn Rn (F ) .

The capacity measures central in the derivation of our result are covering/packing numbers.

Their definitions require the introduction of the following empirical pseudo-metrics: for any f, f ′ ∈ F and t n = (t i )

1 i n ∈ T n , d p,tn (f, f ′ ) =      1 n n i=1 |f (t i ) -f ′ (t i )| p 1 p , if p ∈ [1, +∞) max 1 i n |f (t i ) -f ′ (t i )| , if p = +∞.
Definition 8 (Covering numbers, metric entropy, packing numbers). The L p -norm ǫ-covering

number of F , N (ǫ, F , d p,tn ), is the smallest cardinality of the ǫ-nets of F , i.e., subsets F ⊆ F such that ∀f ∈ F there exists f ∈ F such that d p,tn (f, f ) < ǫ. The logarithm of N (ǫ, F , d p,tn ) is the metric entropy of F . A subset F of F is ǫ-separated with respect to d p,tn if, for any two distinct elements f, f ′ ∈ F , d p,tn (f, f ′ ) ǫ.
The ǫ-packing number of F , M (ǫ, F , d p,tn ), is the maximal cardinality of its ǫ-separated subsets. The uniform covering and packing numbers are

N p (ǫ, F , n) = sup tn∈T n N (ǫ, F , d p,tn )
and

M p (ǫ, F , n) = sup tn∈T n M (ǫ, F , d p,tn ) ,
respectively.

The capacity measures appearing last in our bounds are combinatorial dimensions. They provide useful information about whether the class of interest uniformly satisfies the classical limit theorems [START_REF] Dudley | Uniform central limit theorems[END_REF].

Definition 9 (Fat-shattering dimension [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF], strong dimension [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF]). For γ ∈ R + , a subset S = {t i : 1 i n} of T is said to be γ-shattered by F if there is a function v : S → R 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 (f sn (t i ) -v (t i )) γ.
The fat-shattering dimension of F at scale γ, γ-dim (F ), is the maximal cardinality of a subset of T γ-shattered by F , if such a maximum exists. Otherwise, γ-dim (F ) = ∞. For a class F of integer valued functions, the notion of strong dimension, S-dim (F ), is obtained from the definition of the fat-shattering dimension by setting γ = 1 and restricting the co-domain of v to Z.

As in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF][START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF][START_REF] Mendelson | The shattering dimension of sets of linear functionals[END_REF], we make the hypothesis that the fat-shattering dimensions of the classes G k , γ-dim (G k ), grow no faster than polynomially with γ -1 .

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

a pair (K G , d G ) ∈ R 2 + such that ∀ǫ ∈ (0, M G ] , max 1 k C ǫ-dim (G k ) K G ǫ -dG .
Among the well-known examples of classifiers that satisfy such an assumption are support vector machines with d G = 2 (Theorem 4.6 in [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF]) and feedforward neural networks with d G = 2l for l layers (Corollary 27 in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]). It should be noted that Lipschitz classifiers, such as nearest neighbours also satisfy this assumption as demonstrated by Corollary 4 in [START_REF] Gottlieb | Efficient classification for metric data[END_REF]. Depending on the growth rate d G , our assumptions regarding the data are summarized in Table 1.

Table 1: Assumptions made on the sample size m and the number of categories C with respect to the growth rate d G of the fat-shattering dimensions in Hypothesis 1.

Growth rate Assumptions

d G 2 m > C > 4 d G > 2 m C 1.2 , C > 4
Our starting point is the following basic supremum inequality that bounds the risk by the empirical margin risk plus a control term based on a Rademacher complexity.

Theorem 1 (Theorem 5 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]). Let G be a class of functions satisfying Definition 1. For γ ∈ (0, 1],

let F G,γ be the class of functions deduced from G according to Definition 2. For fixed γ ∈ (0, 1] and δ ∈ (0, 1), with P m probability at least 1δ,

∀g ∈ G, L(g) L γ,m (g) + 2 γ R m (F g,γ ) + ln( 1 δ ) 2m
.

We perform the following sequence of transitions between the capacity measures to derive our result. First, we relate the empirical Rademacher complexity of F G,γ to its metric entropy through the chaining method (see [START_REF] Talagrand | Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems[END_REF]). More precisely, we use the following formulation of the chaining bound due to [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]:

Rm (F G,γ ) h(N ) + 2 N j=1 (h(j) + h(j -1)) ln N (h(j), F G,γ , d 2,zm ) m , (1)
where N ∈ N * and h : N → R + is a decreasing function satifying h(0) γ. Next, using Lemma 1 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF], we decompose the metric entropy of F G,γ in terms of the ones of the classes G k :

∀p ∈ [1, +∞] , ln N (ǫ, F G,γ , d p,zm ) C k=1 ln N ǫ C 1/p , G k , d p,xm , (2)
where x m = (x i ) 1 i m ∈ X m . Finally, our combinatorial bound derived below gives an estimate on the metric entropies of the classes G k in terms of their fat-shattering dimensions.

L p -norm Combinatorial Metric Entropy Bound

We extend the L 2 -norm metric entropy bound of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] to L p -norms with p ∈ N * \ {1, 2}. The bound of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] does not depend on the sample size thanks to the use of the probabilistic extraction principle. In our extension we derive two bounds. In one of them, we keep the dependency on the sample size, and in the other, we remove it using the L p -norm generalization of the aforementioned principle. Under Hypothesis 1, depending on the value of d G , the application of one or the other bound in the chaining allows us to optimize the dependency on C while not degrading the ones on m and γ, as will be seen in Section 4.

Specifically, we have the following L p -norm metric entropy bounds, whose proof is given in A.

Theorem 2. Let F be a class of functions from T into [-M F , M F ] with M F ∈ [1, +∞). For ǫ ∈ (0, M F ], let d (ǫ) = ǫ-dim (F ). For all values of p ∈ N * \ {1, 2} and ǫ ∈ (0, M F ], (a) if n d ǫ 15p , then ln N p (ǫ, F , n) 2d ǫ 15p ln   15epnM F d ǫ 15p ǫ   ; (b) if n d ǫ 37p , then ln N p (ǫ, F , n) 10p d ǫ 36p ln 7p 1 7 M F ǫ .
From (2) one can see that, based on C

∈ (0, M G ], let d (ǫ) = max 1 k C ǫ-dim (G k ). Then, for ǫ ∈ (0, γ] and C > 4, ln N p (ǫ, F G,γ , m) 2Cd ǫ 30 log 2 (2C) ln 30en log 2 (2C) M G ǫ , (3)
and

ln N p (ǫ, F G,γ , m) 10C log 2 (2C) d ǫ 72 log 2 (2C) ln 14 log 1 7 2 (2C) M G ǫ . (4)
Proof. Inequality (3) follows from the application of (2) and part (a) of Theorem 2 (where we drop d(ǫ) from the denominator inside the logarithm as it is greater than one), along with the fact that C 1/⌈log 2 (C)⌉ < 2 and ⌈log 2 (C)⌉ < log 2 (2C). We obtain Inequality (4) in a similar way using part (b) of Theorem 2 instead.

As it was noted in [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF], under Hypothesis 1, the growth rate of the fat-shattering dimension has a dramatic effect on the behavior of the Rademacher complexity of the function class. The availability of two kinds of metric entropy bounds allows us to adapt to this impact in the chaining so as to optimize the dependency on C without worsening those on m and γ. Under the aforementioned hypothesis, two cases can be distinguished. For d G ∈ (0, 2), the formula (1) can be upper bounded by an integral and the use of the dimension-free bound (4) leads to the optimized result. For

d G 2
, such a result is obtained from the application of ( 3) in [START_REF] Vapnik | Statistical Learning Theory[END_REF]. The second case can also be characterized by the fact that there is a freedom in the choice of the number N of steps to construct the chaining. To optimize this construction when d G > 2, we make the non-restrictive assumption that m is greater than a small power of C.

Theorem 3. Let G be a class of functions as in Definition 1. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 2. Then, under Hypothesis 1, there is a function

K (γ, d G , K G ) such that for all C > 4, R m (F G,γ ) K (γ, d G , K G ) C m ×                  (ln(C)) d G 2 + 1 2 , if 0 < d G < 2, ln(C) ln m C ln 1 2 m ln 2 3 (C) C 1 3 , if d G = 2, m 1 2 -1 d G (ln(C)) 2-d G 2 ln 1 2 m 1+ 1 d G ln(C) , if d G > 2 and m C 1.2 .
Compared to Theorem 7 of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF], one can see that in all three cases, the dependency on C is improved: the powers of C are replaced by powers of ln(C) without losing in the dependencies on m and γ. It is interesting to note that, in the third case, when d G 4, which is true for instance for feedforward neural networks (see Corollary 27 in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network[END_REF]), the dependency on C is slightly better than radical. This is, however, at the cost of the constant factor d dG G .

Proof of Theorem 3. For all j ∈ N, we set h(j) = γ2 -α(dG)j with α(d G ) > 0 for all d G ∈ R * + in (1). In the following, we use the relation

∀r > q > 0, N (ǫ, F , d q,tn ) N (ǫ, F , d r,tn ) (5)
which follows directly from the fact that

∀f, f ′ ∈ F , d q,tn (f, f ′ ) d r,tn (f, f ′ ).
First case: d G ∈ (0, 2) This is the only case where Pollard's entropy condition [START_REF] Dudley | Uniform central limit theorems[END_REF] is satisfied.

For this case we could directly use Dudley's integral formula (Formula 33 in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]), however, to optimize with respect to constants, we start from ( 1) and upper bound it by an integral in the following way.

Apply ( 5) and ( 4) in sequence to the right-hand side of (1) and use Hypothesis to get

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

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

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

L = 2 2 -d G K 2-d G 2   ln 1 2 2K 2-d G 2 2K 2-d G 2 + ∞ ln 1 2 2K 2-d G 2 e -t 2 dt   1 2(2 -d G )   ln 1 2 2K 2-d G 2 + 1 2 ln 1 2 2K 2-d G 2   . Consequently, Rm (F G,γ ) 4 10 • 72 dG • K G 2(2 -d G ) • √ C(log 2 (2C)) 1/2+dG /2 √ m γ 1-d G 2 1 + 2 2 2-d G ×   ln 1 2 2K 2-d G 2 + 1 2 ln 1 2 2K 2-d G 2   .
Second case: d G 2 In this case, we apply ( 5) and ( 3) to (1) and use Hypothesis 1 to get

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

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

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

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

d G > 2, we set α(d G ) = 2 d G -2 in (
Rm (F G,γ ) γ2 -2 d G -2 N + 2 2CK G m (30 log 2 (2C)) dG/2 γ 1-d G 2 (1 + 2 2 d G -2 ) × N j=1 2 j ln 1 2 30emM G log 2 (2C) • 2 2 d G -2 j γ γ2 -2 d G -2 N + 4 • 2 N 2CK G m (30 log 2 (2C)) dG/2 γ 1-d G 2 (1 + 2 2 d G -2 ) × ln 1 2 30emM G log 2 (2C) • 2 2 d G -2 N γ . ( 7
) Now, let N = d G -2 2d G log 2 m log 2dG 2 (2C)
1 d G m 1 d G + 8 2K G • 30 dG/2 d dG -2 G γ 1-d G 2 (1 + 2 2 d G -2 ) × √ C (log 2 (2C)) 2-dG/2 m 1 d G ln 1 2 60ed 2 G m 1+ 1 d G M G γ log 2 (2C)
.

Conclusions

We derived a sharper risk bound for multi-category margin classifiers following the pathway of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF].

In this pathway, the first capacity measure that appears in the control term of the guaranteed risk is a Rademacher complexity. It is then related to the metric entropy through the chaining method. Using a decomposition for metric entropy, we transition from the multi-class setting to the bi-class one. Finally, a combinatorial bound gives an estimate on the metric entropy in terms of the combinatorial dimension. The metric entropy bound used in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] is the L 2 -norm one of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF],

which in this paper we generalized to L p -norms with integer p > 2. This generalization resulted in an improved dependency on the number C of categories compared to [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF] without worsening the dependency on the sample size m nor the one on the margin parameter γ.

So far, to get an explicit dependency on C under minimal learnability assumptions, a transition from the multi-class case to the bi-class one has been been performed at the level of one of two capacity measures. Realizing it at the level of a Rademacher complexity, a linear dependency on C was obtained in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]. In this paper, as in [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF], we showed that postponing it to the level of metric entropy, this dependency can be improved to a sublinear one. The case that remains to be studied is a decomposition at the level of a combinatorial dimension, more precisely, at that of the fat-shattering dimension. The goal is to complete the picture of the impact that performing a decomposition at the level of one of three different capacity measures has on the dependencies on C, m and γ.

A Proof of Theorem 2

Let T n = {t i : 1 i n} ⊂ T and t n = (t i ) 1 i n . Let
T n into [ [ 0, N ]
] obtained by the discretization of functions in F ǫ in the following way:

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

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

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

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

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

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

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

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

M (ǫ, F ǫ , d p,tn ) M(ǫ ′ , F η , d p,tn ) = | F η |. (9)
The major step that remains to perform to arrive at the claimed bound is to upper bound the right-hand side of [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF]. To this end, we appeal to Proposition 3. Let d s be the strong dimension of F η . By part (1) of Lemma 3.2 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF],

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

8(4K p ) 1/p + 4 < 8 • 4 1/p p + 4 < 15p.
We can plug this result in the upper bound on d s based on the fact that the fat-shattering dimension decreases with the scale:

d s ǫ 15p -dim( F ǫ | Tn ) ǫ 15p -dim(F ) = d ǫ 15p
.

Now, according to Proposition 3,

| F η |   eN n d ǫ 15p   2d( ǫ 15p )   en d ǫ 15p 2M F η   2d( ǫ 15p )   en d ǫ 15p 8M F (4K p ) 1/p + 4M F ǫ   2d( ǫ 15p ) . (10)
Applying Lemma 1 to the right-hand side of [START_REF] Koltchinskii | Empirical margin distributions and bounding the generalization error of combined classifiers[END_REF] and simplifying it we get

| F η |   15enM F p ǫd ǫ 15p   2d( ǫ 15p ) . (11)
We apply the relation ( 9) and the following well-known inequality [START_REF] Kolmogorov | ǫ-entropy and ǫ-capacity of sets in functional spaces[END_REF] N

(ǫ, F , d p,tn ) M (ǫ, F , d p,tn ) (12)
in sequence to the left-hand side of [START_REF] Talagrand | Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems[END_REF]. Finally, to obtain the claimed result, we take supremum over t n ∈ T n of both sides of the obtained bound.

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

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

|F ǫ | = M ǫ 1 , F ǫ , d p,tq = M ǫ 1 , F ǫ | Tq , d p,tq = | F ǫ | Tq |. (14)
We let η = ǫ 1 ǫ ′ + 2 and discretize the functions in the set F ǫ | Tq in a similar way as in part (a):

F η = f : f (t i k ) = f (t i k ) + M F η , k ∈ [ [ 1, q ] ] , f ∈ F ǫ | Tq .
Applying the same procedure as in the proof of part (a), we obtain that for any f1 , f2 ∈ F η , d p,tq f1 , f2 ǫ ′ , and hence

M ǫ 1 , F ǫ , d p,tq M(ǫ ′ , F η , d p,tq ) = | F η |. (15)
By Proposition 3,

| F η | eN q d s 2ds ,
where d s is the strong dimension of F η . Plugging the value of N and performing similar computations as in Inequalties ( 10)-( 11) of part (a), we get

| F η | 23eqM F (4K p ) 1/p ǫd s 2ds . (16)
Now, we go back from the discretized set F η to F ǫ using the relations ( 14) and ( 15) which yield:

|F ǫ | | F η |.
Using it and Inequality (13) in [START_REF] Dudley | Uniform central limit theorems[END_REF] give:

ln (|F ǫ |) 2d s ln 2576 • 2 2p eM 2p+1 F (4K p ) 1/p ln (|F ǫ |) 3ǫ 2p+1 d s .
Now, based on ln(u) < √ u and by a straightforward computation,

ln (|F ǫ |) 4d s ln 2576 • 2 2p+1 eM 2p+1 F (4K p ) 1/p 3ǫ 2p+1 . (17)
Next, we bound d s using part (1) of Lemma 3.2 in [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] and Lemma 1:

d s η 2 -dim( F ǫ | Tq ) = ǫ 2 4p+1 p (4K p ) 1/p + 2 3p+1 p -dim( F ǫ | Tq ) ǫ 16 • 2 3 p p + 8 • 2 1 p -dim( F ǫ | Tq ) ǫ 36p -dim( F ǫ | Tq ).
Plugging this into [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF] and applying Lemma 1 to K p , we obtain

ln (|F ǫ |) 4d ǫ 36p ln 2576 • 2 2p+1 eM 2p+1 F 4 1/p p 3ǫ 2p+1 10p d ǫ 36p ln 7p 1 7 M F ǫ .
The claim follows from the application of |F ǫ | = M(ǫ, F , d p,tn ), Inequality [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] and taking supremum over t n ∈ T n of both sides of the obtained bound.

B Technical Results

Lemma 1. For all p ∈ N * \ {1, 2},

∞ k=1 k p 2 k < p p .
Proof. By Formula (8.5) in [24, page 119],

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

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

ψ p (-2) = p-1 j=0 p j + 1 ψ (p-1)-j (-2).
For the base case, p = 3, it is easily seen that ψ 3 (-2) < 3 3 /2. Now, assume for k > 3, ψ k (-2) < k k /2. Then,

ψ k+1 (-2) = k j=0 k + 1 j + 1 ψ k-j (-2) = (k + 1)ψ k (-2) + k j=1 k + 1 j + 1 ψ k-j (-2) < (k + 1)k k /2 + k-1 j=0 k + 1 j + 2 ψ (k-1)-j (-2) = (k + 1)k k /2 + k-1 j=0 k j + 1 + k j + 2 ψ (k-1)-j (-2). ( 18
)
We have that

k j + 2 = k! (j + 2)!(k -(j + 2))! = k! (j + 1)!(k -(j + 2))! • k -(j + 1) (k -(j + 1))(j + 2) = k! (j + 1)!(k -(j + 1))! • k -(j + 1) j + 2 < k k j + 1 .
Applying it in [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF], we obtain

ψ k+1 (-2) < (k + 1)k k /2 + k-1 j=0 (k + 1) k j + 1 ψ (k-1)-j (-2) < (k + 1)k k /2 + (k + 1)ψ k (-2) < (k + 1)k k .
Now, by the binomial theorem, for all k > 1,

(k + 1) k = k 0 k 0 + • • • + k k -1 k k-1 + k k k k = 1 + • • • + k • k k-1 + k k > 2k k .
Consequently,

ψ k+1 (-2) < (k + 1) • (k + 1) k /2 = (k + 1) k+1 /2,
where we used the convention that ∀k > n, n k = 0.

The results demonstrated hereafter are the generalizations of those in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]. In the following, we

denote K p = ∞ k=1 k p 2 k with p ∈ N * \ {1, 2}.
Lemma 2 (After Lemma 5 of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]). Let X be a bounded random variable. Let M p (X) = (E|X| p ]) 1/p . Then, there exist numbers a ∈ R and β ∈ (0, 1/2], such that

P X > a + M p (X) 4(2K p ) 1/p β 2 and P X < a - M p (X) 4(2K p ) 1/p 1 -β,
or vice versa.

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

Divide R + into the intervals I k of length cM p (X) with

1 2(2K p ) 1/p < c < 1 (2K p ) 1/p
by setting

I k = (cM p (X)k, cM p (X)(k + 1)], k 0.
Assume the lemma does not hold and let (β i ) i 0 be a non-increasing sequence of non-negative numbers such that

P{X > 0} = β 0 1/2 and P{X ∈ I k } = β k -β k+1 , k 0.
For the conclusion of the lemma to fail it should hold that ∀k 0, β k+1 β k /2.

(

Now, assume that for some k, β k+1 > β k /2 and consider intervals

J 1 = (-∞, 0] ∪ (0, cM p (X)k] = (-∞, 0] ∪   0 j k-1 I j   and J 2 = (cM p (X)(k + 1), ∞). Then, P{X ∈ J 1 } = (1 -β 0 ) + 0 j k-1 (β j -β j+1 ) = 1 -β k and P{X ∈ J 2 } = j k+1 (β j -β j+1 ) = β k+1 .
By definition of (β i ) i 0 and by our assumption, 1/2 β 0 β k β k+1 > β k /2 0, which means that β k ∈ (0, 1/2]. Now, let a be the middle point between the intervals J 1 and J 2 and let β = β k .

We have that

cM p (X)k = a - cM p (X) 2 < a - M p (X) 4(2K p ) 1/p =⇒ 1 -β P X < a - M p (X) 4(2K p ) 1/p and cM p (X)(k + 1) = a + cM p (X) 2 > a + M p (X) 4(2K p ) 1/p =⇒ β 2 P X > a + M p (X) 4(2K p ) 1/p .
Thus, the lemma holds. This proves [START_REF] Mendelson | The shattering dimension of sets of linear functionals[END_REF]. Now, by induction from [START_REF] Mendelson | The shattering dimension of sets of linear functionals[END_REF] we get that

β k 1/2 k+1 .
We use it in the computation of M p p (X). By definition,

M p p (X) = ∞ 0 P{|X| > t}dt p = ∞ 0 P{X > t}dt p + ∞ 0 P{X < -t}dt p .
By construction, whenever

t ∈ I k , P{X > t} P{X > cM p (X)k} = P{X ∈ l k I l } = l k (β l -β l+1 ) = β k . Thus, ∞ 0 P{X > t}dt p k 0 I k β k pt p-1 dt (cM p (X)) p k 0 (k + 1) p -k p 2 k+1 (cM p (X)) p k 1 k p 2 k = (cM p (X)) p K p < M p p (X)/2.
By a similar procedure, it can be proved that

∞ 0 P{X < -t}dt p < M p p (X)/2.
This produces a contradiction M p p (X) < M p p (X)/2 + M p p (X)/2 = M p p (X) proving the lemma.

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

Lemma 3 (After Lemma 6 of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]). Let F be a finite class of functions from T into [0, M F ] with

M F ∈ R + and |F | > 1. Assume that for some ǫ ∈ (0, M F ], F is ǫ-separated in the pseudo-metric d p,tn . Then there exist i ∈ [ [ 1, n ] ], a ∈ R and β ∈ (0, 1/2] such that f ∈ F : f (t i ) > a + ǫ 8(4K p ) 1/p p 1 |F | f ∈ F : f (t i ) < a - ǫ 8(4K p ) 1/p p 2 |F | ,
with p 1 β 2 and p 2 1β or vice versa.

Proof. F can be viewed as a finite probability space (F , A, P F ) with a uniform probability measure P F (A) = |A|/|F | for any A ∈ A. Then, for any two random elements f, f ′ ∈ F selected independently according to P F ,

E f,f ′ ∼PF (d p,tn (f, f ′ )) p = E f,f ′ ∼PF 1 n n i=1 |f (t i ) -f ′ (t i )| p = 1 n n i=1 E f,f ′ ∼PF |f (t i ) -f ′ (t i )| p .

By the Minkowski inequality, for any

i ∈ [ [ 1, n ] ], E f,f ′ ∼PF |f (t i ) -f ′ (t i )| p (E f ∼PF |f (t i )| p ) 1/p + E f ′ ∼PF |-f ′ (t i )| p 1/p p = (E f ∼PF |f (t i )| p ) 1/p + E f ′ ∼PF |f ′ (t i )| p 1/p p = 2 p E f ∼PF |f (t i )| p .
Taking it into account in the formula above, we obtain,

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

E f,f ′ ∼PF (d p,tn (f, f ′ )) p (1 -1/|F |) ǫ p (1 -1/2) ǫ p = ǫ p /2.
Thus,

1 n n i=1 E f ∼PF |f (t i )| p ǫ p 2 p+1 .

It means that there exists

i ∈ [ [ 1, n ] ], such that E f ∼PF |f (t i )| p ǫ p 2 p+1 .
Next, we apply Lemma 2 to the random element f and take into account that

M p (f (t i )) ǫ 2 1+1/p and that M p (f (t i )) 4(2K p ) 1/p ǫ 8 × 2 1/p (2K p ) 1/p = ǫ 8(4K p ) 1/p .
Then, it follows that

β 2 P F f (t i ) > a + M p (f (t i )) 4(2K p ) 1/p P F f (t i ) > a + ǫ 8(4K p ) 1/p
and, similarly,

1 -β P F f (t i ) < a - M p (f (t i )) 4(2K p ) 1/p P F f (t i ) < a - ǫ 8(4K p ) 1/p .
Finally, the claim follows from the definition of P F .

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

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

and ∃i ∈ [ [ 1, n ] ] , ∀(f + , f -) ∈ F+ , F-, f + (t i ) > f -(t i ) + ǫ,
then T (F ) is an ǫ-separating tree.

Proposition 1 (After Proposition 8 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]). Let F be a finite class of functions from T into

[0, M F ] with M F ∈ R + .
Assume that for some ǫ ∈ (0, M F ], F is ǫ-separated in the pseudo-metric d p,tn . Then, there is a ǫ/4(4K p ) 1/p -separating tree of F with at least |F | 1/2 leaves.

Proof. By Lemma 3, F has two subsets F + and

F -such that ∃i ∈ [ [ 1, n ] ] , ∃a ∈ R, ∀(f + , f -) ∈ F + × F -,      f + (t i ) > a + ǫ/8(4K p ) 1/p
f -(t i ) < aǫ/8(4K p ) 1/p , which implies

f + (t i ) < f -(t i ) + ǫ/4(4K p ) 1/p .
The rest of the proof is based on induction on the cardinality of F and is exactly as in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], except that the tree is now ǫ/4(4K p ) 1/p -separated.

Proposition 2 (After Proposition 10 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]). Let F be a class of functions from T into a finite set B of integers. Let S ⊆ T and let v : S → B. The number of pairs (S, v) strongly shattered by F is at least the number of leaves in any 1-separating tree of F .

Proof. The proof follows exactly the one of Proposition 10 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF], with a few minor technical changes. Let F be a node in a 1-separating tree of F . Let N (A) denote the number of pairs strongly shattered by a set A. For the proof it suffices to show that if F+ and Fare two sons of F , then

N ( F ) N ( F+ ) + N ( F-). ( 20
)
By definition of the 1-separating tree, there exists i 0 ∈ [ [ 1, n ] ] such that

∀(f + , f -) ∈ F+ , F-, f + (t i0 ) > f -(t i0 ) + 1.
It follows that

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

Combining it with (21) yields a contradiction:

b + 1 < v(t i0 ) < b -1.
Now, consider a pair (S ∪ {t i0 }, v ′ ), where v ′ (t i ) = v(t i ) for all t i ∈ S and v ′ (t i0 ) = b. This pair is shattered by F , but neither by F+ or F-. As S is shattered both by F+ and F-, then from [START_REF] Gottlieb | Efficient classification for metric data[END_REF] it follows that,

∀(s i ) 1 i n ∈ {-1, 1} n , ∃f + ∈ F+ ,      ∀i ∈ [ [ 1, n ] ] , s i (f + (t i ) -v(t i )) 1, f + (t i0 ) b + 1, similarly, ∀(s i ) 1 i n ∈ {-1, 1} n , ∃f -∈ F-,      ∀i ∈ [ [ 1, n ] ] , s i (f -(t i ) -v(t i )) 1, f -(t i0 ) b -1.
It proves the claim that F shatters the pair (S ∪ {t i0 }, v ′ ). Therefore, in both cases we get [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF].

The next result is obtained by combining Propositions 1 and 2.

Corollary 2 (After Corollary 11 in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]). Let F be a class of functions from T into a finite set B where we used the convention that for all k > n, n k = 0.

1 p

 1 = 2 ( 1 p log 2 (C)) , the dependency on C in the scale of covering numbers can be eliminated for all p log 2 (C). The combination of the decomposition formula (2) with Theorem 2 using p = ⌈log 2 (C)⌉ for C > 4 yields the following result. Corollary 1. Let G be a class of functions as in Definition 1. For γ ∈ (0, 1], let F G,γ be the class of functions deduced from G according to Definition 5. For ǫ

F

  ǫ be an ǫ-separated with respect to the pseudo-metric d p,tn subset of F of maximal cardinality. By definition, |F ǫ | = M (ǫ, F , d p,tn ) = M ǫ, F ǫ | Tn , d p,tn = | F ǫ | Tn |, where F ǫ | Tn denotes the class F ǫ whose domain is restricted to T n . We distinguish three major steps in the proof: i) discretize functions in the set F ǫ | Tn , ii) demonstrate that the set of discretized functions is separated, and iii) upper bound the cardinality of the discretized set. The purpose of discretizing the set of real-valued functions is to reduce the original problem into the one that can be addressed by combinatorial means: we upper bound the packing number of the discretized set which is then related to that of the original set via the step (ii). (a) Let ǫ ′ = 4(4K p ) 1/p , η = ǫ ǫ ′ + 2 and N = ⌊2M F /η⌋. Define the class F η of functions from

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


Krishnendu Chatterjee
email: krishnendu.chatterjee@ist.ac.at

Amir Kafshdar Goharshady
email: amir.goharshady@ist.ac.at

Arash Pourdamghani
email: pourdamghani@ce.sharif.edu

Hybrid Mining

Keywords: Applied computing → Electronic commerce, Secure online transactions, • Computing methodologies → Distributed computing methodologies, Blockchain, Proof of Work, Mining, Distributed Problem Solving, Collaborative Problem Solving

In today's cryptocurrencies, Hashcash proof of work is the most commonly-adopted approach to mining. In Hashcash, when a miner decides to add a block to the chain, she has to solve the difficult computational puzzle of inverting a hash function. While Hashcash has been successfully adopted in both Bitcoin and Ethereum, it has attracted significant and harsh criticism due to its massive waste of electricity, its carbon footprint and environmental effects, and the inherent lack of usefulness in inverting a hash function. Various other mining protocols have been suggested, including proof of stake, in which a miner's chance of adding the next block is proportional to her current balance. However, such protocols lead to a higher entry cost for new miners who might not still have any stake in the cryptocurrency, and can in the worst case lead to an oligopoly, where the rich have complete control over mining.

In this paper, we propose Hybrid Mining: a new mining protocol that combines solving real-world useful problems with Hashcash. Our protocol allows new miners to join the network by taking part in Hashcash mining without having to own an initial stake. It also allows nodes of the network to submit hard computational problems whose solutions are of interest in the real world, e.g. protein folding problems. Then, miners can choose to compete in solving these problems, in lieu of Hashcash, for adding a new block. Hence, Hybrid Mining incentivizes miners to solve useful problems, such as hard computational problems arising in biology, in a distributed manner. It also gives researchers in other areas an easy-to-use tool to outsource their hard computations to the blockchain network, which has enormous computational power, by paying a reward to the miner who solves the problem for them. Moreover, our protocol provides strong security guarantees and is at least as resilient to double spending as Bitcoin.

INTRODUCTION AND PRELIMINARIES

The aim of this paper is to develop a blockchain mining protocol that can be exploited for distributed problem solving. In this section, we review basics of blockchain, mining, and distributed problem solving.

Blockchain and Mining

Bitcoin. Bitcoin was the first cryptocurrency that provided a protocol to achieve consensus about the ownership of funds, without a need for relying on a central governing authority or bank [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. This decentralization was very well-received and, at the time of writing, Bitcoin is the largest cryptocurrency in the world with a market cap of more than 100 billion dollars [START_REF]Cryptocurrency Market Capitalizations[END_REF]. Double Spending. The most basic attack in every electronic monetary system is that of double spending. In the real world, units of currency cannot be duplicated and hence one can pay for goods and services by simply transferring a banknote or coin to the recipient. However, in a digital setting, a coin is just a file or a collection of data and one can copy it and send each copy to a different recipient, effectively creating money out of thin air. A solution to avoid this problem, as employed by Bitcoin, is to have every transaction broadcast to the entire currency network [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. This way, every participant in the network would reject a transaction that is spending the same coin for a second time. However, the problem of double spending is still not solved entirely. If one creates two transactions, sending the same coin to different recipients, and publishes both at the same time in different parts of the world, then due to network latency, some nodes of the network would receive the first transaction and reject the second one as double spending, while other nodes might do the opposite. Bitcoin has an elegant way of ensuring that the entire network reaches a consensus about the results of transactions. This protocol is called the Blockchain [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF].

Blockchain. In a cryptocurrency, a blockchain is a distributed ledger of transactions. The transactions are grouped into fixedsize blocks. The chain starts with a predefined block and each block has a pointer to its preceding block. Hence, a blockchain is effectively a singly-linked list of blocks [START_REF] Tschorsch | Bitcoin and beyond: A technical survey on decentralized digital currencies[END_REF]. Every node of the network keeps a local copy of the blockchain. To ensure that all local copies eventually agree on the contents of the blockchain, one cannot simply add new blocks as she wishes. Instead, adding blocks is regulated by a process called mining [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF][START_REF] Tschorsch | Bitcoin and beyond: A technical survey on decentralized digital currencies[END_REF].

Mining. Mining is the process by which a node of the network is selected and permitted to add a new block to the blockchain [START_REF] Gilad | Algorand: Scaling byzantine agreements for cryptocurrencies[END_REF][START_REF] Tschorsch | Bitcoin and beyond: A technical survey on decentralized digital currencies[END_REF]. The selected node forms a block using the valid transactions she has received. She then broadcasts the block to the entire network. Every other node of the network checks two conditions: (i) whether all the transactions in the broadcast block are valid, and (ii) whether the broadcaster had the right to add a new block according to the mining protocol. If both checks pass, then the node adds this block to the end of her local copy of the blockchain. If the mining protocol always chooses exactly one node for adding the new block, then there will be no conflicts and the entire network would be in consensus about the contents of the blockchain. However, in Bitcoin and other cryptocurrencies, the participants are anonymous, hence are both announced as valid successors to A. However, the chain containing B has become longer and is now the consensus chain. Hence, C and its successors will be dropped by the network nodes.

a protocol cannot simply point to the next person who is allowed to add a block.

Proof of Work. Bitcoin's solution to the problem above is to use a Proof of Work (PoW) protocol. In a PoW, a hard computational problem is chosen and one can add a new block as soon as she succeeds in solving the problem [START_REF] Back | Hashcash -a denial of service counter-measure[END_REF]. In case of Bitcoin, the used protocol is Hashcash [START_REF] Back | [END_REF], i.e. one has to find a nonce value, such that the result of applying the SHA256 hash function to a tuple consisting of her public key, the hash of the previous block, the hash of the current block that is being added, and this nonce value, is at most a predefined amount 1 . Given the one-way property of hash functions, the only strategy for finding a nonce, and hence getting the right to add a new block, is to repeatedly try randomly-generated nonces until one of them solves the problem. This process is called Proof of Work mining and the nodes taking part in finding nonces are called miners. When a miner finds the right nonce, she broadcasts the new block, together with the nonce. Then, every other node of the network can perform the two previously-mentioned checks and add the block to her local copy of the blockchain [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF].

Ensuring Consensus. It is possible that two miners succeed in solving the Hashcash problem at approximately the same time. If this happens, then two new blocks would be broadcast, and network latency leads to a fork in the blockchain, i.e. a situation in which some of the nodes have added the first new block to their local copy, and others have added the second one. In such cases, the blockchain protocol considers both chains to be valid and miners can choose the chain they want to extend. However, as soon as one of the chains becomes longer than the other ones, the protocol dictates that the longest chain is the consensus chain and all other chains will be dropped by everyone in the network [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] (See Figure 1). The probabilistic nature of the mining process guarantees that one of the chains would eventually get longer [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF], and therefore the whole network would reach consensus after a few blocks 2 .

Incentives for Mining. PoW mining requires considerable computational power and electricity usage. Hence, the process is not free for the miners. Therefore, there should be compensations in place to ensure that network participants are incentivized to mine. Bitcoin uses two incentives for the miners [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]:

• Block reward. Any miner who successfully adds a block to the blockchain gets a predefined reward. The reward is currently The data is provided in [START_REF] Smith | Hash Rate: The estimated number of tera hashes per second (trillions of hashes per second) the Bitcoin network is performing[END_REF][START_REF]Quandl: Financial, Economic and Alternative Data[END_REF]. Note that the graph is in logarithmic scale.

set at 12.5 bitcoins, which is roughly equal to 75000 dollars at the time of writing. Hence, in Bitcoin, block rewards are also used as the mechanism for creating new units of currency. • Transaction Fees. While block rewards incentivize miners to add new blocks to the blockchain, the miners might choose to add empty blocks, i.e. blocks that contain no transactions.

There should be an additional incentive for the miners in order to ensure that a transaction is eventually picked up by the miners and added to the blockchain. Bitcoin achieves this using transaction fees. Each transaction in Bitcoin can set a reward, or transaction fee, that is paid to the miner who puts the transaction in a block and adds it to the blockchain.

Computational Power of the Bitcoin Network. The rising price and popularity of Bitcoin has turned mining into a lucrative and highly-specialized industry. The computational (mining) power of the Bitcoin network has been increasing exponentially since its inception. Figure 2 shows the growth in the overall hashrate of the Bitcoin network, i.e. the estimated number of hashes that are computed every second. Note that this figure is in logarithmic scale. Already in 2013, Bitcoin network's computational power was reported to be more than 250 times the computational power of the world's 500 fastest supercomputers combined [START_REF] Cohen | Global Bitcoin Computing Power Now 256 Times Faster Than Top 500 Supercomputers Combined[END_REF]. Specialized Mining Hardware. While anyone can take part in mining using their personal computer, the overall computational power of the bitcoin network is vast and the chances of finding a new block using everyday hardware are slim. Therefore, many specialized hardware modules have been designed for mining. These hardware modules are optimized for the single task of inverting SHA256 hash functions and are extremely efficient [START_REF] Bedford | The evolution of bitcoin hardware[END_REF].

Pool Mining. Given the hardness of mining, and in order to decrease the variance in their revenue, miners often collaborate in pools [START_REF] Chatterjee | Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies[END_REF][START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF]. A pool is basically a group of miners who solve PoW problems using the same public key and share the rewards among themselves. Usually, each pool has a manager who receives all the rewards and divides them among the miners based on their overall contribution. The contribution of a miner is often assessed by partial proofs of work, i.e. proofs of work on the same problem, but with a lower difficulty. The graph above is adapted from [START_REF] De | Bitcoin's Growing Energy Problem[END_REF][START_REF]Bitcoin Energy Consumption Index[END_REF].

Criticisms and Alternatives. There are reports that the Bitcoin PoW mining uses more electricity than the entire country of Ireland [START_REF] Karl | Bitcoin mining and its energy footprint[END_REF]. Moreover, Bitcoin mining's energy consumption has been steadily increasing [START_REF] De | Bitcoin's Growing Energy Problem[END_REF]. See Figure 3. On the other hand, the task of inverting a hash function is inherently useless, and there is no justification for it other than the incentives given by the Bitcoin protocol. Moreover, PoW has considerable environmental consequences and a huge carbon footprint [START_REF] Foteinis | Bitcoin's alarming carbon footprint[END_REF] and has been called an environmental disaster by the Bank for International Settlements [START_REF]Cryptocurrencies: looking beyond the hype[END_REF]. Therefore, the process of mining in Bitcoin has been harshly criticized and many other alternative mining protocols have been suggested in order to reduce the energy usage and carbon footprint of blockchains [START_REF] Forte | Beyond Bitcoin-Part II: Blockchain-based systems without mining[END_REF][START_REF] Vranken | Sustainability of bitcoin and blockchains[END_REF]. Two of the most notable examples are proof of stake [START_REF] Kiayias | Ouroboros: A provably secure proof-of-stake blockchain protocol[END_REF] and proof of space [START_REF] Dziembowski | Proofs of space[END_REF]. In proof of stake, one's chance of getting selected as the miner to add the next block is proportional to the number of cryptocurrency units in her possession, and proof of space replaces energy-consuming computations in PoW with memory-consuming computations.

Obstacles to Adoption. There has been significant resistance against adoption of new mining protocols, especially in Bitcoin [START_REF] Forte | Beyond Bitcoin-Part I: A critical look at blockchain-based systems[END_REF]. There are two major reasons for this: (i) some protocols, such as proof of stake, favor the richer members of the network [START_REF] Poelstra | Distributed consensus from proof of stake is impossible[END_REF] and are considered to be more prone to becoming centralized, i.e. leading to a situation in which a few members of the network have complete control over mining, and (ii) many miners have already invested significant amounts of funds into acquiring specialized PoW mining hardware [START_REF] Bedford | The evolution of bitcoin hardware[END_REF] and are not willing to suddenly switch away from it to other specialized hardware, e.g. for proof of space.

Distributed Problem Solving

In this section, we provide a short review of distributed problem solving approaches. Distributed Problem Solving. There are many intractable problems in various fields of science, for example computational biology [START_REF] Cooper | Predicting protein structures with a multiplayer online game[END_REF], that lack efficient algorithms and finding their solutions takes decades of time on a normal computer. A very costly and non-scalable approach to solving such problems is to use supercomputers with more computing resources. However, many of these problems can also be solved using a new paradigm, which is called Distributed Problem Solving (DPS). In DPS, many computers on a network attempt to solve a single problem. Hence, the computational power that might otherwise be dormant in machines all around the world is effectively used to solve an important realworld problem.

Examples. One of the most well-known examples of DPS is the Great Internet Mersenne Prime Search project [START_REF] Woltman | GIMPS: the Great Internet Mersenne Prime Search[END_REF], in which the problem of finding huge prime numbers of the form 2 p -1 is solved in a distributed manner. Another example is folding@home [START_REF] Stefan M Larson | Folding@ Home and Genome@ Home: Using distributed computing to tackle previously intractable problems in computational biology[END_REF], in which the computationally hard problem of protein folding, which is of great interest to biologists, is tackled by DPS. However, these projects do not provide incentives for contributors and most of the computation is carried out by volunteers, hence the overall computational power of the their networks is far less than that of blockchains. Another notable project is Foldit [START_REF] Cooper | Predicting protein structures with a multiplayer online game[END_REF], in which the problem of finding protein structures is translated to a game, hence using the enjoyment of gaming as an incentive for solving a real-world scientific problem. For more examples of DPS see [START_REF] Adam-Bourdarios | ATLAS@ Home: harnessing volunteer computing for HEP[END_REF][START_REF] Korpela | SETI@ HOME-massively distributed computing for SETI[END_REF]. In this paper, we propose a new mining protocol that provides Bitcoin-like incentives for solving such real-world problems, thereby allowing the DPS networks to grow beyond their volunteer community.

Relationship to Pool Mining. Note that pool mining can itself be considered a special case of DPS, given that miners in the pool are trying to solve an instance of the Hashcash problem in a distributed manner. This observation directly leads to the main goal of this paper, i.e. using the same mechanisms and incentives as mining for distributed solution of real-world practical problems.

NP Problems. The real-world problems mentioned above, that are solved by DPS, belong to the class NP. The class NP represents problems that can be solved in non-deterministic polynomial time, which means that if a correct answer is guessed/provided, it can be verified in polynomial time. However, finding the answer might be a much more challenging problem. The class of problems that can be solved in polynomial time is called P. It is a major open question whether P=NP, and it is widely believed that P NP [START_REF] Arora | Computational complexity: a modern approach[END_REF].

NP-completeness. The class of NP-complete problems represents the core difficult problems of NP. Informally, NP-complete problems (i) belong to the class NP and (ii) are as hard as any other problem in NP. The notion of as hard as any other problem is captured by showing that there is a polynomial-time reduction from any other NP problem to an NP-complete problem [START_REF] Richard | Reducibility among combinatorial problems[END_REF]. This implies that an efficient (polynomial-time) algorithm for an NP-complete problem would imply P=NP, which is unlikely, and these NP-complete problems are considered computationally intractable [START_REF] Arora | Computational complexity: a modern approach[END_REF]. Many of the DPS problems above are known to be NP-complete.

Choosing a Representative Problem. Given an NP-complete problem A, any other problem in NP, including other NP-complete problems, can be reduced to A in polynomial time. Hence, instead of creating distinct DPS networks for each problem, we can simply choose a representative problem A that the whole network tries to solve, and ask owners of real-world problems, such as computational biologists, to translate (reduce) their problem into A before submitting it to the network for solution.

Satisfiability. Any NP-complete problem can be used as a representative for DPS. In this paper, we use the boolean satisfiability (SAT) problem as the representative. However, our approach is not dependent on this and SAT can be replaced by any other NPcomplete problem. We chose SAT because there has been ample research into solving real-world instances of this problem [START_REF] Claessen | SATsolving in practice[END_REF]. An instance of SAT is a propositional logic formula φ in conjunctive normal form, consisting of boolean variables x 1 , x 2 , . . . , x n . The SAT problem asks whether one can find true/false assignments to the variables such that the formula φ is satisfied. The size |φ| of the formula is called the length of the SAT instance, and n is its order.

Our Contribution

In this paper, we present Hybrid Mining: a new mining protocol that combines solving real-world instances of NP-complete problems with Hashcash mining. In our protocol, any node in the network can submit a problem, together with a reward for its solution. Then, every other node of the network can add a new block to the blockchain by either solving a submitted problem or taking part in Hashcash PoW. Our approach has the following benefits:

(i) It provides an easy-to-use protocol for DPS, where people can outsource their problems to be solved using the enormous computational power of the blockchain. (ii) It gives miners a strong incentive to solve useful real-world problems, hence decreasing the waste in energy usage and carbon footprint of PoW. (iii) It gives current Bitcoin miners the choice of reverting back to PoW in case they cannot solve any of the submitted problems, hence making use of the already purchased resources and specialized hardware. (iv) On the other hand, new miners who have not invested in such hardware can join by using software and hardware technologies for solving NP-hard problems, especially SAT. This can in turn lead to financial incentives for research and development in solving such problems and gaining new insights to them. (v) It is at least as secure, and resilient to centralization, as PoW mining. To the best of our knowledge, this is the first mining protocol that incentivizes solving real-world hard problems that are of immediate practical interest to researchers in various fields.

Related Work

There has been ample research in finding alternative mining protocols, or as they are commonly called, proofs of useful work. We list some of these approaches below.

Number Theoretic Approaches. Primecoin [START_REF] King | Primecoin: Cryptocurrency with prime number proof-of-work[END_REF] and Gapcoin [START_REF] King | Gapcoin[END_REF] are two approaches to mining that use alternative numbertheoretic problems, instead of hash inversion, for PoW. Primecoin PoW asks for chains of prime numbers with a specific property, and Gapcoin PoW searches for large prime gaps. • Approaches using NP-completeness. Using NP-complete problems for mining has been studied extensively and there are a variety of mining protocols using different NP-complete problem instances as their PoW. For example, see [START_REF] Ball | Proofs of Useful Work[END_REF][START_REF] Loe | Conquering Generals: an NP-Hard Proof of Useful Work[END_REF][START_REF] Oliver | Proposal for a fully decentralized blockchain and proof-of-work algorithm for solving NP-complete problems[END_REF]. Note that the approaches mentioned above have some important limitations, which are not present in Hybrid Mining. Here are some examples:

• Most of these approaches are limited to finding solutions for a specific problem, such as prime gap search. These problems are not necessarily NP-complete. Our approach allows practical scientists to post any problem by simply translating it to SAT. • These approaches are often referred to as proofs of useful work. However, the word "useful" should be taken with a grain of salt. While the problems solved for mining new blocks are indeed useful, the instances that are being solved are not real-world instances. Instead, they are artificially generated, either randomly or by a process that ensures they have a certain difficulty. This means that the resulting solutions are useful in the sense that they provide new insights into the hardness of the problem at hand, but they do not solve a real-world problem. On the other hand, our approach uses real-world instances that are submitted by and of immediate practical value to their owners, who can be scientists in other fields, including computational biology. • Following the previous point, these approaches cannot be used for DPS, because the instances that are being solved are not proposed by an external entity, but generated by the protocol itself. A major novelty of our work is that we combine DPS with mining, hence creating new incentives for taking part in DPS. • Virtually all of these approaches, with the exception of [START_REF] Loe | Conquering Generals: an NP-Hard Proof of Useful Work[END_REF],

are incompatible with currently-used PoW hardware and therefore alienate a majority of miners. In contrast, our Hybrid Mining protocol welcomes current miners and provides an easy way for them to use their current hardware, while also creating incentives for new types of mining.

PROBLEM STATEMENT AND REQUIREMENTS

We now define the problem we are aiming to solve and the requirements we expect of the final solution. We are aiming for a blockchain mining protocol that combines Hashcash with Distributed Problem Solving (DPS). In order to be useful, such a protocol must meet the following criteria:

(1) Functional Reqirements: This condition also ensures that current miners who have invested in dedicated Hashcash PoW hardware can continue to mine in the new protocol, and that new blocks will be added even if there are no remaining problems to solve. (2) Security Reqirements:

(2.a) The protocol must remain resilient to double spending.

(2.b) The protocol must ensure that a miner is rewarded for solving a published problem, and that no miner can steal solutions found by another miner. (2.c) The protocol must be resilient to spamming and publication of fake or long problems that aim to thwart the network. (2.d) The protocol must ensure that no party, neither a problem proposer, nor a miner, can benefit from dishonest behavior that is detrimental to any other party.

HYBRID MINING

In this section, we propose a new mining protocol, called Hybrid Mining, and show the details of its operation. In the next section, we will show that Hybrid Mining satisfies all the required criteria mentioned above. As expected, in our approach, anyone can propose a new problem in the form of a SAT instance, and one can add a new block to the blockchain by either solving Hashcash or a previouslyunsolved problem on the blockchain. We now provide detailed protocols for each of these actions.

Problem Proposal Protocol

In our system, proposing a problem is considered as a special type of transaction. Consider a problem owner Owen, who likes to broadcast his problem to the network, so that miners solve it for him. To do so, he creates a transaction consisting of the following parts and broadcasts it to the network: • Owen's public key,

• The problem instance φ,

• An expiration date, setting the maximum amount of time Owen is willing to wait for the problem to be solved by the network3 , • Four distinct payments as follows:

-A constant problem proposal fee of f 1 units, -A problem storage fee of |φ| • f 2 units, -A reward value r , chosen by Owen, which will be paid to the first miner who successfully solves the problem, and -A transaction fee t, also chosen by Owen. • Owen's signature proving that he is the one broadcasting the transaction. We call this problem proposal transaction a Type 1 message. Note that Owen has to translate (reduce) his problem to a SAT instance φ, before publishing it on the network. We now explain the reason behind each of the payments:

• The constant problem proposal fee f 1 , which is paid by Owen and is the same as the block reward fee, ensures that one cannot overwhelm the network with many spam problems. Also, it ensures that one cannot add new blocks by adding simple problems and solving them on his own. This money is burnt if the problem is solved, but it will be refunded to Owen if the problem remains unsolved until its expiry time. • The second payment is correlated with the length of the problem instance. Every node of the network has to save the problem instance φ. Hence, in order to avoid unnecessarily long instances that aim to thwart the network, one has to pay a "storage fee" that correlates with the length of the problem. This idea is similar to the concept of Gas in Ethereum [38]. • In order to incentivize miners to solve the problem, Owen has to set a reward r , which will be paid to the miner that provides a solution to φ. • As with any other transaction, Owen should pay a transaction fee t, in order to have his transaction processed and added to a block by a miner. Note that transactions are processed in essentially the same way as Bitcoin. If the problem is not solved until its expiration time, then Owen can create another transaction that refunds the payment to him. We call such a transaction a Type 2 message. The Type 2 transaction would be rejected if it is broadcast prematurely, i.e. before the expiry time of the problem.

Mining Protocol

Consider a miner Mindy, who has formed a block of valid transactions and wants to add it to the blockchain. She has two choices for mining. She can either take part in Hashcash mining or solve one of the currently-unsolved problems on the blockchain. If she solves a Hashcash problem, everything will be similar to Bitcoin. She receives a block reward of f 1 and transaction fees from the transactions she has included in her block. As in Bitcoin, this is also how new coins are created in Hybrid Mining.

On the other hand, if she solves a previously-unsolved problem that has been proposed on the blockchain, she does not receive a block reward, but instead receives the solution reward r which was previously paid by the owner of the solved problem. In any case, Mindy can also claim her transaction fees. The exact protocol for adding a block by solving problems is explained in the next section.

Consensus Chain. As in Bitcoin, we consider the longest chain in the network to be the consensus chain. However, given that the difficulty of problem instances is not well-defined, we consider the length of a chain to be the sum of difficulties of those blocks in the chain that are mined by Hashcash.

Number of Blocks of Each Type. Note that each block that is mined by Hashcash creates f 1 new units of currency. On the other hand, one has to pay a proposal fee of f 1 to add a problem and this fee is burnt in case the problem gets solved and used for adding a new block to the chain. Hence, it is guaranteed that, at any point in time, there are at least as many blocks mined by Hashcash, as by solving proposed problems.

Solution Announcement and Reward Collection Protocol

If a miner Mindy finds a solution to Hashcash, she proceeds with announcing it in the same manner as in Bitcoin. No other miner can claim the rewards for this solution, because Mindy's identity is part of the Hashcash problem. However, if she wants to add a block by solving a proposed problem, she has to publish the solution. This is problematic, because Mindy's identity is not part of the problem, and another miner, Manny, might see the solution, form another block with the same solution and publish it shortly after Mindy. Then network latency can lead to a situation where part of the network believes Manny was the one who solved the problem first.

To avoid this problem, our protocol requires Mindy to announce the block in a two-step manner, as described below.

In the first step, Mindy chooses a secret value s, and then announces the block she has created, which consists of the following parts:

• A block header, showing that the block was created by solving a problem and pointing to the problem that is being solved. • Mindy's public key.

• A hash value h obtained by hashing a tuple consisting of the solution to the problem, the secret value s, and Mindy's public key.

• A deposit of 2 • f 1 + |φ| • f 2 currency units.
• A storage fee of n • f 2 units, which is a compensation for the whole network having to store the solution. Note that n is the number of variables in the problem instance. • A list of transactions that are being included in the new block. • A pointer to the previous block in the blockchain.

• A signature by Mindy, proving that she is the one who broadcast this block. We call this announcement a Type 3 message. Note that the block will be rejected by the network if another block in the blockchain is already claiming to have solved the same problem. By providing h, Mindy is committing to her solution without actually publishing it, i.e. she is promising that she has obtained a solution that, together with the secret value s and her public key, can produce the hash value h. After publishing this block, which includes paying a fee as a deposit for this promise, the block will be added to the blockchain by every node of the network. However, no reward is paid to Mindy until she provides the full solution, i.e. she neither receives her reward r , nor her transaction fees.

In the second step, Mindy has to publish a transaction, claiming the rewards of the block she added to the chain, as well as her deposit. We call this a Type 4 message. Mindy can opt to wait for the chain that includes her block to get longer, so that when she publishes the full solution she is already ensured that the chain will not revert and no one else can claim her rewards. However, there is a certain fixed length limit k, and Mindy has to publish her solution before the length of the chain containing her block is increased by k units. If she fails to do so, she will not receive her solution reward, transaction fees or deposit. Instead, the problem owner, Owen, will be refunded, i.e. he gets back all of his payments that were due to this problem.

Concretely, in the second step, when Mindy is already ensured that her block is going to remain in the blockchain, she can create a specific type of transaction for claiming her money. This transaction has the following parts:

• Mindy's public key,

• A pointer to the block whose rewards are being claimed,

• The full solution to the problem,

• The secret value s, and • A transaction fee.

When this transaction is published, other nodes of the network validate it by checking that (i) the solution is correct, (ii) the problem has not expired, (iii) the length of the chain has increased by at most k since the block was added, (iv) the hash of the tuple consisting of the solution, the secret value s, and Mindy's public key is the promised value h. If all the checks pass, Mindy's deposit will be returned back to her, and she will receive the problem reward r and the transaction fees in her block.

Note that all transactions are permanently saved on the blockchain and the second step transaction above contains the answer to the problem posed by Owen. So Owen can simply read the answer from the blockchain.

Overview of the System

We now summarize all parts of the Hybrid Mining protocol. Any aspect of the protocol that is not mentioned here follows the Bitcoin protocol as in [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. Table 1 provides a summary of constants that we use in Hybrid Mining. The values of these constants can be set at the time of implementation. In order to support mining by Constant Description

f 1
The block reward for mining a Hashcash block, and also the problem proposal fee for adding a new problem

f 2
The storage fee for storing one byte of data, either as part of a problem or its solution k

The maximum allowed waiting time between claiming a solution and announcing it. The time is measured by the increase in chain length.

m

The rate at which new Hashcash blocks are added to the blockchain, i.e. a new Hashcash block should be mined roughly every m minutes. The block is added to the Blockchain, but Mindy's deposit and rewards are not paid until she publishes the entire solution, hence proving her claim.

Solution Announcement

Miner (Mindy)

If the solution is correct, Mindy's deposit is paid back to her, together with the reward for solving the problem and transaction fees in the resulting block. 4 shows a diagram of the behavior of an honest problem owner, Owen, and Figure 5 shows the behavior of an honest miner, Mindy. The circled numbers in these figures denote the type of messages that are broadcast or waited for.

In our protocol, a network node works in exactly the same manner as in Bitcoin. It listens for transactions and blocks that are broadcast on the network. If it receives a valid new transaction, it broadcasts it to the rest of the network. Similarly, if it receives a valid new block, it adds the block to its local copy of the blockchain and broadcasts it (see Figure 6). Moreover, if a longer chain is formed, the node will adopt the new chain and broadcast it. Note that the length of a chain is defined in the same manner as Bitcoin and is the sum of difficulties of Hashcash problems solved in that chain. The only difference with Bitcoin comes from the additional checks solution by the network. Hence, Hybrid Mining satisfies requirement (1.a). As illustrated in Section 3.2, miners can choose to mine using Hashcash or solving previously-submitted problems. The former is done exactly the same manner as in Bitcoin and Section 3.3 provides a protocol for the latter. Hence, our approach satisfies requirements (1.b) and (1.c), as well. Therefore, we have the following proposition: Proposition 1. Hybrid Mining satisfies all the functional requirements listed in Section 2, i.e. it allows problem owners to submit their problems for solution in the same manner as in DPS, and allows miners to mine either by Hashcash or by solving problems.

Security Requirements Analysis

In this section, we analyze the security of Hybrid Mining against several attacks and show that it satisfies the security requirements of Section 2.

Resilience to Double Spending. Given that at any point, at least half of the blocks are mined by Hashcash, and that a new Hashcash block is added roughly every m minutes4 , our protocol is at least as resilient to forks and double spending as Bitcoin, and the same arguments for Bitcoin's resilience, as in [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF], can be applied to our setting without any change. Note that we consider the longest chain to be the consensus chain, and we define the length of a chain as the sum of difficulties of Hashcash blocks in the chain, ignoring the blocks obtained by problem solving. Hence, one cannot create a long chain and double spend by simply solving (possibly easy) problems. Therefore, Hybrid Mining is resilient to double spending and satisfies requirement (2.a).

Analysis of Incentives for Honest Behavior. In several points, our protocol relies on honest behavior of participants, including miners and problem owners. We now show that such behavior is always incentivized, and that the system is resilient to the following attacks:

• Falsely Claiming Solutions. In order to claim a solution, one has to pay a deposit of 2• f 1 +|φ|• f 2 . If the solution is incorrect or not provided later, f 1 + |φ| • f 2 units of this deposit is used to refund the problem owner, who might be the same person who published the false solution claim. However, at least f 1 units of currency will be burnt. Hence, adding a block by falsely claiming a solution has a cost of at least f 1 . Note that this means anyone can pay f 1 units just to add a new block, but this is not a rational strategy and does not have any other effect on the blockchain. • Invalidating a Problem. Another reason for falsely claiming solutions might be to invalidate a problem. For example, if a miner Mindy wants to hurt the problem owner Owen, she can publish a false solution. This leads to a refund for Owen, except for the transaction fees he paid for adding the problem. However, as mentioned before, such behavior will cost Mindy at least f 1 units, which is equal to a full block reward. A block reward is often much more than a transaction fee. Hence, this is not a rational attack for Mindy and has negligible effect on Owen. In both cases above, as well as in the other attacks mentioned below, the misbehaving party is never benefiting from his dishonest behavior. Rather, such dishonest actions lead to significant adverse effects and losses for the party that takes them. Hence, there is no incentive for such behavior and our approach satisfies requirement (2.d). Also note that, even if the attackers are assumed to be irrational and perform an attack despite losses it causes them, none of these attacks lead to significant losses, i.e. losses beyond a small transaction fee, for any other party.

Ensuring Miners are Rewarded for Solving a Problem. A miner who solves a problem can claim the reward set by the problem owner. We now show that our system is resilient to attacks that aim to deprive a miner from her problem solving reward or to steal the reward and claim it for another miner.

-Not Processing Another Miner's Transaction. This line of attack is between miners. Suppose Mindy has solved a problem and published her first step block. After a while, she publishes the transaction for claiming the rewards. Now suppose that the next block is mined by Manny can opt not to include Mindy's transaction in his block. However, this means that Manny loses the transaction fee. Hence, this is not a rational move for Manny. The only way that withholding transactions, as described above, can make sense for Manny, is if he expects to be able to claim the reward himself. However, this is never possible, because after the first step block is published by Mindy, either she gets the rewards or everything is refunded to the problem owner. Hence, Manny cannot steal the solution. -Replication Attack. Another type of attack between miners is as follows: when Mindy publishes her first step block, Manny can copy the block and replace Mindy's public key with his own. Then, part of the network would add Manny's block to their local copy of the blockchain, while the rest will add Mindy's. Then, when Mindy publishes her solution in the second step, Manny can copy the same solution and publish it as his own. Hence, at least part of the network would consider Manny's block as valid and if the chain containing Manny's block eventually happens to get longer, the attack has succeeded. However, this attack is not rational and is avoided by the fact that Mindy's public key is included in the hash value h. Hence, Manny cannot claim the solution for himself and get back his deposit and rewards, i.e. his second step transaction fails the hash check. Therefore, such an attack would have the same consequences as falsely claiming a solution. Given the discussion above, Hybrid Mining satisfies requirement (2.b).

Resilience to Spamming. A problem owner has to pay a problem proposal fee, a storage fee, a transaction fee and a reward for every problem he proposes. Therefore, proposing long spam problems is costly and not rational. Similarly, proposing a problem and then solving it on your own leads to a loss of the f 1 units of proposal fee. Hence, one would not rationally propose a problem that is already solved. Therefore, the system is safe against such attacks. Hence, Hybrid Mining satisfies requirement (2.c).

Given the discussion above, we have the following proposition: Proposition 2. Hybrid Mining satisfies all the security requirements listed in Section 2, i.e. it is resilient to attacks such as double spending, spamming, depriving a miner from her reward or stealing it, and other dishonest behavior mentioned above.

EXPERIMENTAL RESULTS

We implemented our approach in Java, and simulated both Hybrid Mining and classic Hashcash Mining for comparison.

Experiment Details. For classic Hashcash mining, we simulated a blockchain network with 10 miners. In our experiment, in order to speed up the simulation, a new Hashcash block is added roughly every 10 seconds, i.e. m = 1/6. Similarly, for Hybrid Mining, we simulated a network consisting of 10 miners and one problem proposer. The miners randomly choose to attempt either Hashcash or a problem that has not been claimed by another miner. For problems, we use a family of industrial benchmarks from the SAT 2009 competition, which originated from real-world computational biology problems [START_REF] Le | International SAT Competition[END_REF]. For mining by problem-solving, the simulated miners run an extremely efficient SAT solver called SAT4J [START_REF] Le | The SAT4J library, system description[END_REF].

Experiment Machine. The experiment was conducted on an Intel Xeon E5-1650 (12 Threads, 3.8 GHz, 12 MB Cache) machine running 64-bit Debian 8. The machine had a total memory of 128 GB and each network node was given a single thread.

Experimental Results. In our experiment, using Hybrid Mining increases the block mining rate by 87%, in comparison with classic Hashcash, without changing the computational power or energy consumption of the network. Figure 7 shows the number of blocks mined in each approach as time goes by. Hence, Hybrid Mining not only uses the computational power of blockchain for solving useful problems, but also helps the blockchain become more scalable. In practice, when this approach is used in a real-world blockchain, the increase in scalability would be dependent on the relative hardness of the submitted problems and Hashcash, and also the rate at which new problems are submitted to the network.

CONCLUSION

In this paper, we introduced Hybrid Mining: a new mining protocol that can exploit the vast computational power of the blockchain network for solving real-world useful problem instances by incentivizing the miners to solve them, while remaining compatible with the traditional Hashcash method of mining. We implemented our Figure 7: Scalability comparison of Hybrid Mining and Hashcash (using the same computational resources). The x axis is the time, and the y axis is the number of mined blocks. approach and simulated it, using problems from computational biology, showing that in addition to usefulness in DPS, Hybrid Mining can also make blockchains more scalable. We also analyzed the security of the new protocol and showed that it is at least as resilient to double spending as Bitcoin, while also providing several other security guarantees.

A natural direction of future work would be to deploy this protocol in a large scale by creating a new cryptocurrency. This can lead to a much higher total computational power than what was available to us for the experiments, and can be used for solving harder and more important practical problems, specifically in computational biology. An example of such problems is protein folding.

Figure 1 :

 1 Figure1: A Fork in the Blockchain: The two blocks B and C are both announced as valid successors to A. However, the chain containing B has become longer and is now the consensus chain. Hence, C and its successors will be dropped by the network nodes.

Figure 2 :

 2 Figure2: Bitcoin network's estimated hash rate (in trillions of hashes per second). The data is provided in[START_REF] Smith | Hash Rate: The estimated number of tera hashes per second (trillions of hashes per second) the Bitcoin network is performing[END_REF][START_REF]Quandl: Financial, Economic and Alternative Data[END_REF]. Note that the graph is in logarithmic scale.

Figure 3 :

 3 Figure 3: The growing energy consumption of Bitcoin mining. The solid line shows the estimated energy consumption and the dotted line is the minimum possible consumption.The graph above is adapted from[START_REF] De | Bitcoin's Growing Energy Problem[END_REF][START_REF]Bitcoin Energy Consumption Index[END_REF].

  (1.a) Owners of real-world problems should be able to publish their problems for distributed solution by the network, i.e. the computing power of the network should be usable for DPS. (1.b) Conversely, miners should be able to add new blocks to the blockchain by solving the problems published by others. Hence, creating an incentive for them to solve real-world useful problems. (1.c) Miners should have the option to use Hashcash for adding a new block, e.g. in cases when they are not able to solve any of the published real-world problems.

Figure 6 :

 6 Figure 6: The process used by a network node to check validity of a newly broadcast block.

Table 1 :

 1 Summary of Implementation-dependent constants in Hybrid Mining

	Type	Description	Issuer	Effect
		Problem	Problem
				Adds a new unsolved
	1	Proposal	Owner
				problem to the Blockchain.
		Transaction	(Owen)
			Problem	Refunds Owen if his
		Refund
	2		Owner	problem has expired or
		Transaction
			(Owen)	claimed but not solved.
		Committing to
		a Solution and	Miner
	3
		Announcing a	(Mindy)
		New Block

Table 2 :

 2 Summary of the 4 new types of messages in Hybrid Miningproblem solving, we introduced 4 new types of messages that are not present in Bitcoin. Table2summarizes the new message types. Figure

In Bitcoin, this predefined amount is set in a manner that ensures a new block is added roughly every 10 minutes.

In Bitcoin, and consequently in our approach, the length of a chain is not the number of blocks in that chain, but the sum of the hardnesses of the PoW problems that have been solved in that chain.

This time limit can be set by fixing the maximum number of Hashcash blocks that can be added to the chain without expiring the problem.

This constant time is set to 10 minutes in Bitcoin, but can be changed in implementation.

ACKNOWLEDGMENTS

The research was partially supported by Vienna Science and Technology Fund (WWTF) Project ICT15-003, Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Starting Grant (279307: Graph Games), and the IBM PhD Fellowship program.

that are performed for deciding whether blocks and transactions resulting from the 4 new types of messages are valid.

REQUIREMENTS ANALYSIS

In this section, we show how our Hybrid Mining protocol satisfies the requirements enumerated in Section 2. We deal with functional and security requirements separately.

Functional Requirements Analysis

Satisfaction of the functional requirements directly follows from the modeling and design of our protocols. The Problem Proposal Protocol of Section 3.1 allows all nodes to submit new problems for