# Distribution-free Deviation Bounds of Learning via Model Selection with
Cross-validation Risk Estimation

Diego Marcondes  Department of Computer Science, Institute of Mathematics and
Statistics, Universidade de São Paulo, R. do Matão, 1010 - Butantã, São Paulo
- SP, 05508-090, Brazil.
e-mail<EMAIL_ADDRESS>and  Cláudia Peixoto  Department of Applied
Mathematics, Institute of Mathematics and Statistics, Universidade de São
Paulo, R. do Matão, 1010 - Butantã, São Paulo - SP, 05508-090, Brazil.

###### Abstract.

Cross-validation techniques for risk estimation and model selection are widely
used in statistics and machine learning. However, the understanding of the
theoretical properties of learning via model selection with cross-validation
risk estimation is quite low in face of its widespread use. In this context,
this paper presents learning via model selection with cross-validation risk
estimation as a general systematic learning framework within classical
statistical learning theory and establishes distribution-free deviation bounds
in terms of VC dimension, giving detailed proofs of the results and
considering both bounded and unbounded loss functions. We also deduce
conditions under which the deviation bounds of learning via model selection
are tighter than that of learning via empirical risk minimization in the whole
hypotheses space, supporting the better performance of model selection
frameworks observed empirically in some instances.

Keywords: deviation bounds, cross-validation, model selection, statistical
learning theory, unbounded loss function

##  1\. Introduction

The classical framework of Statistical Learning Theory is a triple
$(\mathcal{H},\mathbb{A},\mathcal{D}_{N})$, composed by a set $\mathcal{H}$ of
hypotheses $h$, called hypotheses space, and a learning algorithm
$\mathbb{A}(\mathcal{H},\mathcal{D}_{N})$, which searches $\mathcal{H}$
seeking to minimize a risk measure based on a training sample
$\mathcal{D}_{N}=\\{Z_{1},\dots,Z_{N}\\}$ of a random vector $Z$, with range
$\mathcal{Z}\subset\mathbb{R}^{d},d\geq 1,$ and unknown probability
distribution $P$.

Let $\ell:\mathcal{Z}\times\mathcal{H}\mapsto\mathbb{R}_{+}$ be a loss
function. The risk of a hypothesis $h\in\mathcal{H}$ is an expected value of
the local loss $\ell(z,h),z\in\mathcal{Z}$. If the expectation is the sample
mean of $\ell(z,h)$ under $\mathcal{D}_{N}$, we have the empirical risk
$L_{\mathcal{D}_{N}}(h)$, while if the expectation of $\ell(Z,h)$ is under the
distribution $P$, we then have the out-of-sample risk $L(h)$.

In this context, a target hypothesis $h^{\star}\in\mathcal{H}$ is such that
its out-of-sample risk is minimum in $\mathcal{H}$, i.e., $L(h^{\star})\leq
L(h),\forall h\in\mathcal{H}$, while an empirical risk minimization (ERM)
hypothesis $\hat{h}$ is such that its empirical risk is minimum, i.e.,
$L_{\mathcal{D}_{N}}(\hat{h})\leq L_{\mathcal{D}_{N}}(h),\forall
h\in\mathcal{H}$.

The algorithm $\mathbb{A}$ returns a $\hat{h}^{\mathbb{A}}\in\mathcal{H}$
seeking to approximate a target hypothesis $h^{\star}\in\mathcal{H}$. The
returned hypothesis can be an ERM hypothesis, but this is not necessary. In
any case, such learning framework has an important parameter that is problem-
specific: the hypotheses space $\mathcal{H}$, which has a strong impact on the
generalization quality of the estimated hypothesis $\hat{h}^{\mathbb{A}}$,
that is characterized by a small out-of-sample risk.

The fundamental result in Statistical Learning Theory is the Vapnik-
Chervonenkis (VC) theory [34, 35, 36, 37, 38, 39], which implies that a
hypotheses space $\mathcal{H}$ is PAC-learnable [32] if, and only if, it has
finite VC dimension ($d_{VC}(\mathcal{H})<\infty$) [31, Theorem 6.7]. This
means that, for any data generating distribution $P$, $L(\hat{h})$ is close to
$L(h^{\star})$ with great confidence, if $N$ is sufficiently large. Therefore,
it is possible to learn hypotheses with a finite sample, with precision and
confidence dependent on the training sample size $N$ and the VC dimension
(complexity) of $\mathcal{H}$.

The VC theory is general, has a structural importance to the field, and is a
useful guide for modeling practical problems. From its main results follow a
quantity $N(d_{VC}(\mathcal{H}),\epsilon,\delta)$, that is the least $N$,
given a hypotheses space $\mathcal{H}$, a margin of error $\epsilon$ and a
confidence $\delta$, such that

$\mathbb{P}\left(L(\hat{h})-L(h^{\star})>\epsilon\right)\leq 1-\delta.$ (1.1)

The bounds of VC theory are distribution-free, in the sense that inequality
(1.1) holds with $N$ greater than $N(d_{VC}(\mathcal{H}),\epsilon,\delta)$ for
all possible data generating distributions $P$. However, since the sample size
$N$ depends on data availability, which may be conditioned upon several
factors, such as technical difficulties and costs, the size
$N(d_{VC}(\mathcal{H}),\epsilon,\delta)$ may not be attainable, and hence it
may not be feasible to learn on $\mathcal{H}$ with low error and great
confidence.

In this context, the parameters $(N,\epsilon,\delta)$ are usually
predetermined, and the only free component to be adjusted on VC theory’s
bounds is the hypotheses space or, more precisely, its VC dimension. This
adjustment is usually performed via a data-driven selection of the hypotheses
space, known as model selection (see [12, 17, 26, 27] for a review of model
selection techniques). From now on, we use the words model, hypotheses space
and hypotheses subspace (of a hypotheses space) as synonyms. Once a model is
selected, a hypothesis is then learned on it, so a hypothesis is learned via
model selection.

Learning via model selection is a two-step framework in which first a model is
selected from a collection of candidates, and then a hypothesis is learned on
it. Fix a hypotheses space $\mathcal{H}$, a collection of candidate subsets,
or models,

$\displaystyle\mathbb{C}(\mathcal{H})=\\{\mathcal{M}_{1},\dots,\mathcal{M}_{n}\\}$
such that $\displaystyle\mathcal{H}=\bigcup_{i=1}^{n}\mathcal{M}_{i},$

and an empirical risk estimator
$\hat{L}:\mathbb{C}(\mathcal{H})\mapsto\mathbb{R}_{+}$, which for each
candidate model attributes a risk estimated from data. The first step of
learning via model selection is to select a minimizer of $\hat{L}$ in
$\mathbb{C}(\mathcal{H})$:

$\hat{\mathcal{M}}\coloneqq\operatorname*{arg\,min}_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}\hat{L}(\mathcal{M}).$

Once a model is selected, one employs a data-driven algorithm $\mathbb{A}$ to
learn a hypothesis $\hat{h}^{\mathbb{A}}_{\hat{\mathcal{M}}}$ in
$\hat{\mathcal{M}}$.

A classical instance of model selection is that of variable selection, in
which each candidate model contains the hypotheses which depend on a subset of
variables [16, 19]. A more general approach to model selection is Structural
Risk Minimization in which the candidate models form a chain
$\mathcal{M}_{1}\subseteq\cdots\subseteq\mathcal{M}_{n}$ of subsets with
increasing VC dimension and the risk $\hat{L}$ is a penalization of the
resubstitution risk of each model by its complexity (see [34, Chapter 6] for
more details, and [2] for an example).

Actually, there is a whole area of research that focuses on model selection by
penalization, in which $\hat{L}$ is a penalized empirical risk. See [26] for
an in-depth presentation of model selection by penalization, [3, 8, 22, 21]
for results in more specific learning frameworks and [7] for risk bounds in
this instance. Another class of model selection frameworks is formed by those
based on cross-validation techniques [4, 41, 40, 20].

An intrinsic characteristic of model selection frameworks is a bias-variance
trade off, which is depicted in Figure 1. On the one hand, when one selects
from data a model $\hat{\mathcal{M}}$ among the candidates to learn on, he
adds a bias to the learning process if $h^{\star}$ is not in
$\hat{\mathcal{M}}$, since the best hypotheses $h^{\star}_{\hat{\mathcal{M}}}$
one can learn on $\hat{\mathcal{M}}$ may have a greater risk than $h^{\star}$,
i.e., $L(h^{\star}_{\hat{\mathcal{M}}})>L(h^{\star})$. Hence, even when the
sample size is great, the learned hypothesis may not well generalize relative
to $h^{\star}$. We call this bias type III estimation error, as depicted in
Figure 1.

On the other hand, learning within $\hat{\mathcal{M}}$ may have a lesser error
than on the whole $\mathcal{H}$, in the sense of
$L(\hat{h}^{\mathbb{A}}_{\hat{\mathcal{M}}})$ being close to
$L(h^{\star}_{\hat{\mathcal{M}}})$. We call their difference type II
estimation error, as depicted in Figure 1. The actual error of learning in
this instance is the difference between
$L(\hat{h}^{\mathbb{A}}_{\hat{\mathcal{M}}})$ and $L(h^{\star})$, also
depicted in Figure 1 as type IV estimation error.

A successful framework for model selection should be such that
$L(\hat{h}^{\mathbb{A}}_{\hat{\mathcal{M}}})<L(\hat{h}^{\mathbb{A}})$. In
other words, by adding a bias (III), the learning variance (II) within
$\hat{\mathcal{M}}$ should be low enough, so the actual error (IV) committed
when learning is lesser than the one committed by learning on the whole space
$\mathcal{H}$, that is $L(\hat{h}^{\mathbb{A}})-L(h^{\star})$.

Figure 1. Types II, III, and IV estimation errors when learning on
$\hat{\mathcal{M}}$, in which
$\hat{h}_{\hat{\mathcal{M}}}\equiv\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}}$.
These errors are formally defined in Section 2.2.

In this context, this paper aims to study the distribution-free asymptotics of
learning via model selection, that means bounding the estimation errors in
Figure 1. In special, we seek to obtain bounds that imply sample sizes
$N_{MS}(\mathbb{C}(\mathcal{H}),\epsilon,\delta)<N(d_{VC}(\mathcal{H}),\epsilon,\delta)$,
depending on the family $\mathbb{C}(\mathcal{H})$ of candidate models, such
that

$\mathbb{P}\left(L(\hat{h}^{\mathbb{A}}_{\hat{\mathcal{M}}})-L(h^{\star})>\epsilon\right)\leq
1-\delta$

whenever the sample size is greater than
$N_{MS}(\mathbb{C}(\mathcal{H}),\epsilon,\delta)$, so that generalization may
be improved by learning via model selection. Furthermore, we define the target
model $\mathcal{M}^{\star}$ among the candidates and establish convergence
rates of $\hat{\mathcal{M}}$ to $\mathcal{M}^{\star}$. We focus on frameworks
where the risk of each candidate model is estimated via a cross-validation
procedure.

We present learning via model selection with cross-validation risk estimation
as a general systematic learning framework within classical Statistical
Learning Theory, and establish distribution-free deviation bounds in terms of
VC dimension, giving detailed proofs of the results and considering both
bounded and unbounded loss functions. In order to treat the case of bounded
loss functions we extend the classical Statistical Learning Theory [34, 11] to
learning via model selection, while to treat the case of unbounded loss
functions we apply and extend the recent results of [10].

Cross-validation techniques for risk estimation and model selection are widely
spread in statistics and machine learning, and their asymptotic behavior have
been fairly studied. The asymptotic optimality of specific cross-validation
methods has been studied in [1, 24, 13] and so-called oracle inequalities have
been established for cross-validation methods in [33, 23]. However, the
understanding of the theoretical properties of cross-validation is quite low
in face of its widespread use. This fact has been noted by the recent works
[6, 25] which study the asymptotics of cross-validation for specific classes
of models. To the best of our knowledge, a study of model selection with
cross-validation risk estimation within this distribution-free combinatorial
scope has not been done before, and may bring some insights into the benefits
of model selection, even if the pessimistic bounds of distribution-free
frameworks may not be of practical use.

We expect with the results of this paper to introduce the tools of classical
VC theory to the study of model selection with cross-validation risk
estimation, which is a simple method that works very well in practice, but
lacks a strong theoretical basis in many instances. In [26, p. 314], when
model selection with cross-validation error estimation is discussed in
opposition to model selection with penalization, that is the main object of
[26], it is said that “It could seem a bit disappointing to discover that a
very crude method like hold-out111The hold-out method that [26] refers to is
equivalent to learning via model selection with risk estimated with a
validation sample. is working so well. This is especially true in the
classification framework”. We firmly believe that such a good performance
should be explained by some theory that passes through studying it in a
distribution-free framework.

In Section 2, we present the main concepts of Statistical Learning Theory, and
define the framework of learning via model selection with cross-validation
risk estimation as a systematic general learning framework. In Sections 3 and
4, we establish deviation bounds for learning via model selection for bounded
and unbounded loss functions, respectively. In Section 5, we present an
illustrative example where the deviation bounds of learning via model
selection are tighter than that of learning directly on $\mathcal{H}$ via
empirical risk minimization. We discuss the main results and perspectives of
this paper in Section 6. In Section 7, we present the proof of the results. In
order to increase the self-containment of this paper, enhancing its access to
readers not expert in VC theory, we present in Appendix A an overview of its
main results necessary to this paper.

##  2\. Model selection in Statistical Learning

Let $Z$ be a random vector defined on a probability space
$(\Omega,\mathcal{S},\mathbb{P})$, with range
$\mathcal{Z}\subset\mathbb{R}^{d},d\geq 1$. Denote
$P(z)\coloneqq\mathbb{P}(Z\leq z)$ as the probability distribution of $Z$ at
point $z\in\mathcal{Z}$, which we assume unknown, but fixed. Define a sample
$\mathcal{D}_{N}=\\{Z_{1},\dots,Z_{N}\\}$ as a sequence of independent and
identically distributed random vectors, defined on
$(\Omega,\mathcal{S},\mathbb{P})$, with distribution $P$.

Let $\mathcal{H}$ be a general set, whose typical element we denote by $h$,
which we call hypotheses space. We denote subsets of $\mathcal{H}$ by
$\mathcal{M}_{i}$, indexed by the positive integers, i.e.,
$i\in\mathbb{Z}_{+}$. We may also denote a subset of $\mathcal{H}$ by
$\mathcal{M}$ to ease notation. We consider model and subset of $\mathcal{H}$
as synonyms.

Let $\ell:\mathcal{Z}\times\mathcal{H}\mapsto\mathbb{R}_{+}$ be a, possibly
unbounded, loss function, which represents the loss $\ell(z,h)$ that incurs
when one applies a hypothesis $h\in\mathcal{H}$ to explain a feature of point
$z\in\mathcal{Z}$. Denoting $\ell_{h}(z)\coloneqq\ell(z,h)$ for
$z\in\mathcal{Z}$, we assume that, for each $h\in\mathcal{H}$, the composite
function $\ell_{h}\circ Z$ is $(\Omega,\mathcal{S})$-measurable.

The risk of a hypothesis $h\in\mathcal{H}$ is defined as

$L(h)\coloneqq\mathbb{E}[\ell_{h}(Z)]=\int_{\mathcal{Z}}\ell_{h}(z)\ dP(z),$

in which $\mathbb{E}$ means expectation under $\mathbb{P}$. We define the
empirical risk on sample $\mathcal{D}_{N}$ as

$L_{\mathcal{D}_{N}}(h)\coloneqq\frac{1}{N}\sum_{i=1}^{N}\ell_{h}(Z_{i}),$

that is the empirical mean of $\ell_{h}(Z)$.

We denote the set of target hypotheses of $\mathcal{H}$ as

$h^{\star}\coloneqq\operatorname*{arg\,min}\limits_{h\in\mathcal{H}}L(h),$

that are the hypotheses that minimize $L$ in $\mathcal{H}$, and the set of the
target hypotheses of subsets of $\mathcal{H}$ by

$\displaystyle
h^{\star}_{i}\coloneqq\operatorname*{arg\,min}\limits_{h\in\mathcal{M}_{i}}L(h)$
$\displaystyle
h^{\star}_{\mathcal{M}}\coloneqq\operatorname*{arg\,min}\limits_{h\in\mathcal{M}}L(h),$

depending on the subset.

The set of hypotheses which minimize the empirical risk in $\mathcal{H}$ is
defined as

$\displaystyle\hat{h}^{\mathcal{D}_{N}}\coloneqq\operatorname*{arg\,min}\limits_{h\in\mathcal{H}}L_{\mathcal{D}_{N}}(h),$
(2.1)

while the ones that minimize it in models are denoted by

$\displaystyle\hat{h}_{i}^{\mathcal{D}_{N}}\coloneqq\operatorname*{arg\,min}\limits_{h\in\mathcal{M}_{i}}L_{\mathcal{D}_{N}}(h)$
$\displaystyle\hat{h}_{\mathcal{M}}^{\mathcal{D}_{N}}\coloneqq\operatorname*{arg\,min}\limits_{h\in\mathcal{M}}L_{\mathcal{D}_{N}}(h).$
(2.2)

We assume the minimum of $L$ and $L_{\mathcal{D}_{N}}$ is achieved in
$\mathcal{H}$, and in all subsets of it that we consider throughout this
paper, so the sets above are not empty. To ease notation, we may simply denote
$\hat{h}$ as a hypothesis that minimizes the empirical risk in $\mathcal{H}$.
In general, we denote hypotheses estimated via an algorithm $\mathbb{A}$ in
$\mathcal{H}$ and its subsets by
$\hat{h}^{\mathbb{A}},\hat{h}_{i}^{\mathbb{A}}$ and
$\hat{h}_{\mathcal{M}}^{\mathbb{A}}$. In the special case when $\mathbb{A}$ is
given by empirical risk minimization in sample $\mathcal{D}_{N}$ we have the
hypotheses defined in (2.1) and (2.2)

We denote a collection of candidate models by
$\mathbb{C}(\mathcal{H})=\\{\mathcal{M}_{i}:i\in\mathcal{J}\\}$, for
$\mathcal{J}\subset\mathbb{Z}_{+},\text{\textbar}\mathcal{J}\text{\textbar}<\infty$,
and assume that it covers $\mathcal{H}$:

