Research map / Learning theory and algorithms
Sample complexity: research map
1,553 papers on Sample complexity in Learning theory and algorithms, from ICML, NeurIPS, ICLR, CVPR, AAAI, ICCV and ECCV, and the journals TPAMI, IJCV and JMLR (2016–2026), grouped into 5 clusters and 19 approaches. The busiest year so far is 2024.
What it is
How much data does a learning problem need? This theory topic proves upper and lower bounds on the number of samples required to learn or estimate something to a given accuracy, and asks which problems can be learned efficiently at all.
Terms you will see on this page:
- Sample complexity
- the number of examples needed to reach a target accuracy.
- PAC learning
- probably approximately correct learning, the standard formal model of learnability.
- Minimax rate
- the best accuracy any method can guarantee in the worst case.
Start reading with the most cited papers here:
- The Expressive Power of Neural Networks: A View from the Width (NeurIPS 2017 · 424 citations)
- Efficient Neural Network Robustness Certification with General Activation Functions (NeurIPS 2018 · 332 citations)
Within Learning theory and algorithms, its share held steady from 15.0% in 2023–24 to 13.5% in 2025–26 (334 → 328 papers at ICML, NeurIPS, ICLR, CVPR and AAAI, the venues with data for all four years).
Explore Sample complexity in the interactive map
Working on something in this topic? Describe your idea in scime atlas to see which approach it falls under, the closest papers by meaning and how crowded the spot has become.
What changed recently
Approaches whose share of the topic moved most between 2023–24 and 2025–26 (ICML, NeurIPS, ICLR, CVPR and AAAI):
- Neural network approximation theory rising: 4% → 7% of the topic (14 → 24 papers)
- Statistical-query lower bounds rising: 5% → 7% of the topic (16 → 23 papers)
- Computational thresholds in graphs and structure rising: 4% → 7% of the topic (15 → 22 papers)
- PAC learnability theory falling: 9% → 4% of the topic (29 → 14 papers)
- Robust and surrogate-loss learning bounds falling: 7% → 4% of the topic (25 → 14 papers)
Papers from 2025–2026 that are already cited most:
- Learning Junta Distributions, Quantum Junta States, and QAC$^0$ Circuits (ICML 2026 · 1 citations)
- Approximation and Generalization Abilities of Score-based Neural Network Generative Models for Sub-Gaussian Distributions (NeurIPS 2025 · 0 citations)
- Sample-Adaptivity Tradeoff in On-Demand Sampling (NeurIPS 2025 · 0 citations)
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · 0 citations)
Approaches and key papers
Statistical estimation · 473 papers
Keywords: estimation, estimator, minimax
Approaches in this cluster:
- Minimax estimation rates (131 papers)
Derives optimal risk and rates for parametric and dependent-data estimators. - Optimal mean estimation and subsampling (137 papers)
Develops optimal mean estimators and subsampling or resampling procedures with sharp guarantees. - Density and property estimation (119 papers)
Studies maximum likelihood and profile-likelihood estimators for density, mixtures and distribution properties. - Distributed estimation under communication limits (56 papers)
Derives rates for estimating distributions and means across machines with constrained communication. - Statistical analysis of GAN estimators (30 papers)
Proves error bounds for GANs and neural estimators via adversarial losses and duality.
Most cited and most cited since 2024:
- Fast Fourier Color Constancy (CVPR 2017 · 214 citations)
- Distributed Mean Estimation with Limited Communication (ICML 2017 · 145 citations)
- Robust Nonparametric Regression under Poisoning Attack (AAAI 2024 · 8 citations)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · 5 citations)
Lower bounds and hardness · 345 papers
Keywords: al, bounds, et
Approaches in this cluster:
- Statistical-query lower bounds (90 papers)
Proves computational and sample lower bounds for learning halfspaces, distributions and high-dimensional statistics. - Robust and surrogate-loss learning bounds (83 papers)
Establishes upper and lower bounds for robust learning, surrogate losses and neural network hardness. - Computational thresholds in graphs and structure (91 papers)
Studies low-degree evidence and algorithms for community detection, structure learning and graph search. - Generalization and limits under data constraints (81 papers)
Bounds learning under adaptivity, active learning, missing data and noisy examples.
Most cited and most cited since 2024:
- Lipschitz regularity of deep neural networks: analysis and efficient estimation (NeurIPS 2018 · 135 citations)
- Do GANs learn the distribution? Some Theory and Empirics (ICLR 2018 · 111 citations)
- Watermarks in the Sand: Impossibility of Strong Watermarking for Language Models (ICML 2024 · 9 citations)
- The Impact of Initialization on LoRA Finetuning Dynamics (NeurIPS 2024 · 6 citations)
Learnability and sample complexity · 327 papers
Keywords: sample complexity, pac, optimal sample
Approaches in this cluster:
- Sample complexity of learning distributions (114 papers)
Derives sample bounds for learning Gaussians, simplices and predictors, including gradient-based algorithms. - PAC learnability theory (87 papers)
Characterizes learnability and optimal learners beyond classical PAC, including multiclass and collaborative settings. - Sample complexity of ranking and selection (83 papers)
Bounds samples for item selection, ranking, boosting and auction learning. - Sample complexity of MDPs (43 papers)
Derives near-optimal sample bounds for reinforcement learning in discounted and average-reward Markov decision processes.
Most cited and most cited since 2024:
- SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation (ICML 2018 · 137 citations)
- Sample-Optimal Parametric Q-Learning Using Linearly Additive Features (ICML 2019 · 101 citations)
- Learning Broadcast Protocols (AAAI 2024 · 4 citations)
- On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs) (NeurIPS 2024 · 3 citations)
Learning halfspaces and efficient algorithms · 289 papers
Keywords: epsilon, log, tilde
Approaches in this cluster:
- Learning halfspaces under noise (89 papers)
Develops efficient and label-optimal algorithms for halfspaces under noise and misspecification. - Learning under log-concave distributions (85 papers)
Gives learning and sampling algorithms for log-concave and related distributions, including diffusion-model sampling. - Private and query-efficient algorithms (73 papers)
Gives sample, space and query complexity bounds for private optimization and approximation. - Coresets and sublinear estimation (42 papers)
Estimates statistics and regression with coresets, active learning and sublinear algorithms.
Most cited and most cited since 2024:
- Quantum Perceptron Models (NeurIPS 2016 · 98 citations)
- Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model (NeurIPS 2018 · 85 citations)
- Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · 2 citations)
- Diffusion Posterior Sampling is Computationally Intractable (ICML 2024 · 2 citations)
Learning neural networks · 119 papers
Keywords: relu, functions, activation
Approaches in this cluster:
- Neural network approximation theory (83 papers)
Proves approximation rates and universality for shallow and deep networks across function classes. - Hardness of learning neural networks (36 papers)
Shows computational complexity and learnability limits for training neural networks.
Most cited and most cited since 2024:
- The Expressive Power of Neural Networks: A View from the Width (NeurIPS 2017 · 424 citations)
- Efficient Neural Network Robustness Certification with General Activation Functions (NeurIPS 2018 · 332 citations)
- DeepBern-Nets: Taming the Complexity of Certifying Neural Networks Using Bernstein Polynomial Activations and Precise Bound Propagation (AAAI 2024 · 5 citations)
- Hardness of Learning Neural Networks under the Manifold Hypothesis (NeurIPS 2024 · 4 citations)
Related topics in Learning theory and algorithms
- Matrix and tensor methods (1,467)
- Combinatorial and search optimization (1,576)
- Fairness (550)
- Submodular and game algorithms (1,064)
- Prediction and decision losses (2,400)
- Kernels and regression theory (1,272)
- Clustering (998)
- Optimal transport (462)
