PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Faithful Data Selection: Statistical Limits and Scalable Algorithms

Ahmed Mehdi Inane, Mahdi Haghifam, Gintare Karolina Dziugaite, Ioannis Mitliagkas

arXiv:2610.30442v1cs.LG

TL;DR

Finding a subset with low population risk can be impossible without validation data order-wise larger than the training set. The paper instead bounds faithfulness to full-data training with a training-only proxy and optimizes it using swap-based local search. On CIFAR-10/100, the method matches existing data-selection baselines.

  • Problem

    A selector may be unable to identify a population-risk-optimal subset from training data and validation data of comparable size, even when a good subset exists.

    Source: §1 · pp. 1–2

  • Method

    The paper models training with ULA, uses trajectory gradient discrepancy as a training-only faithfulness proxy, and applies swap-based local search to decrease it.

    Source: §4.1 · p. 9, §6 · p. 11

  • Results

    On CIFAR-10/100, the method matches existing static data-selection baselines on average accuracy.

    Source: §6 · pp. 11–12, §5.2 · p. 11

  • Takeaways & Limitations

    Minimizing GT provides faithfulness across bounded downstream queries, including evaluations beyond average-case accuracy.

    Source: §6 · p. 12

    The faithfulness guarantee is proven for ULA and is one-sided; extending it to SGD or Adam remains open.

    Source: §6 · p. 12

Abstract

from arXiv · show

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.

1 Introduction

The paper asks what selectors can identify from finite training and validation samples, then shifts from finding the population-risk-optimal subset to guaranteeing faithfulness to full-data training. It establishes a statistical limit, proposes a training-only proxy and swap-based optimizer, and reports performance on par with existing static baselines.

1 Introduction

  • Data selection seeks a size-m subset that performs as well as full-data training, while pruning can reduce computation and storage.The paper frames this as a data-centric approach that curates the dataset rather than the model.Source: §1 · p. 1
  • The introduction distinguishes whether a good subset exists from whether a selector can identify it using only training data and a moderate validation set.It also asks whether training-only methods can ensure and optimize faithfulness to full-data training when identifying a population-risk-optimal subset is impossible.Source: §1 · p. 2

CONTRIBUTIONS

  • A good subset may exist yet remain unidentifiable: with validation size v = O(n), some problems force constant selection error even with unlimited computation.The lower bound implies that validation size v/n must diverge for selection error to vanish.Source: CONTRIBUTIONS · pp. 2–3
  • For any candidate subset, the trajectory-accumulated gradient discrepancy GT provides a training-data-only proxy that bounds faithfulness under ULA.The paper also reports that GT correlates with the faithfulness gap for SGD-trained models.Source: CONTRIBUTIONS · p. 3
  • Minimizing GT is NP-hard, but swap-based local search decreases it from any starting subset and can refine another selector’s output.The cost is dominated by per-example gradients, approximated using a single early checkpoint.Source: CONTRIBUTIONS · p. 3
  • On CIFAR-10 and CIFAR-100, the swap-based method performs on par with existing static data-selection baselines.It uses per-example gradients approximated with a single early checkpoint, and each accepted swap decreases the faithfulness proxy.Source: CONTRIBUTIONS · p. 3

2 Statistical Limits of Optimal Subset Selection

The section separates existence of a good subset from a selector’s ability to find it, and proves that finite validation data may leave selection error non-vanishing. Its construction allows both full-data training and an oracle-chosen subset to succeed, while a sample-based selector fails on some problems.

2 Statistical Limits of Optimal Subset Selection

  • The section defines the comparator as the best subset of budget m for the same learner, with risk evaluated on the population distribution.The oracle comparator depends on P, which is unavailable to the selector.Source: §2 · p. 3
  • For fixed λ and v = O(n), every selector–learner pair with small compression error can still incur selection error bounded below by a constant, even with unlimited computation.The constructed problems have zero Bayes risk and an accurate subset for a specified learner.Source: §2 · p. 4
  • The lower bound is tight in its training-sample dependence: v = Θ(λn/ε^2) validation samples suffice for selection error ε.This follows by applying generalization bounds to the finite class induced by running the learner on all size-m subsets.Source: §2 · p. 4
  • The construction couples labels on a cubic graph through parity constraints, making an accurate oracle subset possible while hiding which edges are active from selectors.Masked examples reveal active edges but hide labels, and most groups receive none in the training and validation samples.Source: §2 · p. 5
  • When λ < 1/3, parity constraints leave about 1/3 NB bits of label information, while a size-m subset conveys at most n + mB bits, forcing errors on Ω(γn) edges.Because active edges are hidden, these errors translate into test risk.Source: §2 · p. 5
  • Full-data training and an oracle subset can succeed because observed labels on the boundary of each small missing-edge tree determine its missing labels, except with probability O(1/log n).The oracle can keep the certificates for active edges within budget m.Source: §2 · p. 5

3 Faithful data selection

Because the population-risk-optimal subset depends on an unknown distribution, the paper shifts to comparing subset training with full-data training. It defines faithfulness through closeness of model distributions and explains how this controls bounded evaluations.

3 Faithful data selection

  • When full-data excess risk is small, the selected subset’s excess risk is essentially its faithfulness gap from full-data training.The full-data model is an accessible comparator, unlike the best subset that depends on the unknown distribution.Source: §3 · p. 5
  • The paper’s proxy is useful when the faithfulness gap is small, but it does not overcome the lower bound because the hard distributions can have a large gap.The proxy is computed from training data and a small value implies a small faithfulness gap.Source: §3 · p. 5

3.1 From faithfulness to KL divergence

  • A subset is faithful when its training produces nearly the same model distribution as full-data training, controlling the faithfulness gap and every bounded query.Examples include subgroup or rare-subpopulation accuracy, accuracy under distribution shift, and loss or prediction at a test point.Source: §3.1 · p. 6
  • The bounded-query comparison applies to a fixed training set and any candidate subset, with the two randomized learners sharing the same initialization distribution.The setup considers a measurable bounded function of the trained parameters.Source: §3.1 · p. 6

4 Practical Data Selection using Langevin Algorithm

The paper uses ULA to bound how much subset training can differ from full-data training, yielding a training-data-based faithfulness proxy. It then uses swap-based local search to reduce that proxy without increasing it at accepted steps.

4 Practical Data Selection using Langevin Algorithm

  • ULA bounds the faithfulness gap through trajectory-accumulated squared differences between subset and full-data gradients, yielding a proxy for selecting subsets.The proxy can be estimated from a full-data run without training on candidate subsets or accessing the unknown distribution or held-out data.Source: §4 · pp. 6–7
  • The trajectory gradient discrepancy is the unweighted, trajectory-averaged gradient discrepancy; unlike alignment-only scores, it also accounts for redundancy among selected examples.The paper relates existing gradient-based selectors to pieces of this objective.Source: §4 · p. 7

4.1 Subset selection via gradient swaps

  • Minimizing the discrepancy is NP-hard, and forming or storing its matrix requires Θ(n^2) inner products or memory.The fractional relaxation is uninformative because the matrix satisfies C1 = 0.Source: §4.1 · p. 8
  • Swap descent exchanges one selected example for one unselected example, proposing swaps by gradient scores and accepting them only when the exact quadratic objective decreases.The first-order score drops the selected example most aligned with the subset's gradient error and adds the unselected example most opposed to it.Source: §4.1 · pp. 8–9
  • The implementation stores aggregate gradients rather than the full matrix, while per-example gradients across checkpoints remain a cost of evaluating swaps.The paper notes that long trajectory horizons make swaps expensive because aggregate gradients must be recomputed after each swap.Source: §4 · p. 7, §4.1 · p. 9
  • Every accepted swap lowers the faithfulness proxy, and the finite search returns a subset with no larger discrepancy than its starting subset.This holds whether initialized from a uniform subset or another selector's output.Source: §4.1 · p. 9

