betaFeedback

WorksMathematics

Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

Abstract

We study the problem of agnostic PAC learning under deterministic labels, where the examples are labeled by an arbitrary deterministic function, which need not belong to the concept class CC. This model captures misspecification without stochastic label noise and lies between the realizable and fully agnostic settings. Prior work showed that, when CC has finite diameter KK and VC dimension dd, deterministic labels can improve the sample complexity upper bound from the classical agnostic guarantee O(d/ε2)O(d/\varepsilon^2) to O~(K/ε)\widetilde{O}(K/\varepsilon), but left a large gap between upper and lower bounds. Our main result sharpens this picture. We prove that every class of VC dimension dd and finite diameter KK is learnable with sample complexity O~(K1/3 d2/3ε)\widetilde{O}\left( \frac{K^{1/3} \, d^{2/3}}{\varepsilon} \right), and we construct classes for which this bound is tight up to logarithmic factors. We also study the online analogue of this problem and show that the minimax regret is again partly controlled by the diameter of the class. Technically, our upper bounds are obtained via memorization-based learning algorithms that exploit the deterministic label structure.

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} over X×Y\mathcal{X} \times\mathcal{Y}, where X\mathcal{X} is an instance space and Y\mathcal{Y} is a binary label space. 1 For example, X\mathcal{X} may be a space of medical images, and Y={0,1}\mathcal{Y} = \{0,1\} may be the binary label space, where y=1y = 1 indicates that the corresponding image shows a certain abnormality and y=0y = 0 indicates that it does not. In addition, this framework fixes a concept class CC, consisting of functions from the instance space X\mathcal{X} to the label space Y\mathcal{Y}, which serves as a benchmark family of classifiers. For instance, CC 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}, the learner’s goal is to output a hypothesis h^:X→Y\hat{h} : \mathcal{X} \to\mathcal{Y} whose classification error on future examples also drawn from D\mathcal{D} is, with high probability, close to that of the best concept in C\mathcal{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⋆∈Cc^{\star} \in\mathcal{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} but allow stochastic label noise of restricted severity. Another natural intermediate assumption is that the Bayes-optimal classifier belongs to C\mathcal{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→Yf^{\star} : \mathcal{X} \to\mathcal{Y} specifying the label of each instance; however, f⋆f^{\star} need not belong to the concept class C\mathcal{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} is restricted to belong to a fixed class H\mathcal{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}. 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}}, how many training samples are necessary and sufficient for agnostically PAC learning C\mathcal{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}, denoted by D(C)\mathrm{D}(\mathcal{C}), is infinite, then the optimal sample complexity of agnostically PAC learning C\mathcal{C} under deterministic labels admits a lower bound of Ω(log⁡(1/δ)/ε2)\Omega\left(\log(1/\delta)/\varepsilon^{2}\right). Moreover, they showed that, for every d∈Nd \in\mathbb{N}, there exists a concept class C\mathcal{C} whose Vapnik–Chervonenkis dimension, denoted by VC(C)\mathrm{VC}(\mathcal{C}), equals dd, 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). 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}) is finite, they proved an upper bound of O~(D(C)/ε)\widetilde{O}(\mathrm{D}(\mathcal{C})/\varepsilon), while the only known lower bound is the standard realizable PAC learning lower bound Ehrenfeucht et al. [ [22], namely Ω(VC(C)/ε+log⁡(1/δ)/ε)\Omega\left(\mathrm{VC}(\mathcal{C})/\varepsilon+\log(1/\delta)/\varepsilon\right) for non-trivial concept classes C\mathcal{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}} be a non-degenerate concept class with d:=VC⁡(C)<∞d := \operatorname{VC}(\mathcal{C}) < \infty and K:=D⁡(C)<∞K := \operatorname{D}(\mathcal{C}) < \infty. Then, the following holds.

mC(ε,δ)∈Ω(K1/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),
mC(ε,δ)∈O~(K1/3d2/3+K1/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).

