Introduction
The seminal works of Vapnik and Chervonenkis [ [52 ] , Valiant [ [51 ] laid the foundations of modern statistical learning theory by introducing the probably approximately correct (PAC) learning framework , a fundamental theoretical criterion for supervised learning that has been the focus of extensive research over the past several decades.
In this framework, there is an unknown data distribution D \mathcal{D} D over X × Y \mathcal{X} \times\mathcal{Y} X × Y , where X \mathcal{X} X is an instance space and Y \mathcal{Y} Y is a binary label space. 1 For example, X \mathcal{X} X may be a space of medical images, and Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } may be the binary label space, where y = 1 y = 1 y = 1 indicates that the corresponding image shows a certain abnormality and y = 0 y = 0 y = 0 indicates that it does not. In addition, this framework fixes a concept class C C C , consisting of functions from the instance space X \mathcal{X} X to the label space Y \mathcal{Y} Y , which serves as a benchmark family of classifiers. For instance, C C C may be the class of neural networks with a prescribed architecture. Moreover, given a set of i.i.d. training examples drawn from D \mathcal{D} D , the learner’s goal is to output a hypothesis h ^ : X → Y \hat{h} : \mathcal{X} \to\mathcal{Y} h ^ : X → Y whose classification error on future examples also drawn from D \mathcal{D} D is, with high probability, close to that of the best concept in C \mathcal{C} C .
The statistical and computational learning theory communities have studied several assumptions on the relationship between instances and labels, especially within the PAC learning framework. In the realizable setting, it is assumed that the labels are generated by a fixed concept c ⋆ ∈ C c^{\star} \in\mathcal{C} c ⋆ ∈ C . In the agnostic setting, in contrast, no such assumption is imposed: the joint distribution over instances and labels may be arbitrary. Between these two regimes lie noise models , such as Tsybakov noise Mammen and Tsybakov [ [38 ] , Tsybakov [ [49 ] and Massart noise Massart and Nédélec [ [39 ] , which assume that the labeling rule belongs to C \mathcal{C} C but allow stochastic label noise of restricted severity. Another natural intermediate assumption is that the Bayes-optimal classifier belongs to C \mathcal{C} C . This retains the assumption that the optimal decision rule is contained in the benchmark class but relaxes the control over the label noise.
In this work, we assume that the labels are deterministic . That is, there exists a fixed function f ⋆ : X → Y f^{\star} : \mathcal{X} \to\mathcal{Y} f ⋆ : X → Y specifying the label of each instance; however, f ⋆ f^{\star} f ⋆ need not belong to the concept class C \mathcal{C} C . This model was introduced and systematically studied in the pioneering work of Ben-David and Urner [ [7 ] . A similar assumption has also been investigated in other statistical learning frameworks Ben-David and Ben-David [ [9 ] , Urner and Ben-David [ [50 ] , Bousquet and Zhivotovskiy [ [14 ] . Moreover, this formulation also studied in the literature on computational learning theory, particularly in the agnostic learning of Boolean concept classes; see, for example, Kearns et al. [ [35 ] , Feldman et al. [ [25 ] . Finally, it is closely related to the comparative PAC learning framework, introduced by Hu and Peale [ [34 ] and subsequently developed in Ashkezari and Urner [ [4 ] , in which the target labeling function f ⋆ f^{\star} f ⋆ is restricted to belong to a fixed class H \mathcal{H} H .
This assumption is motivated by modern high-dimensional learning tasks, in which instances often contain sufficient information to determine the correct label. For example, in medical imaging, a sufficiently detailed scan, together with relevant patient information, may determine whether a specific abnormality is present. However, the resulting labeling rule can be highly complex and does not need to belong to the chosen concept class C \mathcal{C} C . Thus, this assumption allows the task to have a well-defined ground truth while still permitting model misspecification.
This leads to the following fundamental and natural question:
Given a concept class C ⊆ { 0 , 1 } X \mathcal{C} \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X , how many training samples are necessary and sufficient for agnostically PAC learning C \mathcal{C} C under deterministic labels?
The work of Ben-David and Urner [ [7 ] made significant progress on the above question. In particular, they proved that if the diameter of a concept class C \mathcal{C} C , denoted by D ( C ) \mathrm{D}(\mathcal{C}) D ( C ) , is infinite, then the optimal sample complexity of agnostically PAC learning C \mathcal{C} C under deterministic labels admits a lower bound of Ω ( log ( 1 / δ ) / ε 2 ) \Omega\left(\log(1/\delta)/\varepsilon^{2}\right) Ω ( log ( 1/ δ ) / ε 2 ) . Moreover, they showed that, for every d ∈ N d \in\mathbb{N} d ∈ N , there exists a concept class C \mathcal{C} C whose Vapnik–Chervonenkis dimension, denoted by V C ( C ) \mathrm{VC}(\mathcal{C}) VC ( C ) , equals d d d , for which the optimal sample complexity of agnostic PAC learning under deterministic labels is lower bounded by Ω ( d / ε 2 + log ( 1 / δ ) / ε 2 ) \Omega\left(d/\varepsilon^{2}+\log(1/\delta)/\varepsilon^{2}\right) Ω ( d / ε 2 + log ( 1/ δ ) / ε 2 ) . Indeed, this lower bound matches, up to constant factors, the upper bound for the fully agnostic setting achieved by empirical risk minimizers (ERMs) proved via the chaining technique Talagrand [ [48 ] . Thus, the infinite-diameter regime already exhibits essentially classical agnostic behavior, leaving limited room for improvement from the deterministic label assumption. In contrast, when D ( C ) \mathrm{D}(\mathcal{C}) D ( C ) is finite, they proved an upper bound of O ~ ( D ( C ) / ε ) \widetilde{O}(\mathrm{D}(\mathcal{C})/\varepsilon) O ( D ( C ) / ε ) , while the only known lower bound is the standard realizable PAC learning lower bound Ehrenfeucht et al. [ [22 ] , namely Ω ( V C ( C ) / ε + log ( 1 / δ ) / ε ) \Omega\left(\mathrm{VC}(\mathcal{C})/\varepsilon+\log(1/\delta)/\varepsilon\right) Ω ( VC ( C ) / ε + log ( 1/ δ ) / ε ) for non-trivial concept classes C \mathcal{C} C . Therefore, closing the gap between the upper and lower bounds in the finite-diameter regime remains open.
Overview of the Main Results
In the present work, our main contribution is to improve both the upper and lower bounds in the finite-diameter regime. Formally, we establish the following theorem.
Theorem 1.1. Let C ⊆ { 0 , 1 } X \mathcal{C} \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X be a non-degenerate concept class with d : = VC ( C ) < ∞ d := \operatorname{VC}(\mathcal{C}) < \infty d := VC ( C ) < ∞ and K : = D ( C ) < ∞ K := \operatorname{D}(\mathcal{C}) < \infty K := D ( C ) < ∞ . Then, the following holds.
m C ( ε , δ ) ∈ Ω ( K 1 / 3 ( log ( 1 / δ ) ∧ K ) 2 / 3 + d + log ( 1 / δ ) ε ) , m_{\mathcal{C}}(\varepsilon,\delta) \in\Omega\left(\frac{K^{1/3}\left(\log(1/\delta) \wedge K\right)^{2/3}+d+\log(1/\delta)}{\varepsilon}\right), m C ( ε , δ ) ∈ Ω ( ε K 1/3 ( log ( 1/ δ ) ∧ K ) 2/3 + d + log ( 1/ δ ) ) , m C ( ε , δ ) ∈ O ~ ( K 1 / 3 d 2 / 3 + K 1 / 3 ( log ( 1 / δ ) ∧ K ) 2 / 3 + log ( 1 / δ ) ε ) . m_{\mathcal{C}}(\varepsilon,\delta) \in\widetilde{O}\left(\frac{K^{1/3}d^{2/3}+K^{1/3}\left(\log(1/\delta) \wedge K\right)^{2/3}+\log(1/\delta)}{\varepsilon}\right). m C ( ε , δ ) ∈ O ( ε K 1/3 d 2/3 + K 1/3 ( log ( 1/ δ ) ∧ K ) 2/3 + log ( 1/ δ ) ) . Moreover, for some finite K 0 K_0 K 0 , for every d ∈ N d \in\mathbb{N} d ∈ N and every K ≥ max { K 0 , d } K \geq\max\{K_0,d\} K ≥ max { K 0 , d } , there exists a concept class C ⊆ { 0 , 1 } X \mathcal{C} \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X with VC ( C ) = d \operatorname{VC}(\mathcal{C}) = d VC ( C ) = d and K = D ( C ) K = \operatorname{D}(\mathcal{C}) K = D ( C ) for which the above upper bound is tight. Namely:
m C ( ε , δ ) ∈ Ω ( K 1 / 3 d 2 / 3 + K 1 / 3 ( log ( 1 / δ ) ∧ K ) 2 / 3 + log ( 1 / δ ) ε ) . m_{\mathcal{C}}(\varepsilon,\delta) \in\Omega\left(\frac{K^{1/3}d^{2/3}+K^{1/3}\left(\log(1/\delta) \wedge K\right)^{2/3}+\log(1/\delta)}{\varepsilon}\right). m C ( ε , δ ) ∈ Ω ( ε K 1/3 d 2/3 + K 1/3 ( log ( 1/ δ ) ∧ K ) 2/3 + log ( 1/ δ ) ) . Here, m C m_{\mathcal{C}} m C denotes the optimal sample complexity of agnostically PAC learning C \mathcal{C} C under deterministic labels; see Definition 2.2 for the formal definition. In addition, we use O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) to hide poly-logarithmic factors. Also, for any a , b ∈ R a,b \in\mathbb{R} a , b ∈ R , we use the notation a ∧ b : = min { a , b } a \wedge b := \min\{a,b\} a ∧ b := min { a , b } .
Technical overview of the upper bound. Our upper bound is obtained by a learning algorithm that combines an empirical risk minimizer with memorization . This contrasts with the algorithm of Ben-David and Urner [ [7 ] , which is purely based on memorization. Furthermore, our analysis of this algorithm departs significantly from known analyses of PAC learning algorithms and may be of independent interest. In particular, we begin by studying the special case in which the concept class consists of only two functions ; a key ingredient in this analysis is the concentration inequalities for the missing mass of discrete distributions McAllester and Ortiz [ [40 ] , Berend and Kontorovich [ [10 ] . We then extend the argument to finite concept classes by drawing on ideas from density estimation Devroye and Lugosi [ [21 ] . Finally, we pass to general VC classes by constructing a suitable finite cover using a technique similar to Hopkins et al. [ [33 ] . For additional details, see § 3 and Appendix § 7 .
Technical overview of the lower bound. The lower bound is technically more involved. The reason is that we must go beyond the standard realizable PAC learning lower bound; however, under deterministic labels, memorization eliminates uncertainty on every sampled point , so the hardness must lie in the unsampled part of the support. We place a small total mass uniformly across a large set of points and assign their deterministic labels according to slightly biased coins, with the direction of the bias chosen uniformly at random. In this way, the best concept in the class, which is either all ones or all zeros on these points, has a small advantage in this rare region. We show that, below the stated sample size, detecting the direction of this advantage is information-theoretically impossible. On the other hand, any learner achieving a small excess error would yield a successful tester by taking a majority vote over its predictions on the unseen rare points, giving the desired contradiction. Finally, an application of the probabilistic method fixes one deterministic labeling for which the learner fails with the required probability. For additional details, including a more detailed technical overview, see Appendix § 8 .
This technical use of memorization in our results is connected to a central phenomenon in machine learning: training-data memorization is pervasive. This is explicit in classical methods such as nearest-neighbor classifiers, whose hypotheses essentially store the training examples, and in support vector machines, whose predictors depend on selected training points. It also arises in ensemble methods such as AdaBoost and random forests, which can fit the training data perfectly while achieving strong generalization performance Wyner et al. [ [53 ] . In modern overparameterized models, memorization is even more pronounced: deep networks can fit the training data with near-perfect accuracy, even when the labels are completely random Zhang et al. [ [54 ] . More recently, memorization has also been empirically demonstrated in large language models and diffusion models, where portions of the training data can sometimes be extracted from the trained model Carlini et al. [ [18 , 19 ] , Nasr et al. [ [42 ] .
The above phenomena are somewhat counterintuitive from the classical point of view, where learning is often associated with extracting generalizable patterns rather than retaining individual training examples Bishop and Nasrabadi [ [11 ] . Yet, the prevalence of memorization suggests that it is not simply opposed to generalization, but rather is probably a fundamental aspect of learning whose role is still not fully understood theoretically. In this direction, a recent line of work has made significant progress in identifying setups where memorization is necessary for accurate learning by focusing primarily on long-tailed or otherwise structured distributional settings [24 ] , [24 ] , [17 ] , [26 ] . In contrast, our results shed light on this phenomenon from a complementary, distribution-free perspective by characterizing the optimal sample complexity of agnostic PAC learning under deterministic labels. Relatedly, a use of memorization also appears in the literature on optimistically universal learning; see, for instance, [12 ] and the references therein. Nevertheless, this line of work studies the universal learning framework, whereas the present work focuses on uniform guarantees .
Our next contribution concerns online binary classification within the Littlestone framework [37 ] . In particular, we consider the problem of agnostic online learning under deterministic labels. Interestingly, the diameter plays an important role here as well. Formally, we establish the following theorem.
Theorem 1.2. Let C ⊆ { 0 , 1 } X C \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X be a concept class with K : = D ( C ) < ∞ K := D(C) < \infty K := D ( C ) < ∞ . Then, we have:
R ⋆ ( C , T ) ∈ O ( K ) . R^{\star}(C,T) \in O(K). R ⋆ ( C , T ) ∈ O ( K ) . Moreover, for every K ∈ N K \in\mathbb{N} K ∈ N , there exists a concept class C ⊆ { 0 , 1 } X C \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X with D ( C ) = K D(C) = K D ( C ) = K and LD ( C ) = 1 \operatorname{LD}(C) = 1 LD ( C ) = 1 for which we have:
R ⋆ ( C , T ) ∈ Ω ( K ) . R^{\star}(C,T) \in\Omega(K). R ⋆ ( C , T ) ∈ Ω ( K ) . Here, R ⋆ ( C , T ) R^{\star}(C,T) R ⋆ ( C , T ) denotes the minimax expected regret as a function of the concept class C C C and the time horizon T T T , and LD ( C ) \operatorname{LD}(C) LD ( C ) denotes the Littlestone dimension of C C C ; see subsection E.1 for formal definitions.
Notably, as in our PAC learning algorithm, memorization is also a key ingredient in the online learning algorithm that obtains the above upper bound. For additional details and further results, see Appendix § 11 .
As mentioned earlier, Ben-David and Urner [ [7 ] provided a lower bound on the optimal sample complexity of agnostic PAC learning with deterministic labels in the finite-diameter regime. As our final contribution, we express their result in terms of a combinatorial complexity parameter that we denote by SET-VC (see Definition 2.7 ). We then complement this lower bound by introducing a larger combinatorial complexity parameter, denoted by PERT-VC (see Definition 2.8 ), which controls the leading 1 / ε 2 1/\varepsilon^2 1/ ε 2 -term in our upper bound in the infinite-diameter regime.
Theorem 1.3. Let C ⊆ { 0 , 1 } X C \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X be a concept class such that SET-VC ( C ) ≤ PERT-VC ( C ) < ∞ \operatorname{SET\text{-}VC}(C) \leq\operatorname{PERT\text{-}VC}(C) < \infty SET - VC ( C ) ≤ PERT - VC ( C ) < ∞ . Then, there exists a constant k ⋆ ∈ N ∪ { 0 } k^{\star} \in\mathbb{N} \cup\{0\} k ⋆ ∈ N ∪ { 0 } , possibly depending on C C C , for which the following holds.
m C ( ε , δ ) = O ~ ( PERT-VC ( C ) ε 2 + k ⋆ ε ) . m_C(\varepsilon,\delta) = \widetilde{O}\left(\frac{\operatorname{PERT\text{-}VC}(C)}{\varepsilon^2} + \frac{k^{\star}}{\varepsilon}\right). m C ( ε , δ ) = O ( ε 2 PERT - VC ( C ) + ε k ⋆ ) . Moreover, the lower bound of Ben-David and Urner [ [7 ] implies
m C ( ε , δ ) = Ω ~ ( SET-VC ( C ) ε 2 ) . m_C(\varepsilon,\delta) = \widetilde{\Omega}\left(\frac{\operatorname{SET\text{-}VC}(C)}{\varepsilon^2}\right). m C ( ε , δ ) = Ω ( ε 2 SET - VC ( C ) ) .
We then raise the natural open question of whether the above lower and upper bounds match, in small ε \varepsilon ε regime. Formally, we have the following open question.
Open Question 1.4. Is there a concept class C C C such that SET-VC ( C ) ≠ PERT-VC ( C ) \operatorname{SET\text{-}VC}(C) \ne\operatorname{PERT\text{-}VC}(C) SET - VC ( C ) = PERT - VC ( C ) ?
For additional details and results, we refer to Appendix § 9 and to the concluding discussion there.
Organization
The remainder of the paper is organized as follows. In § 2 , we introduce the formal notation and definitions used throughout the paper. Then, as a warm-up, in § 3 , we prove our upper bounds for concept classes with two concepts. Finally, § 4 concludes the main body.
In the appendix, Appendix § 6 gives a more extensive discussion of related work. In Appendix § 7 and Appendix § 8 , we give our remaining PAC learning upper and lower bounds, respectively, for the finite-diameter regime. Then, in Appendix § 9 , we present our results for the infinite-diameter regime. Eventually, in Appendix § 10 and Appendix § 11 , we give the definitions and the results for online learning.
Notation and Definitions
In this section, we first set our basic notation in subsection 2.1. We then define the PAC learning framework in subsection 2.2. Finally, we give the definitions of the main combinatorial complexity parameters considered in this work in subsection 2.3.
Notation
In this subsection, we present the basic notations used throughout the paper, most of which are standard in the community. Let N \mathbb{N} N and R \mathbb{R} R stand for the set of natural numbers and real numbers, respectively. In addition, for a given n ∈ N n \in\mathbb{N} n ∈ N , we use [ n ] [n] [ n ] to denote { 1 , 2 , … , n } \{1, 2, \ldots, n\} { 1 , 2 , … , n } . For any a , b ∈ R a,b \in\mathbb{R} a , b ∈ R , we use the notation a ∧ b : = min { a , b } a \wedge b := \min\{a,b\} a ∧ b := min { a , b } . Also, for a , b ∈ N a,b \in\mathbb{N} a , b ∈ N , we write a ∣ b a \mid b a ∣ b if a a a divides b b b , that is, if there exists m ∈ N m \in\mathbb{N} m ∈ N such that b = a m b = am b = am . Next, given n ∈ N n \in\mathbb{N} n ∈ N , for any sequence of size n n n or n n n -tuple v v v , and any i ∈ [ n ] i \in[n] i ∈ [ n ] , let us use v i v_i v i to denote the i i i -th element in v v v . Afterward, we denote by A × B A \times B A × B the Cartesian product of two arbitrary sets A A A and B B B . In addition, for any set A A A and any n ∈ N n \in\mathbb{N} n ∈ N , we let A n A^n A n indicate n n n times the Cartesian product of A A A with itself. Note that for any set A A A , we define A 0 : = { ∅ } A^0 := \{\emptyset\} A 0 := { ∅ } . Also, given a set A A A , we denote by A ∗ A^* A ∗ the set of all finite sequences of members of A A A ; more formally, A ∗ : = ⋃ T = 0 ∞ A T A^* := \bigcup_{T=0}^{\infty} A^T A ∗ := ⋃ T = 0 ∞ A T . Then, for arbitrary sets X X X and Y Y Y , we use Y X Y^X Y X to denote the space of all functions from X X X to Y Y Y . Going further, let e e e and log ( ⋅ ) \log(\cdot) log ( ⋅ ) stand for Euler’s number and the Logarithm function in the base 2, respectively. Finally, we use O ( ⋅ ) O(\cdot) O ( ⋅ ) , Ω ( ⋅ ) \Omega(\cdot) Ω ( ⋅ ) , and Θ ( ⋅ ) \Theta(\cdot) Θ ( ⋅ ) to denote the standard asymptotic notation in theoretical computer science. Furthermore, we use O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) , Ω ~ ( ⋅ ) \widetilde{\Omega}(\cdot) Ω ( ⋅ ) , and Θ ~ ( ⋅ ) \widetilde{\Theta}(\cdot) Θ ( ⋅ ) to hide poly-logarithmic factors.
PAC Learning Framework
We begin by giving the problem setup. Fix a non-empty measurable space ( X , Σ X ) (\mathcal{X}, \Sigma_{\mathcal{X}}) ( X , Σ X ) , referred to as the instance space. For example, the instance space X \mathcal{X} X can be a Euclidean space. In addition, fix Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } as the label space. A concept is a measurable function from X \mathcal{X} X to Y \mathcal{Y} Y . With this in mind, fix a non-empty collection of such functions C \mathcal{C} C as the concept class. For simplicity, we specify instances of the PAC learning framework solely based on the concept class C \mathcal{C} C , which is defined relative to the measurable structure ( X , Σ X ) (\mathcal{X}, \Sigma_{\mathcal{X}}) ( X , Σ X ) .
Additionally, we say that a concept class C ⊆ Y X \mathcal{C} \subseteq\mathcal{Y}^{\mathcal{X}} C ⊆ Y X is non-degenerate if there exist two concepts h 0 , h 1 ∈ C h^0,h^1 \in\mathcal{C} h 0 , h 1 ∈ C and distinct points x 0 , x 1 , … , x k 0 ∈ X x_0,x_1,\ldots,x_{k_0} \in\mathcal{X} x 0 , x 1 , … , x k 0 ∈ X such that h 0 ( x 0 ) = h 1 ( x 0 ) h^0(x_0)=h^1(x_0) h 0 ( x 0 ) = h 1 ( x 0 ) , and h 0 ( x i ) ≠ h 1 ( x i ) h^0(x_i) \ne h^1(x_i) h 0 ( x i ) = h 1 ( x i ) for every i ∈ [ k 0 ] i \in[k_0] i ∈ [ k 0 ] , where k 0 ∈ N k_0 \in\mathbb{N} k 0 ∈ N is constant that appears in subsection C.3.
Next, we present the definition of a data distribution. A data distribution D \mathcal{D} D is a probability measure over X × Y \mathcal{X} \times\mathcal{Y} X × Y . For example, it may be a probability measure over the space of words in a dictionary and their corresponding binary labels.
Subsequently, we present the definition of a learning algorithm. A PAC learning algorithm A \mathbb{A} A is a mapping from ( X × Y ) ∗ × X (\mathcal{X} \times\mathcal{Y})^* \times\mathcal{X} ( X × Y ) ∗ × X to Y \mathcal{Y} Y whose restriction to ( X × Y ) n × X (\mathcal{X} \times\mathcal{Y})^n \times\mathcal{X} ( X × Y ) n × X is universally measurable for every n ∈ N ∪ { 0 } n \in\mathbb{N} \cup\{0\} n ∈ N ∪ { 0 } . In words, a PAC learning algorithm is a function that maps a finite sequence of examples, and an instance, to a label.
Given a PAC learning algorithm A \mathbb{A} A , for every dataset S ∈ ( X × Y ) n S \in(\mathcal{X} \times\mathcal{Y})^n S ∈ ( X × Y ) n , where n ∈ N ∪ { 0 } n \in\mathbb{N} \cup\{0\} n ∈ N ∪ { 0 } , define A S : X → Y \mathbb{A}_S : \mathcal{X} \to\mathcal{Y} A S : X → Y by
A S ( x ) : = A ( ( S , x ) ) for all x ∈ X . \mathbb{A}_S(x) := \mathbb{A}((S,x)) \qquad\text{for all } x \in\mathcal{X}. A S ( x ) := A (( S , x )) for all x ∈ X .
We note that for simplicity, the present work restricts attention to deterministic PAC learning algorithms. Nevertheless, our lower bounds continue to hold, up to constant factors, even when randomized PAC learning algorithms are allowed.
Afterward, we introduce three definitions: the first concerns the true error of a concept, the second concerns the empirical error of a concept, and the last concerns the error of a PAC learning algorithm.
We define the true error of a concept h h h with respect to a data distribution D \mathcal{D} D , denoted by L D ( h ) \mathcal{L}_{\mathcal{D}}(h) L D ( h ) , as follows:
L D ( h ) : = P ( x , y ) ∼ D [ h ( x ) ≠ y ] . \mathcal{L}_{\mathcal{D}}(h) := \mathbb{P}_{(x,y)\sim\mathcal{D}}[h(x) \ne y]. L D ( h ) := P ( x , y ) ∼ D [ h ( x ) = y ] .
Also, given S : = { ( x 1 , y 1 ) , ( x 2 , y 2 ) … , ( x n , y n ) } ∈ ( X × Y ) n S := \{(x_1,y_1),(x_2,y_2)\ldots,(x_n,y_n)\} \in(\mathcal{X} \times\mathcal{Y})^n S := {( x 1 , y 1 ) , ( x 2 , y 2 ) … , ( x n , y n )} ∈ ( X × Y ) n for some n ∈ N ∪ { 0 } n \in\mathbb{N} \cup\{0\} n ∈ N ∪ { 0 } , we define empirical error of a concept h h h with respect to S S S , denote by L S ( h ) \mathcal{L}_S(h) L S ( h ) , as follows:
L S ( h ) : = 1 n ∑ ( x , y ) ∈ S [ h ( x ) ≠ y ] . \mathcal{L}_S(h) := \frac{1}{n}\sum_{(x,y)\in S}[h(x)\ne y]. L S ( h ) := n 1 ( x , y ) ∈ S ∑ [ h ( x ) = y ] .
Let A be a PAC learning algorithm. Given S S S as above, we define the error of A S A_S A S with respect to a data distribution D \mathcal{D} D , denoted by L D ( A S ) \mathcal{L}_{\mathcal{D}}(A_S) L D ( A S ) , as follows:
L D ( A S ) : = P ( x , y ) ∼ D [ A S ( x ) ≠ y ] . \mathcal{L}_{\mathcal{D}}(A_S) := \mathbb{P}_{(x,y)\sim\mathcal{D}}[A_S(x)\ne y]. L D ( A S ) := P ( x , y ) ∼ D [ A S ( x ) = y ] .
In this work, we restrict attention to deterministically labeled distributions. Formally, we have the following definition.
Definition 2.1 (Deterministically labeled distribution). A data distribution D \mathcal{D} D is said to be deterministically labeled if there exists a concept f ∗ : X → Y f^*:\mathcal{X}\to\mathcal{Y} f ∗ : X → Y such that
L D ( f ∗ ) = 0. \mathcal{L}_{\mathcal{D}}(f^*)=0. L D ( f ∗ ) = 0.
Building on the previous definitions, we now define agnostic PAC learnability with deterministic labels. This definition is based on the same principles as those introduced by Valiant [ [51 ] , Vapnik and Chervonenkis [ [52 ] .
Definition 2.2 (Agnostic PAC learnability with deterministic labels). We say that a concept class C \mathcal{C} C is agnostic PAC learnable with deterministic labels, if there exist a PAC learning algorithm A and a sample complexity function m C A : ( 0 , 1 ) × ( 0 , 1 ) → N m^\mathcal{A}_{\mathcal{C}}:(0,1)\times(0,1)\to\mathbb{N} m C A : ( 0 , 1 ) × ( 0 , 1 ) → N such that, for every deterministically labeled distribution D \mathcal{D} D , every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , for n ≥ m C A ( ε , δ ) n\ge m^\mathcal{A}_{\mathcal{C}}(\varepsilon,\delta) n ≥ m C A ( ε , δ ) , we have:
P S ∼ D n [ L D ( A S ) ≤ inf h ∈ C L D ( h ) + ε ] ≥ 1 − δ . \mathbb{P}_{S\sim\mathcal{D}^n}\left[\mathcal{L}_{\mathcal{D}}(A_S)\le\inf_{h\in\mathcal{C}}\mathcal{L}_{\mathcal{D}}(h)+\varepsilon\right]\ge1-\delta. P S ∼ D n [ L D ( A S ) ≤ h ∈ C inf L D ( h ) + ε ] ≥ 1 − δ .
Now, let A be a PAC learning algorithm. We define the sample complexity of A as the function m C A : ( 0 , 1 ) × ( 0 , 1 ) → N m^\mathcal{A}_{\mathcal{C}}:(0,1)\times(0,1)\to\mathbb{N} m C A : ( 0 , 1 ) × ( 0 , 1 ) → N such that, for every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , the value m C A ( ε , δ ) m^\mathcal{A}_{\mathcal{C}}(\varepsilon,\delta) m C A ( ε , δ ) is the pointwise infimum over all functions satisfying the above guarantee for A .
Finally, the optimal sample complexity of agnostic PAC learning C \mathcal{C} C with deterministic labels, denoted by m C : ( 0 , 1 ) × ( 0 , 1 ) → N m_{\mathcal{C}}:(0,1)\times(0,1)\to\mathbb{N} m C : ( 0 , 1 ) × ( 0 , 1 ) → N , is then defined as follows:
m C ( ε , δ ) : = inf A m C A ( ε , δ ) for all ε , δ ∈ ( 0 , 1 ) . m_{\mathcal{C}}(\varepsilon,\delta):=\inf_{\mathcal{A}}m^\mathcal{A}_{\mathcal{C}}(\varepsilon,\delta)\qquad\text{for all }\varepsilon,\delta\in(0,1). m C ( ε , δ ) := A inf m C A ( ε , δ ) for all ε , δ ∈ ( 0 , 1 ) .
that is, given ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , the minimal number of samples sufficient for the existence of some PAC learning algorithm that satisfies the above guarantee.
Combinatorial Complexity Parameters
In this subsection, we introduce the combinatorial complexity parameters appearing in our PAC learning results. We begin with the standard notions of shattering, VC dimension, and diameter. We then define two additional parameters, SET-VC and PERT-VC, which are used in our analysis of the infinite-diameter regime.
Definition 2.3 (Shattered set). Let C ⊆ Y X \mathcal{C}\subseteq\mathcal{Y}^{\mathcal{X}} C ⊆ Y X be a concept class, and let S ⊆ X S\subseteq\mathcal{X} S ⊆ X be a finite set of instances. We say that S S S is shattered by C \mathcal{C} C if for every f : S → { 0 , 1 } f:S\to\{0,1\} f : S → { 0 , 1 } , there exists a concept c ∈ C c\in\mathcal{C} c ∈ C such that c ( x ) = f ( x ) c(x)=f(x) c ( x ) = f ( x ) for all x ∈ S x\in S x ∈ S .
Definition 2.4 (VC dimension). Let C ⊆ Y X \mathcal{C}\subseteq\mathcal{Y}^{\mathcal{X}} C ⊆ Y X be a concept class. The VC dimension of C \mathcal{C} C , denoted by VC ( C ) ∈ N ∪ { 0 , + ∞ } \operatorname{VC}(\mathcal{C})\in\mathbb{N}\cup\{0,+\infty\} VC ( C ) ∈ N ∪ { 0 , + ∞ } , is defined by the supremum sup d ∈ N ∪ { 0 } \sup_{d\in\mathbb{N}\cup\{0\}} sup d ∈ N ∪ { 0 } , such that, there exists a finite set of instances S ⊆ X S\subseteq\mathcal{X} S ⊆ X of size d d d that is shattered by C \mathcal{C} C . Also, if C = ∅ \mathcal{C}=\varnothing C = ∅ , we have: VC ( C ) = 0 \operatorname{VC}(\mathcal{C})=0 VC ( C ) = 0 .
Definition 2.5 (Diameter, following Ben-David and Urner [ [7 ] ). Let C ⊆ Y X \mathcal{C}\subseteq\mathcal{Y}^{\mathcal{X}} C ⊆ Y X be a concept class. The diameter of C \mathcal{C} C , denoted by D ( C ) ∈ N ∪ { 0 , + ∞ } \operatorname{D}(\mathcal{C})\in\mathbb{N}\cup\{0,+\infty\} D ( C ) ∈ N ∪ { 0 , + ∞ } , is defined by
D ( C ) : = sup h , h ′ ∈ C ∣ h △ h ′ ∣ , h △ h ′ : = { x ∈ X ∣ h ( x ) ≠ h ′ ( x ) } . \operatorname{D}(\mathcal{C}):=\sup_{h,h'\in\mathcal{C}}|h\triangle h'|,\qquad h\triangle h':=\{x\in\mathcal{X}\mid h(x)\ne h'(x)\}. D ( C ) := h , h ′ ∈ C sup ∣ h △ h ′ ∣ , h △ h ′ := { x ∈ X ∣ h ( x ) = h ′ ( x )} . Also, if ∣ C ∣ ≤ 1 |\mathcal{C}|\le1 ∣ C ∣ ≤ 1 , we have: D ( C ) = 0 \operatorname{D}(\mathcal{C})=0 D ( C ) = 0 .
The combinatorial parameter SET-VC defined in Definition 2.7 is adapted from the set-shattering notion of Ben-David and Urner [ [7 ] . This notion was used in Ben-David and Urner [ [7 ] to obtain lower bounds for agnostic PAC learning with deterministic labels in the infinite-diameter regime.
Definition 2.6 (Ben-David and Urner [ [7 ] ). Let C \mathcal{C} C be a concept class over a domain X \mathcal{X} X , and let A 1 , … , A d ⊆ X A_1,\ldots,A_d \subseteq\mathcal{X} A 1 , … , A d ⊆ X . We say that C \mathcal{C} C set-shatters A 1 , … , A d A_1,\ldots,A_d A 1 , … , A d if, for every binary vector σ = ( σ 1 , … , σ d ) ∈ { 0 , 1 } d \sigma=(\sigma_1,\ldots,\sigma_d)\in\{0,1\}^d σ = ( σ 1 , … , σ d ) ∈ { 0 , 1 } d , there exists some h σ ∈ C h_\sigma\in\mathcal{C} h σ ∈ C such that, for every i ≤ d i\le d i ≤ d and every x ∈ A i x\in A_i x ∈ A i , h σ ( x ) = σ i h_\sigma(x)=\sigma_i h σ ( x ) = σ i .
Definition 2.7. For any concept class C \mathcal{C} C over domain X \mathcal{X} X , define set VC dimension of C \mathcal{C} C denoted by SET-VC( C ) (\mathcal{C}) ( C ) as the largest d ∈ N ∪ { 0 } d\in\mathbb{N}\cup\{0\} d ∈ N ∪ { 0 } such that, for every k ∈ N k\in\mathbb{N} k ∈ N , there exist subsets A 1 , … , A d ⊆ X A_1,\ldots,A_d\subseteq\mathcal{X} A 1 , … , A d ⊆ X , each of size at least k k k , that are set-shattered by C \mathcal{C} C . If no finite largest such d d d exists, we define SET-VC( C ) = ∞ (\mathcal{C})=\infty ( C ) = ∞ .
The combinatorial parameter PERT-VC defined in Definition 2.8 measures the smallest VC dimension that can be achieved after modifying each concept on at most a bounded number of points. Intuitively, PERT-VC( C , k ) (\mathcal{C}, k) ( C , k ) captures how simple the class can become after allowing k k k perturbations per concept, while PERT-VC( C ) (\mathcal{C}) ( C ) captures the limiting value of this quantity as the perturbation budget grows. In Appendix § 9 , we use this parameter to derive upper bounds for agnostic PAC learning with deterministic labels in the infinite-diameter regime.
Definition 2.8. Let C \mathcal{C} C be a concept class and let k ∈ N ∪ { 0 } k\in\mathbb{N}\cup\{0\} k ∈ N ∪ { 0 } . For every concept class C ′ \mathcal{C}' C ′ , define the pseudo-distance from C \mathcal{C} C to C ′ \mathcal{C}' C ′ by
d ( C ; C ′ ) : = inf { k : ∀ h ∈ C ∃ h ′ ∈ C ′ such that ∣ h △ h ′ ∣ ≤ k } . d(\mathcal{C};\mathcal{C}') := \inf\{k:\ \forall h\in\mathcal{C}\ \exists h'\in\mathcal{C}'\text{ such that }|h\triangle h'|\le k\}. d ( C ; C ′ ) := inf { k : ∀ h ∈ C ∃ h ′ ∈ C ′ such that ∣ h △ h ′ ∣ ≤ k } . Define k k k -perturbation VC dimension of C \mathcal{C} C denoted by PERT-VC( C , k ) (\mathcal{C}, k) ( C , k ) and perturbation VC dimension of C \mathcal{C} C denoted by PERT-VC( C ) (\mathcal{C}) ( C ) as
PERT-VC ( C , k ) : = min { VC ( C ′ ) ∣ C ′ is a concept class such that d ( C ; C ′ ) ≤ k } , \operatorname{PERT\text{-}VC}(\mathcal{C}, k) := \min\{\operatorname{VC}(\mathcal{C}')\mid\mathcal{C}'\text{ is a concept class such that }d(\mathcal{C};\mathcal{C}')\le k\}, PERT - VC ( C , k ) := min { VC ( C ′ ) ∣ C ′ is a concept class such that d ( C ; C ′ ) ≤ k } , PERT-VC ( C ) : = min { VC ( C ′ ) ∣ C ′ is a concept class such that d ( C ; C ′ ) < ∞ } . \operatorname{PERT\text{-}VC}(\mathcal{C}) := \min\{\operatorname{VC}(\mathcal{C}')\mid\mathcal{C}'\text{ is a concept class such that }d(\mathcal{C};\mathcal{C}')<\infty\}. PERT - VC ( C ) := min { VC ( C ′ ) ∣ C ′ is a concept class such that d ( C ; C ′ ) < ∞ } .
Analysis of Two Concepts – Finite Diameter
In this section, we state our upper bounds for optimal sample complexity of agnostic PAC learning for concept classes with two concepts.
Our analysis employs empirical risk minimization with memorization. For a concept class C \mathcal{C} C and a sample S ∈ ( X × Y ) ∗ \mathcal{S}\in(\mathcal{X}\times\mathcal{Y})^* S ∈ ( X × Y ) ∗ , a predictor h : X → Y h:\mathcal{X}\to\mathcal{Y} h : X → Y is called an empirical risk minimizer (ERM) with respect to C \mathcal{C} C over S \mathcal{S} S if
h ∈ arg min h ′ ∈ C L S ( h ′ ) . h\in\arg\min_{h'\in\mathcal{C}}L_{\mathcal{S}}(h'). h ∈ arg h ′ ∈ C min L S ( h ′ ) .
Furthermore, for any concept h h h , define
g h , S ( x ) : = { y if ( x , y ) ∈ S , h ( x ) o.w. (1) g_{h,\mathcal{S}}(x):=
\begin{cases}
y & \text{if }(x,y)\in\mathcal{S},\\
h(x) & \text{o.w.}
\end{cases} \tag*{(1)} g h , S ( x ) := { y h ( x ) if ( x , y ) ∈ S , o.w. (1)
A predictor f f f is called a memorizing empirical risk minimizer (MERM) with respect to C \mathcal{C} C over S \mathcal{S} S if there exists an empirical risk minimizer h h h such that f = g h , S f=g_{h,\mathcal{S}} f = g h , S . Furthermore we say that a PAC learner A A A is ERM / MERM with respect to C \mathcal{C} C , if for every S ∈ ( X × Y ) ∗ \mathcal{S}\in(\mathcal{X}\times\mathcal{Y})^* S ∈ ( X × Y ) ∗ , A S A_{\mathcal{S}} A S is ERM / MERM with respect to C \mathcal{C} C over S \mathcal{S} S .
Theorem 3.1. Let K ∈ N K\in\mathbb{N} K ∈ N . Any concept class with two concepts C = { h 0 , h 1 } \mathcal{C}=\{h_0,h_1\} C = { h 0 , h 1 } such that D ( C ) ≤ K D(\mathcal{C})\le K D ( C ) ≤ K , is agnostic PAC learnable with deterministic labels with sample complexity upper bounded by
m C ( ε , δ ) ≤ 8 ( ln ( 4 / δ ) 2 / 3 K 1 / 3 + 2 ln ( 4 / δ ) ) ε m_{\mathcal{C}}(\varepsilon,\delta)\le\frac{8(\ln(4/\delta)^2/3 K^{1/3}+2\ln(4/\delta))}{\varepsilon} m C ( ε , δ ) ≤ ε 8 ( ln ( 4/ δ ) 2 /3 K 1/3 + 2 ln ( 4/ δ ))
Proof. If, for a fixed instance, we flip the label assigned to that instance by every concept, our analysis remains unchanged. Therefore, without loss of generality we can replace h 0 h_0 h 0 with all-zero function and h 1 h_1 h 1 with h 0 △ h 1 h_0\triangle h_1 h 0 △ h 1 . This indicates that ∣ h 1 ∣ ≤ K |h_1|\le K ∣ h 1 ∣ ≤ K . Fix ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) and fix an arbitrary deterministically labeled distribution D \mathcal{D} D over X × Y \mathcal{X} \times\mathcal{Y} X × Y . Let δ ′ = δ / 4 \delta'=\delta/4 δ ′ = δ /4 , and define
opt C ( D ) : = inf h ∈ C L D ( h ) . \operatorname{opt}_{\mathcal{C}}(\mathcal{D}) := \inf_{h\in\mathcal{C}} \mathcal{L}_{\mathcal{D}}(h). opt C ( D ) := h ∈ C inf L D ( h ) .
For any x ∈ X x \in\mathcal{X} x ∈ X , denote p x = D { ( x , 0 ) ∪ ( x , 1 ) } p_x=\mathcal{D}\{(x,0)\cup(x,1)\} p x = D {( x , 0 ) ∪ ( x , 1 )} . Furthermore, let q : = ∑ x ∈ h 1 p x q := \sum_{x\in h_1} p_x q := ∑ x ∈ h 1 p x be the weight of disagreement of h 0 h_0 h 0 and h 1 h_1 h 1 , and μ : = ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x q \mu:= \frac{\sum_{x\in h_1:f^*(x)=1}p_x}{q} μ := q ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x be the ratio of positive labels in the region of disagreement. In addition, without loss of generality assume that μ ≥ 1 2 \mu\ge\frac{1}{2} μ ≥ 2 1 . This implies that L D ( h 1 ) = opt C ( D ) \mathcal{L}_{\mathcal{D}}(h_1)=\operatorname{opt}_{\mathcal{C}}(\mathcal{D}) L D ( h 1 ) = opt C ( D ) .
For any n ∈ N n \in\mathbb{N} n ∈ N , let S \mathcal{S} S be an i.i.d drawn sample of size n n n from D \mathcal{D} D . Denote n S + : = ∣ ( x , y ) ∈ S ∣ x ∈ h 1 ∣ n_{\mathcal{S}}^+ := |(x,y)\in\mathcal{S}\mid x\in h_1| n S + := ∣ ( x , y ) ∈ S ∣ x ∈ h 1 ∣ as number of instances of S \mathcal{S} S in h 1 h_1 h 1 , and p S + : = ∑ x ∈ h 1 : ( x , 1 ) ∈ S p x p_{\mathcal{S}}^+ := \sum_{x\in h_1:(x,1)\in\mathcal{S}}p_x p S + := ∑ x ∈ h 1 : ( x , 1 ) ∈ S p x as weight of positive instances memorized, and set
γ : = n S + μ 2 2 ( K + n S + μ ) + ε 2 q . \gamma:= \frac{n_{\mathcal{S}}^+\mu^2}{2(K+n_{\mathcal{S}}^+\mu)}+\frac{\varepsilon}{2q}. γ := 2 ( K + n S + μ ) n S + μ 2 + 2 q ε .
We show that any PAC learner A \mathbf{A} A that is MERM with respect to C \mathcal{C} C satisfies
m C A ( ε , δ ) ≤ 8 ( ( ln ( 4 / δ ) ) 2 / 3 K 1 / 3 + 2 ln ( 4 / δ ) ) ε . m_{\mathcal{C}}^{\mathbf{A}}(\varepsilon,\delta)\leq\frac{8\left((\ln(4/\delta))^{2/3}K^{1/3}+2\ln(4/\delta)\right)}{\varepsilon}. m C A ( ε , δ ) ≤ ε 8 ( ( ln ( 4/ δ ) ) 2/3 K 1/3 + 2 ln ( 4/ δ ) ) .
Let h ^ \hat{h} h ^ be a concept satisfying
h ^ ∈ arg min h ∈ C L S ( h ) , A S = g h ^ , S . \hat{h}\in\underset{h\in\mathcal{C}}{\arg\min}\ \mathcal{L}_{\mathcal{S}}(h),\qquad A_{\mathcal{S}}=g_{\hat{h},\mathcal{S}}. h ^ ∈ h ∈ C arg min L S ( h ) , A S = g h ^ , S .
Before proceeding to the proof, we state the following claims. The proof of Claim 2 is stated here and rest of them are deferred to Appendix B.1.
Claim 1: Given a fixed n S + n_{\mathcal{S}}^+ n S + we have
Pr [ p S + q < n S + μ 2 K + n S + μ − γ ] < exp ( − n S + γ 2 ) . \Pr\left[\frac{p_{\mathcal{S}}^+}{q}<\frac{n_{\mathcal{S}}^+\mu^2}{K+n_{\mathcal{S}}^+\mu}-\gamma\right]<\exp\left(-n_{\mathcal{S}}^+\gamma^2\right). Pr [ q p S + < K + n S + μ n S + μ 2 − γ ] < exp ( − n S + γ 2 ) .
Claim 2: Given that n S + ≥ 2 ln ( 1 / δ ′ ) γ 2 n_{\mathcal{S}}^+\geq\frac{2\ln(1/\delta')}{\gamma^2} n S + ≥ γ 2 2 l n ( 1/ δ ′ ) with probability at least 1 − 3 δ ′ 1-3\delta' 1 − 3 δ ′ we have L D ( A S ) ≤ ε \mathcal{L}_{\mathcal{D}}(A_{\mathcal{S}})\leq\varepsilon L D ( A S ) ≤ ε .
Claim 3: For any K , n ∈ N K,n\in\mathbb{N} K , n ∈ N and ε , q ∈ ( 0 , 1 ] \varepsilon,q\in(0,1] ε , q ∈ ( 0 , 1 ] we have
F ( q ) : = q ( n q 2 8 K + 2 n q + ε ) 2 ≤ max { 9 4 3 K n ⋅ 1 ε 3 / 2 , 1 ε } . F(q):=\frac{q}{\left(\frac{nq^2}{8K+2nq}+\varepsilon\right)^2}\leq\max\left\{\frac{9}{4\sqrt{3}}\sqrt{\frac{K}{n}}\cdot\frac{1}{\varepsilon^{3/2}},\frac{1}{\varepsilon}\right\}. F ( q ) := ( 8 K + 2 n q n q 2 + ε ) 2 q ≤ max { 4 3 9 n K ⋅ ε 3/2 1 , ε 1 } .
We show that if the claims are held, the proof is complete. Note that if q < ε q<\varepsilon q < ε , we get
L D ( A S ) ≤ L D ( h ^ ) ≤ L D ( h 0 ) < L D ( h 1 ) + ε , \mathcal{L}_{\mathcal{D}}(A_{\mathcal{S}})\leq\mathcal{L}_{\mathcal{D}}(\hat{h})\leq\mathcal{L}_{\mathcal{D}}(h_0)<\mathcal{L}_{\mathcal{D}}(h_1)+\varepsilon, L D ( A S ) ≤ L D ( h ^ ) ≤ L D ( h 0 ) < L D ( h 1 ) + ε ,
which completes the proof. Therefore, we can assume that q ≥ ε q\geq\varepsilon q ≥ ε . First, observe that for n ≥ 8 ln ( 1 / δ ′ ) ε n\geq\frac{8\ln(1/\delta')}{\varepsilon} n ≥ ε 8 l n ( 1/ δ ′ ) Multiplicative Chernoff Bound (Lemma G.1 ) implies
Pr [ n S + ≤ n q 2 ] ≤ exp ( − n q 8 ) ≤ δ ′ . (2) \Pr\left[n_{\mathcal{S}}^+\leq\frac{nq}{2}\right]\leq\exp\left(-\frac{nq}{8}\right)\leq\delta'. \tag*{(2)} Pr [ n S + ≤ 2 n q ] ≤ exp ( − 8 n q ) ≤ δ ′ . (2)
Then observe that γ \gamma γ is an increasing function of μ \mu μ . Since μ ≥ 1 2 \mu\geq\frac{1}{2} μ ≥ 2 1 , this implies that
γ ≥ γ ′ : = n S + 8 K + 4 n S + + ε 2 q . (3) \gamma\geq\gamma':=\frac{n_{\mathcal{S}}^+}{8K+4n_{\mathcal{S}}^+}+\frac{\varepsilon}{2q}. \tag*{(3)} γ ≥ γ ′ := 8 K + 4 n S + n S + + 2 q ε . (3)
Combining with Claim 2, as long as n S + ≥ 2 ln ( 1 / δ ′ ) γ ′ 2 n_{\mathcal{S}}^+\geq\frac{2\ln(1/\delta')}{\gamma'^2} n S + ≥ γ ′2 2 l n ( 1/ δ ′ ) , with probability at least 1 − 3 δ ′ 1-3\delta' 1 − 3 δ ′ we have L D ( A S ) ≤ ε \mathcal{L}_{\mathcal{D}}(A_{\mathcal{S}})\leq\varepsilon L D ( A S ) ≤ ε . Then observe that n S + − 2 ln ( 1 / δ ′ ) γ ′ 2 n_{\mathcal{S}}^+-\frac{2\ln(1/\delta')}{\gamma'^2} n S + − γ ′2 2 l n ( 1/ δ ′ ) is an increasing function w.r.t. n S + n_{\mathcal{S}}^+ n S + . Combining this fact with Equation (3) and Equation (2) as long as
n q 2 ≥ max { 4 q ln ( 1 / δ ′ ) ε , 2 ln ( 1 / δ ′ ) ( n q 16 K + 4 n q + ε 2 q ) 2 } . (4) \frac{nq}{2}\geq\max\left\{\frac{4q\ln(1/\delta')}{\varepsilon},\frac{2\ln(1/\delta')}{\left(\frac{nq}{16K+4nq}+\frac{\varepsilon}{2q}\right)^2}\right\}. \tag*{(4)} 2 n q ≥ max ⎩ ⎨ ⎧ ε 4 q ln ( 1/ δ ′ ) , ( 16 K + 4 n q n q + 2 q ε ) 2 2 ln ( 1/ δ ′ ) ⎭ ⎬ ⎫ . (4)
with probability at least 1 − 4 δ ′ = 1 − δ 1-4\delta'=1-\delta 1 − 4 δ ′ = 1 − δ we have L D ( A S ) ≤ ε \mathcal{L}_{D}(A_{S})\leq\varepsilon L D ( A S ) ≤ ε . Claim 3 implies that
sup q ∈ ( 0 , 1 ] 1 q ( 4 ln ( 1 / δ ′ ) n q 16 K + 4 n q + ε 2 q ) 2 = 16 ln ( 1 / δ ′ ) sup q ∈ ( 0 , 1 ] q ( n q 2 8 K + 2 n q + ε ) 2 ≤ 4 ln ( 1 / δ ′ ) max { 4 ε , 27 K n ε 3 } . \sup_{q\in(0,1]} \frac{1}{q}\left(\frac{4\ln(1/\delta')}{\frac{nq}{16K+4nq}+\frac{\varepsilon}{2q}}\right)^{2}=16\ln(1/\delta')\sup_{q\in(0,1]}\frac{q}{\left(\frac{nq^{2}}{8K+2nq}+\varepsilon\right)^{2}}\leq4\ln(1/\delta')\max\left\{\frac{4}{\varepsilon},\sqrt{\frac{27K}{n\varepsilon^{3}}}\right\}. q ∈ ( 0 , 1 ] sup q 1 ( 16 K + 4 n q n q + 2 q ε 4 ln ( 1/ δ ′ ) ) 2 = 16 ln ( 1/ δ ′ ) q ∈ ( 0 , 1 ] sup ( 8 K + 2 n q n q 2 + ε ) 2 q ≤ 4 ln ( 1/ δ ′ ) max { ε 4 , n ε 3 27 K } .
Combining this with (4) completes the proof.
Proof of Claim 2: Due to Claim 1 with probability at least 1 − δ ′ 1-\delta' 1 − δ ′ it holds that
p S + q ≥ n S + μ 2 K + n S + μ − γ . (5) \frac{p_{S}^{+}}{q}\geq\frac{n_{S}^{+}\mu^{2}}{K+n_{S}^{+}\mu}-\gamma. \tag*{(5)} q p S + ≥ K + n S + μ n S + μ 2 − γ . (5)
We consider two cases. Case 1: 2 μ − 1 > γ 2\mu-1>\gamma 2 μ − 1 > γ . Since, A S = g h ^ S , S A_{S}=g_{\hat{h}_{S},S} A S = g h ^ S , S , this implies
L D ( A S ) ≤ L D ( g h 0 , S ) = L D ( h 0 ) − p S + = L D ( h 1 ) + ( μ − ( 1 − μ ) ) q − p S + = opt C ( D ) + q ( 2 μ − 1 − p S + q ) < opt C ( D ) + q ( 2 γ − n S + μ 2 K + n S + μ ) = opt C ( D ) + ε . \begin{aligned}
\mathcal{L}_{D}(A_{S})&\leq\mathcal{L}_{D}(g_{h_{0},S})\\
&=\mathcal{L}_{D}(h_{0})-p_{S}^{+}\\
&=\mathcal{L}_{D}(h_{1})+(\mu-(1-\mu))q-p_{S}^{+}\\
&=\operatorname{opt}_{\mathcal{C}}(D)+q\left(2\mu-1-\frac{p_{S}^{+}}{q}\right)\\
&<\operatorname{opt}_{\mathcal{C}}(D)+q\left(2\gamma-\frac{n_{S}^{+}\mu^{2}}{K+n_{S}^{+}\mu}\right)=\operatorname{opt}_{\mathcal{C}}(D)+\varepsilon.
\end{aligned} L D ( A S ) ≤ L D ( g h 0 , S ) = L D ( h 0 ) − p S + = L D ( h 1 ) + ( μ − ( 1 − μ )) q − p S + = opt C ( D ) + q ( 2 μ − 1 − q p S + ) < opt C ( D ) + q ( 2 γ − K + n S + μ n S + μ 2 ) = opt C ( D ) + ε .
This completes the proof of the Claim.
Case 2: 2 μ − 1 ≥ γ 2\mu-1\geq\gamma 2 μ − 1 ≥ γ . Note that every instance of S ′ = { x ∈ h 1 : ∃ y ∈ Y : ( x , y ) ∈ S } S'=\{x\in h_{1}:\exists y\in\mathcal{Y}:(x,y)\in S\} S ′ = { x ∈ h 1 : ∃ y ∈ Y : ( x , y ) ∈ S } is an i.i.d. sample from D ( x ∣ x ∈ h 1 ) D(x\mid x\in h_{1}) D ( x ∣ x ∈ h 1 ) . Therefore, for every x ∈ S ′ x\in S' x ∈ S ′ the random variable A x : = 1 { f ∗ ( x ) = 1 } A_{x}:=\mathbb{1}\{f^{*}(x)=1\} A x := 1 { f ∗ ( x ) = 1 } is a Bernoulli random variable with parameter μ \mu μ . Thus, using Hoeffding inequality (Theorem G.2 ) the probability of h ^ = h 0 \hat{h}=h_{0} h ^ = h 0 is upper bounded by
Pr [ ∣ { x ∈ S ′ : f ∗ ( x ) = 1 } ∣ ∣ S ′ ∣ < 1 2 | n S + ] ≤ 2 exp ( − 2 n S + ( μ − 1 2 ) 2 ) \Pr\left[\frac{|\{x\in S':f^{*}(x)=1\}|}{|S'|}<\frac{1}{2}\,\middle|\,n_{S}^{+}\right]\leq2\exp\left(-2n_{S}^{+}\left(\mu-\frac{1}{2}\right)^{2}\right) Pr [ ∣ S ′ ∣ ∣ { x ∈ S ′ : f ∗ ( x ) = 1 } ∣ < 2 1 n S + ] ≤ 2 exp ( − 2 n S + ( μ − 2 1 ) 2 )
≤ 2 exp ( − n S + γ 2 2 ) ≤ 2 δ ′ . \leq2\exp\left(-\frac{n_{S}^{+}\gamma^{2}}{2}\right)\leq2\delta'. ≤ 2 exp ( − 2 n S + γ 2 ) ≤ 2 δ ′ .
By a union bound with Equation (5) the proof will be completed. □
Conclusion, Discussion, and Future Directions
In this manuscript, we study the fundamental problem of agnostic PAC learning under deterministic labels. We make significant progress on the optimal sample complexity of this problem, substantially improving both the upper and lower bounds of the previous work. Technically, our upper bound is obtained by augmenting an empirical risk minimizer with memorization, and the analysis of this hybrid procedure differs considerably from known analyses of PAC learning algorithms, which may be of independent interest. This use of memorization in our results also sheds light on its role in machine learning. We then extend our investigation to the problem of online binary classification, where memorization again plays an important role. Eventually, we discuss the following future directions:
Another natural direction for future work is to study agnostic active learning under deterministic labels. It is straightforward to see that, in the special case of concept classes with two functions, the optimal query complexity of active learning under deterministic labels is upper bounded by K K K instead of K 1 / 3 / ε K^{1/3}/\varepsilon K 1/3 / ε . As a result, active learning may offer a significant advantage over passive learning in this setting. This direction is especially interesting to explore in light of the recent breakthrough result of [28 ] , whose proof uses the diameter in an essential way.
Acknowledgments and Disclosure of Funding
Steve Hanneke acknowledges support by grant no. 2024243 from the United States - Israel Binational Science Foundation (BSF). Shai Ben-David’s research is supported by an NSERC Discovery grant and through a CIFAR AI Chair. Farnam Mansouri is supported by a NSERC Canada Graduate Scholarship-Doctoral (CGS-D), David Cheriton Scholarship and a Vector Institute Research Grant.
Related Work
Realizable PAC learning. The classical sample-complexity theory of PAC learning was initiated by Vapnik and Chervonenkis [ [52 ] and Valiant [ [51 ] , and was later characterized in terms of the VC dimension by Blumer et al. [ [13 ] . In the realizable setting, Blumer et al. [ [13 ] showed that every class of VC dimension d d d is learnable using empirical risk minimization (ERM), with sample complexity at most
O ( d log ( 1 / ε ) + log ( 1 / δ ) ε ) \mathcal{O}\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right) O ( ε d log ( 1/ ε ) + log ( 1/ δ ) )
and that Ω ( ( d + log ( 1 / δ ) ) / ε ) \Omega((d+\log(1/\delta))/\varepsilon) Ω (( d + log ( 1/ δ )) / ε ) samples are necessary in general. This upper bound is also known to be optimal for proper learners, i.e., learners whose outputs belong to the concept class, including ERM Haussler et al. [ [31 ] , Auer and Ortner [ [5 ] , Simon [ [47 ] , Bousquet et al. [ [15 ] . For improper learners, the remaining logarithmic gap in the dependence on ε \varepsilon ε was resolved by Hanneke [ [27 ] , building on ideas of Simon [ [47 ] , who proved the optimal realizable PAC bound
Θ ( d + log ( 1 / δ ) ε ) \Theta\left(\frac{d+\log(1/\delta)}{\varepsilon}\right) Θ ( ε d + log ( 1/ δ ) )
for arbitrary VC classes. More recently, there have been several attempts to prove optimal guarantees for other, arguably simpler, learning algorithms. These include the practical heuristic of bagging Larsen [ [36 ] , Breiman [ [16 ] , a variant of the one-inclusion graph learning algorithm Aden-Ali et al. [ [1 ] , Haussler et al. [ [31 ] , and a simple majority vote among three ERM classifiers Aden-Ali et al. [ [2 ] .
Agnostic PAC learning. In the agnostic setting, the first general VC-type bounds were obtained by Vapnik and Chervonenkis [ [52 ] and developed in the distribution-free decision-theoretic framework by Haussler [ [30 ] , showing that ERM attains sample complexity
O ( d log ( 1 / ε ) + log ( 1 / δ ) ε 2 ) \mathcal{O}\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon^2}\right) O ( ε 2 d log ( 1/ ε ) + log ( 1/ δ ) )
and that Ω ( ( d + log ( 1 / δ ) ) / ε 2 ) \Omega((d+\log(1/\delta))/\varepsilon^2) Ω (( d + log ( 1/ δ )) / ε 2 ) samples are necessary in general. The extra log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε ) factor in the VC term was later removed using sharper empirical-process techniques, most notably Talagrand’s chaining bounds [48 ] , showing that, unlike in the realizable setting, ERM achieves the optimal agnostic PAC sample complexity
Θ ( d + log ( 1 / δ ) ε 2 ) . \Theta\left(\frac{d+\log(1/\delta)}{\varepsilon^2}\right). Θ ( ε 2 d + log ( 1/ δ ) ) .
Upper Bounds for Finite Diameter
In this section, we prove our upper bounds for optimal sample complexity of agnostic PAC learning with deterministic labels for concept classes with finite diameter. We first prove the two remaining claims used in the proof of Theorem 3.1 in subsection B.1. Then, in subsection B.2 using the results for concept classes with two concepts, we prove our upper bounds for general VC classes.
Missing Proofs for Two Concepts
In this subsection, we prove the two remaining claims used in the proof of Theorem 3.1 . Before proving these claims, we recall an existing missing-mass concentration result, which allows us to convert bounds on the expectation of p ξ + p_{\xi}^{+} p ξ + into high-probability bounds.
Theorem B.1 (Theorem 1 of Berend and Kontorovich [ [10 ] ). Let p = ( p 1 , p 2 , … ) p=(p_1,p_2,\ldots) p = ( p 1 , p 2 , … ) be a distribution over N \mathbb{N} N and suppose that X 1 , X 2 , … , X n X_1,X_2,\ldots,X_n X 1 , X 2 , … , X n are sampled i.i.d according to p p p . Define the indicator variable ξ j \xi_j ξ j to be 0 if j j j occurs in the sample and 1 otherwise:
ξ j = 1 { j ∉ { X 1 , … , X n } } , j ∈ N . \xi_j=\mathbb{1}_{\{j\notin\{X_1,\ldots,X_n\}\}}, \qquad j\in\mathbb{N}. ξ j = 1 { j ∈ / { X 1 , … , X n }} , j ∈ N . Denote the missing mass as the random variable U n = ∑ j ∈ N p j ξ j U_n=\sum_{j\in\mathbb{N}}p_j\xi_j U n = ∑ j ∈ N p j ξ j . Then
Pr [ U n > E [ U n ] + ε ] < exp ( − n ε 2 ) \Pr\left[U_n>\mathbb{E}[U_n]+\varepsilon\right]<\exp\left(-n\varepsilon^2\right) Pr [ U n > E [ U n ] + ε ] < exp ( − n ε 2 )
We then proceed to the proof of the claims.
Proof of Claim 1 of Theorem 3.1 . We first bound expectation of p S + p_S^+ p S + given n S + n_S^+ n S + by
E [ p S + ∣ n S + ] = ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x Pr ( ( x , 1 ) ∈ S ∣ n S + ) = ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x ( 1 − ( 1 − p x q ) n S + ) ≥ ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x ( 1 − e − p x n S + q ) ≥ ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x p x n S + q + n S + p x = ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x 2 n S + q + n S + p x \begin{aligned}
\mathbb{E}\left[p_S^+ \mid n_S^+\right] = \sum_{x \in h_1:f^*(x)=1} p_x \Pr\left((x,1) \in S \mid n_S^+\right) \\
&= \sum_{x \in h_1:f^*(x)=1} p_x\left(1-\left(1-\frac{p_x}{q}\right)^{n_S^+}\right) \\
&\ge\sum_{x \in h_1:f^*(x)=1} p_x\left(1-e^{-\frac{p_x n_S^+}{q}}\right) \\
&\ge\sum_{x \in h_1:f^*(x)=1} p_x\frac{p_x n_S^+}{q+n_S^+p_x} \\
&= \sum_{x \in h_1:f^*(x)=1}\frac{p_x^2n_S^+}{q+n_S^+p_x}
\end{aligned} E [ p S + ∣ n S + ] = x ∈ h 1 : f ∗ ( x ) = 1 ∑ p x Pr ( ( x , 1 ) ∈ S ∣ n S + ) = x ∈ h 1 : f ∗ ( x ) = 1 ∑ p x ( 1 − ( 1 − q p x ) n S + ) ≥ x ∈ h 1 : f ∗ ( x ) = 1 ∑ p x ( 1 − e − q p x n S + ) ≥ x ∈ h 1 : f ∗ ( x ) = 1 ∑ p x q + n S + p x p x n S + = x ∈ h 1 : f ∗ ( x ) = 1 ∑ q + n S + p x p x 2 n S +
By applying Sedrakyan inequality (Lemma G.1 ) we get
E [ p S + ∣ n S + ] ≥ n S + ( ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x ) 2 ∑ x ∈ h 1 : f ∗ ( x ) = 1 ( q + n S + p x ) ≥ n S + ( q μ ) 2 K q + n S + q μ = n S + q μ 2 K + n S + μ (6) \begin{aligned}
\mathbb{E}\left[p_S^+ \mid n_S^+\right]\ge n_S^+\frac{\left(\sum_{x\in h_1:f^*(x)=1}p_x\right)^2}{\sum_{x\in h_1:f^*(x)=1}(q+n_S^+p_x)} \\
&\ge n_S^+\frac{(q\mu)^2}{Kq+n_S^+q\mu} \\
&=\frac{n_S^+q\mu^2}{K+n_S^+\mu} \tag*{(6)}
\end{aligned} E [ p S + ∣ n S + ] ≥ n S + ∑ x ∈ h 1 : f ∗ ( x ) = 1 ( q + n S + p x ) ( ∑ x ∈ h 1 : f ∗ ( x ) = 1 p x ) 2 ≥ n S + K q + n S + q μ ( q μ ) 2 = K + n S + μ n S + q μ 2 (6)
Observe that size of V = { x ∈ h 1 , f ∗ ( x ) = 1 } V=\{x\in h_1,f^*(x)=1\} V = { x ∈ h 1 , f ∗ ( x ) = 1 } is at most K K K and thus is countable. Consider probability distribution p \mathbf{p} p over U U U such that p ( x ) = p x μ q p(x)=\frac{p_x}{\mu q} p ( x ) = μ q p x . Then, S ′ : = { x ∈ h 1 : ∃ y ∈ Y : ( x , y ) ∈ S } S' := \{x\in h_1:\exists y\in Y:(x,y)\in S\} S ′ := { x ∈ h 1 : ∃ y ∈ Y : ( x , y ) ∈ S } would be i.i.d sample of size n S + n_S^+ n S + from p \mathbf{p} p .
Therefore, we can use Theorem B.1 over the domain V V V and distribution p \mathbf{p} p , and i.i.d. samples S ′ S' S ′ .
Then the missing mass U n S + U_{n_S^+} U n S + would be 1 − p S + μ q 1-\frac{p_S^+}{\mu q} 1 − μ q p S + . By using Equation (6) we get
Pr [ p S + μ q < n S + μ K + n S + μ − γ | n S + ] ≤ Pr [ U n S + ≥ E [ U n S + ∣ n S + ] + γ | n S + ] < exp ( − n S + γ 2 ) \Pr\left[\frac{p_S^+}{\mu q}<\frac{n_S^+\mu}{K+n_S^+\mu}-\gamma\ \middle|\ n_S^+\right]\le\Pr\left[U_{n_S^+}\ge\mathbb{E}\left[U_{n_S^+}\mid n_S^+\right]+\gamma\ \middle|\ n_S^+\right]<\exp\left(-n_S^+\gamma^2\right) Pr [ μ q p S + < K + n S + μ n S + μ − γ n S + ] ≤ Pr [ U n S + ≥ E [ U n S + ∣ n S + ] + γ n S + ] < exp ( − n S + γ 2 )
Since μ ≤ 1 \mu\le1 μ ≤ 1 this implies that
Pr [ p S + q < n S + μ 2 K + n S + μ − γ | n S + ] < exp ( − n S + γ 2 ) (7) \Pr\left[\frac{p_S^+}{q}<\frac{n_S^+\mu^2}{K+n_S^+\mu}-\gamma\ \middle|\ n_S^+\right]<\exp\left(-n_S^+\gamma^2\right) \tag*{(7)} Pr [ q p S + < K + n S + μ n S + μ 2 − γ n S + ] < exp ( − n S + γ 2 ) (7)
This completes the proof of Claim 1. □
Proof of Claim 3 of Theorem 3.1 . We bound sup q ∈ ( 0 , 1 ] F ( q ) \sup_{q\in(0,1]}F(q) sup q ∈ ( 0 , 1 ] F ( q ) by considering two cases.
Case 1: n q ≤ 4 K nq\le4K n q ≤ 4 K . In this regime, 8 K + 2 n q ≤ 16 K 8K+2nq\le16K 8 K + 2 n q ≤ 16 K , hence
n q 2 8 K + 2 n q ≥ n q 2 16 K . \frac{nq^2}{8K+2nq}\ge\frac{nq^2}{16K}. 8 K + 2 n q n q 2 ≥ 16 K n q 2 .
Therefore,
F ( q ) ≤ q ( ε + n q 2 16 K ) 2 . F(q)\le\frac{q}{\left(\varepsilon+\frac{nq^2}{16K}\right)^2}. F ( q ) ≤ ( ε + 16 K n q 2 ) 2 q .
Consider the function
g ( q ) : = q ( ε + a q 2 ) 2 , a : = n 16 K . g(q):=\frac{q}{(\varepsilon+aq^2)^2},\qquad a:=\frac{n}{16K}. g ( q ) := ( ε + a q 2 ) 2 q , a := 16 K n .
A direct calculation shows that g g g is maximized at q 2 = ε 3 a q^2 = \frac{\varepsilon}{3a} q 2 = 3 a ε , and
max q > 0 g ( q ) = 9 16 3 ⋅ 1 a ε 3 / 2 . \max_{q>0} g(q) = \frac{9}{16\sqrt{3}} \cdot\frac{1}{\sqrt{a}\,\varepsilon^{3/2}}. q > 0 max g ( q ) = 16 3 9 ⋅ a ε 3/2 1 .
Substituting a = n 16 K a = \frac{n}{16K} a = 16 K n gives
sup q ∈ ( 0 , 1 ] F ( q ) ≤ 9 4 3 K n ⋅ 1 ε 3 / 2 . \sup_{q\in(0,1]} F(q) \le\frac{9}{4\sqrt{3}}\sqrt{\frac{K}{n}} \cdot\frac{1}{\varepsilon^{3/2}}. q ∈ ( 0 , 1 ] sup F ( q ) ≤ 4 3 9 n K ⋅ ε 3/2 1 .
Case 2: n q ≥ 4 K nq \ge4K n q ≥ 4 K . In this regime, 8 K + 2 n q ≤ 4 n q 8K + 2nq \le4nq 8 K + 2 n q ≤ 4 n q , so
n q 2 8 K + 2 n q ≥ q 4 . \frac{nq^2}{8K + 2nq} \ge\frac{q}{4}. 8 K + 2 n q n q 2 ≥ 4 q .
Hence
F ( q ) ≤ q ( ε + q / 4 ) 2 . F(q) \le\frac{q}{(\varepsilon+ q/4)^2}. F ( q ) ≤ ( ε + q /4 ) 2 q .
The right-hand side is maximized at q = 4 ε q = 4\varepsilon q = 4 ε , yielding F ( q ) ≤ 1 ε F(q) \le\frac{1}{\varepsilon} F ( q ) ≤ ε 1 .
Combining both cases completes the proof of claim 3.
Analysis of General Concept Class
In this subsection section, we prove our upper bounds for agnostic PAC learning with deterministic labels of VC classes with finite diameter.
We first prove the result for finite concept classes. The proof reduces the problem to the two-concept case by applying the preceding two-concept guarantee uniformly over all pairs of concepts in C C C . Once this uniform event holds, an MERM over the full class can be compared to each competing concept h ∈ C h \in C h ∈ C by restricting attention to the two-concept class consisting of h h h and the ERM underlying the MERM predictor. This pairwise reduction is similar in spirit to ideas used in density estimation [21 ] .
Theorem B.2. Let K ∈ N K \in\mathbb{N} K ∈ N . There exists a universal constant a 1 > 0 a_1 > 0 a 1 > 0 such that every finite sized concept class C C C such that D ( C ) ≤ K D(C) \le K D ( C ) ≤ K , is agnostic PAC learnable with deterministic labels with sample complexity upper bounded by
m C ( ε , δ ) ≤ a 1 ( ( ln ( ∣ C ∣ / δ ) ) 2 / 3 K 1 / 3 + ln ( ∣ C ∣ / δ ) ) ε . m_C(\varepsilon,\delta) \le\frac{a_1\left(\left(\ln(|C|/\delta)\right)^{2/3}K^{1/3}+\ln(|C|/\delta)\right)}{\varepsilon}. m C ( ε , δ ) ≤ ε a 1 ( ( ln ( ∣ C ∣/ δ ) ) 2/3 K 1/3 + ln ( ∣ C ∣/ δ ) ) . Proof. Denote M : = ( ∣ C ∣ 2 ) M := \binom{|C|}{2} M := ( 2 ∣ C ∣ ) , and let n ∈ N n \in\mathbb{N} n ∈ N . Fix ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) and any deterministically labeled distribution D D D , and let S S S be an i.i.d. sample of size n n n drawn from D D D . Furthermore, suppose PAC learner A is MERM with respect to C C C .
Fix any two distinct concepts h 1 , h 2 ∈ C h_1,h_2 \in C h 1 , h 2 ∈ C . By Theorem 3.1 , as long as
n ≥ 8 ( ( ln ( 4 M / δ ) ) 2 / 3 K 1 / 3 + 2 ln ( 4 M / δ ) ) ε , n \ge\frac{8\left(\left(\ln(4M/\delta)\right)^{2/3}K^{1/3}+2\ln(4M/\delta)\right)}{\varepsilon}, n ≥ ε 8 ( ( ln ( 4 M / δ ) ) 2/3 K 1/3 + 2 ln ( 4 M / δ ) ) , every MERM A h 1 , h 2 A^{h_1,h_2} A h 1 , h 2 with respect to { h 1 , h 2 } \{h_1,h_2\} { h 1 , h 2 } , with probability at least 1 − δ / M 1-\delta/M 1 − δ / M , satisfies
L D ( A S h 1 , h 2 ) ≤ min i ∈ { 1 , 2 } L D ( h i ) + ε . (8) \mathcal{L}_D(A_S^{h_1,h_2}) \le\min_{i\in\{1,2\}}\mathcal{L}_D(h_i)+\varepsilon. \tag*{(8)} L D ( A S h 1 , h 2 ) ≤ i ∈ { 1 , 2 } min L D ( h i ) + ε . (8) Since M ≤ ∣ C ∣ 2 M \le|C|^2 M ≤ ∣ C ∣ 2 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , it suffices for n n n to satisfy
n ≥ 16 ( ( ln ( 2 ∣ C ∣ / δ ) ) 2 / 3 K 1 / 3 + 2 ln ( 2 ∣ C ∣ / δ ) ) ε . n \ge\frac{16\left(\left(\ln(2|C|/\delta)\right)^{2/3}K^{1/3}+2\ln(2|C|/\delta)\right)}{\varepsilon}. n ≥ ε 16 ( ( ln ( 2∣ C ∣/ δ ) ) 2/3 K 1/3 + 2 ln ( 2∣ C ∣/ δ ) ) . By taking a union bound over all pairs of concepts in C C C , with probability at least 1 − δ 1-\delta 1 − δ , Equation (8) holds simultaneously for every pair of distinct concepts.
Let h ^ \hat{h} h ^ be any concept satisfying
h ^ = arg min h ∈ C L S ( h ) , A S = g h ^ , S \hat{h} = \mathop{\arg\min}_{h \in\mathcal{C}} \mathcal{L}_{S}(h), \qquad A_{S} = g_{\hat{h},S} h ^ = arg min h ∈ C L S ( h ) , A S = g h ^ , S
Notice that for every h ≠ h ^ h \ne\hat{h} h = h ^ in C \mathcal{C} C , A S A_{S} A S is also MERM with respect to { h , h ^ } \{h,\hat{h}\} { h , h ^ } over S S S . Therefore, by Equation (8) ,
L D ( A S ) ≤ min ( L D ( h ) , L D ( h ^ ) ) + ε \mathcal{L}_{D}(A_{S}) \le\min\left(\mathcal{L}_{D}(h),\mathcal{L}_{D}(\hat{h})\right) + \varepsilon L D ( A S ) ≤ min ( L D ( h ) , L D ( h ^ ) ) + ε
Which implies that
L D ( A S ) ≤ min h ∈ C L D ( h ) + ε \mathcal{L}_{D}(A_{S}) \le\min_{h \in\mathcal{C}} \mathcal{L}_{D}(h) + \varepsilon L D ( A S ) ≤ h ∈ C min L D ( h ) + ε
This completes the proof.
We next extend the finite-class guarantee to VC classes. The standard way to pass from finite to infinite classes is to discretise the class on a suitably chosen sample. In our setting, the relevant discretization is obtained through an ε \varepsilon ε -net argument: after drawing an auxiliary sample from the distributions, concepts which their true error differ significantly must disagree on at least one point of this sample. This allows us to replace the original infinite class by a finite projection while preserving the comparisons needed for the finite-class theorem. Our descretization technique is similar to used in Hopkins et al. [ [33 ] .
Definition B.3 (ε \varepsilon ε -net). Let X \mathcal{X} X be some domain, B ⊆ 2 X \mathcal{B} \subseteq2^{\mathcal{X}} B ⊆ 2 X a collection of subsets of X \mathcal{X} X and Q Q Q a distribution over X \mathcal{X} X . An ε \varepsilon ε -net for W \mathcal{W} W with respect to Q Q Q is a subset S ⊆ X S \subseteq\mathcal{X} S ⊆ X that intersects every member of B \mathcal{B} B that has Q Q Q -weight at least ε \varepsilon ε .
Lemma B.4 (Haussler and Welzl [ [29 ] ). Let C \mathcal{C} C be a concept class over X \mathcal{X} X with VC ( C ) = d < ∞ \operatorname{VC}(\mathcal{C}) = d < \infty VC ( C ) = d < ∞ and ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) . There exists a universal constant a 2 > 0 a_{2} > 0 a 2 > 0 such that for every distribution Q Q Q over X \mathcal{X} X , a sample S S S of size
n ≥ a 2 ( d ln ( 1 / ε ) + ln ( 1 / δ ) ) ε n \ge\frac{a_{2}\left(d\ln(1/\varepsilon) + \ln(1/\delta)\right)}{\varepsilon} n ≥ ε a 2 ( d ln ( 1/ ε ) + ln ( 1/ δ ) ) i.i.d. drawn from Q Q Q is ε \varepsilon ε -net for C \mathcal{C} C with respect to Q Q Q with probability at least 1 − δ 1-\delta 1 − δ .
Theorem B.5. Let K , d ∈ N K,d \in\mathbb{N} K , d ∈ N . There exists a universal constant a 3 > 0 a_{3} > 0 a 3 > 0 such that every concept class such that VC ( C ) ≤ d \operatorname{VC}(\mathcal{C}) \le d VC ( C ) ≤ d where D ( C ) ≤ K D(\mathcal{C}) \le K D ( C ) ≤ K , is agnostic PAC learnable with deterministic labels with sample complexity upper bounded by
m C ( ε , δ ) ≤ a 3 ( ( d ln ( 1 / ε ) + ln ( 1 / δ ) ) 2 / 3 K 1 / 3 + d ln ( 1 / ε ) + ln ( 1 / δ ) ) ε . m_{\mathcal{C}}(\varepsilon,\delta) \le\frac{a_{3}\left(\left(d\ln(1/\varepsilon) + \ln(1/\delta)\right)^{2/3}K^{1/3} + d\ln(1/\varepsilon) + \ln(1/\delta)\right)}{\varepsilon}. m C ( ε , δ ) ≤ ε a 3 ( ( d ln ( 1/ ε ) + ln ( 1/ δ ) ) 2/3 K 1/3 + d ln ( 1/ ε ) + ln ( 1/ δ ) ) .
Proof. Throughout this proof, for every T ∈ ( X × Y ) ∗ T \in(\mathcal{X} \times\mathcal{Y})^{*} T ∈ ( X × Y ) ∗ we denote the multiset X ( T ) : = { x ∣ ( x , y ) ∈ T } X(T) := \{x \mid(x,y) \in T\} X ( T ) := { x ∣ ( x , y ) ∈ T } . Also, for a N ⊆ X N \subseteq\mathcal{X} N ⊆ X and h ∈ Y X h \in\mathcal{Y}^{\mathcal{X}} h ∈ Y X we define restriction of h h h to N N N denoted by h ∣ N h|_{N} h ∣ N as { h ( x ) ∣ x ∈ N } \{h(x) \mid x \in N\} { h ( x ) ∣ x ∈ N } .
Fix ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) and fix an arbitrary deterministically labeled distribution D \mathcal{D} D over X × Y \mathcal{X} \times\mathcal{Y} X × Y . Let
n 1 = 2 a 2 ( ( 2 d + 1 ) ln ( 2 / ε ) + ln ( 2 / δ ) ) ε , n_{1} = \frac{2a_{2}\left((2d+1)\ln(2/\varepsilon) + \ln(2/\delta)\right)}{\varepsilon}, n 1 = ε 2 a 2 ( ( 2 d + 1 ) ln ( 2/ ε ) + ln ( 2/ δ ) ) ,
n 2 = 2 a 1 ( ( d ln ( e n 1 / d ) + ln ( 4 / δ ) ) 2 / 3 K 1 / 3 + d ln ( e n 1 / d ) + ln ( 4 / δ ) ) ε , n_{2} = \frac{2a_{1}\left(\left(d\ln(en_{1}/d) + \ln(4/\delta)\right)^{2/3}K^{1/3} + d\ln(en_{1}/d) + \ln(4/\delta)\right)}{\varepsilon}, n 2 = ε 2 a 1 ( ( d ln ( e n 1 / d ) + ln ( 4/ δ ) ) 2/3 K 1/3 + d ln ( e n 1 / d ) + ln ( 4/ δ ) ) ,
where a 1 a_{1} a 1 and a 2 a_{2} a 2 are the universal constant defined in Theorem B.2 and Lemma B.4 . Let S S S be an i.i.d. sample of size n ≥ n 1 + n 2 n \ge n_{1}+n_{2} n ≥ n 1 + n 2 drawn from D \mathcal{D} D . Denote S 1 S_{1} S 1 as first n 1 n_{1} n 1 element of S S S , and S 2 = S ∖ S 1 S_{2} = S \setminus S_{1} S 2 = S ∖ S 1 .
Denote C X ( S 1 ) : = { h ∣ X ( S 1 ) : h ∈ C } \mathcal{C}_{\mathcal{X}(S_{1})} := \{h|_{\mathcal{X}(S_{1})} : h \in\mathcal{C}\} C X ( S 1 ) := { h ∣ X ( S 1 ) : h ∈ C } . For each h ∈ C X ( S 1 ) h \in\mathcal{C}_{\mathcal{X}(S_{1})} h ∈ C X ( S 1 ) , choose one representative concept h ′ ∈ C h' \in\mathcal{C} h ′ ∈ C such that h ′ ∣ X ( S 1 ) = h ∣ X ( S 1 ) h'|_{\mathcal{X}(S_{1})} = h|_{\mathcal{X}(S_{1})} h ′ ∣ X ( S 1 ) = h ∣ X ( S 1 ) . Let the resulting finite subclass be denoted by C 1 \mathcal{C}_{1} C 1 . Let A S A_{S} A S be MERM with respect to C 1 \mathcal{C}_{1} C 1 over S 2 S_{2} S 2 . It suffices to prove that with probability at least 1 − δ 1-\delta 1 − δ
L D ( A S ) ≤ inf h ∈ C L D ( h ) + ε . \mathcal{L}_{D}(A_{S}) \le\inf_{h \in\mathcal{C}} \mathcal{L}_{D}(h) + \varepsilon. L D ( A S ) ≤ h ∈ C inf L D ( h ) + ε .
S 1 S_1 S 1 is ε / 2 \varepsilon/2 ε /2 -net. First note that VC ( C △ C ) ≤ 2 d + 1 \operatorname{VC}(\mathcal{C}\mathbin{\triangle}\mathcal{C}) \le2d+1 VC ( C △ C ) ≤ 2 d + 1 (it can be shown similar to the manner claim 1 of Ben-David and Litman [ [6 ] was proved). Thus, from Lemma B.4, we have that S 1 S_1 S 1 is a ε / 2 \varepsilon/2 ε /2 -net for C △ C \mathcal{C}\mathbin{\triangle}\mathcal{C} C △ C with respect to D X D_{\mathcal{X}} D X with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 , where D X D_{\mathcal{X}} D X is the marginal distribution of D \mathcal{D} D over X \mathcal{X} X . This indicates that, for every h ∈ C h\in\mathcal{C} h ∈ C and h ′ ∈ C 1 h'\in\mathcal{C}_1 h ′ ∈ C 1 such that h ∣ X ( S 1 ) = h ′ ∣ X ( S 1 ) h|_{\mathcal{X}(S_1)}=h'|_{\mathcal{X}(S_1)} h ∣ X ( S 1 ) = h ′ ∣ X ( S 1 ) , we have h △ h ′ ∩ S 1 = ∅ h\mathbin{\triangle}h'\cap S_1=\varnothing h △ h ′ ∩ S 1 = ∅ . Thus, D X ( h △ h ′ ) < ε / 2 D_{\mathcal{X}}(h\mathbin{\triangle}h')<\varepsilon/2 D X ( h △ h ′ ) < ε /2 . Therefore,
L D ( h ) ≤ L D ( h ′ ) + ε / 2 , L_{\mathcal{D}}(h)\le L_{\mathcal{D}}(h')+\varepsilon/2, L D ( h ) ≤ L D ( h ′ ) + ε /2 ,
which implies that
inf h ∈ C L D ( h ) ≤ inf h ′ ∈ C 1 L D ( h ′ ) + ε / 2 , (9) \inf_{h\in\mathcal{C}}L_{\mathcal{D}}(h)\le\inf_{h'\in\mathcal{C}_1}L_{\mathcal{D}}(h')+\varepsilon/2, \tag*{(9)} h ∈ C inf L D ( h ) ≤ h ′ ∈ C 1 inf L D ( h ′ ) + ε /2 , (9)
Applying results for finite classes. Notice that D ( C ′ ) ≤ D ( C ) ≤ K D(\mathcal{C}')\le D(\mathcal{C})\le K D ( C ′ ) ≤ D ( C ) ≤ K . Furthermore, by Sauer’s Lemma [43 , 46 ] , since VC ( C ) ≤ d \operatorname{VC}(\mathcal{C})\le d VC ( C ) ≤ d ,
∣ C 1 ∣ = ∣ C X ( S 1 ) ∣ ≤ ( e n 1 d ) d . |\mathcal{C}_1|=|\mathcal{C}_{\mathcal{X}(S_1)}|\le\left(\frac{en_1}{d}\right)^d. ∣ C 1 ∣ = ∣ C X ( S 1 ) ∣ ≤ ( d e n 1 ) d .
Thus,
ln ∣ C 1 ∣ ≤ d ln ( e n 1 d ) . \ln|\mathcal{C}_1|\le d\ln\left(\frac{en_1}{d}\right). ln ∣ C 1 ∣ ≤ d ln ( d e n 1 ) .
Therefore,
∣ S 2 ∣ ≥ n 2 ≥ 2 a 1 ( ( ln ( 4 ∣ C 1 ∣ / δ ) ) 2 / 3 K 1 / 3 + ln ( 4 ∣ C 1 ∣ / δ ) ) ε . |S_2|\ge n_2\ge\frac{2a_1\left((\ln(4|\mathcal{C}_1|/\delta))^{2/3}K^{1/3}+\ln(4|\mathcal{C}_1|/\delta)\right)}{\varepsilon}. ∣ S 2 ∣ ≥ n 2 ≥ ε 2 a 1 ( ( ln ( 4∣ C 1 ∣/ δ ) ) 2/3 K 1/3 + ln ( 4∣ C 1 ∣/ δ ) ) .
Using Theorem B.2 for finite class C 1 \mathcal{C}_1 C 1 with accuracy parameter ε / 2 \varepsilon/2 ε /2 and confidence parameter δ / 2 \delta/2 δ /2 , with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 we have
L D ( A S ) ≤ inf h ′ ∈ C 1 L D ( h ′ ) + ε / 2. L_{\mathcal{D}}(A_{S})\le\inf_{h'\in\mathcal{C}_1}L_{\mathcal{D}}(h')+\varepsilon/2. L D ( A S ) ≤ h ′ ∈ C 1 inf L D ( h ′ ) + ε /2.
Combining with Equation (9) completes the proof.
Combining our results with the O ( K ln ( 1 / ε ) + ln ( 1 / δ ) ε ) O\left(\frac{K\ln(1/\varepsilon)+\ln(1/\delta)}{\varepsilon}\right) O ( ε K l n ( 1/ ε ) + l n ( 1/ δ ) ) upper bound of Ben-David et al. [ [8 ] for agnostic PAC learning with deterministic labels for concept classes of diameter K K K , we immediately obtain the following corollary.
Corollary B.6. Let K , d ∈ N K,d\in\mathbb{N} K , d ∈ N . There exists a universal constant a 3 > 0 a_3>0 a 3 > 0 such that every concept class such that VC ( C ) ≤ d \operatorname{VC}(\mathcal{C})\le d VC ( C ) ≤ d where D ( C ) ≤ K D(\mathcal{C})\le K D ( C ) ≤ K , is agnostic PAC learnable with deterministic labels with sample complexity upper bounded by
m C ( ε , δ ) ≤ O ( ( ( d ln ( 1 / ε ) + ln ( 1 / δ ) ) 2 / 3 K 1 / 3 + d ln ( 1 / ε ) ) ∧ K ln ( 1 / ε ) + ln ( 1 / δ ) ε ) . m_{\mathcal{C}}(\varepsilon,\delta)\le O\left(\frac{\left((d\ln(1/\varepsilon)+\ln(1/\delta))^{2/3}K^{1/3}+d\ln(1/\varepsilon)\right)\wedge K\ln(1/\varepsilon)+\ln(1/\delta)}{\varepsilon}\right). m C ( ε , δ ) ≤ O ( ε ( ( d ln ( 1/ ε ) + ln ( 1/ δ ) ) 2/3 K 1/3 + d ln ( 1/ ε ) ) ∧ K ln ( 1/ ε ) + ln ( 1/ δ ) ) .
Lower Bounds
In this section, we first introduce the additional information-theoretic notation used in the lower-bound arguments in subsection C.1. We then prove our lower bounds for agnostic PAC learning under deterministic labels in subsection C.3.
In this subsection, we collect a few standard information-theoretic notions and definitions used in the lower-bound proofs. Let P P P and Q Q Q be two probability measures on a common measurable space. If P P P is absolutely continuous with respect to Q Q Q , we define the Kullback–Leibler divergence from P P P to Q Q Q by
D K L ( P ∥ Q ) : = ∫ log ( d P d Q ) d P . D_{\mathrm{KL}}(P\|Q):=\int\log\left(\frac{dP}{dQ}\right)\,dP. D KL ( P ∥ Q ) := ∫ log ( d Q d P ) d P .
If P P P is not absolutely continuous with respect to Q Q Q , we set
D K L ( P ∥ Q ) : = + ∞ . D_{\mathrm{KL}}(P\|Q) := +\infty. D KL ( P ∥ Q ) := + ∞.
Next, let X X X and Y Y Y be random variables defined on a common probability space. We define the mutual information between X X X and Y Y Y by
I ( X ; Y ) : = D K L ( P X , Y ∥ P X ⊗ P Y ) , I(X;Y) := D_{\mathrm{KL}}(P_{X,Y}\|P_X \otimes P_Y), I ( X ; Y ) := D KL ( P X , Y ∥ P X ⊗ P Y ) ,
where P X , Y P_{X,Y} P X , Y denotes the joint distribution of ( X , Y ) (X,Y) ( X , Y ) , and P X P_X P X and P Y P_Y P Y denote the marginal distributions of X X X and Y Y Y , respectively.
Finally, for p ∈ [ 0 , 1 ] p \in[0,1] p ∈ [ 0 , 1 ] , we denote by B ( p ) \mathrm{B}(p) B ( p ) the Bernoulli distribution with parameter p p p . That is, if Z ∼ B ( p ) Z \sim\mathrm{B}(p) Z ∼ B ( p ) , then
P [ Z = 1 ] = p and P [ Z = 0 ] = 1 − p . \mathbb{P}[Z=1] = p \qquad\text{and} \qquad\mathbb{P}[Z=0] = 1-p. P [ Z = 1 ] = p and P [ Z = 0 ] = 1 − p .
Detailed Technical Overview of Lower Bounds
The principal difficulty is that, under deterministic labels, observing a point reveals its label. In particular, repeated occurrences of the same point provide no additional evidence about its label that can be exploited in a lower bound construction. Consequently, the hardness must be concentrated on a sufficiently large collection of points that remain unseen by the learner, who is unsure of their labels.
Both proofs place a small total probability mass q q q uniformly over k k k points and place the remaining mass on an anchor point at which the relevant concepts agree. The labels of the rare points are generated using slightly biased coins with a bias magnitude γ \gamma γ , but each label is sampled only once and is then fixed. Thus, every realization of the construction defines a genuinely deterministically labeled distribution. The randomization is used only as an auxiliary device in the lower bound argument, and a final application of the probabilistic method fixes one deterministic labeling on which the learner fails.
The parameters q q q and γ \gamma γ play complementary roles. The total mass of the rare region q q q controls its importance, while γ \gamma γ controls the advantage of the concept aligned with the hidden bias. We choose q γ = C 2 ϵ q\gamma= C_2\epsilon q γ = C 2 ϵ for a sufficiently large universal constant C 2 C_2 C 2 , so that predicting in the wrong biased direction on a constant fraction of the unseen rare points creates an excess error of order q γ q\gamma q γ that is larger than ϵ \epsilon ϵ .
The proof must then balance two requirements. First, sufficiently many rare points must remain unseen. More specifically, let M M M denote the number of distinct rare points observed in the sample. Since the learner may memorize the labels of these points, the excess error gap resulting from the relevant estimation error—an incorrect hidden sign in Lemma D or errors on a constant fraction of the hidden coordinates in Lemma C.2 —has, schematically, the form
Ω ( q γ ) − O ( q M k ) . \Omega(q\gamma)-O\left(\frac{qM}{k}\right). Ω ( q γ ) − O ( k q M ) .
Therefore, to preserve a gap of order q γ q\gamma q γ , we require M ∈ O ( γ k ) M \in O(\gamma k) M ∈ O ( γ k ) . The quantity M M M is at most the number of samples falling in the rare region, whose expectation is n q nq n q . Thus, imposing
n q ≲ γ k nq \lesssim\gamma k n q ≲ γ k
allows the corresponding concentration argument in each proof to ensure that M ∈ O ( γ k ) M \in O(\gamma k) M ∈ O ( γ k ) holds with the required probability. Using q = C 2 ϵ / γ q=C_2\epsilon/\gamma q = C 2 ϵ / γ , this becomes
n ϵ γ ≲ γ k , \frac{n\epsilon}{\gamma} \lesssim\gamma k, γ n ϵ ≲ γ k ,
or equivalently,
n ≲ k γ 2 ϵ . n \lesssim\frac{k\gamma^2}{\epsilon}. n ≲ ϵ k γ 2 .
Second, the sample must contain insufficient information to estimate the hidden parameter. Each distinct observed rare point contributes only O ( γ 2 ) O(\gamma^2) O ( γ 2 ) to the relevant information quantity—KL divergence in Lemma C.1 and mutual information in Lemma C.2 . Since the expected number of distinct observed rare points is at most n q nq n q , this information quantity is at most
O ( n q γ 2 ) = O ( n ϵ ) . O(nq\gamma^2)=O(n\epsilon). O ( n q γ 2 ) = O ( n ϵ ) .
To keep the corresponding estimation problem hard, we require
n ϵ γ ≲ B , n\epsilon\gamma\lesssim B, n ϵ γ ≲ B ,
or equivalently,
n ≲ B ϵ γ , n \lesssim\frac{B}{\epsilon\gamma}, n ≲ ϵ γ B ,
where B B B is the relevant information budget. These two constraints can be summarized as
n ≲ min { B ϵ γ , k γ 2 ϵ } . n \lesssim\min\left\{\frac{B}{\epsilon\gamma},\frac{k\gamma^2}{\epsilon}\right\}. n ≲ min { ϵ γ B , ϵ k γ 2 } .
Balancing the two terms gives
γ ≃ ( B k ) 1 / 3 , n ≲ k 1 / 3 B 2 / 3 ϵ . \gamma\simeq\left(\frac{B}{k}\right)^{1/3}, \qquad n \lesssim\frac{k^{1/3}B^{2/3}}{\epsilon}. γ ≃ ( k B ) 1/3 , n ≲ ϵ k 1/3 B 2/3 .
The two lower bounds instantiate this common mechanism with different hidden parameters and information budgets. In the principal regime log ( 1 / δ ) ≲ k \log(1/\delta) \lesssim k log ( 1/ δ ) ≲ k of Lemma C.1, the hidden parameter is a single sign and the relevant information budget is B = log ( 1 / δ ) B = \log(1/\delta) B = log ( 1/ δ ) ; a binary testing argument then yields the diameter-confidence term
k 1 / 3 log 2 / 3 ( 1 / δ ) ϵ . \frac{k^{1/3}\log^{2/3}(1/\delta)}{\epsilon}. ϵ k 1/3 log 2/3 ( 1/ δ ) .
The complementary regime and the additional confidence term are handled using the standard realizable PAC lower bound. In Lemma C.2 , the k k k rare points are partitioned into d d d blocks, the hidden parameter is a d d d -dimensional sign vector, and the relevant information budget is B = d B = d B = d ; this yields the joint dependence
k 1 / 3 d 2 / 3 ϵ . \frac{k^{1/3}d^{2/3}}{\epsilon}. ϵ k 1/3 d 2/3 .
Proof of the Lower Bounds
Theorem C.1 (Lower bound based on diameter with confidence parameter). There exist universal constants a , a 0 , δ 0 > 0 a, a_0, \delta_0 > 0 a , a 0 , δ 0 > 0 , and k 0 ∈ N k_0 \in\mathbb{N} k 0 ∈ N such that the following holds. Let k ≥ k 0 k \ge k_0 k ≥ k 0 , and let C ⊆ Y X C \subseteq\mathcal{Y}^{\mathcal{X}} C ⊆ Y X be a concept class. Assume that there exist two concepts h 0 , h 1 ∈ C h^0, h^1 \in C h 0 , h 1 ∈ C and distinct points
x 0 , x 1 , … , x k ∈ X x_0,x_1,\ldots,x_k \in\mathcal{X} x 0 , x 1 , … , x k ∈ X such that { x i } ∈ Σ X \{x_i\} \in\Sigma_{\mathcal{X}} { x i } ∈ Σ X for every i ∈ { 0 , 1 , … , k } i \in\{0,1,\ldots,k\} i ∈ { 0 , 1 , … , k } , and
h 0 ( x 0 ) = h 1 ( x 0 ) , h 0 ( x i ) ≠ h 1 ( x i ) for every i ∈ [ k ] . h^0(x_0)=h^1(x_0), \qquad h^0(x_i)\ne h^1(x_i)\ \text{for every } i\in[k]. h 0 ( x 0 ) = h 1 ( x 0 ) , h 0 ( x i ) = h 1 ( x i ) for every i ∈ [ k ] . Then, for every δ ∈ ( 0 , δ 0 ] \delta\in(0,\delta_0] δ ∈ ( 0 , δ 0 ] , writing
r δ : = log ( 1 δ ) and r δ , k : = r δ ∧ k , r_\delta:= \log\left(\frac{1}{\delta}\right) \qquad\text{and}\qquad r_{\delta,k}:=r_\delta\wedge k, r δ := log ( δ 1 ) and r δ , k := r δ ∧ k , and for every
ϵ ∈ ( 0 , a 0 ( r δ , k k ) 1 / 3 ] , \epsilon\in\left(0,a_0\left(\frac{r_{\delta,k}}{k}\right)^{1/3}\right], ϵ ∈ ( 0 , a 0 ( k r δ , k ) 1/3 ] , the optimal sample complexity of agnostic PAC learning C C C with deterministic labels satisfies
m C ( ϵ , δ ) ≥ a ( k 1 / 3 r δ , k 2 / 3 ϵ + r δ ϵ ) . m_C(\epsilon,\delta)\ge a\left(\frac{k^{1/3}r_{\delta,k}^{2/3}}{\epsilon}+\frac{r_\delta}{\epsilon}\right). m C ( ϵ , δ ) ≥ a ( ϵ k 1/3 r δ , k 2/3 + ϵ r δ ) .
Proof. Throughout the proof, all constants are universal, and we decrease a a a , a 0 a_0 a 0 , δ 0 \delta_0 δ 0 and increase k 0 k_0 k 0 whenever needed. As we defined in subsection 2.1, log ( ⋅ ) \log(\cdot) log ( ⋅ ) is in base 2, while some standard inequalities below are naturally written with base e. Indeed, changing between the two bases only changes universal constants. In addition, for a data distribution D \mathcal{D} D , define opt C ( D ) \operatorname{opt}_{\mathcal{C}}(\mathcal{D}) opt C ( D ) as
opt C ( D ) : = inf h ∈ C L D ( h ) . \operatorname{opt}_{\mathcal{C}}(\mathcal{D}) := \inf_{h \in\mathcal{C}} \mathcal{L}_{\mathcal{D}}(h). opt C ( D ) := h ∈ C inf L D ( h ) .
The main claim is that if r δ ≤ a 1 k r_{\delta} \le a_{1}k r δ ≤ a 1 k for some constant a 1 > 0 a_{1} > 0 a 1 > 0 , then we have
m C ( ε , δ ) ≥ a k 1 / 3 r δ 2 / 3 ε . m_{\mathcal{C}}(\varepsilon,\delta) \ge a \frac{k^{1/3}r_{\delta}^{2/3}}{\varepsilon}. m C ( ε , δ ) ≥ a ε k 1/3 r δ 2/3 .
Set
γ : = C 1 ( r δ k ) 1 / 3 , \gamma:= C_{1}\left(\frac{r_{\delta}}{k}\right)^{1/3}, γ := C 1 ( k r δ ) 1/3 ,
where C 1 > 0 C_{1} > 0 C 1 > 0 is a sufficiently large universal constant. By taking a 1 > 0 a_{1} > 0 a 1 > 0 sufficiently small, we may assume 0 < γ ≤ 1 8 0 < \gamma\le\frac{1}{8} 0 < γ ≤ 8 1 . Next, set
q : = C 2 ε γ , q := \frac{C_{2}\varepsilon}{\gamma}, q := γ C 2 ε ,
where C 2 > 0 C_{2} > 0 C 2 > 0 is another sufficiently large universal constant. By taking a 0 > 0 a_{0} > 0 a 0 > 0 sufficiently small, the assumption ε ≤ a 0 ( r δ / k ) 1 / 3 \varepsilon\le a_{0}(r_{\delta}/k)^{1/3} ε ≤ a 0 ( r δ / k ) 1/3 implies that 0 < q ≤ 1 2 0 < q \le\frac{1}{2} 0 < q ≤ 2 1 .
Define a marginal distribution μ \mu μ over X \mathcal{X} X by
μ ( x 0 ) : = 1 − q , and μ ( x i ) : = q k for every i ∈ [ k ] . \mu(x_{0}) := 1-q,\qquad\text{and}\qquad\mu(x_{i}) := \frac{q}{k}\ \text{ for every } i \in[k]. μ ( x 0 ) := 1 − q , and μ ( x i ) := k q for every i ∈ [ k ] .
Let the random variable σ \sigma σ be uniformly distributed over { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } . Conditional on σ \sigma σ , let Z 1 , Z 2 , … , Z k Z_{1},Z_{2},\ldots,Z_{k} Z 1 , Z 2 , … , Z k be independent Bernoulli random variables satisfying
P [ Z i = 1 ∣ σ = + 1 ] = 1 2 + γ , and P [ Z i = 1 ∣ σ = − 1 ] = 1 2 − γ . \mathbb{P}[Z_{i}=1\mid\sigma=+1] = \frac{1}{2}+\gamma,\qquad\text{and}\qquad\mathbb{P}[Z_{i}=1\mid\sigma=-1] = \frac{1}{2}-\gamma. P [ Z i = 1 ∣ σ = + 1 ] = 2 1 + γ , and P [ Z i = 1 ∣ σ = − 1 ] = 2 1 − γ .
For each realization of ( σ , Z 1 , Z 2 , … , Z k ) (\sigma,Z_{1},Z_{2},\ldots,Z_{k}) ( σ , Z 1 , Z 2 , … , Z k ) , define a deterministic labeling function f σ , Z : X → Y f_{\sigma,Z}:\mathcal{X}\to\mathcal{Y} f σ , Z : X → Y by
f σ , Z ( x 0 ) : = h 0 ( x 0 ) = h 1 ( x 0 ) , and f σ , Z ( x i ) : = h Z i ( x i ) for every i ∈ [ k ] . f_{\sigma,Z}(x_{0}) := h^{0}(x_{0}) = h^{1}(x_{0}),\qquad\text{and}\qquad f_{\sigma,Z}(x_{i}) := h^{Z_{i}}(x_{i})\ \text{ for every } i \in[k]. f σ , Z ( x 0 ) := h 0 ( x 0 ) = h 1 ( x 0 ) , and f σ , Z ( x i ) := h Z i ( x i ) for every i ∈ [ k ] .
and define f σ , Z f_{\sigma,Z} f σ , Z arbitrarily outside { x 0 , x 1 , … , x k } \{x_{0},x_{1},\ldots,x_{k}\} { x 0 , x 1 , … , x k } , for example by setting it equal to h 0 h^{0} h 0 there. Since singletons { x i } \{x_{i}\} { x i } are measurable, f σ , Z f_{\sigma,Z} f σ , Z is measurable.
Now, for each realization of ( σ , Z 1 , Z 2 , … , Z k ) (\sigma,Z_{1},Z_{2},\ldots,Z_{k}) ( σ , Z 1 , Z 2 , … , Z k ) , let D σ , Z \mathcal{D}_{\sigma,Z} D σ , Z be the distribution of
( x , f σ , Z ( x ) ) , (x,f_{\sigma,Z}(x)), ( x , f σ , Z ( x )) ,
where x ∼ μ x \sim\mu x ∼ μ . Indeed, D σ , Z \mathcal{D}_{\sigma,Z} D σ , Z is deterministically labeled Definition 2.1 .
Subsequently, fix a sample size n n n that satisfies
n ≤ a k 1 / 3 r δ 2 / 3 ε . n \le a\frac{k^{1/3}r_{\delta}^{2/3}}{\varepsilon}. n ≤ a ε k 1/3 r δ 2/3 .
Let P + P_{+} P + and P − P_{-} P − denote the laws of the sample S ∼ D σ , Z n S \sim\mathcal{D}_{\sigma,Z}^{n} S ∼ D σ , Z n , averaged over Z Z Z , conditional on σ = + 1 \sigma=+1 σ = + 1 and σ = − 1 \sigma=-1 σ = − 1 , respectively. Let I = ( X 1 , X 2 , … , X n ) I=(X_{1},X_{2},\ldots,X_{n}) I = ( X 1 , X 2 , … , X n ) denote the sequence of sampled instances and let Y = ( Y 1 , Y 2 , … , Y n ) Y=(Y_{1},Y_{2},\ldots,Y_{n}) Y = ( Y 1 , Y 2 , … , Y n ) denote the corresponding sequence of labels. Now, by the chain rule for relative entropy, we have
D K L ( P + ∥ P − ) = D K L ( P + I ∥ P − I ) + E I ∼ P + I [ D K L ( P + Y ∣ I ∥ P − Y ∣ I ) ] . D_{\mathrm{KL}}(P_{+}\Vert P_{-}) = D_{\mathrm{KL}}(P_{+}^{I}\Vert P_{-}^{I}) + \mathbb{E}_{I\sim P_{+}^{I}}\left[D_{\mathrm{KL}}\left(P_{+}^{Y\mid I}\Vert P_{-}^{Y\mid I}\right)\right]. D KL ( P + ∥ P − ) = D KL ( P + I ∥ P − I ) + E I ∼ P + I [ D KL ( P + Y ∣ I ∥ P − Y ∣ I ) ] .
where P ± I P_{\pm}^{I} P ± I denote the marginals of P ± P_{\pm} P ± on the instance sequence, and P ± Y ∣ I P_{\pm}^{Y\mid I} P ± Y ∣ I denote the corresponding conditional laws of the label sequence given the instance sequence. Since the marginal distribution of the sampled instances does not depend on Z Z Z , we have D K L ( P + I ∥ P − I ) = 0 D_{\mathrm{KL}}(P_{+}^{I}\Vert P_{-}^{I})=0 D KL ( P + I ∥ P − I ) = 0 . Therefore,
D K L ( P + ∥ P − ) = E I ∼ P + I [ D K L ( P + Y ∣ I ∥ P − Y ∣ I ) ] . D_{\mathrm{KL}}(P_{+}\Vert P_{-}) = \mathbb{E}_{I\sim P_{+}^{I}}\left[D_{\mathrm{KL}}\left(P_{+}^{Y\mid I}\Vert P_{-}^{Y\mid I}\right)\right]. D KL ( P + ∥ P − ) = E I ∼ P + I [ D KL ( P + Y ∣ I ∥ P − Y ∣ I ) ] .
Now, fix a realization of I I I . Let D ( I ) D(I) D ( I ) be the number of distinct points among x 1 , x 2 , … , x k x_1,x_2,\ldots,x_k x 1 , x 2 , … , x k that appear in I I I . Conditional on I I I , only these D ( I ) D(I) D ( I ) points can contribute to the relative entropy between the two conditional label distributions. Moreover, repeated appearances of the same point do not contribute additional independent information, because the label of each point is deterministic once Z Z Z is fixed. Therefore, we have
D K L ( P + Y ∣ I ∥ P − Y ∣ I ) ≤ D ( I ) D K L ( B ( 1 2 + γ ) ∥ B ( 1 2 − γ ) ) . D_{\mathrm{KL}}\left(P_{+}^{Y\mid I}\mathbin{\|}P_{-}^{Y\mid I}\right)\leq D(I)D_{\mathrm{KL}}\left(\mathrm{B}\left(\frac{1}{2}+\gamma\right)\mathbin{\|}\mathrm{B}\left(\frac{1}{2}-\gamma\right)\right). D KL ( P + Y ∣ I ∥ P − Y ∣ I ) ≤ D ( I ) D KL ( B ( 2 1 + γ ) ∥ B ( 2 1 − γ ) ) .
Note that, for γ ≤ 1 / 8 \gamma\leq1/8 γ ≤ 1/8 , we have
D K L ( B ( 1 2 + γ ) ∥ B ( 1 2 − γ ) ) ≤ 16 γ 2 . D_{\mathrm{KL}}\left(\mathrm{B}\left(\frac{1}{2}+\gamma\right)\mathbin{\|}\mathrm{B}\left(\frac{1}{2}-\gamma\right)\right)\leq16\gamma^2. D KL ( B ( 2 1 + γ ) ∥ B ( 2 1 − γ ) ) ≤ 16 γ 2 .
Thus, we have
D K L ( P + ∥ P − ) ≤ 16 γ 2 E I ∼ P I + [ D ( I ) ] . D_{\mathrm{KL}}(P_+\mathbin{\|}P_-)\leq16\gamma^2\mathbb{E}_{I\sim P_I^+}[D(I)]. D KL ( P + ∥ P − ) ≤ 16 γ 2 E I ∼ P I + [ D ( I )] .
Finally, D ( I ) ≤ N D(I)\leq N D ( I ) ≤ N , where N N N is the total number of sampled points falling in { x 1 , x 2 , … , x k } \{x_1,x_2,\ldots,x_k\} { x 1 , x 2 , … , x k } . Since N ∼ Bin ( n , q ) N\sim\operatorname{Bin}(n,q) N ∼ Bin ( n , q ) , we have E [ D ( I ) ] ≤ E [ N ] = n q \mathbb{E}[D(I)]\leq\mathbb{E}[N]=nq E [ D ( I )] ≤ E [ N ] = n q . Therefore, we get
D K L ( P + ∥ P − ) ≤ 16 n q γ 2 . D_{\mathrm{KL}}(P_+\mathbin{\|}P_-)\leq16nq\gamma^2. D KL ( P + ∥ P − ) ≤ 16 n q γ 2 .
Now, using q = C 2 ε / γ q=C_2\varepsilon/\gamma q = C 2 ε / γ and the upper bound on n n n , we obtain
D K L ( P + ∥ P − ) ≤ 16 C 1 C 2 a r δ . D_{\mathrm{KL}}(P_+\mathbin{\|}P_-)\leq16C_1C_2ar_\delta. D KL ( P + ∥ P − ) ≤ 16 C 1 C 2 a r δ .
Taking a > 0 a>0 a > 0 sufficiently small, the Bretagnolle–Huber inequality implies that every estimator σ ^ = σ ^ ( S ) \widehat{\sigma}=\widehat{\sigma}(S) σ = σ ( S ) satisfies
P [ σ ^ ≠ σ ] ≥ 8 δ , \mathbb{P}[\widehat{\sigma}\ne\sigma]\geq8\delta, P [ σ = σ ] ≥ 8 δ ,
where the probability is over σ \sigma σ , Z Z Z , and the sample S S S .
③ Next, fix a deterministic PAC learning algorithm A A A . Now, we construct an estimator from the learner. For a sample S S S , define
I ( S ) : = { i ∈ [ k ] ∣ x i appears in S } , U ( S ) : = [ k ] ∖ I ( S ) , I(S):=\{i\in[k]\mid x_i\text{ appears in }S\},\qquad U(S):=[k]\setminus I(S), I ( S ) := { i ∈ [ k ] ∣ x i appears in S } , U ( S ) := [ k ] ∖ I ( S ) ,
and let M ( S ) : = ∣ I ( S ) ∣ M(S):=|I(S)| M ( S ) := ∣ I ( S ) ∣ . If
M ( S ) > γ k 16 , M(S)>\frac{\gamma k}{16}, M ( S ) > 16 γ k ,
let σ ^ \widehat{\sigma} σ be arbitrary. Otherwise, define σ ^ \widehat{\sigma} σ as follows
σ ^ ( S ) : = { + 1 , ∣ { i ∈ U ( S ) ∣ A S ( x i ) = h 1 ( x i ) } ∣ ≥ ∣ U ( S ) ∣ / 2 , − 1 , otherwise . \widehat{\sigma}(S):=
\begin{cases}
+1, & \left|\{i\in U(S)\mid A_S(x_i)=h^1(x_i)\}\right|\geq|U(S)|/2,\\
-1, & \text{otherwise}.
\end{cases} σ ( S ) := { + 1 , − 1 , { i ∈ U ( S ) ∣ A S ( x i ) = h 1 ( x i )} ≥ ∣ U ( S ) ∣/2 , otherwise .
Thus, in words, σ ^ \widehat{\sigma} σ is the majority vote of the learner’s predictions on the unseen points.
④ We next show that if σ ^ \widehat{\sigma} σ is wrong, then the learner has excess error larger than ε \varepsilon ε , except on an event of probability at most 3 δ 3\delta 3 δ .
First , let N N N be the total number of sample points falling in { x 1 , x 2 , … , x k } \{x_1,x_2,\ldots,x_k\} { x 1 , x 2 , … , x k } . So, we have: N ∼ Bin ( n , q ) N\sim\operatorname{Bin}(n,q) N ∼ Bin ( n , q ) . Hence, we obtain
E [ N ] = n q ≤ a ⋅ k 1 / 3 r δ 2 / 3 ε ⋅ C 2 ε γ = a C 2 C 1 k 2 / 3 r δ 1 / 3 . \mathbb{E}[N]=nq\leq a\cdot\frac{k^{1/3}r_\delta^{2/3}}{\varepsilon}\cdot\frac{C_2\varepsilon}{\gamma}=\frac{aC_2}{C_1}k^{2/3}r_\delta^{1/3}. E [ N ] = n q ≤ a ⋅ ε k 1/3 r δ 2/3 ⋅ γ C 2 ε = C 1 a C 2 k 2/3 r δ 1/3 .
On the other hand, we have:
γ k 16 = C 1 16 k 2 / 3 r δ 1 / 3 . \frac{\gamma k}{16}=\frac{C_1}{16}k^{2/3}r_\delta^{1/3}. 16 γ k = 16 C 1 k 2/3 r δ 1/3 .
Taking a > 0 a>0 a > 0 sufficiently small and noticing that M ( S ) ≤ N M(S)\leq N M ( S ) ≤ N , a Chernoff bound gives
P [ M ( S ) > γ k 16 ] ≤ δ . \mathbb{P}\left[M(S)>\frac{\gamma k}{16}\right]\leq\delta. P [ M ( S ) > 16 γ k ] ≤ δ .
Second , define h σ h^\sigma h σ as follows.
h σ : = { h 1 , σ = + 1 , h 0 , σ = − 1. h^\sigma:= \begin{cases} h^1, & \sigma=+1, \\ h^0, & \sigma=-1. \end{cases} h σ := { h 1 , h 0 , σ = + 1 , σ = − 1.
For every i ∈ [ k ] i \in[k] i ∈ [ k ] , the concept h σ h^\sigma h σ disagrees with f σ , Z f_{\sigma,Z} f σ , Z at x i x_i x i with probability 1 / 2 − γ 1/2-\gamma 1/2 − γ . Therefore, we have:
∣ { i ∈ [ k ] ∣ h σ ( x i ) ≠ f σ , Z ( x i ) } ∣ ∼ Bin ( k , 1 2 − γ ) . \left|\left\{i \in[k] \mid h^\sigma(x_i) \ne f_{\sigma,Z}(x_i)\right\}\right| \sim\operatorname{Bin}\left(k,\frac{1}{2}-\gamma\right). ∣ { i ∈ [ k ] ∣ h σ ( x i ) = f σ , Z ( x i ) } ∣ ∼ Bin ( k , 2 1 − γ ) .
Since h σ ∈ C h^\sigma\in C h σ ∈ C , Hoeffding’s inequality gives
P [ opt C ( D σ , Z ) > q ( 1 2 − 3 γ 4 ) ] ≤ exp ( − k γ 2 8 ) ≤ δ , \mathbb{P}\left[\operatorname{opt}_C(\mathcal{D}_{\sigma,Z}) > q\left(\frac{1}{2}-\frac{3\gamma}{4}\right)\right] \le\exp\left(-\frac{k\gamma^2}{8}\right) \le\delta, P [ opt C ( D σ , Z ) > q ( 2 1 − 4 3 γ ) ] ≤ exp ( − 8 k γ 2 ) ≤ δ ,
where the last inequality follows from the definition of γ \gamma γ and from choosing C 1 C_1 C 1 large enough and a 1 a_1 a 1 small enough.
Third , condition on σ \sigma σ and on a sample S S S satisfying
M ( S ) ≤ γ k 16 and σ ^ ( S ) ≠ σ . M(S) \le\frac{\gamma k}{16}
\qquad\text{and}\qquad
\widehat{\sigma}(S) \ne\sigma. M ( S ) ≤ 16 γ k and σ ( S ) = σ .
Then, on at least half of the unseen indices i ∈ U ( S ) i \in U(S) i ∈ U ( S ) , the learner predicts the minority label relative to σ \sigma σ . Condition on σ \sigma σ and S S S , the labels on the unseen points remain independent. Hence, the expected loss contribution from unseen points is at least
q ( 1 − γ 16 ) 1 2 . q\left(1-\frac{\gamma}{16}\right)\frac{1}{2}. q ( 1 − 16 γ ) 2 1 .
As a result, by Hoeffding’s inequality,
P [ q k ∑ i ∈ U ( S ) 1 [ A S ( x i ) ≠ f σ , Z ( x i ) ] < q ( 1 − γ 16 ) 1 2 − q γ 8 ∣ σ , S ] ≤ exp ( − c k γ 2 ) ≤ δ , \mathbb{P}\left[\left.\frac{q}{k}\sum_{i\in U(S)}\mathbf{1}[A_S(x_i)\ne f_{\sigma,Z}(x_i)] < q\left(1-\frac{\gamma}{16}\right)\frac{1}{2}-\frac{q\gamma}{8}\,\right|\,\sigma,S\right] \le\exp(-c k\gamma^2)\le\delta, P k q i ∈ U ( S ) ∑ 1 [ A S ( x i ) = f σ , Z ( x i )] < q ( 1 − 16 γ ) 2 1 − 8 q γ σ , S ≤ exp ( − c k γ 2 ) ≤ δ ,
for a universal constant c > 0 c>0 c > 0 , again by the choice of C 1 C_1 C 1 and a 1 a_1 a 1 .
Therefore , except on an event of probability at most 3 δ 3\delta 3 δ , whenever σ ^ ( S ) ≠ σ \widehat{\sigma}(S)\ne\sigma σ ( S ) = σ , we have
L D σ , Z ( A S ) − opt C ( D σ , Z ) ≥ q ( 1 − γ 16 ) 1 2 − q γ 8 − q ( 1 2 − 3 γ 4 ) = q γ ( 3 4 − 1 32 − 1 8 ) = 19 32 q γ . \begin{aligned}
\mathcal{L}_{\mathcal{D}_{\sigma,Z}}(A_S)-\operatorname{opt}_C(\mathcal{D}_{\sigma,Z})
\ge q\left(1-\frac{\gamma}{16}\right)\frac{1}{2}-\frac{q\gamma}{8}-q\left(\frac{1}{2}-\frac{3\gamma}{4}\right) \\
&= q\gamma\left(\frac{3}{4}-\frac{1}{32}-\frac{1}{8}\right) \\
&= \frac{19}{32}q\gamma.
\end{aligned} L D σ , Z ( A S ) − opt C ( D σ , Z ) ≥ q ( 1 − 16 γ ) 2 1 − 8 q γ − q ( 2 1 − 4 3 γ ) = q γ ( 4 3 − 32 1 − 8 1 ) = 32 19 q γ .
Since q γ = C 2 ε q\gamma=C_2\varepsilon q γ = C 2 ε and C 2 C_2 C 2 is a sufficiently large universal constant, the last expression is larger than ε \varepsilon ε . Thus, we have:
{ σ ^ ( S ) ≠ σ } ⊆ { L D σ , Z ( A S ) > opt C ( D σ , Z ) + ε } ∪ B , \left\{\widehat{\sigma}(S)\ne\sigma\right\}\subseteq\left\{\mathcal{L}_{\mathcal{D}_{\sigma,Z}}(A_S)>\operatorname{opt}_C(\mathcal{D}_{\sigma,Z})+\varepsilon\right\}\cup\mathcal{B}, { σ ( S ) = σ } ⊆ { L D σ , Z ( A S ) > opt C ( D σ , Z ) + ε } ∪ B ,
where P [ B ] ≤ 3 δ \mathbb{P}[\mathcal{B}]\le3\delta P [ B ] ≤ 3 δ .
⑤ Afterward, combining the above result with the testing lower bound, namely (C.3), gives
P σ , Z , S [ L D σ , Z ( A S ) > opt C ( D σ , Z ) + ε ] ≥ P [ σ ^ ≠ σ ] − 3 δ ≥ 5 δ . \mathbb{P}_{\sigma,Z,S}\left[\mathcal{L}_{\mathcal{D}_{\sigma,Z}}(A_S)>\operatorname{opt}_C(\mathcal{D}_{\sigma,Z})+\varepsilon\right]\ge\mathbb{P}[\widehat{\sigma}\ne\sigma]-3\delta\ge5\delta. P σ , Z , S [ L D σ , Z ( A S ) > opt C ( D σ , Z ) + ε ] ≥ P [ σ = σ ] − 3 δ ≥ 5 δ .
Now, we apply the probabilistic method. In particular, by averaging over ( σ , Z ) (\sigma,Z) ( σ , Z ) , there exists a fixed deterministic labeling f σ , Z f_{\sigma,Z} f σ , Z such that
P S ∼ D σ , Z n [ L D σ , Z ( A S ) > opt C ( D σ , Z ) + ε ] > δ . \mathbb{P}_{S\sim\mathcal{D}_{\sigma,Z}^{n}}\left[\mathcal{L}_{\mathcal{D}_{\sigma,Z}}(A_S)>\operatorname{opt}_C(\mathcal{D}_{\sigma,Z})+\varepsilon\right]>\delta. P S ∼ D σ , Z n [ L D σ , Z ( A S ) > opt C ( D σ , Z ) + ε ] > δ .
Since A A A was arbitrary, no algorithm using
n ≤ a k 1 / 3 r δ 2 / 3 ε n\le a\frac{k^{1/3}r_\delta^{2/3}}{\varepsilon} n ≤ a ε k 1/3 r δ 2/3
samples can satisfy the agnostic PAC learning with deterministic labels guarantee with confidence 1 − δ 1-\delta 1 − δ . Hence, whenever r δ ≤ a 1 k r_{\delta} \leq a_{1}k r δ ≤ a 1 k , we have:
m C ( ε , δ ) ≥ a k 1 / 3 r δ 2 / 3 ε . (10) m_{\mathcal{C}}(\varepsilon,\delta) \geq a\frac{k^{1/3}r_{\delta}^{2/3}}{\varepsilon}. \tag*{(10)} m C ( ε , δ ) ≥ a ε k 1/3 r δ 2/3 . (10)
⑥ Finally, if r δ ≤ a 1 k r_{\delta} \leq a_{1}k r δ ≤ a 1 k , using (10) combined with the standard realizable PAC learning lower bound Ehrenfeucht et al. [ [22 ] , we get
m C ( ε , δ ) ≥ a ( k 1 / 3 r δ 2 / 3 ε + r δ ε ) , m_{\mathcal{C}}(\varepsilon,\delta) \geq a\left(\frac{k^{1/3}r_{\delta}^{2/3}}{\varepsilon}+\frac{r_{\delta}}{\varepsilon}\right), m C ( ε , δ ) ≥ a ( ε k 1/3 r δ 2/3 + ε r δ ) ,
after decreasing a a a by a universal factor.
Now, if r δ > a 1 k r_{\delta} > a_{1}k r δ > a 1 k , again using the standard PAC learning lower bound Ehrenfeucht et al. [ [22 ] , we get
m C ( ε , δ ) ≥ a r δ ε . m_{\mathcal{C}}(\varepsilon,\delta) \geq a\frac{r_{\delta}}{\varepsilon}. m C ( ε , δ ) ≥ a ε r δ .
Since r δ > a 1 k r_{\delta} > a_{1}k r δ > a 1 k , we have
k 1 / 3 ( r δ ∧ k ) 2 / 3 ≤ a 1 − 1 / 3 r δ . k^{1/3}(r_{\delta}\wedge k)^{2/3} \leq a_{1}^{-1/3}r_{\delta}. k 1/3 ( r δ ∧ k ) 2/3 ≤ a 1 − 1/3 r δ .
Thus, after decreasing a a a once more, we have
m C ( ε , δ ) ≥ a ( k 1 / 3 ( r δ ∧ k ) 2 / 3 ε + r δ ε ) . m_{\mathcal{C}}(\varepsilon,\delta) \geq a\left(\frac{k^{1/3}(r_{\delta}\wedge k)^{2/3}}{\varepsilon}+\frac{r_{\delta}}{\varepsilon}\right). m C ( ε , δ ) ≥ a ( ε k 1/3 ( r δ ∧ k ) 2/3 + ε r δ ) .
This proves the theorem.
Lemma C.2 (Block version of the diameter lower bound). There exist universal constants a a a , a 0 a_{0} a 0 , δ 0 > 0 \delta_{0}>0 δ 0 > 0 and k 0 ∈ N k_{0}\in\mathbb{N} k 0 ∈ N such that the following holds. Let d , k ∈ N d,k\in\mathbb{N} d , k ∈ N satisfy
1 ≤ d ≤ k , d ∣ k , k ≥ k 0 . 1\leq d\leq k,\qquad d\mid k,\qquad k\geq k_{0}. 1 ≤ d ≤ k , d ∣ k , k ≥ k 0 . Then, there exist a finite measurable space ( X d , k , 2 X d , k ) (\mathcal{X}_{d,k},2^{\mathcal{X}_{d,k}}) ( X d , k , 2 X d , k ) and a concept class C d , k ⊆ Y X d , k \mathcal{C}_{d,k}\subseteq\mathcal{Y}^{\mathcal{X}_{d,k}} C d , k ⊆ Y X d , k such that
VC ( C d , k ) = d and D ( C d , k ) = k , \operatorname{VC}(\mathcal{C}_{d,k})=d \qquad\text{and}\qquad\operatorname{D}(\mathcal{C}_{d,k})=k, VC ( C d , k ) = d and D ( C d , k ) = k , and, for every
ε ∈ ( 0 , a 0 ( d k ) 1 / 3 ] , \varepsilon\in\left(0,a_{0}\left(\frac{d}{k}\right)^{1/3}\right], ε ∈ ( 0 , a 0 ( k d ) 1/3 ] , the optimal sample complexity of agnostic PAC learning with deterministic labels satisfies
m C d , k ( ε , δ 0 ) ≥ a k 1 / 3 d 2 / 3 ε . m_{\mathcal{C}_{d,k}}(\varepsilon,\delta_{0})\geq a\frac{k^{1/3}d^{2/3}}{\varepsilon}. m C d , k ( ε , δ 0 ) ≥ a ε k 1/3 d 2/3 .
Proof. Throughout the proof, all constants are universal, and we decrease a a a , a 0 a_{0} a 0 , δ 0 \delta_{0} δ 0 and increase k 0 k_{0} k 0 whenever needed. As we defined in subsection 2.1, log ( ⋅ ) \log(\cdot) log ( ⋅ ) is in base 2, while some standard inequalities below are naturally written with base e. Indeed, changing between the two bases only changes universal constants. In addition, for a data distribution D \mathcal{D} D , define opt C ( D ) \operatorname{opt}_{\mathcal{C}}(\mathcal{D}) opt C ( D ) as
opt C ( D ) : = inf h ∈ C L D ( h ) . \operatorname{opt}_{\mathcal{C}}(\mathcal{D}):=\inf_{h\in\mathcal{C}}L_{\mathcal{D}}(h). opt C ( D ) := h ∈ C inf L D ( h ) .
⓪ Set
γ : = C 1 ( d k ) 1 / 3 , \gamma:=C_{1}\left(\frac{d}{k}\right)^{1/3}, γ := C 1 ( k d ) 1/3 ,
where C 1 ∈ ( 0 , 1 / 16 ) C_{1}\in(0,1/16) C 1 ∈ ( 0 , 1/16 ) is a sufficiently small universal constant. Next, set
q : = C 2 ε γ , q:=\frac{C_{2}\varepsilon}{\gamma}, q := γ C 2 ε ,
where C 2 > 0 C_{2} > 0 C 2 > 0 is a sufficiently large universal constant. By taking a 0 > 0 a_{0} > 0 a 0 > 0 sufficiently small, the assumption ε ≤ a 0 ( d / k ) 1 / 3 \varepsilon\leq a_{0}(d/k)^{1/3} ε ≤ a 0 ( d / k ) 1/3 implies that 0 < q ≤ 1 / 2 0 < q \leq1/2 0 < q ≤ 1/2 .
① Let s = k / d s = k/d s = k / d . Define X d , k \mathcal{X}_{d,k} X d , k as
X d , k : = { x 0 } ∪ { x j , ℓ ∣ j ∈ [ d ] , ℓ ∈ [ s ] } \mathcal{X}_{d,k} := \{x_{0}\} \cup\{x_{j,\ell} \mid j \in[d], \ell\in[s]\} X d , k := { x 0 } ∪ { x j , ℓ ∣ j ∈ [ d ] , ℓ ∈ [ s ]}
In addition, for every v = ( v 1 , v 2 , … , v d ) ∈ { − 1 , + 1 } d v = (v_{1}, v_{2}, \ldots, v_{d}) \in\{-1,+1\}^{d} v = ( v 1 , v 2 , … , v d ) ∈ { − 1 , + 1 } d , define h v : X d , k → { 0 , 1 } h^{v} : \mathcal{X}_{d,k} \to\{0,1\} h v : X d , k → { 0 , 1 } by
h v ( x 0 ) : = 0 , and h v ( x j , ℓ ) : = 1 [ v j = + 1 ] for every j ∈ [ d ] , ℓ ∈ [ s ] . h^{v}(x_{0}) := 0, \qquad\text{and} \qquad h^{v}(x_{j,\ell}) := \mathbb{1}[v_{j} = +1] \text{ for every } j \in[d], \ell\in[s]. h v ( x 0 ) := 0 , and h v ( x j , ℓ ) := 1 [ v j = + 1 ] for every j ∈ [ d ] , ℓ ∈ [ s ] .
Also, define C d , k \mathcal{C}_{d,k} C d , k as
C d , k : = { h v ∣ v ∈ { − 1 , + 1 } d } . \mathcal{C}_{d,k} := \left\{h^{v} \mid v \in\{-1,+1\}^{d}\right\}. C d , k := { h v ∣ v ∈ { − 1 , + 1 } d } .
② Next, we compute the combinatorial complexity parameters of C d , k \mathcal{C}_{d,k} C d , k . First, we analyze VC dimension. Observe that the set { x j , 1 ∣ j ∈ [ d ] } \{x_{j,1} \mid j \in[d]\} { x j , 1 ∣ j ∈ [ d ]} is shattered by C d , k \mathcal{C}_{d,k} C d , k , so we have: VC ( C d , k ) ≥ d \operatorname{VC}(\mathcal{C}_{d,k}) \geq d VC ( C d , k ) ≥ d . Conversely, no set of size d + 1 d+1 d + 1 is shattered by C d , k \mathcal{C}_{d,k} C d , k . If it contains x 0 x_{0} x 0 , then the labeling assigns a value 1 1 1 to x 0 x_{0} x 0 cannot be realized; otherwise, by the pigeonhole principle, it contains two points from the same block { x j , ℓ ∣ ℓ ∈ [ s ] } \{x_{j,\ell} \mid\ell\in[s]\} { x j , ℓ ∣ ℓ ∈ [ s ]} , and every concept in C d , k \mathcal{C}_{d,k} C d , k gives the same label to all points in this block. Thus, we have: VC ( C d , k ) < d + 1 \operatorname{VC}(\mathcal{C}_{d,k}) < d+1 VC ( C d , k ) < d + 1 . Therefore, we have: VC ( C d , k ) = d \operatorname{VC}(\mathcal{C}_{d,k}) = d VC ( C d , k ) = d . Second, we analyze diameter. For v , w ∈ { − 1 , + 1 } d v,w \in\{-1,+1\}^{d} v , w ∈ { − 1 , + 1 } d , we have:
∣ { x ∈ X d , k ∣ h v ( x ) ≠ h w ( x ) } ∣ = s ∣ { j ∈ [ d ] ∣ v j ≠ w j } ∣ . \left|\{x \in\mathcal{X}_{d,k} \mid h^{v}(x) \ne h^{w}(x)\}\right| = s\left|\{j \in[d] \mid v_{j} \ne w_{j}\}\right|. ∣ { x ∈ X d , k ∣ h v ( x ) = h w ( x )} ∣ = s ∣ { j ∈ [ d ] ∣ v j = w j } ∣ .
Thus, taking w = − v w=-v w = − v gives disagreement on all k = d s k=ds k = d s non-anchor points. In addition, no pair can disagree on more points. Therefore, we have: D ( C d , k ) = k \operatorname{D}(\mathcal{C}_{d,k}) = k D ( C d , k ) = k .
③ Define a marginal distribution μ \mu μ on X d , k \mathcal{X}_{d,k} X d , k by
μ ( x 0 ) : = 1 − q , and μ ( x j , ℓ ) : = q k for every j ∈ [ d ] , ℓ ∈ [ s ] . \mu(x_{0}) := 1-q, \qquad\text{and} \qquad\mu(x_{j,\ell}) := \frac{q}{k} \text{ for every } j \in[d], \ell\in[s]. μ ( x 0 ) := 1 − q , and μ ( x j , ℓ ) := k q for every j ∈ [ d ] , ℓ ∈ [ s ] .
Let the random variable V = ( V 1 , V 2 , … , V d ) V=(V_{1},V_{2},\ldots,V_{d}) V = ( V 1 , V 2 , … , V d ) be uniformly distributed over { − 1 , + 1 } d \{-1,+1\}^{d} { − 1 , + 1 } d . Conditional on V V V , let Z j , ℓ Z_{j,\ell} Z j , ℓ , j ∈ [ d ] , ℓ ∈ [ s ] j \in[d], \ell\in[s] j ∈ [ d ] , ℓ ∈ [ s ] , be independent Bernoulli random variables satisfying
P [ Z j , ℓ = 1 ∣ V ] = 1 2 + γ V j . \mathbb{P}[Z_{j,\ell}=1 \mid V] = \frac{1}{2}+\gamma V_{j}. P [ Z j , ℓ = 1 ∣ V ] = 2 1 + γ V j .
For each realization of ( V , Z ) (V,Z) ( V , Z ) , define a deterministic labeling function f V , Z : X d , k → { 0 , 1 } f_{V,Z} : \mathcal{X}_{d,k} \to\{0,1\} f V , Z : X d , k → { 0 , 1 } by
f V , Z ( x 0 ) : = 0 , and f V , Z ( x j , ℓ ) : = Z j , ℓ . f_{V,Z}(x_{0}) := 0, \qquad\text{and} \qquad f_{V,Z}(x_{j,\ell}) := Z_{j,\ell}. f V , Z ( x 0 ) := 0 , and f V , Z ( x j , ℓ ) := Z j , ℓ .
Now, for each realization of ( V , Z ) (V,Z) ( V , Z ) , let D V , Z D_{V,Z} D V , Z be the distribution of
( x , f V , Z ( x ) ) , (x,f_{V,Z}(x)), ( x , f V , Z ( x )) ,
where x ∼ μ x \sim\mu x ∼ μ . Indeed, every D V , Z D_{V,Z} D V , Z is deterministically labeled Definition 2.1 .
④ Subsequently, fix a sample size n n n that satisfies
n ≤ a k 1 / 3 d 2 / 3 ε . n \leq a\frac{k^{1/3}d^{2/3}}{\varepsilon}. n ≤ a ε k 1/3 d 2/3 .
Let S ∼ D V , Z n S \sim D_{V,Z}^{n} S ∼ D V , Z n . Let I = ( X 1 , X 2 , … , X n ) I=(X_{1},X_{2},\ldots,X_{n}) I = ( X 1 , X 2 , … , X n ) denote the sequence of sampled instances, and let Y = ( Y 1 , Y 2 , … , Y n ) Y=(Y_{1},Y_{2},\ldots,Y_{n}) Y = ( Y 1 , Y 2 , … , Y n ) denote the corresponding sequence of labels. By the chain rule for mutual information, we have
I ( V ; S ) = I ( V ; I , Y ) = I ( V ; I ) + E I [ I ( V ; Y ∣ I ) ] . I(V;S)=I(V;I,Y)=I(V;I)+\mathbb{E}_{I}[I(V;Y\mid I)]. I ( V ; S ) = I ( V ; I , Y ) = I ( V ; I ) + E I [ I ( V ; Y ∣ I )] .
Since the marginal distribution of the sampled instances does not depend on V V V , we have I ( V ; I ) = 0 I(V;I)=0 I ( V ; I ) = 0 . Therefore,
I ( V ; S ) = E I [ I ( V ; Y ∣ I ) ] . I(V;S)=\mathbb{E}_{I}[I(V;Y\mid I)]. I ( V ; S ) = E I [ I ( V ; Y ∣ I )] .
Now, fix a realization of I I I . Let D ( I ) D(I) D ( I ) be the number of distinct points among { x j , ℓ ∣ j ∈ [ d ] , ℓ ∈ [ s ] } \{x_{j,\ell} \mid j \in[d],\ \ell\in[s]\} { x j , ℓ ∣ j ∈ [ d ] , ℓ ∈ [ s ]} that appear in I I I . Conditional on I I I , only the labels of these D ( I ) D(I) D ( I ) points can carry information about V V V . Moreover, repeated appearances of the same point do not contribute additional independent information, because the label of each point is deterministic once V V V and Z Z Z are fixed. Each such distinct observed point contributes at most C γ 2 C\gamma^2 C γ 2 information about the corresponding coordinate of V V V , for a universal constant C > 0 C > 0 C > 0 . Therefore, we have
I ( V ; Y ∣ I ) ≤ C γ 2 D ( I ) . I(V;Y \mid I) \le C\gamma^2 D(I). I ( V ; Y ∣ I ) ≤ C γ 2 D ( I ) .
Thus, we have
I ( V ; S ) ≤ C γ 2 E [ D ( I ) ] . I(V;S) \le C\gamma^2 \mathbb{E}[D(I)]. I ( V ; S ) ≤ C γ 2 E [ D ( I )] .
Finally, D ( I ) ≤ N D(I) \le N D ( I ) ≤ N , where N N N is the total number of sampled points falling in { x j , ℓ ∣ j ∈ [ d ] , ℓ ∈ [ s ] } \{x_{j,\ell} \mid j \in[d],\ \ell\in[s]\} { x j , ℓ ∣ j ∈ [ d ] , ℓ ∈ [ s ]} . Since N ∼ Bin ( n , q ) N \sim\operatorname{Bin}(n,q) N ∼ Bin ( n , q ) , we have E [ D ( I ) ] ≤ E [ N ] = n q \mathbb{E}[D(I)] \le\mathbb{E}[N] = nq E [ D ( I )] ≤ E [ N ] = n q . Therefore, we get
I ( V ; S ) ≤ C n q γ 2 . I(V;S) \le Cnq\gamma^2. I ( V ; S ) ≤ C n q γ 2 .
Now, using q = C 2 ε / γ q = C_2\varepsilon/\gamma q = C 2 ε / γ and the upper bound on n n n , we obtain
I ( V ; S ) ≤ C C 2 a k 1 / 3 d 2 / 3 γ = C C 1 C 2 a d . I(V;S) \le CC_2ak^{1/3}d^{2/3}\gamma= CC_1C_2ad. I ( V ; S ) ≤ C C 2 a k 1/3 d 2/3 γ = C C 1 C 2 a d .
Taking a > 0 a > 0 a > 0 sufficiently small, we may assume that I ( V ; S ) ≤ c 0 d I(V;S) \le c_0d I ( V ; S ) ≤ c 0 d , where c 0 > 0 c_0 > 0 c 0 > 0 is a sufficiently small universal constant.
By Assouad’s lemma, every estimator V ^ = V ^ ( S ) \widehat{V} = \widehat{V}(S) V = V ( S ) satisfies
E [ ∣ { j ∈ [ d ] ∣ V ^ j ≠ V j } ∣ ] ≥ d 4 . \mathbb{E}\left[\left|\{j \in[d] \mid\widehat{V}_j \ne V_j\}\right|\right] \ge\frac{d}{4}. E [ { j ∈ [ d ] ∣ V j = V j } ] ≥ 4 d .
Consequently, we get
P [ ∣ { j ∈ [ d ] ∣ V ^ j ≠ V j } ∣ ≥ d 8 ] ≥ 1 8 . \mathbb{P}\left[\left|\{j \in[d] \mid\widehat{V}_j \ne V_j\}\right| \ge\frac{d}{8}\right] \ge\frac{1}{8}. P [ { j ∈ [ d ] ∣ V j = V j } ≥ 8 d ] ≥ 8 1 .
⑤ Next, fix a determinist PAC learning algorithm A \mathbf{A} A . Now, we construct an estimator from the learner. For every j ∈ [ d ] j \in[d] j ∈ [ d ] , define the unseen part of the j j j -th block by
U j ( S ) : = { ℓ ∈ [ s ] ∣ x j , ℓ does not appear in S } , U_j(S) := \{\ell\in[s] \mid x_{j,\ell}\text{ does not appear in }S\}, U j ( S ) := { ℓ ∈ [ s ] ∣ x j , ℓ does not appear in S } ,
and let
M ( S ) : = ∣ { ( j , ℓ ) ∈ [ d ] × [ s ] ∣ x j , ℓ appears in S } ∣ M(S) := \left|\{(j,\ell) \in[d] \times[s] \mid x_{j,\ell}\text{ appears in }S\}\right| M ( S ) := ∣ {( j , ℓ ) ∈ [ d ] × [ s ] ∣ x j , ℓ appears in S } ∣
Define V ^ ( S ) ∈ { − 1 , + 1 } d \widehat{V}(S) \in\{-1,+1\}^d V ( S ) ∈ { − 1 , + 1 } d by
V ^ j ( S ) : = { + 1 , ∣ { ℓ ∈ U j ( S ) ∣ A S ( x j , ℓ ) = 1 } ∣ ≥ ∣ U j ( S ) ∣ / 2 , − 1 , otherwise . \widehat{V}_j(S) :=
\begin{cases}
+1, & \left|\{\ell\in U_j(S) \mid A_S(x_{j,\ell}) = 1\}\right| \ge|U_j(S)|/2,\\
-1, & \text{otherwise}.
\end{cases} V j ( S ) := { + 1 , − 1 , ∣ { ℓ ∈ U j ( S ) ∣ A S ( x j , ℓ ) = 1 } ∣ ≥ ∣ U j ( S ) ∣/2 , otherwise .
Thus, if V ^ j ( S ) ≠ V j \widehat{V}_j(S) \ne V_j V j ( S ) = V j , then the learner predicts against the biased direction on at least half of the unseen points in block j j j .
⑥ We now show that, on E \mathcal{E} E , the learner has an excess error larger than ε \varepsilon ε , except for an event with a small probability.
First , since M ( S ) M(S) M ( S ) is at most the total number of samples falling outside x 0 x_0 x 0 , we have
E [ M ( S ) ] ≤ n q . \mathbb{E}[M(S)] \le nq. E [ M ( S )] ≤ n q .
Moreover, we have
n q ≤ a k 1 / 3 d 2 / 3 ε ⋅ C 2 ε γ = a C 2 C 1 k 2 / 3 d 1 / 3 , nq \le a\frac{k^{1/3}d^{2/3}}{\varepsilon}\cdot\frac{C_2\varepsilon}{\gamma}
= \frac{aC_2}{C_1}k^{2/3}d^{1/3}, n q ≤ a ε k 1/3 d 2/3 ⋅ γ C 2 ε = C 1 a C 2 k 2/3 d 1/3 ,
while
γ k = C 1 k 2 / 3 d 1 / 3 . \gamma k = C_1 k^{2/3}d^{1/3}. γ k = C 1 k 2/3 d 1/3 .
Taking a > 0 a > 0 a > 0 sufficiently small, Markov’s inequality gives
P [ M ( S ) > η γ k ] ≤ 1 32 , \mathbb{P}[M(S) > \eta\gamma k] \le\frac{1}{32}, P [ M ( S ) > η γ k ] ≤ 32 1 ,
where η > 0 \eta> 0 η > 0 is a sufficiently small universal constant. Therefore, with probability at least 1 / 8 − 1 / 32 1/8-1/32 1/8 − 1/32 , both
∣ { j ∈ [ d ] ∣ V ^ j ( S ) ≠ V j } ∣ ≥ d 8 \left|\left\{j \in[d] \mid\widehat{V}_j(S) \ne V_j\right\}\right| \ge\frac{d}{8} { j ∈ [ d ] ∣ V j ( S ) = V j } ≥ 8 d
and
M ( S ) ≤ η γ k M(S) \le\eta\gamma k M ( S ) ≤ η γ k
hold. Denote this event by E \mathcal{E} E .
Second, define h V ∈ C d , k h^V \in C_{d,k} h V ∈ C d , k to be the concept corresponding to the vector V V V . Since
h V ( x j , ℓ ) = 1 [ V j = + 1 ] , h^V(x_{j,\ell}) = 1[V_j = +1], h V ( x j , ℓ ) = 1 [ V j = + 1 ] ,
we have:
E [ L D V , Z ( h V ) ∣ V ] = q ( 1 2 − γ ) . \mathbb{E}\left[\mathcal{L}_{D_{V,Z}}(h^V) \mid V\right] = q\left(\frac{1}{2}-\gamma\right). E [ L D V , Z ( h V ) ∣ V ] = q ( 2 1 − γ ) .
Again, by Hoeffding’s inequality, except with probability at most exp ( − c ′ k γ 2 ) \exp(-c' k\gamma^2) exp ( − c ′ k γ 2 ) , where c ′ > 0 c' > 0 c ′ > 0 is a universal constant, we have:
L D V , Z ( h V ) ≤ q ( 1 2 − γ ) + q γ 64 . \mathcal{L}_{D_{V,Z}}(h^V) \le q\left(\frac{1}{2}-\gamma\right) + \frac{q\gamma}{64}. L D V , Z ( h V ) ≤ q ( 2 1 − γ ) + 64 q γ .
Since h V ∈ C d , k h^V \in C_{d,k} h V ∈ C d , k , we get:
opt C d , k ( D V , Z ) ≤ L D V , Z ( h V ) . \operatorname{opt}_{C_{d,k}}(D_{V,Z}) \le\mathcal{L}_{D_{V,Z}}(h^V). opt C d , k ( D V , Z ) ≤ L D V , Z ( h V ) .
Third, define
B ( S , V ) : = ∣ { ( j , ℓ ) ∣ ℓ ∈ U j ( S ) , A S ( x j , ℓ ) ≠ 1 [ V j = + 1 ] } ∣ . B(S,V) := \left|\left\{(j,\ell) \mid\ell\in U_j(S),\ A_S(x_{j,\ell}) \ne1[V_j = +1]\right\}\right|. B ( S , V ) := ∣ { ( j , ℓ ) ∣ ℓ ∈ U j ( S ) , A S ( x j , ℓ ) = 1 [ V j = + 1 ] } ∣ .
If V ^ j ( S ) ≠ V j \widehat{V}_j(S) \ne V_j V j ( S ) = V j , then the learner predicts against the biased direction on at least half of the unseen points in block j j j . Hence, on E \mathcal{E} E , we have
B ( S , V ) ≥ 1 2 ( d 8 ⋅ s − M ( S ) ) ≥ k 16 − η γ k 2 . B(S,V) \ge\frac{1}{2}\left(\frac{d}{8}\cdot s-M(S)\right) \ge\frac{k}{16}-\frac{\eta\gamma k}{2}. B ( S , V ) ≥ 2 1 ( 8 d ⋅ s − M ( S ) ) ≥ 16 k − 2 η γ k .
Conditional on V V V and S S S , the labels on the unseen points remain independent. Let
L u n : = q k ∑ j = 1 d ∑ ℓ ∈ U j ( S ) 1 [ A S ( x j , ℓ ) ≠ f V , Z ( x j , ℓ ) ] . L_{\mathrm{un}} := \frac{q}{k}\sum_{j=1}^{d}\sum_{\ell\in U_j(S)}1\left[A_S(x_{j,\ell}) \ne f_{V,Z}(x_{j,\ell})\right]. L un := k q j = 1 ∑ d ℓ ∈ U j ( S ) ∑ 1 [ A S ( x j , ℓ ) = f V , Z ( x j , ℓ ) ] .
Then, we have:
E [ L u n ∣ V , S ] = q k [ ( k − M ( S ) ) ( 1 2 − γ ) + 2 γ B ( S , V ) ] . \mathbb{E}[L_{\mathrm{un}}\mid V,S] = \frac{q}{k}\left[(k-M(S))\left(\frac{1}{2}-\gamma\right)+2\gamma B(S,V)\right]. E [ L un ∣ V , S ] = k q [ ( k − M ( S )) ( 2 1 − γ ) + 2 γ B ( S , V ) ] .
Thus, by Hoeffding’s inequality, except with probability at most exp ( − c k γ 2 ) \exp(-ck\gamma^2) exp ( − c k γ 2 ) , where c > 0 c > 0 c > 0 is a universal constant, we have
L u n ≥ E [ L u n ∣ V , S ] − q γ 64 . L_{\mathrm{un}} \ge\mathbb{E}[L_{\mathrm{un}}\mid V,S]-\frac{q\gamma}{64}. L un ≥ E [ L un ∣ V , S ] − 64 q γ .
Therefore, except with probability at most exp ( − c k γ 2 ) + exp ( − c ′ k γ 2 ) \exp(-ck\gamma^2)+\exp(-c'k\gamma^2) exp ( − c k γ 2 ) + exp ( − c ′ k γ 2 ) , on the event E \mathcal{E} E we have
L D V , Z ( A S ) − opt C d , k ( D V , Z ) ≥ L u n − L D V , Z ( h V ) ≥ q k [ − M ( S ) ( 1 2 − γ ) + 2 γ B ( S , V ) ] − q γ 32 ≥ q γ ( 3 32 − η 2 ) . \begin{aligned}
\mathcal{L}_{D_{V,Z}}(A_S)-\operatorname{opt}_{C_{d,k}}(D_{V,Z})
&\ge L_{\mathrm{un}}-\mathcal{L}_{D_{V,Z}}(h^V)\\
&\ge\frac{q}{k}\left[-M(S)\left(\frac{1}{2}-\gamma\right)+2\gamma B(S,V)\right]-\frac{q\gamma}{32}\\
&\ge q\gamma\left(\frac{3}{32}-\frac{\eta}{2}\right).
\end{aligned} L D V , Z ( A S ) − opt C d , k ( D V , Z ) ≥ L un − L D V , Z ( h V ) ≥ k q [ − M ( S ) ( 2 1 − γ ) + 2 γ B ( S , V ) ] − 32 q γ ≥ q γ ( 32 3 − 2 η ) .
Taking η > 0 \eta> 0 η > 0 sufficiently small, the last expression is at least c ′ ′ q γ c''q\gamma c ′′ q γ for a universal constant c ′ ′ > 0 c'' > 0 c ′′ > 0 . Since q γ = C 2 ϵ q\gamma=C_2\epsilon q γ = C 2 ϵ , choosing C 2 > 0 C_2 > 0 C 2 > 0 sufficiently large gives
c ′ ′ q γ > ϵ . c''q\gamma>\epsilon. c ′′ q γ > ϵ .
⑦ Finally, observe that
k γ 2 = C 1 2 k 1 / 3 d 2 / 3 . k\gamma^2 = C_1^2 k^{1/3}d^{2/3}. k γ 2 = C 1 2 k 1/3 d 2/3 .
Since d ≥ 1 d \ge1 d ≥ 1 , taking k 0 k_0 k 0 sufficiently large makes
exp ( − c k γ 2 ) + exp ( − c ′ k γ 2 ) \exp(-c k\gamma^2) + \exp(-c' k\gamma^2) exp ( − c k γ 2 ) + exp ( − c ′ k γ 2 )
smaller than a sufficiently small universal constant. Combining this with P [ E ] ≥ 1 / 8 − 1 / 32 \mathbb{P}[\mathcal{E}] \ge1/8 - 1/32 P [ E ] ≥ 1/8 − 1/32 , we get that, for some universal constant δ 0 > 0 \delta_0 > 0 δ 0 > 0 ,
P V , Z , S [ L D V , Z ( A S ) > opt C d , k ( D V , Z ) + ϵ ] > δ 0 . \mathbb{P}_{V,Z,S}\left[\mathcal{L}_{D_{V,Z}}(A_S) > \operatorname{opt}_{C_{d,k}}(D_{V,Z}) + \epsilon\right] > \delta_0. P V , Z , S [ L D V , Z ( A S ) > opt C d , k ( D V , Z ) + ϵ ] > δ 0 .
Now, we apply the probabilistic method. In particular, by averaging over ( V , Z ) (V,Z) ( V , Z ) , there exists a fixed realization ( v , z ) (v,z) ( v , z ) such that, for the corresponding deterministically labeled distribution D v , z D_{v,z} D v , z ,
P S ∼ D v , z n [ L D v , z ( A S ) > opt C d , k ( D v , z ) + ϵ ] > δ 0 . \mathbb{P}_{S\sim D_{v,z}^n}\left[\mathcal{L}_{D_{v,z}}(A_S) > \operatorname{opt}_{C_{d,k}}(D_{v,z}) + \epsilon\right] > \delta_0. P S ∼ D v , z n [ L D v , z ( A S ) > opt C d , k ( D v , z ) + ϵ ] > δ 0 .
Since A A A was arbitrary, no algorithm using
n ≤ a k 1 / 3 d 2 / 3 ϵ n \le a\frac{k^{1/3}d^{2/3}}{\epsilon} n ≤ a ϵ k 1/3 d 2/3
samples satisfies the agnostic PAC learning with deterministic labels guarantee with confidence 1 − δ 0 1-\delta_0 1 − δ 0 . Hence, we have:
m C d , k ( ϵ , δ 0 ) ≥ a k 1 / 3 d 2 / 3 ϵ . m_{C_{d,k}}(\epsilon,\delta_0) \ge a\frac{k^{1/3}d^{2/3}}{\epsilon}. m C d , k ( ϵ , δ 0 ) ≥ a ϵ k 1/3 d 2/3 .
This proves the theorem.
Analysis of Infinite Diameter
In this section, we prove an upper bound for concept classes with infinite diameter. Note that the “Outer C ∗ C^* C ∗ approximation” portion of the proof is inspired by upper bound of Ben-David and Urner [ [7 ] for agnostic PAC learning with deterministic labels of classes with finite diameter.
Theorem D.1. For every k ∈ N k \in\mathbb{N} k ∈ N and concept class C \mathcal{C} C with d : = VC ( C ) < ∞ d := \operatorname{VC}(\mathcal{C}) < \infty d := VC ( C ) < ∞ , C \mathcal{C} C is agnostic PAC learnable with sample complexity upper bounded by
m C ( ϵ , δ ) = O ( PERT-VC ( C , k ) + ln ( 1 / δ ) ϵ 2 + k ln ( 1 / ϵ ) ϵ ) (11) m_{\mathcal{C}}(\epsilon,\delta) = O\left(\frac{\operatorname{PERT\text{-}VC}(\mathcal{C},k) + \ln(1/\delta)}{\epsilon^2} + \frac{k\ln(1/\epsilon)}{\epsilon}\right) \tag*{(11)} m C ( ϵ , δ ) = O ( ϵ 2 PERT - VC ( C , k ) + ln ( 1/ δ ) + ϵ k ln ( 1/ ϵ ) ) (11)
Proof. Let
C ∗ = arg min C ′ { VC ( C ′ ) : d ( C ; C ′ ) ≤ k } . \mathcal{C}^* = \underset{\mathcal{C}'}{\arg\min}\{\operatorname{VC}(\mathcal{C}') : d(\mathcal{C};\mathcal{C}') \le k\}. C ∗ = C ′ arg min { VC ( C ′ ) : d ( C ; C ′ ) ≤ k } .
Fix ϵ , δ ∈ ( 0 , 1 ) \epsilon,\delta\in(0,1) ϵ , δ ∈ ( 0 , 1 ) and fix an arbitrary deterministically labeled distribution D \mathcal{D} D over X × Y \mathcal{X} \times\mathcal{Y} X × Y . Let n ∈ N n \in\mathbb{N} n ∈ N , and S S S be an i.i.d. sample of size n n n drawn from D \mathcal{D} D . Let A A A be an MERM with respect to C ∗ \mathcal{C}^* C ∗ .
Outer C ∗ \mathcal{C}^* C ∗ approximation. We call a point x ∈ X x \in\mathcal{X} x ∈ X heavy if its marginal weight is at least ϵ / 2 k \epsilon/2k ϵ /2 k . Let T T T be the set of heavy points. Since each point in T T T has marginal weight at least ϵ / 2 k \epsilon/2k ϵ /2 k , we have ∣ T ∣ ≤ 2 k / ϵ |T| \le2k/\epsilon ∣ T ∣ ≤ 2 k / ϵ . Therefore, as long as
n ≥ 2 k ln ( 1 / ϵ ) + 2 ln ( 2 / δ ) ϵ , n \ge\frac{2k\ln(1/\epsilon) + 2\ln(2/\delta)}{\epsilon}, n ≥ ϵ 2 k ln ( 1/ ϵ ) + 2 ln ( 2/ δ ) ,
with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 , the sample S S S contains every point in T T T . On this event, for every h ∈ C ∗ h \in\mathcal{C}^* h ∈ C ∗ and every h ′ ∈ C h' \in\mathcal{C} h ′ ∈ C such that ∣ h Δ h ′ ∣ ≤ k |h\Delta h'| \le k ∣ h Δ h ′ ∣ ≤ k , we have
L D ( g h , S ) − L D ( h ′ ) ≤ D X ( h Δ h ′ ∖ S ) ≤ k ⋅ ϵ 2 k = ϵ 2 , (12) \mathcal{L}_{\mathcal{D}}(g_{h,S}) - \mathcal{L}_{\mathcal{D}}(h') \le D_{\mathcal{X}}(h\Delta h' \setminus S) \le k \cdot\frac{\epsilon}{2k} = \frac{\epsilon}{2}, \tag*{(12)} L D ( g h , S ) − L D ( h ′ ) ≤ D X ( h Δ h ′ ∖ S ) ≤ k ⋅ 2 k ϵ = 2 ϵ , (12)
where D X D_{\mathcal{X}} D X is the marginal distribution of D \mathcal{D} D . Inner C ∗ C^* C ∗ approximation. Let h ^ \hat{h} h ^ be a concept satisfying
h ^ ∈ arg min h ∈ C ∗ L S ( h ) , A S = g h ^ , S \hat{h} \in\arg\min_{h \in C^*} \mathcal{L}_S(h), \qquad A_S = g_{\hat{h},S} h ^ ∈ arg h ∈ C ∗ min L S ( h ) , A S = g h ^ , S
By standard PAC theory (e.g. Haussler [ [30 ] ), there exists a universal constant a > 0 a > 0 a > 0 such that for
n ≥ a ( PERT-VC ( C , k ) + ln ( 1 / δ ) ) ε 2 n \ge\frac{a\left(\operatorname{PERT\text{-}VC}(C,k) + \ln(1/\delta)\right)}{\varepsilon^2} n ≥ ε 2 a ( PERT - VC ( C , k ) + ln ( 1/ δ ) )
with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2
L D ( h ^ ) ≤ inf h ∈ C ∗ L D ( h ) + ε / 2. \mathcal{L}_D(\hat{h}) \le\inf_{h \in C^*} \mathcal{L}_D(h) + \varepsilon/2. L D ( h ^ ) ≤ h ∈ C ∗ inf L D ( h ) + ε /2.
Note that for every h , h ′ ∈ C ∗ h,h' \in C^* h , h ′ ∈ C ∗
L D ( g h , S ) − L D ( g h ′ , S ) ≤ L D ( h ) − L D ( h ′ ) , \mathcal{L}_D(g_{h,S}) - \mathcal{L}_D(g_{h',S}) \le\mathcal{L}_D(h) - \mathcal{L}_D(h'), L D ( g h , S ) − L D ( g h ′ , S ) ≤ L D ( h ) − L D ( h ′ ) ,
and that L D ( g h , S ) ≤ L D ( h ) \mathcal{L}_D(g_{h,S}) \le\mathcal{L}_D(h) L D ( g h , S ) ≤ L D ( h ) . Thus, with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2
L D ( g h ^ , S ) ≤ inf h ∈ C ∗ L D ( g h , S ) + ε / 2. \mathcal{L}_D(g_{\hat{h},S}) \le\inf_{h \in C^*} \mathcal{L}_D(g_{h,S}) + \varepsilon/2. L D ( g h ^ , S ) ≤ h ∈ C ∗ inf L D ( g h , S ) + ε /2.
Combining this with Equation (12) with probability at least 1 − δ 1-\delta 1 − δ we get
L D ( g h ^ , S ) ≤ inf h ∈ C ∗ inf h ′ ∈ C : ∣ h ′ △ h ∣ ≤ k L D ( h ′ ) + ε ≤ inf h ′ ∈ C L D ( h ′ ) + ε \mathcal{L}_D(g_{\hat{h},S}) \le\inf_{h \in C^*} \inf_{h' \in C: |h'\mathbin{\triangle}h|\le k} \mathcal{L}_D(h') + \varepsilon\le\inf_{h' \in C} \mathcal{L}_D(h') + \varepsilon L D ( g h ^ , S ) ≤ h ∈ C ∗ inf h ′ ∈ C : ∣ h ′ △ h ∣ ≤ k inf L D ( h ′ ) + ε ≤ h ′ ∈ C inf L D ( h ′ ) + ε
This completes the proof.
Discussion. First, recall the lower bound of Ben-David and Urner [ [7 ] for agnostic PAC learning with deterministic labels in the infinite-diameter regime.
Theorem D.2 (Ben-David and Urner [ [7 ] , restated in terms of SET-VC). For every concept class C C C such that SET-VC ( C ) < ∞ \operatorname{SET\text{-}VC}(C) < \infty SET - VC ( C ) < ∞ , the optimal sample complexity of agnostic PAC learning C C C with deterministic labels satisfies
m C ( ε , δ ) ≥ SET-VC ( C ) ε 2 m_C(\varepsilon,\delta) \ge\frac{\operatorname{SET\text{-}VC}(C)}{\varepsilon^2} m C ( ε , δ ) ≥ ε 2 SET - VC ( C )
Then observe that PERT-VC ( C ) = lim k → ∞ PERT-VC ( C , k ) \operatorname{PERT\text{-}VC}(C) = \lim_{k \to\infty} \operatorname{PERT\text{-}VC}(C,k) PERT - VC ( C ) = lim k → ∞ PERT - VC ( C , k ) . Since PERT-VC ( C , k ) \operatorname{PERT\text{-}VC}(C,k) PERT - VC ( C , k ) is integer-valued and non-increasing in k k k , there exists k ∗ ∈ N k^* \in\mathbb{N} k ∗ ∈ N such that
PERT-VC ( C , k ∗ ) = PERT-VC ( C ) . \operatorname{PERT\text{-}VC}(C,k^*) = \operatorname{PERT\text{-}VC}(C). PERT - VC ( C , k ∗ ) = PERT - VC ( C ) .
Fix such a k ∗ k^* k ∗ . The 1 / ε 2 1/\varepsilon^2 1/ ε 2 term in our upper bound in Equation (11) is controlled by PERT-VC ( C ) \operatorname{PERT\text{-}VC}(C) PERT - VC ( C ) . Therefore, as ε → 0 \varepsilon\to0 ε → 0 , this term dominates the lower-order term. In particular, if SET-VC ( C ) = PERT-VC ( C ) \operatorname{SET\text{-}VC}(C) = \operatorname{PERT\text{-}VC}(C) SET - VC ( C ) = PERT - VC ( C ) , then our upper bound is tight in the small-ε \varepsilon ε regime. This leads to the following natural open question.
Open Question 1.4. Is there a concept class C C C such that SET-VC ( C ) ≠ PERT-VC ( C ) \operatorname{SET\text{-}VC}(C) \ne\operatorname{PERT\text{-}VC}(C) SET - VC ( C ) = PERT - VC ( C ) ?
Deferred Definitions
In this section, we define the online learning framework in subsection E.1. Then in subsection E.2, we give the definition of the main combinatorial complexity parameter that appears in our online learning results in Appendix F.
Online Learning Framework
We begin by giving the problem setup. Fix a non-empty set X \mathcal{X} X , referred to as the instance space. In addition, fix Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } as the label space. A concept is a function from X \mathcal{X} X to Y \mathcal{Y} Y . With this in mind, fix a non-empty collection of such functions C \mathcal{C} C as the concept class. We specify instances of the online learning framework using the concept class C \mathcal{C} C .
Next, fix T ∈ N T \in\mathbb{N} T ∈ N . The problem of online learning is formulated as a T T T -rounded sequential game between a learner and an adversary. In particular, on each round t ∈ [ T ] t \in[T] t ∈ [ T ] :
The adversary chooses an instance x t ∈ X x_t \in\mathcal{X} x t ∈ X and presents it to the learner.
The adversary chooses a label y t ∈ Y y_t \in\mathcal{Y} y t ∈ Y .
The learner predicts a label y ^ t ∈ Y \hat{y}_t \in\mathcal{Y} y ^ t ∈ Y .
The adversary reveals the label y t y_t y t to the learner.
Subsequently, we present the definition of an online learning algorithm. Let D = { ( T , S , x ) ∣ T ∈ N , S ∈ ⋃ t = 0 T − 1 ( X × Y ) t , x ∈ X } \mathcal{D} = \{(T,S,x) \mid T \in\mathbb{N}, S \in\bigcup_{t=0}^{T-1}(\mathcal{X} \times\mathcal{Y})^t, x \in\mathcal{X}\} D = {( T , S , x ) ∣ T ∈ N , S ∈ ⋃ t = 0 T − 1 ( X × Y ) t , x ∈ X } . A randomized online learning rule is a mapping from D \mathcal{D} D to Π ( Y ) \Pi(\mathcal{Y}) Π ( Y ) , where Π ( Y ) \Pi(\mathcal{Y}) Π ( Y ) denotes the set of all probability distributions over Y \mathcal{Y} Y . In words, an online learning algorithm is a function that maps a time horizon, a finite sequence of instances of length at most the time horizon, and an instance, to a distribution over the labels.
Fix an online learning algorithm A \mathrm{A} A . Also, fix T ∈ N T \in\mathbb{N} T ∈ N . Let S S S be a finite sequence of instance label pairs of size T T T , that is, S ∈ ( X × Y ) T S \in(\mathcal{X} \times\mathcal{Y})^T S ∈ ( X × Y ) T . We denote by A ( S ) ∈ Π ( Y ) T \mathrm{A}(S) \in\Pi(\mathcal{Y})^T A ( S ) ∈ Π ( Y ) T the random sequence of outputs of A \mathrm{A} A when the adversary’s choices are obtained according to S S S .
In this work, we restrict attention to deterministically labeled sequences. Formally, we have the following definition.
Definition E.1 (Deterministically labeled sequence). A sequence of instance-label pairs S = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T ) ) ∈ ( X × Y ) T S = ((x_1,y_1),(x_2,y_2),\ldots,(x_T,y_T)) \in(\mathcal{X} \times\mathcal{Y})^T S = (( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T )) ∈ ( X × Y ) T for some T ∈ N T \in\mathbb{N} T ∈ N is said to be deterministically labeled if there exists a concept f ⋆ : X → Y f^\star:\mathcal{X}\to\mathcal{Y} f ⋆ : X → Y such that
f ⋆ ( x t ) = y t for all t ∈ [ T ] . f^\star(x_t) = y_t \qquad\text{for all } t \in[T]. f ⋆ ( x t ) = y t for all t ∈ [ T ] .
To assess the performance of online learning algorithms, we adapt the well-established game-theoretic notion of expected regret to our framework.
Definition E.2 (Expected Number of Mistakes). Let A \mathrm{A} A be a randomized online learning rule. Fix T ∈ N T \in\mathbb{N} T ∈ N . Let S S S be a finite sequence of instance-label pairs of size T T T , namely S = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T ) ) ∈ ( X × Y ) T S = ((x_1,y_1),(x_2,y_2),\ldots,(x_T,y_T)) \in(\mathcal{X} \times\mathcal{Y})^T S = (( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T )) ∈ ( X × Y ) T . We define the expected total number of mistakes made by A \mathrm{A} A on the sequence S S S , denoted by M ‾ ( A ; S ) \overline{\mathrm{M}}(\mathrm{A};S) M ( A ; S ) , as follows:
M ‾ ( A ; S ) : = E [ ∑ t = 1 T 1 [ y t ≠ y ^ t ] ] , \overline{\mathrm{M}}(\mathrm{A};S) := \mathbb{E}\left[\sum_{t=1}^{T}\mathbb{1}[y_t \ne\hat{y}_t]\right], M ( A ; S ) := E [ t = 1 ∑ T 1 [ y t = y ^ t ] ] , where ( y ^ 1 , y ^ 2 , … , y ^ T ) ∼ A ( S ) (\hat{y}_1,\hat{y}_2,\ldots,\hat{y}_T) \sim\mathrm{A}(S) ( y ^ 1 , y ^ 2 , … , y ^ T ) ∼ A ( S ) .
Definition E.3 (Expected Regret). Let A \mathrm{A} A be a randomized online learning rule. Fix T ∈ N T \in\mathbb{N} T ∈ N . Let S S S be a finite sequence of instance-label pairs of size T T T , namely S = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T ) ) ∈ ( X × Y ) T S = ((x_1,y_1),(x_2,y_2),\ldots,(x_T,y_T)) \in(\mathcal{X} \times\mathcal{Y})^T S = (( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T )) ∈ ( X × Y ) T . We define the expected regret of A \mathrm{A} A on the sequence S S S against the performance of the concept class C \mathcal{C} C , denoted by R ( A ; S ; C ) \mathrm{R}(\mathrm{A};S;\mathcal{C}) R ( A ; S ; C ) , as follows:
R ( A ; S ; C ) : = M ‾ ( A ; S ) − inf c ∈ C ∑ t = 1 T 1 [ c ( x t ) ≠ y t ] . \mathrm{R}(\mathrm{A};S;\mathcal{C}) := \overline{\mathrm{M}}(\mathrm{A};S) - \inf_{c \in\mathcal{C}}\sum_{t=1}^{T}\mathbb{1}[c(x_t) \ne y_t]. R ( A ; S ; C ) := M ( A ; S ) − c ∈ C inf t = 1 ∑ T 1 [ c ( x t ) = y t ] .
Finally, we define the best achievable worst-case expected regret in our framework.
Definition E.4 (Optimal Expected Regret with deterministic labels). The best achievable worst-case expected regret as a function of the concept class C \mathcal{C} C and the time horizon T T T , denoted by R ⋆ ( C , T ) \mathrm{R}^\star(\mathcal{C},T) R ⋆ ( C , T ) , is defined as follows:
R ⋆ ( C , T ) : = inf A ∈ A sup S ∈ ( X × Y ) T R ( A ; S ; C ) , \mathrm{R}^\star(\mathcal{C},T) := \inf_{\mathrm{A} \in\mathcal{A}}\ \sup_{S \in(\mathcal{X} \times\mathcal{Y})^T}\ \mathrm{R}(\mathrm{A};S;\mathcal{C}), R ⋆ ( C , T ) := A ∈ A inf S ∈ ( X × Y ) T sup R ( A ; S ; C ) , where A \mathcal{A} A is the set of all randomized adversary-directed online learning rules and S S S is deterministically labeled.
Oblivious vs. Adaptive Adversaries. Although the above definition is stated for an oblivious adversary, all of our results extend to adaptive adversaries. In particular, in the agnostic setting, we rely on Lemma 4.1 of Cesa-Bianchi and Lugosi [ [20 ] .
Combinatorial Complexity Parameters
In this subsection, we define a combinatorial complexity parameter that appears in our online learning results.
Definition E.5 (Finite Rooted Perfect Binary Tree). A finite rooted perfect binary tree is a rooted tree with a finite number of nodes in which each non-leaf node has exactly two children and all leaves have the same depth.
Definition E.6 (Littlestone Tree). Let C ⊆ { 0 , 1 } X \mathcal{C} \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X be a concept class. A Littlestone tree for C \mathcal{C} C is a finite rooted perfect binary tree in which each non-leaf node is labeled by an instance from X \mathcal{X} X , and the two outgoing edges of each non-leaf node are labeled by 0 and 1, accordingly.
Definition E.7 (Shattered Littlestone Tree). Let C ⊆ { 0 , 1 } X \mathcal{C} \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X be a concept class, and let T \mathcal{T} T be a Littlestone tree for C \mathcal{C} C . We say that T \mathcal{T} T is shattered by C \mathcal{C} C if for every root-to-leaf path in T \mathcal{T} T , identified by ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T ) ) ((x_1,y_1),(x_2,y_2),\ldots,(x_T,y_T)) (( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x T , y T )) for some T ∈ N ∪ { 0 } T \in\mathbb{N} \cup\{0\} T ∈ N ∪ { 0 } , there exists a concept c ∈ C c \in\mathcal{C} c ∈ C such that c ( x i ) = y i c(x_i)=y_i c ( x i ) = y i for every i ∈ [ T ] i \in[T] i ∈ [ T ] .
Definition E.8 (Littlestone dimension, following Littlestone [ [37 ] , Ben-David et al. [ [8 ] ). Let C ⊆ { 0 , 1 } X \mathcal{C} \subseteq\{0,1\}^{\mathcal{X}} C ⊆ { 0 , 1 } X be a concept class. The Littlestone dimension of C \mathcal{C} C , denoted by LD ( C ) ∈ N ∪ { 0 , + ∞ } \operatorname{LD}(\mathcal{C}) \in\mathbb{N} \cup\{0,+\infty\} LD ( C ) ∈ N ∪ { 0 , + ∞ } , is defined by the sup d ∈ N ∪ { 0 } \sup_{d \in\mathbb{N}\cup\{0\}} sup d ∈ N ∪ { 0 } such that, there exists a Littlestone tree of depth d d d for C \mathcal{C} C that is shattered by C \mathcal{C} C . Also, if C = ∅ \mathcal{C}=\varnothing C = ∅ , we have: LD ( C ) = 0 \operatorname{LD}(\mathcal{C})=0 LD ( C ) = 0 .
Online Learning Results
In this section, we study optimal expected regret with deterministic labels for classes with finite diameter. First we show that the optimal expected regret with deterministic labels is always upper bounded by the diameter.
Theorem F.1. Let K ∈ N K \in\mathbb{N} K ∈ N . Any concept class C \mathcal{C} C such that D ( C ) ≤ K D(\mathcal{C}) \le K D ( C ) ≤ K satisfies, for every T ∈ N T \in\mathbb{N} T ∈ N ,
R ⋆ ( C , T ) ≤ K . \mathbf{R}^{\star}(\mathcal{C},T) \le K. R ⋆ ( C , T ) ≤ K . Proof. Fix any concept h 0 ∈ C h_0 \in\mathcal{C} h 0 ∈ C . We consider a learner A \mathcal{A} A that predicts according to h 0 h_0 h 0 on previously unseen instances and memorizes the labels of previously observed instances. Formally, for any T ∈ N T \in\mathbb{N} T ∈ N , any history S ∈ ⋃ t = 0 T − 1 ( X × Y ) t S \in\bigcup_{t=0}^{T-1}(\mathcal{X} \times\mathcal{Y})^t S ∈ ⋃ t = 0 T − 1 ( X × Y ) t , and any x ∈ X x \in\mathcal{X} x ∈ X , define
A ( T , S , x ) = { y if ( x , y ) ∈ S , h 0 ( x ) o.w. \mathcal{A}(T,S,x)=
\begin{cases}
y & \text{if } (x,y) \in S,\\
h_0(x) & \text{o.w.}
\end{cases} A ( T , S , x ) = { y h 0 ( x ) if ( x , y ) ∈ S , o.w. Now fix any comparator h ⋆ ∈ C h^{\star} \in\mathcal{C} h ⋆ ∈ C and any deterministic labeling function f ⋆ f^{\star} f ⋆ . Suppose that on some round the comparator is correct, but A \mathcal{A} A is not; that is, h ⋆ ( x ) = f ⋆ ( x ) h^{\star}(x)=f^{\star}(x) h ⋆ ( x ) = f ⋆ ( x ) while A \mathcal{A} A predicts incorrectly on x x x . Since A \mathcal{A} A memorizes labels, this can only happen the first time x x x appears. Moreover, on such a first occurrence, A \mathcal{A} A predicts h 0 ( x ) h_0(x) h 0 ( x ) , so we must have h 0 ( x ) ≠ h ⋆ ( x ) h_0(x) \ne h^{\star}(x) h 0 ( x ) = h ⋆ ( x ) . Therefore, every such excess-mistake round can be charged to a distinct point in h 0 △ h ⋆ h_0 \triangle h^{\star} h 0 △ h ⋆ . Hence the regret with respect to h ⋆ h^{\star} h ⋆ is at most
∣ h 0 △ h ⋆ ∣ ≤ D ( C ) ≤ K . \lvert h_0 \triangle h^{\star}\rvert\le D(\mathcal{C}) \le K. ∣ h 0 △ h ⋆ ∣ ≤ D ( C ) ≤ K . Since this holds for every h ⋆ ∈ C h^{\star} \in\mathcal{C} h ⋆ ∈ C , every deterministic labeling function, and every sequence of instances, we conclude that
R ⋆ ( C , T ) ≤ K . \mathbf{R}^{\star}(\mathcal{C},T) \le K. R ⋆ ( C , T ) ≤ K . This completes the proof. □ \square □
We then show that, for every K K K , there exists a concept class with Littlestone dimension 1 and diameter 2 K 2K 2 K such that the optimal expected regret under deterministic labels is Ω ( K ) \Omega(K) Ω ( K ) for sufficiently large T T T . This shows that, in contrast to our batch learning results, the dependence of regret of Littlestone classes on K K K cannot be improved. Our proof relies on the anti-concentration bound for Binomial distributions stated in Lemma F.2.
Lemma F.2 (Lemma 4.7.2 of Ash [ [3 ] ). Let X X X be a Binomial random variable with parameters K ∈ N K \in\mathbb{N} K ∈ N and p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , for any integer t ≥ K p t \ge Kp t ≥ K p we have
Pr [ X ≥ t ] ≥ K 8 t ( K − t ) exp ( − K D K L ( t K ∥ p ) ) \Pr[X \ge t] \ge\sqrt{\frac{K}{8t(K-t)}} \exp\left(-K D_{\mathrm{KL}}\left(\frac{t}{K}\middle\|p\right)\right) Pr [ X ≥ t ] ≥ 8 t ( K − t ) K exp ( − K D KL ( K t p ) )
where D K L ( q ∥ p ) : = q ln q p + ( 1 − q ) ln 1 − q 1 − p D_{\mathrm{KL}}(q\|p) := q\ln\frac{q}{p} + (1-q)\ln\frac{1-q}{1-p} D KL ( q ∥ p ) := q ln p q + ( 1 − q ) ln 1 − p 1 − q is the KL divergence of Bernoulli random variables with parameters q q q and p p p .
Theorem F.3. For every K ∈ N K \in\mathbb{N} K ∈ N , there exists a concept class C \mathcal{C} C such that LD ( C ) = 1 \operatorname{LD}(\mathcal{C}) = 1 LD ( C ) = 1 and D ( C ) = 2 K D(\mathcal{C}) = 2K D ( C ) = 2 K , and for every T ≥ K T \ge K T ≥ K ,
R ⋆ ( C , T ) ≥ ⌊ 1 4 min { 2 K ln ( T 4 K K ) , K } ⌋ . R^{\star}(\mathcal{C},T) \ge\left\lfloor\frac{1}{4}\min\left\{2\sqrt{K\ln\left(\frac{T}{4K\sqrt{K}}\right)},K\right\}\right\rfloor. R ⋆ ( C , T ) ≥ ⌊ 4 1 min { 2 K ln ( 4 K K T ) , K } ⌋ . In particular, for T ≥ 4 K K exp ( K ) T \ge4K\sqrt{K}\exp(\sqrt{K}) T ≥ 4 K K exp ( K ) , we have
R ⋆ ( C , T ) ≥ ⌊ K 4 ⌋ . R^{\star}(\mathcal{C},T) \ge\left\lfloor\frac{K}{4}\right\rfloor. R ⋆ ( C , T ) ≥ ⌊ 4 K ⌋ .
Proof. Consider the concept class C = { h i ∣ i ∈ N ∪ { 0 } } \mathcal{C} = \{h_i \mid i \in\mathbb{N}\cup\{0\}\} C = { h i ∣ i ∈ N ∪ { 0 }} over the natural numbers, where for every x ∈ N x \in\mathbb{N} x ∈ N ,
h i ( x ) : = 1 { x ∈ [ ( i − 1 ) K + 1 , K i ] } for i ∈ N , h 0 ( x ) : = 0. h_i(x) := \mathbb{1}\{x \in[(i-1)K+1,Ki]\}\quad\text{for }i\in\mathbb{N},\qquad h_0(x):=0. h i ( x ) := 1 { x ∈ [( i − 1 ) K + 1 , K i ]} for i ∈ N , h 0 ( x ) := 0.
Clearly, LD ( C ) = 1 \operatorname{LD}(\mathcal{C})=1 LD ( C ) = 1 and D ( C ) = 2 K D(\mathcal{C})=2K D ( C ) = 2 K . Choose S = { ( 1 , y 1 ) , ( 2 , y 2 ) , … , ( T , y T ) } S=\{(1,y_1),(2,y_2),\ldots,(T,y_T)\} S = {( 1 , y 1 ) , ( 2 , y 2 ) , … , ( T , y T )} , where y t y_t y t is drawn i.i.d. from a Bernoulli distribution with parameter 1 2 \frac{1}{2} 2 1 . Note that for every t ∈ [ T ] t\in[T] t ∈ [ T ] and every y ∈ { 0 , 1 } y\in\{0,1\} y ∈ { 0 , 1 } , we have Pr [ y ≠ y t ] = 1 / 2 \Pr[y\ne y_t]=1/2 Pr [ y = y t ] = 1/2 . Therefore, every learner A \mathrm{A} A satisfies
E S [ M ‾ ( A ; S ) ] = T 2 . (13) \mathbb{E}_{S}\left[\overline{M}(\mathrm{A};S)\right]=\frac{T}{2}. \tag*{(13)} E S [ M ( A ; S ) ] = 2 T . (13)
We then attempt to derive a lower bound for
inf i ∈ N ∪ { 0 } ∑ t = 1 T 1 [ h i ( x t ) ≠ y t ] . \inf_{i\in\mathbb{N}\cup\{0\}}\sum_{t=1}^{T}\mathbb{1}[h_i(x_t)\ne y_t]. i ∈ N ∪ { 0 } inf t = 1 ∑ T 1 [ h i ( x t ) = y t ] .
Denote m : = ⌊ T K ⌋ m:=\left\lfloor\frac{T}{K}\right\rfloor m := ⌊ K T ⌋ , and for every i ∈ [ m ] i\in[m] i ∈ [ m ] , denote Z i = ∑ t = ( i − 1 ) K + 1 i K y t Z_i=\sum_{t=(i-1)K+1}^{iK}y_t Z i = ∑ t = ( i − 1 ) K + 1 i K y t . Then observe that the all-zero function h 0 h_0 h 0 makes ∑ t = 1 T y t \sum_{t=1}^{T}y_t ∑ t = 1 T y t mistakes. For every i ∈ [ m ] i\in[m] i ∈ [ m ] , the function h i h_i h i makes the same predictions as h 0 h_0 h 0 , except on [ ( i − 1 ) K + 1 , K i ] [(i-1)K+1,Ki] [( i − 1 ) K + 1 , K i ] . On this block, h 0 h_0 h 0 makes Z i Z_i Z i mistakes, while h i h_i h i makes K − Z i K-Z_i K − Z i mistakes. Therefore, in total, h i h_i h i makes
∑ t = 1 T y t − Z i + ( K − Z i ) = ∑ t = 1 T y t + K − 2 Z i \sum_{t=1}^{T}y_t-Z_i+(K-Z_i)=\sum_{t=1}^{T}y_t+K-2Z_i t = 1 ∑ T y t − Z i + ( K − Z i ) = t = 1 ∑ T y t + K − 2 Z i
mistakes. This implies that
inf i ∈ N ∪ { 0 } ∑ t = 1 T 1 [ h i ( x t ) ≠ y t ] ≤ min i ∈ { 0 , 1 , … , m } ∑ t = 1 T 1 [ h i ( x t ) ≠ y t ] = ∑ t = 1 T y t − max ( 2 max i ∈ [ m ] Z i − K , 0 ) . \inf_{i\in\mathbb{N}\cup\{0\}}\sum_{t=1}^{T}\mathbb{1}[h_i(x_t)\ne y_t]\le\min_{i\in\{0,1,\ldots,m\}}\sum_{t=1}^{T}\mathbb{1}[h_i(x_t)\ne y_t]
=\sum_{t=1}^{T}y_t-\max\left(2\max_{i\in[m]}Z_i-K,0\right). i ∈ N ∪ { 0 } inf t = 1 ∑ T 1 [ h i ( x t ) = y t ] ≤ i ∈ { 0 , 1 , … , m } min t = 1 ∑ T 1 [ h i ( x t ) = y t ] = t = 1 ∑ T y t − max ( 2 i ∈ [ m ] max Z i − K , 0 ) .
Thus,
E S [ inf i ∈ N ∪ { 0 } ∑ t = 1 T 1 [ h i ( x t ) ≠ y t ] ] ≤ T 2 − E S [ max ( 2 max i ∈ [ m ] Z i − K , 0 ) ] . \mathbb{E}_{S}\left[\inf_{i\in\mathbb{N}\cup\{0\}}\sum_{t=1}^{T}\mathbb{1}[h_i(x_t)\ne y_t]\right]\le\frac{T}{2}-\mathbb{E}_{S}\left[\max\left(2\max_{i\in[m]}Z_i-K,0\right)\right]. E S [ i ∈ N ∪ { 0 } inf t = 1 ∑ T 1 [ h i ( x t ) = y t ] ] ≤ 2 T − E S [ max ( 2 i ∈ [ m ] max Z i − K , 0 ) ] .
Combining with Equation (13) we get
E S [ M ‾ ( A ; S ) − inf i ∈ N ∑ t = 1 T 1 [ h i ( x t ) ≠ y t ] ] ≥ E S [ max ( 2 max i ∈ [ m ] Z i − K , 0 ) ] . (14) \mathbb{E}_{S}\left[\overline{M}(\mathrm{A};S)-\inf_{i\in\mathbb{N}}\sum_{t=1}^{T}\mathbb{1}[h_i(x_t)\ne y_t]\right]\ge\mathbb{E}_{S}\left[\max\left(2\max_{i\in[m]}Z_i-K,0\right)\right]. \tag*{(14)} E S [ M ( A ; S ) − i ∈ N inf t = 1 ∑ T 1 [ h i ( x t ) = y t ] ] ≥ E S [ max ( 2 i ∈ [ m ] max Z i − K , 0 ) ] . (14)
We now lower bound the right-hand side. Applying Lemma F.2 , and for every i ∈ [ m ] i\in[m] i ∈ [ m ] and every integer r r r such that 0 ≤ r ≤ K 4 0\le r\le\frac{K}{4} 0 ≤ r ≤ 4 K , we derive
p r : = Pr [ Z i ≥ K 2 + r ] ≥ K 8 r ( K − r ) exp ( − K D K L ( 1 2 + r K ∥ 1 2 ) ) ≥ 1 2 K exp ( − K D K L ( 1 2 + r K ∥ 1 2 ) ) \begin{aligned}
p_r:=\Pr\left[Z_i\ge\frac{K}{2}+r\right]\ge\sqrt{\frac{K}{8r(K-r)}}\exp\left(-K D_{\mathrm{KL}}\left(\frac{1}{2}+\frac{r}{K}\middle\|\frac{1}{2}\right)\right) \\
&\ge\frac{1}{2\sqrt{K}}\exp\left(-K D_{\mathrm{KL}}\left(\frac{1}{2}+\frac{r}{K}\middle\|\frac{1}{2}\right)\right)
\end{aligned} p r := Pr [ Z i ≥ 2 K + r ] ≥ 8 r ( K − r ) K exp ( − K D KL ( 2 1 + K r 2 1 ) ) ≥ 2 K 1 exp ( − K D KL ( 2 1 + K r 2 1 ) )
Using the elementary inequality D K L ( 1 2 + x ∥ 1 2 ) ≤ 4 x 2 D_{\mathrm{KL}}\left(\frac{1}{2}+x\middle\|\frac{1}{2}\right)\le4x^2 D KL ( 2 1 + x 2 1 ) ≤ 4 x 2 for x ≤ 1 4 x\le\frac{1}{4} x ≤ 4 1 , we get
Pr [ Z i ≥ K 2 + r ] ≥ 1 2 K exp ( − 4 r 2 K ) . \Pr\left[Z_i\ge\frac{K}{2}+r\right]\ge\frac{1}{2\sqrt{K}}\exp\left(-\frac{4r^2}{K}\right). Pr [ Z i ≥ 2 K + r ] ≥ 2 K 1 exp ( − K 4 r 2 ) .
Set r : = ⌊ 1 4 min { 2 K ln ( m 2 K ) , K } ⌋ r:=\left\lfloor\frac{1}{4}\min\left\{2\sqrt{K\ln\left(\frac{m}{2\sqrt{K}}\right)},K\right\}\right\rfloor r := ⌊ 4 1 min { 2 K ln ( 2 K m ) , K } ⌋ . Then,
4 r 2 K ≤ ln ( m 2 K ) \frac{4r^2}{K}\le\ln\left(\frac{m}{2\sqrt{K}}\right) K 4 r 2 ≤ ln ( 2 K m )
This implies p r ≥ m − 1 p_r\ge m^{-1} p r ≥ m − 1 . Therefore,
Pr [ max i ∈ [ m ] Z i ≥ K 2 + r ] = 1 − ( 1 − p r ) m ≥ 1 − e − m p r ≥ 1 − e − 1 ≥ 1 2 . \Pr\left[\max_{i\in[m]}Z_i\ge\frac{K}{2}+r\right]=1-(1-p_r)^m\ge1-e^{-mp_r}\ge1-e^{-1}\ge\frac{1}{2}. Pr [ i ∈ [ m ] max Z i ≥ 2 K + r ] = 1 − ( 1 − p r ) m ≥ 1 − e − m p r ≥ 1 − e − 1 ≥ 2 1 .
This indicates that
E [ max i ∈ [ m ] ( 2 max Z i − K , 0 ) ] ≥ 1 2 ⋅ 2 r + 1 2 ⋅ 0 = r \mathbb{E}\left[\max_{i\in[m]}(2\max Z_i-K,0)\right]\ge\frac{1}{2}\cdot2r+\frac{1}{2}\cdot0=r E [ i ∈ [ m ] max ( 2 max Z i − K , 0 ) ] ≥ 2 1 ⋅ 2 r + 2 1 ⋅ 0 = r
Plugging this into Equation (14) , for every learner A \mathsf{A} A we get
E S [ M ‾ ( A ; S ) − inf i ∈ H ∑ t = 1 T 1 [ h i ( x t ) ≠ y t ] ] ≥ r ≥ ⌊ 1 4 min { 2 K ln ( T 4 K K ) , K } ⌋ \mathbb{E}_{S}\left[\overline{M}(\mathsf{A};S)-\inf_{i\in\mathcal{H}}\sum_{t=1}^{T}\mathbb{1}[h_i(x_t)\ne y_t]\right]\ge r\ge\left\lfloor\frac{1}{4}\min\left\{2\sqrt{K\ln\left(\frac{T}{4K\sqrt{K}}\right)},K\right\}\right\rfloor E S [ M ( A ; S ) − i ∈ H inf t = 1 ∑ T 1 [ h i ( x t ) = y t ] ] ≥ r ≥ ⌊ 4 1 min { 2 K ln ( 4 K K T ) , K } ⌋
Where the second in equality is due the fact that for T ≥ K T\ge K T ≥ K , we have m ≥ T 2 K m\ge\frac{T}{2K} m ≥ 2 K T . This implies that, for every learner A \mathsf{A} A there exists a sequence S S S such that
R ( A ; S , C ) ≥ ⌊ 1 4 min { 2 K ln ( T 4 K K ) , K } ⌋ , \mathsf{R}(\mathsf{A};S,\mathcal{C})\ge\left\lfloor\frac{1}{4}\min\left\{2\sqrt{K\ln\left(\frac{T}{4K\sqrt{K}}\right)},K\right\}\right\rfloor, R ( A ; S , C ) ≥ ⌊ 4 1 min { 2 K ln ( 4 K K T ) , K } ⌋ ,
which completes the proof.
Useful Theorems
Lemma G.1 (Multiplicative Chernoff bounds Motwani and Raghavan [ [41 ] ). Let X 1 , … , X m X_1,\ldots,X_m X 1 , … , X m be independent random variables drawn according to some distribution D D D with mean p p p and support included in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Then, for any γ ∈ [ 0 , 1 p − 1 ] \gamma\in\left[0,\frac{1}{p}-1\right] γ ∈ [ 0 , p 1 − 1 ] , the following inequality holds for p ^ = 1 m ∑ i = 1 m X i \hat{p}=\frac{1}{m}\sum_{i=1}^{m}X_i p ^ = m 1 ∑ i = 1 m X i :
P [ p ^ ≥ ( 1 + γ ) p ] ≤ e − m p γ 2 3 \mathbb{P}[\hat{p}\ge(1+\gamma)p]\le e^{-\frac{mp\gamma^2}{3}} P [ p ^ ≥ ( 1 + γ ) p ] ≤ e − 3 m p γ 2 P [ p ^ ≤ ( 1 − γ ) p ] ≤ e − m p γ 2 2 \mathbb{P}[\hat{p}\le(1-\gamma)p]\le e^{-\frac{mp\gamma^2}{2}} P [ p ^ ≤ ( 1 − γ ) p ] ≤ e − 2 m p γ 2
Theorem G.2 (Hoeffding Inequality Hoeffding [ [32 ] ). Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be independent random variables such that a i ≤ X i ≤ b i a_i\le X_i\le b_i a i ≤ X i ≤ b i almost surely. Consider the sum of variables,
S n = X 1 + ⋯ + X n S_n=X_1+\cdots+X_n S n = X 1 + ⋯ + X n Then Hoeffding’s theorem states that, for all t > 0 t>0 t > 0 ,
Pr ( ∣ S n − E [ S n ] ∣ ≥ t ) ≤ 2 exp ( − 2 t 2 ∑ i = 1 n ( b i − a i ) 2 ) \Pr\left(\lvert S_n-\mathbb{E}[S_n]\rvert\ge t\right)\le2\exp\left(-\frac{2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right) Pr ( ∣ S n − E [ S n ]∣ ≥ t ) ≤ 2 exp ( − ∑ i = 1 n ( b i − a i ) 2 2 t 2 )
Lemma G.3 (Sedrakyan inequality Sedrakyan [ [45 ] , Sedrakyan and Sedrakyan [2018]). Let a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a 1 , a 2 , … , a n be real numbers and b 1 , b 2 , … , b n b_1,b_2,\ldots,b_n b 1 , b 2 , … , b n positive real numbers. Then
a 1 2 b 1 + ⋯ + a n 2 b n ≥ ( a 1 + ⋯ + a n ) 2 b 1 + ⋯ + b n \frac{a_1^2}{b_1}+\cdots+\frac{a_n^2}{b_n}\ge\frac{(a_1+\cdots+a_n)^2}{b_1+\cdots+b_n} b 1 a 1 2 + ⋯ + b n a n 2 ≥ b 1 + ⋯ + b n ( a 1 + ⋯ + a n ) 2