Introduction
A central question in statistical learning theory is how many labeled examples are needed to predict well on unseen data. The classical PAC model [38 , 37 ] answers the uniform case: one rate has to hold for every marginal distribution over the instance space and every target concept in the class. This gives a clean worst-case theory, in which the VC dimension characterizes learnability, but it cannot tell an easy data distribution from a hard one. Marginal-nonuniform learning [4 , 25 ] relaxes exactly this point. The constants in the rate may depend on the marginal distribution D X \mathcal{D}_{X} D X of the unlabeled data, but once D X \mathcal{D}_{X} D X is fixed, the guarantee must hold uniformly over everything else. It sits between uniform PAC learning and universal learning [9 ] , where the constants may depend on the whole data distribution.
Marginal-nonuniform learning has a classical counterpart in concept-nonuniform learning , introduced by Benedek and Itai [ [7 ] and usually called simply nonuniform learning. In this framework, the roles are exchanged: the constants in the rate may depend on the target concept, but the guarantee must hold uniformly over all marginal distributions. This model makes a much larger family of classes learnable, namely all countable unions of VC classes, and it underlies structural risk minimization, Occam’s razor and the minimum description length principle [39 , 8 Rissanen,] 1978, Lugosi and Zeger, 1996]. It distinguishes concepts that are easy to learn from concepts that are hard to learn, whereas marginal-nonuniform learning distinguishes easy marginals from hard ones. Together with uniform and universal learning, these are the four natural notions of learnability obtained by letting the rate depend on the marginal, on the target, on both, or on neither [4 ] . We recall them, in the form needed for this paper, in § 1.1 .
In the realizable case, the possible marginal-nonuniform rates are by now well understood. Hanneke et al. [ [25 ] proved a trichotomy for binary classification: every class is learnable at an exponential rate, at a linear rate, or only at arbitrarily slow rates, and in the linear case the optimal rate is d / n d/n d / n , where d d d is the VC-eluder dimension of Hanneke and Xu [2024]. This dimension can be much smaller than the VC dimension. The work of Brukhim et al. [ [11 ] extended the characterization to multiclass classification, using the uncentered DS-eluder dimension. All of these results assume that some concept in the class labels the data perfectly.
Agnostic marginal-nonuniform learning. Consider an email provider that stores a large archive of messages. The prediction task is chosen only later: filtering spam, detecting phishing, or flagging messages as urgent. The messages, and hence the marginal D X \mathcal{D}_{X} D X , are fixed before the task is known, which is the situation marginal-nonuniform guarantees are designed for. But the labels will come from users, who click carelessly and who disagree with each other: the same newsletter is spam to one user and wanted by another. No concept in the class will label the data perfectly. What the provider can hope for is a filter that is nearly as accurate as the best concept in the class, whatever the task and the behavior of the users turn out to be.
This is the step from realizable to agnostic learning [27 , 29 ] . It is the standard second step in PAC learning: one first studies the realizable case, where the optimal rate is VC ( H ) / n \operatorname{VC}(\mathcal{H})/n VC ( H ) / n , and then drops the assumption on the labels, where the optimal rate becomes VC ( H ) / n \sqrt{\operatorname{VC}(\mathcal{H})/n} VC ( H ) / n . We take the same step in the marginal-nonuniform setting. The learner competes with inf h ∈ H er D ( h ) \inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h) inf h ∈ H er D ( h ) , the constants may depend on the marginal D X \mathcal{D}_{X} D X , and the guarantee must hold for every distribution D \mathcal{D} D over X × Y \mathcal{X}\times\mathcal{Y} X × Y with that marginal. In the example, the archive fixes D X \mathcal{D}_{X} D X , while the task and the behavior of the annotators, i.e., the conditional distribution of the label given the message, are left completely free.
If VC ( H ) < ∞ \operatorname{VC}(\mathcal{H})<\infty VC ( H ) < ∞ , the classical agnostic PAC upper bound applies directly: it holds for every distribution D \mathcal{D} D over X × Y \mathcal{X}\times\mathcal{Y} X × Y , with constants that do not depend on D \mathcal{D} D , so in particular it holds for every distribution with a given marginal D X \mathcal{D}_{X} D X . The classical agnostic PAC lower bound also carries over. Its hard distributions all have the same marginal, namely the uniform distribution on a set of VC ( H ) \operatorname{VC}(\mathcal{H}) VC ( H ) points shattered by H \mathcal{H} H , and only the conditional distribution of the labels depends on the sample size and on the learner. It is therefore a lower bound in the marginal-nonuniform model as well. Combining the two, H \mathcal{H} H is agnostically marginal-nonuniformly learnable at exact rate 1 n \frac{1}{\sqrt{n}} n 1 whenever VC ( H ) < ∞ \operatorname{VC}(\mathcal{H})<\infty VC ( H ) < ∞ . It also provides a fine-grained rate of VC ( H ) n \sqrt{\frac{\operatorname{VC}(\mathcal{H})}{n}} n VC ( H ) . Therefore, we could say that the dependence on the marginal does not help.
Relaxed agnostic marginal-nonuniform learning. The 1 n \frac{1}{\sqrt{n}} n 1 rate is the price of competing with the best concept exactly . In many applications this is more than one needs. Suppose that in the example above the best rule in the class disagrees with the user on 1% of the messages. A guarantee of the form “error at most 1.1%, plus a term of order 1 / n 1/n 1/ n ” is then far more useful than “error at most 1%, plus a term of order 1 / n 1/\sqrt{n} 1/ n ”. When the best concept is already good, a small multiplicative loss costs almost nothing, while the additive 1 / n 1/\sqrt{n} 1/ n term dominates the bound.
This motivates the relaxed agnostic criterion: for a fixed λ ∈ ( 0 , 1 ] \lambda\in(0,1] λ ∈ ( 0 , 1 ] , the learner competes with ( 1 + λ ) inf h ∈ H er D ( h ) (1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h) ( 1 + λ ) inf h ∈ H er D ( h ) . Guarantees of this multiplicative form are common. The weighted majority algorithm competes with a constant factor times the loss of the best expert [31 ] ; efficient algorithms for learning halfspaces with adversarial label noise under suitable distributional assumptions typically guarantee error ( 1 + λ ) OPT + ε (1+\lambda)\operatorname{OPT}+\varepsilon ( 1 + λ ) OPT + ε or C ⋅ OPT + ε C\cdot\operatorname{OPT}+\varepsilon C ⋅ OPT + ε [14 , 3 ] ; and bounds that improve when the best error is small are known as optimistic or first-order bounds. [36 ] . The relaxed criterion also interpolates between the two classical settings: when the data are realizable it is the realizable criterion, and as λ → 0 \lambda\to0 λ → 0 it becomes the agnostic one.
In this case we show that under the relaxed criterion the realizable picture returns, both for the rates and for the fine-grained rates. The achievable rates form the same trichotomy as in the realizable case [25 ] : exponential for finite classes, linear for infinite classes of finite VC dimension, and arbitrarily slow otherwise. Note that even a finite class only has rate 1 n \frac{1}{\sqrt{n}} n 1 under the standard criterion, so the multiplicative slack already matters there. The fine-grained rate is of order d λ n \frac{d}{\lambda n} λn d , where d d d is the uncentered VC-eluder dimension of the class, and the dependence on the marginal is confined to an exponentially small term. So the leading term is again governed by the uncentered VC-eluder dimension rather than by the VC dimension. The VC ( H ) / n \sqrt{\operatorname{VC}(\mathcal{H})/n} VC ( H ) / n barrier of the agnostic case is therefore caused entirely by insisting on the constant 1 in front of the best error.
Main results
We first place our setting among the four learning paradigms mentioned above. A distribution D \mathcal{D} D over X × Y \mathcal{X} \times\mathcal{Y} X × Y consists of its marginal D X \mathcal{D}_{\mathcal{X}} D X and its conditional distribution of the label given the instance, which we denote D Y ∣ X \mathcal{D}_{\mathcal{Y} \mid\mathcal{X}} D Y ∣ X . In the realizable case, D Y ∣ X \mathcal{D}_{\mathcal{Y} \mid\mathcal{X}} D Y ∣ X is given by a target concept; in general it plays the role that the target concept plays there. For λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] and a learner A \mathcal{A} A , write
E λ ( A , D , n ) = E S ∼ D n [ er D ( A S ) ] − ( 1 + λ ) inf h ∈ H er D ( h ) \mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)=\mathbb{E}_{S\sim\mathcal{D}^{n}}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}S)]-(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h) E λ ( A , D , n ) = E S ∼ D n [ er D ( A S )] − ( 1 + λ ) h ∈ H inf er D ( h )
for the excess error, where λ = 0 \lambda=0 λ = 0 is the standard agnostic criterion and λ > 0 \lambda>0 λ > 0 the relaxed one. Adapting Bousquet et al. [ [9 ] and Hanneke et al. [ [25 ] , the four paradigms differ only in the order of the quantifiers. Throughout, we extend every rate function R : N → [ 0 , 1 ] R:\mathbb{N}\to[0,1] R : N → [ 0 , 1 ] to positive real arguments by setting R ( t ) = R ( ⌈ t ⌉ ) R(t)=R(\lceil t\rceil) R ( t ) = R (⌈ t ⌉) for all t > 0 t>0 t > 0 .
Definition 1.1. Let R : N → [ 0 , 1 ] R:\mathbb{N}\to[0,1] R : N → [ 0 , 1 ] be a rate function with lim n → ∞ R ( n ) = 0 \lim_{n\to\infty}R(n)=0 lim n → ∞ R ( n ) = 0 and let λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] .
∃ A ∃ C , c > 0 for all D Y ∣ X for all D X for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) . \exists\mathcal{A}\ \exists C,c>0\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn). ∃ A ∃ C , c > 0 for all D Y ∣ X for all D X for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) . ∃ A for all D Y ∣ X for all D X ∃ C , c > 0 for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) . \exists\mathcal{A}\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \exists C,c>0\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn). ∃ A for all D Y ∣ X for all D X ∃ C , c > 0 for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) . ∃ A for all D Y ∣ X ∃ C , c > 0 for all D X for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) . \exists\mathcal{A}\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \exists C,c>0\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn). ∃ A for all D Y ∣ X ∃ C , c > 0 for all D X for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) . ∃ A for all D X ∃ C , c > 0 for all D Y ∣ X for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) . \exists\mathcal{A}\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \exists C,c>0\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn). ∃ A for all D X ∃ C , c > 0 for all D Y ∣ X for all n ∈ N E λ ( A , D , n ) ≤ C R ( c n ) .
Here D \mathcal{D} D is the distribution over X × Y \mathcal{X}\times\mathcal{Y} X × Y with marginal D X \mathcal{D}_{\mathcal{X}} D X and conditional label distribution D Y ∣ X \mathcal{D}_{\mathcal{Y}\mid\mathcal{X}} D Y ∣ X .
Uniform learning is the classical agnostic PAC model: the constants depend on nothing. In universal learning they may depend on the whole distribution. The two nonuniform models sit in between and are incomparable: in the concept-nonuniform model the constants may depend on how the labels are generated but not on the marginal, and in the marginal-nonuniform model it is the other way round. This paper is about the last paradigm. It is the natural one when the unlabeled data are fixed in advance and the labeling task is not. We state our results at two levels of detail. The first is the rate in the sense of Definition 1.1, which describes the shape of the learning curve. Throughout we assume ∣ H ∣ ≥ 3 |\mathcal{H}|\ge3 ∣ H ∣ ≥ 3 , which only excludes trivial classes [25 ] . Our first result is regarding the rates for standard agnostic and relaxed agnostic settings.
Theorem 1.2. [Rates, informal] Let H \mathcal{H} H be a concept class with ∣ H ∣ ≥ 3 |\mathcal{H}| \ge3 ∣ H ∣ ≥ 3 .
For the standard criterion, the rates are exactly those of uniform agnostic PAC learning. For the relaxed criterion, they are exactly those of realizable marginal-nonuniform learning [25 ] .
Rates alone say nothing about the constants. A bound C R ( c n ) CR(cn) C R ( c n ) in which C C C and c c c may depend on the marginal does not tell us how the class and the marginal together determine the error. This is addressed by the fine-grained rates of Bousquet et al. [ [10 ] , which separate the two dependences into different additive terms: one asks for a bound of the form
E λ ( A , D , n ) ≤ K R ( n ) + δ ( n ) , \mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n) \le K R(n) + \delta(n), E λ ( A , D , n ) ≤ K R ( n ) + δ ( n ) ,
where K K K is a universal constant, the leading term R ( n ) R(n) R ( n ) depends only on the class (and on λ \lambda λ ), and all dependence on the marginal is confined to a lower-order term δ ( n ) = o ( R ( n ) ) \delta(n) = o(R(n)) δ ( n ) = o ( R ( n )) . A matching lower bound asks that a universal constant multiple of R ( n ) R(n) R ( n ) cannot be avoided. The marginal then determines only how long one has to wait before the class-dependent rate takes over, and not the rate itself. The precise definitions are in § 3 .
Theorem 1.3 (Fine-grained rates, informal). 1. If VC ( H ) < ∞ \operatorname{VC}(\mathcal{H}) < \infty VC ( H ) < ∞ , then H \mathcal{H} H is 0 0 0 -agnostically marginal-nonuniformly learnable at exact fine-grained rate VC ( H ) n \sqrt{\frac{\operatorname{VC}(\mathcal{H})}{n}} n VC ( H ) .
If 1 ≤ uVCE ( H ) < ∞ 1 \le\operatorname{uVCE}(\mathcal{H}) < \infty 1 ≤ uVCE ( H ) < ∞ , then for every 0 < λ ≤ 1 0 < \lambda\le1 0 < λ ≤ 1 , H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at exact fine-grained rate uVCE ( H ) λ n \frac{\operatorname{uVCE}(\mathcal{H})}{\lambda n} λn uVCE ( H ) .
Related Works
Agnostic universal and nonuniform learning. The work of Hanneke and Moran [ [20 ] extends the universal learning theory of Bousquet et al. [ [9 ] to the agnostic setting, showing that the optimal universal rate is e − n \mathrm{e}^{-n} e − n , e − o ( n ) \mathrm{e}^{-o(n)} e − o ( n ) , o ( n − 1 / 2 ) o(n^{-1/2}) o ( n − 1/2 ) , or arbitrarily slow, and Hanneke and Xu [ [22 ] characterize the agnostic universal rates of ERMs. Since the constants there may depend on the entire data distribution, every finite class is learnable at rate e − n \mathrm{e}^{-n} e − n even under the standard criterion, whereas in the marginal-nonuniform framework two concepts already force rate 1 n \frac{1}{\sqrt{n}} n 1 unless the criterion is relaxed. In classical comparator-dependent nonuniform learning2 , the agnostic case is handled by structural risk minimization [39 , 32 , 35 ] , and Hanneke et al. [2025c] characterize nonuniform multiclass learnability in both the realizable and the agnostic settings, under both full-information and bandit feedback. To our knowledge, marginal-nonuniform learning has so far been studied only in the realizable case [25 , 11 ] .
Multiplicative slack in the uniform setting. In the uniform learning framework, it is well known that a multiplicative slack yields fast rates. Relative deviation and optimistic bounds [39 , 36 ] show that the error of ERM on n n n examples, over a class of VC dimension d d d , is at most ( 1 + λ ) (1+\lambda) ( 1 + λ ) times the best error in the class plus O ( d log ( n ) / ( λ n ) ) O(d\log(n)/(\lambda n)) O ( d log ( n ) / ( λn )) , and the first-order learner of Mathiasen et al. [ [33 ] (see also Hanneke et al. [2024]) removes the logarithmic factor. Additionally, the work of Asilis et al. [ [1 ] gives a learner whose error is at most c c c times the best error in the class, for a constant c ≤ 2.1 c \le2.1 c ≤ 2.1 , plus the optimal additive term. In statistics, bounds of this form, with a leading constant larger than one, are called nonexact oracle inequalities, and they can give fast rates where exact ones only give slow rates [30 ] . Our results for the relaxed criterion are the marginal-nonuniform analogue, with the VC dimension replaced by the uncentered VC-eluder dimension, which can be much smaller, and with exponential rates for finite classes; neither follows from the uniform bounds.
Learning with a known marginal. Marginal-nonuniform learning is related to learning under a fixed marginal that is known to the learner [6 ] . This is also the idealized limit of semi-supervised learning, where the value of unlabeled data has been studied extensively [5 , 15 , 19 ] . Our fine-grained lower bounds use a single marginal, so they hold even for learners that know D X \mathcal{D}_{\mathcal{X}} D X . In particular, under the standard criterion, knowing the marginal does not improve the fine-grained rate VC ( H ) / n \sqrt{\operatorname{VC}(\mathcal{H})/n} VC ( H ) / n .
Preliminaries
Let X \mathcal{X} X denote a non-empty set which we call the instance space , let Y = { 0 , 1 } \mathcal{Y}=\{0,1\} Y = { 0 , 1 } denote our label space , and let H ⊆ Y X \mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}} H ⊆ Y X be our concept class . The measure-theoretical technicalities have been addressed in appendix § 8 . A data distribution D \mathcal{D} D is a distribution over X × Y \mathcal{X}\times\mathcal{Y} X × Y . For every data distributions D \mathcal{D} D we denote its marginal distribution over X \mathcal{X} X by D X \mathcal{D}_{\mathcal{X}} D X . A learning algorithm A \mathcal{A} A maps a dataset S ∈ ⋃ n = 1 ∞ ( X × Y ) n S\in\bigcup_{n=1}^{\infty}(\mathcal{X}\times\mathcal{Y})^n S ∈ ⋃ n = 1 ∞ ( X × Y ) n to a classifier A S : X → Y \mathcal{A}_S:\mathcal{X}\to\mathcal{Y} A S : X → Y . We allow learning algorithms to use internal randomness, independent of the data; then A S \mathcal{A}_S A S is a random classifier, and er D ( A S ) \operatorname{er}_{\mathcal{D}}(\mathcal{A}_S) er D ( A S ) and all expectations below are also taken over this randomness.
The error rate of a classifier h : X → Y h:\mathcal{X}\to\mathcal{Y} h : X → Y with respect to a data distribution D \mathcal{D} D is er D ( h ) = P ( x , y ) ∼ D [ h ( x ) ≠ y ] \operatorname{er}_{\mathcal{D}}(h)=\mathbb{P}_{(x,y)\sim\mathcal{D}}[h(x)\ne y] er D ( h ) = P ( x , y ) ∼ D [ h ( x ) = y ] . Similarly, given a dataset S ∈ ( X × Y ) n S\in(\mathcal{X}\times\mathcal{Y})^n S ∈ ( X × Y ) n the error rate A S \mathcal{A}_S A S is defined as er D ( A S ) = P ( x , y ) ∼ D [ A S ( x ) ≠ y ] \operatorname{er}_{\mathcal{D}}(\mathcal{A}_S)=\mathbb{P}_{(x,y)\sim\mathcal{D}}[\mathcal{A}_S(x)\ne y] er D ( A S ) = P ( x , y ) ∼ D [ A S ( x ) = y ] and for a concept h ∈ H h\in\mathcal{H} h ∈ H , er D ( h ) = P [ h ( x ) ≠ y ] \operatorname{er}_{\mathcal{D}}(h)=\mathbb{P}[h(x)\ne y] er D ( h ) = P [ h ( x ) = y ] . The works of Hanneke et al. [ [25 ] and Brukhim et al. [ [11 ] focused on the realizable case: namely those distributions satisfying inf h ∈ H er D ( h ) = 0 \inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h)=0 inf h ∈ H er D ( h ) = 0 and study the rate of convergence of the expected error rate E [ er D ( A S ) ] \mathbb{E}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_S)] E [ er D ( A S )] holding uniformly over all label conditionals with the given marginal D X \mathcal{D}_{\mathcal{X}} D X . In contrast, in the context of λ \lambda λ -agnostic learning for a fixed λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] our interest is in characterizing the optimal rates of convergence of the expected excess error rate E [ er D ( A S ) ] − ( 1 + λ ) inf h ∈ H er D ( h ) \mathbb{E}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_S)]-(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h) E [ er D ( A S )] − ( 1 + λ ) inf h ∈ H er D ( h ) holding uniformly over all concept in our concept class for the distribution D \mathcal{D} D (without realizability restrictions). The case λ = 0 \lambda=0 λ = 0 recovers the standard agnostic setting. For λ > 0 \lambda>0 λ > 0 , we call this the relaxed agnostic setting. We extend the definitions of achievable rates from the works of Hanneke et al. [ [25 ] , Brukhim et al. [ [11 ] to apply in the context of λ \lambda λ -agnostic learning. Importantly, in the following definitions, note that the order of the quantifiers allows for the constants C , c C,c C , c to be D X \mathcal{D}_{\mathcal{X}} D X -dependent (which is what distinguishes marginal-nonuniform rates from uniform rates).
Now, we present the definition of agnostic marginal-nonuniform learnability
Definition 3.1. Let H ⊆ Y X \mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}} H ⊆ Y X be a concept class and let R : N → [ 0 , 1 ] \mathcal{R}:\mathbb{N}\to[0,1] R : N → [ 0 , 1 ] be a rate function such that lim n → ∞ R ( n ) = 0 \lim_{n\to\infty}\mathcal{R}(n)=0 lim n → ∞ R ( n ) = 0 . We say
H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at rate R \mathcal{R} R if there is a learning algorithm A \mathcal{A} A such that for all marginal distributions D X \mathcal{D}_{X} D X there exists C , c > 0 C,c>0 C , c > 0 such that for all distributions D \mathcal{D} D with marginal distribution D X \mathcal{D}_{X} D X , E S ∼ D n [ er D ( A S ) ] − ( 1 + λ ) inf h ∈ H er D ( h ) ≤ C R ( c n ) \mathbb{E}_{S\sim\mathcal{D}^{n}}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{S})]-(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h)\le C\mathcal{R}(cn) E S ∼ D n [ er D ( A S )] − ( 1 + λ ) inf h ∈ H er D ( h ) ≤ C R ( c n ) for all n ∈ N n\in\mathbb{N} n ∈ N .
H \mathcal{H} H is not λ \lambda λ -agnostically marginal-nonuniformly learnable at rate faster than R \mathcal{R} R , if for every learning algorithm A \mathcal{A} A , there exists a marginal distribution D X \mathcal{D}_{X} D X such that there exists C , c > 0 C,c>0 C , c > 0 there exists infinitely many n ∈ N n\in\mathbb{N} n ∈ N for each of which there exists a distribution D n \mathcal{D}_{n} D n with marginal D X \mathcal{D}_{X} D X such that E S ∼ D n n [ er D n ( A S ) ] − ( 1 + λ ) inf h ∈ H er D n ( h ) ≥ C R ( c n ) \mathbb{E}_{S\sim\mathcal{D}_{n}^{n}}[\operatorname{er}_{\mathcal{D}_{n}}(\mathcal{A}_{S})]-(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}_{n}}(h)\ge C\mathcal{R}(cn) E S ∼ D n n [ er D n ( A S )] − ( 1 + λ ) inf h ∈ H er D n ( h ) ≥ C R ( c n ) .
H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at exact rate R \mathcal{R} R if H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at R \mathcal{R} R and not faster than rate R \mathcal{R} R .
H \mathcal{H} H requires at least arbitrarily slow rates to be λ \lambda λ -agnostically marginal-nonuniformly learnable if for every rate function R ′ \mathcal{R}' R ′ , the class H \mathcal{H} H is not λ \lambda λ -agnostically marginal-nonuniformly learnable at rate faster than R ′ \mathcal{R}' R ′ .
We also define the fine-grained learning rates as defined in Bousquet et al. [ [10 ] .
Definition 3.2 (Marginal-nonuniform fine-grained rates). Let H \mathcal{H} H be a concept class, let λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , and let R : N → ( 0 , ∞ ) \mathcal{R}:\mathbb{N}\to(0,\infty) R : N → ( 0 , ∞ ) be a function with lim n → ∞ R ( n ) = 0 \lim_{n\to\infty}\mathcal{R}(n)=0 lim n → ∞ R ( n ) = 0 that depends only on H \mathcal{H} H and λ \lambda λ (and not on the distribution).
H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at fine-grained rate R \mathcal{R} R if there are a universal constant K > 0 K>0 K > 0 and a learning algorithm A \mathcal{A} A such that for every marginal distribution D X \mathcal{D}_{X} D X there is a function δ D X : N → [ 0 , ∞ ) \delta_{\mathcal{D}_{X}}:\mathbb{N}\to[0,\infty) δ D X : N → [ 0 , ∞ ) with lim n → ∞ δ D X ( n ) / R ( n ) = 0 \lim_{n\to\infty}\delta_{\mathcal{D}_{X}}(n)/\mathcal{R}(n)=0 lim n → ∞ δ D X ( n ) / R ( n ) = 0 , such that for every distribution D \mathcal{D} D with marginal D X \mathcal{D}_{X} D X and every n ∈ N n\in\mathbb{N} n ∈ N ,
E S ∼ D n [ er D ( A S ) ] − ( 1 + λ ) inf h ∈ H er D ( h ) ≤ K R ( n ) + δ D X ( n ) . \mathbb{E}_{S\sim\mathcal{D}^{n}}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{S})]-(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h)\le K\mathcal{R}(n)+\delta_{\mathcal{D}_{X}}(n). E S ∼ D n [ er D ( A S )] − ( 1 + λ ) h ∈ H inf er D ( h ) ≤ K R ( n ) + δ D X ( n ) . H \mathcal{H} H is not λ \lambda λ -agnostically marginal-nonuniformly learnable at fine-grained rate faster than R \mathcal{R} R if there is a universal constant κ > 0 \kappa>0 κ > 0 such that for every learning algorithm A \mathcal{A} A there is a marginal distribution D X \mathcal{D}_{X} D X such that for infinitely many n ∈ N n\in\mathbb{N} n ∈ N there is a distribution D n \mathcal{D}_{n} D n with marginal D X \mathcal{D}_{X} D X satisfying
E S ∼ D n n [ er D n ( A S ) ] − ( 1 + λ ) inf h ∈ H er D n ( h ) ≥ κ R ( n ) . \mathbb{E}_{S\sim\mathcal{D}_{n}^{n}}[\operatorname{er}_{\mathcal{D}_{n}}(\mathcal{A}_{S})]-(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}_{n}}(h)\ge\kappa\mathcal{R}(n). E S ∼ D n n [ er D n ( A S )] − ( 1 + λ ) h ∈ H inf er D n ( h ) ≥ κ R ( n ) . H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at exact fine-grained rate R \mathcal{R} R if both 1. and 2. hold.
Our main results are based on two combinatorial dimensions; namely, the Vapnik-Chervonenkis (VC) dimension as defined in Vapnik and Chervonenkis [ [38 ] and the uncentered VC-eluder dimension essentially defined in Brukhim et al. [ [11 ] .
Definition 3.3. (H \mathcal{H} H VC-shatters S S S ) We say H \mathcal{H} H VC-shatters a set S S S if the projection of H \mathcal{H} H onto S S S i.e., H ∣ S \mathcal{H}|_{S} H ∣ S has size 2 ∣ S ∣ 2^{|S|} 2 ∣ S ∣ .
(VC dimension) The VC dimension of H \mathcal{H} H , denoted VC ( H ) \operatorname{VC}(\mathcal{H}) VC ( H ) , is the size of the largest set that H \mathcal{H} H VC-shatters, or ∞ \infty ∞ if no such largest set exists.
Definition 3.4. (uncentered VC-eluder sequence) We say that H \mathcal{H} H has an infinite uncentered d d d -VC-eluder sequence B 1 , B 2 , … B_{1},B_{2},\ldots B 1 , B 2 , … if each B k ∈ X d B_{k}\in\mathcal{X}^{d} B k ∈ X d is VC-shattered by concepts in H \mathcal{H} H that are consistent with each other over ⋃ j < k B j \bigcup_{j<k}B_{j} ⋃ j < k B j .
(uncentered VC-eluder dimension) The uncentered VC-eluder dimension of H \mathcal{H} H , denoted by uVCE ( H ) \operatorname{uVCE}(\mathcal{H}) uVCE ( H ) , is defined as largest d d d for which H \mathcal{H} H has an infinite uncentered d d d -VC-eluder sequence. We refer to uncentered 1-VC-eluder sequences as infinite u-eluder sequence. If no infinite sequence exists then uVCE ( H ) = 0 \operatorname{uVCE}(\mathcal{H})=0 uVCE ( H ) = 0 and uVCE ( H ) = ∞ \operatorname{uVCE}(\mathcal{H})=\infty uVCE ( H ) = ∞ if there exists an infinite d d d -VC-eluder sequence for every d ∈ N d\in\mathbb{N} d ∈ N .
The centered version of the above dimension can be defined analogously by fixing a concept h ∗ ∈ Y X h^{*} \in\mathcal{Y}^{\mathcal{X}} h ∗ ∈ Y X and replacing the consistency condition by the requirement that every concept in the corresponding witnessing family agrees with h ∗ h^{*} h ∗ on all previously selected points. See Appendix § 9 and Brukhim et al. [ [11 ] for a detailed comparison.
We now recall a few other standard notions. For every concept class H ⊆ Y X \mathcal{H} \subseteq\mathcal{Y}^{\mathcal{X}} H ⊆ Y X , every finite sequence of instances U = ( x 1 , … , x n ) ∈ X n \mathcal{U} = (x_{1}, \ldots, x_{n}) \in\mathcal{X}^{n} U = ( x 1 , … , x n ) ∈ X n and every concept h ∈ Y X h \in\mathcal{Y}^{\mathcal{X}} h ∈ Y X we define the corresponding version space by V U , h = { f ∈ H : f ( x i ) = h ( x i ) for all i ∈ [ n ] } \mathcal{V}_{\mathcal{U},h} = \{f \in\mathcal{H} : f(x_{i}) = h(x_{i}) \text{ for all } i \in[n]\} V U , h = { f ∈ H : f ( x i ) = h ( x i ) for all i ∈ [ n ]} . Similarly, we can do so, if we have a finite sequence of instance-label pairs. In addition, we define the disagreement region of a class H \mathcal{H} H by DIS ( H ) = { x ∈ X ∣ there exists f , g ∈ H such that f ( x ) ≠ g ( x ) } \operatorname{DIS}(\mathcal{H}) = \{x \in\mathcal{X} \mid\text{there exists } f,g \in\mathcal{H} \text{ such that } f(x) \ne g(x)\} DIS ( H ) = { x ∈ X ∣ there exists f , g ∈ H such that f ( x ) = g ( x )} . Finally, for every class V ⊆ Y X \mathcal{V} \subseteq\mathcal{Y}^{\mathcal{X}} V ⊆ Y X and n ∈ N n \in\mathbb{N} n ∈ N , let SH ( V , n ) = { ( x 1 , … , x n ) ∈ X n : { ( h ( x 1 ) , … , h ( x n ) ) : h ∈ V } = { 0 , 1 } n } \operatorname{SH}(\mathcal{V},n) = \{(x_{1}, \ldots, x_{n}) \in\mathcal{X}^{n} : \{(h(x_{1}), \ldots, h(x_{n})) : h \in\mathcal{V}\} = \{0,1\}^{n}\} SH ( V , n ) = {( x 1 , … , x n ) ∈ X n : {( h ( x 1 ) , … , h ( x n )) : h ∈ V } = { 0 , 1 } n } be the set of n n n -tuples that are VC-shattered by V \mathcal{V} V . A tuple with a repeated point is never shattered.
Definition 3.5 (Distributional VC dimension). For V ⊆ H \mathcal{V} \subseteq\mathcal{H} V ⊆ H , a marginal distribution D X \mathcal{D}_{\mathcal{X}} D X and an integer k ≥ 0 k \ge0 k ≥ 0 , we write VC D X ( V ) ≤ k \operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}) \le k VC D X ( V ) ≤ k if D X k + 1 ( SH ( V , k + 1 ) ) = 0 \mathcal{D}_{\mathcal{X}}^{k+1}(\operatorname{SH}(\mathcal{V},k+1)) = 0 D X k + 1 ( SH ( V , k + 1 )) = 0 , i.e., an i.i.d. sample of k + 1 k+1 k + 1 points from D X \mathcal{D}_{\mathcal{X}} D X is almost surely not VC-shattered by V \mathcal{V} V .
If VC D X ( V ) ≤ k \operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}) \le k VC D X ( V ) ≤ k , then almost surely the projection of V \mathcal{V} V onto an i.i.d. sample from D X \mathcal{D}_{\mathcal{X}} D X of any size has VC dimension at most k k k , and the same holds for every subclass of V \mathcal{V} V . In particular VC D X ( V ′ ) ≤ VC D X ( V ) \operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}') \le\operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}) VC D X ( V ′ ) ≤ VC D X ( V ) whenever V ′ ⊆ V \mathcal{V}' \subseteq\mathcal{V} V ′ ⊆ V . Our upper bounds use a first-order learner whose guarantee depends only on the distributional VC dimension; Appendix § 7 explains why this is needed and shows that such a learner exists.
For V ⊆ H \mathcal{V} \subseteq\mathcal{H} V ⊆ H write τ D , V = inf h ∈ V er D ( h ) \tau_{\mathcal{D},\mathcal{V}} = \inf_{h \in\mathcal{V}} \operatorname{er}_{\mathcal{D}}(h) τ D , V = inf h ∈ V er D ( h ) and τ D = τ D , H \tau_{\mathcal{D}} = \tau_{\mathcal{D},\mathcal{H}} τ D = τ D , H .
Definition 3.6 (First-order learner). A first-order learner is a (possibly randomized) learning rule B \mathcal{B} B that takes a class V ⊆ H \mathcal{V} \subseteq\mathcal{H} V ⊆ H and a sample S S S , and outputs a classifier B V ( S ) \mathcal{B}_{\mathcal{V}}(S) B V ( S ) , such that for a universal constant B ≥ 1 B \ge1 B ≥ 1 the following holds. For every class V \mathcal{V} V that is H \mathcal{H} H or a version space of H \mathcal{H} H , every distribution D \mathcal{D} D over X × Y \mathcal{X} \times\mathcal{Y} X × Y , every k ≥ 1 k \ge1 k ≥ 1 with VC D X ( V ) ≤ k \operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}) \le k VC D X ( V ) ≤ k , and every n ≥ 1 n \ge1 n ≥ 1 ,
E S ∼ D n [ er D ( B V ( S ) ) ] ≤ τ D , V + B ( τ D , V k n + k n ) . (1) \mathbb{E}_{S \sim\mathcal{D}^{n}}[\operatorname{er}_{\mathcal{D}}(\mathcal{B}_{\mathcal{V}}(S))] \le\tau_{\mathcal{D},\mathcal{V}} + B\left(\sqrt{\frac{\tau_{\mathcal{D},\mathcal{V}}k}{n}} + \frac{k}{n}\right). \tag*{(1)} E S ∼ D n [ er D ( B V ( S ))] ≤ τ D , V + B ( n τ D , V k + n k ) . (1) The rule uses only V \mathcal{V} V and S S S ; it does not know D X \mathcal{D}_{\mathcal{X}} D X , k k k or τ D , V \tau_{\mathcal{D},\mathcal{V}} τ D , V . The expectation includes the internal randomness of B \mathcal{B} B . The existence of such a learner has been discussed in Appendix § 7 .
Standard Agnostic Setting
In this section we note that in the standard agnostic setting the dependence on the marginal brings no benefit: both the rates and the fine-grained rates are those of uniform agnostic PAC learning. The upper bounds are uniform bounds, so they hold in particular in the marginal-nonuniform model. We also note that the classical lower bound can be realized with a single marginal i.e. the uniform distribution, so that it also holds in the marginal-nonuniform model. We first prove the fine-grained statement and then deduce the rates from it.
Theorem 4.1 (Fine-grained rate, standard agnostic). Let H \mathcal{H} H be a concept class with d = VC ( H ) < ∞ d = \operatorname{VC}(\mathcal{H}) < \infty d = VC ( H ) < ∞ .
(Upper bound.) There is a learner A \mathcal{A} A such that for every distribution D \mathcal{D} D and every n ≥ 1 n \ge1 n ≥ 1 ,
E S ∼ D n [ er D ( A S ) ] − τ D ≤ B ( d n + d n ) , \mathbb{E}_{S \sim\mathcal{D}^{n}}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{S})] - \tau_{\mathcal{D}} \le B\left(\sqrt{\frac{d}{n}} + \frac{d}{n}\right), E S ∼ D n [ er D ( A S )] − τ D ≤ B ( n d + n d ) , where B B B is the constant of the first-order learner in Definition 3.6 .
(Lower bound.) There is a marginal distribution D X \mathcal{D}_{X} D X such that for every learner A \mathcal{A} A and every n ≥ d n \ge d n ≥ d there is a distribution D \mathcal{D} D with marginal D X \mathcal{D}_{X} D X satisfying
E S ∼ D n [ er D ( A S ) ] − τ D ≥ c d n , \mathbb{E}_{S\sim\mathcal{D}^{n}}\left[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{S})\right]-\tau_{\mathcal{D}} \ge c\sqrt{\frac{d}{n}}, E S ∼ D n [ er D ( A S ) ] − τ D ≥ c n d ,
where c > 0 c > 0 c > 0 is a universal constant.
In particular, H \mathcal{H} H is 0-agnostically marginal-nonuniformly learnable at exact fine-grained rate d n \sqrt{\frac{d}{n}} n d .
Proof. Upper bound. Run the first-order learner on the whole class, A = B H \mathcal{A}=\mathcal{B}_{\mathcal{H}} A = B H . Every marginal D X \mathcal{D}_{X} D X satisfies VC D X ( H ) ≤ VC ( H ) = d \operatorname{VC}_{\mathcal{D}_{X}}(\mathcal{H})\le\operatorname{VC}(\mathcal{H})=d VC D X ( H ) ≤ VC ( H ) = d , so (1) applies with V = H V=\mathcal{H} V = H and k = d k=d k = d . With τ D ≤ 1 \tau_{\mathcal{D}}\le1 τ D ≤ 1 , Definition 3.6 gives the bound. The leading term B d / n B\sqrt{d/n} B d / n depends only on d d d , and the remaining term B d / n Bd/n B d / n is of lower order, so this is a fine-grained upper bound.
Lower bound. This is the classical lower bound for agnostic PAC learning [35 Section 28.2] . The point is that its proof already works with a single marginal. For any class H \mathcal{H} H with VC ( H ) = d \operatorname{VC}(\mathcal{H})=d VC ( H ) = d , all the hard distributions used there have the same marginal: the uniform distribution D X \mathcal{D}_{X} D X on a fixed set { x 1 , … , x d } \{x_{1},\ldots,x_{d}\} { x 1 , … , x d } that is VC-shattered by H \mathcal{H} H . Only the conditional distribution of the labels, which is slightly biased towards a labeling of the shattered set, is chosen depending on n n n and on the learner A \mathcal{A} A . Hence for this one marginal D X \mathcal{D}_{X} D X , for every learner A \mathcal{A} A and every n ≥ d n\ge d n ≥ d , there is a distribution D \mathcal{D} D with marginal D X \mathcal{D}_{X} D X whose expected excess error is at least c d / n c\sqrt{d/n} c d / n . In the notation of Definition 3.2, the upper bound gives item 1 with R ( n ) = d / n R(n)=\sqrt{d/n} R ( n ) = d / n , K = B K=B K = B and δ ( n ) = B d n = o ( R ( n ) ) \delta(n)=B\frac{d}{n}=o(R(n)) δ ( n ) = B n d = o ( R ( n )) , and the lower bound gives item 2 with κ = c \kappa=c κ = c , since it holds for every n ≥ d n\ge d n ≥ d .
Theorem 4.2 (Rates, standard agnostic). Let H \mathcal{H} H be a concept class with ∣ H ∣ ≥ 3 |\mathcal{H}|\ge3 ∣ H ∣ ≥ 3 .
H \mathcal{H} H is 0-agnostically marginal-nonuniformly learnable at exact rate 1 n \frac{1}{\sqrt{n}} n 1 if and only if VC ( H ) < ∞ \operatorname{VC}(\mathcal{H})<\infty VC ( H ) < ∞ .
H \mathcal{H} H requires arbitrarily slow rates to be 0-agnostically marginal-nonuniformly learnable if and only if VC ( H ) = ∞ \operatorname{VC}(\mathcal{H})=\infty VC ( H ) = ∞ .
Proof. Since ∣ H ∣ ≥ 2 |\mathcal{H}|\ge2 ∣ H ∣ ≥ 2 , some point receives two different labels from concepts in H \mathcal{H} H , so VC ( H ) ≥ 1 \operatorname{VC}(\mathcal{H})\ge1 VC ( H ) ≥ 1 .
Finite VC dimension. Let d = VC ( H ) < ∞ d=\operatorname{VC}(\mathcal{H})<\infty d = VC ( H ) < ∞ . By the upper bound of Theorem 4.1 , for n ≥ d n\ge d n ≥ d the excess error is at most B ( d / n + d / n ) ≤ 2 B d / n B(\sqrt{d/n}+d/n)\le2B\sqrt{d/n} B ( d / n + d / n ) ≤ 2 B d / n , and for n < d n<d n < d it is at most 1 ≤ d / n ≤ 2 B d / n 1\le\sqrt{d/n}\le2B\sqrt{d/n} 1 ≤ d / n ≤ 2 B d / n , since B ≥ 1 B\ge1 B ≥ 1 . So for every n n n the excess error is at most 2 B d ⋅ ( 1 / n ) 2B\sqrt{d}\cdot(1/\sqrt{n}) 2 B d ⋅ ( 1/ n ) , and H \mathcal{H} H is learnable at rate 1 / n 1/\sqrt{n} 1/ n , with constants that do not even depend on the marginal. By the lower bound of Theorem 4.1 , a single marginal forces excess error at least c d ⋅ ( 1 / n ) c\sqrt{d}\cdot(1/\sqrt{n}) c d ⋅ ( 1/ n ) at every n ≥ d n\ge d n ≥ d , so H \mathcal{H} H is not learnable at a rate faster than 1 / n 1/\sqrt{n} 1/ n . This proves the “if” direction of the first item, and it also shows that H \mathcal{H} H does not require arbitrarily slow rates.
Infinite VC dimension. Every realizable distribution, i.e., one whose labels are given by some f ∈ H f\in\mathcal{H} f ∈ H , is allowed in our model and thus τ D = 0 \tau_{\mathcal{D}}=0 τ D = 0 , so for it the excess error is the error itself. Hence any lower bound for realizable marginal-nonuniform learning is also a lower bound here. If VC ( H ) = ∞ \operatorname{VC}(\mathcal{H})=\infty VC ( H ) = ∞ , the class requires arbitrarily slow rates already in the realizable case [25 Theorem 3] , hence also in the 0-agnostic case. In particular it is not learnable at rate 1 / n 1/\sqrt{n} 1/ n , which proves the “only if” direction of the first item.
Relaxed Agnostic Setting
Theorem 5.1 (Rates, relaxed agnostic). Let H \mathcal{H} H be a concept class with ∣ H ∣ ≥ 3 |\mathcal{H}|\ge3 ∣ H ∣ ≥ 3 and let 0 < λ ≤ 1 0<\lambda\le1 0 < λ ≤ 1 .
H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at exact rate e − n e^{-n} e − n if and only if H \mathcal{H} H is finite.
H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at exact rate 1 n \frac{1}{n} n 1 if and only if H \mathcal{H} H is infinite and $\operatorname{VC}(\mathcal{H})<\infty.
H \mathcal{H} H requires arbitrarily slow rates to be λ \lambda λ -agnostically marginal-nonuniformly learnable if and only if VC ( H ) = ∞ \operatorname{VC}(\mathcal{H}) = \infty VC ( H ) = ∞ .
The three cases are exhaustive and mutually exclusive. For the first two cases, we establish matching upper and lower bounds; the third requires only a lower bound.
Lower bounds. As in the standard setting, every realizable distribution has τ D = 0 \tau_{\mathcal{D}} = 0 τ D = 0 , so for it the relaxed excess error E [ er D ( A S ) ] − ( 1 + λ ) τ D \mathbb{E}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{S})] - (1+\lambda)\tau_{\mathcal{D}} E [ er D ( A S )] − ( 1 + λ ) τ D is the error itself, whatever λ \lambda λ is. Hence the lower bounds of the realizable trichotomy [25 Theorem 3] carry over: a class with ∣ H ∣ ≥ 3 |\mathcal{H}| \ge3 ∣ H ∣ ≥ 3 is not learnable faster than e − n e^{-n} e − n , an infinite class is not learnable faster than 1 n \frac{1}{n} n 1 , and a class with VC ( H ) = ∞ \operatorname{VC}(\mathcal{H}) = \infty VC ( H ) = ∞ requires arbitrarily slow rates.
Upper bounds. For a finite class we prove an exponential rate in Theorem 5.2 below. For an infinite class with finite VC dimension, Lemma C.1 gives 1 ≤ uVCE ( H ) < ∞ 1 \le\operatorname{uVCE}(\mathcal{H}) < \infty 1 ≤ uVCE ( H ) < ∞ , and the upper bound of Theorem 5.3 gives excess error at most K uVCE ( H ) λ n + C e − c n K\frac{\operatorname{uVCE}(\mathcal{H})}{\lambda n} + Ce^{-cn} K λn uVCE ( H ) + C e − c n , which is a rate 1 n \frac{1}{n} n 1 .
Finite classes
For a finite class, a plain ERM already achieves an exponential rate. The idea is that ERM compares two concepts only on the points where they disagree. On the disagreement region of the best concept and a concept with error more than ( 1 + λ ) τ D (1+\lambda)\tau_{\mathcal{D}} ( 1 + λ ) τ D , the best concept is correct noticeably more often than not, and for a fixed marginal this region has probability bounded away from 0. So ERM prefers the worse concept only with exponentially small probability. This uses λ > 0 \lambda> 0 λ > 0 in an essential way: under the standard criterion even a class of two concepts has rate 1 n \frac{1}{\sqrt{n}} n 1 .
Theorem 5.2 (Exponential rate for finite classes). Let H \mathcal{H} H be a finite concept class and 0 < λ ≤ 1 0 < \lambda\le1 0 < λ ≤ 1 . Let A \mathcal{A} A be any ERM over H \mathcal{H} H . For every marginal D X \mathcal{D}_{X} D X , let
δ D X = min { D X ( DIS ( { h , g } ) ) : h , g ∈ H , D X ( DIS ( { h , g } ) ) > 0 } , \delta_{\mathcal{D}_{X}} = \min\{\mathcal{D}_{X}(\operatorname{DIS}(\{h,g\})) : h,g \in\mathcal{H},\ \mathcal{D}_{X}(\operatorname{DIS}(\{h,g\})) > 0\}, δ D X = min { D X ( DIS ({ h , g })) : h , g ∈ H , D X ( DIS ({ h , g })) > 0 } , with δ D X = 1 \delta_{\mathcal{D}_{X}} = 1 δ D X = 1 if this set is empty. Then for every distribution D \mathcal{D} D with marginal D X \mathcal{D}_{X} D X and every n ≥ 1 n \ge1 n ≥ 1 ,
E S ∼ D n [ er D ( A S ) ] − ( 1 + λ ) τ D ≤ ∣ H ∣ exp ( − λ 2 δ D X 19 n ) . \mathbb{E}_{S \sim\mathcal{D}^{n}}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{S})] - (1+\lambda)\tau_{\mathcal{D}} \le|\mathcal{H}|\exp\left(-\frac{\lambda^{2}\delta_{\mathcal{D}_{X}}}{19}n\right). E S ∼ D n [ er D ( A S )] − ( 1 + λ ) τ D ≤ ∣ H ∣ exp ( − 19 λ 2 δ D X n ) . The constants ∣ H ∣ |\mathcal{H}| ∣ H ∣ and λ 2 δ D X 19 \frac{\lambda^{2}\delta_{\mathcal{D}_{X}}}{19} 19 λ 2 δ D X depend on H \mathcal{H} H , λ \lambda λ and D X \mathcal{D}_{X} D X but not on the conditional distribution of the labels, so this is an exponential marginal-nonuniform rate.
Proof. Fix D \mathcal{D} D with marginal D X \mathcal{D}_{X} D X , and let h ∗ ∈ H h^{*} \in\mathcal{H} h ∗ ∈ H have er D ( h ∗ ) = τ D \operatorname{er}_{\mathcal{D}}(h^{*}) = \tau_{\mathcal{D}} er D ( h ∗ ) = τ D ; it exists because H \mathcal{H} H is finite. Call a concept h ∈ H h \in\mathcal{H} h ∈ H bad if er D ( h ) > ( 1 + λ ) τ D \operatorname{er}_{\mathcal{D}}(h) > (1+\lambda)\tau_{\mathcal{D}} er D ( h ) > ( 1 + λ ) τ D . If ERM outputs a concept that is not bad, its error is at most ( 1 + λ ) τ D (1+\lambda)\tau_{\mathcal{D}} ( 1 + λ ) τ D ; otherwise we bound its error by 1. Hence
E [ er D ( A S ) ] ≤ ( 1 + λ ) τ D + P [ A S is bad ] , (2) \mathbb{E}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{S})] \le(1+\lambda)\tau_{\mathcal{D}} + \mathbb{P}[\mathcal{A}_{S}\text{ is bad}], \tag*{(2)} E [ er D ( A S )] ≤ ( 1 + λ ) τ D + P [ A S is bad ] , (2)
and it remains to show that ERM rarely outputs a bad concept. Fix a bad concept h h h .
Only the disagreement region matters. Let R = DIS ( { h , h ∗ } ) R = \operatorname{DIS}(\{h,h^{*}\}) R = DIS ({ h , h ∗ }) be the set of points where h h h and h ∗ h^{*} h ∗ disagree, and let s = D X ( R ) s = \mathcal{D}_{X}(R) s = D X ( R ) . Outside R R R the two concepts make exactly the same mistakes. Inside R R R the labels are binary, so exactly one of them is wrong: h h h makes a mistake exactly when h ∗ h^{*} h ∗ is correct. Let q = P ( X , Y ) ∼ D [ h ∗ ( X ) ≠ Y ∣ X ∈ R ] q = \mathbb{P}_{(X,Y)\sim\mathcal{D}}[h^{*}(X) \ne Y \mid X \in R] q = P ( X , Y ) ∼ D [ h ∗ ( X ) = Y ∣ X ∈ R ] be the probability that h ∗ h^{*} h ∗ errs on a point of R R R (this is well defined, since s > 0 s > 0 s > 0 as we show next). Then
er D ( h ) − er D ( h ∗ ) = s ( 1 − q ) − s q = s ( 1 − 2 q ) . \operatorname{er}_{\mathcal{D}}(h) - \operatorname{er}_{\mathcal{D}}(h^{*}) = s(1-q) - sq = s(1-2q). er D ( h ) − er D ( h ∗ ) = s ( 1 − q ) − s q = s ( 1 − 2 q ) .
On the disagreement region, h ∗ h^{*} h ∗ is right noticeably more often than wrong. Since h h h is bad, er D ( h ) − er D ( h ∗ ) > λ τ D ≥ 0 \operatorname{er}_{\mathcal{D}}(h) - \operatorname{er}_{\mathcal{D}}(h^{*}) > \lambda\tau_{\mathcal{D}} \ge0 er D ( h ) − er D ( h ∗ ) > λ τ D ≥ 0 , so s > 0 s > 0 s > 0 . Also τ D = er D ( h ∗ ) ≥ s q \tau_{\mathcal{D}} = \operatorname{er}_{\mathcal{D}}(h^{*}) \ge sq τ D = er D ( h ∗ ) ≥ s q , because the mistakes of h ∗ h^{*} h ∗ on R R R are part of all its mistakes. Hence s ( 1 − 2 q ) > λ s q s(1-2q) > \lambda sq s ( 1 − 2 q ) > λ s q , i.e., q < 1 2 + λ q < \frac{1}{2+\lambda} q < 2 + λ 1 , and with λ ≤ 1 \lambda\le1 λ ≤ 1 ,
1 2 − q > 1 2 − 1 2 + λ = λ 2 ( 2 + λ ) ≥ λ 6 . (3) \frac{1}{2} - q > \frac{1}{2} - \frac{1}{2+\lambda} = \frac{\lambda}{2(2+\lambda)} \ge\frac{\lambda}{6}. \tag*{(3)} 2 1 − q > 2 1 − 2 + λ 1 = 2 ( 2 + λ ) λ ≥ 6 λ . (3)
Moreover, s > 0 s > 0 s > 0 means that the set in the definition of δ D X \delta_{\mathcal{D}_X} δ D X is nonempty and contains s s s , so s ≥ δ D X s \ge\delta_{\mathcal{D}_X} s ≥ δ D X .
ERM rarely prefers h h h to h ∗ h^* h ∗ . Let N N N be the number of sample points that fall in R R R , and let M M M be the number of those at which h ∗ h^* h ∗ makes a mistake. On the sample, outside R R R the two concepts have the same mistakes, and inside R R R , h ∗ h^* h ∗ makes M M M mistakes and h h h makes N − M N-M N − M . ERM can output h h h only if h h h makes at most as many mistakes on S S S as h ∗ h^* h ∗ , that is, only if M ≥ N / 2 M \ge N/2 M ≥ N /2 . We bound this probability in two steps.
Given N N N . Conditioned on which sample points fall in R R R , these points are i.i.d. draws from D \mathcal{D} D conditioned on X ∈ R X \in R X ∈ R , so M M M is a sum of N N N independent indicators with mean q q q . By Hoeffding’s inequality and (3) ,
P [ M ≥ N 2 ∣ N ] ≤ exp ( − 2 N ( 1 2 − q ) 2 ) ≤ e − t N , where t = λ 2 18 . \mathbb{P}\left[M \ge\frac{N}{2}\mid N\right] \le\exp\left(-2N\left(\frac{1}{2}-q\right)^2\right) \le e^{-tN}, \text{ where } t=\frac{\lambda^2}{18}. P [ M ≥ 2 N ∣ N ] ≤ exp ( − 2 N ( 2 1 − q ) 2 ) ≤ e − tN , where t = 18 λ 2 .
This also holds when N = 0 N=0 N = 0 , where the right side equals 1 1 1 .
Averaging over N N N . Each sample point falls in R R R independently with probability s s s , so N N N is binomial with parameters n n n and s s s . Hence, using 1 − u ≤ e − u 1-u\le e^{-u} 1 − u ≤ e − u ,
E [ e − t N ] = ( 1 − s ( 1 − e − t ) ) n ≤ exp ( − s n ( 1 − e − t ) ) . \mathbb{E}\left[e^{-tN}\right] = \left(1-s\left(1-e^{-t}\right)\right)^n \le\exp\left(-sn\left(1-e^{-t}\right)\right). E [ e − tN ] = ( 1 − s ( 1 − e − t ) ) n ≤ exp ( − s n ( 1 − e − t ) ) .
Since t ≤ 1 18 t\le\frac{1}{18} t ≤ 18 1 , we have 1 − e − t ≥ t 1 + t ≥ 18 t 19 = λ 2 19 1-e^{-t}\ge\frac{t}{1+t}\ge\frac{18t}{19}=\frac{\lambda^2}{19} 1 − e − t ≥ 1 + t t ≥ 19 18 t = 19 λ 2 .
Combining the two steps and s ≥ δ D X s\ge\delta_{\mathcal{D}_X} s ≥ δ D X ,
P [ A S = h ] ≤ P [ M ≥ N 2 ] ≤ exp ( − λ 2 s 19 n ) ≤ exp ( − λ 2 δ D X 19 n ) . \mathbb{P}[\mathcal{A}_S=h]\le\mathbb{P}\left[M\ge\frac{N}{2}\right]\le\exp\left(-\frac{\lambda^2s}{19}n\right)\le\exp\left(-\frac{\lambda^2\delta_{\mathcal{D}_X}}{19}n\right). P [ A S = h ] ≤ P [ M ≥ 2 N ] ≤ exp ( − 19 λ 2 s n ) ≤ exp ( − 19 λ 2 δ D X n ) .
Union bound. There are at most ∣ H ∣ |\mathcal{H}| ∣ H ∣ bad concepts, so P [ A S is bad ] ≤ ∣ H ∣ exp ( − λ 2 δ D X n / 19 ) \mathbb{P}[\mathcal{A}_S\text{ is bad}]\le|\mathcal{H}|\exp\left(-\lambda^2\delta_{\mathcal{D}_X}n/19\right) P [ A S is bad ] ≤ ∣ H ∣ exp ( − λ 2 δ D X n /19 ) . Together with (2) this proves the theorem. (If no concept is bad, the bound holds trivially.) □ \square □
Fine-grained rates
We now turn to the fine-grained rates for infinite classes of finite VC dimension. We state the result here and prove the upper and lower bounds in the next two subsections.
Theorem 5.3 (Fine-grained rate, relaxed agnostic). Let 0 < λ ≤ 1 0 < \lambda\le1 0 < λ ≤ 1 and 1 ≤ uVCE ( H ) < ∞ 1 \le\operatorname{uVCE}(\mathcal{H}) < \infty 1 ≤ uVCE ( H ) < ∞ . Then H \mathcal{H} H is λ \lambda λ -agnostically marginal-nonuniformly learnable at exact fine-grained rate uVCE ( H ) λ n \frac{\operatorname{uVCE}(\mathcal{H})}{\lambda n} λn uVCE ( H ) .
Theorem 5.3 follows from Theorems 5.4 and 5.9, with R ( n ) = uVCE ( H ) λ n R(n)=\frac{\operatorname{uVCE}(\mathcal{H})}{\lambda n} R ( n ) = λn uVCE ( H ) , which depends only on H \mathcal{H} H and λ \lambda λ . The upper bound gives item 1 of Definition 3.2 with the constant K K K of Theorem 5.4, which depends only on the universal constant B B B of the first-order learner, and with δ D X ( n ) = C e − c n \delta_{\mathcal{D}_X}(n)=Ce^{-cn} δ D X ( n ) = C e − c n , which is o ( R ( n ) ) o(R(n)) o ( R ( n )) . The lower bound gives item 2 with κ = 1 2048 \kappa=\frac{1}{2048} κ = 2048 1 , along the infinite sequence n 1 < n 2 < ⋯ n_1<n_2<\cdots n 1 < n 2 < ⋯ of Theorem 5.9.
Fine-grained upper bound
Theorem 5.4. Let 0 < λ ≤ 1 0 < \lambda\le1 0 < λ ≤ 1 and suppose 1 ≤ d = uVCE ( H ) < ∞ 1 \le d=\operatorname{uVCE}(\mathcal{H}) < \infty 1 ≤ d = uVCE ( H ) < ∞ . There are a learner A λ A_\lambda A λ and a constant K K K depending only on B B B from the first-order learner as in Definition 3.6 such that for every marginal D X \mathcal{D}_X D X there are C , c > 0 C,c>0 C , c > 0 , depending on D X \mathcal{D}_X D X , λ \lambda λ and H \mathcal{H} H only, with
E S ∼ D n [ er D ( A λ , S ) ] − ( 1 + λ ) τ D ≤ K d λ n + C e − c n \mathbb{E}_{S\sim\mathcal{D}^n}\left[\operatorname{er}_{\mathcal{D}}(A_{\lambda,S})\right]-(1+\lambda)\tau_{\mathcal{D}}\le K\frac{d}{\lambda n}+Ce^{-cn} E S ∼ D n [ er D ( A λ , S ) ] − ( 1 + λ ) τ D ≤ K λn d + C e − c n for every D \mathcal{D} D with marginal D X \mathcal{D}_X D X and every n ≥ 1 n\ge1 n ≥ 1 .
Idea. In the realizable case Brukhim et al. [ [11 ] , the learner uses part of the sample to form a version space. After enough samples this version space is “simple”: a fresh sample from D X \mathcal{D}_{\mathcal{X}} D X almost never contains d + 1 d+1 d + 1 points that it shatters. A good learner is then run inside this simple class. In the agnostic case the sample is not consistent with any single concept, so we cannot form this version space. However, a good concept h h h makes few mistakes, so a small random subsample is likely to contain none of them. The version space of such a clean subsample is again simple, and it still contains h h h . We do not know which subsamples are clean, so we try all of them: every subsample gives one candidate predictor, obtained by running the first-order learner inside its version space. Finally, we choose among the candidates on fresh data using exponential weights. The factor ( 1 + λ ) (1+\lambda) ( 1 + λ ) is what pays for this last selection step.
The learner
Fix η = λ 16 \eta= \frac{\lambda}{16} η = 16 λ and p = λ 2 1024 p = \frac{\lambda^2}{1024} p = 1024 λ 2 . For n < 6 n < 6 n < 6 the learner outputs a fixed h ∈ H h \in\mathcal{H} h ∈ H . For n ≥ 6 n \ge6 n ≥ 6 let m = ⌊ n / 3 ⌋ m = \lfloor n/3 \rfloor m = ⌊ n /3 ⌋ and r = n − 2 m r = n-2m r = n − 2 m , so that n 4 ≤ m ≤ r \frac{n}{4} \le m \le r 4 n ≤ m ≤ r , and split S S S into three independent parts, one for each stage of the idea above:
S ( 0 ) = ( ( X i , Y i ) ) i = 1 m , S ( 1 ) of size m , S ( 2 ) of size r . S^{(0)} = ((X_i,Y_i))_{i=1}^{m}, \qquad S^{(1)}\text{ of size }m, \qquad S^{(2)}\text{ of size }r. S ( 0 ) = (( X i , Y i ) ) i = 1 m , S ( 1 ) of size m , S ( 2 ) of size r .
Candidates (experts). Let
E = { ⋆ } ∪ { I ⊆ [ m ] : ( X i , Y i ) i ∈ I is realizable by H } . \mathcal{E} = \{\star\} \cup\{I \subseteq[m] : (X_i,Y_i)_{i\in I}\text{ is realizable by }\mathcal{H}\}. E = { ⋆ } ∪ { I ⊆ [ m ] : ( X i , Y i ) i ∈ I is realizable by H } .
For I ∈ E ∖ { ⋆ } I \in\mathcal{E} \setminus\{\star\} I ∈ E ∖ { ⋆ } , form the version space V I = V ( X i , Y i ) i ∈ I \mathcal{V}_I = \mathcal{V}_{(X_i,Y_i)_{i\in I}} V I = V ( X i , Y i ) i ∈ I and train the first-order learner inside it, g I = B V I ( S ( 1 ) ) g_I = \mathcal{B}_{\mathcal{V}_I}(S^{(1)}) g I = B V I ( S ( 1 ) ) . For the special expert ⋆ \star ⋆ , let g ⋆ g_\star g ⋆ be an ERM over H \mathcal{H} H on S ( 1 ) S^{(1)} S ( 1 ) . The experts are the elements of E \mathcal{E} E : two different experts may output the same classifier, and we still treat them as different experts. This use of realizable subsamples follows the agnostic-to-realizable reductions of David et al. [ [16 ] , Hopkins et al. [ [28 ] , and Hanneke et al. [ [24 ] .
Prior. Let w ( I ) = p ∣ I ∣ ( 1 − p ) m − ∣ I ∣ w(I) = p^{|I|}(1-p)^{m-|I|} w ( I ) = p ∣ I ∣ ( 1 − p ) m − ∣ I ∣ . This is the probability that a random subset of [ m ] [m] [ m ] , which contains each index independently with probability p p p , is exactly I I I . Let Z = ∑ I ∈ E ∖ { ⋆ } w ( I ) Z = \sum_{I\in\mathcal{E}\setminus\{\star\}} w(I) Z = ∑ I ∈ E ∖ { ⋆ } w ( I ) . The empty subsample is realizable, so Z ≥ w ( ∅ ) = ( 1 − p ) m > 0 Z \ge w(\varnothing) = (1-p)^m > 0 Z ≥ w ( ∅ ) = ( 1 − p ) m > 0 , and Z ≤ 1 Z \le1 Z ≤ 1 . Set
π ( ⋆ ) = 1 2 , π ( I ) = w ( I ) 2 Z ≥ w ( I ) 2 for I ∈ E ∖ { ⋆ } . \pi(\star) = \frac{1}{2}, \qquad\pi(I) = \frac{w(I)}{2Z} \ge\frac{w(I)}{2}\quad\text{for } I \in\mathcal{E}\setminus\{\star\}. π ( ⋆ ) = 2 1 , π ( I ) = 2 Z w ( I ) ≥ 2 w ( I ) for I ∈ E ∖ { ⋆ } .
So π \pi π is a probability distribution on E \mathcal{E} E that favors small subsamples.
Aggregation. Let ( X t ′ , Y t ′ ) (X'_t,Y'_t) ( X t ′ , Y t ′ ) , t ∈ [ r ] t \in[r] t ∈ [ r ] , be the examples of S ( 2 ) S^{(2)} S ( 2 ) , and for e ∈ E e \in\mathcal{E} e ∈ E let ℓ t ( e ) ∈ [ 0 , 1 ] \ell_t(e) \in[0,1] ℓ t ( e ) ∈ [ 0 , 1 ] be the probability that g e g_e g e errs on ( X t ′ , Y t ′ ) (X'_t,Y'_t) ( X t ′ , Y t ′ ) (over the internal randomness of g e g_e g e , if any). Run exponential weights with rate η \eta η starting from π \pi π :
w 1 = π , w t + 1 ( e ) = w t ( e ) e − η ℓ t ( e ) ∑ e ′ ∈ E w t ( e ′ ) e − η ℓ t ( e ′ ) . w_1 = \pi,\qquad w_{t+1}(e) = \frac{w_t(e)e^{-\eta\ell_t(e)}}{\sum_{e'\in\mathcal{E}}w_t(e')e^{-\eta\ell_t(e')}}. w 1 = π , w t + 1 ( e ) = ∑ e ′ ∈ E w t ( e ′ ) e − η ℓ t ( e ′ ) w t ( e ) e − η ℓ t ( e ) .
Output the randomized classifier h ^ \hat{h} h ^ that draws t ∈ [ r ] t \in[r] t ∈ [ r ] uniformly, then an expert e ∈ E e \in\mathcal{E} e ∈ E from w t w_t w t , and predicts g e ( x ) g_e(x) g e ( x ) . Its error is er D ( h ^ ) = 1 r ∑ t = 1 r ∑ e ∈ E w t ( e ) er D ( g e ) \operatorname{er}_{\mathcal{D}}(\hat{h}) = \frac{1}{r}\sum_{t=1}^{r}\sum_{e\in\mathcal{E}}w_t(e)\operatorname{er}_{\mathcal{D}}(g_e) er D ( h ^ ) = r 1 ∑ t = 1 r ∑ e ∈ E w t ( e ) er D ( g e ) .
Version spaces become simple
The first tool is taken from Brukhim et al. [ [11 ] : after enough samples from D X \mathcal{D}_{\mathcal{X}} D X , all the version spaces are simple at the same time.
Lemma 5.5 (Exhaustion). If H \mathcal{H} H has no infinite uncentered ( d + 1 ) (d+1) ( d + 1 ) -VC-eluder sequence, then for every marginal D X \mathcal{D}_{\mathcal{X}} D X ,
lim m → ∞ Pr U ∼ D X m [ there is h ∈ H with VC D X ( V U , h ) > d ] = 0. \lim_{m\to\infty}\Pr_{U\sim\mathcal{D}_{\mathcal{X}}^m}\left[\text{there is }h\in\mathcal{H}\text{ with }\operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_{U,h})>d\right]=0. m → ∞ lim U ∼ D X m Pr [ there is h ∈ H with VC D X ( V U , h ) > d ] = 0.
This is Corollary 20 of Brukhim et al. [ [11 ] , stated at width d + 1 d + 1 d + 1 . We include the proof, which follows their Lemma 18.
Proof. Suppose, towards a contradiction, that the limit is not 0 for some D X \mathcal{D}_{\mathcal{X}} D X . Let X 1 , X 2 , … X_1,X_2,\ldots X 1 , X 2 , … be i.i.d. from D X \mathcal{D}_{\mathcal{X}} D X and write U m = ( X 1 , … , X m ) \mathcal{U}_m = (X_1,\ldots,X_m) U m = ( X 1 , … , X m ) , with U 0 \mathcal{U}_0 U 0 empty.
Version spaces depend only on labels. For σ ∈ { 0 , 1 } m \sigma\in\{0,1\}^m σ ∈ { 0 , 1 } m let V U m , σ = { f ∈ H : f ( X i ) = σ i for all i ∈ [ m ] } \mathcal{V}_{\mathcal{U}_m,\sigma} = \{f \in\mathcal{H}: f(X_i) = \sigma_i \text{ for all } i \in[m]\} V U m , σ = { f ∈ H : f ( X i ) = σ i for all i ∈ [ m ]} . For every h ∈ H h \in\mathcal{H} h ∈ H we have V U m , h = V U m , σ \mathcal{V}_{\mathcal{U}_m,h} = \mathcal{V}_{\mathcal{U}_m,\sigma} V U m , h = V U m , σ with σ = ( h ( X 1 ) , … , h ( X m ) ) \sigma= (h(X_1),\ldots,h(X_m)) σ = ( h ( X 1 ) , … , h ( X m )) . So, although H \mathcal{H} H may be uncountable, there are at most 2 m 2^m 2 m different version spaces on U m \mathcal{U}_m U m .
A bad event that never goes away. Let E m E_m E m be the event that some σ ∈ { 0 , 1 } m \sigma\in\{0,1\}^m σ ∈ { 0 , 1 } m satisfies V U m , σ ≠ ∅ \mathcal{V}_{\mathcal{U}_m,\sigma} \ne\varnothing V U m , σ = ∅ and D X d + 1 ( SH ( V U m , σ , d + 1 ) ) > 0 \mathcal{D}_{\mathcal{X}}^{d+1}(\operatorname{SH}(\mathcal{V}_{\mathcal{U}_m,\sigma},d+1)) > 0 D X d + 1 ( SH ( V U m , σ , d + 1 )) > 0 . This is exactly the event that some h ∈ H h \in\mathcal{H} h ∈ H has VC D X ( V U m , h ) > d \operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_{\mathcal{U}_m,h}) > d VC D X ( V U m , h ) > d , and it is a finite union of measurable events. If σ ′ ∈ { 0 , 1 } m + 1 \sigma' \in\{0,1\}^{m+1} σ ′ ∈ { 0 , 1 } m + 1 witnesses E m + 1 E_{m+1} E m + 1 , then its first m m m coordinates σ \sigma σ witness E m E_m E m , because V U m + 1 , σ ′ ⊆ V U m , σ \mathcal{V}_{\mathcal{U}_{m+1},\sigma'} \subseteq\mathcal{V}_{\mathcal{U}_m,\sigma} V U m + 1 , σ ′ ⊆ V U m , σ and a smaller class shatters fewer tuples. Hence E m + 1 ⊆ E m E_{m+1} \subseteq E_m E m + 1 ⊆ E m . By assumption lim m P [ E m ] > 0 \lim_m \mathbb{P}[E_m] > 0 lim m P [ E m ] > 0 , so E ∞ = ⋂ m E m E_\infty= \bigcap_m E_m E ∞ = ⋂ m E m has positive probability.
A set of shattered tuples of positive mass. On E m E_m E m , let σ m \sigma_m σ m be the lexicographically first σ ∈ { 0 , 1 } m \sigma\in\{0,1\}^m σ ∈ { 0 , 1 } m that witnesses E m E_m E m , and let A m = SH ( V U m , σ m , d + 1 ) A_m = \operatorname{SH}(\mathcal{V}_{\mathcal{U}_m,\sigma_m},d+1) A m = SH ( V U m , σ m , d + 1 ) , so that D X d + 1 ( A m ) > 0 \mathcal{D}_{\mathcal{X}}^{d+1}(A_m) > 0 D X d + 1 ( A m ) > 0 . Off E m E_m E m , let A m = ∅ A_m = \varnothing A m = ∅ . Since σ m \sigma_m σ m is chosen among finitely many candidates by a fixed rule, A m A_m A m is determined by U m \mathcal{U}_m U m in a measurable way; we never choose a concept from H \mathcal{H} H .
Future samples hit this set. Cut the future samples X m + 1 , X m + 2 , … X_{m+1},X_{m+2},\ldots X m + 1 , X m + 2 , … into consecutive disjoint blocks of d + 1 d+1 d + 1 points. These blocks are i.i.d. from D X d + 1 \mathcal{D}_{\mathcal{X}}^{d+1} D X d + 1 and independent of U m \mathcal{U}_m U m . Conditioned on U m \mathcal{U}_m U m , each block lies in A m A_m A m independently with probability D X d + 1 ( A m ) \mathcal{D}_{\mathcal{X}}^{d+1}(A_m) D X d + 1 ( A m ) , which is positive on E m E_m E m . By the second Borel–Cantelli lemma, almost surely on E m E_m E m infinitely many blocks lie in A m A_m A m . There are countably many m m m , so almost surely this holds for all m m m at once.
Build the forbidden sequence. Fix a sample path in E ∞ E_\infty E ∞ on which the conclusion of the previous step holds for all m m m ; the rest is deterministic. Set t 0 = 0 t_0 = 0 t 0 = 0 . Given t r − 1 t_{r-1} t r − 1 , pick a block after position t r − 1 t_{r-1} t r − 1 that lies in A t r − 1 A_{t_{r-1}} A t r − 1 , call its set of points B r B_r B r , and let t r t_r t r be the position of its last point. By definition of A t r − 1 A_{t_{r-1}} A t r − 1 , the set B r B_r B r is VC-shattered by V U t r − 1 , σ t r − 1 \mathcal{V}_{\mathcal{U}_{t_{r-1}},\sigma_{t_{r-1}}} V U t r − 1 , σ t r − 1 . All members of this version space have the labels σ t r − 1 \sigma_{t_{r-1}} σ t r − 1 on U t r − 1 \mathcal{U}_{t_{r-1}} U t r − 1 , so they agree with each other there, and U t r − 1 \mathcal{U}_{t_{r-1}} U t r − 1 contains B 1 , … , B r − 1 B_1,\ldots,B_{r-1} B 1 , … , B r − 1 . Hence B 1 , B 2 , … B_1,B_2,\ldots B 1 , B 2 , … is an infinite uncentered ( d + 1 ) (d+1) ( d + 1 ) -VC-eluder sequence, a contradiction. □ \square □
Since uVCE ( H ) = d \operatorname{uVCE}(\mathcal{H}) = d uVCE ( H ) = d , the class has no infinite uncentered ( d + 1 ) (d+1) ( d + 1 ) -VC-eluder sequence and Lemma 5.5 applies. For the rest of this section fix a marginal D X \mathcal{D}_{\mathcal{X}} D X . By the lemma there is q q q which depends on D X \mathcal{D}_{\mathcal{X}} D X such that with
P U ∼ D X q [ VC D X ( V U , h ) ≤ d for every h ∈ H ] ≥ 3 4 . (4) \mathbb{P}_{\mathcal{U}\sim\mathcal{D}_{\mathcal{X}}^q}\left[\operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_{\mathcal{U},h}) \le d \text{ for every } h \in\mathcal{H}\right] \ge\frac{3}{4}. \tag*{(4)} P U ∼ D X q [ VC D X ( V U , h ) ≤ d for every h ∈ H ] ≥ 4 3 . (4)
We call a q q q -tuple U \mathcal{U} U good if the event in (4) holds, and we set
ρ = 1 4 q , β = 3 p 4 ( 1 − 2 − 1 / q ) > 0. \rho= \frac{1}{4q}, \qquad\beta= \frac{3p}{4}\left(1 - 2^{-1/q}\right) > 0. ρ = 4 q 1 , β = 4 3 p ( 1 − 2 − 1/ q ) > 0.
These quantities are used only in the analysis; the learner does not know q q q , ρ \rho ρ or β \beta β .
Clean subsamples localize
Lemma 5.5 is about samples from D X \mathcal{D}_{\mathcal{X}} D X . The next lemma transfers it to what the learner can actually use: a random subsample on which a fixed good concept h h h makes no mistake.
Lemma 5.6 (Localization from a clean subsample). Let h ∈ H h \in\mathcal{H} h ∈ H with a = err D ( h ) ≤ ρ a = \operatorname{err}_{\mathcal{D}}(h) \le\rho a = err D ( h ) ≤ ρ . Draw S ( 0 ) ∼ D m S^{(0)} \sim\mathcal{D}^m S ( 0 ) ∼ D m and independently b 1 , … , b m ∼ Ber ( p ) b_1,\ldots,b_m \sim\operatorname{Ber}(p) b 1 , … , b m ∼ Ber ( p ) . Keep the indices that are selected and on which h h h is correct,
I = { i ∈ [ m ] : b i = 1 and Y i = h ( X i ) } , U I = ( X i ) i ∈ I . I = \{i \in[m]: b_i = 1 \text{ and } Y_i = h(X_i)\}, \qquad\mathcal{U}_I = (X_i)_{i \in I}. I = { i ∈ [ m ] : b i = 1 and Y i = h ( X i )} , U I = ( X i ) i ∈ I .
Then
P [ VC D X ( V U I , h ) > d ] ≤ 2 e − β m . \mathbb{P}\left[\operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_{\mathcal{U}_I,h}) > d\right] \le2e^{-\beta m}. P [ VC D X ( V U I , h ) > d ] ≤ 2 e − β m .
Proof. The kept points are i.i.d. The triples ( X i , Y i , b i ) (X_i, Y_i, b_i) ( X i , Y i , b i ) are i.i.d., and index i i i is kept with probability p ( 1 − a ) p(1-a) p ( 1 − a ) . A kept point has the law ν h \nu_h ν h of X X X conditioned on Y = h ( X ) Y=h(X) Y = h ( X ) . Hence the number of kept points is J = ∣ I ∣ ∼ Bin ( m , p ( 1 − a ) ) J=|I|\sim\operatorname{Bin}(m,p(1-a)) J = ∣ I ∣ ∼ Bin ( m , p ( 1 − a )) , and given J J J the kept points are i.i.d. from ν h \nu_h ν h .
ν h \nu_h ν h is close to D X D_X D X . Conditioning on whether h h h is correct gives D X = ( 1 − a ) ν h + a ν ′ D_X=(1-a)\nu_h+a\nu' D X = ( 1 − a ) ν h + a ν ′ , where ν ′ \nu' ν ′ is the law of X X X given Y ≠ h ( X ) Y\ne h(X) Y = h ( X ) . So TV ( ν h , D X ) ≤ a \operatorname{TV}(\nu_h,D_X)\le a TV ( ν h , D X ) ≤ a , and for q q q -tuples TV ( ν h q , D X q ) ≤ q a ≤ q ρ = 1 4 \operatorname{TV}(\nu_h^q,D_X^q)\le qa\le q\rho=\frac{1}{4} TV ( ν h q , D X q ) ≤ q a ≤ q ρ = 4 1 . By (4) , a q q q -tuple drawn from ν h q \nu_h^q ν h q is therefore good with probability at least 3 4 − 1 4 = 1 2 \frac{3}{4}-\frac{1}{4}=\frac{1}{2} 4 3 − 4 1 = 2 1 .
One good block is enough. Split the kept points into ⌊ J / q ⌋ \lfloor J/q\rfloor ⌊ J / q ⌋ disjoint blocks of q q q points. If some block U ′ U' U ′ is good, then VC D X ( V U ′ , h ) ≤ d \operatorname{VC}_{D_X}(\mathcal{V}_{U',h})\le d VC D X ( V U ′ , h ) ≤ d , and since V U I , h ⊆ V U ′ , h \mathcal{V}_{U_I,h}\subseteq\mathcal{V}_{U',h} V U I , h ⊆ V U ′ , h also VC D X ( V U I , h ) ≤ d \operatorname{VC}_{D_X}(\mathcal{V}_{U_I,h})\le d VC D X ( V U I , h ) ≤ d . The blocks are independent and each fails to be good with probability at most 1 2 \frac{1}{2} 2 1 , so
P [ VC D X ( V U I , h ) > d ∣ J ] ≤ ( 1 2 ) ⌊ J / q ⌋ ≤ 2 ⋅ 2 − J / q . \mathbb{P}\left[\operatorname{VC}_{D_X}(\mathcal{V}_{U_I,h})>d\mid J\right]\le\left(\frac{1}{2}\right)^{\lfloor J/q\rfloor}\le2\cdot2^{-J/q}. P [ VC D X ( V U I , h ) > d ∣ J ] ≤ ( 2 1 ) ⌊ J / q ⌋ ≤ 2 ⋅ 2 − J / q .
Average over J J J . For J ∼ Bin ( m , p ′ ) J\sim\operatorname{Bin}(m,p') J ∼ Bin ( m , p ′ ) and x ∈ [ 0 , 1 ] x\in[0,1] x ∈ [ 0 , 1 ] we have E [ x J ] = ( 1 − p ′ ( 1 − x ) ) m ≤ e − m p ′ ( 1 − x ) \mathbb{E}[x^J]=(1-p'(1-x))^m\le e^{-mp'(1-x)} E [ x J ] = ( 1 − p ′ ( 1 − x ) ) m ≤ e − m p ′ ( 1 − x ) . With p ′ = p ( 1 − a ) ≥ 3 4 p p'=p(1-a)\ge\frac{3}{4}p p ′ = p ( 1 − a ) ≥ 4 3 p (as a ≤ ρ ≤ 1 4 a\le\rho\le\frac{1}{4} a ≤ ρ ≤ 4 1 ) and x = 2 − 1 / q x=2^{-1/q} x = 2 − 1/ q this gives E [ 2 − J / q ] ≤ e − β m \mathbb{E}[2^{-J/q}]\le e^{-\beta m} E [ 2 − J / q ] ≤ e − β m , and the claim follows from the previous step.
Choosing among the candidates
The next lemma is the standard guarantee of exponential weights [18 ] , stated against a distribution Q Q Q over experts instead of a single expert and combined with the usual online-to-batch conversion [12 ] . The price for competing with Q Q Q is D K L ( Q ∥ π ) D_{\mathrm{KL}}(Q\mathbin\Vert\pi) D KL ( Q ∥ π ) , which is small whenever the prior puts enough mass where Q Q Q lives.
Lemma 5.7 (Exponential weights against a distribution). Let a η = 1 − e − η a_\eta=1-e^{-\eta} a η = 1 − e − η and b η = η / a η b_\eta=\eta/a_\eta b η = η / a η . For every distribution Q Q Q on E \mathcal{E} E that is determined by S ( 0 ) S^{(0)} S ( 0 ) and S ( 1 ) S^{(1)} S ( 1 ) ,
E [ er D ( h ^ ) ∣ S ( 0 ) , S ( 1 ) ] ≤ b η ∑ e ∈ E Q ( e ) er D ( g e ) + D K L ( Q ∥ π ) r a η \mathbb{E}\left[\operatorname{er}_{D}(\hat{h})\mid S^{(0)},S^{(1)}\right]\le b_\eta\sum_{e\in\mathcal{E}}Q(e)\operatorname{er}_{D}(g_e)+\frac{D_{\mathrm{KL}}(Q\mathbin\Vert\pi)}{r a_\eta} E [ er D ( h ^ ) ∣ S ( 0 ) , S ( 1 ) ] ≤ b η e ∈ E ∑ Q ( e ) er D ( g e ) + r a η D KL ( Q ∥ π ) where log \log log is the natural logarithm, and for a randomized expert, er D ( g e ) \operatorname{er}_{D}(g_e) er D ( g e ) includes its internal randomness. If Q = π ( ⋅ ∣ G ) Q=\pi(\cdot\mid G) Q = π ( ⋅ ∣ G ) for a set G ⊆ E G\subseteq\mathcal{E} G ⊆ E with π ( G ) > 0 \pi(G)>0 π ( G ) > 0 , then D K L ( Q ∥ π ) = log 1 π ( G ) D_{\mathrm{KL}}(Q\mathbin\Vert\pi)=\log\frac{1}{\pi(G)} D KL ( Q ∥ π ) = log π ( G ) 1 .
Proof. Condition on S ( 0 ) S^{(0)} S ( 0 ) and S ( 1 ) S^{(1)} S ( 1 ) , so that the experts, π \pi π and Q Q Q are fixed. Let L e = ∑ t = 1 r ℓ t ( e ) L_e=\sum_{t=1}^{r}\ell_t(e) L e = ∑ t = 1 r ℓ t ( e ) be the total loss of expert e e e , and consider the potential W t = ∑ e ∈ E π ( e ) exp ( − η ∑ s < t ℓ s ( e ) ) W_t=\sum_{e\in\mathcal{E}}\pi(e)\exp\left(-\eta\sum_{s<t}\ell_s(e)\right) W t = ∑ e ∈ E π ( e ) exp ( − η ∑ s < t ℓ s ( e ) ) , so that W 1 = 1 W_1=1 W 1 = 1 and w t ( e ) = π ( e ) exp ( − η ∑ s < t ℓ s ( e ) ) / W t w_t(e)=\pi(e)\exp\left(-\eta\sum_{s<t}\ell_s(e)\right)/W_t w t ( e ) = π ( e ) exp ( − η ∑ s < t ℓ s ( e ) ) / W t .
The potential drops when the mixture makes a mistake. Using e − η x ≤ 1 − a η x e^{-\eta x}\le1-a_\eta x e − η x ≤ 1 − a η x for x ∈ [ 0 , 1 ] x\in[0,1] x ∈ [ 0 , 1 ] and 1 − u ≤ e − u 1-u\le e^{-u} 1 − u ≤ e − u ,
W t + 1 W t = ∑ e ∈ E w t ( e ) e − η ℓ t ( e ) ≤ 1 − a η ⟨ w t , ℓ t ⟩ ≤ e − a η ⟨ w t , ℓ t ⟩ , \frac{W_{t+1}}{W_t}=\sum_{e\in\mathcal{E}}w_t(e)e^{-\eta\ell_t(e)}\le1-a_\eta\langle w_t,\ell_t\rangle\le e^{-a_\eta\langle w_t,\ell_t\rangle}, W t W t + 1 = e ∈ E ∑ w t ( e ) e − η ℓ t ( e ) ≤ 1 − a η ⟨ w t , ℓ t ⟩ ≤ e − a η ⟨ w t , ℓ t ⟩ ,
so
log W r + 1 ≤ − a η ∑ t = 1 r ⟨ w t , ℓ t ⟩ . \log W_{r+1}\le-a_\eta\sum_{t=1}^{r}\langle w_t,\ell_t\rangle. log W r + 1 ≤ − a η t = 1 ∑ r ⟨ w t , ℓ t ⟩ .
The potential stays large if Q Q Q is good. By Jensen’s inequality,
log W r + 1 = log ∑ e ∈ E π ( e ) e − η L e ≥ ∑ e ∈ E Q ( e ) log π ( e ) e − η L e Q ( e ) = − D K L ( Q ∥ π ) − η ∑ e ∈ E Q ( e ) L e , \log W_{r+1}=\log\sum_{e\in\mathcal{E}}\pi(e)e^{-\eta L_e}\ge\sum_{e\in\mathcal{E}}Q(e)\log\frac{\pi(e)e^{-\eta L_e}}{Q(e)}=-D_{\mathrm{KL}}(Q\mathbin\Vert\pi)-\eta\sum_{e\in\mathcal{E}}Q(e)L_e, log W r + 1 = log e ∈ E ∑ π ( e ) e − η L e ≥ e ∈ E ∑ Q ( e ) log Q ( e ) π ( e ) e − η L e = − D KL ( Q ∥ π ) − η e ∈ E ∑ Q ( e ) L e ,
where the sums over e e e with Q ( e ) = 0 Q(e)=0 Q ( e ) = 0 are dropped.
Combine and take expectations. The previous two steps give a η ∑ t ⟨ w t , ℓ t ⟩ ≤ η ∑ e ∈ E Q ( e ) L e + D K L ( Q ∥ π ) a_\eta\sum_t\langle w_t,\ell_t\rangle\le\eta\sum_{e\in\mathcal{E}}Q(e)L_e+D_{\mathrm{KL}}(Q\mathbin\Vert\pi) a η ∑ t ⟨ w t , ℓ t ⟩ ≤ η ∑ e ∈ E Q ( e ) L e + D KL ( Q ∥ π ) . The weights w t w_t w t depend only on S ( 0 ) S^{(0)} S ( 0 ) , S ( 1 ) S^{(1)} S ( 1 ) and the first t − 1 t-1 t − 1 examples of S ( 2 ) S^{(2)} S ( 2 ) , and the t t t -th example of S ( 2 ) S^{(2)} S ( 2 ) is a fresh draw from D \mathcal{D} D , independent of these. So, conditioned on S ( 0 ) S^{(0)} S ( 0 ) and S ( 1 ) S^{(1)} S ( 1 ) , the expectation of ⟨ w t , ℓ t ⟩ \langle w_t,\ell_t\rangle ⟨ w t , ℓ t ⟩ is the expectation of ∑ e ∈ E w t ( e ) er D ( g e ) \sum_{e\in\mathcal{E}} w_t(e)\operatorname{er}_{\mathcal{D}}(g_e) ∑ e ∈ E w t ( e ) er D ( g e ) , and the expectation of ℓ t ( e ) \ell_t(e) ℓ t ( e ) is er D ( g e ) \operatorname{er}_{\mathcal{D}}(g_e) er D ( g e ) . Summing over t t t , the left side becomes a η r E [ er D ( h ^ ) ∣ S ( 0 ) , S ( 1 ) ] a_\eta r\mathbb{E}\left[\operatorname{er}_{\mathcal{D}}(\hat{h})\mid S^{(0)},S^{(1)}\right] a η r E [ er D ( h ^ ) ∣ S ( 0 ) , S ( 1 ) ] and the right side becomes η r ∑ e ∈ E Q ( e ) er D ( g e ) + D K L ( Q ∥ π ) \eta r\sum_{e\in\mathcal{E}}Q(e)\operatorname{er}_{\mathcal{D}}(g_e)+D_{\mathrm{KL}}(Q\mathbin\Vert\pi) η r ∑ e ∈ E Q ( e ) er D ( g e ) + D KL ( Q ∥ π ) . Divide by r a η r a_\eta r a η .
For Q = π ( ⋅ ∣ G ) Q=\pi(\cdot\mid G) Q = π ( ⋅ ∣ G ) with π ( G ) > 0 \pi(G)>0 π ( G ) > 0 , the ratio Q ( e ) / π ( e ) Q(e)/\pi(e) Q ( e ) / π ( e ) equals 1 π ( G ) \frac{1}{\pi(G)} π ( G ) 1 on G G G and Q ( e ) = 0 Q(e)=0 Q ( e ) = 0 off G G G , which gives the last claim. □ \square □
Finally, when τ D \tau_{\mathcal{D}} τ D is not small we will not need localization at all; a plain ERM is good enough.
Lemma 5.8 (ERM at fixed accuracy). Suppose v = VC ( H ) < ∞ v=\operatorname{VC}(\mathcal{H})<\infty v = VC ( H ) < ∞ . For every ζ ∈ ( 0 , 1 ] \zeta\in(0,1] ζ ∈ ( 0 , 1 ] there are A , b > 0 A,b>0 A , b > 0 , depending only on v v v and ζ \zeta ζ , such that for every distribution D \mathcal{D} D and every m ≥ 1 m\ge1 m ≥ 1 , an ERM g ⋆ g_\star g ⋆ over H \mathcal{H} H on S ∼ D m S\sim\mathcal{D}^m S ∼ D m satisfies
E S ∼ D m [ er D ( g ⋆ ) ] ≤ τ D + ζ + A e − b m . \mathbb{E}_{S\sim\mathcal{D}^m}[\operatorname{er}_{\mathcal{D}}(g_\star)]\le\tau_{\mathcal{D}}+\zeta+Ae^{-bm}. E S ∼ D m [ er D ( g ⋆ )] ≤ τ D + ζ + A e − bm .
Proof. Write er S ( h ) \operatorname{er}_S(h) er S ( h ) for the fraction of examples in S S S that h h h misclassifies.
Uniform convergence. By the VC inequality [17 Theorem 12.5] and Sauer’s lemma, for m ≥ v m\ge v m ≥ v ,
P [ sup h ∈ H ∣ er D ( h ) − er S ( h ) ∣ > ζ 2 ] ≤ 8 ( e m v ) v e − m ζ 2 / 128 . \mathbb{P}\left[\sup_{h\in\mathcal{H}}\left|\operatorname{er}_{\mathcal{D}}(h)-\operatorname{er}_S(h)\right|>\frac{\zeta}{2}\right]\le8\left(\frac{em}{v}\right)^v e^{-m\zeta^2/128}. P [ h ∈ H sup ∣ er D ( h ) − er S ( h ) ∣ > 2 ζ ] ≤ 8 ( v e m ) v e − m ζ 2 /128 .
ERM is accurate outside this event. If ∣ er D ( h ) − er S ( h ) ∣ ≤ ζ 2 \left|\operatorname{er}_{\mathcal{D}}(h)-\operatorname{er}_S(h)\right|\le\frac{\zeta}{2} ∣ er D ( h ) − er S ( h ) ∣ ≤ 2 ζ for every h ∈ H h\in\mathcal{H} h ∈ H , then, since g ⋆ g_\star g ⋆ minimizes the empirical error, for every h ∈ H h\in\mathcal{H} h ∈ H
er D ( g ⋆ ) ≤ er S ( g ⋆ ) + ζ 2 ≤ er S ( h ) + ζ 2 ≤ er D ( h ) + ζ . \operatorname{er}_{\mathcal{D}}(g_\star)\le\operatorname{er}_S(g_\star)+\frac{\zeta}{2}\le\operatorname{er}_S(h)+\frac{\zeta}{2}\le\operatorname{er}_{\mathcal{D}}(h)+\zeta. er D ( g ⋆ ) ≤ er S ( g ⋆ ) + 2 ζ ≤ er S ( h ) + 2 ζ ≤ er D ( h ) + ζ .
Taking the infimum over h ∈ H h\in\mathcal{H} h ∈ H gives er D ( g ⋆ ) ≤ τ D + ζ \operatorname{er}_{\mathcal{D}}(g_\star)\le\tau_{\mathcal{D}}+\zeta er D ( g ⋆ ) ≤ τ D + ζ . On the complementary event we bound er D ( g ⋆ ) ≤ 1 \operatorname{er}_{\mathcal{D}}(g_\star)\le1 er D ( g ⋆ ) ≤ 1 . Hence, for m ≥ v m\ge v m ≥ v ,
E [ er D ( g ⋆ ) ] ≤ τ D + ζ + 8 ( e m v ) v e − m ζ 2 / 128 . \mathbb{E}[\operatorname{er}_{\mathcal{D}}(g_\star)]\le\tau_{\mathcal{D}}+\zeta+8\left(\frac{em}{v}\right)^v e^{-m\zeta^2/128}. E [ er D ( g ⋆ )] ≤ τ D + ζ + 8 ( v e m ) v e − m ζ 2 /128 .
Absorbing the polynomial factor. Let b = ζ 2 / 256 b=\zeta^2/256 b = ζ 2 /256 . The function m ↦ 8 ( e m / v ) v e − m ζ 2 / 256 m\mapsto8(em/v)^v e^{-m\zeta^2/256} m ↦ 8 ( e m / v ) v e − m ζ 2 /256 is bounded on [ v , ∞ ) [v,\infty) [ v , ∞ ) ; let A 1 A_1 A 1 be its supremum. Then for m ≥ v m\ge v m ≥ v the last term is at most A 1 e − b m A_1e^{-bm} A 1 e − bm . For m < v m<v m < v we use the trivial bound E [ er D ( g ⋆ ) ] ≤ 1 ≤ e b v e − b m \mathbb{E}[\operatorname{er}_{\mathcal{D}}(g_\star)]\le1\le e^{bv}e^{-bm} E [ er D ( g ⋆ )] ≤ 1 ≤ e b v e − bm . The lemma follows with A = max { A 1 , e b v } A=\max\{A_1,e^{bv}\} A = max { A 1 , e b v } , which depends only on v v v and ζ \zeta ζ . □ \square □
Proof of the upper bound
Proof of Theorem 5.4 . Fix a distribution D \mathcal{D} D with marginal D X \mathcal{D}_X D X . For n < 6 n<6 n < 6 the learner outputs a fixed concept and the bound holds trivially, since K λ n ≥ K 6 ≥ 1 \frac{K}{\lambda n}\ge\frac{K}{6}\ge1 λn K ≥ 6 K ≥ 1 . We assume n ≥ 6 n\ge6 n ≥ 6 from now on. We will use the elementary bounds
b η ≤ 1 + η , a η ≥ η 2 , log 1 1 − p ≤ 2 p , n 4 ≤ m ≤ r . (5) b_\eta\le1+\eta,\qquad a_\eta\ge\frac{\eta}{2},\qquad\log\frac{1}{1-p}\le2p,\qquad\frac{n}{4}\le m\le r. \tag*{(5)} b η ≤ 1 + η , a η ≥ 2 η , log 1 − p 1 ≤ 2 p , 4 n ≤ m ≤ r . (5)
The proof has two cases. If the best concept in H \mathcal{H} H has small error, we compete with the candidates trained in clean version spaces (Case 1). Otherwise the ERM candidate g ⋆ g_\star g ⋆ already suffices (Case 2).
Case 1: τ D ≤ ρ / 2 \tau_{\mathcal{D}}\le\rho/2 τ D ≤ ρ /2 .
A comparator. Fix any h ∈ H h\in\mathcal{H} h ∈ H with a = er D ( h ) ≤ ρ a=\operatorname{er}_{\mathcal{D}}(h)\le\rho a = er D ( h ) ≤ ρ ; such h h h exist because τ D < ρ \tau_{\mathcal{D}}<\rho τ D < ρ . Let
E h = { i ≤ m : Y i ≠ h ( X i ) } , K h = ∣ E h ∣ , E_h=\{i\le m:Y_i\ne h(X_i)\},\qquad K_h=|E_h|, E h = { i ≤ m : Y i = h ( X i )} , K h = ∣ E h ∣ ,
be the positions of the mistakes of h h h on S ( 0 ) S^{(0)} S ( 0 ) and their number, so E [ K h ] = m a \mathbb{E}[K_h] = ma E [ K h ] = ma . A subsample I I I is clean if I ∩ E h = ∅ I \cap E_h = \varnothing I ∩ E h = ∅ . For a clean I I I the labels on I I I are those of h h h , so I ∈ E I \in\mathcal{E} I ∈ E , and
V I = V U I , h ∋ h . (6) \mathcal{V}_I = \mathcal{V}_{\mathcal{U}_I,h} \ni h. \tag*{(6)} V I = V U I , h ∋ h . (6)
The good experts. Define
G h = { I ∈ E ∖ { ⋆ } : I is clean and VC D X ( V U I , h ) ≤ d } . G_h = \{I \in\mathcal{E} \setminus\{\star\} : I \text{ is clean and } \operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_{\mathcal{U}_I,h}) \le d\}. G h = { I ∈ E ∖ { ⋆ } : I is clean and VC D X ( V U I , h ) ≤ d } .
These are the experts trained in a version space that is simple and contains h h h . The set G h ⊆ E G_h \subseteq\mathcal{E} G h ⊆ E depends on S ( 0 ) S^{(0)} S ( 0 ) and h h h only. We show that every good expert is accurate and that the good experts together have enough prior mass; exponential weights then finds them in the following steps.
Each good expert is accurate. Let I ∈ G h I \in G_h I ∈ G h . By (6) , V I \mathcal{V}_I V I is a version space of H \mathcal{H} H with τ D , V I ≤ a \tau_{\mathcal{D},\mathcal{V}_I} \le a τ D , V I ≤ a and VC D X ( V I ) ≤ d \operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_I) \le d VC D X ( V I ) ≤ d . Since S ( 1 ) S^{(1)} S ( 1 ) is independent of S ( 0 ) S^{(0)} S ( 0 ) , we can apply Definition 3.6 to the fixed class V I \mathcal{V}_I V I with k = d k=d k = d . Its right-hand side is increasing in τ D , V I \tau_{\mathcal{D},\mathcal{V}_I} τ D , V I , so writing z = d / m z=d/m z = d / m ,
E [ er D ( g I ) ∣ S ( 0 ) ] ≤ a + B a z + B z , \mathbb{E}\left[\operatorname{er}_{\mathcal{D}}(g_I) \mid S^{(0)}\right] \le a + B\sqrt{az} + Bz, E [ er D ( g I ) ∣ S ( 0 ) ] ≤ a + B a z + B z ,
where the expectation is over S ( 1 ) S^{(1)} S ( 1 ) and the internal randomness of B \mathcal{B} B . To separate a a a from z z z we use
B a z ≤ ε a + B 2 z 4 ε B\sqrt{az} \le\varepsilon a + \frac{B^2z}{4\varepsilon} B a z ≤ ε a + 4 ε B 2 z
with ε = λ 16 \varepsilon= \frac{\lambda}{16} ε = 16 λ
E [ er D ( g I ) ∣ S ( 0 ) ] ≤ ( 1 + ε ) a + ( B + B 2 ) z ε . (7) \mathbb{E}\left[\operatorname{er}_{\mathcal{D}}(g_I) \mid S^{(0)}\right] \le(1+\varepsilon)a + \frac{(B+B^2)z}{\varepsilon}. \tag*{(7)} E [ er D ( g I ) ∣ S ( 0 ) ] ≤ ( 1 + ε ) a + ε ( B + B 2 ) z . (7)
This is the only place where the first-order learner is used, and it is why we need a first-order bound: a term z \sqrt{z} z in place of a z \sqrt{az} a z could not be absorbed into ε a \varepsilon a ε a .
The good experts have enough prior mass. Recall that w w w is the law of a random subset R ⊆ [ m ] R \subseteq[m] R ⊆ [ m ] that contains each index independently with probability p p p . This subset is clean with probability ( 1 − p ) K h (1-p)^{K_h} ( 1 − p ) K h , so ∑ I c l e a n w ( I ) = ( 1 − p ) K h \sum_{I\ \mathrm{clean}} w(I) = (1-p)^{K_h} ∑ I clean w ( I ) = ( 1 − p ) K h . Let
b h = P [ VC D X ( V U R , h ) > d ∣ S ( 0 ) , R is clean ] b_h = \mathbb{P}\left[\operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_{\mathcal{U}_R,h}) > d \mid S^{(0)},\ R\text{ is clean}\right] b h = P [ VC D X ( V U R , h ) > d ∣ S ( 0 ) , R is clean ]
be the fraction of the clean mass that is not good. Then, using π ( I ) ≥ 1 2 w ( I ) \pi(I) \ge\frac{1}{2}w(I) π ( I ) ≥ 2 1 w ( I ) ,
π ( G h ) = ∑ I ∈ G h π ( I ) ≥ 1 2 ∑ I ∈ G h w ( I ) = 1 2 ( 1 − p ) K h ( 1 − b h ) . (8) \pi(G_h) = \sum_{I\in G_h}\pi(I) \ge\frac{1}{2}\sum_{I\in G_h}w(I) = \frac{1}{2}(1-p)^{K_h}(1-b_h). \tag*{(8)} π ( G h ) = I ∈ G h ∑ π ( I ) ≥ 2 1 I ∈ G h ∑ w ( I ) = 2 1 ( 1 − p ) K h ( 1 − b h ) . (8)
Conditioned on S ( 0 ) S^{(0)} S ( 0 ) and on R R R being clean, R R R has the same law as the set I I I of Lemma 5.6 given S ( 0 ) S^{(0)} S ( 0 ) : each index outside E h E_h E h is included independently with probability p p p .
Hence b h = P [ VC D X ( V U I , h ) > d ∣ S ( 0 ) ] b_h = \mathbb{P}\left[\operatorname{VC}_{\mathcal{D}_{\mathcal{X}}}(\mathcal{V}_{\mathcal{U}_I,h}) > d \mid S^{(0)}\right] b h = P [ VC D X ( V U I , h ) > d ∣ S ( 0 ) ] , and taking expectations over S ( 0 ) S^{(0)} S ( 0 ) , Lemma 5.6 gives E [ b h ] ≤ 2 e − β m \mathbb{E}[b_h] \le2e^{-\beta m} E [ b h ] ≤ 2 e − β m . By Markov’s inequality, the event T h = { b h ≤ 1 2 } T_h = \{b_h \le\frac{1}{2}\} T h = { b h ≤ 2 1 } satisfies P [ T h c ] ≤ 4 e − β m \mathbb{P}[T_h^c] \le4e^{-\beta m} P [ T h c ] ≤ 4 e − β m . On T h T_h T h , (8) gives π ( G h ) ≥ 1 4 ( 1 − p ) K h \pi(G_h) \ge\frac{1}{4}(1-p)^{K_h} π ( G h ) ≥ 4 1 ( 1 − p ) K h . In particular π ( G h ) > 0 \pi(G_h)>0 π ( G h ) > 0 , so Q = π ( ⋅ ∣ G h ) Q=\pi(\cdot\mid G_h) Q = π ( ⋅ ∣ G h ) is well defined. The factor ( 1 − p ) K h (1-p)^{K_h} ( 1 − p ) K h is the reason for the choice of prior: every mistake of h h h costs only a factor ( 1 − p ) (1-p) ( 1 − p ) , so the cost below is proportional to the error of h h h .
Aggregate. The event T h T_h T h and the distribution Q = π ( ⋅ ∣ G h ) Q=\pi(\cdot\mid G_h) Q = π ( ⋅ ∣ G h ) depend on S ( 0 ) S^{(0)} S ( 0 ) only. On T h T_h T h we apply Lemma 5.7 with this Q Q Q ; by the previous steps and (5) ,
D K L ( Q ∥ π ) = log 1 π ( G h ) ≤ log 4 + K h log 1 1 − p ≤ log 4 + 2 p K h . D_{\mathrm{KL}}(Q\Vert\pi) = \log\frac{1}{\pi(G_h)} \le\log4 + K_h\log\frac{1}{1-p} \le\log4 + 2pK_h. D KL ( Q ∥ π ) = log π ( G h ) 1 ≤ log 4 + K h log 1 − p 1 ≤ log 4 + 2 p K h .
On T h c T_h^c T h c we use the trivial bound er D ( h ^ ) ≤ 1 \operatorname{er}_{\mathcal{D}}(\hat{h})\le1 er D ( h ^ ) ≤ 1 . Taking expectations, using (7) for every expert in the support of Q Q Q , and E [ K h ] = m a \mathbb{E}[K_h]=ma E [ K h ] = ma ,
E [ er D ( h ^ ) ] ≤ b h ( ( 1 + ε ) a + ( B + B 2 ) z ε ) + log 4 + 2 p m a r η + 4 e − β m . (9) \mathbb{E}\left[\operatorname{er}_{\mathcal{D}}(\hat{h})\right] \le b_h\left((1+\varepsilon)a+\frac{(B+B^2)z}{\varepsilon}\right)+\frac{\log4+2pma}{r\eta}+4e^{-\beta m}. \tag*{(9)} E [ er D ( h ^ ) ] ≤ b h ( ( 1 + ε ) a + ε ( B + B 2 ) z ) + r η log 4 + 2 p ma + 4 e − β m . (9)
Simplify. We collect the terms of (9) using (5) , η = ε = λ 16 \eta=\varepsilon=\frac{\lambda}{16} η = ε = 16 λ and p = λ 2 1024 p=\frac{\lambda^2}{1024} p = 1024 λ 2 .
( 1 + η ) ( 1 + ε ) + 2 p m r ⋅ 2 η ≤ ( 1 + λ 16 ) 2 + 4 p η = ( 1 + λ 16 ) 2 + λ 16 ≤ 1 + λ 4 . (1+\eta)(1+\varepsilon)+\frac{2pm}{r}\cdot\frac{2}{\eta}\leq\left(1+\frac{\lambda}{16}\right)^2+\frac{4p}{\eta}=\left(1+\frac{\lambda}{16}\right)^2+\frac{\lambda}{16}\leq1+\frac{\lambda}{4}. ( 1 + η ) ( 1 + ε ) + r 2 p m ⋅ η 2 ≤ ( 1 + 16 λ ) 2 + η 4 p = ( 1 + 16 λ ) 2 + 16 λ ≤ 1 + 4 λ .
Terms of order 1 n \frac{1}{n} n 1 . Since m , r ≥ n 4 m,r\geq\frac{n}{4} m , r ≥ 4 n ,
b η ( B + B 2 ) z ε + log 4 r a η ≤ 17 16 ⋅ 16 ( B + B 2 ) λ ⋅ 4 d n + 128 log 4 λ n ≤ K d λ n , b_\eta\frac{(B+B^2)z}{\varepsilon}+\frac{\log4}{r a_\eta}\leq\frac{17}{16}\cdot\frac{16(B+B^2)}{\lambda}\cdot\frac{4d}{n}+\frac{128\log4}{\lambda n}\leq K\frac{d}{\lambda n}, b η ε ( B + B 2 ) z + r a η log 4 ≤ 16 17 ⋅ λ 16 ( B + B 2 ) ⋅ n 4 d + λn 128 log 4 ≤ K λn d ,
where K = 68 ( B + B 2 ) + 178 K=68(B+B^2)+178 K = 68 ( B + B 2 ) + 178 .
Therefore,
E [ er D ( h ^ ) ] ≤ ( 1 + λ 4 ) er D ( h ) + K d λ n + 4 e − β n / 4 . (10) \mathbb{E}\left[\operatorname{er}_{D}(\widehat{h})\right]\leq\left(1+\frac{\lambda}{4}\right)\operatorname{er}_{D}(h)+K\frac{d}{\lambda n}+4e^{-\beta n/4}. \tag*{(10)} E [ er D ( h ) ] ≤ ( 1 + 4 λ ) er D ( h ) + K λn d + 4 e − β n /4 . (10)
Remove the comparator. The learner does not depend on h h h , and (10) holds for every h ∈ H h\in\mathcal{H} h ∈ H with er D ( h ) ≤ ρ \operatorname{er}_{D}(h)\leq\rho er D ( h ) ≤ ρ . Taking such h h h with er D ( h ) \operatorname{er}_{D}(h) er D ( h ) arbitrarily close to τ D \tau_D τ D gives
E [ er D ( h ^ ) ] ≤ ( 1 + λ ) τ D + K d λ n + 4 e − β n / 4 . \mathbb{E}\left[\operatorname{er}_{D}(\widehat{h})\right]\leq(1+\lambda)\tau_D+K\frac{d}{\lambda n}+4e^{-\beta n/4}. E [ er D ( h ) ] ≤ ( 1 + λ ) τ D + K λn d + 4 e − β n /4 .
Case 2: τ D > ρ / 2 \tau_D>\rho/2 τ D > ρ /2 . Now τ D \tau_D τ D is bounded below by a constant, so an additive error that is a small constant can be charged to λ τ D \lambda\tau_D λ τ D . Since uVCE ( H ) < ∞ \operatorname{uVCE}(\mathcal{H})<\infty uVCE ( H ) < ∞ we have v = VC ( H ) < ∞ v=\operatorname{VC}(\mathcal{H})<\infty v = VC ( H ) < ∞ by Lemma C.1 . Apply Lemma 5.8 to the ERM expert g ⋆ g_\star g ⋆ with ζ = λ ρ 64 < λ τ D 32 \zeta=\frac{\lambda\rho}{64}<\frac{\lambda\tau_D}{32} ζ = 64 λ ρ < 32 λ τ D :
E [ er D ( g ⋆ ) ] ≤ ( 1 + λ 32 ) τ D + A e − b m . \mathbb{E}[\operatorname{er}_{D}(g_\star)]\leq\left(1+\frac{\lambda}{32}\right)\tau_D+Ae^{-bm}. E [ er D ( g ⋆ )] ≤ ( 1 + 32 λ ) τ D + A e − bm .
Then apply Lemma 5.7 with Q Q Q the point mass on the expert ⋆ \star ⋆ . It is fixed in advance, so it is determined by S ( 0 ) S^{(0)} S ( 0 ) and S ( 1 ) S^{(1)} S ( 1 ) , and D K L ( Q ∥ π ) = log 1 π ( ⋆ ) = log 2 D_{\mathrm{KL}}(Q\mathbin\Vert\pi)=\log\frac{1}{\pi(\star)}=\log2 D KL ( Q ∥ π ) = log π ( ⋆ ) 1 = log 2 . Taking expectations and using (5) ,
E [ er D ( h ^ ) ] ≤ ( 1 + λ 16 ) ( 1 + λ 32 ) τ D + 2 A e − b n / 4 + 128 log 2 λ n ≤ ( 1 + λ ) τ D + K d λ n + 2 A e − b n / 4 . \mathbb{E}\left[\operatorname{er}_{D}(\widehat{h})\right]\leq\left(1+\frac{\lambda}{16}\right)\left(1+\frac{\lambda}{32}\right)\tau_D+2Ae^{-bn/4}+\frac{128\log2}{\lambda n}\leq(1+\lambda)\tau_D+K\frac{d}{\lambda n}+2Ae^{-bn/4}. E [ er D ( h ) ] ≤ ( 1 + 16 λ ) ( 1 + 32 λ ) τ D + 2 A e − bn /4 + λn 128 log 2 ≤ ( 1 + λ ) τ D + K λn d + 2 A e − bn /4 .
Conclude. In both cases
E [ er D ( h ^ ) ] − ( 1 + λ ) τ D ≤ K d λ n + C e − c n , C = 4 + 2 A , c = min { β , b } 4 . \mathbb{E}\left[\operatorname{er}_{D}(\widehat{h})\right]-(1+\lambda)\tau_D\leq K\frac{d}{\lambda n}+Ce^{-cn},\qquad C=4+2A,\quad c=\frac{\min\{\beta,b\}}{4}. E [ er D ( h ) ] − ( 1 + λ ) τ D ≤ K λn d + C e − c n , C = 4 + 2 A , c = 4 min { β , b } .
The constants β \beta β , A A A and b b b depend on D X \mathcal{D}_X D X (through q q q ), on λ \lambda λ and on H \mathcal{H} H , but not on the conditional distribution of Y Y Y given X X X . So C C C and c c c are the same for all D D D with marginal D X \mathcal{D}_X D X .
Remark 1. The result is for each fixed λ > 0 \lambda>0 λ > 0 ; the marginal-dependent remainder is not controlled uniformly as λ ↓ 0 \lambda\downarrow0 λ ↓ 0 , so the theorem does not permit choosing λ \lambda λ as a function of n n n to recover an agnostic bound with uVCE ( H ) \operatorname{uVCE}(\mathcal{H}) uVCE ( H ) .
Fine-grained lower bound
Theorem 5.9. Let 0 < λ ≤ 1 0<\lambda\leq1 0 < λ ≤ 1 and let H \mathcal{H} H be a concept class that has an infinite uncentered d d d -VC-eluder sequence for some d ≥ 1 d\geq1 d ≥ 1 . There exist a marginal D X \mathcal{D}_X D X and sample sizes n 1 < n 2 < ⋯ n_1<n_2<\cdots n 1 < n 2 < ⋯ such that for every learner A \mathcal{A} A and every k k k there is a distribution D D D with marginal D X \mathcal{D}_X D X satisfying
E S ∼ D n k [ er D ( A S ) ] − ( 1 + λ ) τ D ≥ 1 2048 ⋅ d λ n k . \mathbb{E}_{S\sim D^{n_k}}\left[\operatorname{er}_{D}(\mathcal{A}_S)\right]-(1+\lambda)\tau_D\geq\frac{1}{2048}\cdot\frac{d}{\lambda n_k}. E S ∼ D n k [ er D ( A S ) ] − ( 1 + λ ) τ D ≥ 2048 1 ⋅ λ n k d .
Idea. The idea is similar to the fine-grained lower bound for agnostic PAC learning. We spread the marginal over infinitely many shattered blocks with decaying masses. For each sample size n k n_k n k we look at one block that has little probability mass, so the sample contains only a few points from it. In this block we hide d d d bits in noisy labels, in the spirit of Assouad’s lemma [2 ] (Yu 1997). With so few points from the block, the learner cannot figure out most of the bits, and it pays for each bit it gets wrong. The noise level is chosen proportional to λ \lambda λ , so that the price of the wrong bits is larger than the slack that the factor ( 1 + λ ) (1+\lambda) ( 1 + λ ) gives the learner. The earlier blocks do not help, since all the concepts we use agree there, and the later blocks have too little mass to matter.
Proof. We first set up the three ingredients for the proof: the blocks, the witnesses, and the marginal.
Setup. Fix an infinite uncentered d d d -VC-eluder sequence B 1 , B 2 , … B_1,B_2,\ldots B 1 , B 2 , … with B k = { x k , 1 , … , x k , d } B_k=\{x_{k,1},\ldots,x_{k,d}\} B k = { x k , 1 , … , x k , d } . By Definition 3.4 , for each k k k there is F k ⊆ H F_k\subseteq\mathcal{H} F k ⊆ H that VC-shatters B k B_k B k and whose members all agree with each other on the earlier blocks B 1 ∪ ⋯ ∪ B k − 1 B_1\cup\cdots\cup B_{k-1} B 1 ∪ ⋯ ∪ B k − 1 . We record three consequences.
For each θ ∈ { 0 , 1 } d \theta\in\{0,1\}^{d} θ ∈ { 0 , 1 } d there is a witness h k , θ ∈ F k h_{k,\theta}\in F_k h k , θ ∈ F k with h k , θ ( x k , j ) = θ j h_{k,\theta}(x_{k,j})=\theta_j h k , θ ( x k , j ) = θ j for all j ∈ [ d ] j\in[d] j ∈ [ d ] .
There is a function c k c_k c k on B 1 ∪ ⋯ ∪ B k − 1 B_1\cup\cdots\cup B_{k-1} B 1 ∪ ⋯ ∪ B k − 1 such that h ( x ) = c k ( x ) h(x)=c_k(x) h ( x ) = c k ( x ) for every h ∈ F k h\in F_k h ∈ F k and every x x x in an earlier block. In words: on earlier blocks all witnesses carry the same labels, so these labels say nothing about θ \theta θ .
The blocks are pairwise disjoint: a point of an earlier block has the same label under every member of F k F_k F k , so it cannot belong to the shattered set B k B_k B k .
Let s = λ 128 s=\frac{\lambda}{128} s = 128 λ , and let D X D_X D X be the marginal that gives each point of B k B_k B k mass p k d \frac{p_k}{d} d p k , where p k = ( 1 − s ) s k − 1 p_k=(1-s)s^{k-1} p k = ( 1 − s ) s k − 1 is the total mass of block k k k (note ∑ k p k = 1 \sum_k p_k=1 ∑ k p k = 1 ). The total mass of the blocks after B k B_k B k , which we call the tail , is
t k = ∑ ℓ > k p ℓ = s 1 − s p k . t_k=\sum_{\ell>k}p_\ell=\frac{s}{1-s}p_k. t k = ℓ > k ∑ p ℓ = 1 − s s p k .
The geometric decay is what lets one marginal serve all sample sizes: block k k k has mass p k p_k p k , so it is the block that a sample of size about 1 p k \frac{1}{p_k} p k 1 has barely explored. For the k k k th sample size we hide d d d bits in block k k k .
Parameters. Take the noise level
γ = λ 1 + 2 λ , so that 0 < γ ≤ 1 3 and 1 2 − γ = 1 2 ( 1 + 2 λ ) , \gamma=\frac{\lambda}{1+2\lambda},
\qquad\text{so that}\qquad
0<\gamma\le\frac{1}{3}
\quad\text{and}\quad
\frac{1}{2}-\gamma=\frac{1}{2(1+2\lambda)}, γ = 1 + 2 λ λ , so that 0 < γ ≤ 3 1 and 2 1 − γ = 2 ( 1 + 2 λ ) 1 ,
and the sample sizes n k = ⌊ d 128 p k γ 2 ⌋ n_k=\left\lfloor\frac{d}{128p_k\gamma^2}\right\rfloor n k = ⌊ 128 p k γ 2 d ⌋ for k ≥ 2 k\ge2 k ≥ 2 . We use three facts about these choices.
The tail is negligible: since s ≤ 1 2 s\le\frac{1}{2} s ≤ 2 1 , t k = s 1 − s p k ≤ 2 s p k = λ 64 p k t_k=\frac{s}{1-s}p_k\le2sp_k=\frac{\lambda}{64}p_k t k = 1 − s s p k ≤ 2 s p k = 64 λ p k .
n k n_k n k is not too small: for k ≥ 2 k\ge2 k ≥ 2 we have p k ≤ s = λ 128 p_k\le s=\frac{\lambda}{128} p k ≤ s = 128 λ and γ ≤ λ ≤ 1 \gamma\le\lambda\le1 γ ≤ λ ≤ 1 , so 128 p k γ 2 ≤ 1 ≤ d 128p_k\gamma^2\le1\le d 128 p k γ 2 ≤ 1 ≤ d , i.e., d 128 p k γ 2 ≥ 1 \frac{d}{128p_k\gamma^2}\ge1 128 p k γ 2 d ≥ 1 . As ⌊ u ⌋ ≥ u / 2 \lfloor u\rfloor\ge u/2 ⌊ u ⌋ ≥ u /2 for u ≥ 1 u\ge1 u ≥ 1 ,
d 256 p k γ 2 ≤ n k ≤ d 128 p k γ 2 . (11) \frac{d}{256p_k\gamma^2}\le n_k\le\frac{d}{128p_k\gamma^2}. \tag*{(11)} 256 p k γ 2 d ≤ n k ≤ 128 p k γ 2 d . (11)
The n k n_k n k increase: p k + 1 = s p k ≤ p k 128 p_{k+1}=sp_k\le\frac{p_k}{128} p k + 1 = s p k ≤ 128 p k , so by (11) n k + 1 ≥ d 256 p k + 1 γ 2 ≥ 64 ⋅ d 128 p k γ 2 ≥ 64 n k > n k n_{k+1}\ge\frac{d}{256p_{k+1}\gamma^2}\ge64\cdot\frac{d}{128p_k\gamma^2}\ge64n_k>n_k n k + 1 ≥ 256 p k + 1 γ 2 d ≥ 64 ⋅ 128 p k γ 2 d ≥ 64 n k > n k .
Fix a learner A \mathcal{A} A and k ≥ 2 k\ge2 k ≥ 2 .
Construction. For θ ∈ { 0 , 1 } d \theta\in\{0,1\}^{d} θ ∈ { 0 , 1 } d let D θ \mathcal{D}_{\theta} D θ be the distribution with marginal D X \mathcal{D}_{X} D X in which the label y y y of a point x x x is drawn as follows:
if x x x lies in an earlier block ( B 1 , … , B k − 1 ) (B_{1},\ldots,B_{k-1}) ( B 1 , … , B k − 1 ) : y = c k ( x ) y=c_{k}(x) y = c k ( x ) ;
if x = x k , j x=x_{k,j} x = x k , j lies in the current block: y = θ j y=\theta_{j} y = θ j with probability 1 2 + γ \frac{1}{2}+\gamma 2 1 + γ , and y = 1 − θ j y=1-\theta_{j} y = 1 − θ j otherwise;
if x x x lies in a later block: y = 0 y=0 y = 0 .
Only the labels in the current block depend on θ \theta θ . This is the reason for labeling the tail by the constant 0 0 0 rather than by h k , θ h_{k,\theta} h k , θ : the values of h k , θ h_{k,\theta} h k , θ on later blocks are not controlled by the definition and could reveal θ \theta θ to the learner.
The comparator is small. The witness h k , θ h_{k,\theta} h k , θ never makes a mistake on earlier blocks (there it equals c k c_{k} c k ). It makes a mistake with probability 1 2 − γ \frac{1}{2}-\gamma 2 1 − γ on each point of B k B_{k} B k (there it predicts θ j \theta_{j} θ j ), and may make a mistake on the tail, whose total mass is t k t_{k} t k . Since h k , θ ∈ H h_{k,\theta}\in\mathcal{H} h k , θ ∈ H , we get
τ D θ ≤ er D θ ( h k , θ ) ≤ p k ( 1 2 − γ ) + t k . (12) \tau_{\mathcal{D}_{\theta}}\leq\operatorname{er}_{\mathcal{D}_{\theta}}(h_{k,\theta})\leq p_{k}\left(\frac{1}{2}-\gamma\right)+t_{k}. \tag*{(12)} τ D θ ≤ er D θ ( h k , θ ) ≤ p k ( 2 1 − γ ) + t k . (12)
The learner’s error on the current block. Let ξ \xi ξ denote the internal randomness of A \mathcal{A} A , which is independent of the sample, and let q j ( θ ) = P [ A S ( x k , j ) ≠ θ j ] q_{j}(\theta)=\mathbb{P}[A_{S}(x_{k,j})\neq\theta_{j}] q j ( θ ) = P [ A S ( x k , j ) = θ j ] be the probability that the learner gets bit j j j wrong, where S ∼ D θ n k S\sim\mathcal{D}_{\theta}^{n_{k}} S ∼ D θ n k and the probability is also over ξ \xi ξ . By construction, the label at x k , j x_{k,j} x k , j equals θ j \theta_{j} θ j with probability 1 2 + γ \frac{1}{2}+\gamma 2 1 + γ . So a classifier g : X → Y g:\mathcal{X}\to\mathcal{Y} g : X → Y errs at x k , j x_{k,j} x k , j with probability 1 2 − γ \frac{1}{2}-\gamma 2 1 − γ if g ( x k , j ) = θ j g(x_{k,j})=\theta_{j} g ( x k , j ) = θ j , and with probability 1 2 + γ \frac{1}{2}+\gamma 2 1 + γ otherwise; in both cases the error probability at x k , j x_{k,j} x k , j is 1 2 − γ + 2 γ 1 [ g ( x k , j ) ≠ θ j ] \frac{1}{2}-\gamma+2\gamma\mathbb{1}[g(x_{k,j})\neq\theta_{j}] 2 1 − γ + 2 γ 1 [ g ( x k , j ) = θ j ] . Each point of B k B_{k} B k has mass p k d \frac{p_{k}}{d} d p k , and the error on the other blocks is nonnegative, so er D θ ( g ) ≥ ∑ j = 1 d p k d ( 1 2 − γ + 2 γ 1 [ g ( x k , j ) ≠ θ j ] ) \operatorname{er}_{\mathcal{D}_{\theta}}(g)\geq\sum_{j=1}^{d}\frac{p_{k}}{d}\left(\frac{1}{2}-\gamma+2\gamma\mathbb{1}[g(x_{k,j})\neq\theta_{j}]\right) er D θ ( g ) ≥ ∑ j = 1 d d p k ( 2 1 − γ + 2 γ 1 [ g ( x k , j ) = θ j ] ) . Applying this to g = A S g=A_{S} g = A S (which need not belong to H \mathcal{H} H ) and taking the expectation over S ∼ D θ n k S\sim\mathcal{D}_{\theta}^{n_{k}} S ∼ D θ n k and ξ \xi ξ ,
E S ∼ D θ n k [ er D θ ( A S ) ] ≥ ∑ j = 1 d p k d ( 1 2 − γ + 2 γ q j ( θ ) ) . (13) \mathbb{E}_{S\sim\mathcal{D}_{\theta}^{n_{k}}}[\operatorname{er}_{\mathcal{D}_{\theta}}(A_{S})]\geq\sum_{j=1}^{d}\frac{p_{k}}{d}\left(\frac{1}{2}-\gamma+2\gamma q_{j}(\theta)\right). \tag*{(13)} E S ∼ D θ n k [ er D θ ( A S )] ≥ j = 1 ∑ d d p k ( 2 1 − γ + 2 γ q j ( θ ) ) . (13)
It remains to show that the learner gets many bits wrong, i.e., that the q j ( θ ) q_{j}(\theta) q j ( θ ) are large on average.
The learner cannot tell θ j = 0 \theta_{j}=0 θ j = 0 from θ j = 1 \theta_{j}=1 θ j = 1 . Fix j ∈ [ d ] j\in[d] j ∈ [ d ] and θ ∈ { 0 , 1 } d \theta\in\{0,1\}^{d} θ ∈ { 0 , 1 } d , and let θ ( j ) \theta^{(j)} θ ( j ) denote θ \theta θ with its j j j th bit flipped. Let P θ P_{\theta} P θ be the joint law of ( S , ξ ) (S,\xi) ( S , ξ ) when S ∼ D θ n k S\sim\mathcal{D}_{\theta}^{n_{k}} S ∼ D θ n k , and consider the event E = { ( S , ξ ) : A S ( x k , j ) ≠ θ j } E=\{(S,\xi):A_{S}(x_{k,j})\neq\theta_{j}\} E = {( S , ξ ) : A S ( x k , j ) = θ j } . The learner is wrong about bit j j j under D θ \mathcal{D}_{\theta} D θ exactly when ( S , ξ ) ∈ E (S,\xi)\in E ( S , ξ ) ∈ E , and, because θ j ( j ) = 1 − θ j \theta_{j}^{(j)}=1-\theta_{j} θ j ( j ) = 1 − θ j , it is wrong about bit j j j under D θ ( j ) \mathcal{D}_{\theta^{(j)}} D θ ( j ) exactly when ( S , ξ ) ∉ E (S,\xi)\notin E ( S , ξ ) ∈ / E . Therefore
q j ( θ ) + q j ( θ ( j ) ) = P θ ( E ) + 1 − P θ ( j ) ( E ) ≥ 1 − TV ( P θ , P θ ( j ) ) = 1 − TV ( D θ n k , D θ ( j ) n k ) , (14) q_{j}(\theta)+q_{j}\left(\theta^{(j)}\right)=P_{\theta}(E)+1-P_{\theta^{(j)}}(E)\geq1-\operatorname{TV}(P_{\theta},P_{\theta^{(j)}})=1-\operatorname{TV}\left(\mathcal{D}_{\theta}^{n_{k}},\mathcal{D}_{\theta^{(j)}}^{n_{k}}\right), \tag*{(14)} q j ( θ ) + q j ( θ ( j ) ) = P θ ( E ) + 1 − P θ ( j ) ( E ) ≥ 1 − TV ( P θ , P θ ( j ) ) = 1 − TV ( D θ n k , D θ ( j ) n k ) , (14)
where the last equality holds because ξ \xi ξ has the same law under both and is independent of S S S . So it suffices to show that the total variation distance TV ( D θ n k , D θ ( j ) n k ) = sup E ′ ∣ D θ n k ( E ′ ) − D θ ( j ) n k ( E ′ ) ∣ \operatorname{TV}\left(\mathcal{D}_{\theta}^{n_{k}},\mathcal{D}_{\theta^{(j)}}^{n_{k}}\right)=\sup_{E'}\left|\mathcal{D}_{\theta}^{n_{k}}(E')-\mathcal{D}_{\theta^{(j)}}^{n_{k}}(E')\right| TV ( D θ n k , D θ ( j ) n k ) = sup E ′ D θ n k ( E ′ ) − D θ ( j ) n k ( E ′ ) is small. We bound it through the KL divergence.
The distributions D θ \mathcal{D}_{\theta} D θ and D θ ( j ) \mathcal{D}_{\theta^{(j)}} D θ ( j ) have the same marginal and differ only in the label at x k , j x_{k,j} x k , j : there the label equals θ j \theta_{j} θ j with probability 1 2 + γ \frac{1}{2}+\gamma 2 1 + γ under D θ \mathcal{D}_{\theta} D θ and with probability 1 2 − γ \frac{1}{2}-\gamma 2 1 − γ under D θ ( j ) \mathcal{D}_{\theta^{(j)}} D θ ( j ) . The labels on earlier and later blocks do not depend on θ \theta θ at all. Since x k , j x_{k,j} x k , j has mass p k d \frac{p_{k}}{d} d p k , the chain rule for the KL divergence gives
D K L ( D θ ∥ D θ ( j ) ) = p k d D K L ( Ber ( 1 2 + γ ) ∥ Ber ( 1 2 − γ ) ) = 2 γ p k d ln 1 + 2 γ 1 − 2 γ ≤ 8 γ 2 1 − 4 γ 2 p k d ≤ 16 γ 2 p k d , \mathrm{D}_{\mathrm{KL}}(\mathcal{D}_{\theta}\Vert\mathcal{D}_{\theta^{(j)}})=\frac{p_{k}}{d}\mathrm{D}_{\mathrm{KL}}\left(\operatorname{Ber}\left(\frac{1}{2}+\gamma\right)\middle\Vert\operatorname{Ber}\left(\frac{1}{2}-\gamma\right)\right)=\frac{2\gamma p_{k}}{d}\ln\frac{1+2\gamma}{1-2\gamma}\leq\frac{8\gamma^{2}}{1-4\gamma^{2}}\frac{p_{k}}{d}\leq\frac{16\gamma^{2}p_{k}}{d}, D KL ( D θ ∥ D θ ( j ) ) = d p k D KL ( Ber ( 2 1 + γ ) Ber ( 2 1 − γ ) ) = d 2 γ p k ln 1 − 2 γ 1 + 2 γ ≤ 1 − 4 γ 2 8 γ 2 d p k ≤ d 16 γ 2 p k ,
where we used ln 1 + u 1 − u ≤ 2 u 1 − u 2 \ln\frac{1+u}{1-u} \le\frac{2u}{1-u^2} ln 1 − u 1 + u ≤ 1 − u 2 2 u with u = 2 γ u=2\gamma u = 2 γ , and 1 − 4 γ 2 ≥ 5 9 ≥ 1 2 1-4\gamma^2 \ge\frac{5}{9} \ge\frac{1}{2} 1 − 4 γ 2 ≥ 9 5 ≥ 2 1 since γ ≤ 1 3 \gamma\le\frac{1}{3} γ ≤ 3 1 . The KL divergence is additive over the n k n_k n k i.i.d. samples, so by the upper bound in (11) ,
D K L ( D θ n k ∥ D θ ( j ) n k ) ≤ 16 n k p k γ 2 d ≤ 1 8 . D_{\mathrm{KL}}\left(\mathcal{D}_{\theta}^{n_k} \,\middle\|\, \mathcal{D}_{\theta^{(j)}}^{n_k}\right) \le\frac{16n_kp_k\gamma^2}{d} \le\frac{1}{8}. D KL ( D θ n k D θ ( j ) n k ) ≤ d 16 n k p k γ 2 ≤ 8 1 .
By Pinsker’s inequality,
TV ( D θ n k , D θ ( j ) n k ) ≤ 1 2 D K L ( D θ n k ∥ D θ ( j ) n k ) ≤ 1 16 = 1 4 , \operatorname{TV}\left(\mathcal{D}_{\theta}^{n_k},\mathcal{D}_{\theta^{(j)}}^{n_k}\right) \le\sqrt{\frac{1}{2}D_{\mathrm{KL}}\left(\mathcal{D}_{\theta}^{n_k}\,\middle\|\,\mathcal{D}_{\theta^{(j)}}^{n_k}\right)} \le\sqrt{\frac{1}{16}}=\frac{1}{4}, TV ( D θ n k , D θ ( j ) n k ) ≤ 2 1 D KL ( D θ n k D θ ( j ) n k ) ≤ 16 1 = 4 1 ,
and therefore q j ( θ ) + q j ( θ ( j ) ) ≥ 3 4 q_j(\theta)+q_j(\theta^{(j)})\ge\frac{3}{4} q j ( θ ) + q j ( θ ( j ) ) ≥ 4 3 by (14) .
Average over θ \theta θ . The vectors θ ∈ { 0 , 1 } d \theta\in\{0,1\}^d θ ∈ { 0 , 1 } d split into 2 d − 1 2^{d-1} 2 d − 1 pairs { θ , θ ( j ) } \{\theta,\theta^{(j)}\} { θ , θ ( j ) } , and by the previous step each pair contributes at least 3 4 \frac{3}{4} 4 3 . Hence
1 2 d ∑ θ ∈ { 0 , 1 } d q j ( θ ) = 1 2 d ∑ θ : θ j = 0 ( q j ( θ ) + q j ( θ ( j ) ) ) ≥ 1 2 d ⋅ 2 d − 1 ⋅ 3 4 = 3 8 \frac{1}{2^d}\sum_{\theta\in\{0,1\}^d}q_j(\theta)=\frac{1}{2^d}\sum_{\theta:\theta_j=0}\left(q_j(\theta)+q_j(\theta^{(j)})\right)\ge\frac{1}{2^d}\cdot2^{d-1}\cdot\frac{3}{4}=\frac{3}{8} 2 d 1 θ ∈ { 0 , 1 } d ∑ q j ( θ ) = 2 d 1 θ : θ j = 0 ∑ ( q j ( θ ) + q j ( θ ( j ) ) ) ≥ 2 d 1 ⋅ 2 d − 1 ⋅ 4 3 = 8 3
for every j ∈ [ d ] j\in[d] j ∈ [ d ] .
Averaging (13) over a uniformly random θ \theta θ therefore gives
1 2 d ∑ θ E S ∼ D θ n k [ er D θ ( A S ) ] ≥ p k ( 1 2 − γ ) + 2 γ p k ⋅ 3 8 = p k ( 1 2 − γ ) + 3 4 γ p k . (15) \frac{1}{2^d}\sum_{\theta}\mathbb{E}_{S\sim\mathcal{D}_{\theta}^{n_k}}\left[\operatorname{er}_{D_\theta}(\mathcal{A}_S)\right]\ge p_k\left(\frac{1}{2}-\gamma\right)+2\gamma p_k\cdot\frac{3}{8}=p_k\left(\frac{1}{2}-\gamma\right)+\frac{3}{4}\gamma p_k. \tag*{(15)} 2 d 1 θ ∑ E S ∼ D θ n k [ er D θ ( A S ) ] ≥ p k ( 2 1 − γ ) + 2 γ p k ⋅ 8 3 = p k ( 2 1 − γ ) + 4 3 γ p k . (15)
Subtract the relaxed comparator. Subtracting ( 1 + λ ) (1+\lambda) ( 1 + λ ) times (12) from (15) , the term p k ( 1 2 − γ ) p_k\left(\frac{1}{2}-\gamma\right) p k ( 2 1 − γ ) cancels once and
1 2 d ∑ θ ( E S ∼ D θ n k [ er D θ ( A S ) ] − ( 1 + λ ) τ D θ ) ≥ 3 4 γ p k ⏟ wrong bits − λ ( 1 2 − γ ) p k ⏟ slack on the block − ( 1 + λ ) t k ⏟ tail . \frac{1}{2^d}\sum_{\theta}\left(\mathbb{E}_{S\sim\mathcal{D}_{\theta}^{n_k}}\left[\operatorname{er}_{D_\theta}(\mathcal{A}_S)\right]-(1+\lambda)\tau_{D_\theta}\right)\ge\underbrace{\frac{3}{4}\gamma p_k}_{\text{wrong bits}}-\underbrace{\lambda\left(\frac{1}{2}-\gamma\right)p_k}_{\text{slack on the block}}-\underbrace{(1+\lambda)t_k}_{\text{tail}}. 2 d 1 θ ∑ ( E S ∼ D θ n k [ er D θ ( A S ) ] − ( 1 + λ ) τ D θ ) ≥ wrong bits 4 3 γ p k − slack on the block λ ( 2 1 − γ ) p k − tail ( 1 + λ ) t k .
This is where the choice of γ \gamma γ is used. Since γ = λ 1 + 2 λ \gamma=\frac{\lambda}{1+2\lambda} γ = 1 + 2 λ λ and 1 2 − γ = 1 2 ( 1 + 2 λ ) \frac{1}{2}-\gamma=\frac{1}{2(1+2\lambda)} 2 1 − γ = 2 ( 1 + 2 λ ) 1 , the wrong bits beat the slack:
3 4 γ p k − λ ( 1 2 − γ ) p k = 3 λ p k 4 ( 1 + 2 λ ) − λ p k 2 ( 1 + 2 λ ) = λ p k 4 ( 1 + 2 λ ) . \frac{3}{4}\gamma p_k-\lambda\left(\frac{1}{2}-\gamma\right)p_k=\frac{3\lambda p_k}{4(1+2\lambda)}-\frac{\lambda p_k}{2(1+2\lambda)}=\frac{\lambda p_k}{4(1+2\lambda)}. 4 3 γ p k − λ ( 2 1 − γ ) p k = 4 ( 1 + 2 λ ) 3 λ p k − 2 ( 1 + 2 λ ) λ p k = 4 ( 1 + 2 λ ) λ p k .
For the tail, 1 + λ < 2 1+\lambda<2 1 + λ < 2 and t k ≤ λ 64 p k t_k\le\frac{\lambda}{64}p_k t k ≤ 64 λ p k give ( 1 + λ ) t k ≤ λ p k 32 ≤ λ p k 8 ( 1 + 2 λ ) (1+\lambda)t_k\le\frac{\lambda p_k}{32}\le\frac{\lambda p_k}{8(1+2\lambda)} ( 1 + λ ) t k ≤ 32 λ p k ≤ 8 ( 1 + 2 λ ) λ p k , using 1 + 2 λ ≤ 3 ≤ 4 1+2\lambda\le3\le4 1 + 2 λ ≤ 3 ≤ 4 . Hence the average excess error is at least
λ p k 4 ( 1 + 2 λ ) − λ p k 8 ( 1 + 2 λ ) = λ p k 8 ( 1 + 2 λ ) . \frac{\lambda p_k}{4(1+2\lambda)}-\frac{\lambda p_k}{8(1+2\lambda)}=\frac{\lambda p_k}{8(1+2\lambda)}. 4 ( 1 + 2 λ ) λ p k − 8 ( 1 + 2 λ ) λ p k = 8 ( 1 + 2 λ ) λ p k .
Finally, the lower bound in (11) gives p k ≥ d 256 γ 2 n k = d ( 1 + 2 λ ) 2 256 λ 2 n k p_k\ge\frac{d}{256\gamma^2n_k}=\frac{d(1+2\lambda)^2}{256\lambda^2n_k} p k ≥ 256 γ 2 n k d = 256 λ 2 n k d ( 1 + 2 λ ) 2 , so
λ p k 8 ( 1 + 2 λ ) ≥ d ( 1 + 2 λ ) 2048 λ n k ≥ d 2048 λ n k . \frac{\lambda p_k}{8(1+2\lambda)}\ge\frac{d(1+2\lambda)}{2048\lambda n_k}\ge\frac{d}{2048\lambda n_k}. 8 ( 1 + 2 λ ) λ p k ≥ 2048 λ n k d ( 1 + 2 λ ) ≥ 2048 λ n k d .
Some θ \theta θ attains at least the average; take D = D θ D=D_\theta D = D θ .
The sample sizes n k n_k n k are defined and increasing for k ≥ 2 k\ge2 k ≥ 2 . Relabeling them as n 1 < n 2 < ⋯ n_1<n_2<\cdots n 1 < n 2 < ⋯ gives the statement of the theorem.
Conclusion
We studied marginal-nonuniform learning in the agnostic case, for binary classification, at the level of both rates and fine-grained rates. In the standard agnostic setting, allowing the constants to depend on the marginal does not help: a class is learnable at rate 1 n \frac{1}{\sqrt{n}} n 1 exactly when its VC dimension is finite, and the fine-grained rate is VC ( H ) / n \sqrt{\operatorname{VC}(\mathcal{H})/n} VC ( H ) / n , as in uniform PAC learning, with a lower bound attained by a single marginal. In the relaxed setting, where the learner competes with ( 1 + λ ) inf h ∈ H er D ( h ) (1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_D(h) ( 1 + λ ) inf h ∈ H er D ( h ) , the picture of the realizable case returns. The rates form the same trichotomy as in the realizable case: exponential for finite classes, linear for infinite classes of finite VC dimension, and arbitrarily slow otherwise. The fine-grained rate is of order d λ n \frac{d}{\lambda n} λn d , where d d d is the uncentered VC-eluder dimension, and the marginal only affects an exponentially small term. So the slow rate of the agnostic setting comes only from competing with the best concept exactly: any constant multiplicative slack restores the realizable rates, and even makes finite classes learnable at an exponential rate.
We expect the ideas of this paper to extend to multiclass classification with a bounded label space. The lower bounds only use the labels of a shattered set, and the upper bound is built from three ingredients that are not specific to two labels: the exhaustion lemma, which Brukhim et al. [ [11 ] already prove in the multiclass setting; the version spaces of clean subsamples; and aggregation by exponential weights. With the VC dimension replaced by a suitable multiclass dimension and a multiclass first-order learner in place of the binary one, we believe the same arguments go through, with constants that depend on the number of labels. The main open problem is the case of an infinite label space, where two dimensions play a role [13 ] .
Existence of the first-order learner
Our upper bounds run a learner inside a version space of H \mathcal{H} H , and they need a guarantee whose lower-order term scales with the complexity of that version space. Known first-order guarantees for agnostic PAC learning [33 ] (Hanneke et al. 2024) assume that the class has VC dimension at most k k k . This is not what we have. The version spaces used in § 5.3 are only simple in the distributional sense, VC D X ( V ) ≤ k \operatorname{VC}_{D_{\mathcal{X}}}(\mathcal{V}) \le k VC D X ( V ) ≤ k , and their VC dimension can be much larger than k k k . For instance, let X = { z 1 , … , z M } ∪ N \mathcal{X} = \{z_1, \ldots, z_M\} \cup\mathbb{N} X = { z 1 , … , z M } ∪ N , and let H \mathcal{H} H consist of all labelings of z 1 , … , z M z_1, \ldots, z_M z 1 , … , z M that are 0 0 0 on N \mathbb{N} N , together with the indicator functions 1 { x } \mathbb{1}_{\{x\}} 1 { x } of the points x ∈ N x \in\mathbb{N} x ∈ N . Then VC ( H ) = M \operatorname{VC}(\mathcal{H}) = M VC ( H ) = M while uVCE ( H ) = 1 \operatorname{uVCE}(\mathcal{H}) = 1 uVCE ( H ) = 1 . If D X D_{\mathcal{X}} D X puts no mass on the points z j z_j z j , then no sample contains them, so every version space still VC-shatters { z 1 , … , z M } \{z_1, \ldots, z_M\} { z 1 , … , z M } . Every version space thus has VC dimension M M M , while its distributional VC dimension is at most 1 1 1 . Applying a first-order guarantee with k = M k = M k = M would give a bound of order VC ( H ) λ n \frac{\operatorname{VC}(\mathcal{H})}{\lambda_n} λ n VC ( H ) instead of uVCE ( H ) λ n \frac{\operatorname{uVCE}(\mathcal{H})}{\lambda_n} λ n uVCE ( H ) . Moreover, the learner does not know D X D_{\mathcal{X}} D X , so it cannot discard the part of the class that lives on a set of probability zero. We therefore need a first-order learner whose guarantee depends only on the distributional VC dimension. Definition Definition 3.6 asks for such a learner, and Lemma A.1 shows that it exists. The point is that a shattered set of probability zero almost surely never appears among the sample points or the test point, so a learner whose guarantee depends only on the points it sees is not affected by it.
Lemma A.1. A first-order learner in the sense of Definition 3.6 exists.
Proof. We use a rule B \mathcal{B} B with the following leave-one-out guarantee [33 ] : there are universal constants c 1 , c 2 c_1, c_2 c 1 , c 2 such that for every N N N , every labeled sequence z 1 , … , z N z_1,\ldots,z_N z 1 , … , z N with z i = ( x i , y i ) z_i=(x_i,y_i) z i = ( x i , y i ) , and every class V \mathcal{V} V whose trace on ( x 1 , … , x N ) (x_1,\ldots,x_N) ( x 1 , … , x N ) has VC dimension at most k k k ,
1 N ∑ i = 1 N P [ B V ( z − i ) ( x i ) ≠ y i ] ≤ L ∗ + c 1 L ∗ k N + c 2 k N , L ∗ = min h ∈ V 1 N ∑ i = 1 N 1 [ h ( x i ) ≠ y i ] , \frac{1}{N}\sum_{i=1}^{N}\mathbb{P}[\mathcal{B}_{\mathcal{V}}(z_{-i})(x_i)\ne y_i]\le L^*+c_1\sqrt{\frac{L^*k}{N}}+c_2\frac{k}{N},\qquad L^*=\min_{h\in\mathcal{V}}\frac{1}{N}\sum_{i=1}^{N}\mathbb{1}[h(x_i)\ne y_i], N 1 i = 1 ∑ N P [ B V ( z − i ) ( x i ) = y i ] ≤ L ∗ + c 1 N L ∗ k + c 2 N k , L ∗ = h ∈ V min N 1 i = 1 ∑ N 1 [ h ( x i ) = y i ] ,
where z − i z_{-i} z − i is the sequence with z i z_i z i removed and the probability is over the randomness of B \mathcal{B} B .
Now let S ∼ D n S\sim\mathcal{D}^n S ∼ D n and draw a fresh ( X , Y ) ∼ D (X,Y)\sim\mathcal{D} ( X , Y ) ∼ D , so that z 1 , … , z n + 1 z_1,\ldots,z_{n+1} z 1 , … , z n + 1 are i.i.d. from D \mathcal{D} D .
The trace condition holds almost surely. If VC D X ( V ) ≤ k \operatorname{VC}_{\mathcal{D}_X}(\mathcal{V})\le k VC D X ( V ) ≤ k , then each of the ( n + 1 k + 1 ) \binom{n+1}{k+1} ( k + 1 n + 1 ) sub-tuples of size k + 1 k+1 k + 1 of ( x 1 , … , x n + 1 ) (x_1,\ldots,x_{n+1}) ( x 1 , … , x n + 1 ) is shattered by V \mathcal{V} V with probability 0 0 0 , so the trace of V \mathcal{V} V on these points has VC dimension at most k k k almost surely.
Exchangeability. Since the z i z_i z i are i.i.d., each term of the leave-one-out average has the same expectation as the error of B V ( S ) \mathcal{B}_{\mathcal{V}}(S) B V ( S ) on the fresh point, so E [ er D ( B V ( S ) ) ] \mathbb{E}[\operatorname{er}_{\mathcal{D}}(\mathcal{B}_{\mathcal{V}}(S))] E [ er D ( B V ( S ))] equals the expected left-hand side above with N = n + 1 N=n+1 N = n + 1 .
Jensen. Taking expectations and using concavity of the square root,
E [ er D ( B V ( S ) ) ] ≤ E [ L ∗ ] + c 1 E [ L ∗ ] k n + 1 + c 2 k n + 1 . \mathbb{E}[\operatorname{er}_{\mathcal{D}}(\mathcal{B}_{\mathcal{V}}(S))]\le\mathbb{E}[L^*]+c_1\sqrt{\frac{\mathbb{E}[L^*]k}{n+1}}+c_2\frac{k}{n+1}. E [ er D ( B V ( S ))] ≤ E [ L ∗ ] + c 1 n + 1 E [ L ∗ ] k + c 2 n + 1 k .
Finally, for every h ∈ V h\in\mathcal{V} h ∈ V we have E [ L ∗ ] ≤ er D ( h ) \mathbb{E}[L^*]\le\operatorname{er}_{\mathcal{D}}(h) E [ L ∗ ] ≤ er D ( h ) , hence E [ L ∗ ] ≤ τ D , V \mathbb{E}[L^*]\le\tau_{\mathcal{D},\mathcal{V}} E [ L ∗ ] ≤ τ D , V . This gives (1) with B = max { c 1 , c 2 , 1 } B=\max\{c_1,c_2,1\} B = max { c 1 , c 2 , 1 } .
Remark 2. Hanneke et al. [2024] were the first to obtain a first-order bound with the optimal τ D , V k / n \sqrt{\tau_{\mathcal{D},\mathcal{V}}k/n} τ D , V k / n term, with an additional polylogarithmic factor in the lower-order term. Using their learner in place of B \mathcal{B} B , the same argument gives E [ er D ( A λ , S ) ] − ( 1 + λ ) τ D ≤ K d polylog ( n / d ) λ n + C e − c n \mathbb{E}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}_{\lambda,S})]-(1+\lambda)\tau_{\mathcal{D}}\le K\frac{d\,\operatorname{polylog}(n/d)}{\lambda n}+Ce^{-cn} E [ er D ( A λ , S )] − ( 1 + λ ) τ D ≤ K λn d polylog ( n / d ) + C e − c n . The optimal learner of Mathiasen et al. [ [33 ] removes the logarithmic factor, which is what gives the exact fine-grained rate d λ n \frac{d}{\lambda n} λn d and the linear rate in Theorem 5.1 .
Measurability
As in Bousquet et al. [ [9 ] and Hanneke et al. [ [25 ] , we assume that X \mathcal{X} X is a Polish space with its Borel σ \sigma σ -algebra and that H \mathcal{H} H is measurable in the following sense: there are a Polish space Θ \Theta Θ and a Borel map ( θ , x ) ↦ h θ ( x ) (\theta,x)\mapsto h_\theta(x) ( θ , x ) ↦ h θ ( x ) such that H = { h θ : θ ∈ Θ } \mathcal{H}=\{h_\theta:\theta\in\Theta\} H = { h θ : θ ∈ Θ } . Under this assumption, every event in this paper that is defined by an existential quantifier over H \mathcal{H} H (for example, that a tuple of points is VC-shattered by a version space) is an analytic set, hence universally measurable, so all the probabilities we write are well defined. We also assume that the learning rules we use, namely ERM and the first-order learner, are universally measurable functions of the data; for ERM such a choice exists by the Jankov–von Neumann uniformization theorem. If H \mathcal{H} H is countable, all of this holds trivially.
The uncentered VC-eluder dimension
In this appendix we collect the properties of uVCE that we use, and we show that for binary classification it coincides with the VC-eluder dimension of Hanneke and Xu [2024], which characterizes the realizable marginal-nonuniform rate [25 ] . All statements here are purely combinatorial.
We first recall the centered notion. Following Hanneke and Xu [2024], an infinite d d d -VC-eluder sequence for H \mathcal{H} H is a sequence of labeled points ( x 1 , y 1 ) , ( x 2 , y 2 ) , … (x_1,y_1),(x_2,y_2),\ldots ( x 1 , y 1 ) , ( x 2 , y 2 ) , … such that every finite prefix is realizable by H \mathcal{H} H and, for every k ≥ 1 k\ge1 k ≥ 1 , the block { x ( k − 1 ) d + 1 , … , x k d } \{x_{(k-1)d+1},\ldots,x_{kd}\} { x ( k − 1 ) d + 1 , … , x k d } is VC-shattered by the version space { h ∈ H : h ( x i ) = y i for all i ≤ ( k − 1 ) d } \{h\in\mathcal{H}:h(x_i)=y_i\text{ for all }i\le(k-1)d\} { h ∈ H : h ( x i ) = y i for all i ≤ ( k − 1 ) d } . The VC-eluder dimension VCE ( H ) \operatorname{VCE}(\mathcal{H}) VCE ( H ) is the largest d d d for which such a sequence exists, with VCE ( H ) = 0 \operatorname{VCE}(\mathcal{H})=0 VCE ( H ) = 0 if there is none for d = 1 d=1 d = 1 and VCE ( H ) = ∞ \operatorname{VCE}(\mathcal{H})=\infty VCE ( H ) = ∞ if there is one for every d d d .
The two notions differ in what the witnesses must agree on. In the centered version, all concepts that shatter a block agree with one fixed labeling of the earlier blocks. In the uncentered version (Definition 3.4 ), the concepts that shatter block k k k only need to agree with each other on the earlier blocks, and different blocks may use different labelings of the past. For binary labels this extra freedom does not help.
Proposition 1. For every concept class H ⊆ { 0 , 1 } X \mathcal{H} \subseteq\{0,1\}^{\mathcal{X}} H ⊆ { 0 , 1 } X and every d ≥ 1 d \ge1 d ≥ 1 , H \mathcal{H} H has an infinite uncentered d d d -VC-eluder sequence if and only if it has an infinite d d d -VC-eluder sequence. In particular, uVCE ( H ) = VCE ( H ) \operatorname{uVCE}(\mathcal{H}) = \operatorname{VCE}(\mathcal{H}) uVCE ( H ) = VCE ( H ) .
Proof. Centered implies uncentered. Given an infinite d d d -VC-eluder sequence, let B k B_k B k be its k k k th block and F k \mathcal{F}_k F k the version space of the labeled points before B k B_k B k . Then F k \mathcal{F}_k F k shatters B k B_k B k , and all its members agree with the labels y i y_i y i on the earlier blocks, so in particular they agree with each other there. Hence B 1 , B 2 , … B_1, B_2, \ldots B 1 , B 2 , … is an infinite uncentered d d d -VC-eluder sequence.
Uncentered implies centered. Let B 1 , B 2 , … B_1, B_2, \ldots B 1 , B 2 , … be an infinite uncentered d d d -VC-eluder sequence. For each k k k let F k ⊆ H \mathcal{F}_k \subseteq\mathcal{H} F k ⊆ H shatter B k B_k B k with all members agreeing with each other on B 1 ∪ ⋯ ∪ B k − 1 B_1 \cup\cdots\cup B_{k-1} B 1 ∪ ⋯ ∪ B k − 1 , and let c k c_k c k be their common labeling there. We pass to a subsequence along which these labelings are consistent. Let N 0 = N N_0 = \mathbb{N} N 0 = N . Given an infinite set N j − 1 ⊆ N N_{j-1} \subseteq\mathbb{N} N j − 1 ⊆ N , let k j = min N j − 1 k_j = \min N_{j-1} k j = min N j − 1 . For every k ∈ N j − 1 k \in N_{j-1} k ∈ N j − 1 with k > k j k > k_j k > k j , the restriction of c k c_k c k to B k j B_{k_j} B k j is one of the 2 d 2^d 2 d labelings of B k j B_{k_j} B k j , so some labeling σ j \sigma_j σ j occurs for infinitely many such k k k . Let N j N_j N j be the set of these k k k ; it is infinite, and N j ⊆ N j − 1 N_j \subseteq N_{j-1} N j ⊆ N j − 1 . Since k j ∈ N j − 1 ⊆ N i k_j \in N_{j-1} \subseteq N_i k j ∈ N j − 1 ⊆ N i for all i < j i < j i < j , we have
c k j = σ i on B k i for all i < j . (16) c_{k_j} = \sigma_i \text{ on } B_{k_i} \qquad\text{for all } i < j. \tag*{(16)} c k j = σ i on B k i for all i < j . (16)
Now list the blocks B k 1 , B k 2 , … B_{k_1}, B_{k_2}, \ldots B k 1 , B k 2 , … in this order, labeling the points of B k i B_{k_i} B k i by σ i \sigma_i σ i . We check that this is an infinite d d d -VC-eluder sequence.
Every block is shattered by the current version space. Let V j \mathcal{V}_j V j be the set of concepts that equal σ i \sigma_i σ i on B k i B_{k_i} B k i for all i < j i < j i < j . By (16) , every member of F k j \mathcal{F}_{k_j} F k j lies in V j \mathcal{V}_j V j , and F k j \mathcal{F}_{k_j} F k j shatters B k j B_{k_j} B k j . Hence V j \mathcal{V}_j V j shatters B k j B_{k_j} B k j .
Every finite prefix is realizable. Any member of F k j + 1 \mathcal{F}_{k_{j+1}} F k j + 1 equals σ i \sigma_i σ i on B k i B_{k_i} B k i for all i ≤ j i \le j i ≤ j , by (16) with j + 1 j+1 j + 1 in place of j j j . So the labeled blocks B k 1 , … , B k j B_{k_1}, \ldots, B_{k_j} B k 1 , … , B k j , and hence every prefix of the sequence, are realizable by H \mathcal{H} H .
Both notions are monotone in d d d (dropping one point from every block gives a sequence of width d − 1 d-1 d − 1 ), so the equivalence for every d d d gives uVCE ( H ) = VCE ( H ) \operatorname{uVCE}(\mathcal{H}) = \operatorname{VCE}(\mathcal{H}) uVCE ( H ) = VCE ( H ) , including the cases 0 0 0 and ∞ \infty ∞ . □
The only place where binary labels enter is the pigeonhole step: a block of size d d d has finitely many labelings. The same argument works for any finite label space, with ∣ Y ∣ d |\mathcal{Y}|^d ∣ Y ∣ d in place of 2 d 2^d 2 d , but not for an infinite label space. This is why we state our results with the uncentered notion, which is also the form used in the multiclass setting [11 ] , and which is the form our proofs use directly (Lemma 5.5 and Theorem 5.9).
Remark 3. By Proposition 1, the fine-grained rate uVCE ( H ) λ n \frac{\operatorname{uVCE}(\mathcal{H})}{\lambda n} λn uVCE ( H ) of Theorem 5.3 equals VCE ( H ) λ n \frac{\operatorname{VCE}(\mathcal{H})}{\lambda n} λn VCE ( H ) . The realizable fine-grained rate is VCE ( H ) λ n \frac{\operatorname{VCE}(\mathcal{H})}{\lambda n} λn VCE ( H ) [25 ] . So under the relaxed criterion, the agnostic fine-grained rate is governed by the same dimension as the realizable one, and only an additional factor 1 λ \frac{1}{\lambda} λ 1 is paid.
We next relate uVCE to the size and the VC dimension of the class.
Lemma C.1. For every concept class H \mathcal{H} H :
uVCE ( H ) ≤ VC ( H ) \operatorname{uVCE}(\mathcal{H}) \le\operatorname{VC}(\mathcal{H}) uVCE ( H ) ≤ VC ( H ) ;
uVCE ( H ) = 0 \operatorname{uVCE}(\mathcal{H}) = 0 uVCE ( H ) = 0 if and only if H \mathcal{H} H is finite;
uVCE ( H ) < ∞ \operatorname{uVCE}(\mathcal{H}) < \infty uVCE ( H ) < ∞ if and only if VC ( H ) < ∞ \operatorname{VC}(\mathcal{H}) < \infty VC ( H ) < ∞ .
Proof. 1. The first block of an infinite uncentered d d d -VC-eluder sequence is a VC-shattered set of size d d d .
2, finite classes. Suppose H \mathcal{H} H has an infinite uncentered 1-VC-eluder sequence B 1 , B 2 , … B_1, B_2, \ldots B 1 , B 2 , … with witnesses F k \mathcal{F}_k F k . Since F k \mathcal{F}_k F k shatters B k B_k B k , it contains two concepts f k ≠ g k f_k \ne g_k f k = g k that disagree on B k B_k B k . For k < k ′ k < k' k < k ′ , the concepts f k ′ f_{k'} f k ′ and g k ′ g_{k'} g k ′ agree on B k B_k B k , while f k f_k f k and g k g_k g k do not, so { f k , g k } ≠ { f k ′ , g k ′ } \{f_k, g_k\} \ne\{f_{k'}, g_{k'}\} { f k , g k } = { f k ′ , g k ′ } . Hence H \mathcal{H} H contains infinitely many distinct pairs of concepts, and H \mathcal{H} H is infinite. So a finite class has uVCE ( H ) = 0 \operatorname{uVCE}(\mathcal{H}) = 0 uVCE ( H ) = 0 .
2, infinite classes. We build an infinite uncentered 1-VC-eluder sequence. Let H 0 = H \mathcal{H}_0 = \mathcal{H} H 0 = H . Given an infinite class H r − 1 ⊆ H \mathcal{H}_{r-1} \subseteq\mathcal{H} H r − 1 ⊆ H whose members agree with each other on the points x 1 , … , x r − 1 x_1, \ldots, x_{r-1} x 1 , … , x r − 1 chosen so far, pick two members of H r − 1 \mathcal{H}_{r-1} H r − 1 and a point x r x_r x r where they disagree. Then { x r } \{x_r\} { x r } is VC-shattered by H r − 1 \mathcal{H}_{r-1} H r − 1 , and x r x_r x r is a new point, since all members of H r − 1 \mathcal{H}_{r-1} H r − 1 agree on the earlier points. One of the two classes { h ∈ H r − 1 : h ( x r ) = 0 } \{h \in\mathcal{H}_{r-1} : h(x_r) = 0\} { h ∈ H r − 1 : h ( x r ) = 0 } and { h ∈ H r − 1 : h ( x r ) = 1 } \{h \in\mathcal{H}_{r-1} : h(x_r) = 1\} { h ∈ H r − 1 : h ( x r ) = 1 } is infinite; call it H r \mathcal{H}_r H r . Its members agree on x 1 , … , x r x_1, \ldots, x_r x 1 , … , x r , so we can continue. The singletons { x 1 } , { x 2 } , … \{x_1\}, \{x_2\}, \ldots { x 1 } , { x 2 } , … form an infinite uncentered 1-VC-eluder sequence.
If VC ( H ) < ∞ \operatorname{VC}(\mathcal{H}) < \infty VC ( H ) < ∞ , then uVCE ( H ) < ∞ \operatorname{uVCE}(\mathcal{H}) < \infty uVCE ( H ) < ∞ by item 1. Conversely, suppose VC ( H ) = ∞ \operatorname{VC}(\mathcal{H}) = \infty VC ( H ) = ∞ and fix d ≥ 1 d \ge1 d ≥ 1 ; we build an infinite uncentered d d d -VC-eluder sequence. The argument is the same as for item 2, with “infinite VC dimension” in place of “infinite”. Let H 0 = H \mathcal{H}_0 = \mathcal{H} H 0 = H . Given H r − 1 ⊆ H \mathcal{H}_{r-1} \subseteq\mathcal{H} H r − 1 ⊆ H with VC ( H r − 1 ) = ∞ \operatorname{VC}(\mathcal{H}_{r-1}) = \infty VC ( H r − 1 ) = ∞ whose members agree with each other on B 1 ∪ ⋯ ∪ B r − 1 B_1 \cup\cdots\cup B_{r-1} B 1 ∪ ⋯ ∪ B r − 1 , pick a set B r B_r B r of size d d d that is VC-shattered by H r − 1 \mathcal{H}_{r-1} H r − 1 . It is disjoint from the earlier blocks, since all members of H r − 1 \mathcal{H}_{r-1} H r − 1 agree there. Split H r − 1 \mathcal{H}_{r-1} H r − 1 into the 2 d 2^d 2 d classes of concepts with a given labeling of B r B_r B r . Since the VC dimension of a union of two classes is at most the sum of their VC dimensions plus one, a finite union of classes of finite VC dimension has finite VC dimension. So one of these 2 d 2^d 2 d classes has infinite VC dimension; call it H r \mathcal{H}_r H r . Its members agree on B 1 ∪ ⋯ ∪ B r B_1 \cup\cdots\cup B_r B 1 ∪ ⋯ ∪ B r , so we can continue. Hence uVCE ( H ) ≥ d \operatorname{uVCE}(\mathcal{H}) \ge d uVCE ( H ) ≥ d for every d d d , i.e., uVCE ( H ) = ∞ \operatorname{uVCE}(\mathcal{H}) = \infty uVCE ( H ) = ∞ .
By Proposition 1, items 2 and 3 are also consequences of the corresponding facts for VCE [Hanneke and Xu, 2024]; we include the short proofs to keep the paper self-contained.
Finally, uVCE ( H ) \operatorname{uVCE}(\mathcal{H}) uVCE ( H ) can be much smaller than VC ( H ) \operatorname{VC}(\mathcal{H}) VC ( H ) , which is where the relaxed criterion gains over the standard one.
Example C.2. Let M ≥ 2 M \ge2 M ≥ 2 , let X = { z 1 , … , z M } ∪ N \mathcal{X} = \{z_1, \ldots, z_M\} \cup\mathbb{N} X = { z 1 , … , z M } ∪ N , and let H \mathcal{H} H consist of
all labelings of z 1 , … , z M z_1, \ldots, z_M z 1 , … , z M that are 0 on N \mathbb{N} N , and
The set { z 1 , … , z M } \{z_1, \ldots, z_M\} { z 1 , … , z M } is VC-shattered. No set that contains a point of N \mathbb{N} N together with another point is VC-shattered, since no concept labels both points 1. Hence VC ( H ) = M \operatorname{VC}(\mathcal{H}) = M VC ( H ) = M . The class is infinite, so uVCE ( H ) ≥ 1 \operatorname{uVCE}(\mathcal{H}) \ge1 uVCE ( H ) ≥ 1 by Lemma C.1 . In an infinite uncentered 2-VC-eluder sequence, every block would be a shattered pair, hence a subset of { z 1 , … , z M } \{z_1, \ldots, z_M\} { z 1 , … , z M } , and the blocks are pairwise disjoint, so there are at most M / 2 M/2 M /2 of them. Hence uVCE ( H ) = 1 \operatorname{uVCE}(\mathcal{H}) = 1 uVCE ( H ) = 1 . For this class, the standard agnostic fine-grained rate is M / n \sqrt{M/n} M / n (Theorem 4.1 ), while the relaxed one is 1 λ n \frac{1}{\lambda n} λn 1 (Theorem 5.3 ), whatever M M M is. The finite part of the class only affects the marginal-dependent lower-order term.