Geometric Data Valuation via Leverage Scores

AI summary

Overview

Research area: Data valuation and active learning, at the intersection of numerical linear algebra, cooperative game theory (Shapley values), and optimal experimental design. Presented at the MLxOR workshop on "Mathematical Foundations and Operational Integration of Machine Learning for Uncertainty-Aware Decision-Making."

Technical level: Advanced. The paper leans heavily on linear algebra, matrix concentration inequalities, and ridge regression theory, although the motivating ideas are intuitive.

Scope (one sentence): The paper proposes statistical leverage scores—and their ridge-regularized version—as a tractable geometric substitute for expensive Shapley-based data valuation, proves Shapley-style axioms and error bounds for the resulting subsampled model, and tests the idea in a small MNIST active learning experiment.

What This Paper Is About

Shapley data valuation is theoretically attractive because it assigns each datapoint a value obeying principled fairness axioms, but it is combinatorial: it requires evaluating a utility function over all subsets of the data, which is infeasible at scale. The author proposes replacing that combinatorial measure with a purely geometric one, based on statistical leverage scores, which quantify how much each datapoint extends the span of the dataset in representation space. The goal is a data valuation that is cheap to compute, model-agnostic, and still connected to provable guarantees about downstream model quality.

Key Contributions

1. Leverage scores as Shapley proxies. The paper defines a normalized leverage score π_i = ℓ_i / Σ_j ℓ_j and proves (Theorem 1) that when X has full column rank, this value function satisfies the symmetry, efficiency, and dummy axioms of data Shapley under the span-based utility U(S) := span{x_i : i ∈ S}. It does not generally satisfy linearity.

2. Ridge leverage to fix dimensional saturation. Because plain leverage scores drop to zero marginal value once the span reaches the ambient dimension d, the paper extends the valuation to ridge leverage scores with regularization λ > 0, showing each contributes strictly positive marginal gain and connecting the scores to classical A-optimal and D-optimal experimental design criteria.

3. ε-close decision quality guarantee. Theorem 3 proves that sampling m indices with probabilities proportional to ridge leverage, then training ridge regression, yields a model whose parameters and predictive risk are within O(ε) of the full-data optimum, under a stated sample-size condition.

4. Active learning experiment. A small-scale MNIST experiment shows ridge-leverage sampling outperforming standard active learning baselines without needing gradients, labels, or quadratic computation.

Main Findings

• Plain leverage scores satisfy three Shapley axioms. Under the utility U(S) := span{x_i : i ∈ S} and rank(X) = d, the normalized leverage value π_i satisfies symmetry, efficiency, and dummy. Efficiency holds because the projection matrix H has trace d, so Σ π_i = 1.
• Linearity is not preserved. The author notes the leverage valuation does not generally satisfy the linearity axiom, arguing this is acceptable when value depends on structural diversity.
• Dimensional saturation is the core weakness of plain leverage. Once rank(X_S) = d, any additional datapoint receives zero marginal value—a consequence the author calls the price of simplicity.
• Ridge leverage restores positive marginal gains. For λ > 0, ridge leverage ℓ_i^(λ) ∈ (0,1) and the statistical dimension k_λ = Σ ℓ_i^(λ) lies strictly between 0 and d. New datapoints continue to contribute.
• Connection to optimal design. The D-optimality marginal gain is log(1 + ℓ^(λ)(x)) > 0, and the A-optimality change equals −‖A⁻¹x‖₂² / (1 + ℓ^(λ)(x)) < 0, with A = XᵀX + λI.
• Ridge leverage satisfies symmetry and efficiency but not dummy. For U_D(S) = log det(X_SᵀX_S + λI) and U_A(S) = −Tr((X_SᵀX_S + λI)⁻¹), the exact Shapley value vanishes only when x_i = 0, so the normalized ridge leverage is described as a geometric surrogate rather than an exact Shapley value.
• Subsampled model is provably close to the full-data solution. If m ≥ C (k_λ + log(2d/δ)) / ε², then with probability at least 1 − δ: (1 − ε)A ⪯ A_S ⪯ (1 + ε)A; ‖b_S − b‖_{A⁻¹} ≤ ε‖θ_lin‖_A; ‖θ̂ − θ*‖_A ≤ 4ε‖θ_lin‖_A; and R(θ̂) − R(θ*) ≤ 8ε²‖θ_lin‖_A². This assumes the realizable model y = Xθ_lin.
• Active learning result. In the MNIST experiment, ridge-leverage sampling reached the highest mean test accuracy of 0.846 ± 0.006 by the end of the 40 acquisition rounds, with low run-to-run variability and no access to gradients or labels.

Methodology in Plain English

The author starts from the observation that Shapley values are exact but exponential to compute, and asks whether a purely geometric quantity—how much a datapoint sticks out from the cloud of other datapoints—can stand in for them.

