AI Paper Atlas

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:

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).

2016: 72162017: 86172018: 83182019: 95192020: 148202021: 174212022: 161222023: 179232024: 199242025: 187252026: 16926

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):

Papers from 2025–2026 that are already cited most:

Approaches and key papers

Statistical estimation · 473 papers
Keywords: estimation, estimator, minimax

Approaches in this cluster:

Most cited and most cited since 2024:

Lower bounds and hardness · 345 papers
Keywords: al, bounds, et

Approaches in this cluster:

Most cited and most cited since 2024:

Learnability and sample complexity · 327 papers
Keywords: sample complexity, pac, optimal sample

Approaches in this cluster:

Most cited and most cited since 2024:

Learning halfspaces and efficient algorithms · 289 papers
Keywords: epsilon, log, tilde

Approaches in this cluster:

Most cited and most cited since 2024:

Learning neural networks · 119 papers
Keywords: relu, functions, activation

Approaches in this cluster:

Most cited and most cited since 2024:

Related topics in Learning theory and algorithms

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy