Faithful Data Selection: Statistical Limits and Scalable Algorithms

Problem

Data selection is usually defined as the problem of 'minimizing the population error of a model trained only on the subset.' However, it was not well understood whether this goal can actually be achieved from the data alone, that is, where the statistical limits lie.

Method

The authors first prove an information-theoretic lower bound. They construct a family of classification problems in which, unless validation data is larger in order than the training data, no selector can find a good subset even when one exists (using cubic graphs with large girth and parity constraints). They therefore change the goal to 'faithfulness': a criterion that checks whether the distribution of models trained on the subset is close to the distribution of models trained on the full data. They model training as ULA (Unadjusted Langevin Algorithm) and upper-bound the KL divergence between the two parameter distributions by the trajectory-accumulated gradient mismatch G_T(I). Because minimizing G_T is NP-hard, they propose a local search in which every accepted swap reduces the bound. It can also be used to improve the output of another selector by taking it as the starting point. Per-example gradients are approximated using a single early checkpoint.

Results

• The authors prove that for compression ratio λ<1/3, for any learner–selector pair there exists a problem whose expected excess risk is at least Ω(n/(n+v)). So to drive selection error to zero, the validation data size v must be larger in order than the training data size n.
• On the same problem family, training on the full data, and training on a subset chosen by an oracle that knows the distribution, both achieve a small error of order O(1/log n). In other words, a good subset exists, but it cannot be found from the data alone.
• The lower bound is tight in its dependence on the number of training samples. With validation data v=Θ(λn/ε²), the selection error can be reduced to ε.
• The authors report that for models trained with SGD, G_T correlated with the faithfulness gap.
• On CIFAR-10 and CIFAR-100, the proposed swap local search performed comparably to existing static data selection baselines. The authors do not claim it outperforms the baselines.

Limitations

Experiments are limited to CIFAR-10/100 image classification, and results are on par with existing methods with no clear advantage. The faithfulness bound relies on the assumption that SGD is approximated by ULA, and per-example gradients are also approximated with a single early checkpoint. The local search does not guarantee an optimal solution to the NP-hard problem. Also, this approach does not get around the lower bound itself. The authors themselves note that it is only meaningful when training on the full data already works well.

Why it matters

When choosing a data selection (pruning) method, it provides a theoretical basis for the point that claims of 'finding the optimal subset' cannot be verified without large validation data. As an alternative, it offers a criterion that can be computed from training data alone and guarantees the gap from full-data training. It is also practically useful that the output of any selector can be refined without worsening the bound.

Key terms

Faithfulness

A criterion that measures how closely a model trained on a subset follows the same distribution as a model trained on the full data. It can be estimated from training data alone, without knowing the true distribution.

Compression error and selection error

Compression error indicates whether a good subset exists within the sample, and selection error indicates whether a selection algorithm actually finds that subset. This paper shows that the latter has a lower bound.

ULA(Unadjusted Langevin Algorithm)

A training model that adds Gaussian noise to gradient descent. Because it lets the training outcome be treated as a probability distribution over parameters, it makes the KL divergence bound easy to compute.

Trajectory-accumulated gradient mismatch

The value obtained by accumulating, over the whole training path, how much the subset's average gradient differs from the full data's average gradient. Reducing this value makes the faithfulness bound smaller.

Original

• arXiv abstract
• PDF
• HTML full text
• Hugging Face

Authors: Ahmed Mehdi Inane, Mahdi Haghifam, Gintare Karolina Dziugaite, Ioannis Mitliagkas · Posted 2026-10-21 · License CC BY 4.0 · Based on the full text

This review is an AI-written summary of the paper. Please treat the original paper as the reference.