Nearly Optimal Subdata Selection

• URL: http://arxiv.org/abs/2604.23930v1
• Date: Mon, 27 Apr 2026 01:12:36 GMT
• Title: Nearly Optimal Subdata Selection
• Abstract summary: A central question for selecting subdata of size $n$ from $N$ available data points is which $n$ points to select.<n>We develop a new methodology for information-based subdata selection, resulting in subdata that approaches the optimal solution.<n>We show that the subdata obtained through the new methodology is highly efficient and outperforms all existing methods.
• Score: 14.067057089303134
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
  We introduce a new data selection framework based on low-rank approximation and residual-based sampling.<n>We show that it is possible to select a weighted subset of $tildeOleft(k + frac1varepsilon2right)$ data points whose average loss approximates the average loss over the full dataset.
  arXiv  Detail & Related papers  (2026-06-14T22:29:59Z)
• Data Selection for ERMs [67.57726352698933]
  We study how well can $mathcalA$ perform when trained on at most $nll N$ data points selected from a population of $N$ points.<n>Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression.
  arXiv  Detail & Related papers  (2025-04-20T11:26:01Z)
• Unifying and Optimizing Data Values for Selection via Sequential-Decision-Making [5.755427480127593]
  We show that data values applied for selection can be reformulated as a sequential-decision-making problem.<n>We propose an efficient approximation scheme using learned bipartite graphs as surrogate utility models.
  arXiv  Detail & Related papers  (2025-02-06T23:03:10Z)
• TSDS: Data Selection for Task-Specific Model Finetuning [39.19448080265558]
  The efficacy of task-specific finetuning largely depends on the selection of appropriate training data.<n>We present TSDS (Task-Specific Data Selection), a framework to select data for task-specific model finetuning.<n>We show that instruction tuning using data selected by our method with a 1% selection ratio often outperforms using the full dataset.
  arXiv  Detail & Related papers  (2024-10-15T05:54:17Z)
• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Optimal Data Selection: An Online Distributed View [61.31708750038692]
  We develop algorithms for the online and distributed version of the problem. We show that our selection methods outperform random selection by $5-20%$. In learning tasks on ImageNet and MNIST, we show that our selection methods outperform random selection by $5-20%$.
  arXiv  Detail & Related papers  (2022-01-25T18:56:16Z)
• S$^3$VAADA: Submodular Subset Selection for Virtual Adversarial Active Domain Adaptation [49.01925978752677]
  In the real-world scenario's it might be feasible to get labels for a small proportion of target data. We propose S$3$VAADA which i) introduces a novel submodular criterion to select a maximally informative subset to label and ii) enhances a cluster-based DA procedure. Our approach consistently outperforms the competing state-of-the-art approaches on datasets with varying degrees of domain shifts.
  arXiv  Detail & Related papers  (2021-09-18T10:53:57Z)
• Low Budget Active Learning via Wasserstein Distance: An Integer Programming Approach [81.19737119343438]
  Active learning is the process of training a model with limited labeled data by selecting a core subset of an unlabeled data pool to label. We propose a new integer optimization problem for selecting a core set that minimizes the discrete Wasserstein distance from the unlabeled pool. Our strategy requires high-quality latent features which we obtain by unsupervised learning on the unlabeled pool.
  arXiv  Detail & Related papers  (2021-06-05T21:25:03Z)
• Self-Representation Based Unsupervised Exemplar Selection in a Union of Subspaces [27.22427926657327]
  We present a new exemplar selection model that searches for a subset that best reconstructs all data points as measured by the $ell_1$ norm of the representation coefficients. When the dataset is drawn from a union of independent subspaces, our method is able to select sufficiently many representatives from each subspace. We also develop an exemplar based subspace clustering method that is robust to imbalanced data and efficient for large scale data.
  arXiv  Detail & Related papers  (2020-06-07T19:43:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.