betaFeedback

WorksComputer Science

Towards Faithful Data Selection: Statistical Limits and Scalable Algorithms

Abstract

What does it mean to have an optimal data selection algorithm? Optimality is conventionally framed as finding a subset that minimizes the population error of the classifier trained only on that subset. Our starting point in this work is first to show that this goal is information-theoretically impossible unless the data selection algorithm has access to a validation set order-wise larger than the training set. This impossibility result motivates shifting from unverifiable population risk minimization to a one-sided guarantee that we refer to as faithfulness: for any candidate subset, we provide an estimable proxy that upper-bounds the difference between training on the full training data and on only the subset. We model training with the Unadjusted Langevin Algorithm and bound the Kullback–Leibler divergence between subset-trained and full-data-trained parameter distributions by the trajectory-accumulated gradient discrepancy. Minimizing this discrepancy gives a principled way to select a subset. Even though the resulting problem is NP-hard, we propose a swap-based local search that decreases the bound at every accepted step. It can therefore refine the output of any selector without worsening its bound. Finally, we provide experimental results on CIFAR10 and CIFAR100 showing that it matches existing data selection baselines. Implementation of our algorithm and the code for reproducing the results are available at: https://github.com/Mehdi-Inane/data_selection_swap.

Introduction

Training on ever-larger datasets is expensive, and not all samples contribute equally: careful pruning can improve how performance scales with dataset size [30]. Data selection formalizes this idea: given a training set SS of nn samples and a learning algorithm A\mathcal{A}, find a subset I⊆SI \subseteq S of size m<nm < n such that training on II alone performs as well as training on all of SS. Besides reducing computation and storage, selection is a concrete instance of the data-centric view of machine learning [40], in which the dataset, rather than the model, is the object to curate.

There is a vast body of work on data selection algorithms [21], which differs in what the data selection algorithm has access to and in how it uses this information. Bi-level optimization approaches [17, 37, 24] select subsets of the training set based on the error on a held-out validation set, and training-data based methods use only information stemming from the training set and the learning dynamics induced by a learning algorithm (Toneva et al., 2019; Paul et al., 2021; Killamsetty et al., 2021a; Cohen-Addad et al., 2026. Despite this empirical progress, the statistical limits of data selection remain poorly understood.

There has also been a recent line of theoretical work on the statistical aspects of data selection. For instance, data memorization is inherently related to data selection, since memorization identifies training examples that a learner cannot afford to discard. The work of Feldman [7] shows theoretically that on long-tailed distributions, rare examples may provide the only information about subpopulations that collectively carry substantial test mass, making their memorization necessary for near-optimal accuracy. Empirically, Feldman and Zhang [8] show that on standard image benchmarks memorized examples often improve accuracy on related test points, so dropping rare samples may degrade the test accuracy. In recent work, Hanneke et al. [11] study the following fundamental question: for empirical risk minimizers, given a set of training samples, does there exist a (smaller) good subset such that training on it performs nearly as well as training on all the samples? Their main result is to give affirmative answers in various settings. Another line of work ([18]) identifies settings in which selection improves over full-sample training, and provides settings where popular selection methods like unbiased reweighting and influence-based rules are suboptimal. Neither work, however, asks what a selector can identify from the samples alone. In this work, we complete this picture by asking: when the training sample contains a subset on which training yields an accurate model, what can a data selection algorithm infer about this subset from finite training (and possibly validation) samples?

To make this question precise, let S=(Z1,…,Zn)S = (Z_1, \ldots, Z_n) be i.i.d. samples from an unknown distribution PP, and let A\mathcal{A} be a learning algorithm. For I⊆[n]I \subseteq[n], write RP(A(SI))R_P(\mathcal{A}(S_I)) for the population risk under PP of the model trained on SI=(Zi)i∈IS_I = (Z_i)_{i \in I}, and RP⋆R_P^\star for the Bayes error. Given a budget mm, let I^⊆[n]\widehat{I} \subseteq[n] with ∣I^∣=m|\widehat{I}| = m be the subset chosen by our data selection algorithm, and let I⋆∈arg⁡min⁡I⊆[n],∣I∣=mRP(A(SI))I^\star\in\arg\min_{I \subseteq[n], |I|=m} R_P(\mathcal{A}(S_I)) be the best subset with the same budget. Writing A(SI^)\mathcal{A}(S_{\widehat{I}}) to denote the hypothesis learned from SI^S_{\widehat{I}}, we consider two ways of decomposing the excess risk, RP(A(SI^))−RP⋆R_P(\mathcal{A}(S_{\widehat{I}})) - R_P^\star:

RP(A(SI⋆))−RP⋆⏟compression error+RP(A(SI^))−RP(A(SI⋆))⏟selection error,(1)\underbrace{R_P(\mathcal{A}(S_{I^\star})) - R_P^\star}_{\text{compression error}} + \underbrace{R_P(\mathcal{A}(S_{\widehat{I}})) - R_P(\mathcal{A}(S_{I^\star}))}_{\text{selection error}}, \tag*{(1)}

and

RP(A(S))−RP⋆⏟full-data excess risk+RP(A(SI^))−RP(A(S))⏟faithfulness gap.(2)\underbrace{R_P(\mathcal{A}(S)) - R_P^\star}_{\text{full-data excess risk}} + \underbrace{R_P(\mathcal{A}(S_{\widehat{I}})) - R_P(\mathcal{A}(S))}_{\text{faithfulness gap}}. \tag*{(2)}

The first decomposition separates two questions: whether the realized training sample contains a good subset of size at most mm (a question that Hanneke et al. [11] studies), and whether the data selection algorithm can identify one. In our statistical setting, however, the comparator A(SI⋆)\mathcal{A}(S_{I^\star}) is not available to the data selection algorithm, because I⋆I^\star depends on the unknown distribution PP. The second decomposition replaces this inaccessible comparator with the full-data model A(S)\mathcal{A}(S); both A(SI^)\mathcal{A}(S_{\widehat{I}}) and A(S)\mathcal{A}(S) can be trained on the observed data. This motivates two questions: (1) When are there more good subsets of size mm exist, can a data selection algorithm find a good subset, and do so using only the training sample and a validation set of moderate size? (2) When this is impossible, can the algorithm use the training data alone to ensure faithfulness to full-data training, and can it optimize this faithfulness at scale?

Contributions

  • A statistical limit on the selection error. We separate the existence of a good subset from the ability of a data selector to find it. For every compression fraction λ∈(0,1)\lambda\in(0,1), training-set size nn, and validation-set size vv, we construct a finite family Pλ,n,v\mathcal{P}_{\lambda,n,v} of zero-Bayes-error classification problems with two properties (Theorem 2.1). First, the family is not degenerate: there is a learner A⋆\mathcal{A}^\star that, on every problem in the family, attains vanishing excess risk both when trained on all nn examples and when trained on its best subset of size m=⌊λn⌋m = \lfloor\lambda n \rfloor, so an accurate subset always exists. Second, no

selector can find one: for every learner A\mathcal{A} and every selector Π\Pi that sees only the training sample and a validation set of size vv, some problem in the family forces

E[RP(A(SIm⋆))−RP⋆⏟compression error+RP(A(SI^m))−RP(A(SIm⋆))⏟selection error]≥Ωλ(nn+v).\mathbb{E}\left[\underbrace{R_P\left(\mathcal{A}(S_{I_m^\star})\right)-R_P^\star}_{\text{compression error}}+\underbrace{R_P\left(\mathcal{A}(S_{\widehat{I}_m})\right)-R_P\left(\mathcal{A}(S_{I_m^\star})\right)}_{\text{selection error}}\right] \geq\Omega_\lambda\left(\frac{n}{n+v}\right).

Hence every learner whose compression error vanishes, A⋆\mathcal{A}^\star among them, pays a selection error of order n/(n+v)n/(n+v) with every selector: a validation set of v/n→∞v/n \to\infty is required to make it vanish.

  • Faithfulness, with a training-data only proxy. The negative result points to the second decomposition: we ask for a faithful subset, one whose training approximates the same distribution over models as training on SS. By modeling training dynamics of gradient-based methods with the Unadjusted Langevin Algorithm (ULA), we bound the faithfulness by the trajectory-accumulated gradient discrepancy GT(I)G_T(I) (Theorem 4.1). This gives a faithfulness proxy for any candidate subset. In Figure 1 we show that the trajectory gradient discrepancy GTG_T correlates with the faithfulness gap for SGD-trained models.

Empirical faithfulness gap versus the estimate of the trajectory gradient error

Figure 1. Empirical Faithfulness gap R^P(A(SI))−R^P(A(S))\widehat{R}_{P}(\mathcal{A}(S_I))-\widehat{R}_{P}(\mathcal{A}(S)) versus the estimate of G^T(I)/2\sqrt{\widehat{G}_T(I)}/2 for CIFAR-10 / ResNet-18 (left) and CIFAR-100 / VGG-16 (right) at retention fraction 0.1. Each point represents a subset from a data selection method, and A\mathcal{A} represents the SGD training procedure. Subsets with large GT(I)G_T(I) are the ones with the largest gap. The inset (right) zooms in on the dotted region. Points in the upper-right corner correspond to EL2N (EL2N in Figure 2 achieves lower accuracy), confirming the theoretical prediction of Theorem 4.2.

  • A simple algorithm with an improvement guarantee. Minimizing GT(I)G_T(I) is NP-hard, and we do not claim to solve it optimally. Existing gradient-based selectors only optimize relaxations of it, for instance by matching gradients at a single training iterate or by scoring examples independently (Remark 4.3), so none directly target the quantity our bound controls. Instead, we give a simple swap-based local search algorithm that, starting from any subset, halts or identifies a subset II that decreases GT(I)G_T(I). One can start from the full training data, or aim to refine the output of another selector (Theorem 4.6). Its cost is dominated by per-example gradients, which we approximate using a single early checkpoint, yielding an estimate G^T\widehat{G}_T of GTG_T. On CIFAR-10 and CIFAR-100, this simple method is on par with existing static data selection baselines. This opens up avenues for improving the optimization of GT(I)G_T(I) as a way to improve data selection.

Statistical Limits of Optimal Subset Selection

In this section, we start by defining the task of finding the optimal subset in the training set. A natural comparator (or goal) is as follows: Fix a possibly randomized learning algorithm A={An}n∈N\mathcal{A}=\{\mathcal{A}_n\}_{n\in\mathbb{N}}, where Am\mathcal{A}_m is the learner applied to samples of size mm and a training sample S=(Z1,…,Zn)∼PnS=(Z_1,\ldots,Z_n)\sim P^n. Assume that we have a budget of size mm for data selection. For every index set I⊆[n]I\subseteq[n], let SI=(Zi)i∈IS_I=(Z_i)_{i\in I}, with the indices in increasing order. Let

Im⋆∈arg⁡min⁡I⊆[n]∣I∣=m RP(Am(SI)),(3)I_m^\star\in\underset{\substack{I\subseteq[n]\\ |I|=m}}{\arg\min}\ R_P\left(\mathcal{A}_m(S_I)\right), \tag*{(3)}

with ties broken canonically. Thus RP(Am(SIm⋆))R_P\left(\mathcal{A}_m(S_{I_m^\star})\right) is the risk of the best subset that an oracle with access to PP can find in the realized sample. Importantly, the oracle must use the same learner A\mathcal{A} as the data selector.

Let V∼PvV\sim P^v be an independent validation set, and let Π:Zn×Zv⟶{I⊆[n]:∣I∣=m}\Pi:\mathcal{Z}^n\times\mathcal{Z}^v\longrightarrow\{I\subseteq[n]:|I|=m\} be a (possibly randomized) data selection algorithm. Write I^m:=Π(S,V)\widehat{I}_m:=\Pi(S,V) for the selected subset. Letting A=Am\mathcal{A}=\mathcal{A}_m denote the learning algorithm fed mm samples, the excess risk of the hypothesis A(SI^m)\mathcal{A}(S_{\widehat{I}_m}) can be decomposed into the compression error and selection error as in Equation (1). Both terms in this decomposition are nonnegative: the first asks whether the training sample contains a good size-mm subset for Am\mathcal{A}_m, and the second measures the cost of finding one using Π\Pi. As we will show, there exists a class of problems for which we have a dichotomy: every size-mm subset has large compression error for Am\mathcal{A}_m, or a good subset exists, but Π\Pi cannot identify it.

References

  1. [1]Attias, I., Dziugaite, G. K., Haghifam, M., Livni, R., and Roy, D. M. (2024). Information complexity of stochastic convex optimization: Applications to generalization and memorization. ICML 2024.arxiv.org/abs/2402.09327
  2. [2]Brown, G., Bun, M., Feldman, V., Smith, A., and Talwar, K. (2021). When is memorization of irrelevant training data necessary for high-accuracy learning? In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pages 123–132.DOI
  3. [3]Chien, E., Wang, H., Chen, Z., and Li, P. (2024). Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning. _eprint: 2401.10371.arxiv.org/abs/2401.10371
  4. [5]Coleman, C., Yeh, C., Mussmann, S., Mirzasoleiman, B., Bailis, P., Liang, P., Leskovec, J., and Zaharia, M. (2019). Selection via proxy: Efficient data selection for deep learning. arXiv preprint arXiv:1906.11829.arxiv.org/abs/1906.11829
  5. [6]El Halabi, M., Orfanides, G., and Hoheisel, T. (2023). Difference of submodular minimization via dc programming. In International Conference on Machine Learning, pages 9172–9201. PMLR.arxiv.org/abs/2305.11046
  6. [7]Feldman, V. (2020). Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954–959, Chicago IL USA. ACM.arxiv.org/abs/1906.05271
  7. [8]Feldman, V. and Zhang, C. (2020). What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation. In Advances in Neural Information Processing Systems, volume 33, pages 2881–2891. Curran Associates, Inc.arxiv.org/abs/2008.03703
  8. [9]Guo, C., Zhao, B., and Bai, Y. (2022). Deepcore: A comprehensive library for coreset selection in deep learning.arxiv.org/abs/2204.08499
  9. [10]Haghifam, M., Negrea, J., Khisti, A., Roy, D. M., and Dziugaite, G. K. (2020). Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms. In Advances in Neural Information Processing Systems, volume 33, pages 9925–9935. Curran Associates, Inc.arxiv.org/abs/2004.12983
  10. [11]Hanneke, S., Moran, S., Shlimovich, A., and Yehudayoff, A. (2025). Data selection for erms. In Haghshab, N. and Moitra, A., editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2634–2665. PMLR.arxiv.org/abs/2504.14572
  11. [13]Inane, A. M., Qurion, V., Dziugaite, G. K., and Mitliagkas, I. (2026). Unlearning with asymmetric sources: Improved unlearning-utility trade-off with public data.arxiv.org/abs/2605.11170
  12. [14]Iyer, R., Khargoankar, N., Bilmes, J., and Asanani, H. (2021). Submodular combinatorial information measures with applications in machine learning. In Feldman, V., Ligett, K., and Sabato, S., editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 722–754. PMLR.arxiv.org/abs/2006.15412
  13. [15]Johnson, W. B., Lindenstrauss, J., et al. (1984). Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1.
  14. [16]Killamsetty, K., Sivasubramanian, D., Ramakrishnan, G., De, A., and Iyer, R. (2021a). GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training. arXiv:2103.00123 [cs].arxiv.org/abs/2103.00123
  15. [17]Killamsetty, K., Sivasubramanian, D., Ramakrishnan, G., and Iyer, R. (2021b). Glister: Generalization based data subset selection for efficient and robust learning.
  16. [18]Kolossov, G., Montanari, A., and Tandon, P. (2023). Towards a statistical theory of data selection under weak supervision. arXiv:2309.14563 [stat.ML].arxiv.org/abs/2309.14563
  17. [19]Krizhevsky, A. (2009). Learning multiple layers of features from tiny images. https://www.cs.toronto.edu/kriz/learning-features-2009-TR.pdf.
  18. [20]Mirzasoleiman, B., Bilmes, J., and Leskovec, J. (2020). Coresets for Data-efficient Training of Machine Learning Models. arXiv:1906.01827 [cs].arxiv.org/abs/1906.01827
  19. [21]Moser, B. B., Shanbhag, A. S., Frolov, S., Raue, F., Folz, J., and Dengel, A. (2025). A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances. Version Number: 2.arxiv.org/abs/2505.17799
  20. [22]Narasimhan, M. and Bilmes, J. A. (2012). A submodular-supermodular procedure with applications to discriminative structure learning.arxiv.org/abs/1207.1404
  21. [23]Negrea, J., Haghifam, M., Dziugaite, G. K., Khisti, A., and Roy, D. M. (2019). Information-theoretic generalization bounds for SGLD via data-dependent estimates. Advances in Neural Information Processing Systems, 32.arxiv.org/abs/1911.02151
  22. [24]Nikdan, M., Cohen-Addad, V., Alistarh, D., and Mirrokni, V. (2026). Efficient data selection at scale via influence distillation. Advances in Neural Information Processing Systems, 38:143229–143265.
  23. [25]Paul, M., Ganguli, S., and Dziugaite, G. K. (2021). Deep Learning on a Data Diet: Finding Important Examples Early in Training. In Advances in Neural Information Processing Systems, volume 34, pages 20596–20607. Curran Associates, Inc.arxiv.org/abs/2107.07075
  24. [26]Pia, A. D., Dey, S. S., and Molinaro, M. (2014). Mixed-integer quadratic programming is in np.arxiv.org/abs/1407.4798
  25. [27]Pruthi, G., Liu, F., Sundararajan, M., and Kale, S. (2020). Estimating Training Data Influence by Tracing Gradient Descent. arXiv:2002.08484 [cs.LG].arxiv.org/abs/2002.08484
  26. [28]Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
  27. [29]Simonyan, K. and Zisserman, A. (2015). Very deep convolutional networks for large-scale image recognition.
  28. [30]Sorscher, B., Geirhos, R., Shekhar, S., Ganguli, S., and Morcos, A. S. (2023). Beyond neural scaling laws: beating power law scaling via data pruning.arxiv.org/abs/2206.14486
  29. [31]Szegedy, C., Liu, W., Jia, Y., Sermanet, P., Reed, S., Anguelov, D., Erhan, D., Vanhoucke, V., and Rabinovich, A. (2014). Going deeper with convolutions.
  30. [32]Tan, H., Wu, S., Du, F., Chen, Y., Wang, Z., Wang, F., and Qi, X. (2023). Data pruning via moving-one-sample-out. Advances in neural information processing systems, 36:18251–18262.arxiv.org/abs/2310.14664
  31. [34]Wei, K., Iyer, R., and Bilmes, J. (2015). Submodularity in data subset selection and active learning. In Bach, F. and Blei, D., editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1954–1963, Lille, France. PMLR.
  32. [35]Welling, M. (2009). Herding dynamical weights to learn. In Proceedings of the 26th annual international conference on machine learning, pages 1121–1128.DOI
  33. [36]Welling, M. and Teh, Y. W. (2011). Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML’11, page 681–688, Madison, WI, USA. Omnipress.
  34. [37]Xia, M., Malladi, S., Gururangan, S., Arora, S., and Chen, D. (2024). Less: Selecting influential data for targeted instruction tuning. arXiv preprint arXiv:2402.04333.arxiv.org/abs/2402.04333
  35. [38]Xia, X., Liu, J., Yu, J., Shen, X., Han, B., and Liu, T. (2022). Moderate coreset: A universal method of data selection for real-world data-efficient deep learning. In The Eleventh International Conference on Learning Representations.
  36. [40]Zha, D., Bhat, Z. P., Lai, K.-H., Yang, F., Jiang, Z., Zhong, S., and Hu, X. (2025). Data-centric artificial intelligence: A survey. ACM Computing Surveys, 57(5):1–42.arxiv.org/abs/2303.10158

Paper details

vlnc:W_uwgw3nvd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents