REVIEW 2 major objections 5 minor 20 references
Unifying and Optimizing Data Values for Selection via Sequential Decision-Making
T0 review · 2 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read Data values for selection are approximate solutions to a sequential decision problem, and the gap between a value-based ranking and the optimal sequence is governed by utility curvature.
desk verdict Smart MDP/ADP framing of data valuation, but the surrogate's exact-optimality theorem is false and the advertised LLM experiments are missing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery that carries the argument is the reformulation of data selection as a finite-horizon deterministic MDP, together with the Bellman equation $V(s)=U(s)+\max_{a\in D\setminus s}V(s\cup\{a\})$. States are selected subsets, actions are the next training point, transitions are $s_{t+1}=s_t\cup\{a_t\}$, and rewards are the utility $U(s_t)$, so that the sum of rewards equals the selection-curve objective. Existing data values enter as a specific ADP instance: a linear reward surrogate $\hat U(S)=\sum_{i\in S}\theta_i$ estimated by weighted least squares, paired with the myopic decision rule $\pi(s)=\arg\max_{a\notin s}\theta_a$; the weights in the least-squares fit select which game-theoretic value is recovered. The analysis object that explains performance is the curvature $c$ of a monotone submodular utility, which upper-bounds how much marginal contributions shrink, and the paper's guarantee is the $(1-c)^2$ factor. For the practical surrogate, the mechanism is a weighted bipartite graph from training points to validation points, with the coverage utility $\hat U(S)=|\cup_{i\in S}S_i|$, whose monotonicity and submodularity justify greedy maximum-coverage selection.
What would settle it
Take a small coverage instance with three training points and two validation points arranged so that the largest first-step coverage blocks later coverage, enumerate all six selection orders, and compare $\sum_{k=1}^n \hat U(S_k)$ for greedy versus the best order; a better non-greedy order would refute the appendix's exact-optimality claim for the surrogate.
Extended reading notes
Core claim
The paper's central claim is that data values for selection are not autonomous scores but encodings of an optimal sequential policy. Formally, it models selection as a deterministic MDP whose state is the current selected set, whose action is the next point to add, and whose reward at step $t$ is the utility $U(s_t)$; the objective is $\max_\pi \frac{1}{|D|}\sum_{k=1}^{|D|}U(S_k)$ with nested sets. The exact solution is the Bellman recursion $V(s)=U(s)+\max_{a\in D\setminus s}V(s\cup\{a\})$. The paper claims that every game-theoretic valuation can be reproduced as an ADP solution that uses a linear surrogate $\hat U(S)=\sum_{i\in S}\theta_i$ plus a myopic policy that always picks the largest $\theta_i$, with method-specific weights chosen by least squares. It then proves a $(1-c)^2$ approximation for monotone submodular utilities with curvature $c$, showing why high substitutability destroys the ranking's value. Finally, it proposes a bipartite coverage model $\hat U(S)=|\cup_{i\in S}S_i|$ over validation points, claims greedy maximum coverage is optimal for that surrogate, and reports experiments on eight datasets where the bipartite method reaches target accuracy with far fewer samples than the baselines.
Load-bearing premise
The bipartite surrogate's theoretical guarantee depends on greedy selection being exactly optimal for the sum-of-prefix coverage objective, a premise asserted by an exchange argument that does not account for how early choices constrain later coverage.
Editorial extensions
If this is right
- Under linear utility, every semi-value method produces the same selection sequence, and that sequence is optimal for the sequential objective.
- For monotone submodular utilities of curvature $c$, every semi-value ranking satisfies $U(G_k)\ge (1-c)^2 U(\mathrm{OPT}_k)$ for each prefix, and the same bound holds for the summed selection objective.
- As $c$ approaches 1, the guarantee degrades quadratically, so high data substitutability—not dataset size or noise—is what causes game-theoretic values to lose their advantage.
- Optimal data values are naturally defined by the selection step $v^*(i)=n-t^*(i)$ in the optimal trajectory, rather than by aggregating marginal rewards.
- A learned bipartite coverage model turns selection into greedy maximum coverage, avoiding model retraining, and the reported curves show it reaching target accuracy with substantially fewer samples.
Reading between the lines
- If the MDP view is accepted, the gap between a value method's ranking and the DP-optimal sequence can serve as a model-free diagnostic for when data values mislead selection; the paper does not build this diagnostic, but its experiments suggest it would flag high-curvature datasets.
- The $(1-c)^2$ bound points to a practical pre-check: estimate utility curvature before choosing a valuation method, and prefer coverage-based or non-myopic selection when curvature is high; the paper validates the trend but does not propose such a rule.
- The surrogate's exact-optimality claim may need to be relaxed to a constant-factor approximation, since the sum-of-prefix coverage objective is computationally hard in general; the reported selection-curve gains would still support using the method.
- A natural extension is to replace the uniform distribution over budgets with any user-supplied distribution, which the DP formulation can accommodate and which would yield data values tuned to the budgets that actually matter.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper reformulates data selection—ranking data by scores and then selecting prefixes of that ranking—as a finite-horizon deterministic MDP whose objective is the sum (equivalently average) of utilities of all prefixes. It interprets game-theoretic data values (Data Shapley, Beta Shapley, Data Banzhaf) as myopic linear reward approximations in an ADP scheme, proves that all semivalues are optimal under linear utility and enjoy a (1-c)^2 approximation under monotone submodular utilities with curvature c, and proposes a learned bipartite coverage surrogate for which greedy selection is claimed to be exactly optimal. The experiments compare the proposed surrogate against a large set of baselines on eight OpenML datasets.
Significance. The unifying MDP/ADP perspective is conceptually attractive and may be of interest to the data-valuation community. Theorem 4.3 and Theorem 4.6 appear correct and give a clean, testable explanation of when linear/myopic value rankings should degrade. The paper also provides reproducible code and a careful evaluation protocol. However, the headline guarantee of the proposed bipartite surrogate—that greedy selection is optimal under a correctly specified coverage surrogate—is false, because the corresponding optimization problem is minimum sum set cover, which is NP-hard; this invalidates the main algorithmic contribution as advertised.
major comments (2)
- [Appendix G, Theorem G.3] Theorem G.3 asserts that the greedy sequence is exactly optimal for the sum-of-prefix-utilities objective of the coverage surrogate. This objective is equivalent, up to an additive constant, to minimizing the sum of first-cover times over validation points, i.e., the minimum sum set cover problem, which is NP-hard and for which greedy is known to achieve only a 4-approximation. The exchange argument in §G.4 is therefore invalid: swapping two adjacent elements can change the first-cover times of many later-covered validation points, and submodularity of the coverage function does not imply that an inversion-free sequence maximizes the prefix-sum objective. Since Section 5.3 and the abstract rely on Theorem G.3 for the claim that greedy selection is optimal when the surrogate is correctly specified and learned, the advertised provable guarantees of the bipartite method are unsupported.
- [Appendix C, Lemma C.1 and Theorem 4.1] The claimed equivalence between game-theoretic data values and the proposed ADP solution rests on Lemma C.1, which states that constrained weighted least-squares coefficients converge to the semivalue. This lemma is not proved: the displayed constraint 'Û(S)θ_i = U(D) − U(∅)' is not a well-formed constraint on θ, and the proof simply asserts that the expectation converges to the exact marginal contributions. A valid derivation (or a precise citation to the projection/least-squares characterization of semivalues) is needed; without it, Theorem 4.1's statement that Data Shapley, Beta Shapley, and Data Banzhaf are exactly recovered as myopic linear approximations remains unestablished.
minor comments (5)
- [Abstract and Section 7] The abstract states that experiments include large-scale LLM fine-tuning data selection, but Section 7 and Appendix H describe only eight OpenML datasets with logistic regression; no LLM fine-tuning experiments are reported.
- [Table 1] The 'Average' and 'Std Dev' rows of Table 1 appear to be miscomputed or misaligned: for example, DataShap is listed with average 0.043, while its nine per-dataset means are all near 0.6–0.8.
- [Remark 4.7] Remark 4.7 misspells 'performs' as 'preforms'.
- [Appendix E] Appendix E refers to 'Section 4.4 of the main paper', but the relevant discussion is in Section 4.1.1.
- [Appendix H.5] Section H.5 states that DynamicProgramming is run on training sets of 20 points, but the paper does not describe how the 2^20 subset utilities are obtained under the 1000-retraining budget; this should be clarified.
Circularity Check
One constructed equivalence (semivalues as ADP solutions) is self-definitional, but the DP reformulation, curvature bound, and experiments are independent.
-
self definitional
[Theorem 4.1; Appendix C.1 (Utility Function Approximation Analysis), Lemmas C.1-C.2]
"These weighting schemes are specifically designed to recover the corresponding game-theoretic values in the limit of infinite samples."
Theorem 4.1 claims semivalue orderings are ADP solutions with linear surrogate Û(S)=Σ_{i∈S}θ_i and myopic policy argmax_a θ(a). But the least-squares weights are 'specifically designed' so θ_i converges to the target value v(i) (Lemma C.1); the myopic policy then selects by descending θ, i.e., by v(i) (Lemma C.2). The equivalence is therefore constructed, not derived: θ=v by choice of weights, so the 'unification' merely renames semivalue ranking as ADP. The DP reformulation, (1−c)^2 analysis, and experiments do not rely on this constructed step, keeping the circularity localized.
full rationale
The main derivation chain is self-contained: Section 3 defines a genuine deterministic MDP whose Bellman recursion (Eq. 2) yields an optimal selection sequence, and the curvature theorem (4.6) is proved from the semivalue definition and monotone-submodularity assumptions without importing the ADP reinterpretation. The experiments compare against external baselines and a separate test set, so the empirical claims are not fitted to the predictions. The only reduction I found is Theorem 4.1: existing semivalues are shown to be ADP solutions by choosing the linear surrogate's least-squares weights to reproduce exactly those values; this is a representation/renaming step rather than a derivation, and it is not used to derive the subsequent curvature or bipartite results. Separately, I note a correctness concern that is not circularity: the bipartite surrogate's advertised guarantee (Theorem G.3) is unsupported — the objective in Definition G.1 is, up to a constant, the Minimum Sum Set Cover objective, for which greedy is not exactly optimal, so the exchange argument in G.4 cannot be valid. That should be weighed as a correctness risk, not as evidence of circularity. Overall score 2: one localized self-definitional equivalence; the central claims retain independent content.
Assumptions & free parameters
free parameters (3)
- edge threshold tau* =
selected over Nτ candidates by minimizing error on random subsets
- number of thresholds Nτ
- subset sample count K
assumptions (5)
- domain assumption The true utility U is monotone submodular with curvature c
- domain assumption Utility U(S) can be evaluated for arbitrary subsets
- ad hoc to paper The constrained weighted least squares coefficients converge to the target semivalue
- ad hoc to paper Greedy maximum coverage is exactly optimal for the prefix-sum objective
- ad hoc to paper The coverage surrogate accurately represents the utility's dependency structure
Cite this review
Pith. "Pith review of Unifying and Optimizing Data Values for Selection via Sequential Decision-Making." pith.science (2026). https://pith.science/paper/LBHWDQR6
@misc{pith2026250204554,
author = {Pith},
title = {Pith review of: Unifying and Optimizing Data Values for Selection via Sequential Decision-Making},
year = {2026},
howpublished = {\url{https://pith.science/paper/LBHWDQR6}},
note = {Machine review of arXiv:2502.04554}
}
read the original abstract
Data selection has emerged as a crucial downstream application of data valuation, yet the theoretical foundations for using data values in selection remain underexplored. We reformulate data selection as a sequential decision-making problem where the optimal selection sequence arises from dynamic programming, and data values can be understood as encodings of this optimal sequence. This framework unifies and reinterprets existing methods like Data Shapley through the lens of approximate dynamic programming, revealing them as myopic linear approximations to the sequential problem. We further analyze how selection optimality degrades with utility curvature under submodularity, explaining when and why these approximations fail. To bridge theory and practice, we propose an efficient bipartite graph-based surrogate that preserves submodular structure while enabling scalable greedy selection with provable guarantees. Experiments on classical ML benchmarks and large-scale LLM fine-tuning data selection demonstrate substantial improvements over existing methods. Code is publicly available at https://github.com/frankhlchi/SeqDataVal
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
By Lemma D.2, the ordering based on semi-values v(i) is equivalent to ordering based on weights wi
-
[2]
For any size k, the subset Sk selected by this ordering contains the k elements with largest weights
-
[3]
Therefore: nX k=1 U (Sk) ≥ nX k=1 U (Sπ k ) for any alternative sequence π, establishing optimality
Due to linearity, for any size k: U (Sk) = X i∈Sk wi ≥ X i∈Sπ k wi = U (Sπ k ) for any alternative subset Sπ k of size k. Therefore: nX k=1 U (Sk) ≥ nX k=1 U (Sπ k ) for any alternative sequence π, establishing optimality. This proof shows that all semi-value methods achieve identical selection performance under linear utilities because they preserve the ...
-
[4]
Performance Curves: Plot test accuracy versus selection size k ∈ [1, |Dtrain|]
-
[5]
22 Unifying and Optimizing Data Values for Selection via Sequential-Decision-Making H.5
Experimental Control: • All methods limited to 1000 model retraining steps • Results averaged over 20 independent runs • Consistent random seeds used across methods This protocol follows standard practices in data valuation literature (Ghorbani & Zou, 2019; Kwon & Zou, 2021; Tarun et al., 2024) and ensures fair and comprehensive evaluation of different me...
work page 2019
-
[6]
Data Shapley: w(S) ∝ |S|!(|D|−|S|−1)! |D|!
-
[7]
Data Banzhaf: w(S) = 1 2|D|−1
-
[8]
Lemma E.1 (Value-Curvature Relationship)
Leave-one-out: w(S) = 1 if S = D \ {i}, 0 otherwise We now establish a fundamental relationship between data values and singleton utility values under curvature constraints. Lemma E.1 (Value-Curvature Relationship). For any element i ∈ D, the data value v(i) and singleton value U ({i}) satisfy: v(i) ≥ (1 − c)U ({i}) Proof. The proof follows from the curva...
work page 2016
Show all 20 references
-
[9]
Monotonicity: ∀A ⊆ B ⊆ U : ˆU (A) ≤ ˆU (B)
-
[10]
Submodularity: ∀A ⊆ B ⊆ U, e∈ U \ B : ˆU (A ∪ {e}) − ˆU (A) ≥ ˆU (B ∪ {e}) − ˆU (B) 19 Unifying and Optimizing Data Values for Selection via Sequential-Decision-Making
-
[11]
For monotonicity, consider any A ⊆ B ⊆ U
Prefix-sum Structure: For any permutation π of U: ˆU (π) = nX k=1 k[ j=1 Sπ(j) Proof. For monotonicity, consider any A ⊆ B ⊆ U. For each v ∈ V : X u∈A wuv ≤ X u∈B wuv Since min{cv, x} is monotone in x, we have: min{cv, X u∈A wuv} ≤min{cv, X u∈B wuv} Summing over all v ∈ V yiel...
-
[12]
By submodularity, moving the higher-gain element earlier preserves its marginal contribution: ∆(π∗(j)|Ai−1) ≤ ∆(π∗(j)|Ai−2)
-
[13]
The prefix-sum structure ensures earlier coverage provides more total contribution
-
[14]
Other elements’ contributions remain unchanged or increase due to submodularity. Through repeated application of such swaps, we can transform π∗ into a sequence ˜π with no inversions, maintaining: ˆU (˜π) ≥ ˆU (π∗) However, a sequence with no inversions must be the greedy sequ...
2017
-
[16]
Data Splitting: Each dataset D is randomly split into: • Training set Dtrain • Validation set Dvalid (for computing utility functions) • Test set Dtest (for evaluation)
-
[17]
Value Assignment: Data valuation methods compute values for each training point using validation set performance
-
[18]
Sequential Selection: • Rank training points by assigned values in descending order • Iteratively add points following this ranking • Train model on selected subset at each step • Record test accuracy
-
[2017]
De Farias, D
URL https://doi.org/10.7910/DVN/ 42MVDX. De Farias, D. P. and Van Roy, B. On constraint sampling in the linear programming approach to approximate dy- namic programming. Mathematics of operations research, 29(3):462–478, 2004. Feurer, M., Van Rijn, J. N., Kadra, A., Gijsbers, ...
-
[2023]
and represent a diverse range of learning tasks and data characteristics. H.4. Evaluation Protocol Details For each dataset, we follow a rigorous evaluation protocol:
-
[2024]
Lin, J., Zhang, A., L ´ecuyer, M., Li, J., Panda, A., and Sen, S
URL https://openreview.net/forum? id=lvSMIsztka. Lin, J., Zhang, A., L ´ecuyer, M., Li, J., Panda, A., and Sen, S. Measuring the effect of training data on deep learning predictions via randomized experiments. In In- ternational Conference on Machine Learning, pp. 13468– 13504...
2022 arXiv
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.