# Nearly Optimal Subdata Selection

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 27 Apr 2026.

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

- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Support points](https://mlsanity.com/paper/1609.01811/) (2016)
- [SPlit: An Optimal Method for Data Splitting](https://mlsanity.com/paper/2012.10945/) (2020)
- [Information-Based Optimal Subdata Selection for Big Data Linear Regression](https://mlsanity.com/paper/1710.10382/) (2017)
- [Orthogonal Subsampling for Big Data Linear Regression](https://mlsanity.com/paper/2105.14647/) (2021)
- [Algorithms for Generalized Cluster-wise Linear Regression](https://mlsanity.com/paper/1607.01417/) (2016)
- [Sequential online subsampling for thinning experimental designs](https://mlsanity.com/paper/2004.00792/) (2020)
- [Information-based Optimal Subdata Selection for Clusterwise Linear Regression](https://mlsanity.com/paper/2309.00720/) (2023)

## Abstract (arXiv)

When, in terms of the number of data points, the size of a dataset exceeds available computing resources, or when labeling is expensive, an attractive solution consists of selecting only some of the data points (subdata) for further consideration. A central question for selecting subdata of size n from N available data points is which n points to select. While an answer to this question depends on the objective, one approach for a parametric model and a focus on parameter estimation is to select subdata that retains maximal information. Identifying such subdata is a classical NP-hard problem due to its inherent discreteness. Based on optimal approximate design theory, we develop a new methodology for information-based subdata selection, resulting in subdata that approaches the optimal solution. To achieve this, we develop a novel algorithm that applies to a general model, accommodates arbitrary choices of N and n, and supports multiple optimality criteria, and we prove its convergence. Moreover, the new methodology facilitates an assessment of the efficiency of subdata selected by any method by obtaining tight lower and upper bounds for the efficiency. We show that the subdata obtained through the new methodology is highly efficient and outperforms all existing methods.