$\mathcal{H}=\bigcup_{i\in\mathcal{J}}\mathcal{M}_{i}.$

We define the VC dimension under loss function $\ell$ of such a collection as

$d_{VC}(\mathbb{C}(\mathcal{H}),\ell)\coloneqq\max\limits_{i\in\mathcal{J}}d_{VC}(\mathcal{M}_{i},\ell)$

and assume that $d_{VC}(\mathbb{C}(\mathcal{H}),\ell)<\infty$. Since every
model in $\mathbb{C}(\mathcal{H})$ is a subset of $\mathcal{H}$ it follows
that $d_{VC}(\mathbb{C}(\mathcal{H}),\ell)\leq d_{VC}(\mathcal{H},\ell)$. In
Appendix A we review the main concepts of VC theory [34]. In special, we
define the VC dimension of a hypotheses space under loss function $\ell$ (cf.
Definition A.2). When the loss function is clear from the context, or not of
relevance to our argument, we denote the VC dimension simply by
$d_{VC}(\mathcal{M})$ for $\mathcal{M}\subseteq\mathcal{H}$ and
$d_{VC}(\mathbb{C}(\mathcal{H}))$.

###  2.1. Model risk estimation

The risk of a model in $\mathbb{C}(\mathcal{H})$ is defined as

$L(\mathcal{M})\coloneqq\min\limits_{h\in\mathcal{M}}L(h)=L(h^{\star}_{\mathcal{M}}),$

for $\mathcal{M}\in\mathbb{C}(\mathcal{H})$, and we consider estimators
$\hat{L}(\mathcal{M})$ for $L(\mathcal{M})$ based on cross-validation. We
assume that $\hat{L}$ is of the form

$\displaystyle\hat{L}(\mathcal{M})=\frac{1}{m}\ \sum_{j=1}^{m}\
\hat{L}^{(j)}(\hat{h}^{(j)}_{\mathcal{M}}),$
$\displaystyle\mathcal{M}\in\mathbb{C}(\mathcal{H}),$ (2.3)

in which there are $m$ pairs of independent training and validation samples,
$\hat{L}^{(j)}$ is the empirical risk under the $j$-th validation sample, and
$\hat{h}^{(j)}_{\mathcal{M}}$ is a hypothesis that minimizes the empirical
risk in $\mathcal{M}$ under the $j$-th training sample, denoted by
$\mathcal{D}_{N}^{(j)}$. We assume independence between samples within a pair
$j$, but there may exist dependence between samples of distinct pairs
$j,j^{\prime}$. All training and validation samples are subsets of
$\mathcal{D}_{N}$.

In order to exemplify the results obtained in this paper, we will apply them
for two estimators of the form (2.3), obtained with a validation sample and
k-fold cross validation, which we formally define below. When there is no need
to specify which estimator of $L(\mathcal{M})$ we are referring, we denote
simply $\hat{L}(\mathcal{M})$ to mean an arbitrary estimator with form (2.3).

####  2.1.1. Validation sample

Fix a sequence $\\{V_{N}:N\geq 1\\}$ such that
$\lim\limits_{N\rightarrow\infty}V_{N}=\lim\limits_{N\to\infty}N-V_{N}=\infty$,
and let

$\displaystyle\mathcal{D}_{N}^{(\text{train})}=\\{Z_{l}:1\leq l\leq
N-V_{N}\\}$
$\displaystyle\mathcal{D}_{N}^{(\text{val})}=\\{Z_{l}:N-V_{N}<l\leq N\\}$

be a split of $\mathcal{D}_{N}$ into a training and validation sample.
Proceeding in this manner, we have two samples
$\mathcal{D}_{N}^{(\text{train})}$ and $\mathcal{D}_{N}^{(\text{val})}$, which
are independent. The estimator under the validation sample is given by

$\hat{L}_{\text{val}}(\mathcal{M})\coloneqq
L_{\mathcal{D}_{N}^{(\text{val})}}(\hat{h}_{\mathcal{M}}^{(\text{train})})=\frac{1}{V_{N}}\sum_{N-V_{N}<l\leq
N}\ell\big{(}Z_{l},\hat{h}_{\mathcal{M}}^{(\text{train})}\big{)},$

in which

$\hat{h}_{\mathcal{M}}^{(\text{train})}=\operatorname*{arg\,min}_{h\in\mathcal{M}}L_{\mathcal{D}_{N}^{(\text{train})}}(h)$

minimizes the empirical risk in $\mathcal{M}$ under
$\mathcal{D}_{N}^{(\text{train})}$.

####  2.1.2. K-fold cross-validation

Fix $k\in\mathbb{Z}_{+}$ and assume $N\coloneqq kn$, for a
$n\in\mathbb{Z}_{+}$. Then, let

$\displaystyle\mathcal{D}_{N}^{(j)}\coloneqq\\{Z_{l}:(j-1)n<l\leq jn\\},$
$\displaystyle j=1,\dots,k,$

be a partition of $\mathcal{D}_{N}$:

$\displaystyle\mathcal{D}_{N}=\bigcup_{j=1}^{k}\mathcal{D}_{N}^{(j)}$ and
$\displaystyle\mathcal{D}_{N}^{(j)}\cap\mathcal{D}_{N}^{(j^{\prime})}=\emptyset\text{
if }j\neq j^{\prime}.$

We define

$\hat{h}^{(j)}_{\mathcal{M}}\coloneqq\operatorname*{arg\,min}_{h\in\mathcal{M}}\
L_{\mathcal{D}_{N}\setminus\mathcal{D}_{N}^{(j)}}(h)=\operatorname*{arg\,min}_{h\in\mathcal{M}}\
\frac{1}{(k-1)n}\sum_{\begin{subarray}{c}l\leq(j-1)n\\\ \cup\
l>jn\end{subarray}}\ell(Z_{l},h)$

as the hypothesis which minimizes the empirical risk in $\mathcal{M}$ under
the sample $\mathcal{D}_{N}\setminus\mathcal{D}_{N}^{(j)}$, that is the sample
composed by all folds, but the $j$-th, and

$\hat{L}_{\text{cv(k)}}^{(j)}(\mathcal{M})\coloneqq
L_{\mathcal{D}_{N}^{(j)}}(\hat{h}^{(j)}_{\mathcal{M}})=\frac{1}{n}\sum_{(j-1)n<l\leq
jn}\ell(Z_{l},\hat{h}^{(j)}_{\mathcal{M}}),$

as the validation risk of the $j$-th fold.

The k-fold cross-validation estimator of $L(\mathcal{M})$ is then given by

$\hat{L}_{\text{cv(k)}}(\mathcal{M})\coloneqq\frac{1}{k}\
\sum_{j=1}^{k}\hat{L}_{\text{cv(k)}}^{(j)}(\mathcal{M}),$

that is the average validation risk over the folds.

###  2.2. Target model and estimation errors

The motivation for learning via model selection is presented in Figure 2, in
which the ellipses represent some models in $\mathbb{C}(\mathcal{H})$, and
their area is proportional to their complexity, given for example by VC
dimension. Assume that $\mathcal{H}$ is all we have to learn on, and we are
not willing to consider any hypothesis outside $\mathcal{H}$. Then, if we
could choose, we would like to learn on $\mathcal{M}^{\star}$: the least
complex model in $\mathbb{C}(\mathcal{H})$ which contains a target hypothesis
$h^{\star}$. We call $\mathcal{M}^{\star}$ the target model.

In order to formally define the target model, we need to consider equivalence
classes of models, as it is not possible to differentiate some models with the
concepts of Statistical Learning Theory. Define in $\mathbb{C}(\mathcal{H})$
the equivalence relation given by

$\displaystyle\mathcal{M}_{i}\sim\mathcal{M}_{j}\text{ if, and only if,
}d_{VC}(\mathcal{M}_{i})=d_{VC}(\mathcal{M}_{j})\text{ and
}L(\mathcal{M}_{i})=L(\mathcal{M}_{j}),$ (2.4)

for $\mathcal{M}_{i},\mathcal{M}_{j}\in\mathbb{C}(\mathcal{H})$: two models in
$\mathbb{C}(\mathcal{H})$ are equivalent if they have the same VC dimension
and risk. Let

$\mathcal{L}^{\star}=\operatorname*{arg\,min}\limits_{\mathcal{M}\in\
\nicefrac{{\mathbb{C}(\mathcal{H})}}{{\sim}}}L(\mathcal{M})$

be the equivalence classes which contain a target hypothesis of $\mathcal{H}$,
so their risk is minimum. We define the target model
$\mathcal{M}^{\star}\in\nicefrac{{\mathbb{C}(\mathcal{H})}}{{\sim}}$ as

$\mathcal{M}^{\star}=\operatorname*{arg\,min}\limits_{\mathcal{M}\in\mathcal{L}^{\star}}d_{VC}(\mathcal{M}),$

which is the class of the smallest models in $\mathbb{C}(\mathcal{H})$, in the
VC dimension sense, that are not disjoint with $h^{\star}$. The target model
has the lowest complexity among the unbiased models in
$\mathbb{C}(\mathcal{H})$.

The target model is dependent on both $\mathbb{C}(\mathcal{H})$ and the data
generating distribution, so we cannot establish beforehand, without looking at
data, on which model of $\mathbb{C}(\mathcal{H})$ to learn. Hence, in this
context, a model selection procedure should, based on data, learn a model
$\hat{\mathcal{M}}$ among the candidates $\mathbb{C}(\mathcal{H})$ as an
estimator of $\mathcal{M}^{\star}$.

Figure 2. Decomposition of $\mathcal{H}$ by a $\mathbb{C}(\mathcal{H})$. We
omitted some models for a better visualization, since
$\mathbb{C}(\mathcal{H})$ should cover $\mathcal{H}$.

However, when learning on a model
$\hat{\mathcal{M}}\in\mathbb{C}(\mathcal{H})$ selected based on data, one
commits three types of errors:

$\displaystyle\textbf{(II)}\ \
L(\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}})-L(h^{\star}_{\hat{\mathcal{M}}})$
$\displaystyle\textbf{(III)}\ \ L(h^{\star}_{\hat{\mathcal{M}}})-L(h^{\star})$
$\displaystyle\textbf{(IV)}\ \
L(\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}})-L(h^{\star}),$

that we call types II, III, and IV estimation errors222We define type I
estimation error in Section 2.3.2 (cf. (2.8))., which are illustrated in
Figure 1. In a broad sense, type III estimation error would represent the bias
of learning on $\hat{\mathcal{M}}$, while type II would represent the variance
within $\hat{\mathcal{M}}$, and type IV would be the error, with respect to
$\mathcal{H}$, committed when learning on $\hat{\mathcal{M}}$ with algorithm
$\mathbb{A}$.

Indeed, type III estimation error compares a target hypothesis
$h_{\hat{\mathcal{M}}}^{\star}$ of $\hat{\mathcal{M}}$ with a target
hypothesis $h^{\star}$ of $\mathcal{H}$, hence any difference between them
would be a systematic bias of learning on $\hat{\mathcal{M}}$ when compared to
learning on $\mathcal{H}$. Type II estimation error compares the loss of the
estimated hypothesis $\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}}$ of
$\hat{\mathcal{M}}$ and the loss of its target, assessing how much the
estimated hypothesis varies from a target of $\hat{\mathcal{M}}$, while type
IV is the effective error committed, since compares the estimated hypothesis
of $\hat{\mathcal{M}}$ with a target of $\mathcal{H}$.

As is often the case, there will be a bias-variance trade-off that should be
minded when learning on $\hat{\mathcal{M}}$, so it is important to guarantee
that, when the sample size increases, all the estimation errors tend to zero.
Furthermore, it is desired that the learned model $\hat{\mathcal{M}}$
converges to the target model $\mathcal{M}^{\star}$ with probability one, so
learning is asymptotically optimal. The proposed learning framework via model
selection defined in the next section will take these desires into account.

###  2.3. Learning hypotheses via model selection

Learning via model selection is composed of two steps: first learn a model
$\hat{\mathcal{M}}$ from $\mathbb{C}(\mathcal{H})$ and then learn a hypothesis
on $\hat{\mathcal{M}}$. In this section, we define $\hat{\mathcal{M}}$ and an
algorithm $\mathbb{A}$ to learn on it.

####  2.3.1. Learning model $\hat{\mathcal{M}}$

Model selection is performed by applying a $(\Omega,\mathcal{S})$-measurable
function $\mathbb{M}_{\mathbb{C}(\mathcal{H})}$, dependent on
$\mathbb{C}(\mathcal{H})$, satisfying

$\omega\in\Omega\xrightarrow{(\mathcal{D}_{N},\hat{L})}(\mathcal{D}_{N}(\omega),\hat{L}(\omega))\xrightarrow{\
\ \mathbb{M}_{\mathbb{C}(\mathcal{H})}\ \
}\mathcal{\hat{M}}(\omega)\in\mathbb{C}(\mathcal{H}),$ (2.5)

which is such that, given $\mathcal{D}_{N}$ and an estimator $\hat{L}$ of the
risk of each candidate model, learns a
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$. Note from (2.5) that
$\mathcal{\hat{M}}$ is a $(\Omega,\mathcal{S})$-measurable
$\mathbb{C}(\mathcal{H})$-valued function, as it is the composition of
measurable functions, i.e.,
$\mathcal{\hat{M}}\coloneqq\mathcal{\hat{M}}_{\mathcal{D}_{N},\hat{L},\mathbb{C}(\mathcal{H})}=\mathbb{M}_{\mathbb{C}(\mathcal{H})}\big{(}\mathcal{D}_{N},\hat{L}\big{)}$.
Even though $\mathcal{\hat{M}}$ depends on $\mathcal{D}_{N},\hat{L}$ and
$\mathbb{C}(\mathcal{H})$, we drop the subscripts to ease notation.

We are interested in a $\mathbb{M}_{\mathbb{C}(\mathcal{H})}$ such that

$\mathcal{\hat{M}}=\mathbb{M}_{\mathbb{C}(\mathcal{H})}\big{(}\mathcal{D}_{N},\hat{L}\big{)}\xrightarrow{N\rightarrow\infty}\mathcal{M}^{\star}\text{
with probability one}.$ (2.6)

Actually, it is desired the model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$ to be as simple as it can be under the
restriction that it converges to the target model.

A $\mathbb{M}_{\mathbb{C}(\mathcal{H})}$ which satisfies (2.6) may be defined
by mimicking the definition of $\mathcal{M}^{\star}$, but employing the
estimated risk $\hat{L}$ instead of $L$. Define in $\mathbb{C}(\mathcal{H})$
the equivalence relation given by

$\displaystyle\mathcal{M}_{i}\hat{\sim}\mathcal{M}_{j}\text{ if, and only if,
}d_{VC}(\mathcal{M}_{i})=d_{VC}(\mathcal{M}_{j})\text{ and
}\hat{L}(\mathcal{M}_{i})=\hat{L}(\mathcal{M}_{j}),$

for $\mathcal{M}_{i},\mathcal{M}_{j}\in\mathbb{C}(\mathcal{H})$, which is a
random $(\Omega,\mathcal{S})$-measurable equivalence relation. Let

$\hat{\mathcal{L}}=\operatorname*{arg\,min}\limits_{\mathcal{M}\in\
\nicefrac{{\mathbb{C}(\mathcal{H})}}{{\hat{\sim}}}}\hat{L}(\mathcal{M})$

be the classes in $\nicefrac{{\mathbb{C}(\mathcal{H})}}{{\hat{\sim}}}$ with
the least estimated risk. We call the classes in $\hat{\mathcal{L}}$ the
global minimums of $\mathbb{C}(\mathcal{H})$. Then,
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$ selects

$\hat{\mathcal{M}}=\operatorname*{arg\,min}\limits_{\mathcal{M}\in\mathcal{\hat{L}}}d_{VC}(\mathcal{M}),$
(2.7)

the simplest class among the global minimums.

####  2.3.2. Learning hypotheses on $\hat{\mathcal{M}}$

Once $\hat{\mathcal{M}}$ is selected, we need to learn hypotheses on it and,
to this end, we assume there is a sample
$\tilde{\mathcal{D}}_{M}=\\{\tilde{Z}_{l}:1\leq l\leq M\\}$ of $M$ independent
and identically distributed random vectors with distribution $P$, independent
of $\mathcal{D}_{N}$, so we can learn

$\displaystyle\hat{h}_{\hat{\mathcal{M}}}^{\tilde{\mathcal{D}}_{M}}\coloneqq\operatorname*{arg\,min}\limits_{h\in\hat{\mathcal{M}}}L_{\tilde{\mathcal{D}}_{M}}(h),$

that are the hypotheses which minimize the empirical risk under
$\tilde{\mathcal{D}}_{M}$ on $\hat{\mathcal{M}}$. Figure 3 summarizes the
systematic framework of learning via model selection.

Figure 3. The systematic framework for learning hypotheses via model
selection. A sample of size $N+M$ is split into two, one of size $N$ that is
used to estimate $\hat{\mathcal{M}}$ by the minimization of $\hat{L}$ on
$\mathbb{C}(\mathcal{H})$, and another of size $M$ is used to learn a
hypothesis on $\hat{\mathcal{M}}$ by the minimization of the empirical risk.

We define the type I estimation error as

$\displaystyle\textbf{(I)}\sup\limits_{h\in\hat{\mathcal{M}}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar},$
(2.8)

which represents how well one can estimate the loss uniformly on
$\hat{\mathcal{M}}$ by the empirical risk under $\tilde{\mathcal{D}}_{M}$.

######  Remark 2.1.

We assume that the supremum in (2.8) is $(\Omega,\mathcal{S})$-measurable, so
it is meaningful to calculate probabilities of events which involve it. We
also assume throughout this paper that this supremum, over any fixed
$\mathcal{M}\in\mathbb{C}(\mathcal{H}),$ is also
$(\Omega,\mathcal{S})$-measurable.

###  2.4. Deviation bounds and main results

In classical learning theory, or VC theory, there are two kinds of estimation
errors, whose tail probabilities are

$\displaystyle\mathbb{P}$
$\displaystyle\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L_{\mathcal{D}_{N}}(h)-L(h)\text{\textbar}>\epsilon\right)$
(2.9)

and