The leverage score of a datapoint is computed from the projection matrix onto the column space of the data matrix. Points that lie in unusual directions (contributing new "span") get high scores; points that sit inside the span of others get low scores. Normalizing these scores gives a number between 0 and 1 that sums to 1, and the author shows this behaves like a Shapley value under three of the four axioms.

To avoid the problem that no new point can contribute once the data span fills the entire feature space, the author adds a ridge penalty λ to the matrix inverse, which mathematically prevents the marginal contribution of any point from reaching exactly zero. This ridge version is then linked to two classic criteria from optimal experimental design (A-optimality and D-optimality).

For the theory side, the author uses a matrix Chernoff bound (a standard tool from randomized numerical linear algebra) to show that sampling rows with probabilities proportional to ridge leverage produces a sketch whose Gram matrix is a good spectral approximation of the full matrix. From that approximation, closeness of parameters and risk follows.

For the empirical side, a 3-layer multilayer perceptron (784 → 256 → 64 → 10 neurons) is trained on MNIST. Six selection strategies are compared: ridge leverage with adaptive regularization λ = 0.01 × Tr(XᵀX)/64 computed on 64-dimensional penultimate-layer embeddings, K-center, Margin, Entropy, Expected Gradient Length, and a uniform random baseline. Each run starts from 100 randomly labeled samples, performs 20 rounds of deterministic pretraining, then 40 active learning rounds of 5 samples each, across 5 independent trials (seeds 0–4).

Why This Matters

Impact on research. The paper offers a middle ground between the axiomatic rigor of data Shapley and the practicality of cheap heuristics. It shows leverage scores can be treated as direct geometric surrogates for Shapley values rather than just a tool for estimating them via sampling (as in prior work the author cites), and it links data valuation to well-developed theory in optimal experimental design and randomized numerical linear algebra.

Real-world applications (all mentioned by the author as motivating settings):

• Dataset curation and pruning — identifying mislabeled or redundant examples to build compact, informative training subsets.
• Data markets — assigning fair prices or payouts to data contributors.
• Federated and collaborative learning — allocating incentives across participants.
• Data-efficient learning under uncertainty — deciding which samples to acquire or label when data is costly, where the paper's active learning result is directly relevant.

Industry relevance. Because the method uses only feature geometry—no gradients, no backward passes, no labels during selection, and no quadratic computation—it fits contexts where gradient access is expensive or unavailable, including inference-only systems and privacy-constrained pipelines. The author also notes the final selector does not yet match state-of-the-art methods, which limits immediate production deployment.

Future Directions

• Extend the theory beyond the noiseless linear model. The author explicitly states that the analysis of Theorem 3 relies on the realizable assumption y = Xθ_lin, and that extending to labels contaminated by sub-Gaussian noise is left to future work.
• Build a stronger selector. The paper calls for fully developing ridge leverage into a selector that competes with the state of the art, describing this as warranting separate, dedicated study.
• Address the linearity gap. Since leverage valuation does not satisfy the linearity axiom, understanding whether any relaxation or alternative normalization restores it remains open.
• Scale the empirical evaluation. The active learning experiment is described as small-scale, and comparisons to methods such as BALD, BatchBALD, ActiveMatch, LESS, and TRAK were not included.

Target Audience

Researchers and practitioners working on data valuation, data-centric machine learning, active learning, and dataset curation who are comfortable with linear algebra and statistical learning theory. It would also interest readers from numerical linear algebra and optimal experimental design, since the paper bridges those fields to Shapley-style data valuation. Readers looking purely for an off-the-shelf selection algorithm may find the method promising but not yet state-of-the-art, as the author acknowledges.

Authors’ abstract

Shapley data valuation provides a principled, axiomatic framework for assigning importance to individual datapoints, and has gained traction in dataset curation, pruning, and pricing. However, it is a combinatorial measure that requires evaluating marginal utility across all subsets of the data, making it computationally infeasible at scale. We propose a geometric alternative based on statistical leverage scores, which quantify each datapoint's structural influence in the representation space by measuring how much it extends the span of the dataset and contributes to the effective dimensionality of the training problem. We show that our scores satisfy the dummy, efficiency, and symmetry axioms of Shapley valuation and that extending them to \emph{ridge leverage scores} yields strictly positive marginal gains that connect naturally to classical A- and D-optimal design criteria. We further show that training on a leverage-sampled subset produces a model whose parameters and predictive risk are within $O(\varepsilon)$ of the full-data optimum, thereby providing a rigorous link between data valuation and downstream decision quality. Finally, we conduct an active learning experiment in which we empirically demonstrate that ridge-leverage sampling outperforms standard baselines without requiring access gradients or backward passes.