Research map / Learning theory and algorithms / Sample complexity
Coresets and sublinear estimation
Estimates statistics and regression with coresets, active learning and sublinear algorithms.
35 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2018–2026) · an approach in Sample complexity, keyword cluster “epsilon · log · tilde”
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.
10 papers in 2023–24 and 14 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 3.0% 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
- 2018 · On Coresets for Logistic Regression (NeurIPS 2018 · 20 citations)
- 2019 · Refined Complexity of PCA with Outliers (ICML 2019 · 6 citations)
- 2020 · Coresets for Regressions with Panel Data (NeurIPS 2020 · 9 citations)
- 2021 · Learning-based Support Estimation in Sublinear Time (ICLR 2021 · 7 citations)
- 2022 · Semi-supervised Active Linear Regression (NeurIPS 2022 · 0 citations)
- 2023 · On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing (ICML 2023 · 3 citations)
- 2024 · Coresets for Multiple $\ell_p$ Regression (ICML 2024 · 0 citations)
- 2025 · Binary Hypothesis Testing for Softmax Models and Leverage Score Models (ICML 2025 · 0 citations)
- 2026 · Linear Regression with Unknown Truncation Beyond Gaussian Features (ICML 2026 · 0 citations)
Earliest papers here
- On Coresets for Logistic Regression (NeurIPS 2018 · 20 citations)
- Refined Complexity of PCA with Outliers (ICML 2019 · 6 citations)
- Which Factorization Machine Modeling Is Better: A Theoretical Answer with Optimal Guarantee (AAAI 2019 · 3 citations)
What has been tried
22 papers here report 119 measured changes (a component added, removed or swapped, compared with a baseline): helped 68%, no clear effect 8%, hurt 14%, mixed 9%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Add the STaR component to Bets | Bernoulli and Beta experiments · interval width | Helped | STAR-Bets: Sequential TArget-Recalculating Bets for Tighter Confidence Intervals (NeurIPS 2025 · 0 citations) | |
| Replace the full squared-log condition with the simplified condition | Dense neural networks · overparameterization | Helped | On the Sparsity of the Strong Lottery Ticket Hypothesis (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 24 papers; from OpenAlex and the papers' affiliations).
- Boston University · 3 papers
- University of California, Berkeley · 3 papers
- Google · 3 papers
- Rice University · 2 papers
- University of Texas at Austin · 2 papers
- Stanford University · 2 papers
Use it
Download BibTeX of 34 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
- Learning halfspaces under noise (84 papers)
- Learning under log-concave distributions (80 papers)
- Private and query-efficient algorithms (70 papers)
Elsewhere in the topic
- Minimax estimation rates (109 papers)
- Sample complexity of learning distributions (101 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)
- Robust and surrogate-loss learning bounds (83 papers)
- Sample complexity of ranking and selection (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).