Statistical Learning Theory: Slow and fast learning bounds

Extract from my upcoming thesis - 20/03/20

Statistical learning theory

Summary: This chapter is a short introduction to statistical learning theory, which focuses on the derivation of bounds on the generalization error for the binary classification problem. For that matter, we first present the probabilistic setting associated to binary classification and the associated risks. Then, to bound the excess risk of the empirical minimizer, we introduce a few basic concentration inequalities, followed by strategies to relate the excess risk to the complexity of a proposal class, which enable us to derive generalization bounds that are independent of the distribution of the data. Next, we address the looseness of those bounds with more involved concentration inequalities, which, combined with noise assumptions on the distribution of the data, imply fast, distribution-dependent bounds on the generalization error. Finally, we dwelve into the necessary notions to extend those results for the problems tackled in the thesis, and refer to the specific parts of those that require the tools and results presented here. We refer the reader to (Bousquet, Boucheron, and Lugosi 2004), (Boucheron, Bousquet, and Lugosi 2005) and (Györfi 2002) for more detailed introductions on statistical learning theory.

1 - Introduction

Statistical learning theory is described in (Bousquet, Boucheron, and Lugosi 2004, chap. 1) as a mathematical framework for studying the problem of inference, that is of gaining knowledge about some modeled phenomenon from data. It can be considered as a mathematical tool that justifies the soundness of performing machine learning, i.e. of using data collected in some specific context, e.g. in the past, to make decisions in another context, e.g. in the future. For that to be sensible, one has to make assumptions as to how the data collected - called training data - relates to the testing data, and those assumptions are referred to as inductive bias.

Generally, one collects data that belong to a input space \(\mathcal{X}\), also called feature space, that is often a \(d\)-dimensional Euclidean space, i.e. \(\mathcal{X}= \mathbb{R}^d\). Using that information, one wishes to gain knowledge about some value that belongs to an output space \(\mathcal{Y}\). To study the relationship between the collected features and the output value, those are modeled as a pair of dependent random variables r.v. \((X, Y) \in \mathcal{X}\times\mathcal{Y}\) that follow some unknown joint distribution \(P\) defined on a probability space \((\Omega, \mathcal{A}, \mathbb{P})\). We refer to the two first chapters of (Shorack 2000) for a thorough definition of these mathematical objects. The random variable \(Y\) is referred to as the output r.v., while \(X\) is referred to as the input r.v.. We introduce the distribution of \(X\) as \(F\), called the marginal distribution of \(X\), see (Papoulis 1965 Chapter 6, page 171). Mathematically, statistical learning theory is generally interested in recovering some information about distribution of the output r.v. for any possible value of the input r.v. \(X\), i.e. about the conditional random variable \(Y | X=x\) for any \(x \in A\), with \(A \subset \mathcal{X}\) such that (s.t.) \(\mathbb{P}\{X \in A \}=1\). The distribution \(P\) can be decomposed as \(F \times P_{Y|X}\), with \(P_{Y|X}\) the conditional distribution of \(Y\) given \(X\). It is referred to as the posterior probability of \(Y\), and its existence is justified in (Shorack 2000 Chapter 8, Theorem 5.2).

Many learning problems assume that the output random variable \(Y\) is binary, i.e. \(\mathcal{Y}= \{ -1, +1 \}\), such as binary classification or bipartite ranking. Under that assumption, the posterior probability \(P_{Y|X}\) is summarized by the mapping \(\eta\) with: \[\begin{align} \eta : \; \mathcal{X}&\to [0,1],\\ x & \mapsto \mathbb{P}\{ Y=+1 \mid X=x\},\end{align}\] which is referred to as the regression function or as the Bayes scorer in the bipartite ranking literature. The distribution \(P\) is completely characterized by the pair \((F, \eta)\). Another way to specify \(P\) is to define the proportion of positive instances \(p = \mathbb{P}\{ Y = +1 \}\) and the distribution of the conditional random variables \(X|Y=y\) with for both \(y = +1\) and \(y = -1\) as \(G\) and \(H\), respectively. Then, the two characterizations are related by the relations \(G = \eta F/p\) and \(H = (1-\eta)F/(1-p)\) and \(p = \int \eta(x)dF(x)\). They imply \(F = pG + (1-p)H\) and \(\eta/(1-\eta) = pG/( (1-p)H)\).

