{'fraction_non_alphanumeric': 0.04957257794166946, 'fraction_numerical': 0.01751592356687898, 'mean_word_length': 4.40666062528319, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence

In this paper, we present the Bennett-type generalization bounds of the learning process for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional results. In particular, we first develop two types of Bennett-type deviation inequality for the i.i.d. learning process: one provides the generalization bounds based on the uniform entropy number; the other leads to the bounds based on the Rademacher complexity. We then adopt a new method to obtain the alternative expressions of the Bennett-type generalization bounds, which imply that the bounds have a faster rate o(N^{-1/2}) of convergence than the traditional results O(N^{-1/2}). Additionally, we find that the rate of the bounds will become faster in the large-deviation case, which refers to a situation where the empirical risk is far away from (at least not close to) the expected risk. Finally, we analyze the asymptotical convergence of the learning process and compare our analysis with the existing results.


Introduction
In learning theory, one of the major concerns is to obtain the generalization bounds of the learning process for i.i.d. samples, which measure the probability that a function obtained in the i.i.d. learning process has a sufficiently small error [Vapnik, 1998, Bousquet et al., 2004. Generalization bounds have been widely used to study many topics of learning theory, e.g., the consistency of ERM-based learning processes [Vapnik, 1998], the asymptotic convergence of empirical process [Van der Vaart and Wellner, 1996] and the learnability of learning models [Blumer et al., 1989].
Deviation (or concentration) inequalities play an essential role in obtaining generalization bounds. There are many popular deviation and concentration inequalities, e.g., Hoeffding's inequality, McDiarmid's inequality, Bennett's inequality, Bernstein's inequality and Talagrand's inequality. Among them, Hoeffding's inequality and McDiarmid's inequality have been intensively used to obtain the generalization bounds based on the covering number (or uniform entropy number) and the Rademacher complexity, respectively [Mendelson, 2003, Van der Vaart andWellner, 1996]. To obtain the generalization bounds based on the VC dimension, Vapnik [1998] applied some classical inequalities, for example, Chernoff's inequality and Hoeffding's inequality, but also developed specific concentration inequalities. Bartlett et al. [2005] presented generalization bounds based on the local Rademacher complexity by using Talagrand's inequality. Additionally, there are also other works to study the generalization bound in statistical learning theory [Ben-David et al., 2010, Mohri andRostamizadeh, 2010]. However, to our best knowledge, there is little theoretical investigation into the generalization bounds derived from Bennett's inequality.

Motivation
The paper is motivated by the difference between Hoeffding's inequality [Hoeffding, 1963] and Bennett's inequality [Bennett, 1962]. It is well-known that Hoeffding's inequality is achieved by only exploiting the expectation information, and Bennett's inequality is based on both of expectation and variance. Intuitively, the Bennett-type generalization bounds should have a faster rate of convergence than that of the Hoeffdingtype results. However, to our best knowledge, this issue has not been well explored in the literature. In this paper, we will give a theoretical argument to show the faster rate of the Bennett-type results.

Overview of Main Results
In this paper, we are mainly concerned with the following three aspects: (1) Bennett-type deviation inequality; (2) Bennett-type generalization bounds; (3) rate of convergence.
By extending the classical Bennett's inequality, we use the martingale method to develop a Bennett-type deviation inequality for the case of multiple random variables and this inequality leads to the generalization bounds based on the uniform entropy number (UEN). Moreover, under the bounded-difference condition, we present another Bennett-type deviation inequality that is similar to McDiarmid's inequality. We use this deviation inequality to further obtain the generalization bounds based on the Rademacher complexity. Note that the aforementioned generalization bounds are said to be of Bennett-type, because they are derived from the Bennett-type deviation inequalities.
In order to analyze the rate of convergence of the bounds, one needs to obtain the alternative expressions of the Bennett-type generalization bounds. Differing from the Hoeffding-type bounds [see (7)], the expression of ] are not welldefined and thus it is difficult to directly present the alternative expressions of the Bennett-type bounds. 1 Instead, one generally transforms the Bennett-type bound to the Bernstain-type one and then obtains the corresponding alternative expression showing that the bound has the rate O(N − 1 2 ) of convergence, which is in accordance with the classical result (8). Here, we use a new method to obtain another alternative expression of the Bennett-type bound and show that the Bennett-type bounds have a faster rate o(N − 1 2 ) of convergence than the classical result O(N − 1 2 ). Additionally, we point out that the rate of the bounds will become faster as the discrepancy between the empirical risk and the expected risk becomes larger. This situation is called as the large-deviation case [see Remark 4.3].
Note that it is well-known that the rate of the empirical Rademacher complexity is up to O(N − 1 2 ) [see (10)], and thus it seems to be a contradiction that the Bennett-type bounds have a faster rate o(N − 1 2 )) [see Remark 5.1]. An explanation to the contradiction is given to support the theoretical findings on the faster rate of convergence.

Organization of the Paper
The rest of this paper is organized as follows. Section 2 formalizes the main issues of this paper and briefs the classical results. In Section 3, we present two Bennetttype deviation inequalities for the case of multiple random variables. Section 4 provides the generalization bounds and a new upper bound of the Rademacher complexity is presented in Section 5. In Section 6, we analyze the asymptotic convergence of the i.i.d. learning process and the last section concludes the paper. The proofs of the main results are given in the long version of this paper. 2

Preliminaries
In this section, we first introduce some notations to formalize the proposed research of this paper, and then present the definitions of the covering number, the uniform entropy number and the Rademacher complexity. Moreover, we also brief the classical results of the Heoffding-type generalization bounds of the i.i.d. learning process.

Problem Setup
Let X ⊂ R I and Y ⊂ R J be an input space and its corresponding output space, respectively. Denote Z := X × Y ⊂ R I × R J with K = I + J. Let G ⊂ Y X be a function class with the domain X and the range Y. Given a loss function : Y 2 → R, it is expected to find a function g * ∈ G : X → Y that minimizes the expected risk over G where P(z) stands for the distribution of z = (x, y).
Generally, the distribution P(z) is unknown and thus the target function g * cannot be directly obtained by minimizing (1). Instead, we can apply the empirical risk minimization (ERM) principle to handle this issue [Vapnik, 1998]. Given a function class G and a set of i.i.d. samples Z N 1 := {z n } N n=1 drawn from Z, we define the empirical risk of g ∈ G as which is considered as an approximation to the expected risk (1). Let g N ∈ G be the function that minimizes the empirical risk (2) over G and deem g N as an estimate to g * with respect to Z N 1 . In the aforementioned i.i.d. learning process, we are mainly interested in the following two types of quantities: , which corresponds to the estimation of the expected risk from an empirical quantity; • E( • g N ) − E( • g * ), which corresponds to the performance of the ERM-based algorithm.
Recalling (1) and (2), since and thus This shows that the asymptotic behaviors of the aforementioned two quantities, when the sample number N goes to infinity, can both be described by the supremum sup which is the so-called generalization bound of the i.i.d. learning process.
For convenience, we define the loss function class and call F as the function class in the rest of this paper. By (1) and (2), given a sample set Z N 1 drawn from Z, we briefly denote for any f ∈ F, Thus, we rewrite the generalization bound (3) as

Complexity Measures of Function Classes
Generally, the generalization bound of a certain learning process is achieved by incorporating the complexity measure of the function class, e.g., the covering number, the VC dimensions and the Rademacher complexity. This paper is mainly concerned with the covering number, the uniform entropy number (UEN) and the Rademacher complexity.

Covering Number and Uniform Entropy Number (UEN)
The following is the definition of the covering number and we refer to Mendelson [2003] for details.
Definition 2.1 Let F be a function class and d be a metric on F. For any ξ > 0, the covering number of F at radius ξ with respect to the metric d, denoted by N (F, ξ, d) is the minimum size of a cover of radius ξ.
For clarity of presentation, we give a useful notation for the following discussion. Given a sample set as the ghost-sample set drawn from Z such that the ghost sample z n has the same distribution as z n for we then obtain the covering number N F, ξ, p (Z 2N 1 ) . The uniform entropy number (UEN) is a variant of the covering number and we refer to Mendelson [2003] for details as well. By setting the metric p (Z N 1 ) (p > 0), the UEN is defined as follows:

