Research map / Learning theory and algorithms / Sample complexity
Sample complexity of learning distributions
Derives sample bounds for learning Gaussians, simplices and predictors, including gradient-based algorithms.
101 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.
26 papers in 2023–24 and 22 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 7.8% to 6.7%.
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 · Supervised learning through the lens of compression (NeurIPS 2016 · 19 citations)
- 2017 · Being Robust (in High Dimensions) Can Be Practical (ICML 2017 · 68 citations)
- 2018 · Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes (NeurIPS 2018 · 32 citations)
- 2019 · Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation (NeurIPS 2019 · 54 citations)
- 2020 · Efficient Learning of Discrete Graphical Models (NeurIPS 2020 · 12 citations)
- 2021 · Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets? (ICLR 2021 · 20 citations)
- 2022 · Towards Bridging Sample Complexity and Model Capacity (AAAI 2022 · 5 citations)
- 2023 · Tree Learning: Optimal Sample Complexity and Algorithms (AAAI 2023 · 2 citations)
- 2024 · On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs) (NeurIPS 2024 · 3 citations)
- 2025 · Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · 0 citations)
- 2026 · Token Sample Complexity of Attention (ICML 2026 · 0 citations)
Earliest papers here
- Supervised learning through the lens of compression (NeurIPS 2016 · 19 citations)
- Being Robust (in High Dimensions) Can Be Practical (ICML 2017 · 68 citations)
- Algorithmic Stability and Hypothesis Complexity (ICML 2017 · 48 citations)
What has been tried
82 papers here report 432 measured changes (a component added, removed or swapped, compared with a baseline): helped 68%, no clear effect 9%, hurt 15%, mixed 8%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Orthogonalize initial hidden weights to have overlap 1 / \sqrt d with the spike | Spiked Wishart and spiked cumulant models · distinguishability | 1 / \sqrt d | No clear effect | Learning from higher-order correlations, efficiently: hypothesis tests, random features, and neural networks (NeurIPS 2024 · 2 citations) |
| Train on low-discrepancy sequence points instead of uniformly random points | Two-dimensional random Heisenberg model, 20–45 qubits · prediction RMSE | No clear effect | Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms (NeurIPS 2024 · 2 citations) | |
| Use K1=4 and K2=3 instead of K1=2 and K2=1 | Synthetic Gaussian Wigner graphs, n=50, ρ=0.99 · Correlation detection performance | Helped | Sample Complexity of Correlation Detection in the Gaussian Wigner Model (ICML 2025 · 0 citations) | |
| Use the input norm ‖x‖₂ rather than only the normalized direction | Gaussian SIM · runtime | d^{{\rm sk}_\star} -> d^{{\rm sk}_\star/2+1} | Helped | Learning single index models via harmonic decomposition (NeurIPS 2025 · 0 citations) |
| Use prior-matched sparse perturbations rather than a polynomial-size cover of the sparse prior | k-sparse prior · sample complexity | \tilde{O}(k^{s^\star} \cdot d / k^2) | Hurt | Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · 0 citations) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 48 papers; from OpenAlex and the papers' affiliations).
- Princeton University · 6 papers
- Massachusetts Institute of Technology · 3 papers
- University of Texas at Austin · 3 papers
- Tel Aviv University · 2 papers
- Weizmann Institute of Science · 2 papers
- George Mason University · 2 papers
- Northwestern University · 2 papers
- Yale University · 2 papers
- Google · 2 papers
- New York University · 2 papers
Use it
Download BibTeX of 40 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
- PAC learnability theory (79 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).