$\displaystyle\mathbb{P}$
$\displaystyle\left(L(\hat{h}^{\mathcal{D}_{N}})-L(h^{\star})>\epsilon\right),$
(2.10)

for $\epsilon>0$. In the terminology of this paper, they are called,
respectively, type I and II estimation error, when the target hypotheses of
$\mathcal{H}$ are estimated by minimizing the empirical risk under sample
$\mathcal{D}_{N}$.

When the loss function is bounded, the rate of convergence of (2.10) to zero
is decreasing on the VC dimension of $\mathcal{H}$. This is the main result of
VC theory, which may be stated as follows, and is a consequence of Corollaries
A.12 and A.22. Observe that the bounds do not depend on $P$, and are valid for
any distribution $Z$ may have, that is, are distribution-free. A result
analogous to Proposition 2.2 will be stated for unbounded loss functions in
Section 4. In what follows, a.s. stands for almost sure convergence or
convergence with probability one.

######  Proposition 2.2.

Assume the loss function is bounded. Fixed a hypotheses space $\mathcal{H}$
with $d_{VC}(\mathcal{H})<\infty$, there exist sequences
$\\{B^{I}_{N,\epsilon}:N\geq 1\\}$ and $\\{B^{II}_{N,\epsilon}:N\geq 1\\}$ of
positive real-valued increasing functions with domain $\mathbb{Z}_{+}$
satisfying

$\lim\limits_{N\to\infty}B^{I}_{N,\epsilon}(k)=\lim\limits_{N\to\infty}B^{II}_{N,\epsilon}(k)=0,$

for all $\epsilon>0$ and $k\in\mathbb{Z}_{+}$ fixed, such that

$\displaystyle\mathbb{P}$
$\displaystyle\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L_{\mathcal{D}_{N}}(h)-L(h)\text{\textbar}>\epsilon\right)\leq
B^{I}_{N,\epsilon}(d_{VC}(\mathcal{H}))$ $\displaystyle\mathbb{P}$
$\displaystyle\left(L(\hat{h}^{\mathcal{D}_{N}})-L(h^{\star})>\epsilon\right)\leq
B^{II}_{N,\epsilon}(d_{VC}(\mathcal{H})).$

Furthermore, the following holds:

$\displaystyle\sup\limits_{h\in\mathcal{H}}\text{\textbar}L_{\mathcal{D}_{N}}(h)-L(h)\text{\textbar}\xrightarrow[N\to\infty]{a.s.}0$
$\displaystyle
L(\hat{h}^{\mathcal{D}_{N}})-L(h^{\star})\xrightarrow[N\to\infty]{a.s.}0.$

The sequences $\\{B^{I}_{N,\epsilon}:N\geq 1\\}$ and
$\\{B^{II}_{N,\epsilon}:N\geq 1\\}$ are what we call the deviation bounds of
learning via empirical risk minimization in $\mathcal{H}$. The main results of
this paper are the convergence of $\hat{\mathcal{M}}$ to $\mathcal{M}^{\star}$
with probability one and deviation bounds for types I, II, III, and IV
estimation errors when learning via model selection with bounded or unbounded
loss function.

In special, it will follow that the established deviation bounds for the type
IV estimation error of learning via model selection may be tighter than that
for the type II estimation error of learning directly on $\mathcal{H}$ via
empirical risk minimization, and hence one may have a lower risk by learning
via model selection. This means that by introducing a bias III, which
converges to zero, we may decrease the variance II of the learning process, so
it is more efficient to learn via model selection.

In the following sections, we treat the cases of bounded and unbounded loss
functions.

######  Remark 2.3.

The quantity $N(d_{VC}(\mathcal{H}),\epsilon,\delta)$, introduced in (1.1), is
obtained by solving on $N$ the equation

$B_{N,\epsilon}^{II}(d_{VC}(\mathcal{H}))=1-\delta,$

hence developing deviation bounds is equivalent to obtaining the sample size
necessary to solve the learning problem with $\epsilon,\delta$ and
$d_{VC}(\mathcal{H})$ fixed.

##  3\. Learning via model selection with bounded loss functions

In Section 3.1, we show the convergence of $\hat{\mathcal{M}}$ to the target
model $\mathcal{M}^{\star}$ with probability one, and in Section 3.2 we
establish deviation bounds for the estimation errors of learning via model
selection when the loss function is bounded. We assume from now there exists a
constant $C>0$ such that

$\displaystyle 0\leq\ell(z,h)\leq C$ $\displaystyle\text{ for all
}z\in\mathcal{Z},h\in\mathcal{H}.$

###  3.1. Convergence to the target model

We start by studying a result weaker than the convergence of
$\hat{\mathcal{M}}$ to $\mathcal{M}^{\star}$, that is, the convergence of
$L(\hat{\mathcal{M}})$ to $L(\mathcal{M}^{\star})$.

In order to have $L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star})$, one does not
need to know exactly $L(\mathcal{M})$ for all
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$, i.e., one does not need
$\hat{L}(\mathcal{M})=L(\mathcal{M})$, for all
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$. We argue that it suffices to have
$\hat{L}(\mathcal{M})$ close enough to $L(\mathcal{M})$, for all
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$, so the global minimums of
$\mathbb{C}(\mathcal{H})$ will have the same risk as $\mathcal{M}^{\star}$,
even if it is not possible to properly estimate their risk. This “close
enough” depends on $P$, hence is not distribution-free, and is given by the
maximum discrimination error (MDE) of $\mathbb{C}(\mathcal{H})$ under $P$,
which we define as

$\epsilon^{\star}=\epsilon^{\star}(\mathbb{C}(\mathcal{H}),P)\coloneqq\min\limits_{\begin{subarray}{c}\mathcal{M}\in\mathbb{C}(\mathcal{H})\\\
L(\mathcal{M})>L(\mathcal{M}^{\star})\end{subarray}}L(\mathcal{M})-L(\mathcal{M}^{\star}).$

The MDE is the minimum difference between the out-of-sample risk of a target
hypothesis and the best hypothesis in a model which does not contain a target.
In other words, it is the difference between the risk of the best model
$\mathcal{M}^{\star}$ and the second to best. The meaning of
$\epsilon^{\star}$ is depicted in Figure 4.

Figure 4. The risks of the equivalence classes (cf. (2.4)) of
$\mathbb{C}(\mathcal{H})$ in ascending order. The MDE $\epsilon^{\star}$ is
the difference between the risk of the target class $\mathcal{M}^{\star}$, and
the second to best $\mathcal{M}_{2}$. The colored intervals represent a
distance of $\epsilon^{\star}/2$ from the out-of-sample risk of each model,
and the colored estimated risks $\hat{L}$ illustrate a case such that the
estimated risk is within $\epsilon^{\star}/2$ of the out-of-sample risk for
all models. The class $\mathcal{M}_{1}$ has the same risk as
$\mathcal{M}^{\star}$, but has a smaller estimated risk, and, by the
definition of $\mathcal{M}^{\star}$, greater VC dimension. Note from the
representation that, if one can estimate $\hat{L}$ within a margin of error of
$\epsilon^{\star}/2$, then $\hat{\mathcal{M}}$ will be a model with the same
risk as $\mathcal{M}^{\star}$, in this case $\mathcal{M}_{1}$ (cf. Proposition
3.1).

The MDE is defined only if there exists at least one
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$ such that
$h^{\star}\cap\mathcal{M}=\emptyset$, i.e., there is a subset in
$\mathbb{C}(\mathcal{H})$ which does not contain a target hypothesis. If
$h^{\star}\cap\mathcal{M}\neq\emptyset$ for all
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$, then type III estimation error is
zero, and type IV reduces to type II. From this point, we assume that
$\epsilon^{\star}$ is well defined.

The terminology MDE is used for we can show that a fraction of
$\epsilon^{\star}$ is the greatest error one can commit when estimating
$L(\mathcal{M})$ by $\hat{L}(\mathcal{M})$, for all
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$, in order for $L(\mathcal{\hat{M}})$
to be equal to $L(\mathcal{M}^{\star})$. This is the result of the next
proposition.

######  Proposition 3.1.

Assume there exists $\delta>0$ such that

$\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}<\epsilon^{\star}/2\right)\geq
1-\delta.$ (3.1)

Then

$\mathbb{P}\left(L(\mathcal{\hat{M}})=L(\mathcal{M}^{\star})\right)\geq
1-\delta.$ (3.2)

######  Remark 3.2.

Since there may exist $\mathcal{M}\in\
\nicefrac{{\mathbb{C}(\mathcal{H})}}{{\sim}}$ with
$L(\mathcal{M})=L(\mathcal{\mathcal{M}^{\star}})$ and
$d_{VC}(\mathcal{M})>d_{VC}(\mathcal{M}^{\star})$, condition (3.1) guarantees
only that the estimated risk of both $\mathcal{M}$ and $\mathcal{M}^{\star}$
is lesser than the estimated risk of any model with risk greater than theirs,
but it may happen that $\hat{L}(\mathcal{M})<\hat{L}(\mathcal{M}^{\star})$
(see Figure 4 for an example). In this instance, we have
$\hat{\mathcal{M}}=\mathcal{M}$ and
$L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star})$.

Recall we are assuming that $\hat{L}$ is of the form (2.3). In this case, we
may obtain a bound for (3.2) depending on $\epsilon^{\star}$, on
$d_{VC}(\mathbb{C}(\mathcal{H}))$, and on bounds for tail probabilities of
type I estimation error under each validation and training sample (cf.
Proposition 2.2). These bounds also depend on the number of maximal models of
$\mathbb{C}(\mathcal{H})$, which are models in

$\displaystyle\text{Max
}\mathbb{C}(\mathcal{H})=\left\\{\mathcal{M}\in\mathbb{C}(\mathcal{H}):\text{
if }\mathcal{M}\subset\mathcal{M}^{\prime}\in\mathbb{C}(\mathcal{H})\text{
then }\mathcal{M}=\mathcal{M}^{\prime}\right\\},$

that are models not contained in any element in $\mathbb{C}(\mathcal{H})$
besides themselves. We denote

$\mathfrak{m}(\mathbb{C}(\mathcal{H}))=\text{\textbar}\text{Max
}\mathbb{C}(\mathcal{H})\text{\textbar},$

the number of maximal models in $\mathbb{C}(\mathcal{H})$. We have the
following rate of convergence of $L(\hat{\mathcal{M}})$ to
$L(\mathcal{M}^{\star})$, and condition for $\hat{\mathcal{M}}$ to converge to
$\mathcal{M}^{\star}$ with probability one.

######  Theorem 3.3.

Assume the loss function is bounded. For each $\epsilon>0$, let
$\\{B_{N,\epsilon}:N\geq 1\\}$ and $\\{\hat{B}_{N,\epsilon}:N\geq 1\\}$ be
sequences of positive real-valued increasing functions with domain
$\mathbb{Z}_{+}$ satisfying

$\lim\limits_{N\to\infty}B_{N,\epsilon}(k)=\lim\limits_{N\to\infty}\hat{B}_{N,\epsilon}(k)=0,$

for all $\epsilon>0$ and $k\in\mathbb{Z}_{+}$ fixed, and such that

$\displaystyle\max_{j}\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon\right)\leq
B_{N,\epsilon}(d_{VC}(\mathcal{M}))$ and
$\displaystyle\max_{j}\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon\right)\leq\hat{B}_{N,\epsilon}(d_{VC}(\mathcal{M})),$

for all $\mathcal{M}\in\mathbb{C}(\mathcal{M})$, recalling that
$L_{\mathcal{D}_{N}^{(j)}}$ and $\hat{L}^{(j)}$ represent the empirical risk
under the $j$-th training and validation samples, respectively. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then,

$\displaystyle\mathbb{P}\left(L(\hat{\mathcal{M}})\neq
L(\mathcal{M}^{\star})\right)$ $\displaystyle\leq m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[B_{N,\epsilon^{\star}/8}(d_{VC}(\mathbb{C}(\mathcal{H})))+\hat{B}_{N,\epsilon^{\star}/4}(d_{VC}(\mathbb{C}(\mathcal{H})))\right],$
(3.3)

in which $m$ is the number of pairs considered to calculate (2.3).
Furthermore, if

$\displaystyle\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}\max_{j}\sup\limits_{h\in\mathcal{M}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}\xrightarrow{\text{a.s.}}0$
and (3.4)
$\displaystyle\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}\max_{j}\sup\limits_{h\in\mathcal{M}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}\xrightarrow{\text{a.s.}}0,$

then

$\lim_{N\rightarrow\infty}\mathbb{P}\left(\hat{\mathcal{M}}=\mathcal{M}^{\star}\right)=1.$

A bound for $\mathbb{P}(L(\hat{\mathcal{M}})\neq L(\mathcal{M}^{\star}))$, and
the almost sure convergence of $\hat{\mathcal{M}}$ to $\mathcal{M}^{\star}$ in
the case of k-fold cross validation, follow from Proposition 2.2, recalling
that the sample size in each training and validation sample is $(k-1)n$ and
$n$, respectively, with $N=kn$. Analogously, we may obtain a bound when an
independent validation sample is considered. This result is stated in the next
theorem.

######  Theorem 3.4.

Assume the loss function is bounded. If $\hat{L}$ is given by k-fold cross-
validation or by an independent validation sample, then $\hat{\mathcal{M}}$
converges with probability one to $\mathcal{M}^{\star}$.

From bound (3.3), follows that we have to better estimate with the training
samples, that require a precision of $\epsilon^{\star}/8$ in contrast to a
precision $\epsilon^{\star}/4$ with the validation samples. Hence, as is done
in k-fold cross validation, it is better to consider a greater sample size for
training rather than for validation.

Moreover, from this bound follows that, with a fixed sample size, we can have
a tighter bound for $\mathbb{P}(L(\hat{\mathcal{M}})\neq
L(\mathcal{M}^{\star}))$ by choosing a family of candidate models with small
$d_{VC}(\mathbb{C}(\mathcal{H}))$ and few maximal elements, while attempting
to increase $\epsilon^{\star}$. Of course, there is a trade-off between
$d_{VC}(\mathbb{C}(\mathcal{H}))$ and the number of maximal elements of
$\mathbb{C}(\mathcal{H})$, the only known free quantities in bound
$\eqref{bound_pM}$, since the sample size is fixed and $\epsilon^{\star}$ is
unknown.

###  3.2. Deviation bounds for estimation errors on $\hat{\mathcal{M}}$

Bounds for types I and II estimation errors when learning on a random model
with a sample independent of the one employed to compute such random model,
may be obtained when there is a bound for them on each
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$ under the independent sample. This is
the content of Theorem 3.5.

######  Theorem 3.5.

Fix a bounded loss function. Assume we are learning with an independent sample
$\tilde{\mathcal{D}}_{M}$, and that for each $\epsilon>0$ there exist
sequences $\\{B^{I}_{M,\epsilon}:M\geq 1\\}$ and $\\{B^{II}_{M,\epsilon}:M\geq
1\\}$ of positive real-valued increasing functions with domain
$\mathbb{Z}_{+}$ satisfying

$\lim\limits_{M\to\infty}B^{I}_{M,\epsilon}(k)=\lim\limits_{M\to\infty}B^{II}_{M,\epsilon}(k)=0,$

for all $\epsilon>0$ and $k\in\mathbb{Z}_{+}$ fixed, such that

$\displaystyle\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\right)\leq
B^{I}_{M,\epsilon}(d_{VC}(\mathcal{M}))$ and (3.5)
$\displaystyle\mathbb{P}\left(L(\hat{h}_{\mathcal{M}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{M}})>\epsilon\right)\leq
B^{II}_{M,\epsilon}(d_{VC}(\mathcal{M})),$

for all $\mathcal{M}\in\mathbb{C}(\mathcal{H})$. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then, for any $\epsilon>0$,

$\displaystyle\textbf{(I)}\ \mathbb{P}$
$\displaystyle\left(\sup\limits_{h\in\mathcal{\hat{M}}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\right)\leq\mathbb{E}\Big{[}B^{I}_{M,\epsilon}(d_{VC}(\mathcal{\hat{M}}))\Big{]}\leq
B^{I}_{M,\epsilon}\left(d_{VC}(\mathbb{C}(\mathcal{H}))\right)$

and

$\displaystyle\textbf{(II)}\
\mathbb{P}\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{\hat{M}}})>\epsilon\right)\leq\mathbb{E}\Big{[}B^{II}_{M,\epsilon}(d_{VC}(\mathcal{\hat{M}}))\Big{]}\leq
B^{II}_{M,\epsilon}\left(d_{VC}(\mathbb{C}(\mathcal{H}))\right),$

in which the expectations are over all samples $\mathcal{D}_{N}$, from which
$\hat{\mathcal{M}}$ is calculated. Since
$d_{VC}(\mathbb{C}(\mathcal{H}))<\infty$, both probabilities above converge to
zero when $M\to\infty$.

Our definition of $\mathcal{\hat{M}}$ ensures that it is going to have the
smallest VC dimension under the constraint that it is a global minimum of
$\mathbb{C}(\mathcal{H})$. As the quantities inside the expectations of
Theorem 3.5 are increasing functions of VC dimension, fixed $\epsilon$ and
$M$, we tend to have smaller expectations, thus tighter bounds for types I and
II estimation errors. Furthermore, it follows from Theorem 3.5 that the sample
complexity needed to learn on $\hat{\mathcal{M}}$ is at most that of
$d_{VC}(\mathbb{C}(\mathcal{H}))$. This implies that this complexity is at
most that of $\mathcal{H}$, but may be much lesser if
$d_{VC}(\mathbb{C}(\mathcal{H}))\ll d_{VC}(\mathcal{H})$. We conclude that the
bounds for the tail probabilities of types I and II estimation errors on
$\hat{\mathcal{M}}$ are tighter than that on $\mathcal{H}$ (cf. Corollaries
A.12 and A.22), and the sample complexity needed to learn on
$\hat{\mathcal{M}}$ is at most that of $\mathbb{C}(\mathcal{H})$, and not of
$\mathcal{H}$.

A bound for type III estimation error may be obtained using methods similar to
that we employed to prove Theorem 3.3. As in that theorem, the bound for type
III estimation error depends on $\epsilon^{\star}$, on bounds for type I
estimation error under each training and validation sample, and on
$\mathbb{C}(\mathcal{H})$, more specifically, on its VC dimension and number
of maximal elements. To ease notation, we denote
$\epsilon\vee\epsilon^{\star}\coloneqq\max\\{\epsilon,\epsilon^{\star}\\}$ for
any $\epsilon>0$.

######  Theorem 3.6.

Assume the premises of Theorem 3.3 are in force. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then, for any $\epsilon>0$,

(III) $\displaystyle\
\mathbb{P}\left(L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})>\epsilon\right)$
$\displaystyle\leq m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[B_{N,(\epsilon\vee\epsilon^{\star})/8}(d_{VC}(\mathbb{C}(\mathcal{H})))+\hat{B}_{N,(\epsilon\vee\epsilon^{\star})/4}(d_{VC}(\mathbb{C}(\mathcal{H})))\right].$

In particular,

$\displaystyle\lim_{N\rightarrow\infty}\mathbb{P}\left(L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})>\epsilon\right)=0,$

for any $\epsilon>0$.

On the one hand, by definition of $\epsilon^{\star}$, if
$\epsilon<\epsilon^{\star}$, then type III estimation error is lesser than
$\epsilon$ if, and only if, $L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star})$, so
this error is actually zero, and the result of Theorem 3.3 is a bound for type
III estimation error in this case. On the other hand, if
$\epsilon>\epsilon^{\star}$, one way of having type III estimation error
lesser than $\epsilon$ is to have the estimated risk of each $\mathcal{M}$ at
a distance at most $\epsilon/2$ from its out-of-sample risk and, as can be
inferred from the proof of Theorem 3.3, this can be accomplished if one has
type I estimation error not greater than a fraction of $\epsilon$ under each
training and validation sample considered, so a modification of Theorem 3.3
applies to this case.

Finally, as the tail probability of type IV estimation error may be bounded by
the following inequality, involving the tail probabilities of types II and III
estimation errors,

$\displaystyle\textbf{(IV)}\ \mathbb{P}$
$\displaystyle\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star})>\epsilon\right)$
$\displaystyle\leq\mathbb{P}\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{\hat{M}}})>\epsilon/2\right)+\mathbb{P}\left(L(h^{\star}_{\mathcal{\hat{M}}})-L(h^{\star})>\epsilon/2\right),$
(3.6)

a bound for (3.2) is a direct consequence of Theorems 3.5 and 3.6.

######  Corollary 3.7.

Assume the premises of Theorems 3.3 and 3.5 are in force. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then, for any $\epsilon>0$,

$\displaystyle\textbf{(IV)}\
\mathbb{P}\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star})>\epsilon\right)$
$\displaystyle\leq\mathbb{E}\Big{[}B^{II}_{M,\epsilon/2}(d_{VC}(\mathcal{\hat{M}}))\Big{]}$
$\displaystyle+m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[B_{N,(\epsilon/2\vee\epsilon^{\star})/8}(d_{VC}(\mathbb{C}(\mathcal{H})))+\hat{B}_{N,(\epsilon/2\vee\epsilon^{\star})/4}(d_{VC}(\mathbb{C}(\mathcal{H})))\right]$
$\displaystyle\leq B^{II}_{M,\epsilon/2}(d_{VC}(\mathbb{C}(\mathcal{H})))$
$\displaystyle+m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[B_{N,(\epsilon/2\vee\epsilon^{\star})/8}(d_{VC}(\mathbb{C}(\mathcal{H})))+\hat{B}_{N,(\epsilon/2\vee\epsilon^{\star})/4}(d_{VC}(\mathbb{C}(\mathcal{H})))\right].$

In particular,

$\displaystyle\lim_{\begin{subarray}{c}N\rightarrow\infty\\\
M\rightarrow\infty\end{subarray}}\mathbb{P}\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star})>\epsilon\right)=0,$

for any $\epsilon>0$.

##  4\. Learning via model selection with unbounded loss functions

When the loss function is unbounded, we need to consider relative estimation
errors and make assumptions about the tail weight of $P$. Heavy tail
distributions are classically defined as those with a tail heavier than that
of exponential distributions [15]. Nevertheless, in the context of learning,
the tail weight of $P$ should take into account the loss function $\ell$.
Hence, for $1<p<\infty$ and a fixed hypotheses space $\mathcal{H}$, we measure
the weight of the tails of distribution $P$ by

$\tau_{p}\coloneqq\sup\limits_{h\in\mathcal{H}}\frac{\left(\int_{\mathcal{Z}}\ell^{p}(z,h)\
dP(z)\right)^{\frac{1}{p}}}{\int_{\mathcal{Z}}\ell(z,h)\
dP(z)}=\sup\limits_{h\in\mathcal{H}}\frac{L^{p}(h)}{L(h)},$

in which $L^{p}(h)\coloneqq\left(\int_{\mathcal{Z}}\ell^{p}(z,h)\
dP(z)\right)^{\frac{1}{p}}$. We omit the dependence of $\tau_{p}$ on $\ell$,
$P$ and $\mathcal{H}$ to simplify notation, since they will be clear from
context. The weight of the tails of distribution $P$ may be defined based on
$\tau_{p}$, as follows. Our presentation is analogous to [34, Section 5.7] and
is within the framework of [10].

######  Definition 4.1.

We say that distribution $P$ on $\mathcal{H}$ under $\ell$ has:

  * •

Light tails, if there exists a $p>2$ such that $\tau_{p}<\infty$;

  * •

Heavy tails, if there exists a $1<p\leq 2$ such that $\tau_{p}<\infty$, but
$\tau_{p}=\infty$ for all $p>2$;

  * •

Very heavy tails, if $\tau=\infty$ for all $p>1$.

We assume that $P$ has at most heavy tails, which means there exists a $p>1$,
that can be lesser than 2, with

$\displaystyle\tau_{p}<\tau^{\star}<\infty,$ (4.1)

that is, $P$ is in a class of distributions for which bound (4.1) holds. From
now on, fix a $p>1$ and a $\tau^{\star}$ such that (4.1) holds.

Besides the constraint (4.1), we also assume that the loss function is greater
or equal to one: $\ell(z,h)\geq 1$ for all $z\in\mathcal{Z},h\in\mathcal{H}$.
This is done to ease the presentation, and without loss of generality, since
it is enough to sum 1 to any unbounded loss function to have this property
and, in doing so, not only the minimizers of $L_{\mathcal{D}_{N}}$ and $L$ in
each model in $\mathbb{C}(\mathcal{H})$ remain the same, but also
$\epsilon^{\star}$ does not change. Hence, by summing one to the loss, the
estimated model $\hat{\mathcal{M}}$ and learned hypotheses from it do not
change, and the result of the model selection framework is the same. We refer
to Remark A.20 for the technical reason we choose to consider loss functions
greater than one.

Finally, we assume that $\ell$ has a finite moment of order $p$, under $P$ and
under the empirical measure, for all $h\in\mathcal{H}$. That is, defining333We
elevate (4.2) to the $1/p$ power to be consistent with the theory presented in
Appendix A.

$L_{\mathcal{D}_{N}}^{p}(h)\coloneqq\left(\frac{1}{N}\sum_{i=1}^{N}\ell^{p}(Z_{i},h)\right)^{\frac{1}{p}},$
(4.2)

we assume that

$\displaystyle\sup\limits_{h\in\mathcal{H}}L_{\mathcal{D}_{N}}^{p}(h)<\infty$
and $\displaystyle\sup\limits_{h\in\mathcal{H}}L^{p}(h)<\infty,$ (4.3)

in which the first inequality should hold with probability one, for all
possible samples $\mathcal{D}_{N}$. Since the moments $L^{p}(h)$ are
increasing in $p$, (4.3) actually implies (4.1), so (4.3) is the non-trivial
constraint in distribution $P$.

Although this is a deviation from the distribution-free framework, it is a
mild constraint in distribution $P$. On the one hand, the condition on $L^{p}$
is usually satisfied for distributions observed in real data (see [34, Section
5.7] for examples with Normal, Uniform, and Laplacian distributions under the
quadratic loss function). On the other hand, the condition on
$L_{\mathcal{D}_{N}}^{p}$ is more a feature of the loss function, than of the
distribution $P$, and can be guaranteed if one excludes from $\mathcal{H}$
some hypotheses with arbitrarily large loss in a way that $h^{\star}$ and
$d_{VC}(\mathcal{H})$ remain the same (see Lemma A.13 and Remark A.19 for more
details).

When the loss function is unbounded, besides the constraints in the moments of
$\ell$, under $P$ and the empirical measure, we also have to consider variants
of the estimation errors. Instead of the estimation errors, we consider the
relative estimation errors:

$\displaystyle\textbf{(I)}\sup\limits_{h\in\hat{\mathcal{M}}}\
\frac{\text{\textbar}L(h)-L_{\tilde{\mathcal{D}}_{M}}(h)\text{\textbar}}{L(h)}$
$\displaystyle\textbf{(II)}\
\frac{L(\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}})-L(h^{\star}_{\hat{\mathcal{M}}})}{L(\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}})}$
$\displaystyle\textbf{(III)}\
\frac{L(h^{\star}_{\hat{\mathcal{M}}})-L(h^{\star})}{L(h^{\star}_{\hat{\mathcal{M}}})}$
$\displaystyle\textbf{(IV)}\
\frac{L(\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}})-L(h^{\star})}{L(\hat{h}_{\hat{\mathcal{M}}}^{\mathbb{A}})}$

where algorithm $\mathbb{A}$ is dependent on the estimation technique once
$\hat{\mathcal{M}}$ is selected.

In this section, we prove analogues of Theorems 3.3, 3.5 and 3.6. Before
starting the study of the convergence of $\hat{\mathcal{M}}$ to
$\mathcal{M}^{\star}$, we state a result analogous to Proposition 2.2 about
deviation bounds of relative type I and II estimation errors on $\mathcal{H}$,
which are a consequence of Corollaries A.16 and A.23. These are novel results
of this paper which extend that of [10].

######  Proposition 4.2.

Assume the loss function is unbounded and $P$ is such that (4.3) hold. Fixed a
hypotheses space $\mathcal{H}$ with $d_{VC}(\mathcal{H})<\infty$, there exist
sequences $\\{B^{I}_{N,\epsilon}:N\geq 1\\}$ and $\\{B^{II}_{N,\epsilon}:N\geq
1\\}$ of positive real-valued increasing functions with domain
$\mathbb{Z}_{+}$ satisfying

$\lim\limits_{N\to\infty}B^{I}_{N,\epsilon}(k)=\lim\limits_{N\to\infty}B^{II}_{N,\epsilon}(k)=0,$

for all $\epsilon>0$ and $k\in\mathbb{Z}_{+}$ fixed, such that

$\displaystyle\mathbb{P}$
$\displaystyle\left(\sup\limits_{h\in\mathcal{H}}\frac{\text{\textbar}L_{\mathcal{D}_{N}}(h)-L(h)\text{\textbar}}{L(h)}>\epsilon\right)\leq
B^{I}_{N,\epsilon}(d_{VC}(\mathcal{H}))\text{ and }$ $\displaystyle\mathbb{P}$
$\displaystyle\left(\frac{L(\hat{h}^{\mathcal{D}_{N}})-L(h^{\star})}{L(\hat{h}^{\mathcal{D}_{N}})}>\epsilon\right)\leq
B^{II}_{N,\epsilon}(d_{VC}(\mathcal{H})).$

Furthermore, the following holds:

$\displaystyle\sup\limits_{h\in\mathcal{H}}\frac{\text{\textbar}L_{\mathcal{D}_{N}}(h)-L(h)\text{\textbar}}{L(h)}\xrightarrow[N\to\infty]{a.s.}0$
and
$\displaystyle\frac{L(\hat{h}^{\mathcal{D}_{N}})-L(h^{\star})}{L(\hat{h}^{\mathcal{D}_{N}})}\xrightarrow[N\to\infty]{a.s.}0.$

The results of this section seek to obtain insights about the asymptotic
behavior of learning via model selection in the case of unbounded loss
functions, rather than obtain the tightest possible bounds. Hence, in some
results, the simplicity of the bounds is preferred over its tightness, and
tighter bounds may be readily obtained from the proofs.

###  4.1. Convergence to the target model

We start by showing a result similar to Theorem 3.3.

######  Theorem 4.3.

Assume the loss function is unbounded and $P$ is such that (4.3) hold. For
each $\epsilon>0$, let $\\{B_{N,\epsilon}:N\geq 1\\}$ and
$\\{\hat{B}_{N,\epsilon}:N\geq 1\\}$ be sequences of positive real-valued
increasing functions with domain $\mathbb{Z}_{+}$ satisfying

$\lim\limits_{N\to\infty}B_{N,\epsilon}(k)=\lim\limits_{N\to\infty}\hat{B}_{N,\epsilon}(k)=0,$

for all $\epsilon>0$ and $k\in\mathbb{Z}_{+}$ fixed, and such that

$\displaystyle\max_{j}\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\frac{\text{\textbar}L(h)-L_{\mathcal{D}_{N}^{(j)}}(h)\text{\textbar}}{L(h)}>\epsilon\right)\leq
B_{N,\epsilon}(d_{VC}(\mathcal{M}))$ and
$\displaystyle\max_{j}\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\frac{\text{\textbar}L(h)-\hat{L}^{(j)}(h)\text{\textbar}}{L(h)}>\epsilon\right)\leq\hat{B}_{N,\epsilon}(d_{VC}(\mathcal{M})),$

for all $\mathcal{M}\in\mathbb{C}(\mathcal{M})$, recalling that
$L_{\mathcal{D}_{N}^{(j)}}$ and $\hat{L}^{(j)}$ represent the empirical risk
under the $j$-th training and validation samples, respectively. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then,

$\displaystyle\mathbb{P}\left(L(\hat{\mathcal{M}})\neq
L(\mathcal{M}^{\star})\right)\leq 2m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[\hat{B}_{N,\frac{\delta(1-\delta)}{2}}(d_{VC}(\mathbb{C}(\mathcal{H})))+B_{N,\frac{\delta(1-\delta)}{4}}(d_{VC}(\mathbb{C}(\mathcal{H})))\right],$

in which $m$ is the number of pairs considered to calculate (2.3) and

$\delta\coloneqq\frac{\epsilon^{\star}}{2\max\limits_{i\in\mathcal{J}}L(\mathcal{M}_{i})}.$

Furthermore, if

$\displaystyle\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}\max_{j}\sup\limits_{h\in\mathcal{M}}\frac{\text{\textbar}L(h)-L_{\mathcal{D}_{N}^{(j)}}(h)\text{\textbar}}{L(h)}\xrightarrow[N\to\infty]{\text{a.s.}}0$
and (4.4)
$\displaystyle\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}\max_{j}\sup\limits_{h\in\mathcal{M}}\frac{\text{\textbar}L(h)-\hat{L}^{(j)}(h)\text{\textbar}}{L(h)}\xrightarrow[N\to\infty]{\text{a.s.}}0,$

then

$\lim_{N\rightarrow\infty}\mathbb{P}\left(\hat{\mathcal{M}}=\mathcal{M}^{\star}\right)=1.$

In this instance, a bound for $\mathbb{P}(L(\hat{\mathcal{M}})\neq
L(\mathcal{M}^{\star}))$, and the almost sure convergence of
$\hat{\mathcal{M}}$ to $\mathcal{M}^{\star}$, in the case of k-fold cross
validation and independent validation sample, follow from Proposition 4.2 in a
manner analogous to Theorem 3.4. We state the almost sure convergence in
Theorem 4.4, whose proof is analogous to that of Theorem 3.4, and follows from
Corollary A.16.

######  Theorem 4.4.

Assume the loss function is unbounded and $P$ is such that (4.3) hold. If
$\hat{L}$ is given by k-fold cross-validation or by an independent validation
sample, then $\hat{\mathcal{M}}$ converges with probability one to
$\mathcal{M}^{\star}$.

###  4.2. Convergence of estimation errors on $\hat{\mathcal{M}}$

The results stated here are rather similar to the case of bounded loss
functions, with some minor modifications. Hence, we state the analogous
results and present a proof only when it is different from the respective
result in Section 3.2.

Bounds for relative types I and II estimation errors, when learning on a
random model with a sample independent of the one employed to compute such
random model, may be obtained as in Theorem 3.5. In fact, the proof of the
following bounds are the same as in that theorem, with the respective changes
from estimation errors to relative estimation errors. Hence, we state the
results without a proof.

######  Theorem 4.5.

Fix an unbounded loss function and assume $P$ is such that (4.3) hold. Assume
we are learning with an independent sample $\tilde{\mathcal{D}}_{M}$, and that
for each $\epsilon>0$ there exist sequences $\\{B^{I}_{M,\epsilon}:M\geq 1\\}$
and $\\{B^{II}_{M,\epsilon}:M\geq 1\\}$ of positive real-valued increasing
functions with domain $\mathbb{Z}_{+}$ satisfying

$\lim\limits_{M\to\infty}B^{I}_{M,\epsilon}(k)=\lim\limits_{M\to\infty}B^{II}_{M,\epsilon}(k)=0,$

for all $\epsilon>0$ and $k\in\mathbb{Z}_{+}$ fixed, such that

$\displaystyle\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\frac{\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}}{L(h)}>\epsilon\right)\leq
B^{I}_{M,\epsilon}(d_{VC}(\mathcal{M}))$ and
$\displaystyle\mathbb{P}\left(\frac{L(\hat{h}_{\mathcal{M}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{M}})}{L(\hat{h}_{\mathcal{M}}^{\tilde{\mathcal{D}}_{M}})}>\epsilon\right)\leq
B^{II}_{M,\epsilon}(d_{VC}(\mathcal{M})),$

for all $\mathcal{M}\in\mathbb{C}(\mathcal{H})$. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then, for any $\epsilon>0$,

$\displaystyle\textbf{(I)}\ \mathbb{P}$
$\displaystyle\left(\sup\limits_{h\in\mathcal{\hat{M}}}\frac{\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}}{L(h)}>\epsilon\right)\leq\mathbb{E}\Big{[}B^{I}_{M,\epsilon}(d_{VC}(\mathcal{\hat{M}}))\Big{]}\leq
B^{I}_{M,\epsilon}\left(d_{VC}(\mathbb{C}(\mathcal{H}))\right)$

and

$\displaystyle\textbf{(II)}\
\mathbb{P}\left(\frac{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{\hat{M}}})}{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})}>\epsilon\right)\leq\mathbb{E}\Big{[}B^{II}_{M,\epsilon}(d_{VC}(\mathcal{\hat{M}}))\Big{]}\leq
B^{II}_{M,\epsilon}\left(d_{VC}(\mathbb{C}(\mathcal{H}))\right),$

in which the expectations are over all samples $\mathcal{D}_{N}$, from which
$\hat{\mathcal{M}}$ is calculated. Since
$d_{VC}(\mathbb{C}(\mathcal{H}))<\infty$, both probabilities above converge to
zero when $M\to\infty$.

The convergence to zero of relative type III estimation error may be obtained,
as in Theorem 3.6, by the methods used to prove Theorem 4.3. We state and
prove this result, since its proof is slightly different from that of Theorem
3.6.

######  Theorem 4.6.

Assume the premises of Theorem 4.3 are in force. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then, for any $\epsilon>0$,

(III) $\displaystyle\
\mathbb{P}\left(\frac{L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})}{L(h_{\hat{\mathcal{M}}}^{\star})}>\frac{\epsilon}{L(\mathcal{M}^{\star})}\right)$
$\displaystyle\leq 2m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[\hat{B}_{N,\frac{\delta^{\prime}(1-\delta^{\prime})}{2}}(d_{VC}(\mathbb{C}(\mathcal{H})))+B_{N,\frac{\delta^{\prime}(1-\delta^{\prime})}{4}}(d_{VC}(\mathbb{C}(\mathcal{H})))\right]$

in which

$\delta^{\prime}\coloneqq\frac{\epsilon\vee\epsilon^{\star}}{2\max\limits_{i\in\mathcal{J}}L(\mathcal{M}_{i})}.$

In particular,

$\displaystyle\lim_{N\rightarrow\infty}\mathbb{P}\left(\frac{L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})}{L(h_{\hat{\mathcal{M}}}^{\star})}>\epsilon\right)=0,$

for any $\epsilon>0$.

Finally, a bound on the rate of convergence of type IV estimation error to
zero is a direct consequence of Theorems 4.5 and 4.6, and the following
inequality

$\displaystyle\textbf{(IV)}\
\mathbb{P}\left(\frac{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star})}{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})}>\frac{\epsilon}{L(\mathcal{M}^{\star})}\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{L(\hat{h}_{\mathcal{\hat{\mathcal{M}}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\hat{\mathcal{M}}})}{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})}>\frac{\epsilon}{2L(\mathcal{M}^{\star})}\right)+\mathbb{P}\left(\frac{L(h^{\star}_{\hat{\mathcal{M}}})-L(h^{\star})}{L(h^{\star}_{\mathcal{\hat{\mathcal{M}}}})}>\frac{\epsilon}{2L(\mathcal{M}^{\star})}\right),$

which is true since
$L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})\geq
L(h^{\star}_{\mathcal{\hat{M}}})$.

######  Corollary 4.7.

Assume the premises of Theorems 4.3 and 4.5 are in force. Let
$\mathcal{\hat{M}}\in\mathbb{C}(\mathcal{H})$ be a random model learned by
$\mathbb{M}_{\mathbb{C}(\mathcal{H})}$. Then, for any $\epsilon>0$,

$\displaystyle\mathbb{P}\left(\frac{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star})}{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})}>\frac{\epsilon}{L(\mathcal{M}^{\star})}\right)$
$\displaystyle\leq\mathbb{E}\Big{[}B^{II}_{M,\frac{\epsilon}{2L(\mathcal{M}^{\star})}}(d_{VC}(\mathcal{\hat{M}}))\Big{]}$
$\displaystyle+2m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[\hat{B}_{N,\frac{\delta^{\prime}(1-\delta^{\prime})}{2}}(d_{VC}(\mathbb{C}(\mathcal{H})))+B_{N,\frac{\delta^{\prime}(1-\delta^{\prime})}{4}}(d_{VC}(\mathbb{C}(\mathcal{H})))\right]$
$\displaystyle\leq
B^{II}_{M,\frac{\epsilon}{2L(\mathcal{M}^{\star})}}(d_{VC}(\mathbb{C}(\mathcal{H})))$
$\displaystyle+2m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[\hat{B}_{N,\frac{\delta^{\prime}(1-\delta^{\prime})}{2}}(d_{VC}(\mathbb{C}(\mathcal{H})))+B_{N,\frac{\delta^{\prime}(1-\delta^{\prime})}{4}}(d_{VC}(\mathbb{C}(\mathcal{H})))\right]$

with

$\delta^{\prime}\coloneqq\frac{\epsilon/2\vee\epsilon^{\star}}{2\max\limits_{i\in\mathcal{J}}L(\mathcal{M}_{i})}.$

In particular,

$\displaystyle\lim_{\begin{subarray}{c}N\rightarrow\infty\\\
M\rightarrow\infty\end{subarray}}\mathbb{P}\left(\frac{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star})}{L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})}>\epsilon\right)=0,$

for any $\epsilon>0$.

##  5\. Enhancing generalization by learning via model selection

In this section, we present an example illustrating that the bound for type IV
estimation error may be tighter than the classical VC bound for type II
estimation error in $\mathcal{H}$.

Let $\mathcal{X}$ be an arbitrary set with
$\text{\textbar}\mathcal{X}\text{\textbar}<\infty$ and let
$\mathcal{H}=\\{h:\mathcal{X}\mapsto\\{0,1\\}\\}$ be the set of all functions
from $\mathcal{X}$ to $\\{0,1\\}$. Assuming $Z=(X,Y)$ and
$\mathcal{Z}=\mathcal{X}\times\\{0,1\\}$, under the simple loss function
$\ell((x,y),h)=\mathds{1}\\{h(x)\neq y\\}$, it follows that
$d_{VC}(\mathcal{H})=\text{\textbar}\mathcal{X}\text{\textbar}$ and
$L(h)=\mathbb{P}(h(X)\neq Y)$ is the classification error.

Denote $\Pi=\\{\pi:\pi\text{ is a partition of }\mathcal{H}\\}$ as the set of
all partitions of $\mathcal{X}$. A partition $\pi=\\{p_{1},\dots,p_{k}\\}$ is
a collection of subsets of $\mathcal{X}$ such that

$\displaystyle\bigcup_{i=1}^{k}p_{i}=\mathcal{X}$ $\displaystyle p_{i}\cap
p_{i^{\prime}}=\emptyset\text{ if }i\neq i^{\prime}.$

Each partition $\pi\in\Pi$ creates an equivalence class in $\mathcal{X}$ with
equivalence between points in a same block of partition $\pi$:

$x\equiv_{\pi}y\iff\exists p\in\pi\text{ such that }\\{x,y\\}\subset p.$

For each $\pi\in\Pi$, define the model

$\mathcal{M}_{\pi}\coloneqq\left\\{h\in\mathcal{H}:h(x)=h(y)\text{ if
}x\equiv_{\pi}y\right\\}$

containing all functions that respect partition $\pi$, that is, classify
points in a same block of $\pi$ in a same class. Observe that
$d_{VC}(\mathcal{M}_{\pi})=\text{\textbar}\pi\text{\textbar}$ for all
$\pi\in\Pi$. We consider as candidate models

$\mathbb{C}(\mathcal{H})\coloneqq\left\\{\mathcal{M}_{\pi}:\pi\in\Pi\right\\},$

the collection of models that respect each partition of $\mathcal{X}$. Since
$\mathcal{H}\in\mathbb{C}(\mathcal{H})$, as
$\mathcal{H}=\mathcal{M}_{\mathcal{X}}$ where $\mathcal{X}$ is the partition
with singletons as blocks, $\mathbb{C}(\mathcal{H})$ covers $\mathcal{H}$.
Furthermore, $d_{VC}(\mathbb{C}(\mathcal{H}))=d_{VC}(\mathcal{H})$. Figure 5
presents an example of $\Pi$ and of models $\mathcal{M}_{\pi}$.

Figure 5. The set $\Pi$ of all partitions of $\mathcal{X}=\\{1,2,3,4\\}$. The
tables present the hypotheses in selected models
$\mathcal{M}_{\pi_{1}},\mathcal{M}_{\pi_{2}}$. The partitions with at most two
blocks, that generate $\mathbb{C}_{2}(\mathcal{H})$, are in orange. The edges
represent the partial relation $\leq$ between partitions, defined as
$\pi_{1}\leq\pi_{2}\iff\forall p\in\pi_{2},\exists p^{\prime}\in\pi_{1}\text{
such that }p\subset p^{\prime}$. Under this partial relation, $(\Pi,\leq)$ is
a complete lattice. Observe that, if $\pi_{1}\leq\pi_{2}$ then
$\mathcal{M}_{\pi_{1}}\subset\mathcal{M}_{\pi_{2}}$.

Another possible family of candidate models is formed only by the models which
respect a partition with at most two blocks:

$\mathbb{C}_{2}(\mathcal{H})\coloneqq\\{\mathcal{M}_{\pi}:\pi\in\Pi,\text{\textbar}\pi\text{\textbar}\leq
2\\}.$

These partitions are in orange in the example of Figure 5. For each
$h\in\mathcal{H}$ let

$\pi_{h}=\left\\{\\{x\in\mathcal{X}:h(x)=0\\},\\{x\in\mathcal{X}:h(x)=1\\}\right\\}$

be the partition of $\mathcal{X}$ generated by it, which has at most two
blocks. Clearly, $h\in\mathcal{M}_{\pi_{h}}$ which is in
$\mathbb{C}_{2}(\mathcal{H})$ for all $h\in\mathcal{H}$, what implies that
$\mathbb{C}_{2}(\mathcal{H})$ covers $\mathcal{H}$. Furthermore,
$d_{VC}(\mathbb{C}_{2}(\mathcal{H}))=2$ by construction.

Observe that $d_{VC}(\mathcal{M}^{\star})=2$ since it is the class of models
of form444Assuming that $h^{\star}$ is not constant. Otherwise,
$d_{VC}(\mathcal{M}^{\star})=1$. $\mathcal{M}_{h^{\star}}$. Hence, the target
class of both $\mathbb{C}(\mathcal{H})$ and $\mathbb{C}_{2}(\mathcal{H})$ is
the same. Actually, the MDE $\epsilon^{\star}$ is also the same in both
collections.

We will illustrate an instance where the established bound for type IV
estimation error when learning via model selection in
$\mathbb{C}_{2}(\mathcal{H})$ is tighter than the respective bound for type II
estimation error when learning in the whole $\mathcal{H}$ via empirical risk
minimization. We also illustrate that this may still be the case when learning
in $\mathbb{C}(\mathcal{H})$ when
$\hat{\mathcal{M}}\approx\mathcal{M}^{\star}$.

To this end, we first compare the bounds for type IV estimation error on
$\mathbb{C}_{2}(\mathcal{H})$ (cf. Corollary 3.7), with samples of size $N$
and $M=N$, when $\hat{L}$ is estimated with a validation sample, with
classical VC theory bounds for type II estimation error when learning directly
on $\mathcal{H}$ (cf. (2.10)), by considering the estimator
$\hat{h}^{\mathcal{D}_{2N}}$ that is a hypothesis that minimizes the empirical
risk in $\mathcal{H}$ of the whole sample of size $2N$.

On the one hand, by Corollary A.22, we have that

$\mathbb{P}\left(L(\hat{h}^{\mathcal{D}_{2N}})-L(h^{\star})>\epsilon\right)\leq
8\exp\left\\{d_{VC}(\mathcal{H})\left(1+\ln\frac{2N}{d_{VC}(\mathcal{H})}\right)-2N\frac{\epsilon^{2}}{128}\right\\}.$
(5.1)

On the other hand, by Corollaries 3.7, A.11 and A.22, when the independent
sample has size $N$, the validation sample has size $cN$ and the training
sample has size $(1-c)N$, with $0<c<1/2$, it follows that

$\displaystyle\mathbb{P}$
$\displaystyle\left(L(\hat{h}_{\mathcal{\hat{M}}}(\tilde{\mathcal{D}}_{N}))-L(h^{\star})>\epsilon\right)\leq
8\exp\left\\{2\left(1+\ln\frac{N}{2}\right)-N\frac{\epsilon^{2}}{512}\right\\}$
$\displaystyle+8\left(2^{d_{VC}(\mathcal{H})-1}-1\right)\Bigg{[}\exp\left\\{2\left(1+\ln\frac{cN}{2}\right)-cN\frac{(\epsilon/2\vee\epsilon^{\star})^{2}}{512}\right\\}$
$\displaystyle+\exp\left\\{2\left(1+\ln\frac{(1-c)N}{2}\right)-(1-c)N\frac{(\epsilon/2\vee\epsilon^{\star})^{2}}{2048}\right\\}\Bigg{]}.$
(5.2)

In Figure 6, we present, for selected values of $d_{VC}(\mathcal{H}),\epsilon$
and $\epsilon^{\star}$, the value of $N$ such that the bounds (5.1) and (5)
are equal to $0.05$, considering $c=0.2$. We first note that, in any case,
this value of $N$ is of order at least $10^{6}$, as is often the case with the
pessimistic distribution-free bounds of VC theory. Nevertheless, we see that
the bound for type IV estimation error is actually tighter when
$2\epsilon\leq\epsilon^{\star}$, meaning that, for $\epsilon$ small enough,
one needs fewer samples to properly estimate $h^{\star}$ when learning via
model selection on $\mathbb{C}_{2}(\mathcal{H})$, when compared with learning
via empirical risk minimization on $\mathcal{H}$ directly.

Figure 6. Sample size $N$ needed to have bounds (5.1) and (5) equal to $0.05$
as a function of $d_{VC}(\mathcal{H})$, for distinct values of
$\epsilon^{\star}$ (columns) and $\epsilon$ (lines), and $c=0.2$. The curves
of type II bound (5.1) are in red, and the ones of type IV bound (5) are in
green. When the red curve is below the green one, we have a tighter bound for
type II estimation error when learning directly on $\mathcal{H}$ with a sample
of size $2N$, while when the green curve is below the red one, we have a
tighter bound for type IV estimation error when learning via model selection
on $\mathbb{C}_{2}(\mathcal{H})$, with a training sample of size $0.8N$, a
validation sample of size $0.2N$, and an independent sample of size $N$. To
aid in the visualization, we painted the space between the two curves in green
when the bound of type IV estimation error (5) is tighter, and in red when the
bound of type II estimation error (5.1) is tighter.

Now, by learning via model selection on $\mathbb{C}(\mathcal{H})$ with samples
of size $N$ and $M=N$, when $\hat{L}$ is estimated with a validation sample,
and assuming that $d_{VC}(\hat{\mathcal{M}})\approx
d_{VC}(\mathcal{M}^{\star})=2$, we have the following bound for type IV
estimation error:

$\displaystyle\mathbb{P}$
$\displaystyle\left(L(\hat{h}_{\mathcal{\hat{M}}}(\tilde{\mathcal{D}}_{N}))-L(h^{\star})>\epsilon\right)\leq
8\exp\left\\{2\left(1+\ln\frac{N}{2}\right)-N\frac{\epsilon^{2}}{512}\right\\}$
$\displaystyle+8\Bigg{[}\exp\left\\{d_{VC}(\mathcal{H})\left(1+\ln\frac{cN}{d_{VC}(\mathcal{H})}\right)-cN\frac{(\epsilon/2\vee\epsilon^{\star})^{2}}{512}\right\\}$
$\displaystyle+\exp\left\\{d_{VC}(\mathcal{H})\left(1+\ln\frac{(1-c)N}{d_{VC}(\mathcal{H})}\right)-(1-c)N\frac{(\epsilon/2\vee\epsilon^{\star})^{2}}{2048}\right\\}\Bigg{]}.$
(5.3)

In Figure 7, we present, for selected values of $d_{VC}(\mathcal{H}),\epsilon$
and $\epsilon^{\star}$, the value of $N$ such that the bounds (5.1) and (5)
are equal to $0.05$, again considering $c=0.2$. We see in this case that bound
(5) may also be tighter than (5.1), but $\epsilon$ should be much lesser than
$\epsilon^{\star}$, for instance, $5\epsilon<\epsilon^{\star}$.

Figure 7. Sample size $N$ needed to have bounds (5.1) and (5) equal to $0.05$
as a function of $d_{VC}(\mathcal{H})$, for distinct values of
$\epsilon^{\star}$ (columns) and $\epsilon$ (lines), and $c=0.2$. The curves
of type II bound (5.1) are in red, and the ones of type IV bound (5) are in
green. When the red curve is below the green one, we have a tighter bound for
type II estimation error when learning directly on $\mathcal{H}$ with a sample
of size $2N$, while when the green curve is below the red one, we have a
tighter bound for type IV estimation error when learning via model selection
on $\mathbb{C}(\mathcal{H})$ with a training sample of size $0.8N$, a
validation sample of size $0.2N$ and an independent sample of size $N$. To aid
in the visualization, we painted the space between the two curves in green
when the bound of type IV estimation error (5) is tighter, and in red when the
bound of type II estimation error (5.1) is tighter.

##  6\. Discussion

We presented learning via model selection with cross-validation risk
estimation as a systematic data-driven framework consisting of selecting the
simplest global minimum of a family of candidate models, and then learning a
hypothesis on it with an independent sample, seeking to approximate a target
hypothesis of $\mathcal{H}$. We studied the distribution-free asymptotics of
such a framework by showing the convergence of the estimated model to the
target one, and of the estimation errors to zero, for both bounded and
unbounded loss functions. The case of bounded loss functions was treated with
the usual tools of VC theory, while the case of unbounded loss functions
required some new technical results, which are an extension of those in [10]
and were established in Appendix A.

We introduced the maximum discrimination error $\epsilon^{\star}$ and
evidenced the possibility of better learning with a fixed sample size by
properly modeling the family of candidate models, seeking to (a) have
$\mathcal{M}^{\star}$ with small VC dimension and (b) have a great MDE
$\epsilon^{\star}$. More interesting than the consistency, which is expected
from a probabilistic perspective, is that the rate of the convergences,
specially of type IV estimation error, evidence scenarios in which it may be
better to learn via model selection than directly on $\mathcal{H}$ via ERM.

From the results established, follow that the family of candidate models plays
an important role on the rate of convergence of
$\mathbb{P}(L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star}))$ to one, and of the
estimation errors to zero, through
$\mathfrak{m}(\mathbb{C}(\mathcal{H})),\epsilon^{\star}$ and
$d_{VC}(\mathcal{M}^{\star})$. Moreover, these results also shed light on
manners of improving the quality of the learning, i.e., decreasing the
estimation errors, specially type IV, when the sample size is fixed. We now
discuss some implications of the results of this paper.

First, since $\hat{\mathcal{M}}$ converges to $\mathcal{M}^{\star}$ with
probability one,

$\mathbb{E}(G(\mathcal{\hat{M}}))\xrightarrow{N\rightarrow\infty}G(\mathcal{M}^{\star}),$

by the Dominated Convergence Theorem, in which
$G:\mathbb{C}(\mathcal{H})\mapsto\mathbb{R}$ is any real-valued function,
since the domain of $G$ is finite. The convergence of
$\mathbb{E}(G(\mathcal{\hat{M}}))$ ensures that the expectations of functions
of $\hat{\mathcal{M}}$ on the right-hand side of inequalities in Theorems 3.5
and 4.5 and Corollaries 3.7 and 4.7 tend to the same functions evaluated at
$\mathcal{M}^{\star}$, when $N$ tends to infinity. Hence, if one was able to
isolate $h^{\star}$ within a model $\mathcal{M}^{\star}$ with small VC
dimension, the bounds for types I, II and IV estimation errors will tend to be
tighter for a sample of a given size $N+M$.

Second, if the MDE of $\mathbb{C}(\mathcal{H})$ under $P$ is great, then we
need less precision when estimating $L(\mathcal{M})$ for
$L(\hat{\mathcal{M}})$ to be equal to $L(\mathcal{M}^{\star})$, and for types
III and IV estimation errors to be lesser than a $\epsilon\ll\epsilon^{\star}$
with high probability, so fewer samples are needed to learn a model as good as
$\mathcal{M}^{\star}$ and to have lesser types III and IV estimation errors.
Moreover, the sample complexity to learn this model is that of the most
complex model in $\mathbb{C}(\mathcal{H})$, hence is at most the complexity of
a model with VC dimension $d_{VC}(\mathbb{C}(\mathcal{H}))$, which may be
lesser than that of $\mathcal{H}$.

Since the bounds were established for a general hypotheses space with finite
VC dimension in a distribution-free framework, they are not the tightest
possible in specific cases, hence an interesting topic for future research
would be to apply the methods used here to obtain tighter bounds for
restricted classes of hypotheses spaces, candidate models and/or data
generating distributions. The results of this paper may be extended when
distribution-dependent bounds for types I and II estimation errors are
available in the framework of Propositions 2.2 and 4.2. Observe that our
results assume there exist bounds $B_{N,\epsilon}^{I}(\mathcal{M})$ and
$B_{N,\epsilon}^{II}(\mathcal{M})$ for these estimation errors in each
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$. We assumed these bounds depended on
$\mathcal{M}$ by means only of $d_{VC}(\mathcal{M})$, but the results may be
extended if they depend on $\mathcal{M}$ through other complexity measure or
if they are distribution-dependent. We leave the study of such extensions for
future research. Moreover, when deducing the bounds, we have not made use of
the dependence between the samples in different folds and just applied a union
bound to consider each pair of samples separately. The bounds could be
improved if this dependence was considered, but it would be necessary to
restrict the study to a specific class of models, since such a result should
not be possible in a general framework.

Furthermore, although outside the scope of this paper, the computational cost
of computing $\hat{\mathcal{M}}$ by solving optimization problem (2.7) should
also be taken into consideration when choosing family
$\mathbb{C}(\mathcal{H})$. This family of candidate models should have some
structure that allows an efficient computation of (2.7), or the computation of
a suboptimal solution with satisfactory practical results. In the case of
variable selection, this could be performed via U-curve algorithms [30, 28, 5,
14, 29], that perform efficient searches on Boolean lattices, and an extension
of such algorithms could aid the computation of (2.7) when
$\mathbb{C}(\mathcal{H})$ is a non-Boolean lattice. We leave this topic for
future researches.

Finally, the choice of learning with an independent sample on
$\hat{\mathcal{M}}$ simplifies the bounds, but may not be practical in some
instances since requires a sample great enough to be divided into two. A
interesting topic for future researches would be to consider other forms of
learning on $\hat{\mathcal{M}}$ as, for example, by reusing the whole sample
$\mathcal{D}_{N}$ to learn on $\hat{\mathcal{M}}$ by empirical risk
minimization, what could work better with shortage of samples, but would be
liable to biases.

##  7\. Proof of results

###  7.1. Results of Section 3

###### Proof of Proposition 3.1.

If

$\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}<\epsilon^{\star}/2$

then, for any $i\in\mathcal{J}$ such that
$L(\mathcal{M}_{i})>L(\mathcal{M}^{\star})$, we have

$\displaystyle\hat{L}(\mathcal{M}_{i})-\hat{L}(\mathcal{M}^{\star})>L(\mathcal{M}_{i})-L(\mathcal{M}^{\star})-\epsilon^{\star}\geq
0,$ (7.1)

in which the last inequality follows from the definition of
$\epsilon^{\star}$. From (7.1) follows that the global minimum of
$\nicefrac{{\mathbb{C}(\mathcal{H})}}{{\hat{\sim}}}$ with the least VC
dimension, that is $\hat{\mathcal{M}}$, is such that
$L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star})$. Indeed, from (7.1) follows that
$\hat{L}(\mathcal{M})>\hat{L}(\mathcal{M}^{\star})$ for all
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$ such that
$L(\mathcal{M})>L(\mathcal{M}^{\star})$.

Hence, since $\hat{L}(\hat{\mathcal{M}})\leq\hat{L}(\mathcal{M}^{\star})$, we
must have $L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star})$. Therefore, we have
the inclusion of events

$\left\\{\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}<\epsilon^{\star}/2\right\\}\subset\left\\{L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star})\right\\},$
(7.2)

which proves the result. ∎

###### Proof of Theorem 3.3.

We will apply Proposition 3.1. Denoting
$\hat{h}_{i}^{(j)}\coloneqq\hat{h}_{\mathcal{M}_{i}}^{(j)}$,

$\displaystyle\mathbb{P}$
$\displaystyle\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}\geq\epsilon^{\star}/2\right)\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sum_{j=1}^{m}\frac{1}{m}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/2\right)$
$\displaystyle\leq\mathbb{P}\left(\max_{j}\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/2\right)$
$\displaystyle\leq\mathbb{P}\left(\bigcup_{j=1}^{m}\left\\{\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/2\right\\}\right)$
$\displaystyle\leq\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/2\right)$
$\displaystyle=\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-L(\hat{h}^{(j)}_{i})+L(\hat{h}^{(j)}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/2\right)$
$\displaystyle\leq\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}L(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})+\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\hat{h}^{(j)}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/2\right)$
$\displaystyle\leq\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}L(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})>\epsilon^{\star}/4\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\hat{h}^{(j)}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/4\right)$
$\displaystyle\leq\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}L(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})>\epsilon^{\star}/4\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup_{h\in\mathcal{M}_{i}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon^{\star}/4\right)$
(7.3)

in which in the first inequality we applied the definition of
$\hat{L}(\mathcal{M})$. For each $j$, the first probability in (7.1) is equal
to

$\displaystyle\mathbb{P}$
$\displaystyle\left(\max\limits_{i\in\mathcal{J}}L(\hat{h}^{(j)}_{i})-L_{\mathcal{D}_{N}^{(j)}}(\hat{h}^{(j)}_{i})+L_{\mathcal{D}_{N}^{(j)}}(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})>\epsilon^{\star}/4\right)$
$\displaystyle\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}L(\hat{h}^{(j)}_{i})-L_{\mathcal{D}_{N}^{(j)}}(\hat{h}^{(j)}_{i})+L_{\mathcal{D}_{N}^{(j)}}(h^{\star}_{i})-L(\mathcal{M}_{i})>\epsilon^{\star}/4\right)$
$\displaystyle\leq\mathbb{P}\left(\left\\{\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\hat{h}^{(j)}_{i})-L_{\mathcal{D}_{N}^{(j)}}(\hat{h}^{(j)}_{i})\text{\textbar}>\epsilon^{\star}/8\right\\}\bigcup\left\\{\max\limits_{i\in\mathcal{J}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h^{\star}_{i})-L(\mathcal{M}_{i})\text{\textbar}>\epsilon^{\star}/8\right\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup_{h\in\mathcal{M}_{i}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon^{\star}/8\right),$

in which the first inequality follows from the fact that
$L_{\mathcal{D}_{N}^{(j)}}(\hat{h}^{(j)}_{i})\leq
L_{\mathcal{D}_{N}^{(j)}}(h^{\star}_{i})$, and the last follows since
$L(\mathcal{M}_{i})=L(h^{\star}_{i})$. We conclude that

$\displaystyle\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}\geq\epsilon^{\star}/2\right)$
$\displaystyle\leq\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup_{h\in\mathcal{M}_{i}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon^{\star}/8\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup_{h\in\mathcal{M}_{i}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon^{\star}/4\right).$

If $\mathcal{M}_{1}\subset\mathcal{M}_{2}$ then, for any $\epsilon>0$ and
$j=1,\dots,m$, we have the following inclusion of events

$\displaystyle\left\\{\sup_{h\in\mathcal{M}_{1}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon\right\\}\subset\left\\{\sup_{h\in\mathcal{M}_{2}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon\right\\}$
$\displaystyle\left\\{\sup_{h\in\mathcal{M}_{1}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon\right\\}\subset\left\\{\sup_{h\in\mathcal{M}_{2}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon\right\\},$

hence it is true that

$\displaystyle\left\\{\max\limits_{i\in\mathcal{J}}\sup_{h\in\mathcal{M}_{i}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon^{\star}/4\right\\}\subset\left\\{\max_{\mathcal{M}\in\text{
Max
}\mathbb{C}(\mathcal{H})}\sup_{h\in\mathcal{M}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon^{\star}/4\right\\}$
$\displaystyle\left\\{\max\limits_{i\in\mathcal{J}}\sup_{h\in\mathcal{M}_{i}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon^{\star}/8\right\\}\subset\left\\{\max_{\mathcal{M}\in\text{
Max
}\mathbb{C}(\mathcal{H})}\sup_{h\in\mathcal{M}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon^{\star}/8\right\\},$

which yields

$\displaystyle\mathbb{P}$
$\displaystyle\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}\geq\epsilon^{\star}/2\right)$
$\displaystyle\leq\sum_{j=1}^{m}\sum_{\mathcal{M}\in\text{ Max
}\mathbb{C}(\mathcal{H})}\mathbb{P}\left(\sup_{h\in\mathcal{M}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon^{\star}/8\right)+\mathbb{P}\left(\sup_{h\in\mathcal{M}}\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}>\epsilon^{\star}/4\right)$
$\displaystyle\leq m\sum_{\mathcal{M}\in\text{ Max
}\mathbb{C}(\mathcal{H})}\left[B_{N,\epsilon^{\star}/8}(d_{VC}(\mathcal{M}))+\hat{B}_{N,\epsilon^{\star}/4}(d_{VC}(\mathcal{M}))\right]$
$\displaystyle\leq m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[B_{N,\epsilon^{\star}/8}(d_{VC}(\mathbb{C}(\mathcal{H})))+\hat{B}_{N,\epsilon^{\star}/4}(d_{VC}(\mathbb{C}(\mathcal{H})))\right],$
(7.4)

in which the last inequality follows from the fact that both
$\hat{B}_{N,\epsilon^{\star}/4}$ and $B_{N,\epsilon^{\star}/8}$ are increasing
functions, and
$d_{VC}(\mathbb{C}(\mathcal{H}))=\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}d_{VC}(\mathcal{M})$.
The result follows from Proposition 3.1 since

$\\{L(\hat{\mathcal{M}})\neq
L(\mathcal{M}^{\star})\\}\subset\left\\{\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}\geq\epsilon^{\star}/2\right\\}.$

If the almost sure convergences (3.4) hold, then

$\hat{L}(\mathcal{M})\xrightarrow[N\to\infty]{\text{a.s.}}L(\mathcal{M})$
(7.5)

for all $\mathcal{M}\in\mathbb{C}(\mathcal{H})$, since, if
$L(h)=\hat{L}^{(j)}(h)=L_{\mathcal{D}_{N}}^{(j)}(h)$ for all $j=1,\dots,m$ and
$h\in\mathcal{H}$, then $\hat{L}(\mathcal{M})=L(\mathcal{M})$ for all
$\mathcal{M}\in\mathbb{C}(\mathcal{H})$. Observe that

$\displaystyle\left\\{\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}\text{\textbar}L(\mathcal{M})-\hat{L}(\mathcal{M})\text{\textbar}=0\right\\}\subset\left\\{\hat{\mathcal{M}}=\mathcal{M}^{\star}\right\\},$
(7.6)

since, if the estimated risk $\hat{L}$ is equal to the out-of-sample risk $L$,
then the definitions of $\hat{\mathcal{M}}$ and $\mathcal{M}^{\star}$
coincide. As the probability of the event on the left hand-side of (7.6)
converges to one if (7.5) is true, we conclude that, if (3.4) hold, then
$\hat{\mathcal{M}}$ converges to $\mathcal{M}^{\star}$ with probability one. ∎

###### Proof of Theorem 3.4.

We need to show that (3.4) holds in these instances. For any $\epsilon>0$, by
Corollary A.12,

$\displaystyle\mathbb{P}\left(\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}\max_{j}\sup\limits_{h\in\mathcal{M}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon\right)\leq\sum_{j=1}^{m}\mathbb{P}\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L_{\mathcal{D}_{N}^{(j)}}(h)-L(h)\text{\textbar}>\epsilon\right)$
$\displaystyle\leq m\
8\exp\left\\{d_{VC}(\mathcal{H})\left(1+\ln\frac{N_{j}}{d_{VC}(\mathcal{H})}-N_{j}\frac{\epsilon^{2}}{32C^{2}}\right)\right\\}$

in which $N_{j}$ is the size of the $j$-th training sample. By the inequality
above, and Borel-Cantelli Lemma [9, Theorem 4.3], the first convergence in
(3.4) holds. The second convergence holds since the inequality above is also
true, but with $L_{\mathcal{D}_{N}^{(j)}}$ and $N_{j}$ interchanged by
$\hat{L}^{(j)}$ and $\hat{N}_{j}$, the empirical risk and size of the $j$-th
validation sample. ∎

###### Proof of Theorem 3.5.

We first note that

$\displaystyle\mathbb{P}$
$\displaystyle\left(\sup\limits_{h\in\mathcal{\hat{M}}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\right)=\mathbb{E}\Bigg{(}\mathbb{P}\left(\sup\limits_{h\in\mathcal{\hat{M}}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\text{\textbar}\mathcal{\hat{M}}\right)\Bigg{)}$
$\displaystyle=\sum_{i\in\mathcal{J}}\mathbb{P}\left(\sup\limits_{h\in\mathcal{\hat{M}}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\text{\textbar}\mathcal{\hat{M}}=\mathcal{M}_{i}\right)\mathbb{P}(\mathcal{\hat{M}}=\mathcal{M}_{i})$
$\displaystyle=\sum_{i\in\mathcal{J}}\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}_{i}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\text{\textbar}\mathcal{\hat{M}}=\mathcal{M}_{i}\right)\mathbb{P}(\mathcal{\hat{M}}=\mathcal{M}_{i}).$
(7.7)

Fix $\mathcal{M}\in\mathbb{C}(\mathcal{H})$ with
$\mathbb{P}(\mathcal{\hat{M}}=\mathcal{M})>0$. We claim that

$\displaystyle\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\text{\textbar}\mathcal{\hat{M}}=\mathcal{M}\right)=\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\right).$

Indeed, since $\tilde{\mathcal{D}}_{M}$ is independent of $\mathcal{D}_{N}$,
the event

$\left\\{\sup_{h\in\mathcal{M}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\right\\}$

is independent of $\\{\mathcal{\hat{M}}=\mathcal{M}\\}$, as the former depends
solely on $\tilde{\mathcal{D}}_{M}$, and the latter solely on
$\mathcal{D}_{N}$. Hence, by applying bound $\eqref{bound_theoremBC}$ to each
positive probability in the sum (7.1), we obtain that

$\displaystyle\mathbb{P}\left(\sup\limits_{h\in\mathcal{\hat{M}}}\text{\textbar}L_{\tilde{\mathcal{D}}_{M}}(h)-L(h)\text{\textbar}>\epsilon\right)$
$\displaystyle\leq\sum_{i\in\mathcal{J}}B_{M,\epsilon}^{I}(d_{VC}(\mathcal{M}_{i}))\mathbb{P}(\mathcal{\hat{M}}=\mathcal{M}_{i})$
$\displaystyle=\mathbb{E}\left(B_{M,\epsilon}^{I}(d_{VC}(\mathcal{\hat{M}}))\right)\leq
B_{N,\epsilon}^{I}(d_{VC}(\mathbb{C}(\mathcal{H}))),$

as desired, in which the last inequality follows from the fact that
$B_{M,\epsilon}^{I}$ is an increasing function and
$d_{VC}(\mathbb{C}(\mathcal{H}))=\max_{\mathcal{M}\in\mathbb{C}(\mathcal{H})}d_{VC}(\mathcal{M})$.

The bound for type II estimation error may be obtained similarly, since

$\displaystyle\mathbb{P}$
$\displaystyle\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{\hat{M}}})>\epsilon\right)=\mathbb{E}\Bigg{(}\mathbb{P}\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{\hat{M}}})>\epsilon\text{\textbar}\mathcal{\hat{M}}\right)\Bigg{)}$
$\displaystyle=\sum_{i\in\mathcal{J}}\mathbb{P}\left(L(\hat{h}_{\mathcal{\hat{M}}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{\hat{M}}})>\epsilon\text{\textbar}\mathcal{\hat{M}}=\mathcal{M}_{i}\right)\mathbb{P}(\mathcal{\hat{M}}=\mathcal{M}_{i})$
$\displaystyle=\sum_{i\in\mathcal{J}}\mathbb{P}\left(L(\hat{h}_{\mathcal{M}_{i}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{M}_{i}})>\epsilon\text{\textbar}\mathcal{\hat{M}}=\mathcal{M}_{i}\right)\mathbb{P}(\mathcal{\hat{M}}=\mathcal{M}_{i})$
$\displaystyle=\sum_{i\in\mathcal{J}}\mathbb{P}\left(L(\hat{h}_{\mathcal{M}_{i}}^{\tilde{\mathcal{D}}_{M}})-L(h^{\star}_{\mathcal{M}_{i}})>\epsilon\right)\mathbb{P}(\mathcal{\hat{M}}=\mathcal{M}_{i}),$

