Research map / Learning theory and algorithms
Sample complexity: research map
1,363 accepted papers on Sample complexity in Learning theory and algorithms, from ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026), grouped into 5 clusters and 19 approaches. The busiest year so far is 2025.
Within Learning theory and algorithms, its share shrank from 15.0% in 2023–24 to 13.5% in 2025–26 (334 → 328 papers at ICML, NeurIPS, 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.
Approaches and key papers
estimation · estimator · minimax · 361 papers
Approaches in this cluster:
- Minimax estimation rates (109 papers)
Derives optimal risk and rates for parametric and dependent-data estimators. - Optimal mean estimation and subsampling (95 papers)
Develops optimal mean estimators and subsampling or resampling procedures with sharp guarantees. - Density and property estimation (86 papers)
Studies maximum likelihood and profile-likelihood estimators for density, mixtures and distribution properties. - Distributed estimation under communication limits (49 papers)
Derives rates for estimating distributions and means across machines with constrained communication. - Statistical analysis of GAN estimators (22 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)
al · bounds · et · 324 papers
Approaches in this cluster:
- Statistical-query lower bounds (85 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 (84 papers)
Studies low-degree evidence and algorithms for community detection, structure learning and graph search. - Generalization and limits under data constraints (72 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)
sample complexity · pac · optimal sample · 302 papers
Approaches in this cluster:
- Sample complexity of learning distributions (101 papers)
Derives sample bounds for learning Gaussians, simplices and predictors, including gradient-based algorithms. - PAC learnability theory (79 papers)
Characterizes learnability and optimal learners beyond classical PAC, including multiclass and collaborative settings. - Sample complexity of ranking and selection (80 papers)
Bounds samples for item selection, ranking, boosting and auction learning. - Sample complexity of MDPs (42 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)
epsilon · log · tilde · 269 papers
Approaches in this cluster:
- Learning halfspaces under noise (84 papers)
Develops efficient and label-optimal algorithms for halfspaces under noise and misspecification. - Learning under log-concave distributions (80 papers)
Gives learning and sampling algorithms for log-concave and related distributions, including diffusion-model sampling. - Private and query-efficient algorithms (70 papers)
Gives sample, space and query complexity bounds for private optimization and approximation. - Coresets and sublinear estimation (35 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)
relu · functions · activation · 107 papers
Approaches in this cluster:
- Neural network approximation theory (77 papers)
Proves approximation rates and universality for shallow and deep networks across function classes. - Hardness of learning neural networks (30 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,074)
- Combinatorial and search optimization (1,492)
- Fairness (516)
- Submodular and game algorithms (1,030)
- Prediction and decision losses (2,134)
- Kernels and regression theory (1,004)
- Clustering (725)
- Optimal transport (384)