We now focus on the binary classification problem, and refer to the thesis for a discussion on the extension of those results to other settings. The goal of binary classification is to find a function \(g: \mathcal{X}\to \mathcal{Y}= \{-1, +1\}\) in a class of candidate functions \(\mathcal{G}\) that minimizes the misclassification error \(R(g)\), \[\begin{align} R(g) := \mathbb{P}\{ g(X) \ne Y \}.\end{align}\] The following proposition characterizes the best classifier in the set of all measurable functions.

Proof

Note that \(R(g^*) = \mathbb{E}[\min(\eta(X), 1-\eta(X))]\), which means that \(g^*\) has a positive risk unless \(\eta(X) \in \{0, 1\}\) a.s., which means that the Bayes classifier makes classification mistakes unless the classes are separable. A sensible goal when selecting a candidate function in \(\mathcal{G}\) is to find \(g \in \mathcal{G}\) with \(R(g)\) as close as possible to \(R(g^*)\), which is measured by the notion of excess risk, defined as: \[\begin{align} E(g) := R(g) - R(g^*).\end{align}\]

Unlike for Remark 4, in most cases, the class \(\mathcal{G}\) is not large enough to contain the Bayes classifier \(g^*\). Then, the gap in performance between any minimizer \(g^\dagger\) of \(R\) in \(\mathcal{G}\), i.e. \(g^\dagger \in {\arg \min}_{g\in\mathcal{G}} \; R(g)\), and \(g^*\) is quantified by the approximation error defined as: \[\begin{align} R(g^\dagger) - R(g^*) > 0.\end{align}\] Controlling the approximation error generally requires an assumption about the smoothness of the target function. One way to introduce this type of assumption is to assume that the regression function \(\eta\) belongs to a Sobolev space, see (Jost 2011 Appendix A.1). While results exist in the case of regression, see e.g. (Smale and Zhou 2011), bounding the approximation error in classification remains an open problem.

Since \(P\) is unknown, we cannot directly measure the risk \(R\). The general idea of statistical learning is to use a notion of empirical risk to approximate \(R\). Introduce a sequence of \(n\) i.i.d. pairs with the same distribution as \((X,Y)\), i.e. \(\mathcal{D}_n = \{(X_i, Y_i)\}_{i=1}^n \overset{\text{i.i.d.}}{\sim} P\), we define the empirical risk \(R_n\), on the data \(\mathcal{D}\) as: \[\begin{align} \label{eq-estimate-empirical-risk}\tag{2} R_n(g) := \frac{1}{n} \sum_{i=1}^n \mathbb{I}\{ g(X_i) \ne Y_i \},\end{align}\] and denote by \(g_n\) the minimizer of \(R_n\) over \(\mathcal{G}\). The precision of the approximation of \(R\) by \(R_n\), and as a result, the choise of \(g_n\), depends on the difference between the empirical distribution and the real distribution, illustrated in Section 3. A quantity of interest is the risk \(R(g_n)\) of the minimizer of the empirical risk, as it quantifies the performance of the classifier learned from data. Observe, that, since \(R_n(g_n) \le R_n(g^\dagger)\) by definition of \(g_n\), we have: \[\begin{align} E(g_n) &\le R(g^\dagger) - R(g^*) + R(g_n) - R_n(g_n) + R_n(g^\dagger) - R(g^\dagger),\\ &\le R(g^\dagger) - R(g^*) + 2 \sup_{g\in\mathcal{G}} { \lvert R_n(g) - R(g)\rvert }. \label{eq-sup_emp_bound}\tag{3}\end{align}\] Eq. (3) shows that one can bound the excess of risk by the approximation error plus the uniform deviation \({ \lVert R_n - R\rVert }_{\mathcal{G}} := \sup_{g\in\mathcal{G}} { \lvert R_n(g) - R(g)\rvert }\) of \(R_n(g) - R(g)\) over \(\mathcal{G}\), which quantifies the generalization error. The bound can be seen as a formalization of the bias-variance tradeoff presented in (Domingos 2012), where the bias term corresponds to the approximation error, while the variance corresponds to the generalization error. When one increase the size of the proposal family \(\mathcal{G}\), the approximation error decreases, while the generalization error increases.