and $B^{II}_{M,\epsilon}(d_{VC}(\mathcal{M}_{i}))$ is a bound for the
probabilities inside the sum by (3.5). The assertion that types I and II
estimation errors are asymptotically zero when
$d_{VC}(\mathbb{C}(\mathcal{H}))<\infty$ is immediate from the established
bounds. ∎

###### Proof of Theorem 3.6.

We first show that

$\displaystyle\mathbb{P}\left(L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})>\epsilon\right)\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})\text{\textbar}>(\epsilon\vee\epsilon^{\star})/2\right).$
(7.8)

If $\epsilon\leq\epsilon^{\star}$ then, by the inclusion of events (7.2) in
the proof of Proposition 3.1, we have that

$\displaystyle\left\\{\max\limits_{i\in\mathcal{J}}\text{\textbar}\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})\text{\textbar}<(\epsilon\vee\epsilon^{\star})/2\right\\}\subset\left\\{L(\hat{\mathcal{M}})=L(\mathcal{M}^{\star})\right\\}\subset\left\\{L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})<\epsilon\right\\},$
(7.9)

since $L(h^{\star}_{\hat{\mathcal{M}}})=L(\hat{\mathcal{M}})$ and
$L(h^{\star}_{\mathcal{M}^{\star}})=L(\mathcal{M}^{\star})$, so (7.8) follows
in this case.

Now, if $\epsilon>\epsilon^{\star}$ and
$\max\limits_{i\in\mathcal{J}}\text{\textbar}\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})\text{\textbar}<\epsilon/2$,
then

$\displaystyle L(\hat{\mathcal{M}})-L(\mathcal{M}^{\star})$
$\displaystyle=[L(\hat{\mathcal{M}})-\hat{L}(\mathcal{M}^{\star})]-[L(\mathcal{M}^{\star})-\hat{L}(\mathcal{M}^{\star})]$
$\displaystyle\leq[L(\hat{\mathcal{M}})-\hat{L}(\hat{\mathcal{M}})]-[L(\mathcal{M}^{\star})-\hat{L}(\mathcal{M}^{\star})]$
$\displaystyle\leq\epsilon/2+\epsilon/2=\epsilon,$

in which the first inequality follows from the fact that the minimum of
$\hat{L}$ is attained at $\hat{\mathcal{M}}$, and the last inequality follows
from
$\max\limits_{i\in\mathcal{J}}\text{\textbar}\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})\text{\textbar}<\epsilon/2$.
Since
$L(\hat{\mathcal{M}})-L(\mathcal{M}^{\star})=L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})$,
we also have the inclusion of events

$\displaystyle\left\\{\max\limits_{i\in\mathcal{J}}\text{\textbar}\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})\text{\textbar}<(\epsilon\vee\epsilon^{\star})/2\right\\}\subset\left\\{L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})<\epsilon\right\\},$
(7.10)

when $\epsilon>\epsilon^{\star}$. From (7.9) and (7.10) follows (7.8), as
desired.

Substituting $\epsilon^{\star}$ by $\epsilon\vee\epsilon^{\star}$ in (7.1) we
obtain

$\displaystyle\mathbb{P}$
$\displaystyle\left(\max\limits_{i\in\mathcal{J}}\text{\textbar}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})\text{\textbar}\geq(\epsilon\vee\epsilon^{\star})/2\right)\leq$
$\displaystyle m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[B_{N,(\epsilon\vee\epsilon^{\star})/8}(d_{VC}(\mathbb{C}(\mathcal{H})))+\hat{B}_{N,(\epsilon\vee\epsilon^{\star})/4}(d_{VC}(\mathbb{C}(\mathcal{H})))\right].$
(7.11)

The result follows combining (7.8) and (7.1). ∎

###  7.2. Results of Section 4

###### Proof of Theorem 4.3.

We claim that

$1-\delta<\frac{\hat{L}(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}<1+\delta,\
\forall i\in\mathcal{J}\implies\max\limits_{i\in\mathcal{J}}\
\text{\textbar}\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})\text{\textbar}<\frac{\epsilon^{\star}}{2}.$
(7.12)

Indeed, the left-hand side of (7.12) implies

$\begin{cases}L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})<\frac{\epsilon^{\star}L(\mathcal{M}_{i})}{2\max\limits_{i\in\mathcal{J}}L(\mathcal{M}_{i})}<\frac{\epsilon^{\star}}{2}\\\
\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})<\frac{\epsilon^{\star}L(\mathcal{M}_{i})}{2\max\limits_{i\in\mathcal{J}}L(\mathcal{M}_{i})}<\frac{\epsilon^{\star}}{2}\\\
\end{cases}\ \forall i\in\mathcal{J},$

as desired. In particular, it follows from inclusion (7.2) in the proof of
Proposition 3.1 that

$\mathbb{P}\left(L(\hat{\mathcal{M}})\neq
L(\mathcal{M}^{\star})\right)\leq\mathbb{P}\left(\min\limits_{i\in\mathcal{J}}\frac{\hat{L}(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\leq
1-\delta\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\frac{\hat{L}(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\geq
1+\delta\right)$ (7.13)

hence it is enough to bound both probabilities on the right-hand side of the
expression above.

The first probability in (7.13) may be written as

$\displaystyle\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{L(\mathcal{M}_{i})-\hat{L}(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\geq\delta\right)\leq\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{L(\mathcal{M}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})}{L(\mathcal{M}_{i})}\geq\delta\right),$
(7.14)

in which the inequality follows from a union bound. Since
$x\mapsto\frac{x-\alpha}{x}$ is increasing, and $L(\mathcal{M}_{i})\leq
L(\hat{h}^{(j)}_{i})$ for every $j=1,\dots,m$, each probability in (7.14) is
bounded by

$\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{L(\hat{h}^{(j)}_{i})-\hat{L}^{(j)}(\hat{h}^{(j)}_{i})}{L(\hat{h}^{(j)}_{i})}\geq\delta\right)\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup\limits_{h\in\mathcal{M}_{i}}\
\frac{\text{\textbar}L(h)-\hat{L}^{(j)}(h)\text{\textbar}}{L(h)}\geq\delta\right).$
(7.15)

We turn to the second probability in (7.13) which can be written as

$\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{\hat{L}(\mathcal{M}_{i})-L(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\geq\delta\right)\leq\sum_{j=1}^{m}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{\hat{L}^{(j)}(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\geq\delta\right),$
(7.16)

in which again the inequality follows from a union bound. In order to bound
each probability in (7.16) we intersect its event with

$\max\limits_{i\in\mathcal{J}}\frac{L(\hat{h}_{i}^{(j)})}{L(\mathcal{M}_{i})}\leq\frac{1}{1-\delta}\iff\max\limits_{i\in\mathcal{J}}\frac{L(\hat{h}_{i}^{(j)})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\leq\delta,$

and its complement, to obtain

$\displaystyle\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{\hat{L}^{(j)}(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\geq\delta\right)\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\frac{L(\hat{h}_{i}^{(j)})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\delta\right)$
$\displaystyle+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\left(\frac{L(\hat{h}_{i}^{(j)})}{L(\mathcal{M}_{i})}\right)\frac{\hat{L}^{(j)}(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\delta,\max\limits_{i\in\mathcal{J}}\frac{L(\hat{h}_{i}^{(j)})}{L(\mathcal{M}_{i})}\leq\frac{1}{1-\delta}\right)$
$\displaystyle\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\frac{L(\hat{h}_{i}^{(j)})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\delta\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{\hat{L}^{(j)}(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\delta(1-\delta)\right)$
$\displaystyle\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup\limits_{h\in\mathcal{M}_{i}}\frac{\text{\textbar}L_{\mathcal{D}_{N}}^{(j)}(h)-L(h)\text{\textbar}}{L(h)}\geq\frac{\delta}{2}\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{\hat{L}^{(j)}(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\delta(1-\delta)\right)$
(7.17)

in which the last inequality follows from Lemma A.21.

It remains to bound the second probability in (7.2). We have that it is equal
to

$\displaystyle\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{\hat{L}^{(j)}(\hat{h}^{(j)}_{i})-L(\hat{h}^{(j)}_{i})+L(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\delta(1-\delta)\right)$
$\displaystyle\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{\hat{L}^{(j)}(\hat{h}^{(j)}_{i})-L(\hat{h}^{(j)}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\frac{\delta(1-\delta)}{2}\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\
\frac{L(\hat{h}^{(j)}_{i})-L(\mathcal{M}_{i})}{L(\hat{h}_{i}^{(j)})}\geq\frac{\delta(1-\delta)}{2}\right)$
$\displaystyle\leq\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup\limits_{h\in\mathcal{M}_{i}}\
\frac{\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}}{L(h)}\geq\frac{\delta(1-\delta)}{2}\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup\limits_{h\in\mathcal{M}_{i}}\
\frac{\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}}{L(h)}\geq\frac{\delta(1-\delta)}{4}\right),$
(7.18)

in which the last inequality follows again from Lemma A.21. From (7.13-7.2),
follows that

$\displaystyle\mathbb{P}\left(L(\hat{\mathcal{M}})\neq
L(\mathcal{M}^{\star})\right)\leq$ $\displaystyle
2\sum_{j=1}^{m}\Bigg{[}\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup\limits_{h\in\mathcal{M}_{i}}\
\frac{\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}}{L(h)}\geq\frac{\delta(1-\delta)}{2}\right)+$
$\displaystyle\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\sup\limits_{h\in\mathcal{M}_{i}}\
\frac{\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}}{L(h)}\geq\frac{\delta(1-\delta)}{4}\right)\Bigg{]}$
$\displaystyle\leq 2\sum_{j=1}^{m}\sum_{\mathcal{M}\in\text{ Max
}\mathbb{C}(\mathcal{H})}\Bigg{[}\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\
\frac{\text{\textbar}\hat{L}^{(j)}(h)-L(h)\text{\textbar}}{L(h)}\geq\frac{\delta(1-\delta)}{2}\right)+$
$\displaystyle\mathbb{P}\left(\sup\limits_{h\in\mathcal{M}}\
\frac{\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}}{L(h)}\geq\frac{\delta(1-\delta)}{4}\right)\Bigg{]},$

in which the inequality holds by the same arguments as in (7.1), hence

$\mathbb{P}\left(L(\hat{\mathcal{M}})\neq L(\mathcal{M}^{\star})\right)\leq
2m\
\mathfrak{m}(\mathbb{C}(\mathcal{H}))\left[\hat{B}_{N,\frac{\delta(1-\delta)}{2}}(d_{VC}(\mathbb{C}(\mathcal{H})))+B_{N,\frac{\delta(1-\delta)}{4}}(d_{VC}(\mathbb{C}(\mathcal{H})))\right].$

If the almost sure convergences (4.4) hold, then
$L(h)=L_{\mathcal{D}_{N}}^{(j)}(h)=\hat{L}^{(j)}(h)$ for all $j$ and
$h\in\mathcal{H}$, and the definitions of $\mathcal{M}^{\star}$ and
$\hat{\mathcal{M}}$ coincide. ∎

###### Proof of Theorem 4.6.

We show that

$\displaystyle\mathbb{P}\left(L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})>\epsilon\right)\geq\mathbb{P}\left(\frac{L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})}{L(h_{\hat{\mathcal{M}}}^{\star})}>\frac{\epsilon}{L(\mathcal{M}^{\star})}\right),$
(7.19)

so from (7.8) and (7.12) will follow that

$\mathbb{P}\left(\frac{L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})}{L(h_{\hat{\mathcal{M}}}^{\star})}>\frac{\epsilon}{L(\mathcal{M}^{\star})}\right)\leq\mathbb{P}\left(\min\limits_{i\in\mathcal{J}}\frac{\hat{L}(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\leq
1-\delta^{\prime}\right)+\mathbb{P}\left(\max\limits_{i\in\mathcal{J}}\frac{\hat{L}(\mathcal{M}_{i})}{L(\mathcal{M}_{i})}\geq
1+\delta^{\prime}\right),$

and the result is then direct from the proof of Theorem 4.3. But (7.19) is
clearly true since

$\displaystyle\frac{L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})}{L(h_{\hat{\mathcal{M}}}^{\star})}>\frac{\epsilon}{L(\mathcal{M}^{\star})}\implies
L(h_{\hat{\mathcal{M}}}^{\star})-L(h^{\star})>\epsilon\frac{L(h_{\hat{\mathcal{M}}}^{\star})}{L(\mathcal{M}^{\star})}\geq\epsilon.$

∎

## Acknowledgments

D. Marcondes was funded by grant #2022/06211-2, São Paulo Research Foundation
(FAPESP), during the writing of this paper.

##  Appendix A Vapnik-Chervonenkis theory

In this appendix, we present the main ideas and results of classical Vapnik-
Chervonenkis (VC) theory, the stone upon which the results in this paper are
built. The presentation of the theory is a simplified merge of [34], [35],
[11] and [10], where the simplicity of the arguments is preferred over the
refinement of the bounds. Hence, we present results which support those in
this paper and outline the main ideas of VC theory, even though are not the
tightest available bounds. We omit the proofs, and note that refined versions
of the results presented here may be found at one or more of the references.

This appendix is a review of VC theory, except for novel results presented in
Section A.2.3 for the case of unbounded loss functions, where we obtain new
bounds for relative type I estimation error by extending the results in [10].
We start defining the shatter coefficient and VC dimension of a hypotheses
space under loss function $\ell$.

######  Definition A.1 (Shatter coefficient).

Let $\mathcal{G}=\\{I:\mathcal{Z}\mapsto\\{0,1\\}\\}$ be a set of binary
functions with domain $\mathcal{Z}$. The $N$-shatter coefficient of
$\mathcal{G}$ is defined as

$S(\mathcal{G},N)=\max\limits_{(z_{1},\dots,z_{N})\in\mathcal{Z}^{N}}\text{\textbar}\big{\\{}\big{(}I(z_{1}),\dots,I(z_{N})\big{)}:I\in\mathcal{G}\big{\\}}\text{\textbar},$

for $N\in\mathbb{Z}_{+}$, in which $\text{\textbar}\cdot\text{\textbar}$ is
the cardinality of a set.

######  Definition A.2 (Vapnik-Chervonenkis dimension).

Fixed a hypotheses space $\mathcal{H}$ and a loss function $\ell$, set

$\displaystyle C=\sup\limits_{\begin{subarray}{c}z\in\mathcal{Z}\\\
h\in\mathcal{H}\end{subarray}}\ell(z,h),$

in which $C$ can be infinity. Consider, for each $h\in\mathcal{H}$ and
$\beta\in(0,C)$, the binary function
$I(z;h,\beta)=\mathds{1}\\{\ell(z,h)\geq\beta\\}$, for $z\in\mathcal{Z}$, and
denote

$\displaystyle\mathcal{G}_{\mathcal{H},\ell}=\Big{\\{}I(\cdot;h,\beta):h\in\mathcal{H},\beta\in(0,C)\Big{\\}}.$

We define the shatter coefficient of $\mathcal{H}$ under loss function $\ell$
as

$S(\mathcal{H},\ell,N)\coloneqq S(\mathcal{G}_{\mathcal{H},\ell},N).$

The Vapnik-Chervonenkis (VC) dimension of $\mathcal{H}$ under loss function
$\ell$ is the greatest integer $k\geq 1$ such that
$S(\mathcal{H},\ell,k)=2^{k}$, and is denoted by $d_{VC}(\mathcal{H},\ell)$.
If $S(\mathcal{H},\ell,k)=2^{k}$, for all integer $k\geq 1$, we denote
$d_{VC}(\mathcal{H},\ell)=\infty$.

######  Remark A.3.

If there is no confusion about which loss function we are referring, or when
it is not of importance to our argument, we omit $\ell$ and denote the shatter
coefficient and VC dimension simply by $S(\mathcal{H},N)$ and
$d_{VC}(\mathcal{H})$. We note that if the hypotheses in $\mathcal{H}$ are
binary valued functions and $\ell$ is the simple loss function
$\ell((x,y),h)=\mathds{1}\\{h(x)\neq y\\}$, then
$\mathcal{H}=\mathcal{G}_{\mathcal{H},\ell}$, and its $N$-th shatter
coefficient is actually the maximum number of dichotomies that can be
generated by the functions in $\mathcal{H}$ with $N$ points.

###  A.1. Generalized Glivenko-Cantelli Problems

The main results of VC theory are based on a generalization of the Glivenko-
Cantelli Theorem, which can be stated as follows. Recall that
$\mathcal{D}_{N}=\\{Z_{1},\dots,Z_{N}\\}$ is a sequence of independent random
vectors with a same distribution $P(z)\coloneqq\mathbb{P}(Z\leq z)$, for
$z\in\mathcal{Z}\subset\mathbb{R}^{d}$, defined in a probability space
$(\Omega,\mathcal{S},\mathbb{P})$.

In order to easy notation, we assume, without loss of generality, that
$\Omega=\mathbb{R}^{d}$, $\mathcal{S}$ is the Borel $\sigma$-algebra of
$\mathbb{R}^{d}$, the random vector $Z$ is the identity $Z(\omega)=\omega$,
for $\omega\in\Omega$, and $\mathbb{P}$ is the unique probability measure such
that $\mathbb{P}(\\{\omega:\omega\leq z\\})=P(z)$, for all
$z\in\mathbb{R}^{d}$. Define

$\displaystyle
P_{\mathcal{D}_{N}}(z)\coloneqq\frac{1}{N}\sum_{i=1}^{N}\mathds{1}\\{Z_{i}\leq
z\\},$ $\displaystyle z\in\mathcal{Z}$

as the empirical distribution of $Z$ under sample $\mathcal{D}_{N}$.