Moreover, for some finite K0K_0, for every d∈Nd \in\mathbb{N} and every K≥max⁡{K0,d}K \geq\max\{K_0,d\}, there exists a concept class C⊆{0,1}X\mathcal{C} \subseteq\{0,1\}^{\mathcal{X}} with VC⁡(C)=d\operatorname{VC}(\mathcal{C}) = d and K=D⁡(C)K = \operatorname{D}(\mathcal{C}) for which the above upper bound is tight. Namely:

mC(ε,δ)∈Ω(K1/3d2/3+K1/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).

Here, mCm_{\mathcal{C}} denotes the optimal sample complexity of agnostically PAC learning C\mathcal{C} under deterministic labels; see Definition 2.2 for the formal definition. In addition, we use O~(⋅)\widetilde{O}(\cdot) to hide poly-logarithmic factors. Also, for any a,b∈Ra,b \in\mathbb{R}, we use the notation a∧b:=min⁡{a,b}a \wedge 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}XC \subseteq\{0,1\}^{\mathcal{X}} be a concept class with K:=D(C)<∞K := D(C) < \infty. Then, we have:

R⋆(C,T)∈O(K).R^{\star}(C,T) \in O(K).

Moreover, for every K∈NK \in\mathbb{N}, there exists a concept class C⊆{0,1}XC \subseteq\{0,1\}^{\mathcal{X}} with D(C)=KD(C) = K and LD⁡(C)=1\operatorname{LD}(C) = 1 for which we have:

R⋆(C,T)∈Ω(K).R^{\star}(C,T) \in\Omega(K).

Here, R⋆(C,T)R^{\star}(C,T) denotes the minimax expected regret as a function of the concept class CC and the time horizon TT, and LD⁡(C)\operatorname{LD}(C) denotes the Littlestone dimension of CC; 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/ε21/\varepsilon^2-term in our upper bound in the infinite-diameter regime.

Theorem 1.3. Let C⊆{0,1}XC \subseteq\{0,1\}^{\mathcal{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. Then, there exists a constant k⋆∈N∪{0}k^{\star} \in\mathbb{N} \cup\{0\}, possibly depending on CC, for which the following holds.

mC(ε,δ)=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).

Moreover, the lower bound of Ben-David and Urner [ [7] implies

mC(ε,δ)=Ω~(SET-VC⁡(C)ε2).m_C(\varepsilon,\delta) = \widetilde{\Omega}\left(\frac{\operatorname{SET\text{-}VC}(C)}{\varepsilon^2}\right).

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 CC such that SET-VC⁡(C)≠PERT-VC⁡(C)\operatorname{SET\text{-}VC}(C) \ne\operatorname{PERT\text{-}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} and R\mathbb{R} stand for the set of natural numbers and real numbers, respectively. In addition, for a given n∈Nn \in\mathbb{N}, we use [n][n] to denote {1,2,…,n}\{1, 2, \ldots, n\}. For any a,b∈Ra,b \in\mathbb{R}, we use the notation a∧b:=min⁡{a,b}a \wedge b := \min\{a,b\}. Also, for a,b∈Na,b \in\mathbb{N}, we write a∣ba \mid b if aa divides bb, that is, if there exists m∈Nm \in\mathbb{N} such that b=amb = am. Next, given n∈Nn \in\mathbb{N}, for any sequence of size nn or nn-tuple vv, and any i∈[n]i \in[n], let us use viv_i to denote the ii-th element in vv. Afterward, we denote by A×BA \times B the Cartesian product of two arbitrary sets AA and BB. In addition, for any set AA and any n∈Nn \in\mathbb{N}, we let AnA^n indicate nn times the Cartesian product of AA with itself. Note that for any set AA, we define A0:={∅}A^0 := \{\emptyset\}. Also, given a set AA, we denote by A∗A^* the set of all finite sequences of members of AA; more formally, A∗:=⋃T=0∞ATA^* := \bigcup_{T=0}^{\infty} A^T. Then, for arbitrary sets XX and YY, we use YXY^X to denote the space of all functions from XX to YY. Going further, let ee and log⁡(⋅)\log(\cdot) stand for Euler’s number and the Logarithm function in the base 2, respectively. Finally, we use O(⋅)O(\cdot), Ω(⋅)\Omega(\cdot), and Θ(⋅)\Theta(\cdot) to denote the standard asymptotic notation in theoretical computer science. Furthermore, we use O~(⋅)\widetilde{O}(\cdot), Ω~(⋅)\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}}), referred to as the instance space. For example, the instance space X\mathcal{X} can be a Euclidean space. In addition, fix Y={0,1}\mathcal{Y} = \{0,1\} as the label space. A concept is a measurable function from X\mathcal{X} to Y\mathcal{Y}. With this in mind, fix a non-empty collection of such functions C\mathcal{C} as the concept class. For simplicity, we specify instances of the PAC learning framework solely based on the concept class C\mathcal{C}, which is defined relative to the measurable structure (X,ΣX)(\mathcal{X}, \Sigma_{\mathcal{X}}).

References

  1. [1]Ibrahim Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal PAC bounds without uniform convergence. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1203–1223. IEEE Computer Society, 2023.
  2. [2]Ishaq Aden-Ali, Mikael Møller Hø̄ndgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. Majority-of-three: The simplest optimal learner? In The Thirty Seventh Annual Conference on Learning Theory, pages 22–45. PMLR, 2024.
  3. [3]Robert B Ash. Information theory. Courier Corporation, 1990.
  4. [4]Sajad Rahmanian Ashkezari and Ruth Urner. Refining the sample complexity of comparative learning. In 36th International Conference on Algorithmic Learning Theory, 2025.
  5. [5]Peter Auer and Ronald Ortner. A new pac bound for intersection-closed concept classes. Machine Learning, 66(2):151–163, 2007.
  6. [6]Shai Ben-David and Ami Litman. Combinatorial variability of vapnik-chervonenkis classes with applications to sample compression schemes. Discrete Applied Mathematics, 86(1):3–25, 1998.
  7. [7]Shai Ben-David and Ruth Urner. The sample complexity of agnostic learning under deterministic labels. In Conference on Learning Theory, pages 527–542. PMLR, 2014.
  8. [8]Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, volume 3, page 1, 2009.
  9. [9]Shalev Ben-David and Shai Ben-David. Learning a classifier when the labeling is known. In International Conference on Algorithmic Learning Theory, pages 440–451. Springer, 2011.
  10. [10]Daniel Berend and Aryeh Kontorovich. On the concentration of the missing mass. Electronic Communications in Probability, 18(none):1–7, 2013. doi: 10.1214/ECP.v18-2359.DOI
  11. [11]Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning, volume 4. Springer, 2006.
  12. [12]Moise Blanchard, Steve Hanneke, and Patrick Jaillet. Contextual bandits and optimistically universal learning. arXiv preprint arXiv:2301.00241, 2022.arxiv.org/abs/2301.00241
  13. [13]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929–965, 1989.DOI
  14. [14]Olivier Bousquet and Nikita Zhivotovskiy. Fast classification rates without standard margin assumptions. Information and Inference: A Journal of the IMA, 10(4):1389–1421, 12 2021. ISSN 2049-8772. doi: 10.1093/imaiai/iaab010.DOI
  15. [15]Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal svm bound. In Conference on Learning Theory, pages 582–609. PMLR, 2020.arxiv.org/abs/2005.11818
  16. [16]Leo Breiman. Bagging predictors. Machine learning, 24(2):123–140, 1996.
  17. [17]Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When is memorization of irrelevant training data necessary for high-accuracy learning? In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 123–132, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380539. doi: 10.1145/3406325.3451131.DOI
  18. [18]Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX security symposium (USENIX Security 21), pages 2633–2650, 2021.arxiv.org/abs/2012.07805
  19. [19]Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Seh­wag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In 32nd USENIX security symposium (USENIX Security 23), pages 5253–5270, 2023.arxiv.org/abs/2301.13188
  20. [20]N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. ISBN 9781139454827.
  21. [21]Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation, volume 1. Springer, 2001.
  22. [22]Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247–261, 1989.
  23. [24]Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in neural information processing systems, 33:2881–2891, 2020.arxiv.org/abs/2008.03703
  24. [25]Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing, 39(2):606–645, 2009.DOI
  25. [26]Vitaly Feldman, Guy Kornowski, and Xin Liu. Trade-offs in data memorization via strong data processing inequalities. arXiv preprint arXiv:2506.01855, 2025.arxiv.org/abs/2506.01855
  26. [27]Steve Hanneke. The optimal sample complexity of pac learning. Journal of Machine Learning Research, 17(38):1–15, 2016.arxiv.org/abs/1507.00473
  27. [28]Steve Hanneke. Agnostic active learning is always better than passive learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2026.DOI
  28. [29]D Haussler and E Welzl. Epsilon-nets and simplex range queries. In Proceedings of the Second Annual Symposium on Computational Geometry, SCG ’86, page 61–71, New York, NY, USA, 1986. Association for Computing Machinery. ISBN 0897911946. doi: 10.1145/10515.10522.DOI
  29. [30]David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992.
  30. [31]David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0, 1}-functions on randomly drawn points. Information and Computation, 115(2):248–292, 1994.
  31. [32]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409–426, 1994.
  32. [33]Max Hopkins, Daniel M Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. In Conference on Learning Theory, pages 3015–3069. PMLR, 2022.DOI
  33. [34]Lunjia Hu and Charlotte Peale. Comparative learning: A sample complexity theory for two hypothesis classes. arXiv preprint arXiv:2211.09101, 2022.arxiv.org/abs/2211.09101
  34. [35]Michael J Kearns, Robert E Schapire, and Linda M Sellie. Toward efficient agnostic learning. In Proceedings of the fifth annual workshop on Computational learning theory, pages 341–352, 1992.
  35. [36]Kasper Green Larsen. Bagging is an optimal pac learner. In The Thirty Sixth Annual Conference on Learning Theory, pages 450–468. PMLR, 2023.arxiv.org/abs/2212.02264
  36. [37]Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285–318, 1988.
  37. [38]Enno Mammen and Alexandre B. Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6):1808 – 1829, 1999. doi: 10.1214/aos/1017939240.DOI
  38. [39]Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 (5):2326 – 2366, 2006. doi: 10.1214/009053606000000786.DOI
  39. [40]David McAllester and Luis Ortiz. Concentration inequalities for the missing mass and for histogram rule error. Journal of Machine Learning Research, 4(Oct):895–911, 2003.
  40. [41]Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. ACM Computing Surveys (CSUR), 28(1):33–37, 1996.
  41. [42]Milad Nasr, Javier Rando, Nicholas Carlini, Jonathan Hayase, Matthew Jagielski, A Feder Cooper, Daphne Ippolito, Christopher A Choquette-Choo, Florian Tramèr, and Katherine Lee. Scalable extraction of training data from aligned, production language models. In The Thirteenth International Conference on Learning Representations, 2025.
  42. [43]Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972.DOI
  43. [45]Nairi Sedrakyан. About the applications of one useful inequality. Kvant, (2):42–44, 1997.
  44. [46]Saharon Shelah. A combinatorial problem: stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247–261, 1972.DOI
  45. [47]Hans U Simon. An almost optimal pac algorithm. In Conference on Learning Theory, pages 1552–1563. PMLR, 2015.
  46. [48]M. Talagrand. Sharper Bounds for Gaussian and Empirical Processes. The Annals of Probability, 22(1):28 – 76, 1994. doi: 10.1214/aop/1176988847.DOI
  47. [49]Alexander B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135 – 166, 2004. doi: 10.1214/aos/1079120131.DOI
  48. [50]Ruth Urner and Shai Ben-David. Probabilistic lipschitzness a niceness assumption for deterministic labels. In Learning Faster from Easy Data-Workshop@ NIPS, volume 2, page 1, 2013.
  49. [51]Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
  50. [52]Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974.
  51. [53]Abraham J Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of adaboost and random forests as interpolating classifiers. Journal of Machine Learning Research, 18(48):1–33, 2017.
  52. [54]Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.arxiv.org/abs/1611.03530

Paper details

vlnc:W_abkqqmfu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents