A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes
Alireza F. Pour, Shai Ben-David · 2025
Read A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes by Alireza F. Pour, Shai Ben-David (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-09996.txt.
Introduction
Alireza F. Pour and Shai Ben-David propose a new learning paradigm for problems where the set of candidate models is so large that sample estimates cannot uniformly match true losses. The standard fixes, structural risk minimization and regularization, lean heavily on prior assumptions chosen by the algorithm designer. Their approach instead leans harder on the empirical data itself and needs fewer a priori decisions.
The authors analyze how well the paradigm generalizes and show its value under several common assumptions: nearby points being similar, domains clustering into label-homogeneous regions, Lipschitz labeling rules, and contrastive learning setups. A practical advantage is that the method can exploit such structure without knowing the true parameters in advance, which is how those assumptions usually fail to help in practice.
Catalog record
| CREATOR | Alireza F. Pour, Shai Ben-David |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-09996
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes Alireza F. Pour, Shai Ben-David Abstract We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses. While the common approach to such challenges is SRM (or regularization) based learning algorithms, we propose a novel learning paradigm that relies on stronger incorporation of empirical data and requires less algorithmic decisions to be based on prior assumptions. We analyze the generalization capabilities of our approach and demonstrate its merits in several common learning assumptions, including similarity of close points, clustering of the domain into highly label-homogeneous regions, Lipschitzness assumptions of the labeling rule, and contrastive learning assumptions. Our approach allows utilizing such assumptions without the need to know their true parameters a priori. \DeclareDelimFormat [bib]nametitledelim 1 Introduction We propose a new learning paradigm that closely follows the objective of non-uniform learning, namely, given a set \mathcal{C} of candidate hypotheses , how many samples do we need to compete with the generalization error of some h\in\mathcal{C} ? The canonical approach to non-uniform learning is the Structural Risk Minimization (SRM) algorithm, where the learner structures the hypotheses in a sequence of nested classes. The generalization error that SRM guarantees for any h\in\mathcal{C} then scales with the index of the first class in which h appears, which is implicit in some weighting function w(.) , and the complexity of that class, e.g., its VC dimension. Hence, the success of SRM depends on how well the structure reflects the prior belief about low approximating hypotheses, and how justified that belief is. That is, whether data matching hypotheses are given high weight and/or the class in which they appear is ‘simple’ to learn. For instance, one may assume that the labelling rule is Lipschitz and assign to hypotheses weights that scale with the margin around their decision boundary. The caveat is that the SRM paradigm requires fixing an a priori weighting function and selects its decision rule based on this weighting. We introduce a different learning paradigm (for classes that are too big for enjoying uniform convergence). We introduce a novel parameter of a collection of hypothesis classes: Given a collection \mathbb{H} , the growth function of the collection, denoted by \tau_{\mathbb{H}}(m) , controls the number of equivalence classes of behaviours that the collection induces on a sample of size m . We show that, whenever we group \mathcal{C} into a collection of hypothesis classes \mathbb{H} , for any h\in\mathcal{C} , it is possible to guarantee a generalization error that scales with \tau_{\mathbb{H}}(m) and the complexity of the class to which h belongs. In contrast to a weighting function w(h) , this parameter is uniform over any h - there is no ‘penalty’ to placing a data fitting h in a low weight class. Thus, we shift the focus to finding a grouping of \mathcal{C} that minimizes the growth function of the collection of classes and the complexity of the classes that contain low approximating hypotheses. This paradigm can be directly applied to partial concepts. A partial concept is a function that can be undefined on parts of the domain with the goal of incorporating data assumptions [ 3 ] . Given an assumption (or prior knowledge) about the labelling function, a total function h can be transformed into a set of behaviours such that each behaviour aligns with the assumption on its \{0,1\} part, namely, its support. Our paradigm leads the following approach: given a collection \mathcal{C} of (total) concepts, find a parameter of pairs (a partial function, a finite sample) with the property that (i) it reflects the prior knowledge to enable evaluating to what extent a transformation of a concept into a partial one aligns with the assumption; and (ii) grouping the partial concepts into classes based on this parameter will result in a collection with bounded growth rate. We will show in Section 4 that this covers several common choices such as similarity of close points, clustering of the domain, Lipschitzness assumptions on the labeling rule, and contrastive assumptions. Another difference between our paradigm and SRM is that our proposed paradigm guarantees its error by relying on a compression-based argument. The learner goes over different subsets of the training data, on which it invokes learners \mathcal{A}_{\mathcal{H}},\mathcal{H}\in\mathbb{H} that are specifically designed to learn from the classes \mathcal{H}\in\mathbb{H} . It then estimates the expected error of these predictors on the left out part of the training sample. The learner guarantees the convergence of the error of \mathcal{A}_{\mathcal{H}} on the left out set to its expected error with a failure probability that scales with the size of the subset that is used as input training data to \mathcal{A}_{\mathcal{H}} . Notably, this is one reason that the proposed learner has data-dependent guarantees. Whenever the function belongs to a class with a small data-dependent complexity, we show that the learner needs a smaller subset as training input to learn from that class and thus it will be assigned a large weight when estimating its error on the left out part. We will discuss in Section 2.1 the comparison with SRM in more detail. 2 Learning with Respect to a Collection of Concept Classes In this section, we discuss learnability results with respect to collections of concept classes. For a partial concept class \mathcal{H}\subseteq\{0,1,\star\}^{\mathcal{X}} and any set U\in\mathcal{X}^{*} , we define \mathcal{H}_{|U}=\{h_{|U}:h\in\mathcal{H},h_{|U}\in\{0,1\}^{|U|}\} . Note that based on this definition \mathcal{H}_{|U} will always be a subset of \{0,1\}^{|U|} and we never include in \mathcal{H}_{|U} the behaviours that contain \star . For a labelled set S\in(\mathcal{X}\times\{0,1\})^{*} , we denote by \mathsf{dom}(S) the unlabelled part of S . For a set S , we will write \mathsf{VC}(\mathcal{H},S) as a shorthand notation for the VC dimension \mathsf{VC}(\mathcal{H}_{|{\mathsf{dom}(S)}}) . For any set S and any hypothesis h:\mathcal{X}\rightarrow\{0,1,\star\} we will denote \mathsf{err}(h,S)=\frac{1}{|S|}\sum_{(x,y)\in S}1\{h(x)\neq y\} . For a distribution \mathcal{D} over \mathcal{X}\times\{0,1\} and any hypothesis h:\mathcal{X}\rightarrow\{0,1,\star\} we will define \mathsf{err}(h,\mathcal{D})=\mathbb{P}_{(x,y)\sim\mathcal{D}}\left[h(x)\neq y\right] . Moreover, for any hypothesis class \mathcal{H} , we define \mathsf{err}(\mathcal{H},\mathcal{D})=\inf_{h\in\mathcal{H}}(\mathsf{err}(h,\mathcal{D})) . We now give the definitions of the equivalence relation between hypothesis classes and the growth parameter of a collection. Definition 1 . Let \mathcal{H},\mathcal{H}^{\prime}\subseteq\{0,1,\star\}^{\mathcal{X}} be two (partial) concept classes defined on \mathcal{X} . Given a set U\in\mathcal{X}^{*} , we say \mathcal{H} and \mathcal{H}^{\prime} are equivalent on S if \mathcal{H}_{|T}=\mathcal{H}^{\prime}_{|T} for all T\subseteq U and we denote it by \mathcal{H}\sim_{U}\mathcal{H}^{\prime} . For a family of partial concept classes \mathbb{H} and for any hypothesis class \mathcal{H}\in\mathbb{H} we denote [\mathcal{H}_{\sim_{U}}]_{\mathbb{H}}=\{\mathcal{H}^{\prime}\in\mathbb{H}:\mathcal{H}\sim_{U}\mathcal{H}^{\prime}\} . Moreover, for any set U\in\mathcal{X}^{*} , we denote the set of all equivalence classes generated by members of \mathbb{H} on U by \mathbb{H}_{|U}:=\{[\mathcal{H}_{\sim_{U}}]_{\mathbb{H}}:\mathcal{H}\in\mathbb{H}\} . Definition 2 (Growth parameter \tau_{\mathbb{H}} ) . Let \mathbb{H} be a family of (partial) concept classes. Given a set U\in\mathcal{X}^{*} we define \tau_{\mathbb{H}}(U)=|\mathbb{H}_{|U}| . We denote by \tau_{\mathbb{H}}(m) the maximum number of the equivalence classes generated on sets of size m . Formally, \tau_{\mathbb{H}}(m)=\max_{U\in\mathcal{X}^{m}}\tau_{\mathbb{H}}(U)=\max_{U\in\mathcal{X}^{m}}|\mathbb{H}_{|U}|. Moreover, for a distribution \mathcal{D} and \delta\in(0,1) , we denote by \tau_{\mathbb{H}}(m,\mathcal{D},\delta) the smallest integer such that \mathbb{P}_{S\sim\mathcal{D}^{m}}\left[\tau_{\mathbb{H}}(\mathsf{dom}(S))\leq\tau_{\mathbb{H}}(m,\mathcal{D},\delta)\right]\geq 1-\delta . We will sometimes overload the notation and write \mathcal{H}_{|S} (or \mathbb{H}_{|S} ) for labeled samples S\in(\mathcal{X}\times\{0,1\})^{*} instead of \mathcal{H}_{|\mathsf{dom}(S)} (or \mathbb{H}_{|\mathsf{dom}(S)} ) and write \tau_{\mathbb{H}}(S) instead of \tau_{\mathbb{H}}(\mathsf{dom}(S)) . We