The learning bounds presented throughout the thesis consist in PAC (probably approximately correct)-style bounds, i.e. bounds satisfied for any outcome \(\omega \in A_\delta\) for some \(A_\delta \subset \Omega\) with \(\mathbb{P}\{ A_\delta \} \ge 1 - \delta\), for similar types of uniform deviations over diverse families of functions. All of the bounds concern the generalization error.

Firstly, Section 2 shows how to derive an uniform learning bound, i.e. bounds that do not depend on the distribution of the data, i.e. that hold for the most complicated distributions \(P\) possible, but tend to be quite loose for sensible distributions. Secondly, Section 3 responds to this weakness by deriving tighter bounds under mild assumptions on the data. Finally, Section 4 discusses the extension of such results to the more complicated statistics involved in the thesis and indexes the uses of the tools and results of this chapter in the thesis.

2 - Uniform learning bounds

Most learning bounds are based on the Chernoff bound, which bounds the tail \(\mathbb{P}\{ Z > t\}\) of a r.v. \(Z\) using its moment generating function \(\lambda \mapsto \mathbb{E}[e^{\lambda Z}]\), as shown below.

Proof

By substituting \(Z\) with \({ \lVert R_n - R\rVert }_\mathcal{G}\) in Eq. (4), one sees that controlling the uniform deviation can be achieved by combining two separate results. Specifically, one needs to control \(\mathbb{E}[Z]\), a term that measures the expressivity of the proposal class \(\mathcal{G}\), and a term \(Z-\mathbb{E}[Z]\) a term that measures the robustness of the process of selecting \(g\) from data. For sensible families \(\mathcal{G}\), both of these quantities decrease to zero when \(n\) increases, but with different convergence speeds. The parameter \(\lambda\) is typically selected to balance the speeds of convergence of the two terms.

Section 2.1 presents basic concentration inequalities, that are required to study the terms \(\mathbb{E}[Z]\) and \(Z-\mathbb{E}[Z]\) where \(Z = { \lVert R_n - R\rVert }_\mathcal{G}\). Controlling the convergence of \(\mathbb{E}[Z]\) is based on controlling the complexity of the proposal class of functions \(\mathcal{G}\), which is dealt with in Section 2.2. Finally, Section 2.3 exploits the results of Section 2.2 and the McDiarmid’s inequality presented in Section 2.1 to conclude.

2.1 - Basic concentration inequalities

Three distinct but related formulations exist for any result of Section 2.1. One can write as a bound on the tail \(\mathbb{P}\{Z>t\}\) of a r.v. \(Z\), or a bound on the moment generating function \(t \mapsto \mathbb{E}[e^{tZ}]\) of a r.v. \(Z\), which relates simply to the tail of \(Z\) with Chernoff’s bound, see Proposition 3. One form implies the other, and all theorems can be stated in any of those two forms. Finally, consider a bound on the tail of a r.v. \(Z\) that writes \(\mathbb{P}\{ Z > t \} \le f(t)\), and define \(t_\delta\) as the solution in \(t\) of \(\delta = f(t)\) with some \(\delta > 0\). The bound \(\mathbb{P}\{ Z > t \} \le f(t)\) is then equivalent to a simple inequality of the form \(Z \le t_\delta\), that holds with probability (w.p.) larger than (\(\ge\)) \(1-\delta\). For example, Corollary 3 below is provided in that last formulation.

The most famous concentration inequality is Hoeffding’s inequality (Györfi 2002 Theorem 1.2), which gives a PAC bound on the deviation of the mean of bounded i.i.d. r.v.’s from their expectation of the order \(O(n^{-1/2})\). It stems from a simple bound on the tail \(\mathbb{P}\{ Z > t\}\) of a bounded random variable \(Z\), a property introduced in (Györfi 2002 Lemma 1.2 ) and presented in the lemma below.

Proof Proof

One can bound the tail of \({ \lvert \bar{Z}_n - \mathbb{E}[\bar{Z}_n]\rvert }\) using the union bound, also referred to as the subadditivity of measures or Boole’s inequality, (Shorack 2000 Chapter 1, Proposition 1.2), between Corollary 3 and its application to the family \(-Z_1, \dots, - Z_n\), which writes: \[\begin{align} \mathbb{P}\{ { \lvert \bar{Z}_n - \mathbb{E}[\bar{Z}_n] \rvert } > t \} \le \mathbb{P}\{ \bar{Z}_n - \mathbb{E}[\bar{Z}_n] > t \} + \mathbb{P}\{ \mathbb{E}[\bar{Z}_n] - \bar{Z}_n > t \} \le 2 e^{-2t^2 n /(b-a)^2}.\end{align}\]

The Hoeffding inequality on its own implies guarantees for finite families of functions \(\mathcal{G}\), as presented in (Bousquet, Boucheron, and Lugosi 2004, sec. 3.4) and shown in the corollary below:

Proof

The result presented in Lemma 1 can be used to derive bounds on the expectation of the maximum of a family of random variables, as shown in the following lemma. It is useful when considering minimizers of the empirical risk, to upper-bound the value of \(\mathbb{E}[{ \lVert R_n - R\rVert }_\mathcal{G}]\) presented in Section 1.

Proof

One can again bound the tail of \(\max_{j\le m} { \lvert Z_j\rvert }\) by applying the preceding result to a family of \(2m\) elements by considering \(\max(Z_1, -Z_1, \dots, Z_m, -Z_m)\). Now that we have presented inequalities to deal with the term \(\mathbb{E}[{ \lVert R_n - R\rVert }_\mathcal{G}]\), we introduce the one that controls the deviation of \(\mathbb{E}[{ \lVert R_n - R\rVert }_\mathcal{G}]\) from its mean.

Proof

2.2 - The complexity of classes of functions

This section regroups several ways used to control the complexity of a class of proposal functions \(\mathcal{G}\), referred to as capacity measures in (Boucheron, Bousquet, and Lugosi 2005). Those include Rademacher averages, the concept of shatter coefficient and VC dimension, as well as covering numbers. First, we introduce the notion of Rademacher average and relate it to the notion of VC dimension. For an introduction to covering numbers in this context, we refer to (Boucheron, Bousquet, and Lugosi 2005 Section 5.1).

The Rademacher average measures the capacity of a family of functions to fit random noise, and can be used to bound the expectation of \({ \lVert R_n - R\rVert }_\mathcal{G}\), as shown in the following proposition.

Proof

While the notion of Rademacher average is a standard analysis tool, is used for many important results, e.g. in the derivation of sharp bounds for the supremum of empirical processes, see (Györfi 2002 Section 1.4.6), and allows for the derivation of data-dependent bounds, see e.g. (Boucheron, Bousquet, and Lugosi 2005 Theorem 3.2), it does not relate directly to simple properties of the proposal family.

Introduce the shatter coefficient \(\mathbb{S}_\mathcal{G}(n)\) of a family of functions \(\mathcal{G}\) as the maximal number of ways to split any collection of \(n\) elements in \(\mathcal{X}\times\mathcal{Y}\) with \(\mathcal{G}\), formally: \[\begin{align} \label{eq-def-shatter}\tag{9} \mathbb{S}_\mathcal{G}(n) = \sup_{\{ (x_i, y_i)\}_{i=1}^n \in (\mathcal{X}\times \mathcal{Y})^n} { \lvert \left\{ (\mathbb{I}\{g(x_1) \ne y_1\}, \dots, \mathbb{I}\{g(x_n) \ne y_n\} ) \mid g \in \mathcal{G} \right\}\rvert }.\end{align}\] Note that the shatter coefficient does not depend on the sample \(\mathcal{D}_n\), and is bounded by \(2^n\). A set of \(n\) points is said to be shattered by a family \(\mathcal{G}\) if its shatter coefficient is equal to \(2^n\), with the convention that the empty set is always shattered.

Lemma 3 can be used to link the Rademacher average with the shatter coefficient, which in turn enable us to replace the supremum over \(\mathcal{G}\) with a maximum over a set of \(\mathbb{S}_\mathcal{G}(n)\) vectors, as detailed in the following corollary.

Proof

The combination of Proposition 2 and Corollary 2 is referred to as the Vapnik-Chervonenkis inequality, see (Györfi 2002 Theorem 1.9, page 13). When the class \(\mathcal{G}\) is finite of size \(N\), then we have that \(\mathbb{S}_{\mathcal{G}}(n) \le N\), which implies a bound on \(\mathbb{E}\left[ { \lVert R_n-R\rVert }_\mathcal{G} \right]\) that decreases in \(O(n^{-1/2})\). While the shatter coefficient gives a simpler bound on the Rademacher average by removing the expectation, the bound depends of \(n\), and determining the shatter coefficients of simple families of functions is not intuitive. On the other hand, the VC-dimension is intuitive and summarizes the complexity of a class of functions by a single coefficient.

The following lemma relates the VC-dimension to the shatter coefficient.

Proof

All of the results of Section 2.2 come into play to control the quantity \(\mathbb{E}\left[ { \lVert R_n - R\rVert }_\mathcal{G} \right]\) introduced in Proposition 3. They are necessary to derive a first, basic learning bound, presented in the section below.

2.3 - Uniform generalization bounds

By joining the results of Section 2.2 to control \(\mathbb{E}\left[ { \lVert R_n - R\rVert }_\mathcal{G} \right]\) in Proposition 3, with Theorem 2 for the deviation of \({ \lVert R_n - R\rVert }_\mathcal{G}\) to its mean, one can derive a simple uniform learning bound.

By combining Proposition 2, Corollary 2 and Lemma 4, we obtain the following result:

Proposition 7 gives a bound on \(\mathbb{E}\left[ { \lVert R_n - R\rVert }_\mathcal{G} \right]\), and we now deal with the other term in Proposition 3. The following corollary is a simple application of Theorem 2 to the random variable \({ \lVert R_n - R\rVert }_{\mathcal{G}}\).

Proof

Joining the results of Proposition 3, with those of Proposition 7 and Corollary 4 gives the following learning bound, with an usual order in \(O(n^{-\frac{1}{2}})\) in statistical learning theory, as the term in \(\log(n)\) is negligible in front of the other terms. A more advanced technique for controlling the complexity of \(\mathcal{G}\), called chaining, allows to derive sharper bounds in \(O(n^{-\frac{1}{2}})\) without the logarithmic term \(\log(n)\). Chaining is mentioned in (Boucheron, Bousquet, and Lugosi 2005 Theorem 3.4), while its proof is featured in (Györfi 2002 Theorem 1.16 and 1.17).

Proof

While the bounds hold for any possible distribution \(P\), they are loose for most sensible distributions. Indeed, in many cases, the uniform deviation of the empirical risk \(\sup_{g\in\mathcal{G}} { \lvert R_n(g) - R(g)\rvert }\) over \(\mathcal{G}\) is a very poor bound for \(R(g_n) - R(g^\dagger)\), as mentioned in (Boucheron, Bousquet, and Lugosi 2005 Section 5.2). The looseness of the bound of this section is illustrated in Remark 3..

3 - Faster learning bounds

This section introduces the derivations of learning rates faster than \(O(n^{-1/2})\) under a noise assumption on the distribution of the data. Firstly, we introduce concentration inequalities that involve the variance of random variables. Secondly, we introduce noise conditions and explain how they induce an upper-bound on the variance of the excess loss. Finally, we show that combining these two first results gives a fixed-point inequality, which implies fast learning rates.

The methodology presented here is limited to finite classes of functions \(\mathcal{G}\) and to problems for which the Bayes classifier \(g^*\) belongs to \(\mathcal{G}\). In this section, we also discuss the generalization of those results to general classes of functions of controlled complexity that do not contain the Bayes classifier.

We introduce a family of functions \(\mathcal{F}\) such that any \(f\in\mathcal{F}\) corresponds to a \(g \in \mathcal{G}\) with: \[\begin{align} f(X, Y) := \mathbb{I}\{ g(X) \ne Y \} - \mathbb{I}\{ g^*(X) \ne Y \},\end{align}\] i.e. the family \(\mathcal{F}\) is the family of the excess losses of all elements in \(\mathcal{G}\).

