When Does Data Value Reduce to Class Balance? A Coverage View of Per-Point Data Valuation

AI summary

Overview

Research area: Machine learning — specifically data valuation, training-data selection (coreset selection / data pruning), and the theory of influence functions and Data Shapley.

Technical level: Intermediate overall, with an Advanced theory core. The central argument is stated in plain terms (a point's worth depends on what else you already picked), but the proofs use linear algebra (Gram matrices, projectors, Rayleigh quotients), occupancy/combinatorics, and spiked-covariance asymptotics.

Scope (one sentence): The paper proves that selecting the top-k points by any fixed, mode-blind per-point valuation score is provably suboptimal in a latent-mode model, quantifies the exact excess risk, and derives a simple decision rule — balance within labels when labels name the learner's modes, otherwise apply explicit learner-geometry coverage.

What This Paper Is About

Data valuation methods such as Data Shapley, leave-one-out/influence, datamodels, leverage scores and prototypicality assign every training point a single number, and practitioners typically keep the top-k scoring points to train or fine-tune cheaply. The paper argues that this selection rule is structurally wrong exactly in the regime where selection matters, because a point's value is not a fixed number but a function of which other points have already been chosen: a near-duplicate of an already-selected point adds almost nothing no matter how high its score.

The goal is to make that intuition exact. The authors build a latent-mode model in which the failure has a closed-form cost, prove a lower bound on the gap between fixed top-k and adaptive greedy coverage, isolate the conditions under which the gap is large, and then test when the fix is simply balancing the same scores by class versus when an explicit coverage/diversity correction is required.

Key Contributions

1. Value as a context function (§2). A training point's value is reframed as g_i(S) = R(S) − R(S ∪ {i}), a function of the already-selected set rather than a scalar. For kernel/linear learners the paper gives a closed form (Eq. 1): the marginal is the Σ-novelty of a point's feature after orthogonalizing against the selected span, i.e. a Gram–Schmidt / partial-correlation quantity. Interaction is shown to come from two sources — rank collapse (a duplicate drives the marginal to zero) and directional rotation (under anisotropy of Σ) — both carried by the off-diagonal mass of the learner-geometry Gram.

2. An exact impossibility result (§3). In an equal latent-mode instance with r modes of size m, equal costs ρ, and uniform tie-breaking, any symmetric per-point valuation used as top-k covers only the occupancy m*(k) = r(1 − (1 − 1/r)^k) as N → ∞, versus min(k, r) for adaptive greedy coverage. The expected excess risk is exactly ρ δ_N(k) with δ_N(k) = min(k, r) − m*(k). LOO/influence is identically zero in the redundant regime, and Shapley is mode-constant at ρ/m. Extensions cover randomized scores that are "non-coordinated" within modes (Proposition 3) and soft modes via a spiked-covariance analysis (gap ≥ ρ δ_N(k) − c η²k).

3. The modes-vs-labels boundary (§4). The relevant question is not whether a scalar score is accurate pointwise, but whether the groups available at selection time name the learner's modes. When modes coincide with labels, a one-line class balance of the same scores recovers the missing coverage. When labels are missing or coarser than the modes, explicit learner-geometry coverage or coverage within coarse strata is needed.

4. A pre-specified diagnostic (§4.4). The rule is turned into a decision procedure (Algorithm 1) and validated across favorable and stress-test settings, including a near-threshold misroute on coarse labels caught by a pre-stated ambiguity rule and a subgroup-audit row that detects Waterbirds' hidden modes.

Main Findings

• The price of a fixed ranking is exact, not approximate. In the latent-mode model, a symmetric valuation's top-k set behaves like a uniformly random k-subset, so it covers m*(k) modes; greedy covers min(k, r). The difference ρ δ_N(k) is a lower bound for any non-coordinated randomized score and is attained with equality only when mode-level values are equal.

• The gap has a precise phase boundary (Corollary 2). The gap is nonzero exactly when ρ > 0 (hard, non-interpolable task), m ≥ 2 (redundant geometry), and 2 ≤ k ≤ N − m. It is largest at a binding budget: for k ≤ r the per-budget regret δ(k)/k is O(k/r), at k = Θ(r) the gap is Θ(r) — a constant fraction of total risk ρr, with δ(r) = r/e + O(1) — and for k ≥ r it decays as δ(k) ≤ r·e^(−k/r).

• A more accurate score can select worse (Corollary 1). Whether a valuation helps depends on how its high values are spread across modes. A score that concentrates on a few dense, typical modes can fall below the uniform baseline; empirically, estimated Data Shapley and prototypicality dip to or below random near k = C.

• Boundary cases are exact. At k = 1 a single draw always covers a fresh mode, so δ_N(1) = 0 and top-k is optimal; for k > N − m every subset covers all modes; if m = 1 there is no redundancy and δ_N ≡ 0. Redundancy is what creates the gap.

• Synthetic confirmation (Table 1, r = C = 10). At the binding budget k = C = 10, greedy-FL reaches 0.895 and greedy-proj (the theory's exact selector) 0.889, versus the best scalar (prototypicality) at 0.637 — a gap of +0.258. Random is 0.601, leverage 0.600, Shapley 0.615, marginal 0.417, LOO 0.263. The gap is δ-shaped: +0.047 at k = 5, +0.258 at k = 10, +0.168 at k = 15, +0.081 at k = 20, +0.001 at k = 30 and −0.010 at k = 50.

• Coverage counts match the formula. A symmetric valuation's top-k agrees with the closed-form m*(k) within 0.007 modes (Table 22), all boundary cases of the corrected theorem are verified, and on real pools the same zero-parameter formula predicts random selection's coverage, with every raw scalar top-k falling below it (Table 17). At k = C = 10, Shapley covers 6.0 and leverage 6.7 of 10 modes versus greedy's 9.7.

• Labels equal to modes: balancing wins. Class-balancing the same per-point scores matches or beats generic greedy set coverage on standard classification tasks with strong pretrained features (Table 3). KNN-Shapley also concentrates like every other scalar (Table 4).

• No labels: coverage wins, raw top-k can lose. Label-free coverage improves accuracy by +0.08 to +0.20 over random while raw top-k can fall below random (Table 5).

• Coarse labels: stratify, don't balance. On coarse-label CIFAR-100, coverage within coarse strata reaches 0.419 fine accuracy versus 0.240 for coarse-balanced prototypicality.

• Failures are predicted, not accidental. Coverage fails when the representation does not express the relevant modes (Waterbirds), and when data quality varies independently of coverage (corrupted pools, Table 7).

• Unequal modes can reverse the bound (Remark 2). With r = 10 modes — nine singletons and one mode of 91 points — and k = 9, a score that prefers the singletons covers all nine, beating uniform random. Only equal modes give the unconditional lower bound.

• The result is robust in scope but bounded. The gap persists across probes (ridge, an SGD-trained MLP, logistic regression, 1-NN), three encoders, a text corpus, a from-scratch CNN pilot, and a LoRA fine-tune of the backbone; coverage tracks accuracy across 244 pooled pairs in §4.5. The advantage is representation-relative: between 46% and 74% of the learner's target variance is constant within label-free geometry modes, and the trained learner is correct on only 0–5% of test points from uncovered classes.

Methodology in Plain English

The argument proceeds in three moves: reframe, prove, then test where the assumptions hold only approximately.

Reframe. Instead of asking "how valuable is this point?", the authors ask "how much does this point add, given what has already been selected?" For a kernel or linear learner this has an exact answer: project the point's feature away from the span of everything already chosen, and measure the remaining mass under the feature second-moment matrix Σ. Two points in the same direction collapse each other's value to zero; two points in different directions do not. That collapse is the whole story.

Prove. They build a deliberately simple "latent-mode" world: the pool splits into r interchangeable groups (modes) of size m, one representative per mode is enough to cover it, and every uncovered mode costs ρ. Four idealizations are stated openly: rank-collapse coverage (A1), block exchangeability (A2), equal sizes and costs (A3), and a mode-aligned target (A4). In this world the marginal value of a point is either ρ (its mode is uncovered) or 0 (already covered). Every symmetric scalar score becomes a constant, so its top-k is a random k-subset, and the expected number of covered modes is a textbook occupancy number. Greedy selection, by contrast, gains a fresh mode at every step. Subtracting gives the closed-form gap, and a companion proposition (Proposition 1) shows that under a mode-aligned target the coverage objective is the supervised excess risk, exactly at η = 0 and to leading order for small η. Two extensions handle scores that are only noisy approximations (non-coordinated scores, Definition 1) and modes that are only approximately redundant (spiked covariance, small noise η).

Test. The synthetic suite instantiates the model literally: C = 10 classes, three input-distant clusters each, and an embedding that collapses each class's three clusters onto one near-orthogonal class direction — so the learner geometry has r = C = 10 modes even though the input space has 30 clusters. Real-data experiments select from frozen pretrained representations (ViT features) with probe-family learners, emphasizing the binding budget k ≈ C, with full sweeps at k = C, 2C, 4C in the appendix. Selectors compared include random, LOO/influence, leverage, prototypicality, marginal, Shapley, KNN-Shapley, greedy facility location, and greedy-proj (greedy trace reduction / OMP on the feature second moment). The theory's exact selector is shown to match facility location in the block regime (0.889 vs 0.895 at k = C, both covering ≈9.7–9.8 of 10 modes) and to diverge exactly where the lemma's condition fails.

Decide. The practical takeaway is compressed into a one-line rule and a diagnostic: check whether the groups available at selection time name the learner's modes; if yes, class-balance the scores; if no, add an explicit learner-geometry coverage correction; if the modes are not expressed in the representation at all, expect neither to help.

Why This Matters

Impact on research. The paper reframes data valuation from a pointwise estimation problem to a set-level selection problem. That shift implies that leaderboards ranking valuation methods by how well they predict leave-one-out values are measuring the wrong thing: a sharper per-point number can produce a worse training set. It also supplies a clean theoretical bridge between marginal screening and forward selection / orthogonal matching pursuit in sparse approximation, with the off-diagonal Gram mass as the governing quantity.

Real-world applications.

• Budgeted fine-tuning set curation: when only a few hundred examples can be labeled or trained on, keeping the top-scoring points systematically over-samples already-represented concepts.
• Dataset pruning and deduplication for pretraining: the theory explains why naive importance pruning can degrade a model even when the importance estimates are accurate, and why a coverage constraint is the structural fix.
• Active learning and coreset construction: the class-balance-versus-coverage decision rule gives a cheap pre-check before committing to an acquisition strategy.
• Subgroup and long-tail auditing: the diagnostic's subgroup-audit row detects hidden modes (as on Waterbirds) and warns when the representation does not express the groups that matter — a common failure in fairness-sensitive data curation.

Industry relevance. Top-k selection by a per-point score is the default in data-centric ML pipelines: influence-based cleaning, Shapley-based data buying, and prototype-based coresets. The paper's message — that the remedy is structural (balance or cover), not a better scalar — is directly actionable and costs almost nothing to implement, since it reuses the scores already being computed. The paper releases code at https://github.com/Benjy-byj/Data-Value-Class-Balance and is reviewed on OpenReview.

Future Directions

• Partially aligned selectors. The paper states informally that a selector whose geometry is only partly aligned with the modes should interpolate between greedy coverage and the mode-blind occupancy baseline, and explicitly leaves formalizing that interpolation for general representations open.

• Unequal mode sizes and costs. The unconditional lower bound requires equal sizes and equal costs; with unequal sizes the bound can reverse (nine singletons plus one 91-point mode at k = 9). A general theory keyed to whether a score's high values align with small or large modes is not yet available.

• Soft-mode constants and general spectra. The spiked-covariance extension is asymptotic in η with constants that are not optimized; for general Σ the problem reduces to the marginal-screening-versus-OMP gap governed by Gram coherence, which the paper does not develop into a full non-asymptotic theory.

• Representations that hide the modes. Coverage gives no handle when the relevant modes — such as spurious subgroups — are not expressed in the learner geometry. Whether better encoders, subgroup discovery, or explicit augmentation can restore the coverage handle is an open problem, with Waterbirds as the standing counterexample.

• Beyond frozen features. The real-data claims rest on frozen pretrained representations with probe learners; the from-scratch CNN pilot and the LoRA fine-tuning check are checks rather than full studies, leaving end-to-end training regimes as a natural extension.

Target Audience

• Data-centric ML practitioners and platform engineers who build dataset pruning, coreset selection, or data-buying pipelines and currently rank points by Shapley, influence, or leverage scores.
• Researchers in data valuation and influence functions who want a precise statement of when per-point scores are sufficient for selection and when they provably are not.
• Theorists of representation learning and sparse approximation interested in the connection between Gram-matrix coherence, marginal screening, and greedy/orthogonal-matching-pursuit selection.
• Fairness and robustness auditors who need a cheap diagnostic for whether the groups that matter are actually represented in the learner's geometry.

Beginners can read §1 and §4 for the message and the decision rule; the proofs in §3 and the appendices assume comfort with linear algebra and probability at a graduate level.

Authors’ abstract

Per-point data-valuation scores -- Data Shapley, influence, leverage -- are routinely used to select training data: keep the points with the top $k$ scores. We argue that top-$k$ by a fixed, mode-blind per-point score is the wrong selection rule precisely in the regime where data selection matters. The reason is that a point's value is not a fixed number but depends on what else has been selected -- a near-duplicate of an already-chosen point adds almost nothing, however high its score -- and a per-point scalar cannot express this interaction. The theory quantifies this failure exactly: in an equal latent-mode model, fixed top-$k$ selection incurs a closed-form excess risk over adaptive coverage because it repeatedly spends budget on already-covered modes. The gap is largest when the budget is tight, the learner representation is redundant, and missing a mode is costly. The practical rule is simple: use balance when the labels available at selection identify the learner's modes, and use explicit coverage when they do not. On standard classification tasks with strong pretrained features, class-balancing the same per-point scores recovers the missing coverage and matches or outperforms generic set coverage across our datasets. Without labels, label-free coverage improves accuracy by up to +0.20 while raw top-$k$ can fall below random; when labels are coarser than the modes, coverage within coarse strata performs best. We turn this distinction into a pre-specified diagnostic and validate it across both favorable and stress-test settings. The limits are part of the claim: the advantage is representation-relative. Coverage fails when the relevant modes are not expressed in the learner geometry, as with spurious subgroups, or when data quality varies independently of coverage -- exactly as the theory predicts.