5 Experiments

Across CIFAR-10 and CIFAR-100, Gradient Swap performs on par with static selection baselines at the tested retention fractions. The experiments also find that the estimated discrepancy tracks faithfulness gaps and that one early checkpoint suffices for selection.

5.1 Experimental setup

  • The study compares six static selectors and random selection, omitting adaptive methods that periodically reselect subsets during training.The baselines include Herding, Moderate Coreset, Facility Location, GraphCut, EL2N, and MoSo.Source: §5.1 · p. 10
  • Experiments retrain models from scratch at 10%, 20%, 40%, and 50% retention, averaging test accuracy over five seeds.The evaluation uses CIFAR-10 and CIFAR-100 with ResNet-18, VGG-16, and Inception.Source: §5.1 · pp. 9–10

5.2 Results

  • Using τ = 1 checkpoint gives accuracy results within roughly one standard error of settings with more checkpoints, with no monotone trend in τ.The single checkpoint is from epoch 1; additional checkpoints cost more without detectable improvement.Source: §5.2 · p. 11, Table 1 · p. 11
  • Estimated GT correlates with faithfulness gaps at r = +0.98 for ResNet-18 on CIFAR-10 and r = +0.80 for VGG-16 on CIFAR-100.The estimate is computed from SGD while the theoretical GT is derived for ULA, and subset models are retrained with SGD.Source: §5.2 · p. 11
  • Gradient Swap’s test accuracy falls within the spread of static baselines at every retention fraction across datasets and architectures, with no consistent winner.Figure 2 reports retrained-model accuracy against retention fraction for CIFAR-10 and CIFAR-100.Source: Figure 2 · p. 10, §5.2 · p. 11

6 Discussion and Limitations

The paper separates the existence of accurate subsets from selectors’ ability to identify them, then replaces inaccessible population-risk optimization with a training-data proxy for faithfulness. Its appendix describes a graph-based distribution family used to study the statistical limit.

6 Discussion and Limitations

  • Even when an accurate subset exists, no selector can reliably identify one from training data and a validation set of comparable size.The result is established for a finite family of zero-Bayes-error problems and a learner that succeeds on both the full sample and its best subset.Source: §6 · p. 11
  • ULA analysis bounds the faithfulness gap using trajectory-accumulated gradient discrepancy, G_T(I), a training-only proxy for candidate subsets.The proxy’s off-diagonal structure captures redundancy.Source: §6 · p. 11
  • The swap-descent algorithm decreases the faithfulness bound at every accepted step, although minimizing G_T(I) is NP-hard.The method is presented as a refinement that improves the bound rather than as an optimal solver.Source: §6 · p. 11
  • On average accuracy, the method performs on par with existing methods, while minimizing G_T(I) guarantees faithfulness across bounded downstream queries.The discussion contrasts this guarantee with average-case heuristics, which it says lack the same robustness guarantee.Source: §6 · p. 12
  • The faithfulness guarantee is proven for ULA and is one-sided; extending it to SGD or Adam is identified as future work.The authors describe those extensions as a way to close the gap between analysis and practice.Source: §6 · p. 12

B.1.1 Data distribution and meta-distribution

  • Each group contains candidate edges, one of which is designated active; risk is incurred only on active edges, and masked examples reveal them.The construction uses groups of k_group edges and chooses k_group = ceil(10/λ) to limit the expected number of certificate examples.Source: §B.1.1 · p. 16

B.1.2 Main argument

This section develops the main lower- and upper-bound arguments, including how selected examples may fail to reveal unresolved labels and how parity constraints and compact edge certificates support the upper bound and faithfulness guarantee. It then formalizes gradient-trajectory minimization as subset selection and describes the swap algorithm’s exchange rule.

B.1.2 Main argument

  • The lower-bound proof reduces risk to errors on unresolved groups, where the active edge is uniform given the learner’s information, and bounds those errors using an entropy argument.The learner receives labels only through the selected examples; comparing the entropy of the hidden labels with that of the learner’s output yields a Fano-style lower bound on mistakes.Source: §B.1.2 · pp. 18–20
  • For sufficiently large n, the lower-bound proof derives equation (13) and shows that some distribution in the family attains the bound for each fixed learner and selector.The resulting distribution may depend on the learner and selector, although the family of distributions does not.Source: §B.1.2 · p. 20

B.2 Upper bound

  • The learner forms a linear system over F2 in Θ and solves it by Gaussian elimination; when an edge’s certificate does not fail, every subsample containing its certificate determines Θe, while failure probability is at most 3/s.Source: §B.2 · pp. 20, 22
  • The oracle can form an m-example subset from certificates of active edges, sharing certificate examples across edges in the same small missing component.When the certificate union fits within m, the selected sample determines each active edge’s label unless its certificate fails; otherwise the learner’s risk remains bounded by pmasked.Source: §B.2 · pp. 23–24
  • The upper-bound proof concludes under k_group ≥ 10/λ, with constants and the threshold nλ depending only on λ.The passage also gives a bound involving γ, k_group, n, v, and log2 n, but its formula is incomplete in the supplied text.Source: §B.2 · p. 24

C KL divergence in parameter space upper bounds the faithfulness error

  • For every measurable q bounded in [a, b], the proof uses Pinsker’s inequality to bound its expectation discrepancy under P and Q through their KL divergence.The argument applies directly to the absolute discrepancy, without separate treatment of positive and negative parts.Source: C KL divergence in parameter space… · pp. 24–25

D Proof of the gradient trajectory upper bounding the faithfulness

  • The proof bounds endpoint KL divergence by path KL divergence, using the Markov-chain KL chain rule and data processing for chains with common initial law and Gaussian noise.The path bound’s outer expectation is under the full-data chain’s marginal, so it involves only that chain.Source: D Proof of the gradient trajectory… · p. 25

Proof of the quadratic program formulation of subset selection by optimizing the gradient trajectory

  • Minimizing the gradient-trajectory objective over subsets of size m is the stated integer program, because size-m subsets correspond bijectively to their indicator vectors.The proof expresses the centered per-example gradients as ζ_i = g_i − ḡ.Source: Proof of the quadratic program… · p. 26

F Construction and analysis of the Swap algorithm

  • The swap algorithm’s exchange pair minimizes the linearized objective change over all exchanges, for a convex, centered objective D.The setup states C ⪰ 0 and C1 = 0; the described algorithm evaluates and accepts proposed swaps based on their objective change.Source: F Construction and analysis of the… · pp. 26–27

F.1 Proof of the swap gap

Accepted swaps strictly decrease the objective, so the search terminates without increasing the bound. The section also records a shared-reference-trajectory caveat and checkpoint-selection details for the experiments.

F.1 Proof of the swap gap

  • Every accepted swap strictly decreases GT, and only finitely many size-m subsets exist, so the search terminates with GT(Iout) ≤ GT(I0).The bound holds for every starting subset and tie-breaking rule.Source: §F.1 · p. 27

G.1 Caveat on the train / validation split

  • For four of five seeds, the selection pool and reference pool are different 45,000-example draws, overlapping on about 90% of their elements.The shared reference trajectory was not retrained per seed because that would multiply the most expensive step by five.Source: §G.1 · p. 28

G.2 More empirical details

  • The experiments reuse one full-data reference trajectory per dataset–architecture pair, trained on the seed-42 pool.The same trajectory supplies stored parameters and learning rates for all five selection seeds.Source: §G.2 · p. 28
  • Baseline comparisons use one checkpoint, while the checkpoint-variation experiments select stored epochs nearest equally spaced optimizer-step times.For τ = 4, the selected checkpoints are approximately epochs 1, 100, 200, and 300.Source: §G.2 · p. 28

H Empirical correlation between faithfulness error and trajectory gradient discrepancy

Across six dataset–architecture settings, the estimated proxy tracks the empirical faithfulness gap. The evaluation estimates the proxy from one reference run and compares it with faithfulness errors from retrained selected subsets.

H Empirical correlation between faithfulness error and trajectory gradient discrepancy

  • The proxy estimate uses a single SGD reference run on 45,000 sampled training points, with stored parameters from the training trajectory.The reference run plays the role of A(S).Source: H Empirical correlation between… · p. 28
  • Each plotted point is one selection-method and seed pair, whose subset is retrained from a shared initialization and evaluated on the official test set.The panels fix dataset and architecture at a 10% selection ratio.Source: H Empirical correlation between… · p. 29
  • Pearson correlation exceeds 0.70 in all six settings between estimated faithfulness and estimated bGT.The subsets with the largest trajectory gradient discrepancy also depart most from full-data training.Source: Figure 7 · p. 29, H Empirical correlation between… · p. 29

I Gradient-Swap with warm starts

Warm-start swaps lower the proxy for each tested selector, but downstream accuracy gains depend on the starting subset. EL2N improves after swaps, while already-low-discrepancy selectors show no measurable accuracy gain.

I Gradient-Swap with warm starts

  • Swaps lower bGT for every tested starting selector, even though the swaps use τ=10 checkpoints and evaluation uses all 300.The comparison starts from GraphCut, Random, Herding, or EL2N subsets.Source: I Gradient-Swap with warm starts · p. 29
  • For GraphCut, Herding, and Random, test accuracy remains unchanged within one standard deviation after swaps.These starting selectors already lie inside the low-bGT faithfulness envelope.Source: I Gradient-Swap with warm starts · pp. 29–30
  • For EL2N, 500 swaps reduce bGT by 16% and improve test accuracy by 2.6 percentage points, though performance remains far from the other selectors.The table reports full-network Gradient Swap on CIFAR10 at 10% of the pool, with means and standard deviations over five seeds.Source: I Gradient-Swap with warm starts · pp. 29–30, Table 2 · p. 30

J Ablation study on the number of used checkpoints

The checkpoint ablation finds no consistent test-accuracy effect from using more checkpoints across three architectures, motivating τ = 1 as a computational simplification.

J Ablation study on the number of used checkpoints

K Johnson-Lindenstrauss Embeddings Ablation

Count-sketch embeddings reduce gradient storage while preserving the selected subsets’ test accuracy in the reported CIFAR-10/ResNet-18 experiments.

K Johnson-Lindenstrauss Embeddings Ablation

  • A width-1024 count sketch replaces each checkpoint’s aggregate gradient with a vector in R^p, making the swap test exact for the sketched objective.Increasing p to 2048 or 4096 produces no further gain in the reported accuracy.Source: K Johnson-Lindenstrauss Embeddings… · p. 31
  • The same accuracy match holds when the trajectory grows from one checkpoint to four, supporting use of the embedding instead of exact aggregates.Source: K Johnson-Lindenstrauss Embeddings… · p. 31
  • On CIFAR-10 with ResNet-18, sketched runs preserve test accuracy relative to exact aggregates across subset fractions and τ values.The largest gap is 0.60 points at τ = 1, p = 2048, and 10%, below either run’s seed standard deviation; from 40% upward, gaps are about 0.1 points.Source: Table 5 · p. 31, K Johnson-Lindenstrauss Embeddings… · p. 31, Table 6 · p. 32

L Selected examples for each selection method

The selected-example display samples six raw training images per method from 10% subsets across CIFAR-10 and CIFAR-100 architectures.

L Selected examples for each selection method

Related papers

Loading 2610.30442v1…