pith. sign in

arxiv: 1507.00473 · v4 · pith:RAXLUIHUnew · submitted 2015-07-02 · 💻 cs.LG · stat.ML

The Optimal Sample Complexity of PAC Learning

Steve Hanneke This is my paper
classification 💻 cs.LG stat.ML
keywords learningboundcomplexitysampleanalysisboundsbreakthroughbuild
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Assessing Trustworthiness of AI Training Dataset using Subjective Logic -- A Use Case on Bias

    cs.LG 2025-08 unverdicted novelty 6.0

    Presents the first formal Subjective Logic framework for uncertainty-aware assessment of dataset-level trustworthiness properties such as bias, evaluated on a traffic sign recognition dataset in centralized and federa...