# Training Data Subset Selection for Regression with Controlled Generalization Error

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 51 references that are in the map.
- First posted on arXiv 23 Jun 2021.

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

- [Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels](https://mlsanity.com/paper/1805.07836/) (2018)
- [Learning to Reweight Examples for Robust Deep Learning](https://mlsanity.com/paper/1803.09050/) (2018)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [Anchor regression: heterogeneous data meets causality](https://mlsanity.com/paper/1801.06229/) (2018)
- [Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent](https://mlsanity.com/paper/1802.01737/) (2018)
- [Learning From Less Data: A Unified Data Subset Selection and Active Learning Framework for Computer Vision](https://mlsanity.com/paper/1901.01151/) (2019)
- [Classification Under Human Assistance](https://mlsanity.com/paper/2006.11845/) (2020)
- [Regression Under Human Assistance](https://mlsanity.com/paper/1909.02963/) (2019)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions](https://mlsanity.com/paper/1311.2110/) (2013)
- [Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization](https://mlsanity.com/paper/1511.07211/) (2015)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Optimal approximation for unconstrained non-submodular minimization](https://mlsanity.com/paper/1905.12145/) (2019)
- [Submodular Observation Selection and Information Gathering for Quadratic Models](https://mlsanity.com/paper/1905.09919/) (2019)
- [Polyhedral aspects of Submodularity, Convexity and Concavity](https://mlsanity.com/paper/1506.07329/) (2015)
- [Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice](https://mlsanity.com/paper/1805.06990/) (2018)

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

- [Data Distillation: A Survey](https://mlsanity.com/paper/2301.04272/) (2023)
- [Compute-Efficient Deep Learning: Algorithmic Trends and Opportunities](https://mlsanity.com/paper/2210.06640/) (2022)
- [Infinite Recommendation Networks: A Data-Centric Approach](https://mlsanity.com/paper/2206.02626/) (2022)
- [Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks](https://mlsanity.com/paper/2409.12255/) (2024)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [Generalization Bounds and Stopping Rules for Learning with Self-Selected Data](https://mlsanity.com/paper/2505.07367/) (2025)
- [Tackling Provably Hard Representative Selection via Graph Neural Networks](https://mlsanity.com/paper/2205.10403/) (2022)
- [Soft Random Sampling: A Theoretical and Empirical Analysis](https://mlsanity.com/paper/2311.12727/) (2023)
- [Representative Subset Selection for Efficient Fine-Tuning in Self-Supervised Speech Recognition](https://mlsanity.com/paper/2203.09829/) (2022)
- [SHaSaM: Submodular Hard Sample Mining for Fair Facial Attribute Recognition](https://mlsanity.com/paper/2602.05162/) (2026)
- [DOSE: Data Selection for Multi-Modal LLMs via Off-the-Shelf Models](https://mlsanity.com/paper/2604.16979/) (2026)
- [SMA: Submodular Modality Aligner For Data Efficient Multimodal Learning](https://mlsanity.com/paper/2605.12872/) (2026)
- [Data Valuation for Offline Reinforcement Learning](https://mlsanity.com/paper/2205.09550/) (2022)
- [Efficient Semi-Automated Material Microstructure Analysis Using Deep Learning: A Case Study in Additive Manufacturing](https://mlsanity.com/paper/2603.13831/) (2026)

## Abstract (arXiv)

Data subset selection from a large number of training instances has been a successful approach toward efficient and cost-effective machine learning. However, models trained on a smaller subset may show poor generalization ability. In this paper, our goal is to design an algorithm for selecting a subset of the training data, so that the model can be trained quickly, without significantly sacrificing on accuracy. More specifically, we focus on data subset selection for L2 regularized regression problems and provide a novel problem formulation which seeks to minimize the training loss with respect to both the trainable parameters and the subset of training data, subject to error bounds on the validation set. We tackle this problem using several technical innovations. First, we represent this problem with simplified constraints using the dual of the original training problem and show that the objective of this new representation is a monotone and alpha-submodular function, for a wide variety of modeling choices. Such properties lead us to develop SELCON, an efficient majorization-minimization algorithm for data subset selection, that admits an approximation guarantee even when the training provides an imperfect estimate of the trained model. Finally, our experiments on several datasets show that SELCON trades off accuracy and efficiency more effectively than the current state-of-the-art.