The assertion of the theorem below is that of [11, Theorem 12.4]. Its bottom
line is that the empirical distribution of random variables converges
uniformly to $P$ with probability one.

######  Theorem A.4 (Glivenko-Cantelli Theorem).

Assume $d=1$ and $\mathcal{Z}=\mathbb{R}$. Then, for a fixed $\epsilon>0$ and
$N$ great enough,

$\mathbb{P}\left(\sup\limits_{z\in\mathbb{R}}\text{\textbar}P(z)-P_{\mathcal{D}_{N}}(z)\text{\textbar}>\epsilon\right)\leq
8(N+1)\exp\left\\{-N\frac{\epsilon^{2}}{32}\right\\}.$ (A.1)

Applying Borel-Cantelli Lemma [9, Theorem 4.3] to (A.1) yields

$\lim\limits_{N\to\infty}\sup\limits_{z\in\mathbb{R}}\text{\textbar}P(z)-P_{\mathcal{D}_{N}}(z)\text{\textbar}=0\text{
with probability one.}$

In other words, $P_{\mathcal{D}_{N}}$ converges uniformly almost surely to
$P$.

Theorem A.4 has the flavor of VC theory results: a rate of uniform convergence
of the empirical probability of a class of events to their real probability,
which implies the almost sure convergence. Indeed, letting
$\mathcal{S}^{\star}\subset\mathcal{S}$ be a class of events, that is not
necessarily a $\sigma$-algebra, and denoting

$\mathbb{P}_{\mathcal{D}_{N}}(A)=\frac{1}{N}\sum_{i=1}^{N}\mathds{1}\\{Z_{i}\in
A\\},$

as the empirical probability of event $A\in\mathcal{S}$ under sample
$\mathcal{D}_{N}$, the probability in (A.1) can be rewritten as

$\mathbb{P}\left(\sup\limits_{A\in\mathcal{S}^{\star}}\text{\textbar}\mathbb{P}(A)-\mathbb{P}_{\mathcal{D}_{N}}(A)\text{\textbar}>\epsilon\right),$
(A.2)

in which $\mathcal{S}^{\star}=\\{A_{z}:z\in\mathbb{R}\\}$ with
$A_{z}=\\{\omega\in\Omega:\omega\leq z\\}$. If probability (A.2) converges to
zero when $N$ tends to infinity for a class
$\mathcal{S}^{\star}\subsetneq\mathcal{S}$, we say there exists a partial
uniform convergence of the empirical measure to $\mathbb{P}$.

Observe that in (A.2) not only the class $\mathcal{S}^{\star}$ is fixed, but
also the probability measure $\mathbb{P}$, hence partial uniform convergence
is dependent on the class and the probability. Nevertheless, in a
distribution-free framework, such as that of learning (cf. Section 2), the
convergences of interest should hold for any data generating distribution,
which is the case, for example, of Glivenko-Cantelli Theorem, that presents a
rate of convergence (A.1) which does not depend on $P$, holding for any
probability measure and random variable $Z$. Therefore, once a class
$\mathcal{S}^{\star}$ of interest is fixed, partial uniform convergence should
hold for any data generating distribution, a problem which can be stated as
follows.

Let $\mathcal{P}$ be the class of all possible probability distributions of a
random variable with support in $\mathcal{Z}$, and let $\mathcal{S}^{\star}$
be a class of events. The generalized Glivenko-Cantelli problem (GGCP) is to
find a positive constant $a$ and a function
$b:\mathbb{Z}_{+}\mapsto\mathbb{R}_{+}$, such that
$\lim\limits_{N\to\infty}b(N)/\exp cN=0,\forall c>0$, satisfying, for $N$
great enough,555In the presentation of [34, Chapter 2] it is assumed that $b$
is a positive constant, not depending on sample size $N$. Nevertheless, having
$b$ as a function of $N$ of an order lesser than exponential does not change
the qualitative behavior of this convergence, that is, also guarantees the
almost sure converge due to Borel-Cantelli Lemma.

$\sup\limits_{P\in\mathcal{P}}\mathbb{P}\left(\sup\limits_{A\in\mathcal{S}^{\star}}\text{\textbar}\mathbb{P}(A)-\mathbb{P}_{\mathcal{D}_{N}}(A)\text{\textbar}>\epsilon\right)\leq
b(N)\exp\\{-a\epsilon^{2}N\\},$ (A.3)

in which $\mathbb{P}$ is to be understood as dependent on $P$, since it is the
unique probability measure on the Borel $\sigma$-algebra that equals $P$ on
the events $\\{\omega\in\Omega:\omega\leq z\\},z\in\mathbb{R}^{d}$. If the
events are of the form $A=\\{w\in\Omega:Z(w)\leq z\\},z\in\mathbb{R}$, then
(A.3) is equivalent to (A.1), although in the latter it is implicit that it
holds for any distribution $P$.

The investigation of GGCP revolves around deducing necessary and sufficient
conditions on the class $\mathcal{S}^{\star}$ for (A.3) to hold. We will study
these conditions in order to establish the almost sure convergence to zero of
type I estimation error (cf. (2.9)) when the loss function is binary, what may
be stated as a GGCP.

###  A.2. Convergence to zero of type I estimation error

####  A.2.1. Binary loss functions

Fix a hypotheses space $\mathcal{H}$, a binary loss function $\ell$, and
consider the class $\mathcal{S}^{\star}=\\{A_{h}:h\in\mathcal{H}\\}$, such
that $\mathds{1}\\{z\in
A_{h}\\}=\ell(z,h)\in\\{0,1\\},z\in\mathcal{Z},h\in\mathcal{H}$, that is, if
$z\in A_{h}$ the loss is one, and otherwise it is zero. For example, if
$Z=(X,Y)$, the hypotheses in $\mathcal{H}$ are functions from the range of $X$
to that of $Y$, and $\ell$ is the simple loss function, then $A_{h}$ may be
explicitly written as

$A_{h}=\\{\omega:h(X(\omega))\neq Y(\omega)\\}.$

In this instance, the probability in the left-hand side of (A.3) may be
written as

$\mathbb{P}\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}\mathbb{E}(\ell(Z,h))-\mathbb{E}_{\mathcal{D}_{N}}(\ell(Z,h))\text{\textbar}>\epsilon\right),$
(A.4)

in which $\mathbb{E}$ is expectation with respect to $\mathbb{P}$ and
$\mathbb{E}_{\mathcal{D}_{N}}$ is the empirical mean under $\mathcal{D}_{N}$.
With the notation of Section 2, this last probability equals

$\mathbb{P}\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}>\epsilon\right),$

the tail probability of type I estimation error in $\mathcal{H}$.

For each fixed $h\in\mathcal{H}$, we are comparing in (A.4) the mean of a
binary function with its empirical mean, so we may apply Hoeffding’s
inequality [18] to obtain

$\mathbb{P}\left(\text{\textbar}\mathbb{E}(\ell(Z,h))-\mathbb{E}_{\mathcal{D}_{N}}(\ell(Z,N))\text{\textbar}>\epsilon\right)\leq
2\exp\\{-2\epsilon^{2}N\\},$

from which follows a solution of type I estimation error GGCP when the
cardinality of $\mathcal{H}$ is finite, by applying an elementary union bound:

$\displaystyle\mathbb{P}\Bigg{(}\sup\limits_{h\in\mathcal{H}}\text{\textbar}\mathbb{E}(\ell(Z,h))-\mathbb{E}_{\mathcal{D}_{N}}(\ell(Z,N))\text{\textbar}>\epsilon\Bigg{)}$
$\displaystyle\leq\sum_{h\in\mathcal{H}}\mathbb{P}\left(\text{\textbar}\mathbb{E}(\ell(Z,h))-\mathbb{E}_{\mathcal{D}_{N}}(\ell(Z,N))\text{\textbar}>\epsilon\right)$
$\displaystyle\leq
2\text{\textbar}\mathcal{H}\text{\textbar}\exp\\{-2\epsilon^{2}N\\},$

what establishes the almost sure convergence to zero of type I estimation
error when $\mathcal{H}$ is finite and $\ell$ is binary.

In order to treat the case when $\mathcal{H}$ has infinitely many hypotheses,
we rely on a modification of Glivenko-Cantelli Theorem, which depends on the
shatter coefficient of a class $\mathcal{S}^{\star}\subset\mathcal{S}$ of
events in the Borel $\sigma$-algebra of $\mathbb{R}^{d}$, defined below.

######  Definition A.5.

Fix $\mathcal{S}^{\star}\subset\mathcal{S}$ and let

$\mathcal{G}_{\mathcal{S}^{\star}}=\\{h_{A}(z)=\mathds{1}\\{z\in
A\\}:A\in\mathcal{S}^{\star}\\}$

be the characteristic functions of the sets in $\mathcal{S}^{\star}$. We
define the shatter coefficient of $\mathcal{S}^{\star}$ as

$S(\mathcal{S}^{\star},N)\coloneqq S(\mathcal{G}_{\mathcal{S}^{\star}},N),$

in which $S(\mathcal{G}_{\mathcal{S}^{\star}},N)$ is the shatter coefficient
of $\mathcal{G}_{\mathcal{S}^{\star}}$ (cf. Definition A.1). From this
definition follows that

$d_{VC}(\mathcal{S}^{\star})=d_{VC}(\mathcal{G}_{\mathcal{S}^{\star}}).$

The shatter coefficient and VC dimension of a class $\mathcal{S}^{\star}$ are
related to the dichotomies this class can build with $N$ points by considering
whether a point is in each set or not. From a simple modification of the proof
of Theorem A.4 presented in [11, Theorem 12.4] follows a result due to [37].

######  Theorem A.6.

For any probability measure $\mathbb{P}$ and class of sets
$\mathcal{S}^{\star}\subset\mathcal{S}$, for fixed $N\in\mathbb{Z}$ and
$\epsilon>0$, it is true that

$\mathbb{P}\left(\sup\limits_{A\in\mathcal{S}^{\star}}\text{\textbar}\mathbb{P}(A)-\mathbb{P}_{\mathcal{D}_{N}}(A)\text{\textbar}>\epsilon\right)\leq
8S(\mathcal{S}^{\star},N)\exp\left\\{-N\frac{\epsilon^{2}}{32}\right\\}.$

From this theorem follows a bound for tail probabilities of type I estimation
error when $\ell$ is binary.

######  Corollary A.7.

Fix a hypotheses space $\mathcal{H}$ and a loss function
$\ell:\mathcal{Z}\times\mathcal{H}\mapsto\\{0,1\\}$. Let
$\mathcal{S}^{\star}=\\{A_{h}:h\in\mathcal{H}\\}$, with

$\mathds{1}\\{z\in A_{h}\\}=\ell(z,h),z\in\mathcal{Z},h\in\mathcal{H}.$

Then,

$\mathbb{P}\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}>\epsilon\right)\leq
8\ S(\mathcal{H},N)\exp\left\\{-N\frac{\epsilon^{2}}{32}\right\\},$ (A.5)

with

$S(\mathcal{H},N)\coloneqq S(\mathcal{S}^{\star},N).$

######  Remark A.8.

We remark that $S(\mathcal{S}^{\star},N)=S(\mathcal{G}_{\mathcal{H},\ell},N)$,
as defined in Definition A.2, when the loss $\ell$ is binary. Observe that
$\mathcal{S}^{\star}$ depends on $\ell$, although we omit the dependence to
easy notation.

The calculation of the quantities on the right-hand side of (A.5) is not
straightforward, since the shatter coefficient is not easily determined for
arbitrary $N$. Nevertheless, the shatter coefficient may be bounded by a
quantity depending on the VC dimension of $\mathcal{H}$. This is the content
of [34, Theorem 4.3].

######  Theorem A.9.

If $d_{VC}(\mathcal{H})<\infty$, then

$\ln S(\mathcal{H},N)\begin{cases}=N\ln 2,&\text{ if }N\leq
d_{VC}(\mathcal{H})\\\ \leq
d_{VC}(\mathcal{H})\left(1+\ln\frac{N}{d_{VC}(\mathcal{H})}\right),&\text{ if
}N>d_{VC}(\mathcal{H})\end{cases}.$

######  Remark A.10.

Theorem A.9 is true for any loss function $\ell$, not only binary.

Combining this theorem with Corollary A.7, we obtain the following result.

######  Corollary A.11.

Under the hypotheses of Corollary A.7 it holds

$\mathbb{P}\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}>\epsilon\right)\leq
8\
\exp\left\\{d_{VC}(\mathcal{H})\left(1+\ln\frac{N}{d_{VC}(\mathcal{H})}\right)-N\frac{\epsilon^{2}}{32}\right\\}.$
(A.6)

In particular, if $d_{VC}(\mathcal{H})<\infty$, not only (A.6) converges to
zero, but also

$\sup\limits_{h\in\mathcal{H}}\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}\xrightarrow[N\to\infty]{}0,$

with probability one by Borel-Cantelli Lemma.

From Corollary A.11 follows the convergence to zero of type I estimation error
when the loss function is binary and $d_{VC}(\mathcal{H})$ is finite. We now
extend this result to real-valued bounded loss functions.

####  A.2.2. Bounded loss functions

Assume the loss function is bounded, that is, for all $z\in\mathcal{Z}$ and
$h\in\mathcal{H}$,

$0\leq\ell(z,h)\leq C<\infty,$ (A.7)

for a positive constant $C\in\mathbb{R}_{+}$. Throughout this section, a
constant $C$ satisfying (A.7) is fixed.

For any $h\in\mathcal{H}$, by definition of Lebesgue-Stieltjes integral, we
have that

$L(h)=\int_{\mathcal{Z}}\ell(z,h)\
dP(z)=\lim\limits_{n\to\infty}\sum_{k=1}^{n-1}\frac{C}{n}\mathbb{P}\left(\ell(Z,h)>\frac{kC}{n}\right),$

recalling that $Z$ is a random variable with distribution $P$. In a same
manner, we may also write the empirical risk under $\mathcal{D}_{N}$ as

$L_{\mathcal{D}_{N}}(h)=\frac{1}{N}\sum_{i=1}^{N}\ell(Z_{i},h)=\lim\limits_{n\to\infty}\sum_{k=1}^{n-1}\frac{C}{n}\mathbb{P}_{\mathcal{D}_{N}}\left(\ell(Z,h)>\frac{kC}{n}\right),$

recalling that $\mathbb{P}_{\mathcal{D}_{N}}$ is the empirical measure
according to $\mathcal{D}_{N}$.

From the representation of $L$ and $L_{\mathcal{D}_{N}}$ described above, we
have that, for each $h\in\mathcal{H}$ fixed,

$\displaystyle\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}$
$\displaystyle=\text{\textbar}\lim\limits_{n\to\infty}\sum_{k=1}^{n-1}\frac{C}{n}\left(\mathbb{P}\left(\ell(Z,h)>\frac{kC}{n}\right)-\mathbb{P}_{\mathcal{D}_{N}}\left(\ell(Z,h)>\frac{kC}{n}\right)\right)\text{\textbar}$
$\displaystyle\leq\text{\textbar}\lim\limits_{n\to\infty}\sum_{k=1}^{n-1}\frac{C}{n}\sup\limits_{0\leq\beta\leq
C}\left(\mathbb{P}\left(\ell(Z,h)>\beta\right)-\mathbb{P}_{\mathcal{D}_{N}}\left(\ell(Z,h)>\beta\right)\right)\text{\textbar}$
$\displaystyle\leq\lim\limits_{n\to\infty}\sum_{k=1}^{n-1}\frac{C}{n}\sup\limits_{0\leq\beta\leq
C}\text{\textbar}\mathbb{P}\left(\ell(Z,h)>\beta\right)-\mathbb{P}_{\mathcal{D}_{N}}\left(\ell(Z,h)>\beta\right)\text{\textbar}$
$\displaystyle=C\sup\limits_{0\leq\beta\leq
C}\text{\textbar}\int_{\mathcal{Z}}\mathds{1}\\{\ell(z,h)>\beta\\}\
dP(z)-\frac{1}{N}\sum_{i=1}^{N}\
\mathds{1}\\{\ell(Z_{i},h)>\beta\\}\text{\textbar}.$

We conclude that

$\displaystyle\mathbb{P}\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L(h)-L_{\mathcal{D}_{N}(h)}\text{\textbar}>\epsilon\right)$
$\displaystyle\leq\mathbb{P}\left(\sup\limits_{\begin{subarray}{c}h\in\mathcal{H}\\\
0\leq\beta\leq
C\end{subarray}}\text{\textbar}\int_{\mathcal{Z}}\mathds{1}\\{\ell(z,h)>\beta\\}\
dP(z)-\frac{1}{N}\sum_{i=1}^{N}\
\mathds{1}\\{\ell(Z_{i},h)\\}\text{\textbar}>\frac{\epsilon}{C}\right).$

Since the right-hand side of the expression above is a GGCP with

$\mathcal{S}^{\star}=\\{\\{z\in\mathcal{Z}:\ell(z,h)>\beta\\}:h\in\mathcal{H},0\leq\beta\leq
C\\}$

and, recalling the definition of shatter coefficient of $\mathcal{H}$ under a
real-valued loss function $\ell$ (cf. Definition A.1), we note that

$\displaystyle S(\mathcal{G}_{\mathcal{H},\ell},N)=S(\mathcal{S}^{\star},N)$
hence $\displaystyle d_{VC}(\mathcal{H})=d_{VC}(\mathcal{S}^{\star})$

so a bound for the tail probabilities of type I estimation error when the loss
function is bounded follows immediately from Theorems A.6 and A.9.

######  Corollary A.12.

Fix a hypotheses space $\mathcal{H}$ and a loss function
$\ell:\mathcal{Z}\times\mathcal{H}\mapsto\mathbb{R}_{+}$, with
$0\leq\ell(z,h)\leq C$ for all $z\in\mathcal{Z},h\in\mathcal{H}$. Then,

$\mathbb{P}\left(\sup\limits_{h\in\mathcal{H}}\text{\textbar}L(h)-L_{\mathcal{D}_{N}}(h)\text{\textbar}>\epsilon\right)\leq
8\
\exp\left\\{d_{VC}(\mathcal{H})\left(1+\ln\frac{N}{d_{VC}(\mathcal{H})}\right)-N\frac{\epsilon^{2}}{32C^{2}}\right\\}.$
(A.8)