Research map / Learning theory and algorithms / Sample complexity
PAC learnability theory
Characterizes learnability and optimal learners beyond classical PAC, including multiclass and collaborative settings.
79 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Sample complexity, keyword cluster “sample complexity · pac · optimal sample”
State History Tried Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
29 papers in 2023–24 and 14 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 8.7% to 4.3%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Lifelong Learning with Weighted Majority Votes (NeurIPS 2016 · 13 citations)
- 2017 · Scanpath Complexity: Modeling Reading Effort Using Gaze Information (AAAI 2017 · 27 citations)
- 2018 · Tight Bounds for Collaborative PAC Learning via Multiplicative Weights (NeurIPS 2018 · 8 citations)
- 2019 · Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models (NeurIPS 2019 · 17 citations)
- 2020 · On the Theory of Transfer Learning: The Importance of Task Diversity (NeurIPS 2020 · 65 citations)
- 2021 · Few-Shot Learning via Learning the Representation, Provably (ICLR 2021 · 53 citations)
- 2022 · Learning single-index models with shallow neural networks (NeurIPS 2022 · 11 citations)
- 2023 · A Parameterized Theory of PAC Learning (AAAI 2023 · 2 citations)
- 2024 · Learning Broadcast Protocols (AAAI 2024 · 4 citations)
- 2025 · Fundamental limits of learning in sequence multi-index models and deep attention networks: high-dimensional asymptotics and sharp thresholds (ICML 2025 · 0 citations)
- 2026 · Universal Multiclass Transductive Online Learning (ICML 2026 · 0 citations)
Earliest papers here
- Lifelong Learning with Weighted Majority Votes (NeurIPS 2016 · 13 citations)
- Multi-step learning and underlying structure in statistical models (NeurIPS 2016 · 1 citation)
- Scanpath Complexity: Modeling Reading Effort Using Gaze Information (AAAI 2017 · 27 citations)
What has been tried
46 papers here report 248 measured changes (a component added, removed or swapped, compared with a baseline): helped 71%, no clear effect 7%, hurt 16%, mixed 6%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Fix first-layer weights to zero | Two-layer attention · prediction error | Hurt | Fundamental limits of learning in sequence multi-index models and deep attention networks: high-dimensional asymptotics and sharp thresholds (ICML 2025 · 0 citations) | |
| Replace independent random rounding with r-wise independent hash rounding | Label-consistent multi-distribution learning · sample complexity | O(k\ln^2(k/(\varepsilon \delta))/\varepsilon^2) -> O(k\ln^3(k/(\varepsilon \delta))/\varepsilon^2) | Hurt | Derandomizing Multi-Distribution Learning (NeurIPS 2024 · 0 citations) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 43 papers; from OpenAlex and the papers' affiliations).
- Purdue University · 7 papers
- University of California, Berkeley · 5 papers
- Google · 5 papers
- Tel Aviv University · 3 papers
- Yale University · 3 papers
- University of Wisconsin - Madison · 2 papers
- University of Washington · 2 papers
- Meta · 2 papers
- Swiss Federal Institute of Technology Lausanne · 2 papers
- Toyota Technological Institute at Chicago · 2 papers
Use it
Download BibTeX of 39 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Sample complexity of learning distributions (101 papers)
- Sample complexity of ranking and selection (80 papers)
- Sample complexity of MDPs (42 papers)
Elsewhere in the topic
- Minimax estimation rates (109 papers)
- Optimal mean estimation and subsampling (95 papers)
- Density and property estimation (86 papers)
- Statistical-query lower bounds (85 papers)
- Computational thresholds in graphs and structure (84 papers)
- Learning halfspaces under noise (84 papers)
- Robust and surrogate-loss learning bounds (83 papers)
- Learning under log-concave distributions (80 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).