The bound of Proposition 1 used the fact that the random variable \(f(X, Y)\) is bounded for any \(g \in \mathcal{G}\). However, in many situations, as we choose a candidate \(g\) that approaches \(g^*\), the variance of \(f(X,Y)\) may be very small in front of the range of \(f(X,Y)\). Since advanced concentrations inequalities exploit the variance of random variables to derive tighter bounds, the next section present concentrations inequalities that use the variance of random variables, which will server to derive tighter bounds than based on hypotheses on the distribution of the data.

3.1 - Advanced concentration inequalities

The derivation of fast learning bounds relies on concentration inequalities that involve the variance of the random variables involved. The simplest one is Bernstein’s inequality, seen in (Boucheron, Lugosi, and Massart 2013 Corollary 2.11). Its proof is featured in (Boucheron, Lugosi, and Massart 2013 Theorem 2.10), and we recall the simplest formulation of the inequality here.

Popoviciu’s inequality on variances, see (Egozcue and García 2018), gives an upper bound on the variance of a bounded random variable. Precisely, it states that the variance \(\sigma^2\) of a r.v. \(Z\) such that \(m \le Z \le M\) is smaller than \((M-m)^2/4\). Plugging this result into Theorem 1 gives a similar result as Corollary 3.

Bernstein’s inequality does not give a guarantee on the supremum of a family of functions, but on an empirical mean, as does Hoeffding’s inequality. A direct consequence of Hoeffding’s inequality were guarantees on a finite family of functions, as shown in Corollary 1. As such, only the derivation of guarantees on a finite family of functions are a direct application of the combination of Bernstein’s inequality and noise conditions on \(P\).

To extend those results to more general classes of functions, one requires Talagrand’s inequality below, see (Boucheron, Bousquet, and Lugosi 2005 Section 5.3, Theorem 5.4) for a simple version, and (Boucheron, Lugosi, and Massart 2013 Theorem 7.9, page 225) for the proof. For any \(f \in \mathcal{F}\), we denote by \(Pf := \mathbb{E}[f(X, Y)]\) the distribution of \((X, Y)\) and by \(P_nf := (1/n) \sum_{i=1}^n f(X_i, Y_i)\) the empirical distribution associated to \(\mathcal{D}_n\).

The formulations of Bernstein’s inequality and Talagrand’s inequality are very similar, and their main difference lies in the fact that, while the first deals with simple means, the second handles the supremum of empirical processes. Note that the first term in the bound of Talagrand’s inequality is controlled in Section 2.2.

These inequalities will prove useful when combined with a clever upper bound of the variance of the excess loss, i.e. the variance of \(f(X,Y)\). Conveniently, that quantity is upper-bounded by a function of the excess risk \(R(g) -R(g^*)\), using the noise conditions introduced in the following section.

3.2 - Noise conditions

The simplest noise assumption to derive faster bounds is called Massart’s noise condition, see (Boucheron, Bousquet, and Lugosi 2005, page 340). It is a local condition on the value of \(\eta\), that assumes that \(\eta(X)\) is always far from \(1/2\), i.e. that there is a clear separation between the two classes for the classification decision.

A less restrictive assumption is called the Mammen-Tsybakov noise condition, see (Boucheron, Bousquet, and Lugosi 2005, page 340), and gives a bound on the proportion of \(\mathcal{X}\) for which the classification decision is hard to take. This bound is parameterized by \(a\in[0,1]\). When \(a\) is close to \(1\), it is very easy to separate the two classes, while it is harder when \(a\) is close to \(0\).