Rademacher Complexity
The Rademacher complexity is one of the most frequently used complexity measures of function classes and we refer to Bousquet et al. [2004] for details.
Definition 2.2 Let F be a function class and {z n } N n=1 be a sample set drawn from Z. Denote {σ n } N n=1 as a set of random variables independently taking either value of {−1, 1} with equal probability. The Rademacher complexity of F is defined as with its empirical version where E stands for the expectation taken with respect to all random variables {z n } N n=1 and {σ n } N n=1 , and E σ stands for the expectation only taken with respect to random variables {σ n } N n=1 .

Classical Hoeffding-type Generalization Bounds
Next, we summarize some classical results of the generalization bounds. Note that the following bounds are said to be of Hoeffding-type, because they are derived from (or strongly related to) Hoeffding's inequality and Hoeffding's lemma [Hoeffding, 1963].
First, based on the covering number, one can use Hoeffding's inequality (or Hoeffding's lemma) to obtain the following generalization bound w.r.t. a function class F with the range [a, b] [see Mendelson, 2003, Theorem 2.3]: for any (7) which is one of the most frequently used generalization results in statistical learning theory. Because of its well-defined expression, we can directly obtain its alternative expression: for any Following the alternative expression (8), it is observed that the generalization bound sup f ∈F E N f − Ef has a convergence rate of O(N − 1 2 ).
On the other hand, McDiarmid's inequality can provide the following generalization bound based on the Rademacher complexity [see Bousquet et al., 2004, Theorem 5]: for any > 0 and f ∈ F, with probability at least 1 − , which is also of Hoeffding-type, because McDiarmid's inequality is actually derived from Hoeffiding's lemma under the condition that f has the bounded-differences property [see Bousquet et al., 2004, Theorem 6]. Furthermore, it is followed from Sudakov minoration for Rademacher processes 3 [Talagrand, 1994b,a, Lata la, 1997] and Massart's finite class lemma (Dudley's entropy integral) 4 [Mendelson, 2003, Van der Vaart andWellner, 1996] that: which shows the lower and the upper bounds of the empirical Rademacher complexity R N (F). The combination of (9) and (10) implies that the rate of con-

Bennett-type Deviation Inequalities
By extending the classical Bennett's inequality [Bennett, 1962] to the case of multiple random variables, this section will present two Bennett-type deviation inequalities for the i.i.d. learning process. We also refer to Bousquet [2002] for the application of Bennett's inequality in the empirical process.
Then, we have for any 0 < ξ < N (b − a), where The proof of this result is processed by the martingale method. Compared to the classical Bennett's inequality, this result is valid for the case of multiple random variables and provides the convenience to obtain the generalization bound of the i.i.d. learning process. Especially, the two inequalities will coincide, if there is only one random variable.
Moreover, recalling the classical McDiarmid's inequality [see Bousquet et al., 2004, Theorem 6], it is actually derived from Hoeffiding's lemma under the condition that f has the bounded-differences property. Thus, McDiarmid's inequality has a similar expression to that of Hoeffding's inequality and the two inequalities coincide if there is only one random variable. Similarly, we obtain another Bennett-type deviation inequality under the bounded-difference condition: Theorem 3.2 Let z 1 , · · · , z N be N independent random variables taking values from Z. Assume that there exists a positive constant such that the function H : Z N → R satisfies the bounded-difference condition: for any 1 ≤ n ≤ N , sup z1,··· ,z N ,z n H z 1 , · · · , z n , · · · , z N − H z 1 , · · · , z n , · · · , z N ≤ c.
Then, we have for any ξ > 0 Pr H z 1 , · · · , z n , · · · , z N (15) The inequality (15) is an extension of the classical Bennett's inequality and the two results will coincide if there is only one random variable as well.
Subsequently, we will use the above two deviation inequalities to obtain the generalization bounds based on the uniform entropy number and the Rademacher complexity, respectively.

Bennett-type Generalization Bounds
In this section, we will show the Bennett-type generalization bounds of the i.i.d learning process. The derived bounds are based on the uniform entropy number (UEN) and the Rademacher complexity, respectively. Note that since the presented bounds (16), (18) and (23) are derived from the Bennett-type deviation inequalities, they are said to be of Bennett-type as well.

UEN-based Generalization Bounds
By using the deviation inequality (12) .
This theorem implies that the probability of the event that the generalization bound sup f ∈F Ef − E N f | is larger than any ξ > 0 can be bounded by the righthand side of (16). We can find that the expression of the bound is similar to that of Bennett's inequality.
Different from the aforementioned Hoeffding-type result (7) and its alternative expression (8), it is difficult to directly achieve the alternative expression of the Bennett-type bound (16), because it is difficult to obtain the analytical expression of the inverse function of Γ(x) = x−(x+1) ln(x+1). Instead, one generally uses the term −x 2 2+(2x/3) to approximate the function Γ(x) and then get the so-called Bernstein's inequality. 5 In the same way, we can obtain the following alternative expression of the Bennett-type result (16): which implies that the rate of convergence of the Bennett-type bound is also up to O N − 1 2 . It is in accordance with the rate of the aforementioned classical results (8). For convenience, the alternative expression is said to be of Bernstein-type if no confusion arises.

Large-deviation Case
Subsequently, we will show that the Bennett-type bounds can reach a faster rate of convergence in the large-deviation case.

Remark 4.3
The word "large-deviation" means that the discrepancy between the empirical risk and the expected risk is large (or not small). Given any ξ > 0, one of our major concerns is the probability Pr sup f ∈F E N f − Ef > ξ , and then we say that the case the value of ξ approaches to (b − a) is of largedeviation. 6 Actually, the large-deviation case is referring to a situation where the empirical quantity E N f is far away from (at least not close to) the expected risk Ef . As shown in Fig. 1, for any β 1 ∈ (0.0075, 0.4434], the curve of γ(β 1 ; x) is monotonically decreasing w.r.t.
In contrast, the Hoeffding-type results consistently provide the rate O(N − 1 2 ) regardless of the discrepancy between E N f and Ef . Thus, the Bennett-type results can give a more detailed description to the asymptotical behavior of the learning process.

Effect of the Parameter β 1
As addressed in the introduction, the main motivation of this paper is to study whether the Bennett-type generalization bounds have a faster rate of convergence than that of the Hoeffding-type generalization results, because the Bennett-type results are derived from the corporation of the expectation information and the variance information and in contrast, the Hoeffdingtype results are only related to the expectation information. However, the main challenge to analyze the rate lies in obtaining the alternative expression of the bound (16), because it is difficult to analytically express the inverse function of Γ(x). Instead, we exploit the term −βx γ to substitute Γ(x) [see (20)] and Fig.  2 illustrates the validity of this method. In Fig. 2, the curve e −x 2 /32 and e Γ(x/8) correspond to the Hoeffdingtype bound (7) and the Bennett-type bound (16), respectively. Evidently, setting β 1 = 0.4804 makes the curve e −β1(x/8) 2 almost coincide with the curve e Γ(x/8) .

Rademacher-complexity-based Generalization Bounds
By using the deviation inequality (15), we can obtain the generalization bounds based on the Rademacher complexity: Theorem 4.4 Assume that F is a function class consisting of functions with the range [a, b]. Let Z N 1 = {z n } N n=1 be a set of i.i.d. samples drawn from Z. Then, for any f ∈ F, we have with probability at least 1 − , where β 2 is taken from the interval (0.0075, 0.3863), := exp N Γ(x) and 0 < γ β 2 ; x ≤ γ < 2 (x ∈ (0, 1]) with γ(β; x) defined in (19).
The above theorem presents the Bennett-type generalization bounds based on the Rademacher complexity. Compared to the classical Rademacher-complexitybased results (9), the new bounds (23) incorporate a term O N − 1 γ (i.e., o N − 1 2 because γ < 2) with a faster rate of convergence than the term O N − 1 2 appearing in (9), when N goes to infinity.

Bounds of Rademacher Complexities
Recalling (16) and (23), it is observed that there might be a contradiction: Remark 5.1 The generalization bound (16) has the faster rate o N − 1 2 , while the magnitude of the empirical Rademacher complexity has been proved to be O N − 1 2 as shown in the classical result (10).
In order to explain this contradiction, we should consider the following two questions: (Q1) whether the empirical Rademacher complexity R N (F) can totally describe the behavior of Rademacher complexity R(F); (Q2) whether the classical results (10) are either applicable to R(F).

Answer to Question Q1
Recalling (9) and (23), the quantity (Ef −E N f ) is originally bounded by the Rademacher complexity R(F), while it is difficult to compute R(F) due to the unknown distribution of Z N 1 . Instead, by using deviation inequalities (e.g. Hoeffding's inequality and Bennett's inequality), one can further bound R(F) by using its empirical version R N (F) as follows: with probability as least 1 − /2, However, the behavior of Rademacher complexity R(F) cannot be totally described by its empirical version R N (F). In fact, the joint distribution of σ n f (z n ) may not be a Rademacher process because z is a random variable of an unknown distribution.

Answer to Question Q2
Recalling (10), the lower and the upper bounds of R N (F) are respectively derived from the Sudakov minoration for Rademacher processes and Massart's finite class lemma, both of which are strongly related to (or have the similar forms as that of) the Hoeffdingtype results. 7 Thus, all Hoeffding-type conclusions mentioned in Section 2.3 are consistent.
However, as answered above, the joint distribution of σ n f (z n ) may not be a Rademacher process. Since Sudakov minoration is not valid for an arbitrary process [see Talagrand, 1994b,a, Lata la, 1997, the lower bound of R N (F) with the rate O(N − 1 2 ) is not applicable to the lower bound of R(F).
Additionally, we also need to consider the following question: why we do not use Bennett's inequality to obtain the upper bound of R N (F)? In fact, in order to obtain the upper bound of R N (F), one needs 7 Recalling Massart's finite class lemma, the main step of its proof is processed by using a term e λ 2 r 2 /2 which is also similar to the term e λ 2 r 2 /8 appearing in Hoeffding's lemma. See http://ttic.uchicago.edu/∼tewari/lectures/lecture10.pdf to consider the following term Ee σf (z) . Since σ is a Rademacher variable taking values from {±1} with equivalent probability for a given sample z, there holds that which differs from the related formula (28) in Lemma A.1 that is built in the case that the distribution of z is unknown.

Asymptotical Convergence
Based on the generalization bound (16), we study the asymptotic convergence of the i.i.d. learning process.
We also give a comparison with the existing results.
Recalling (13), it is noteworthy that there is only one solution x = 0 to the equation Γ(x) = 0 and Γ(x) is monotonically decreasing when x ≥ 0 [see Fig. 3]. Following Theorem 4.1, we can directly obtain the following result indicating that the asymptotic convergence of the i.i.d. learning process is determined by the uniform entropy number ln N 1 (F, ξ/8, 2N ). Ef − E N f > ξ = 0.
As shown in Theorem 6.1, if the uniform entropy number ln N 1 (F, ξ/8, 2N ) satisfies the condition (24), the probability of the event sup f ∈F Ef − E N f > ξ will converge to zero for any ξ > 0, when the sample number N goes to infinity. This is in accordance with the classical result shown in (7): the probability of the event that sup f ∈F Ef − E N f > ξ will converge to zero for any ξ > 0, if the uniform entropy number ln N 1 (F, ξ/8, 2N ) satisfies the same condition as (24).

Conclusion
In this paper, we present the Bennett-type generalization bounds and analyze the rate of convergence of the derived bounds. In particular, we first extend the classical Bennett's inequality to develop two Bennett-type deviation inequalities. Based on the derived inequality, we then obtain the generalization bounds based on the uniform entropy number and the Rademcaher complexity, respectively.
Moreover, we show that the Bennett-type generalization bounds have a faster rate o(N − 1 2 ) of convergence than the rate O(N − 1 2 ) of the classical Hoeffding-type results [see (7) and (8)]. Especially, we show that the rate will become faster in the large-deviation case, where the empirical risk E N f is far away from the expected risk Ef . In contrast, the Hoeffding-type results provide the rate O(N − 1 2 ) regardless of the discrepancy between E N f and Ef . From view of this point, the Bennett-type results give a more detailed description to the asymmetrical behavior of the learning process.
We give an explanation to the "contradiction" mentioned in Remark 5.1.
As shown in Talagrand [1994b,a], Lata la [1997], Sudakov minoration provides a lower bound of the empirical Rademacher complexity R N (F) with the rate O(N − 1 2 ) [Mendelson, 2003], because the empirical Rademacher complexity R N (F) actually is a special case of subgaussian process given a sample set {z n } N n=1 . In contrast, it is difficult to specify the distribution characteristics of R(F) and thus the classical result (10) could not be applied to bound R(F).