Abstract
Cross-validation is one of the most widely used tools for risk estimation and model selection in statistics and machine learning, yet its theoretical properties when embedded in a learning procedure remain insufficiently understood. This paper develops a general, distribution-free framework for learning via model selection with cross -validation risk estimation within classical statistical learning theory. We establish VC dimension-based deviation bounds for the entire learning pipeline, providing detailed proofs for both bounded and unbounded loss functions, the latter requiring a novel extension of existing results. A central focus of the analysis is how the structure of the collection of candidate models influences generalization. To this end, we introduce Learning Spaces as collections of candidate models equipped with a partial order whose inclusion structure reflects increasing model complexity. We show how Learning Spaces can be constructed from domain knowledge and analyze how such structural information increases generalization. The framework is illustrated through case studies and a simulation study in high-dimensional linear regression, comparing learning via model selection in two distinct Learning Spaces against ordinary least squares, LASSO, and ridge regression across scenarios of varying alignment between prior knowledge and the true target. The results demonstrate that, when the Learning Space is well-adapted to the target and an efficient search algorithm is employed, learning via model selection can outperform standard methods by orders of magnitude. Through theoretical insights and concrete examples, we provide guidance on selecting the family of candidate models based on domain knowledge to enhance the performance of model selection with cross-validation.
1 Introduction
In learning problems, properly choosing a hypotheses space is critical to achieving high generalization, which is more likely when it contains hypotheses with low risk and is of limited complexity relative to the sample size, so overfitting is avoided and low-risk hypotheses can be learned. Properly selecting a hypotheses space involves translating prior information and domain knowledge into properties that low-risk hypotheses should satisfy, and then designing a space containing hypotheses with these properties. This can be done, for example, by identifying invariances, such as a group invariance, associated with the learning problem and considering only hypotheses which respect them (Marcondes et al., 2024b).
If prior information was wrong or weak, or if it could not be properly converted into a relatively simple hypotheses space, then generalization may be low. In order to mitigate these issues, one may select the hypotheses space from data, in what is known in the literature as model selection (Ding et al., 2018; Massart, 2007; Raschka, 2018). In model selection, one fixes a collection \(\{\mathcal {M}_{1},\dots ,\mathcal {M}_{n}\}\) of hypotheses spaces, or models, and an empirical error \(\hat{L}(\mathcal {M}_{i})\) for each one, which is often given by an independent validation sample, cross-validation, or complexity penalization. A hypotheses space is selected by minimizing the empirical error, and a hypotheses is learned from it.
If the candidate models are nested, i.e., \(\mathcal {M}_{1} \subset \cdots \subset \mathcal {M}_{n}\), then a method based on the Structured Risk Minimization (SRM) Inductive Principle, in which the resubstitution error of the estimated hypotheses of \(\mathcal {M}_{i}\) is penalized by its complexity, may be applied to solve this problem (see Vapnik (2000), Chapter 4 for more details and Anguita et al. (2012) for an example). More generally, model selection may be performed by penalizing the resubstitution error by the complexity of each model, in both nested and non-nested frameworks (see Massart (2007) for an in-depth presentation of model selection by penalization and Koltchinskii (2001, 2008), Arlot and Bartlett (2011), Bartlett (2008) for more specific results). Moreover, the classical problem of variable selection (Guyon & Elisseeff, 2003; John et al., 1994) constitutes another framework for model selection, in which a partially ordered structured family of constrained hypotheses spaces is generated through the elimination of variables.
Although there is a rich literature about model selection, the methods usually have two shortcomings. First, the collection of candidate models is heuristically selected, and strong domain knowledge is not considered. For example, nested candidate models are selected due to their increasing complexity and not necessarily because their hypotheses have some properties that are believed to be satisfied by low-risk hypotheses. Second, even when domain knowledge is considered, the collection of candidate models does not have a rich structure that could be leveraged to enhance the computational efficiency and generalization of model selection. For example, a collection of nested models does not have as many algebraic properties as a Boolean lattice, which is isomorphic to the collection of candidate models in variable selection. Although variable selection is an example that considers domain knowledge and its collection of candidate models has a lattice structure, it is specific to problems in which low-risk hypotheses do not depend on all variables, and it cannot be readily adapted to other scenarios.
In this paper, we analyze how domain knowledge and prior information can be leveraged to increase generalization by learning via model selection. We focus on model selection with cross-validation risk estimation, in which a hypotheses is learned on the selected model with an independent sample or by reusing the sample used to select the model. We formalize model selection within the statistical learning framework and deduce insightful distribution-free deviation bounds for learning via model selection in this instance. These insights are then illustrated through case studies and a simulation study, in which practical ways of increasing generalization by incorporating domain knowledge into the family of candidate models are presented.
2 Background
The classical framework of Statistical Learning Theory, in the case of binary classification, is a triple \((\mathcal {H},\mathbb {A},\mathcal {D}_{N})\), composed of a set \(\mathcal {H}\) of functions \(h: \mathbb {R}^{d} \rightarrow \{0,1\},d \ge 1\), called hypotheses space, and a learning algorithm \(\mathbb {A}(\mathcal {H},\mathcal {D}_{N})\), which searches \(\mathcal {H}\) to minimize the classification error over a training sample \(\mathcal {D}_{N} = \{(X_{1},Y_{1}),\dots ,(X_{N},Y_{N})\}\) of a random vector (X, Y), with range \(\mathbb {R}^{d} \times \{0,1\}\) and unknown probability distribution P. We refer to Sect. 3 for more details about the general framework of statistical learning.
Let \(\ell (h(x),y) :=\mathbbm {1}\{h(x) \ne y\}\) be the 0–1 loss function. The risk of a hypotheses \(h \in \mathcal {H}\) is an expected value of the local loss \(\ell (h(x),y), x \in \mathbb {R}^{d}, y \in \{0,1\}\). If the expectation is the sample mean of \(\ell (h(x),y)\) under \(\mathcal {D}_{N}\), we have the empirical risk \(L_{\mathcal {D}_{N}}(h)\), while if the expectation of \(\ell (h(X),Y)\) is under the distribution P, we then have the out-of-sample risk \(L(h) = \mathbb {P}(h(X) \ne Y)\). A target hypotheses \(h^{\star } \in \mathcal {H}\) is such that its out-of-sample risk is minimum in \(\mathcal {H}\), i.e., \(L(h^{\star }) \le L(h), \forall h \in \mathcal {H}\), while an empirical risk minimization (ERM) hypotheses \(\hat{h}\) is such that its empirical risk is minimum, i.e., \(L_{\mathcal {D}_{N}}(\hat{h}) \le L_{\mathcal {D}_{N}}(h), \forall h \in \mathcal {H}\).
In this context, learning via model selection is a two-step framework in which first a model is selected from a collection of candidates, and then a hypotheses is learned on it. Fix a hypotheses space \(\mathcal {H}\), a collection of candidate subsets, or models,
and an empirical risk estimator \(\hat{L}: \mathbb {C}(\mathcal {H}) \mapsto \mathbb {R}_{+}\), which assigns to each candidate model 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})\):
Once a model is selected, one employs a data-driven algorithm \(\mathbb {A}\), for example empirical risk minimization under a training sample, to learn a hypotheses \(\hat{h}^{\mathbb {A}}_{\hat{\mathcal {M}}}\) in \(\hat{\mathcal {M}}\).
An intrinsic characteristic of model selection frameworks is a bias-variance trade-off, which is depicted in Fig. 1. On the one hand, when one selects from data a model \(\hat{\mathcal {M}}\) among the candidates to learn on, one 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 large, the learned hypotheses may not well generalize relative to \(h^{\star }\). We call this bias type III estimation error, as depicted in Fig. 1.
On the other hand, learning within \(\hat{\mathcal {M}}\) may have a smaller 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 Fig. 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 Fig. 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}})\) where \(\hat{h}^{\mathbb {A}}\) is obtained by learning on the whole space \(\mathcal {H}\) with algorithm \(\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 smaller than the one committed by learning on the whole space \(\mathcal {H}\), that is, \(L(\hat{h}^{\mathbb {A}}) - L(h^{\star })\).
In this paper, we study distribution-free asymptotics of learning via model selection, meaning bounding the estimation errors in Fig. 1. 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 and learning on \(\hat{\mathcal {M}}\) is performed with an independent sample. We briefly discuss the case in which the same sample that was used to selected \(\hat{\mathcal {M}}\) is reused to learn on it.
2.1 Related Work
Cross-validation techniques for risk estimation and model selection are widely used in statistics and machine learning, and their asymptotic behavior has been well studied. The asymptotic optimality of specific cross-validation methods has been studied in Andrews (1991), Li (1987), Dudoit and van der Laan (2005) and so-called oracle inequalities have been established for cross-validation methods in Van der Vaart et al. (2006), Lecué and Mitchell (2012). Moreover, some straightforward deviation-bounds in distribution-free scenarios can be found in Mohri et al. (2018, Chapter 4). However, the understanding of the theoretical properties of cross-validation is quite low in light of its widespread use. This fact has been noted by Austern and Zhou (2025), Maillard (2021), which study the asymptotics of cross-validation for specific classes of models. To the best of our knowledge, a systematic study of model selection with cross-validation risk estimation within a distribution-free framework has not been done before, and may bring some insights into the benefits of model selection and have an impact on practical applications.
In this paper, we apply some techniques that have been applied before in the context of model selection via complexity penalization. For instance, results in Mohri et al. (2018, Chapter 4) present deviation bounds for SRM depending on the VC dimension of the target model, as do ours. However, our results also depend on the minimum discrimination error, that is, informally, the difference between the risk of the target model and the second best.
We note that substantial work has been done in model selection in distribution dependent settings, especially for complexity penalization, as thoroughly presented in Massart (2007). In particular, we highlight (Mendelson et al., 2003), which, in a distribution-dependent framework, obtains insights about the effect of the complexity of the learned model on the generalization quality of learning via model selection. Distribution-dependent bounds are out of the scope of this paper, but the results presented here might be adapted to distribution-dependent scenarios, a topic we will leave for future studies.
Despite the rich literature about model selection, an important facet of it is rarely treated from a statistical perspective: how the family of candidate models should be chosen. This question, when addressed, is usually done so from a computational perspective by fixing a family which can be efficiently searched. In particular, how generalization can be increased by properly selecting a penalization is a highly studied topic, but how it can be increased by properly selecting the family of candidate models is not. This paper is especially concerned with this neglected topic and how to leverage domain knowledge to increase generalization.
2.2 Main Contributions
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 for the estimation errors 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 (Devroye et al., 1996; Vapnik, 1998) to learning via model selection, while to treat the case of unbounded loss functions, we apply and extend results of Cortes et al. (2019).
In Cortes et al. (2019), bounds for the tail probabilities of
are established for unbounded loss functions, for any \(\varsigma> 0\), in which \(L^{p}(h)\) is the p-norm of \(\ell (h(X),Y)\) and \(p> 1\) is such that \(\sup _{h \in \mathcal {H}} L^{p}(h) < \infty\). We extend this result to \(p = 1\) to obtain bounds for the relative type I estimation error
so that we can carry out an analysis of model selection with unbounded loss functions. The details about this extension are in Sect. A.2.3 in Appendix A.
We also define the Learning Spaces as a class of candidate models in which the partial order by inclusion reflects model complexity. In particular, we focus on Learning Spaces that have a lattice structure and formalize a way of defining them through Learning Space generators. We present some examples and discuss how the Learning Space can be modeled to reflect domain knowledge and prior information about the target hypotheses. We illustrate this through case studies and a simulation study comparing learning via model selection against benchmark methods across scenarios of varying domain knowledge alignment in classification and linear regression. We expect with the theoretical results and these concrete examples to guide practitioners and applied researchers on how to choose the family of candidate models based on domain knowledge to increase generalization.
2.3 Paper Structure
In Sect. 3, 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 Sects. 4 and 5, we establish deviation bounds for learning via model selection with an independent sample for bounded and unbounded loss functions, respectively. In Sect. 6, we briefly discuss learning via model selection by reusing. In Sect. 7, we introduce the Learning Spaces, discuss how they can be built based on prior information, and in Sect. 8 we present numerical simulations to study two concrete examples to better understand the effect on the generalization quality of quantities present in the established deviation-bounds. In particular, we discuss how domain knowledge can be leveraged to increase generalization by learning via model selection and briefly present considerations about computational aspects of learning via model selection. We discuss the main results and perspectives of this paper in Sect. 10. In Sect. 11, we present the proof of the results. To improve the accessibility of this paper to readers not familiar with VC theory, we present in Appendix A an overview of its main results that are used in this paper.
3 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 \ge 1\). Denote \(P(z) :=\mathbb {P}(Z \le z)\), in which \(\le\) is the component-wise partial order in \(\mathbb {R}^{d}\), 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 hypotheses \(h \in \mathcal {H}\) to explain a feature of point \(z \in \mathcal {Z}\). Denoting \(\ell _{h}(z) :=\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 hypotheses \(h \in \mathcal {H}\) is defined as
in which \(\mathbb {E}\) means expectation under \(\mathbb {P}\). We define the empirical risk on sample \(\mathcal {D}_{N}\) as
that is the empirical mean of \(\ell _{h}(Z)\).
In classification problems, when \(Z = (X,Y)\) with X taking values in \(\mathbb {R}^{d}\) and Y in a finite set of labels, the usual loss function is \(\ell _{h}((x,y)) = \mathbbm {1}\{h(x) \ne y\}\) when h is a function of x, so the risk is the respective classification error. In regression problems, when Y takes values in \(\mathbb {R}\) the loss function is the quadratic loss \(\ell _{h}((x,y)) = (h(x) - y)^2\) and the risk is the respective mean squared error. By considering, for example, the loss function as \(\ell _{h}(z) = - \log f(z|h)\) for a probability density function that depends on \(h \in \mathcal {H}\), the empirical risk is minus the log-likelihood and empirical risk minimization is equivalent to maximum likelihood.
We denote the set of target hypotheses of \(\mathcal {H}\) as
that are the hypotheses that minimize L in \(\mathcal {H}\), and the set of the target hypotheses of subsets of \(\mathcal {H}\) by
depending on the subset.
The set of hypotheses which minimize the empirical risk in \(\mathcal {H}\) is defined as
while the ones that minimize it in models are denoted by
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 hypotheses 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 (1) and (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 {|}\mathcal {J}\text {|} < \infty\), and assume that it covers \(\mathcal {H}\):
We define the VC dimension under loss function \(\ell\) of such a collection as
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 ) \le d_{VC}(\mathcal {H},\ell )\). In Appendix A, we review the main concepts of VC theory (Vapnik, 1998). In particular, 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 relevant 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}))\).
3.1 Model Risk Estimation
The risk of a model in \(\mathbb {C}(\mathcal {H})\) is defined as
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
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 hypotheses 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}\). We assume all training samples have a size \(N_{t}\) and the validation samples a size \(N_{v}\).
In order to exemplify the results obtained in this paper, we consider two estimators of the form (3), obtained with a validation sample and k-fold cross-validation, which we formally define in Sect. 11.1. When there is no need to specify which estimator of \(L(\mathcal {M})\) we are referring to, we simply denote \(\hat{L}(\mathcal {M})\) to mean an arbitrary estimator with form (3).
3.2 Target Model and Estimation Errors
The motivation for learning via model selection stems from a trade-off inherent to the models in \(\mathbb {C}(\mathcal {H})\): simpler models, e.g., those with lower VC dimension, tend to allow more accurate estimation, but at the risk of not containing a hypotheses that performs as well as the best one available in \(\mathcal {H}\). In this context, assume that \(\mathcal {H}\) is all we have to learn on, and we are not willing to consider any hypotheses 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 hypotheses \(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
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
be the equivalence classes which contain a target hypotheses of \(\mathcal {H}\), so their risk is minimum. We define the target model \(\mathcal {M}^{\star } \in {\mathbb {C}(\mathcal {H})}/{\sim }\) as
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 }\).
However, when learning on a model \(\hat{\mathcal {M}} \in \mathbb {C}(\mathcal {H})\) selected based on data, one commits three types of errors:
that we call types II, III, and IV estimation errorsFootnote 1, which are illustrated in Fig. 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 hypotheses \(h_{\hat{\mathcal {M}}}^{\star }\) of \(\hat{\mathcal {M}}\) with a target hypotheses \(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 hypotheses \(\hat{h}_{\hat{\mathcal {M}}}^{\mathbb {A}}\) of \(\hat{\mathcal {M}}\) and the loss of its target, assessing how much the estimated hypotheses varies from a target of \(\hat{\mathcal {M}}\), while type IV is the effective error committed, since it compares the estimated hypotheses 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 properties into account.
3.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 hypotheses on \(\hat{\mathcal {M}}\). In this section, we define \(\hat{\mathcal {M}}\) and two algorithms \(\mathbb {A}\) to learn on it.
3.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
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 (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}} :=\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
In particular, it is desired that the model learned by \(\mathbb {M}_{\mathbb {C}(\mathcal {H})}\) 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 (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
for \(\mathcal {M}_{i}, \mathcal {M}_{j} \in \mathbb {C}(\mathcal {H})\), which is a random \((\Omega ,\mathcal {S})\)-measurable equivalence relation. Let
be the classes in \({\mathbb {C}(\mathcal {H})}/{\hat{\sim }}\) with the least estimated risk. We call the classes in \(\hat{\mathcal {L}}\) the global minima of \(\mathbb {C}(\mathcal {H})\). Then, \(\mathbb {M}_{\mathbb {C}(\mathcal {H})}\) selects
the simplest class among the global minima.
3.3.2 Learning Hypotheses on \(\hat{\mathcal {M}}\)
Once \(\hat{\mathcal {M}}\) is selected, we need to learn hypotheses on it. In this paper, we focus on learning with an independent sample and briefly discuss learning by reusing, as follows.
Let \(\tilde{\mathcal {D}}_{M} = \{\tilde{Z}_{l}: 1 \le l \le M\}\) be a sequence of M independent and identically distributed random vectors with distribution P, independent of \(\mathcal {D}_{N}\). When learning with an independent sample, we consider
that are the hypotheses which minimize the empirical risk under \(\tilde{\mathcal {D}}_{M}\) on \(\hat{\mathcal {M}}\).
Another straightforward way of learning on \(\hat{\mathcal {M}}\) is to simply consider
that are the hypotheses which minimize the empirical error under \(\mathcal {D}_{N}\) on \(\hat{\mathcal {M}}\). We call this framework learning by reusing. Figure 2 summarizes these systematic frameworks of learning via model selection.
We define the type I estimation error as
which represents how well one can estimate the loss uniformly on \(\hat{\mathcal {M}}\) by the empirical risk under \(\tilde{\mathcal {D}}_{M}\) and \(\mathcal {D}_{N}\), respectively.
Remark 3.1
We assume that the suprema in (9) are \((\Omega ,\mathcal {S})\)-measurable, so it is meaningful to calculate probabilities of events which involve them. We also assume throughout this paper that these suprema, over any fixed \(\mathcal {M} \in \mathbb {C}(\mathcal {H}),\) are also \((\Omega ,\mathcal {S})\)-measurable.
3.4 Deviation Bounds and Main Results
In classical learning theory, or VC theory, there are two kinds of estimation errors, whose tail probabilities are
and
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 (11) 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 3.2 will be stated for unbounded loss functions in Sect. 5. In what follows, a.s. stands for almost sure convergence or convergence with probability one.
Proposition 3.2
Assume the loss function is bounded and fix a hypotheses space \(\mathcal {H}\) with \(d_{VC}(\mathcal {H}) < \infty\). There exist sequences \(\{B^{I}_{N,\epsilon }: N \ge 1\}\) and \(\{B^{II}_{N,\epsilon }: N \ge 1\}\) of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, such that
Furthermore, the following holds:
The sequences \(\{B^{I}_{N,\epsilon }: N \ge 1\}\) and \(\{B^{II}_{N,\epsilon }: N \ge 1\}\) are what we call the deviation bounds of learning via empirical risk minimization in \(\mathcal {H}\) and we refer to Appendix A.2 for explicit formulas for them. 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 functions.
In particular, it will follow that the established deviation bounds for the type IV estimation error of learning via model selection may be tighter than those 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 Sect. 7, we further discuss when this is the case and how domain knowledge can be leveraged to choose a class of candidate models in which learning via model selection may be, in general, better than learning via ERM in \(\mathcal {H}\).
In the following sections, we treat the cases of bounded and unbounded loss functions.
Remark 3.3
Throughout this paper, we assume that functions such as \(B_{N,\epsilon }^{I}(k)\) and \(B_{N,\epsilon }^{II}(k)\) are decreasing on \(\epsilon\) and N for k fixed.
Remark 3.4
The results of this paper for bounded loss functions hold for any distribution-free complexity, such that Proposition 3.2 remains true. In fact, the results hold by assuming the existence of bounds \(B_{N,\epsilon }^{I}(d(\mathcal {H}))\) and \(B_{N,\epsilon }^{II}(d(\mathcal {H}))\) for (10) and (11) depending on a complexity measure \(d(\mathcal {H})\). For instance, bounds based on the Rademacher and Gaussian complexities (Bartlett and Mendelson, 2002) or the fat-shattering dimension (Bartlett et al., 1994) could be considered. We stated the results for the VC-dimension to be consistent with the unbounded loss results, since in that case, we could only show that similar bounds hold for the VC dimension (cf. Proposition 5.2) by extending results in Cortes et al. (2019).
4 Learning via Model Selection with Bounded Loss Functions
In Sect. 4.1, we show the convergence of \(\hat{\mathcal {M}}\) to the target model \(\mathcal {M}^{\star }\) with probability one, and in Sect. 4.2 we establish deviation bounds for the estimation errors of learning via model selection when the loss function is bounded. From now on, we assume there exists a constant \(C> 0\) such that
In this section, we focus on learning with an independent sample and in Sect. 6 we briefly present analogous results for learning by reusing.
4.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 minima 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
The MDE is the minimum difference between the out-of-sample risk of a target hypotheses and the best hypotheses 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 best. The meaning of \(\epsilon ^{\star }\) is depicted in Fig. 3.
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})\) that does not contain a target hypotheses. If \(h^{\star } \cap \mathcal {M} \ne \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 because 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 4.1
Assume there exists \(\delta> 0\) such that
Then
Remark 4.2
Since there may exist \(\mathcal {M} \in \ \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 (12) guarantees only that the estimated risk of both \(\mathcal {M}\) and \(\mathcal {M}^{\star }\) is smaller 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 Fig. 3 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 (3). In this case, we may obtain a bound for (13) 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 3.2). These bounds also depend on the number of maximal models of \(\mathbb {C}(\mathcal {H})\), which are models in
i.e., models not contained in any element of \(\mathbb {C}(\mathcal {H})\) besides themselves. We denote
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 4.3
Assume the loss function is bounded. For each \(\epsilon> 0\), let \(\{B_{N,\epsilon }: N \ge 1\}\) and \(\{\hat{B}_{N,\epsilon }: N \ge 1\}\) be sequences of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, and such that
for all \(\mathcal {M} \in \mathbb {C}(\mathcal {H})\), 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,
in which m is the number of pairs considered to calculate (3). Furthermore, if
then
A bound for \(\mathbb {P}(L(\hat{\mathcal {M}}) \ne 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 3.2 by taking \(N = N_{t} + N_{v}\) the total of the training and validation samples, with both sample sizes tending to infinity. Analogously, we may obtain a bound when an independent validation sample is considered. This result is stated in the next theorem.
Theorem 4.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 }\).
Since \(B_{N,\epsilon }(k)\) and \(\hat{B}_{N,\epsilon }(k)\) are decreasing on \(\epsilon\) and N for k fixed, it follows from (14) that a tighter bound for \(\mathbb {P}(L(\hat{\mathcal {M}}) \ne L(\mathcal {M}^{\star }))\) is obtained if the training sample size is greater than the validation sample size (\(N_{t}> N_{v}\)) since the functions \(B_{N_{t},\epsilon ^{\star }/8}\) and \(\hat{B}_{N_{v},\epsilon ^{\star }/4}\) appear on the bound. Observe that this is the case in k-fold cross-validation.
Moreover, from this bound it follows that, with a fixed sample size, we can have a tighter bound for \(\mathbb {P}(L(\hat{\mathcal {M}}) \ne 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 (14), since the sample size is fixed and \(\epsilon ^{\star }\) is unknown.
4.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 4.5.
Theorem 4.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 \ge 1\}\) and \(\{B^{II}_{M,\epsilon }: M \ge 1\}\) of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, such that
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\),
and
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 \rightarrow \infty\).
Our definition of \(\mathcal {\hat{M}}\) ensures that it has 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 4.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 4.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 smaller if \(d_{VC}(\mathbb {C}(\mathcal {H})) \ll d_{VC}(\mathcal {H})\).
A bound for type III estimation error may be obtained using methods similar to those we employed to prove Theorem 4.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 } :=\max \{\epsilon ,\epsilon ^{\star }\}\) for any \(\epsilon> 0\).
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\),
In particular,
for any \(\epsilon> 0\).
Remark 4.7
Type III estimation error, and its bound presented in Theorem 4.6, do not depend on the algorithm \(\mathbb {A}\) employed to learn on \(\hat{\mathcal {M}}\), hence this theorem is true for both frameworks in Fig. 2, holding also when learning by reusing.
On the one hand, by definition of \(\epsilon ^{\star }\), if \(\epsilon < \epsilon ^{\star }\), then type III estimation error is smaller 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 4.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 smaller 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 4.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 4.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,
a bound for (17) is a direct consequence of Theorems 4.5 and 4.6.
Corollary 4.8
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\),
In particular,
for any \(\epsilon> 0\).
Comparing the bounds of Corollary 4.8 with those of type II estimation error of learning via ERM in \(\mathcal {H}\) for a sample size of \(N + M\) (cf. Proposition 3.2), we see that the former can be tighter. This is the case when the VC dimension of the maximal models is smaller than \(d_{VC}(\mathcal {H})\), \(\epsilon ^{\star }\) is large or \(d_{VC}(\mathcal {M}^{\star })\) is small and \(d_{VC}(\hat{\mathcal {M}}) \approx d_{VC}(\mathcal {M}^{\star })\) with high probability. This fact evidences that by properly modeling the set of candidate models, it may be possible to increase generalization without increasing the sample size. This fact will be further explored in Sects. 7 and 8. This relation between the bounds also holds for unbounded functions (cf. Corollary 5.7) and when learning by reusing (cf. Sect. 6).
5 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 (Foss et al., 2011). 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
in which \(L^{p}(h) :=\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 (Vapnik, 1998, Sect. 5.7) and is within the framework of Cortes et al. (2019). In this section, we again focus on learning with an independent sample and in Sect. 6 we present analogous results for learning by reusing.
Definition 5.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 \le 2\) such that \(\tau _{p} < \infty\), but \(\tau _{p} = \infty\) for all \(p> 2\);
-
Very heavy tails, if \(\tau _{p} = \infty\) for all \(p> 1\).
We assume that P has at most heavy tails, which means there exists a \(p> 1\), that can be less than 2, with
that is, P is in a class of distributions for which bound (18) holds. From now on, fix a \(p> 1\) and a \(\tau ^{\star }\) such that (18) holds.
Besides the constraint (18), we also assume that the loss function is greater or equal to one: \(\ell (z,h) \ge 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 add 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 adding 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, definingFootnote 2
we assume that
in which the first inequality should hold with probability one, for all possible samples \(\mathcal {D}_{N}\). Since \(L^{p}(h)\) is non-decreasing in p for each fixed h, (20) actually implies (18), so (20) is the non-trivial constraint in distribution P.
Although this is a deviation from the distribution-free framework, it is a mild constraint on distribution P. On the one hand, the condition on \(L^{p}\) is usually satisfied for distributions observed in real data (see Vapnik, 1998, Sect. 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:
in which algorithm \(\mathbb {A}\) depends on the estimation technique once \(\hat{\mathcal {M}}\) is selected.
In this section, we prove analogues of Theorems 4.3, 4.5 and 4.6. Before starting the study of the convergence of \(\hat{\mathcal {M}}\) to \(\mathcal {M}^{\star }\), we state a result analogous to Proposition 3.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 those of Cortes et al. (2019).
Proposition 5.2
Assume the loss function is unbounded and P is such that (20) holds. Fix a hypotheses space \(\mathcal {H}\) with \(d_{VC}(\mathcal {H}) < \infty\). There exist sequences \(\{B^{I}_{N,\epsilon }: N \ge 1\}\) and \(\{B^{II}_{N,\epsilon }: N \ge 1\}\) of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, such that
Furthermore, the following holds:
We refer to Appendix A.2.3 for explicit formulas for \(B^{I}_{N,\epsilon }(k)\) and \(B^{II}_{N,\epsilon }(k)\) in this case. In particular, the rate of convergence of \(B^{I}_{N,\epsilon }(k)\) and \(B^{II}_{N,\epsilon }(k)\) when \(N \rightarrow \infty\) depends on the value of p for which (18) holds, even though they converge to zero for all \(p> 1\).
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 their tightness, and tighter bounds may be readily obtained from the proofs.
5.1 Convergence to the Target Model
We start by showing a result similar to Theorem 4.3.
Theorem 5.3
Assume the loss function is unbounded and P is such that (20) holds. For each \(\epsilon> 0\), let \(\{B_{N,\epsilon }: N \ge 1\}\) and \(\{\hat{B}_{N,\epsilon }: N \ge 1\}\) be sequences of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, and such that
for all \(\mathcal {M} \in \mathbb {C}(\mathcal {H})\), 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,
in which m is the number of pairs considered to calculate (3) and
Furthermore, if
then
In this instance, a bound for \(\mathbb {P}(L(\hat{\mathcal {M}}) \ne 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 5.2 in a manner analogous to Theorem 4.4. We state the almost sure convergence in Theorem 5.4, whose proof is analogous to that of Theorem 4.4, and follows from Corollary A.16.
Theorem 5.4
Assume the loss function is unbounded and P is such that (20) holds. 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 }\).
5.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 Sect. 4.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 4.5. In fact, the proof of the following bounds is 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 5.5
Fix an unbounded loss function and assume P is such that (20) holds. 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 \ge 1\}\) and \(\{B^{II}_{M,\epsilon }: M \ge 1\}\) of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, such that
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\),
and
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 \rightarrow \infty\).
The convergence to zero of relative type III estimation error may be obtained, as in Theorem 4.6, by the methods used to prove Theorem 5.3. We state and prove this result, since its proof is slightly different from that of Theorem 4.6.
Theorem 5.6
Assume the premises of Theorem 5.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\),
in which
In particular,
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 5.5 and 5.6, and the following inequality
which is true since \(L(\hat{h}_{\mathcal {\hat{M}}}^{\tilde{\mathcal {D}}_{M}}) \ge L(h^{\star }_{\mathcal {\hat{M}}})\).
Corollary 5.7
Assume the premises of Theorems 5.3 and 5.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\),
with
In particular,
for any \(\epsilon> 0\).
6 Learning by Reusing
In this section, we present bounds for types I, II, and consequently IV, estimation errors for learning by reusing for bounded and unbounded loss functions. When learning by reusing, one is employing the same sample points to estimate \(\hat{\mathcal {M}}\) and to learn a hypotheses \(\hat{h}^{\mathcal {D}_{N}}_{\hat{\mathcal {M}}} \in \hat{\mathcal {M}}\) from it, so there is a dependence between types I and II estimation errors and the events \(\{\hat{\mathcal {M}} = \mathcal {M}\}, \mathcal {M} \in \mathbb {C}(\mathcal {H})\). For instance, the bounds for types I and II estimation errors in Theorem 4.5 depend on an equality (cf. (29) in the proof of Theorem 4.5) that does not hold when learning by reusing since
Conditioned on \(\{\hat{\mathcal {M}} = \mathcal {M}\}\), the distribution of each sample point \((X_{i},Y_{i}), i = 1,\dots ,N\), changes, and moreover these points are no longer independent, as they must satisfy \(\hat{\mathcal {M}} = \mathcal {M}\). Therefore, the argument of the proof of Theorem 4.5 does not hold in this instance.
Nevertheless, since \(\hat{\mathcal {M}}\) converges with probability one to \(\mathcal {M}^{\star }\) by Theorem 4.3, we may obtain a bound for types I and II estimation errors when learning by reusing, expressed in terms of the corresponding bounds on \(\mathcal {M}^{\star }\) and the rate of convergence of \(\hat{\mathcal {M}}\) to \(\mathcal {M}^{\star }\).
Theorem 6.1
Fix a bounded loss function. Assume we are learning by reusing and that, for each \(\epsilon> 0\), there exist sequences \(\{B^{I}_{N,\epsilon }: N \ge 1\}\) and \(\{B^{II}_{N,\epsilon }: N \ge 1\}\) of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, such that
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\),
and
If conditions (15) of Theorem 4.3 are satisfied, both probabilities above converge to zero when \(N \rightarrow \infty\).
Remark 6.2
Theorem 6.1 also holds when learning with an independent sample by exchanging \(\mathcal {D}_{N}\) with \(\tilde{\mathcal {D}}_{M}\).
From inequality (17) and the bound for type III estimation error established in Theorem 4.6, which also holds when learning by reusing (cf. Remark 4.7), it follows that the tail probability of type IV estimation error converges to zero as N tends to infinity, a result analogous to Corollary 4.8.
For unbounded loss functions, when learning by reusing, a result analogous to Theorem 6.1, together with Theorem 5.3 and a result analogous to Corollary 5.7, will imply the convergence of the estimation errors to zero. We state this result without proof.
Theorem 6.3
Fix an unbounded loss function and assume P is such that (20) holds. Assume we are learning by reusing and that, for each \(\epsilon> 0\), there exist sequences \(\{B^{I}_{N,\epsilon }: N \ge 1\}\) and \(\{B^{II}_{N,\epsilon }: N \ge 1\}\) of positive real-valued increasing functions with domain \(\mathbb {Z}_{+}\) satisfying
for all \(\epsilon> 0\) and \(k \in \mathbb {Z}_{+}\) fixed, such that
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\),
and
If conditions (21) of Theorem 5.3 are satisfied, both probabilities above converge to zero when \(N \rightarrow \infty\).
Remark 6.4
Bounds for the probabilities in Theorems 6.1 and 6.3 of the form \(B^{\cdot }_{N,\epsilon }(k) + \mathbb {P}(d_{VC}(\hat{\mathcal {M}})> k), 1 \le k < d_{VC}(\mathbb {C}(\mathcal {H})),\) could be obtained by conditioning the respective probability on the events \(\{d_{VC}(\hat{\mathcal {M}}) \le k\}\) and the complement \(\{d_{VC}(\hat{\mathcal {M}})> k\}\) instead of \(\{\hat{\mathcal {M}} = \mathcal {M}^\star \}\) and \(\{\hat{\mathcal {M}} \ne \mathcal {M}^\star \}\) in the proof of these theorems (cf. Sect. 11.4). In principle, this quantity could be minimized in k to obtain tighter bounds.
Remark 6.5
Another approach for learning via model selection is considering a combination of the hypotheses used in the computation of cross-validation errors as the learned hypotheses. This is also a case that cannot be easily analyzed in the general, distribution-free framework, as the same sample is reused both to select the model and to learn on it. Its study in specific cases is an interesting topic for future research.
7 Increasing Generalization by Learning via Model Selection
In this section, we analyze concrete examples to better understand how generalization may be increased by learning via model selection. In particular, we illustrate the role of \(\epsilon ^{\star }\), \(d_{VC}(\mathcal {M}^{\star })\) and \(d_{VC}(\mathbb {C}(\mathcal {H}))\) on the generalization and how it can be increased by inserting prior information about \(h^{\star }\) into the family of candidate models.
In Sects. 7.1 and 7.2, we present a class of candidate models in which the partial order by inclusion reflects the complexity of the models. We call this class Learning Spaces and focus our analyses on a subclass that has a lattice structure. In Sect. 8.1, we analyze a worst-case scenario of learning a classifier with finite domain, focusing on the effect of \(\epsilon ^{\star }\) and \(d_{VC}(\mathbb {C}(\mathcal {H}))\) on the generalization. In Sect. 8.2, we simulate a typical case in linear regression in high dimension, focusing on the effect of \(d_{VC}(\mathcal {M}^{\star })\) and prior information about \(h^{\star }\) on generalization. In Sect. 9, we further discuss how generalization may be increased by inserting domain knowledge into the family of candidate models.
7.1 Learning Spaces
Let \(\mathbb {L}(\mathcal {H}) :=\{\mathcal {M}_{i}: i \in \mathcal {J} \subset \mathbb {Z}_{+}\}\) be a finite subset of the power set of \(\mathcal {H}\), i.e., \(\mathbb {L}(\mathcal {H}) \subset \mathcal {P}(\mathcal {H})\) and \(|\mathcal {J}| < \infty\). We say that the partially ordered set (poset) \((\mathbb {L}(\mathcal {H}),\subset )\) is a Learning Space if
-
(i)
\(\bigcup \limits _{i \in \mathcal {J}} \mathcal {M}_{i} = \mathcal {H}\)
-
(ii)
\(\mathcal {M}_{1}, \mathcal {M}_{2} \in \mathbb {L}(\mathcal {H})\) and \(\mathcal {M}_{1} \subset \mathcal {M}_{2}\) implies \(d_{VC}(\mathcal {M}_{1}) < d_{VC}(\mathcal {M}_{2})\).
Learning Spaces are families of candidate models that cover \(\mathcal {H}\) and such that any element \(\mathcal {M} \in \mathbb {L}(\mathcal {H})\) is complexity maximal in the sense that there does not exist \(\mathcal {M}' \in \mathbb {L}(\mathcal {H}), \mathcal {M}' \ne \mathcal {M},\) such that \(d_{VC}(\mathcal {M}') = d_{VC}(\mathcal {M})\) and \(\mathcal {M}' \subset \mathcal {M}\). This condition guarantees that if \(\mathcal {M}_{1} \subset \mathcal {M}_{2}\), then the complexity of \(\mathcal {M}_{2}\) is greater than that of \(\mathcal {M}_{1}\). This implies that the poset \((\mathbb {L}(\mathcal {H}),\subset )\) reflects the complexity of its models. We note that one could choose \(\{\mathcal {M}_{1},\dots ,\mathcal {M}_{n}\}\) without thinking of it as a decomposition of a hypotheses space \(\mathcal {H}\). Nevertheless, if condition (ii) is satisfied, then it would be a Learning Space of \(\mathcal {H} = \cup _{i} \mathcal {M}_{i}\), so taking \(\mathcal {H}\) as this union, the only non-trivial condition is (ii).
Learning Spaces are not unique, i.e., there are multiple subsets of \(\mathcal {P}(\mathcal {H})\) which are Learning Spaces, and the main class of Learning Spaces are the Lattice Learning Spaces, which have a complete lattice structure. A complete lattice \((\mathbb {L}(\mathcal {H}),\subset ,\wedge ,\vee ,\mathcal {O},\mathcal {I})\) is the poset \((\mathbb {L}(\mathcal {H}),\subset )\) with binary relations meet (\(\wedge\)) and join (\(\vee\)) representing the greatest lower bound and least upper bound of two elements. A lattice is complete if every subset of \(\mathbb {L}(\mathcal {H})\) has a meet and a join in \(\mathbb {L}(\mathcal {H})\). In particular, a complete lattice has a least element (\(\mathcal {O}\)) and greatest element (\(\mathcal {I}\)) that are the meet and join of \(\mathbb {L}(\mathcal {H})\), so \(Max \ \mathbb {L}(\mathcal {H}) = \{\mathcal {I}\}\) and \(\mathfrak {m}(\mathbb {L}(\mathcal {H})) = 1\).
Remark 7.1
Although we consider the VC-dimension, other complexity measures of hypotheses spaces could be used to define the Learning Spaces, such as the fat-shattering dimension (Bartlett et al., 1994) and the Rademacher and Gaussian complexities (Bartlett and Mendelson, 2002). However, these are complexity measures that depend on the data-generating distribution, and hence could lead to collections of models that are Learning Spaces for some distributions, but not for others. Nevertheless, we note that the value of the VC dimension is not important to the algebraic aspect of the Learning Space definition, but only the fact that it increases when we consider nested models. Hence, any other complexity measure such that this increase is also observed for the chosen poset of models, under the data generating distribution, would generate a valid Learning Space.
The first step in building a Learning Space is fixing an algebraic parametric representation of the hypotheses in \(\mathcal {H}\). The algebraic structure of \((\mathbb {L}(\mathcal {H}),\subset )\) may be defined from the learning model and algebraic parametric representation fixed, in the following manner. Let \((\mathcal {F},\le )\) be a poset, in which \(\mathcal {F}\) is an arbitrary set with finite cardinality. Moreover, let \(\mathcal {R}: \mathcal {F} \mapsto Im(\mathcal {R}) \subset \mathcal {P}(\mathcal {H})\) be a lattice isomorphism from set \((\mathcal {F},\le )\) to \((Im(\mathcal {R}),\subset )\), a subset of the power set of \(\mathcal {H}\) partially ordered by inclusion. This means that \(\mathcal {R}\) is bijective, and if \(a,b \in \mathcal {F}, a \le b\), then \(\mathcal {R}(a) \subset \mathcal {R}(b)\), so \(\mathcal {R}\) preserves the partial order \(\le\) on \(\mathcal {F}\) as the partial order on \(Im(\mathcal {R})\) given by inclusion. Then, if
-
(i)
\(\bigcup \limits _{a \in \mathcal {F}} \mathcal {R}(a) = \mathcal {H}\) and
-
(ii)
\(a,b \in \mathcal {F}, a \le b,\) implies \(d_{VC}(\mathcal {R}(a)) < d_{VC}(\mathcal {R}(b))\),
we may define \(\mathbb {L}(\mathcal {H}) :=Im(\mathcal {R})\) as a Learning Space of \(\mathcal {H}\). We call isomorphisms which satisfy these conditions Learning Space generators. Since the generator \(\mathcal {R}\) is an isomorphism, it preserves properties of \((\mathcal {F},\le )\), hence, for instance, by applying \(\mathcal {R}\) to a complete lattice we obtain a Lattice Learning Space.
A Learning Space is completely defined by a triple \((\mathcal {F},\le ,\mathcal {R})\), in which the elements of \(\mathcal {F}\) may be interpreted as sets of parameters which describe a subset of hypotheses, i.e., the hypotheses in \(\mathcal {R}(a), a \in \mathcal {F},\) are represented by the parameters a, so that, in particular, \(\mathcal {F}\) generates a parametric representation of the functions in \(\mathcal {H}\). For this reason, we call \((\mathcal {F},\le )\) a parametric poset of \(\mathcal {H}\). Therefore, in general, to build a Learning Space of \(\mathcal {H}\) we apply a generator to a parametric poset of its hypotheses.
7.2 Examples of Learning Spaces
We present some examples of Learning Spaces completely defined by a triple \((\mathcal {F},\le ,\mathcal {R})\).
Example 1
(Variable Selection) Assume that \(\mathcal {H}\) is a space of functions with domain \(\mathcal {X} \subset \mathbb {R}^{d}, d> 1\). Let \(\mathcal {F} = \mathcal {P}(\{1,\dots ,d\})\) be the power set of \(\{1,\dots ,d\}\) partially ordered by inclusion, so that \((\mathcal {F},\subset ,\cap ,\cup ,\emptyset ,\{1,\dots ,d\})\) is a complete Boolean lattice. Consider the Learning Space generator \(\mathcal {R}: \mathcal {F} \mapsto Im(\mathcal {R}) \subset \mathcal {P}(\mathcal {H})\) given by
in which \(a = \{a_{1},\dots ,a_{j}\} \in \mathcal {F}\) and \(x = (x_{1},\dots ,x_{d}) \equiv _{a} z = (z_{1},\dots ,z_{d})\) if, and only if, \(x_{a_{i}} = z_{a_{i}}\) for \(i = 1,\dots ,j\), so \(\mathcal {R}(a)\) contains the hypotheses which depend solely on variables in a. The lattice isomorphism \(\mathcal {R}\) satisfies condition (i) and often satisfies (ii), as in many applications the VC dimension is an increasing function of the number of variables, so \(Im(\mathcal {R})\) is often a Learning Space. This is the usual collection of candidate models for variable selection problems. \(\square\)
Example 2
(Partition Lattice) Let \(\mathcal {X}\) be an arbitrary set with \(\text {|}\mathcal {X}\text {|} < \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) = \mathbbm {1}\{h(x) \ne y\}\), it follows that \(L(h) = \mathbb {P}(h(X) \ne Y)\) is the classification error.
Denote by \(\Pi = \{\pi : \pi \text { is a partition of } \mathcal {X}\}\) the set of all partitions of \(\mathcal {X}\). A partition \(\pi = \{p_{1},\dots ,p_{k}\}\) is a collection of subsets of \(\mathcal {X}\), called blocks or parts, such that
Each partition \(\pi \in \Pi\) induces an equivalence relation on \(\mathcal {X}\), with equivalence between points in the same block of partition \(\pi\):
Consider in \(\Pi\) the partial order \(\le\) defined as
for \(\pi _{1}, \pi _{2} \in \Pi\), which turns it into a complete lattice \((\Pi ,\le ,\wedge ,\vee ,\{\mathcal {X}\},\mathcal {X})\). This partial order is equivalent to \(\pi _{1} \le \pi _{2}\) if, and only if, for every \(p_{2} \in \pi _{2}\) there exists a \(p_{1} \in \pi _{1}\) such that \(p_{2} \subset p_{1}\). See Fig. 4 for an example of a partition lattice. By applying the generator \(\mathcal {R}: \mathcal {F} \mapsto Im(\mathcal {R}) \subset \mathcal {P}(\mathcal {H})\) given by
for \(\pi \in \Pi\), we obtain the partition lattice Learning Space \(\mathbb {L}(\mathcal {H}) :=Im(\mathcal {R})\). The set \(\mathcal {R}(\pi )\) is formed by all hypotheses which classify the points inside a block of \(\pi\) in the same category; those are the hypotheses which respect \(\pi\). This lattice is indeed a Learning Space since \(\mathcal {H} \in \mathbb {L}(\mathcal {H})\) and \(d_{VC}(\mathcal {M}_{\pi }) = |\pi |\). In this case, the parameters of the functions \(h \in \mathcal {H}\) are the elements in their domain \(\mathcal {X}\), in contrast, for example, to the variables they depend on, as in Example 1.
For any distribution P, \(d_{VC}(\mathcal {M}^{\star }) \le 2\) since \(h^{\star } \in \mathcal {M}_{\pi ^{\star }}\) in which \(\pi ^{\star } = \{\{x: h^{\star }(x) = 0\},\{x: h^{\star }(x) = 1\}\}\) is the partition generated by \(h^{\star }\). \(\square\)
Example 3
(Linear Regression) Let \(\mathcal {H}\) be given by the linear functions in \(\mathbb {R}^{d}, d \ge 1\):
in which \(x = (x_{1},\dots ,x_{d}) \in \mathbb {R}^{d}\) and \(h_{a}\) is the function indexed by its parameters \(a = (a_{0},\dots ,a_{d}) \in \mathbb {R}^{d+1}\). Assume \(Z = (X,Y)\) and \(\mathcal {Z} = \mathbb {R}^{d} \times \mathbb {R}\), and consider the square loss function \(\ell ((x,y),h) = (h(x) - y)^{2}\), so \(L(h) = \mathbb {E}[(h(X) - Y)^{2}]\) is the mean squared error.
Denoting \(\mathcal {A} = \{1,\dots ,d\}\), we consider two distinct Learning Space generators: from the Boolean lattice \((\mathcal {P}(\mathcal {A}),\subset ,\cap ,\cup ,\emptyset ,\mathcal {A})\) and from the partition lattice \((\Pi _{\mathcal {A}},\le ,\wedge ,\vee ,\{\mathcal {A}\},\mathcal {A})\) of \(\mathcal {A}\), in which \(\mathcal {P}(\mathcal {A})\) is the power set of \(\mathcal {A}\) and \(\Pi _{\mathcal {A}}\) is the set of all partitions of \(\mathcal {A}\). The partition lattice is represented in Fig. 4 for \(d = 4\).
Define \(\mathcal {R}_{1}: \mathcal {P}(\mathcal {A}) \mapsto \mathcal {P}(\mathcal {H})\) as
for \(A \in \mathcal {P}(\mathcal {A})\) as a variable selection generator, and define \(\mathcal {R}_{2}: \Pi _{\mathcal {A}} \mapsto \mathcal {P}(\mathcal {H})\) as
for \(\pi \in \Pi _{\mathcal {A}}\) as a generator that constrains parameters to be equal within equivalence classes of \(\mathcal {A}\). Both \(\mathcal {R}_{1}, \mathcal {R}_{2}\) clearly satisfy (i) and (ii). Therefore, these lattice isomorphisms generate two distinct Lattice Learning Spaces for the same hypotheses space \(\mathcal {H}\). Isomorphic Learning Spaces also apply to the hypotheses space of linear classifiers. \(\square\)
8 Numerical Experiments
This section presents two numerical studies designed to illustrate the theoretical results established in Sects. 4 to 6. The first study (Sect. 8.1) considers learning a classifier on a finite domain using the partition lattice Learning Space, and focuses on the role of the maximum discrimination error \(\epsilon ^\star\) and the VC dimension \(d_{VC}(\mathbb {C}(\mathcal {H}))\) in determining when learning via model selection outperforms ERM.
The second study (Sect. 8.2) considers high-dimensional linear regression with two distinct Learning Spaces, the variable selection Learning Space and the partition lattice Learning Space, and compares learning via model selection against ERM, LASSO and ridge regression across four scenarios that span a wide range of alignment between domain knowledge and the true target function, from perfect to complete misalignment. All simulations are implemented in R (R Core Team, 2026) and the code will be made available. The simulations of Sect. 8.2 were performed using nodes equipped with Intel Xeon Platinum 8274 processors (3.2 GHz, 48 cores per node).
The four regression scenarios in Sect. 8.2 are explicitly designed to instantiate the theoretical decomposition of the generalization error into types II, III, and IV estimation errors (cf. Sect. 3.2 and Fig. 1). When the Learning Space is well-adapted to the target, i.e., the target model is simple, and the search algorithm successfully locates a low-complexity good model, the theory predicts, via Corollaries 4.8 and 5.7, substantially lower Type IV error than ERM, since the bound depends on \(d_{VC}(\hat{\mathcal {M}})\) rather than \(d_{VC}(\mathcal {H})\). The simulations evidence this quantitatively. When the search fails, Type III error is large and performance degrades, irrespective of the theoretical adaptation of the Learning Space, illustrating the binding role of the optimization algorithm as a practical constraint.
Together, the two studies address the practical dimension of the framework. Section 8.1 clarifies under what conditions on \(\epsilon ^\star\) and sample size model selection is most beneficial relative to ERM. Section 8.2 illustrates that the theoretical gains are realizable in high-dimensional settings (\(d \in \{100, 500, 1000\}\) variables), provided the prior information encoded in the Learning Space is at least partially aligned with the true target and a proper search of the Learning Space can be performed.
8.1 Partition Lattice Learning Space for classification
In this section, we compare learning via ERM on the whole hypotheses space with learning via model selection in the partition lattice Learning Space of Example 2. We consider the worst-case distribution for a fixed value of \(\epsilon ^{\star }\), that is, when the joint distribution of (X, Y) has maximum conditional entropy. Clearly, this happens when \(\mathbb {P}(X = x) = 1/|\mathcal {X}|\) for all \(x \in \mathcal {X} = \{1,\dots ,K\}\) and
There are \(2^{|\mathcal {X}|}\) distributions that satisfy (22) and we choose the one such that \(\mathbb {P}(Y = 1|X = x)> \mathbb {P}(Y = 0|X = x)\) if x is odd and \(\mathbb {P}(Y = 1|X = x) < \mathbb {P}(Y = 0|X = x)\) if x is even. For any value of \(\epsilon ^{\star }\), \(h^{\star }(x)\) equals one for x odd and zero for x even, and \(\mathcal {M}^{\star } = \mathcal {M}_{\pi }\) in which \(\pi\) is the partition of even and odd numbers with \(d_{VC}(\mathcal {M}^{\star }) = 2\).
For each \(\epsilon ^{\star } \in \{0.0025,0.005,0.0125,0.025,0.05,0.075,0.1\}\) we simulate 1, 000 samples of total size \(n = M + N \in \{16,32,64,128,256\}\) considering \(\mathcal {X} = \{1,\dots ,8\}\) and the worst-case distribution described above. The distributions considered are in Table 2 in Appendix B. For each sample, we learn by ERM with the whole sample, learn via model selection with an independent sample by dividing the sample into 50% - 50% for training \((N = n/2)\) and independent \((M = n/2)\) sample, and learn via model selection by reusing. Model risks are estimated by k-fold cross-validation with \(k = 4\), and when the solution is not unique, i.e., \(\hat{\mathcal {M}}\) is an equivalence class with more than one model, learning is performed by minimizing the respective empirical risk in the union of the models in \(\hat{\mathcal {M}}\).
Figure 5 presents for each scenario the number of simulated samples in which the risk of the estimated hypotheses via model selection was greater, lesser or equal to the risk of the ERM hypotheses. We see that for all \(\epsilon ^{\star }\), the number of samples in which learning via model selection is better than ERM decreases with n, illustrating that learning via model selection is more beneficial for small sample sizes. For all sample sizes, the number of samples in which learning via model selection is better decreases with \(\epsilon ^{\star }\), and for large values of \(\epsilon ^{\star }\) (\(\ge 0.05\)) learning via model selection is as good as via ERM in the majority of cases for mild to large sample sizes. Finally, learning via model selection by reusing is, in general, slightly better than with an independent sample relative to learning via ERM.
The results in Fig. 5 illustrate the effect of \(\epsilon ^{\star }\) in the generalization of learning via model selection. On the one hand, if \(\epsilon ^{\star }\) is too large, the learning problem is actually quite easy and model selection is not necessary. For example, the conditional distribution for \(\epsilon ^{\star } = 0.1\) is such that \(\mathbb {P}(Y = 1|X = 1) = 0.9\) (cf. Table 2) so we do not need many samples with \(X = 1\) to figure out that \(h^{\star }(1) = 1\). Therefore, with or without model selection, we can properly learn \(h^{\star }\).
On the other hand, when \(\epsilon ^{\star }\) is small, the learning problem becomes harder. For example, the conditional distribution for \(\epsilon ^{\star } = 0.0025\) is such that \(\mathbb {P}(Y = 1|X = 1) = 0.51\) so more samples with \(X = 1\) are needed to establish that \(h^{\star }(1) = 1\). However, if we could somehow figure out that, say, \(h^{\star }(1) = h^{\star }(3)\) then we could pool the samples with \(X = 1\) and \(X = 3\) together to figure the value of \(h^{\star }\) at these points. Therefore, by knowing a partition of the domain with points in the same block having the same value of \(h^{\star }\), we need fewer samples in the independent sample to properly learn. In the limit case, when the partition selected is that of the even and odd numbers, learning with an independent sample will be performed in a (good) hypotheses space with VC dimension 2 and few samples will suffice.
Figure 6 presents the average bias of the ERM hypotheses and types II, III, and IV estimation errors over the 1,000 simulated samples for each case. For \(\epsilon ^{\star } \ge 0.05\), the average estimation errors decrease with the sample size, while the average bias of the ERM hypotheses decreases with n for all \(\epsilon ^{\star } \ge 0.005\). For \(\epsilon ^{\star } \le 0.025\), the average of the estimation errors first increases with n, then remains stable, until attaining a sample size in which it rapidly decreases, especially for learning with an independent sample. In particular, the average of the bias of the ERM hypotheses is, in general, greater than the average of type IV estimation error for small sample sizes.
The increase in the estimation errors from sample size 16 to 32 can be explained by the fact that with 16 samples the model of the constant functions, related to the partition \(\pi = \{\{\mathcal {X}\}\}\), which has VC dimension 1, is often selected: between 22–33% for small values of \(\epsilon ^{\star }\) (see Fig. 11 in Appendix B). When this model is selected, then the learned hypotheses has a risk equal to \(L(h^{\star }) + 4\epsilon ^{\star }\), that is, the risk of the constant hypotheses. When more samples are available, models with VC dimension 2 are selected more often and the risk can be as large as \(L(h^{\star }) + 8\epsilon ^{\star }\), so it is reasonable that the average of estimation errors slightly increases.
The abrupt decrease of the error when n increases, especially for type II estimation error, is due to a phase transition which is a feature of, for example, the bounds in Theorems 4.6 and 5.6 and Corollaries 4.8 and 5.7, because of the term \(\epsilon \vee \epsilon ^{\star }\). When there are not enough samples to properly estimate the risks with a precision of \(\epsilon ^{\star }/2\) with high probability, it is unlikely that a model close, in the type III estimation error sense, to \(\mathcal {M}^{\star }\) is selected. But once there are enough samples for type III estimation error to be low, learning improves and types II and IV estimation errors decrease significantly.
We end this section by analyzing the case of learning via model selection, considering only the models with VC dimension 2 in the partition lattice Learning Space. This family of candidate models has VC dimension two and \(2^{7} - 1\) maximal elements, since all of its elements are maximal, but it has the same \(\epsilon ^{\star }\) as the whole partition lattice Learning Space. The comparison with learning via ERM for this case is in Fig. 7. The performance of model selection relative to learning via ERM improves substantially for this family of candidate models when compared to the whole partition lattice. For instance, learning via ERM is better than learning via model selection by reusing in no more than 8.4% of the simulated samples for all sample sizes, and learning via model selection is strictly better in as many as two thirds of the samples for small sample sizes. However, as \(\epsilon ^{\star }\) and the sample size increase, learning via ERM becomes as good as learning via model selection, since the learning problem becomes easier to solve. More details about this simulation can be found in Appendix B.
8.2 Learning Spaces for linear regression
In this section, we compare learning via ERM on the whole hypotheses space (i.e., ordinary least squares), LASSO (Tibshirani, 1996) and ridge (Hoerl and Kennard, 1970) regression with learning via model selection in linear regression leveraging domain knowledge. We consider two kinds of prior information about \(h^{\star }: \mathbb {R}^{d} \rightarrow \mathbb {R}\): that it is sparse and that the effect of some of the d input variables is the same. Denoting \(h^{\star }(x) = a_{0}^{\star } + \sum _{i=1}^{d} a_{i}^{\star } x_{i}\), sparsity means that \(a_{i}^{\star } = 0\) for i in a subset of \(\{1,\dots ,d\}\) and two input variables \(x_{i}, x_{j}\) having the same effect on the output means that \(a_{i}^{\star } = a_{j}^{\star }\).
We simulate four cases, combining two levels of sparsity, namely, sparse when only \(\ell :=d/10\) of the d input variables are active and dense when all are active, with two levels of homogeneity of effect, namely, unequal when the active variables have pairwise distinct coefficients and grouped when the active variables are split into few groups that share a common coefficient. Table 1 presents the four target hypotheses considered \(h^{\star }_{1},\dots ,h^{\star }_{4}\), each with intercept \(a_{0}^{\star } = 0\).
We consider a typical scenario for each target hypotheses. Let X be a random vector uniformly distributed in \([-1,1]^{d}\) and define, for \(i = 1,\dots ,4\), the random variable \(Y^{(i)} = h^{\star }_{i}(X) + \varepsilon\), in which \(\varepsilon\) is independent of X and has mean zero and variance \(\sigma ^{2}> 0\). Denote the distribution of \((X,Y^{(i)})\) as \(P_{i}\), so \(h^{\star }_{i}\) is the target hypotheses under \(P_{i}\). Considering the square loss function, the risk of each target hypotheses is \(L_{i}(h_{i}^{\star }) = \sigma ^{2}\), in which \(L_{i}\) is the expected loss under \(P_{i}\).
First, we analyze the variable selection Learning Space (VSLS) generated by \(\mathcal {R}_{1}\) from Example 3. Under \(P_{1}\) and \(P_{2}\), the target hypotheses are sparse depending only on the first \(\ell\) variables, so \(\mathcal {M}_{1}^{\star ,(1)} = \mathcal {M}_{1}^{\star ,(2)} = \mathcal {R}_{1}(\{1,\dots ,\ell \})\) is formed by the linear functions that depend only on the first \(\ell\) input variables. Under \(P_{3}\) and \(P_{4}\), the target hypotheses are dense, so \(\mathcal {M}_{1}^{\star ,(3)} = \mathcal {M}_{1}^{\star ,(4)} = \mathcal {H} = \mathcal {R}_{1}(\{1,\dots ,d\})\).
Now consider the partition lattice Learning Space (PLLS) generated by \(\mathcal {R}_{2}\) from Example 3. Under \(P_{1}\), the zero coefficients are grouped, but, since the active coefficients are pairwise distinct, they cannot be grouped, hence \(\mathcal {M}^{\star ,(1)}_{2} = \mathcal {R}_{2}(\{\{1\},\dots ,\{\ell \},\{\ell +1,\dots ,d\}\})\). Under \(P_{2}\), the active variables share a common coefficient, hence can be grouped, and \(\mathcal {M}^{\star ,(2)}_{2} = \mathcal {R}_{2}(\{\{1,\dots ,\ell \},\{\ell +1,\dots ,d\}\})\). Under \(P_{3}\), the odd and even indexed variables each share a common coefficient, so \(\mathcal {M}^{\star ,(3)}_{2} = \mathcal {R}_{2}(\{\{i: i \text { odd}\},\{i: i \text { even}\}\})\). Finally, under \(P_{4}\), all coefficients are pairwise distinct, so \(\mathcal {M}^{\star ,(4)}_{2} = \mathcal {H} = \mathcal {R}_{2}(\{\{1\},\dots ,\{d\}\})\).
We observe that the variable selection Learning Space is especially adapted to scenarios 1 (S1) and 2 (S2) in which the target is sparse, while the partition lattice Learning Space is particularly adapted to the scenarios 2 and 3 (S3) in which the coefficients can be grouped into two groups, and partially adapted to S1 in which the variables can be grouped into \(\ell + 1\) groups. In these cases, the target model has low complexity, which, theoretically, can lead to better performance compared with ERM on the whole hypotheses space as long as these sets can be properly learned. Scenario 4 (S4) is dense and the variables cannot be grouped, hence neither Learning Space provides any theoretical gain over ERM since the target model is the whole hypotheses space.
From a prior knowledge perspective, if one knows that the problem is sparse (S1 and S2) then the variable selection Learning Space should be chosen; if, additionally, it is known that many of the active variables have equal effect (S2), then the partition lattice Learning Space should be considered. Now, if one only knows that there are few groups of variables with the same effect (S2 and S3), then the partition lattice Learning Space should be considered. If the prior information is inaccurate, and the true target function is actually dense and the effects cannot be grouped (S4), then both Learning Spaces should perform poorly compared with ERM.
8.2.1 Simulation Details
For each \(d \in \{100,500,1000\}\), with \(\ell = d/10\), and each scenario, we consider three values of \(\sigma\), called easy, moderate and hard: \(\sigma = \sqrt{0.1/3m^{2}}\), \(\sigma = \sqrt{1/3m^{2}}\) and \(\sigma = \sqrt{10/3m^{2}}\), respectively for increasing difficulty, in which \(m \in \{\ell ,d\}\) is the number of active variables. As \(\sigma\) increases, the signal-to-noise ratio decreases and the problem becomes harder. The value \(1/3m^{2}\) was selected as a scale comparable to the value of \(\epsilon ^{\star }\) for the VSLS in all scenarios.
For each \((d,\sigma )\) combination we simulate 96 replications, and for each replication we generate two independent samples of size \(N = M \in \big \{\lceil 4(d+5)/3\rceil ,\, \lceil 5(d+5)/3\rceil ,\, \lceil 6(d+5)/3\rceil \big \}\) from \(P_{i}\), considering a Gaussian distribution for \(\varepsilon\). For each pair of samples, we learn by ERM, LASSO and ridge regression with the pooled sample of size N + M, and by model selection with an independent sample in both the variable selection and partition lattice Learning Spaces, in which the candidate model is selected by minimizing the k-fold cross-validation risk estimate on one sample and the final hypotheses is learned on the other. Model risk is estimated by k-fold cross-validation with \(k=4\).
LASSO and ridge regression estimate the parameters by minimizing the empirical squared loss plus, respectively, an \(\ell _{1}\) penalty \(\lambda \sum _{i=1}^{d}|a_{i}|\) and an \(\ell _{2}\) penalty \(\lambda \sum _{i=1}^{d}a_{i}^{2}\) on the slope coefficients, with the former additionally inducing sparsity by shrinking some coefficients exactly to zero. The regularization parameter \(\lambda\) is selected by k-fold cross-validation under the one-standard-error rule, that is, as the largest \(\lambda\) whose cross-validated risk is within one standard error of the minimum, favoring the most regularized, and hence simplest, model among those statistically indistinguishable from the one with the smallest estimated risk. They are fitted using the R package glmnet (Tay et al., 2023).
8.2.2 Optimization Algorithms for Learning Spaces
Given the exponential size of the lattices for \(d \in \{100,500,1000\}\), we cannot perform an exhaustive search and we need specialized algorithms for minimizing functions in lattices. For the Boolean VSLS we consider a stepwise approach which, starting from the model without variables, one variable is added/removed at each step. The selected addition or removal is that which leads to the least cross-validation error. When there are ties, we select one of the minimums randomly with equal probability among the ones with least number of variables. The algorithm runs for a pre-specified computation time and returns the model with the least cross-validation error visited during the search. The computation time was set to 120 seconds. This differs from usual stepwise algorithms that stop when no addition/removal of variables decreases the cross-validation error.
For the PLLS we consider the stochastic lattice descent algorithm (SLDA) proposed in Marcondes and Barrera (2024a, 2024b), Marcondes et al. (2024a, 2025), which is a generalization of the U-curve algorithms (Atashpaz-Gargari et al., 2018; Estrela et al., 2020; Reis et al., 2018; Ris et al., 2010), proposed for minimizing U-shaped functions in Boolean lattices. In the implemented SLDA, the search is initialized at the partition with a single block containing all variables. At each step, a set of candidate neighboring partitions is generated by either splitting one existing block into two, or merging two existing blocks into one.
Rather than sampling these candidates uniformly, splits are proposed by first regressing the residuals (i.e., point-wise errors) of the current partition model trained with the whole N size training sample onto the raw variables within each block. The probability of each block being selected for splitting is proportional to the \(R^2\) of this within-block regression. Observe that large values of \(R^2\) are evidence that the residuals are strongly correlated with the variables, which is an indication that considering the same coefficient for all variables is not providing goodness of fit.
When a block is selected, it is then split into two groups: one containing all variables in which the residual regression coefficients are positive and the other all that have non-positive coefficients. The sign of the residual regression coefficient is an indication that the true value of the model coefficient for the variable should be greater or smaller than the common estimated coefficient. This heuristic should lead to splittings that tend to group together variables with true coefficients that are close to each other.
On the other hand, merges of blocks are proposed by sampling pairs of blocks with probability inversely proportional to the squared difference between their current fitted coefficients of the model considering the whole training sample, since blocks with similar coefficients are the best candidates for merging without loss of fit.
At each step, a pre-specified number of split and merge neighbors are sampled with the established probabilities, their cross-validation error is computed, and the algorithm moves to the neighbor with the least cross-validation error, breaking ties first in favor of those with fewest blocks and then uniformly at random. As with the Boolean VSLS, the algorithm runs for a pre-specified computation time and returns the partition with the least cross-validation error visited during the search, rather than stopping at the first local optimum.
The number of sampled neighbors is 128, 64 and 32 for \(d = 100, 500\) and 1000, respectively, with half being sampled among the splits, and half among the merges. These choices are made to allow the algorithm to explore a bigger region of the bigger lattices in the pre-specified running time, which was also set at 120 seconds.
8.2.3 Results
Figure 8 presents, for each scenario, number of variables, error level and sample size, the average with 95% confidence intervals of the types II, III, and IV estimation errors of learning in each Learning Space. The average with 95% confidence intervals of the difference between the risk of the fitted function and the target is presented for ERM, LASSO and ridge regression as the type IV estimation error in each case. Table 5 in Appendix B presents the detailed results for each case. Figure 9 presents the cross-validation error at each step of the search on the VSLS and PLLS for all repetitions in each case.
Scenario 1. The target is sparse with unequal active coefficients, so the VSLS is theoretically well-adapted, while the PLLS is only partially adapted. The results evidence this clearly for \(d = 100\): VSLS achieves the lowest Type IV estimation error across all noise levels and sample sizes, with values on the order of \(10^{-5}\) to \(10^{-3}\), substantially below ERM (\(10^{-4}\) to \(10^{-2}\)) and far below LASSO and ridge, while PLLS sits above VSLS in all cases. As d grows, however, the picture changes sharply for VSLS: with only \(\sim 30\)−45 search steps available within 120 seconds, the stepwise algorithm cannot adequately explore the \(2^d\)-element Boolean lattice, and its Type IV estimation error collapses to values orders of magnitude worse than any competitor. On the other hand, PLLS, running the SLDA with 110–140 steps, is better, or as competitive as ERM, for all cases at \(d = 500\). For \(d = 1000\), the PLLS has a Type IV estimation error orders of magnitude lower than LASSO and ridge regression, but is not as low as ERM. We observe that learning via model selection has a better performance when the Type III estimation error is low, or even zero, meaning a good model was selected; when Type III error is large, especially for the VSLS in higher dimensions, the performance cannot be as high. This scenario outlines an important practical message: even when the VSLS is theoretically optimal for a sparse target, its stepwise search algorithm does not scale, and the PLLS with the SLDA provides a computationally viable alternative that leverages the partial grouping structure of the target function to achieve remarkable generalization at high dimension.
Scenario 2. This scenario combines sparsity with grouped active coefficients, making it suited to both Learning Spaces simultaneously. At \(d = 100\), VSLS again achieves the best Type IV error (order \(10^{-5}\) to \(10^{-3}\)), closely followed by PLLS, while LASSO performs competitively. The PLLS’s particular strength emerges as d increases: at \(d = 500\) and \(d = 1000\), PLLS achieves the lowest Type IV errors of any method, reaching values as low as \(\sim 7 \times 10^{-8}\) at \(d = 1000\), \(n = 2010\), easy, roughly 15 times better than LASSO and 16 times better than ERM in the same setting. This gain is a direct consequence of the PLLS target model’s minimal complexity: with only two groups of variables (active and inactive), the SLDA needs very few steps to locate the optimum, explaining why PLLS’s step counts at \(d = 500\)−1000 (120–175) remain comparable to or slightly above those in S1, while the performance is far higher. This is also evidenced in the Type III estimation error, that is zero in many cases, evidencing that a model that contains the target was selected. On the other hand, VSLS again degrades for \(d \ge 500\) for the same search-cost reasons as in S1. The results in S2 thus provide the clearest empirical evidence of the central theoretical message: structuring the collection of candidate models to match domain knowledge yields results that beat ERM and regularization (LASSO and ridge).
Scenario 3. The target is dense with grouped coefficients, where all d variables are active but split into two groups with distinct shared coefficients. Here VSLS has no theoretical advantage over ERM, while PLLS is ideally adapted. The results confirm this asymmetry: the PLLS achieved the lowest Type IV estimation error with the exception of the hard noise level for \(d = 100\). In particular, the true advantage of PLLS materializes at \(d = 500\) and \(d = 1000\), where it dominates all methods across all noise levels and sample sizes, by multiple orders of magnitude in many cases. On the other hand, VSLS, as expected theoretically, performs very poorly for \(d \ge 500\), with Type IV errors near 0.08- 0.04 that barely decrease with n, reflecting the fact that the search cannot locate the full-variable model within the 120-second budget. These results underscore that the PLLS’s advantage is not merely theoretical: for dense problems with groupable coefficients, the SLDA efficiently exploits the two-group structure to achieve generalization that scales gracefully with d.
Scenario 4. This is the adversarial case for both Learning Spaces in which the target is dense with all d variables active and pairwise distinct coefficients. The results confirm this unambiguously: ERM dominates across every combination of d, n, and noise level, achieving Type IV estimation error orders of magnitude smaller than any other method.
Evolution of optimization algorithms. The search algorithm of the VSLS has two distinct behaviors. The first, observed in the cases it struggles most (\(d = 500\) for S3 and S4, and \(d = 1000\)), is characterized by the cross-validation error not decreasing over time and a low variability among the repetitions. The second is characterized by high variability among repetitions; a sudden decrease in the error; and high variability over time evidencing visits to subsets with higher cross-validation error after a (local) minimum is found.
On the other hand, the SLDA in general converges, especially in lower dimension and S1, S2 and S3, without large variability over time: after a good minimum is found, the cross-validation error does not increase substantially afterwards. Furthermore, no abrupt decrease on the error is seen, with the exception of the first steps in some cases. Nevertheless, in some cases, such as S1 and S4 in \(d = 500\) and S4 in \(d = 1000\), there is a variability among the repetitions, with some converging faster than the others outlining that the stochasticity of the algorithm may lead to distinct convergence behaviors.
8.2.4 Comment
The results above highlight that the performance of learning via model selection depends jointly on two distinct factors: the alignment between the Learning Space and the target hypotheses, and the ability of the search algorithm to locate the target model within the allotted computation budget. When both conditions are met, as in S2 under PLLS and S1 under VSLS at \(d = 100\), the Type III estimation error is zero across replications, meaning the selected model contains the target, and the Type IV estimation error is substantially below that of ERM and regularization methods. When the Learning Space is well-adapted but the search fails to locate the target model, as with VSLS at \(d \ge 500\), the Type III error grows and directly degrades performance, irrespective of the theoretical advantage conferred by the Learning Space structure. This makes the quality of the optimization algorithm a binding practical constraint, and suggests that bounding the gap between the model returned by the SLDA and the global minimum as a function of computation time is an important open problem.
The results also clarify the effect of partially correct prior knowledge. Scenario 1 under the PLLS is precisely such a case: the target is sparse with pairwise distinct active coefficients, so the PLLS target model has \(\ell + 1\) blocks rather than the minimal two blocks of S2, meaning the imposed structure is imperfect. Nevertheless, PLLS still outperforms ERM and regularization at \(d = 500\) and \(d = 1000\), illustrating that any reduction in the complexity of the target model, even partial, translates into improved generalization, with the magnitude of the gain related to how much the structure reduces the complexity of the target model relative to the full hypotheses space.
Finally, the four scenarios are designed to span a wide range of alignment between domain knowledge and the true target: from perfect alignment, to partial alignment, to complete misalignment (S4 for both). The Type II, III, and IV estimation errors reported in Fig. 8 directly instantiate the theoretical decomposition of the generalization error: Type II measures the approximation gap of the selected model, Type III measures the model selection error, and Type IV measures the total gap between the fitted hypotheses and the target. The consistent pattern across all scenarios, that lower target model complexity leads to lower Type IV error when the search successfully minimizes Type III error, provides direct empirical corroboration of the paper’s central theoretical message. In particular, it illustrates when learning via model selection with cross-validation error estimation based on prior information can beat ERM and established regularization methods.
Remark 8.1
We note that the stepwise algorithm for the VSLS could be adapted by also sampling candidate models at each step to increase the range of the lattice that is visited with the limited computation budget. However, a good heuristic would be necessary to assign probabilities to each neighboring model.
9 Inserting Domain Knowledge into Learning Spaces Increases Generalization
The example in Sect. 8.2 is a special case in which generalization may be increased by inserting prior information into the Learning Space. If it is known that the target hypotheses is sparse, then the variable selection Learning Space should be chosen to increase generalization, while if it is known that some input variables have the same effect, the partition lattice Learning Space should be chosen.
In ERM, in order to increase generalization, much stronger domain knowledge must be available to consider \(\mathcal {H}\) as a simpler hypotheses space without adding a large bias. For instance, knowing that the target is sparse is not enough, and it is necessary to know exactly on what variables it depends on. Moreover, knowing that some variables have the same effect is not enough, and it is necessary to know which variables have the same effect. Conversely, the Learning Spaces can leverage weaker domain knowledge to increase generalization, as illustrated in Sect. 8.2.
Domain knowledge can be especially leveraged to decrease the complexity of \(\mathcal {M}^{\star }\), which should enable greater generalization. Indeed, if it is too complex, then there would only be the possibility of learning a target hypotheses if a highly complex model was selected, and then it was learned from it. This scenario would require a large computational budget to search the Learning Space and a large independent sample to properly learn the target hypotheses once a highly complex model that contains it is selected; actually, a large sample size might also be necessary to select such a complex model. On the other hand, if \(\mathcal {M}^{\star }\) has low complexity, then it might be more likely to select it, or a low-complexity model that contains it, and fewer samples and computational resources are necessary to both select a suitable model and learn a hypotheses from it. The results in Fig. 8 illustrate this fact.
Figure 10 presents some examples of how the quality of prior information can be associated with the complexity of \(\mathcal {M}^{\star }\). In Fig. 10a, the complexity of \(\mathcal {M}^{\star }\) is low, so generalization might be higher. The partition lattice Learning Space of linear functions in Sect. 8.2 when the target is \(h_{3}^{\star }\) is an example of this scenario. In Fig. 10b, the complexity of \(\mathcal {M}^{\star }\) is not as low, but generalization might be higher than in the scenario in Fig. 10c, in which \(\mathcal {M}^{\star }\) is highly complex. The partition lattice Learning Space of linear functions in Sect. 8.2 when the target is \(h_{1}^{\star }\) is an example of Fig. 10b and the variable selection Learning Space when the target is \(h^{\star }_{3}\) is an example of Fig. 10c.
The reasoning illustrated in Fig. 10 also argues against considering nested models as the family of candidates from a statistical perspective. Nested models represent a chain \(\mathcal {M}_{1} \subset \dots \subset \mathcal {M}_{r}\) in the lattice, and the amount of domain knowledge has to be substantial to choose the right chain. This is illustrated in Fig. 10a in which \(h^{\star }\) is in a simple model of one chain, but a complex model of the other chain. In this case, domain knowledge would need to be spot on so that the right chain could be selected. In Scenario 3 of Sect. 8.2, this would mean that only knowing that some variables have the same effect would not be sufficient and more prior information would have to lead one to select a chain that passes through the partition of the even and odd numbers. Moreover, we argue that lattice Learning Spaces also have advantages from a computational perspective, especially when searching for approximately optimal models within the allotted computation budget.
10 Final Remarks
Model selection techniques have been historically sought to increase generalization. The main concern of these methods has been to control the complexity of the hypotheses space to avoid overfitting. This is explicitly done in model selection by complexity penalization, and in variable selection, since the complexity of the model is related to the number of variables. However, selecting a low-complexity model is only one step to achieving high generalization, since it is also necessary to have low-risk hypotheses in such a model; otherwise high generalization is unfeasible. In this paper, we investigated how modeling the collection of candidate models based on domain knowledge and prior information may increase generalization.
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 hypotheses on it with an independent sample or by reusing, seeking to approximate a target hypotheses 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 Cortes et al. (2019).
We introduced the maximum discrimination error \(\epsilon ^{\star }\), formalized the concept of target model, and illustrated the possibility of better learning with a fixed sample size by properly modeling the family of candidate models with two simulation studies. We argued that by modeling the collection of candidate models based on domain knowledge, it is possible to increase generalization. In particular, we introduced the Learning Spaces and discussed how generalization might be increased by designing them in such a way that the target hypotheses is contained in simple models. The theoretical results also support this assertion, as follows.
First, since \(\hat{\mathcal {M}}\) converges to \(\mathcal {M}^{\star }\) with probability one,
in which \(G: \mathbb {C}(\mathcal {H}) \mapsto \mathbb {R}\) is any real-valued function. 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 4.5 and 5.5 and Corollaries 4.8 and 5.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 fixed sample size. Furthermore, tighter bounds are obtained in cases in which \(d_{VC}(\hat{\mathcal {M}}) \approx d_{VC}(\mathcal {M}^{\star })\), or \(\hat{\mathcal {M}} = \mathcal {M}^{\star }\), with high probability (see also Theorems 6.1 and 6.3).
Second, if the MDE of \(\mathbb {C}(\mathcal {H})\) under P is large, 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 smaller than an \(\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 smaller 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 smaller than that of \(\mathcal {H}\). However, there may be a trade-off between \(d_{VC}(\mathbb {C}(\mathcal {H}))\) and the number \(\mathfrak {m}(\mathbb {C}(\mathcal {H}))\) of maximal elements in \(\mathbb {C}(\mathcal {H})\), as can be seen on the established bounds.
The simulation study of Sect. 8 provides direct empirical support for these theoretical assertions. In the regression experiments, learning via model selection in the partition lattice Learning Space substantially outperformed ERM, LASSO, and ridge regression in scenarios where the target model had low complexity and the search algorithm successfully located it (low Type III estimation error), illustrating that a well-designed Learning Space can yield generalization gains orders of magnitude beyond those of standard methods. Conversely, when the search failed to locate the target model, or when the Learning Space was misaligned with the true target (Scenario 4), performance degraded as predicted by the bounds, with ERM dominating. Together, the theoretical bounds and simulation results highlight that the practical benefit of learning via model selection depends jointly on the alignment between the Learning Space and the true target, i.e., prior knowledge, and on the quality of the optimization algorithm used to search it.
Since the bounds were developed 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 3.2 and 5.2. In particular, a theoretical study of the estimation errors in the examples in Sect. 7 should be straightforward, so they ought to be the first distribution-dependent settings to be investigated in future studies. Bounding the estimation errors in the framework of Mendelson et al. (2003) is also a promising line of research in this context.
The established bounds are not useful to determine the number of folds in cross-validation, since 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 and insights about the optimal number of folds could be obtained 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. Insights and refined results in the learning by reusing framework could also be obtained by restricting the study to a specific class of models and data generating distributions, in which the effect of considering the same sample to select the model and learn on it could be better understood.
Although outside the scope of this paper, the computational cost of computing \(\hat{\mathcal {M}}\) by solving optimization problem (7) should also be considered when choosing family \(\mathbb {C}(\mathcal {H})\). As evidenced in the simulation study of Sect. 8.2, this family of candidate models should have some structure that allows an efficient computation of (7), or the computation of a suboptimal solution with satisfactory practical results.
The framework of this paper could be studied considering other risk estimators besides cross-validation. For example, one could consider modeling the family of candidate models based on domain knowledge together with penalization methods, by taking the risk \(\hat{L}\) as a penalization of the empirical error. This approach, in both a distribution-free and dependent scenario, could lead to tighter bounds and better practical methods for specific problems. Also, an interesting topic for future research would be to prove the results of this paper relaxing the assumption that the sample is independent and identically distributed.
From an applied perspective, there is great promise in investigating how specific domain knowledge may be leveraged to design a Learning Space to solve specific learning problems. The examples in Sect. 7 illustrate how this can be done, but it is necessary to further study not only how to translate prior information into a suitable Learning Space, but also the effect of this modeling on the generalization in other applied problems. This can be investigated from a theoretical perspective, by developing deviation-bounds in specific scenarios, and empirically by comparing learning via model selection based on domain knowledge with other methods.
11 Proof of Results
11.1 Definition of Validation Errors
11.1.1 Validation Sample
Fix a sequence \(\{V_{N}: N \ge 1\}\) such that \(\lim \limits _{N \rightarrow \infty } V_{N} = \lim \limits _{N \rightarrow \infty } N - V_{N} = \infty\), and let
be a split of \(\mathcal {D}_{N}\) into a training and validation sample. The two samples \(\mathcal {D}_{N}^{(\text {train})}\) and \(\mathcal {D}_{N}^{(\text {val})}\) are independent. The estimator under the validation sample is given by
in which
minimizes the empirical risk in \(\mathcal {M}\) under \(\mathcal {D}_{N}^{(\text {train})}\).
11.1.2 K-Fold Cross-Validation
Fix \(k \in \mathbb {Z}_{+}\) and assume \(N :=kn\), for a \(n \in \mathbb {Z}_{+}\). Then, let
be a partition of \(\mathcal {D}_{N}\):
We define
as the hypotheses 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
as the validation risk of the j-th fold.
The k-fold cross-validation estimator of \(L(\mathcal {M})\) is then given by
that is the average validation risk over the folds.
11.2 Results of Sect. 4
We start with a lemma.
Lemma 11.1
Proof
If
then, for any \(i \in \mathcal {J}\) such that \(L(\mathcal {M}_{i})> L(\mathcal {M}^{\star })\), we have
in which the last inequality follows from the definition of \(\epsilon ^{\star }\). From (23) it follows that the global minimum of \(\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 (23) it 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}}) \le \hat{L}(\mathcal {M}^{\star })\), we must have \(L(\hat{\mathcal {M}}) = L(\mathcal {M}^{\star })\) implying the desired inclusion of events. \(\square\)
Proof of Proposition 4.1
The result is a direct consequence of Lemma 11.1. \(\square\)
We state and prove a lemma that will aid the proof of Theorem 4.3
Lemma 11.2
Assume the premises of Theorem 4.3 are in force. Then, for any \(\epsilon> 0\) it holds
Proof
Fix \(\epsilon> 0\). Denoting \(\hat{h}_{i}^{(j)} :=\hat{h}_{\mathcal {M}_{i}}^{(j)}\),
in which in the first inequality we applied the definition of \(\hat{L}(\mathcal {M})\). For each j, the first probability in (24) is equal to
in which the first inequality follows from the fact that \(L_{\mathcal {D}_{N}^{(j)}}(\hat{h}^{(j)}_{i}) \le L_{\mathcal {D}_{N}^{(j)}}(h_{i})\), and the last follows since \(L(\mathcal {M}_{i}) = L(h_{i})\). We conclude that
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
hence it is true that
which yields
in which the last inequality follows from the fact that both \(\hat{B}_{N_{v},\epsilon /4}\) and \(B_{N_{t},\epsilon /8}\) are increasing functions, and \(d_{VC}(\mathbb {C}(\mathcal {H})) = \max _{\mathcal {M} \in \mathbb {C}(\mathcal {H})} d_{VC}(\mathcal {M})\). \(\square\)
Proof of Theorem 4.3
It follows from Lemma 11.2 that
so the result follows from Proposition 4.1 since
If the almost sure convergences (15) hold, then
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
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 (27) converges to one if (26) is true, we conclude that, if (15) holds, then \(\hat{\mathcal {M}}\) converges to \(\mathcal {M}^{\star }\) with probability one. \(\square\)
Proof of Theorem 4.4
We need to show that (15) holds in these instances. For any \(\epsilon> 0\), by Corollary A.12,
By the inequality above, and Borel-Cantelli Lemma (Billingsley, 2008, Theorem 4.3), the first convergence in (15) holds. The second convergence holds since the inequality above is also true, but with \(L_{\mathcal {D}_{N}^{(j)}}\) and \(N_{t}\) interchanged by \(\hat{L}^{(j)}\) and \(N_{v}\), the empirical risk and size of the j-th validation sample. \(\square\)
Proof of Theorem 4.5
We first note that
Fix \(\mathcal {M} \in \mathbb {C}(\mathcal {H})\) with \(\mathbb {P}(\mathcal {\hat{M}} = \mathcal {M})> 0\). We claim that
Indeed, since \(\tilde{\mathcal {D}}_{M}\) is independent of \(\mathcal {D}_{N}\), the event
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 (16) to each positive probability in the sum (28), we obtain that
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
and \(B^{II}_{M,\epsilon }(d_{VC}(\mathcal {M}_{i}))\) is a bound for the probabilities inside the sum by (16). 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. \(\square\)
Proof of Theorem 4.6
We first show that
If \(\epsilon \le \epsilon ^{\star }\) then, by Lemma 11.1, we have that
since \(L(h^{\star }_{\hat{\mathcal {M}}}) = L(\hat{\mathcal {M}})\) and \(L(h^{\star }_{\mathcal {M}^{\star }}) = L(\mathcal {M}^{\star })\), so (30) follows in this case.
Now, if \(\epsilon> \epsilon ^{\star }\) and \(\max \limits _{i \in \mathcal {J}} \text {|}\hat{L}(\mathcal {M}_{i}) - L(\mathcal {M}_{i})\text {|} < \epsilon /2\), then
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 {|}\hat{L}(\mathcal {M}_{i}) - L(\mathcal {M}_{i})\text {|} < \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
when \(\epsilon> \epsilon ^{\star }\). From (31) and (32) follows (30), as desired.
It follows from Lemma 11.2 that
The result follows combining (30) and (33). \(\square\)
11.3 Results of Sect. 5
Proof of Theorem 5.3
We claim that
Indeed, the left-hand side of (34) implies
as desired. In particular, it follows from Lemma 11.1 that
hence it is enough to bound both probabilities on the right-hand side of the expression above.
The first probability in (35) may be written as
in which the inequality follows from a union bound. Since \(x \mapsto \frac{x - \alpha }{x}\) is increasing, and \(L(\mathcal {M}_{i}) \le L(\hat{h}^{(j)}_{i})\) for every \(j = 1,\dots ,m\), each probability in (36) is bounded by
We turn to the second probability in (35) which can be written as
in which again the inequality follows from a union bound. In order to bound each probability in (38) we intersect its event with
and its complement, to obtain
in which the last inequality follows from Lemma A.21.
It remains to bound the second probability in (39). We have that it is equal to
in which the last inequality follows again from Lemma A.21. From (35–40), it follows that
in which the inequality holds by the same arguments as in (25), hence
If the almost sure convergences (21) 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. \(\square\)
Proof of Theorem 5.6
We show that
so from (30) and (34) will follow that
and the result is then direct from the proof of Theorem 5.3. But (41) is clearly true since
\(\square\)
11.4 Results of Sect. 6
Proof of Theorem 6.1
The bound for type I estimation error follows from the inequality
by noting that \(B_{N,\epsilon }^{I}(d_{VC}(\mathcal {M}^{\star }))\) is a bound for the first probability. With a similar argument, we have the bound for type II estimation error. \(\square\)
Data Availability
The R code that generates the simulated data and performs the analysis can be provided.
Notes
We elevate (19) to the 1/p power to be consistent with the theory presented in Appendix A.
In the presentation of (Vapnik, 1998, 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.
References
Andrews, D. W. (1991). Asymptotic optimality of generalized cl, cross-validation, and generalized cross-validation in regression with heteroskedastic errors. Journal of Econometrics, 47(2–3), 359–377.
Anguita, D., Ghio, A., Oneto, L., & Ridella, S. (2012). In-sample and out-of-sample model selection and error estimation for support vector machines. IEEE Transactions on Neural Networks and Learning Systems, 23(9), 1390–1406.
Arlot, S., & Bartlett, P. L. (2011). Margin-adaptive model selection in statistical learning. Bernoulli, 17(2), 687–713.
Atashpaz-Gargari, E., Reis, M. S., Braga-Neto, U. M., Barrera, J., & Dougherty, E. R. (2018). A fast branch-and-bound algorithm for u-curve feature selection. Pattern Recognition, 73, 172–188.
Austern, M., & Zhou, W. (2025). Asymptotics of cross-validation. Annales de l’Institut Henri Poincare (B) Probabilites et Statistiques (Vol. 61, pp. 2804–2865) Institut Henri Poincaré.
Bartlett, P. L. (2008). Fast rates for estimation error and oracle inequalities for model selection. Econometric Theory, 24(2), 545–552.
Bartlett, P. L., Long, P. M., & Williamson, R. C. (1994). Fat-shattering and the learnability of real-valued functions. Proceedings of the Seventh Annual Conference on Computational Learning Theory (pp. 299–310)
Bartlett, P. L., & Mendelson, S. (2002). Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3, 463–482.
Billingsley, P. (2008). Probability and Measure. John Wiley & Sons.
Cortes, C., Greenberg, S., & Mohri, M. (2019). Relative deviation learning bounds and generalization with unbounded loss functions. Annals of Mathematics and Artificial Intelligence, 85(1), 45–70.
Devroye, L., Györfi, L., & Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition (Vol. Vol. 31). Springer.
Ding, J., Tarokh, V., & Yang, Y. (2018). Model selection techniques: An overview. IEEE Signal Processing Magazine, 35(6), 16–34.
Dudoit, S., & van der Laan, M. J. (2005). Asymptotics of cross-validated risk estimation in estimator selection and performance assessment. Statistical Methodology, 2(2), 131–154.
Estrela, G., Gubitoso, M. D., Ferreira, C. E., Barrera, J., & Reis, M. S. (2020). An efficient, parallelized algorithm for optimal conditional entropy-based feature selection. Entropy, 22(4), 492.
Foss, S., Korshunov, D., & Zachary, S. (2011). An Introduction to Heavy-tailed and Subexponential Distributions (Vol. 6). Springer.
Guyon, I., & Elisseeff, A. (2003). An introduction to variable and feature selection. Journal of machine learning research, 3, 1157–1182.
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301), 13–30.
Hoerl, A. E., & Kennard, R. W. (1970). Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1), 55–67.
John, G. H., Kohavi, R., & Pfleger, K. (1994). Irrelevant features and the subset selection problem. Machine Learning: Proceedings of the Eleventh International Conference (pp. 121–129)
Koltchinskii, V. (2001). Rademacher penalties and structural risk minimization. IEEE Transactions on Information Theory, 47(5), 1902–1914.
Koltchinskii, V. (2011). Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d’Eté de Probabilités de Saint-Flour XXXVIII-2008 vol. 2033. Springer, New York
Lecué, G., & Mitchell, C. (2012). Oracle inequalities for cross-validation type procedures. Electronic Journal of Statistics, 6, 1803–1837.
Li, K.-C. (1987). Asymptotic optimality for cp, cl, cross-validation and generalized cross-validation: discrete index set. The Annals of Statistics (pp. 958–975)
Maillard, G. (2021). Local asymptotics of cross-validation in least-squares density estimation. arXiv preprint arXiv:2106.09962.
Marcondes, D., & Barrera, J. (2024a). Discrete morphological neural networks. SIAM Journal on Imaging Sciences, 17(3), 1650–1689.
Marcondes, D., & Barrera, J. (2024b). The lattice overparametrization paradigm for the machine learning of lattice operators. International Conference on Discrete Geometry and Mathematical Morphology (pp. 204–216). Springer.
Marcondes, D., Feldman, M., & Barrera, J. (2024a). An algorithm to train unrestricted sequential discrete morphological neural networks. International Conference on Discrete Geometry and Mathematical Morphology (pp. 178–191). Springer.
Marcondes, D., Feldman, M., & Barrera, J. (2025). Unrestricted sequential discrete morphological neural networks. Journal of Mathematical Imaging and Vision, 67(4), 39.
Marcondes, D., Simonis, A., & Barrera, J. (2024b). Back to basics to open the black box. Nature Machine Intelligence, 1–4.
Massart, P. (2007). Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII-2003. Springer.
Mendelson, S., Philips, P., & Bartlett, P. (2003). On the importance of small coordinate projections. Journal of Machine Learning Research, 3(3)
Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of Machine Learning. MIT press.
R Core Team. (2026). R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. R Foundation for Statistical Computing. https://www.R-project.org/
Raschka, S. (2018). Model evaluation, model selection, and algorithm selection in machine learning. arXiv preprint arXiv:1811.12808.
Reis, M. S., Estrela, G., Ferreira, C. E., & Barrera, J. (2018). Optimal boolean lattice-based algorithms for the u-curve optimization problem. Information Sciences
Ris, M., Barrera, J., & Martins, D. C. (2010). U-curve: A branch-and-bound optimization algorithm for u-shaped cost functions on boolean lattices applied to the feature selection problem. Pattern Recognition, 43(3), 557–568.
Tay, J. K., Narasimhan, B., & Hastie, T. (2023). Elastic net regularization paths for all generalized linear models. Journal of Statistical Software, 106(1), 1–31. https://doi.org/10.18637/jss.v106.i01
Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1), 267–288.
Van der Vaart, A. W., Dudoit, S., & Van der Laan, M. J. (2006). Oracle inequalities for multi-fold cross validation. Statistics & Decisions, 24(3), 351–371.
Vapnik, V. (1998). Statistical Learning Theory (Vol. 3). Wiley.
Vapnik, V. (2000). The Nature of Statistical Learning Theory. Springer.
Vapnik, V. N., & Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16, 264–280.
Acknowledgements
D. Marcondes was funded by grant #2022/06211-2, São Paulo Research Foundation (FAPESP), during the writing of this paper. We thank J. Barrera and A. Simonis for many fruitful conversations about Learning Spaces. During the preparation of this work, the authors used Claude AI to assist in writing and refining the code of the simulation in Sect. 8.2. After using this tool, the authors reviewed and carefully edited the code, verified its output, and take full responsibility for the content of this publication. This work was supported by computational resources provided by the Australian Government through the National Computational Infrastructure (NCI) under the ANU Startup Scheme.
Funding
Open Access funding enabled and organized by CAUL and its Member Institutions
Author information
Authors and Affiliations
Contributions
D.M. wrote the main manuscript text and performed the simulation studies. D.M and C.P. conceptualised the methods and reviewed the manuscript.
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Editor: Ronaldo Prati.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
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 Vapnik (1998, 2000), Devroye et al. (1996) and Cortes et al. (2019), 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 Sect. 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 Cortes et al. (2019). 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
for \(N \in \mathbb {Z}_{+}\), in which \(\text {|}\cdot \text {|}\) is the cardinality of a set.
Definition A.2
(Vapnik-Chervonenkis dimension) Fixed a hypotheses space \(\mathcal {H}\) and a loss function \(\ell\), set
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 ) = \mathbbm {1}\{\ell (z,h) \ge \beta \}\), for \(z \in \mathcal {Z}\), and denote
We define the shatter coefficient of \(\mathcal {H}\) under loss function \(\ell\) as
The Vapnik-Chervonenkis (VC) dimension of \(\mathcal {H}\) under loss function \(\ell\) is the greatest integer \(k \ge 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 \ge 1\), we denote \(d_{VC}(\mathcal {H},\ell ) = \infty\).
Remark A.3
If there is no confusion about which loss function we are referring to, 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) = \mathbbm {1}\{h(x) \ne 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.
1.1 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) :=\mathbb {P}(Z \le z)\), for \(z \in \mathcal {Z} \subset \mathbb {R}^{d}\), defined in a probability space \((\Omega ,\mathcal {S},\mathbb {P})\).
In order to ease 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 \le z\}) = P(z)\), for all \(z \in \mathbb {R}^{d}\). Define
as the empirical distribution of Z under sample \(\mathcal {D}_{N}\).
The assertion of the theorem below is that of (Devroye et al., 1996, 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,
Applying Borel-Cantelli Lemma (Billingsley, 2008, Theorem 4.3) to (A1) yields
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
as the empirical probability of event \(A \in \mathcal {S}\) under sample \(\mathcal {D}_{N}\), the probability in (A1) can be rewritten as
in which \(\mathcal {S}^{\star } = \{A_{z}:z \in \mathbb {R}\}\) with \(A_{z} = \{\omega \in \Omega : \omega \le z\}\). If probability (A2) 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 (A2) 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. Sect. 3), 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 (A1) 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 \rightarrow \infty } b(N)/\exp cN = 0, \forall c> 0\), satisfying, for N great enough,Footnote 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 \le z\}, z \in \mathbb {R}^{d}\). If the events are of the form \(A = \{w \in \Omega : Z(w) \le z\}, z \in \mathbb {R}\), then (A3) is equivalent to (A1), 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 (A3) to hold. We will study these conditions in order to establish the almost sure convergence to zero of type I estimation error (cf. (10)) when the loss function is binary, what may be stated as a GGCP.
1.2 A.2 Convergence to Zero of Type I Estimation Error
1.2.1 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 \(\mathbbm {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
In this instance, the probability in the left-hand side of (A3) may be written as
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 Sect. 3, this last probability equals
the tail probability of type I estimation error in \(\mathcal {H}\).
For each fixed \(h \in \mathcal {H}\), we are comparing in (A4) the mean of a binary function with its empirical mean, so we may apply Hoeffding’s inequality (Hoeffding, 1963) to obtain
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:
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
be the characteristic functions of the sets in \(\mathcal {S}^{\star }\). We define the shatter coefficient of \(\mathcal {S}^{\star }\) as
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, it follows that
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 (Devroye et al., 1996, Theorem 12.4) follows a result due to Vapnik and Chervonenkis (1971).
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
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
Then,
with
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 ease notation.
The calculation of the quantities on the right-hand side of (A5) 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 (Vapnik, 1998, Theorem 4.3).
Theorem A.9
If \(d_{VC}(\mathcal {H}) < \infty\), then
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
In particular, if \(d_{VC}(\mathcal {H}) < \infty\), not only (A6) converges to zero, but also
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.
1.2.2 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}\),
for a positive constant \(C \in \mathbb {R}_{+}\). Throughout this section, a constant C satisfying (A7) is fixed.
For any \(h \in \mathcal {H}\), by definition of Lebesgue-Stieltjes integral, we have that
recalling that Z is a random variable with distribution P. In the same manner, we may also write the empirical risk under \(\mathcal {D}_{N}\) as
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,
We conclude that
Since the right-hand side of the expression above is a GGCP with
and, recalling the definition of shatter coefficient of \(\mathcal {H}\) under a real-valued loss function \(\ell\) (cf. Definition A.1), we note that
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 \le \ell (z,h) \le C\) for all \(z \in \mathcal {Z}, h \in \mathcal {H}\). Then,
In particular, if \(d_{VC}(\mathcal {H}) < \infty\), not only (A8) converges to zero, but also
with probability one by Borel-Cantelli Lemma.
It remains to treat the case of unbounded loss functions, which requires a different approach.
1.2.3 A.2.3 Unbounded Loss Functions
In this section, we establish conditions on P and \(\mathcal {H}\) for the convergence in probability to zero of type I relative estimation error when \(\ell\) is unbounded. The framework treated here is that described at the beginning of Sect. 5.
In order to ease notation, we denote
the vector sample point loss, so it follows from (19) that, for \(1 \le q \le p\),
in which \(\Vert \cdot \Vert _{q}\) is the q-norm in \(\mathbb {R}^{N}\). Recall that we assume that P has at most heavy tails, which means there exists a \(p> 1\), that can be less than 2, with
and that
in which the first inequality should hold with probability one.
The first condition in (A11) is more a feature of the loss function, than of distribution P. Actually, one can bound \(L_{\mathcal {D}_{N}}^{p}(h)\) by a quantity depending on N and \(L_{\mathcal {D}_{N}}^{q}(h)\) with \(1 \le q < p\), for any sample \(\mathcal {D}_{N}\) of any distribution P. This is the content of the next lemma, which will be useful later on, and that implies the following: if \(\sup _{h \in \mathcal {H}} L_{\mathcal {D}_{N}}^{1}(h) = \sup _{h \in \mathcal {H}} L_{\mathcal {D}_{N}}(h) < \infty\), then \(\sup _{h \in \mathcal {H}} L_{\mathcal {D}_{N}}^{p}(h) < \infty\) for any \(1< p < \infty\), for N and \(\mathcal {H}\) fixed.
Lemma A.13
For fixed \(\mathcal {H}\), \(N \ge 1\) and \(1 \le q < p\), it follows that
for all \(h \in \mathcal {H}\).
Proof
Recalling definition (A9), we have that
so it is enough to show that
Now, the right inequality above is clear, since if \(w \in \mathbb {R}^{N}\) is such that \(\Vert w \Vert _{q} = 1\), then
so the result follows when \(\Vert w \Vert _{q} = 1\) by elevating both sided to the 1/p power. To conclude the proof it is enough to see that, for any \(w \in \mathbb {R}^{N}\setminus \{0\}\),
The left inequality is a consequence of Hölder’s inequality, since, for \(w \in \mathbb {R}^{N}\),
and the result follows by taking the 1/q power on both sides. \(\square\)
For unbounded losses, rather than considering the convergence of type I estimation error to zero, we will consider the convergence of the relative type I estimation error, defined as
In order to establish bounds for the tail probabilities of (A12) when (A10) and (20) hold, we rely on the following novel technical theorem.
Theorem A.14
Let \(q = \sqrt{p}\). For any hypotheses space \(\mathcal {H}\), loss function \(\ell\) satisfying \(\ell (h,z) \ge 1\), and \(0< \epsilon < 1\), it holds
in which \(L^{\prime },L_{\mathcal {D}_{N}}^{\prime }\) and \(L_{\mathcal {D}_{N}}^{\prime k}\) are the respective risks and k moments of loss function \(\ell ^{\prime }(z,h) :=(\ell (z,h))^{q}\).
Proof
We first note that
since
by (A10). With an analogous deduction, it follows that
Hence, the probability on the left hand-side of the statement is lesser or equal to
so it is enough to properly bound the second probability in (A13).
In order to do so, we will intersect the event inside the probability with the following event, and its complement:
in which
Proceeding in this way, we conclude that
To bound the first probability above, we recall the definition of \(L_{\mathcal {D}_{N}}^{p}(h)\) and note that \(a^{\frac{1}{q}} - b^{\frac{1}{q}} \le a - b\) if \(q> 1\) and \(1 \le b \le a\), so that
Define the loss function \(\ell ^{\prime }(z,h) :=(\ell (z,h))^{q}\), and let \(L^{\prime },L^{\prime k},L_{\mathcal {D}_{N}}^{\prime }\) and \(L_{\mathcal {D}_{N}}^{\prime k}\) be the risks and k moments according to this new loss function. Then, the probability in (A15) can be written as
since \(\frac{p}{q} = q\) and \(N^{\frac{1}{p}} \le N^{\frac{1}{q}}\).
We turn to the second probability in (A14). By applying Lemma A.13, and recalling the definition of \(\delta\), we have that \(L_{\mathcal {D}_{N}}^{q}(h) - \delta L_{\mathcal {D}_{N}}^{p}(h)\) is equal to
from which follows
The result follows by combining (A13), (A14), (A16) and (A17). \(\square\)
An exponential bound for relative type I estimation error (A12) depending on p, \(\tau ^{\star }\) and \(d_{VC}(\mathcal {H})\) is a consequence of Theorems A.9 and A.14, and results in Cortes et al. (2019), which we now state. Define, for a \(0< \varsigma < 1\) fixed,
for \(0< \epsilon< 1, 1 < p \le 2\), and
for \(p> 2\).
Theorem A.15
Fix a hypotheses space \(\mathcal {H}\) and an unbounded loss function \(\ell\), and assume that (A11) is in force. Then, the following holds:
-
If P has light tails, so that (A10) holds for a \(p> 2\) fixed, then
$$\begin{aligned} \mathbb {P}\Bigg (\sup \limits _{h \in \mathcal {H}}&\frac{L(h) - L_{\mathcal {D}_{N}}(h)}{\root p \of {\left( L^{p}(h)\right) ^{p} + \varsigma }}> \Lambda (p) \epsilon \Bigg )\\ &< 4 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}N}{4}\right\} \end{aligned}$$and
$$\begin{aligned} \mathbb {P}\Bigg (\sup \limits _{h \in \mathcal {H}}&\frac{L_{\mathcal {D}_{N}}(h) - L(h)}{\root p \of {\left( L_{\mathcal {D}_{N}}^{p}(h)\right) ^{p} + \varsigma }}> \Lambda (p) \epsilon \Bigg ) \\ &< 4 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}N}{4}\right\} , \end{aligned}$$for \(0< \epsilon < 1\) and \(0< \varsigma < \epsilon ^{2}\).
-
If P has heavy tails, so that (A10) holds only for a \(1 < p \le 2\) fixed, then
$$\begin{aligned} \mathbb {P}\Bigg (\sup \limits _{h \in \mathcal {H}}&\frac{L(h) - L_{\mathcal {D}_{N}}(h)}{\root p \of {\left( L^{p}(h)\right) ^{p} + \varsigma }}> \Gamma (p,\epsilon ) \epsilon \Bigg ) \\ &< 4 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}N^{\frac{2(p-1)}{p}}}{2^{\frac{p+2}{2}}}\right\} \end{aligned}$$and
$$\begin{aligned} \mathbb {P}\Bigg (\sup \limits _{h \in \mathcal {H}}&\frac{L_{\mathcal {D}_{N}}(h) - L(h)}{\root p \of {\left( L_{\mathcal {D}_{N}}^{p}(h)\right) ^{p} + \varsigma }}> \Gamma (p,\epsilon ) \epsilon \Bigg ) \\ &< 4 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}N^{\frac{2(p-1)}{p}}}{2^{\frac{p+2}{2}}}\right\} , \end{aligned}$$for \(0< \epsilon < 1\) and \(0< \varsigma ^{\frac{p-1}{p}} < \epsilon ^{\frac{p}{p-1}}\).
Theorem A.15, together with Theorem A.14, imply the following corollary, which is an exponential bound for relative type I estimation error when P has heavy or light tails. The value of \(\varsigma\) in the definitions of \(\Lambda (p)\) and \(\Gamma (p,\epsilon )\) below can be arbitrarily small.
Corollary A.16
Fix a hypotheses space \(\mathcal {H}\), an unbounded loss function \(\ell\) and \(\epsilon> 0\). The following holds:
-
If (A10) holds for a \(p \ge 4\) fixed, then
$$\begin{aligned} \mathbb {P}&\Bigg (\sup \limits _{h \in \mathcal {H}} \frac{\text {|}L(h) - L_{\mathcal {D}_{N}}(h)\text {|}}{L(h)}> \tau ^{\star } \Lambda (\sqrt{p}) \epsilon \Bigg ) \\&< 12 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}(1-\epsilon )^{2}N^{1 - \frac{2}{\sqrt{p}} + \frac{2}{p}}}{4}\right\} \end{aligned}$$ -
If (A10) holds for a \(1< p < 4\) fixed, then
$$\begin{aligned} \mathbb {P}&\Bigg (\sup \limits _{h \in \mathcal {H}} \frac{\text {|}L(h) - L_{\mathcal {D}_{N}}(h)\text {|}}{L(h)}> \tau ^{\star } \Gamma \left( \sqrt{p},\frac{\epsilon }{N^{\frac{1}{\sqrt{p}} - \frac{1}{p}}}\right) \epsilon \Bigg ) \\&< 12 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}N^{\frac{2(\sqrt{p} - 1)}{\sqrt{p}} - \frac{2}{\sqrt{p}} + \frac{2}{p}}}{2^{\frac{\sqrt{p} + 2}{2}}} \right\} . \end{aligned}$$
In both cases, if \(d_{VC}(\mathcal {H}) < \infty\), then, by Borel-Cantelli Lemma,
with probability one.
Corollary A.16 establishes the convergence to zero of relative type I estimation error, and concludes our study of type I estimation error convergence in classical VC theory.
Remark A.17
We simplified the bounds in Corollary A.16 since, by combining Theorems A.14 with A.15, we obtain a bound with three terms of different orders in N, where the exponential in each of them is multiplied by four. The term of the greatest order is that we show in Corollary A.16, with the exponential multiplied by twelve, since we can bound the two terms of lesser order by the one of the greatest order. This worsens the bound for fixed N, but eases notation and has the same qualitative effect of presenting an exponential bound for relative type I estimation error, which implies its almost sure convergence to zero.
Remark A.18
Observe that \(d_{VC}(\mathcal {M},\ell ) = d_{VC}(\mathcal {M},\ell ^{\prime })\), in which \(\ell ^{\prime }(z,h) = \left( \ell (z,h)\right) ^{q}, q = \sqrt{p},\) as defined in Theorem A.14, hence we can bound all three terms of the inequality in this theorem by \(d_{VC}(\mathcal {M},\ell )\), as is done in Corollary A.16. The VC dimension equality is true since \(\mathcal {G}_{\mathcal {M},\ell } = \mathcal {G}_{\mathcal {M},\ell ^{\prime }}\) (cf. Definition A.2), as each function \(g_{\beta ,h}(z) = \mathbbm {1}\{\ell (z,h) \ge \beta \}\) in \(\mathcal {G}_{\mathcal {M},\ell }\) has a correspondent \(g^{\prime }_{\beta ^{q},h}(z) = \mathbbm {1}\{\ell ^{\prime }(z,h) \ge \beta ^{q}\}\) in \(\mathcal {G}_{\mathcal {M},\ell ^{\prime }}\) that is such that \(g \equiv g^{\prime }\).
Remark A.19
Condition (A11) is not actually satisfied by many \(\mathcal {H}\), for instance it does not hold for linear regression under the quadratic loss function. However, one can actually consider a \(\mathcal {M} \subset \mathcal {H}\) such that (A11) is true, with \(d_{VC}(\mathcal {M}) = d_{VC}(\mathcal {H})\) and \(L(h^{\star }) = L(h^{\star }_{\mathcal {M}})\), without loss of generality. For example, in linear regression one could consider only hypotheses with parameters bounded by a very large constant \(\gamma\), excluding hypotheses that are unlikely to be the target one. Observe that, in this example, it is better to consider the bounds for relative type I estimation error of unbounded loss functions, rather than consider that the loss function is bounded by a very large constant \(C = \mathcal {O}(\gamma ^2)\), which would generate bad bounds when applying Corollary A.12. The results for unbounded loss functions hold for bounded ones, with p arbitrarily large.
Remark A.20
The main reason we assume that \(\ell (z,h) \ge 1\), for all \(z \in \mathcal {Z}\) and \(h \in \mathcal {H}\), is to simplify the argument before (A15), which could fail if the losses were lesser than one. We believe this assumption could be dropped at the cost of more technical results. Nevertheless, the results in Corollary A.16 present an exponential bound for
for any unbounded loss function \(\ell\). We note that, if we had not imposed this constraint in the loss function, we would have to deal with the denominators in the estimation errors, which could then be zero. This could have been easily accomplished by summing a constant to the denominators and then making it go to zero after the bounds are established, that is, find bounds for
and then make \(\varsigma \rightarrow 0\). This is done in Cortes et al. (2019). By considering loss functions greater or equal to one, we have avoided the need to have heavier notations and more technical details when establishing the convergence of relative estimation errors.
1.3 A.3 Convergence to Zero of Type II Estimation Error
A bound for type II estimation error (11) and relative type II estimation error, defined as
follow immediately from a bound obtained for the respective type I error. This is a consequence of the following elementary inequality, which can be found in part in (Devroye et al., 1996, Lemma 8.2).
Lemma A.21
For any hypotheses space \(\mathcal {H}\) and possible sample \(\mathcal {D}_{N}\),
and, if \(\ell (z,h) \ge 1\), for all \(z \in \mathcal {Z}\) and \(h \in \mathcal {H}\), then
These inequalities yield
and
Proof
The first inequality follows from
For the second one, analogous to the deduction above, we have that
since \(L(\hat{h}^{\mathcal {D}_{N}}) \ge L(h^{\star })\). The inequalities (A20) and (A21) are direct from (A18) and (A19). \(\square\)
Combining Lemma A.21 with Corollaries A.11 and A.12 we obtain the consistency of type II estimation error, when \(d_{VC}(\mathcal {H}) < \infty\) and the loss function is bounded, what also concerns binary loss functions.
Corollary A.22
Fix a hypotheses space \(\mathcal {H}\) and a loss function \(\ell : \mathcal {Z} \times \mathcal {H} \mapsto \mathbb {R}_{+}\), with \(0 \le \ell (z,h) \le C\) for all \(z \in \mathcal {Z}, h \in \mathcal {H}\). Then,
In particular, if \(d_{VC}(\mathcal {H}) < \infty\), not only (A22) converges to zero, but also
with probability one by Borel-Cantelli Lemma.
Finally, combining Lemma A.21 with Corollary A.16, we obtain the consistency of relative type II estimation error when \(d_{VC}(\mathcal {H}) < \infty\), the loss function is unbounded, and P satisfies (A10).
Corollary A.23
Fix a hypotheses space \(\mathcal {H}\), an unbounded loss function \(\ell\) and \(\epsilon> 0\). The following holds:
-
If (A10) holds for a \(p \ge 4\) fixed, then
$$\begin{aligned} \mathbb {P}\Bigg (&\frac{L(\hat{h}^{\mathcal {D}_{N}}) - L(h^{\star })}{L(\hat{h}^{\mathcal {D}_{N}})}> \tau ^{\star } \Lambda (\sqrt{p}) \epsilon \Bigg ) \\&< 12 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}(1-\epsilon /2)^{2}N^{1 - \frac{2}{\sqrt{p}} + \frac{2}{p}}}{16}\right\} \end{aligned}$$ -
If (A10) holds for a \(1< p < 4\) fixed, then
$$\begin{aligned} \mathbb {P}\Bigg (&\frac{L(\hat{h}^{\mathcal {D}_{N}}) - L(h^{\star })}{L(\hat{h}^{\mathcal {D}_{N}})}> \tau ^{\star } \Gamma \left( \sqrt{p},\frac{\epsilon }{N^{\frac{1}{\sqrt{p}} - \frac{1}{p}}}\right) \epsilon \Bigg ) \\&< 12 \exp \left\{ d_{VC}(\mathcal {H})\left( 1 + \ln \frac{2N}{d_{VC}(\mathcal {H})}\right) - \frac{\epsilon ^{2}N^{\frac{2(\sqrt{p} - 1)}{\sqrt{p}} - \frac{2}{\sqrt{p}} + \frac{2}{p}}}{2^{\frac{\sqrt{p} + 6}{2}}} \right\} . \end{aligned}$$
In any case, if \(d_{VC}(\mathcal {H}) < \infty\), then, by Borel-Cantelli Lemma,
with probability one.
This ends the study of type II estimation error convergence.
Appendix B Results of the Experiments
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/
About this article
Cite this article
Marcondes, D., Peixoto, C. Distribution-Free Deviation Bounds and the Role of Domain Knowledge in Learning via Model Selection with Cross-Validation Risk Estimation. Mach Learn 115, 217 (2026). https://doi.org/10.1007/s10994-026-07150-7
Received:
Revised:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s10994-026-07150-7
Keywords
- Deviation bounds
- Cross-validation
- Model selection
- Statistical learning theory
- Unbounded loss function
- Empirical risk minimization