Observe that Mammen’s noise condition is void when \(a = 0\), and that it is implied with \(a=1\) by Massart’s noise condition. Both noise assumptions can be used to derive a convenient bound on the variance of a function \(f \in \mathcal{F}\), as a consequence of both a second moment bound, i.e. a bound of the form \(\text{Var}(Z) \le \mathbb{E}[Z^2]\), namely: \[\begin{align} \label{eq-var-upper-bound}\tag{12} \text{Var}(f(X,Y)) \le \mathbb{E}[\mathbb{I}\{ g(X) \ne g^*(X) \} ],\end{align}\] and the decomposition of the excess risk presented in Eq. (1): \[\begin{align} R(g) - R(g^*) = \mathbb{E}\left[ { \lvert 2\eta(X)-1\rvert }\mathbb{I}\{g(X) \ne g^*(X) \right].\end{align}\] Combined with Eq. (12) and Eq. (1), Massart’s inequality implies: \[\begin{align} \text{Var}(f(X,Y)) \le \mathbb{E}[\mathbb{I}\{ g(X) \ne g^*(X) \} ] \le \frac{1}{h} \mathbb{E}[ { \lvert 2 \eta(X) - 1\rvert } \mathbb{I}\{ g(X) \ne g^*(X) \} ] = \frac{1}{h}\left( R(g) - R(g^*) \right).\end{align}\] Similarly, the Mammen-Tsybakov noise assumption implies the following proposition.

Proof

Both of the preceding results are contained, or consequences of (Bousquet, Boucheron, and Lugosi 2004 Section 5.2). The proof of Proposition 5 uses an equivalent formulation of Proposition 5, which are proven in (Bousquet, Boucheron, and Lugosi 2004 Definition 7). Those results enable us to derive fast, distribution-dependent generalization bounds, by using those results in conjonction with the concentration inequalities of Section 3.1, and solving a fixed-point equation.

3.3 - Distribution-dependent generalization bounds

The reasoning presented here can be found in (Bousquet, Boucheron, and Lugosi 2004 Section 5.2), but is more detailed here. A union bound of Bernstein’s inequality applied on each element of finite family of \(N\) elements gives that, for any \(\delta > 0\), w.p \(\ge 1-\delta\), we have simultaneously for any \(g \in \mathcal{G}\), with \(f\) the corresponding element in \(\mathcal{F}\): \[\begin{align} \label{eq-bernstein-4-bound}\tag{13} R(g) - R(g^*) \le R_n(g) - R_n(g^*) + \frac{2c \log(N/\delta)}{3n} + \sqrt{\frac{2\text{Var}(f(X,Y)) \log(N/\delta)}{n}}.\end{align}\] Combining Eq. (13) with the implications of the Mammen-Tsybakov noise assumption, i.e. with Proposition 5, for the empirical risk minimizer and under the assumption that \(g^*\) belongs to the proposal class, i.e. for \(g = g_n\) and that \(g^* \in \mathcal{G}\), we have: for any \(\delta > 0\), w.p \(\ge 1-\delta\), \[\begin{align} \label{eq-fixed-point-4-bound}\tag{14} R(g_n) - R(g^*) \le \frac{2c \log(N/\delta)}{3n} + (R(g_n) - R(g^*))^{a/2} \sqrt{\frac{2c \log(N/\delta)}{n}},\end{align}\] which is a fixed point inequality in \(R(g_n) - R(g^*)\). To derive an upper-bound on \(R(g_n) - R(g^*)\) from Eq. (14), we use the following Lemma, which is found in (Cucker and Smale 2002 Lemma 7).

Proof

Using Lemma 2, we can prove a fast learning bound for finite families of functions.

Proof

Proposition 4 gives a learning bound of the order \(O(n^{-\frac{1}{2-a}})\), under a noise condition parameterized by \(a \in [0,1]\). When \(a\) is close to \(0\), one recovers the order \(O(n^{-\frac{1}{2}})\) derived in Section 2.3. On the other hand, when \(a\) is close to zero, one approaches the fast rate \(O(n^{-1})\). The fast bounds are illustrated in Remark 3. The generalization of Proposition 4 to non-finite families of functions is more involved and is a consequence of Talagrand’s inequality (Theorem 3), and we refer to (Boucheron, Bousquet, and Lugosi 2005 Section 5.3) for that extension. The analysis presented there extends to the case where \(g^*\) does not belongs to \(\mathcal{G}\), which is detailed in (Boucheron, Bousquet, and Lugosi 2005 Section 5.3.5).

In real problems, as the distribution of the data is unknown, one can not verify whether a noise assumption is satisfied by the distribution of the data. Still, fast learning speeds partially justify the looseness of the bounds derived in Section 2 and constitute strong evidence of the soundness of learning from empirical data.

---

Bibliography

---