# Data Selection for ERMs

arXiv: https://arxiv.org/abs/2504.14572 · HTML: https://mlsanity.com/paper/2504.14572/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 20 Apr 2025.

## Builds on (most cited first, 10 of 10)

- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Teacher Improves Learning by Selecting a Training Subset](https://mlsanity.com/paper/1802.08946/) (2018)

## Built on by (most cited first, 3 of 3)

- [Exact Risk Ratios for Weighted Data Selection in Linear Regression](https://mlsanity.com/paper/2608.28007/) (2026)
- [Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression](https://mlsanity.com/paper/2608.30254/) (2026)
- [Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws](https://mlsanity.com/paper/2610.00101/) (2026)

## Abstract (arXiv)

Learning theory has traditionally followed a model-centric approach, focusing on designing optimal algorithms for a fixed natural learning task (e.g., linear classification or regression). In this paper, we adopt a complementary data-centric perspective, whereby we fix a natural learning rule and focus on optimizing the training data. Specifically, we study the following question: given a learning rule A and a data selection budget n, how well can A perform when trained on at most n data points selected from a population of N points? We investigate when it is possible to select n ll N points and achieve performance comparable to training on the entire population. We address this question across a variety of empirical risk minimizers. Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression. Additionally, we establish two general results: a taxonomy of error rates in binary classification and in stochastic convex optimization. Finally, we propose several open questions and directions for future research.