Source-linked AI summary
The Optimal Sample Complexity of PAC Learning
Steve Hanneke
TL;DR
PAC learning requires a finite sample guarantee that holds across target concepts and data distributions, but prior general bounds left a logarithmic gap. This paper builds on Simon’s majority-vote idea with a novel recursive algorithm and proves an upper bound matching known lower bounds up to numerical constant factors. The result resolves the long-standing problem, although the proof’s constants remain large and substantial changes may be needed to improve them substantially.
Problem
Determining the optimal sample complexity of PAC learning remained open because general upper and lower bounds differed by a logarithmic factor.
Method
The paper develops a majority-vote algorithm whose classifiers use recursively specified, substantially overlapping data subsets, building on Simon’s approach.
Results
The new upper bound matches the known lower bound up to numerical constant factors, eliminating the logarithmic factor.
Takeaways & Limitations
The work determines the precise form of optimal PAC sample complexity up to numerical constant factors for general concept spaces.
Takeaways & Limitations
The proof obtains quite large constant factors, and improving them by more than roughly one order of magnitude may require substantial changes to the analysis or algorithm.
Abstract
from arXiv · showhide
This work establishes a new upper bound on the number of samples sufficient for PAC learning in the realizable case. The bound matches known lower bounds up to numerical constant factors. This solves a long-standing open problem on the sample complexity of PAC learning. The technique and analysis build on a recent breakthrough by Hans Simon.
1. Introduction
PAC learning asks how many labeled samples are sufficient to guarantee low error with high probability across all target concepts and data distributions. The paper closes the long-standing logarithmic gap in this sample-complexity question using a majority vote whose classifiers are trained on recursively specified, substantially overlapping data subsets.
- PAC learning requires error at most ε with probability at least 1−δ for every target concept and data distribution.
- The central problem is determining the minimum sample complexity M(ε, δ) sufficient for PAC learning.
- The new algorithm completely eliminates the logarithmic factor separating prior upper and lower bounds.
- Its classifiers are combined by majority vote and trained on recursively specified data subsets with substantial overlap.
2. Notation
The paper formalizes PAC learning over measurable instance and label spaces, a concept class, data distributions, target functions, and consistent classifiers. It assumes a nontrivial concept class with finite VC dimension and allows randomized learning algorithms under specified measurability and asymptotic conventions.
- The instance space X is a nonempty measurable space, the label space is Y = {−1, +1}, and classifiers map X measurably to Y.
- A concept space C is a nonempty set of classifiers, with |C| ≥3 assumed to exclude trivial cases.
- The data distribution P generates independent unlabeled samples, while a target function f⋆ belongs to C and defines classification error.
- Sample complexity M(ε, δ) is the smallest sample size for which some algorithm meets the PAC guarantee uniformly over distributions and target functions.
- For a labeled sequence S, C[S] denotes the classifiers in C consistent with every example in S.
- A sequence is shattered when all 2^k labelings are realized by classifiers in C; the largest such k is the VC dimension d.
- The paper assumes finite VC dimension, permits randomized algorithms with randomness independent of the data, and uses numerical constants independent of C and X in its O-notation.
3. Background
Existing PAC sample-complexity bounds leave a gap between general lower and upper bounds, despite tighter results for restricted concept spaces or distributions. The paper introduces a general upper bound matching the lower bound up to numerical constants, thereby determining the optimal form.
- Known lower bounds combine terms involving VC dimension, accuracy, and confidence, establishing the target asymptotic dependence of M(ε, δ).
- Classical sample-consistent learning algorithms achieve general upper bounds, while modified one-inclusion methods provide sometimes-better bounds.
- Simon’s majority-vote algorithm reduced the logarithmic gap to a very slowly growing iterated-logarithm factor but did not eliminate it.
- Special-case analyses close the gap only under restrictions that exclude commonly studied spaces such as linear separators and multilayer neural networks.
- The paper establishes a novel upper bound valid for any concept space that improves the joint dependence on ε, δ, and d.
- The new upper bound matches the lower bound up to numerical constant factors, determining the precise optimal sample-complexity form.
4. Main Result
The paper introduces a recursive, overlapping-subsample majority-vote algorithm and proves that it achieves the optimal realizable PAC sample complexity, removing the longstanding logarithmic gap.
- The main contribution is a novel learning algorithm together with a proof that it achieves optimal sample complexity.
- 4.1 Sketch of the Approach: The analysis builds on Simon’s argument, which bounds joint mistakes by combining one classifier’s error rate with another’s conditional error rate.
- 4.1 Sketch of the Approach: Unlike Simon’s independent-data construction, the new method recursively creates substantially overlapping subsamples, allowing each classifier to use more data.
- 4.2 Formal Details: The recursive construction partitions a working sample into one smaller core and three blocks, then makes three calls that retain different pairs of blocks.
- 4.2 Formal Details: The resulting classifier is the majority vote of sample-consistent classifiers trained on the recursively generated subsamples.
- 4.3 Proof of Theorem 2: The proof uses an inductive guarantee, a classic generalization bound for consistent classifiers, and a combinatorial argument relating majority-vote mistakes to paired classifier mistakes.
- 4.3 Proof of Theorem 2: Applying the bound with empty auxiliary data shows that Majority(L(A(S; ∅))) achieves the stated sample-complexity expression and hence the main theorem.
5. Remarks
The remarks establish computational efficiency under suitable base learners while noting that the proof’s constant factors remain large and may require substantial changes to improve substantially.
- Computational complexity: The subsample construction is computationally efficient because recursion has branching factor 3, reduces |S0| by roughly a factor of 4, and uses constant-time node operations.The total number of returned subsamples is sublinear in |S|, and indices directly determine subsample membership.
- Computational complexity: The main remaining computational issue is the efficiency of the sample-consistent base learner L.Efficient algorithms are known for several concept spaces, including linear separators.
- Computational complexity: For any concept space C efficiently PAC learnable using a hypothesis space H of VC dimension O(d), the construction yields an efficient PAC learner with optimal sample complexity up to numerical constant factors.This conclusion combines efficient base-learning facts with the recursive subsample construction.
- Constant factors: The proof’s constant factors are quite large, and reducing them by more than roughly one order of magnitude may require significant changes to the analysis or algorithm.Small refinements include enlarging subsequences or using a tighter Chernoff bound.
- Constant factors: The conjecture that the one-inclusion graph prediction algorithm achieves optimal-form sample complexity remains open.That predictor already achieves optimal sample complexity in a closely related expected-error prediction model with a nearly optimal numerical constant.
Appendix A. A Technical Lemma
The appendix introduces a technical lemma that bounds a logarithmic expression by separately controlling its component terms under different parameter regimes.
- Lemma assumptions: The lemma applies to parameters a, b, c1, and c2 with a, b, c1 in [1, ∞) and c2 in [0, ∞).These are the stated parameter ranges for the lemma.
- Case analysis: When a > e, the relevant bound is at most 1, and the proof states that the other case is handled as well.The displayed fragments indicate a case split on a.
- Bounding the expression: The proof bounds the first term by a ln(c1(c2 + 2)) and then by a ln(c1(c2 + e)).This is the explicit upper-bound step shown for the first term.
- Bounding the expression: The second term is rewritten as b ln(b/a) before the remaining case analysis.The supplied proof separates this term from the first-term bound.