aiqbench analysis
This arXiv paper is about machine learning data selection: choosing a training subset whose model matches full-data training. It argues that optimizing population error is information-theoretically infeasible without a very large validation set, and proposes a "faithfulness" bound based on Langevin-dynamics training with a swap-based local search, tested on CIFAR-10 and CIFAR-100. For readers, the main takeaway is a verifiable, estimable proxy for subset quality, though the experiments only show parity with existing baselines rather than gains.
Towards Faithful Data Selection: Statistical Limits and Scalable Algorithms
arXiv:2610.30442v1 Announce Type: new 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.
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: this https URL.
Machine Learning (cs.LG)
arXiv:2610.30442 [cs.LG]
(or arXiv:2610.30442v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.30442 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 307 words
Related coverage
Publicly-Verifiable Certificates for Statistical Algorithms
arXiv · Jul 20, 2026
A Probabilistic Framework for Learnable Optimization Algorithms
arXiv · Aug 17, 2026
Efficient classical algorithm for estimating linear statistics of Boson Sampling
arXiv · Sep 30, 2026
CAS II: Symmetric Partitions as Kolmogorov Models
arXiv · Oct 1, 2026