Technical Summary: Unifying and Optimizing Data Values for Selection via Sequential Decision-Making

Problem Statement

Data selection is a critical downstream application of data valuation, aiming to identify optimal subsets of training data that maximize model performance. While existing data valuation methods (e.g., Data Shapley, Banzhaf, Beta Shapley) provide principled ways to quantify sample contributions based on cooperative game theory, their theoretical foundations for selection remain underexplored. Specifically, these methods are not explicitly optimized for the selection objective, which requires maximizing cumulative performance across all possible subset sizes (selection curves). The paper identifies a gap between the theoretical optimality of selection sequences and the practical performance of current valuation methods, particularly in scenarios involving high data redundancy or diminishing returns (submodularity).

Methodology

The authors reformulate data selection as a sequential decision-making problem modeled as a Deterministic Markov Decision Process (DMDP).

1. Sequential Formulation:

   • State: The set of data points selected so far ($s_t \subseteq D$).
   • Action: The next data point to add ($a_t \in D \setminus s_t$).
   • Reward: The utility of the resulting subset, $U(s_t \cup \{a_t\})$.
   • Objective: Maximize the expected cumulative utility across all prefix sizes (equivalent to the Area Under the Selection Curve, AUSC).

2. Exact Solution via Dynamic Programming (DP):

   • The optimal selection sequence is derived using the Bellman optimality equation. This yields an exact solution where the optimal policy considers both immediate rewards and future value (full lookahead).
   • Limitation: The state space grows exponentially ($O(n \cdot 2^n)$), making exact DP computationally intractable for large datasets.

3. Reinterpretation of Existing Methods via Approximate Dynamic Programming (ADP):

   • The paper demonstrates that existing game-theoretic data values (Shapley, Banzhaf, Beta Shapley) correspond to myopic linear approximations within the ADP framework.
   • These methods implicitly fit a linear surrogate utility function $\hat{U}(S) = \hat{b} + \sum_{i \in S} \theta_i$ and adopt a myopic policy (greedy selection based on immediate marginal gain $\theta_i$).
   • Theoretical analysis shows that the effectiveness of these approximations depends on the curvature ($c$) of the utility function. For linear utilities ($c=0$), these methods are optimal. However, as curvature increases (indicating diminishing returns/submodularity), the performance guarantee degrades quadratically as $(1-c)^2$.

4. Proposed Solution: Bipartite Graph-Based Surrogate:

   • To bridge the gap between theoretical optimality and computational efficiency, the authors propose a novel approximation scheme using a bipartite graph between training and validation sets.
   • Utility Modeling: The surrogate utility is defined as the "coverage" of validation points by selected training points. This coverage function is proven to be normalized, monotone, and submodular.
   • Selection Policy: A greedy selection algorithm is applied to this surrogate.
   • Theoretical Guarantees: Under "sandwich" conditions where the surrogate uniformly approximates the true utility, the method provides an end-to-end approximation guarantee of $(1-\epsilon)(1-1/e)$.

Key Contributions

• Theoretical Unification: The paper establishes a framework unifying data valuation and sequential decision-making, revealing that popular semi-value methods are specific instances of myopic linear approximations in ADP.
• Optimality Analysis: It provides new theoretical insights characterizing when and why existing methods fail, specifically linking performance degradation to the curvature of the utility function.
• Efficient Algorithm: The authors develop a bipartite graph-based surrogate that preserves submodular structure, enabling scalable greedy selection with provable theoretical guarantees.
• Empirical Validation: Comprehensive experiments demonstrate that existing methods consistently underperform optimal sequential selection, while the proposed bipartite approach substantially closes this gap.

Experimental Results

The authors evaluated their method against nine baselines (including Data Shapley, Beta Shapley, Banzhaf, Influence Functions, and learning-based methods) across eight classical ML benchmarks and a large-scale LLM fine-tuning task.

• Gap to Optimality: Existing methods underperformed the optimal Dynamic Programming solution by 8.39% to 23.76% in cumulative selection performance. The largest gaps were observed in structured datasets with high redundancy.
• Curvature Impact: Experiments manipulating data substitutability (as a proxy for curvature) confirmed that as substitutability increases, the performance of game-theoretic methods degrades and converges, aligning with the $(1-c)^2$ theoretical bound.
• Bipartite Performance: The proposed bipartite method achieved the highest average accuracy across datasets.
  • On the bbc-embeddings dataset, it achieved 0.878 accuracy compared to 0.809 for the best baseline.
  • On the digits dataset, it reached 0.764 accuracy versus 0.680 for the next best.
  • In large-scale LLM fine-tuning (DATE-LM benchmark), the method (BipCov) achieved 63.89% average accuracy, outperforming strong baselines like RDS+ (62.88%) and Random (62.82%).
• Utility Approximation: The bipartite surrogate demonstrated significantly lower approximation error (MSE: 0.019) compared to linear regression baselines (MSE: 0.089), validating its ability to capture underlying utility relationships.

Significance and Claims

The paper claims to provide a theoretical framework that unifies data valuation with sequential decision-making, offering a rigorous explanation for the limitations of current game-theoretic methods. By reframing data values as encodings of an optimal selection sequence derived from dynamic programming, the authors argue that existing methods are fundamentally limited by their myopic, linear nature.

The significance of the work lies in:

1. Diagnosing Failure: Providing a principled explanation (curvature) for why data valuation methods struggle on redundant datasets.
2. Practical Improvement: Offering a computationally efficient method (bipartite graph surrogate) that retains theoretical guarantees while significantly outperforming existing state-of-the-art selection strategies.
3. Scalability: Demonstrating that principled data selection can be scaled to large datasets and LLM fine-tuning tasks without the prohibitive cost of exact dynamic programming.

The authors remain modest regarding the theoretical bounds, noting that the $(1-c)^2$ guarantee is a worst-case lower bound useful for explaining failures rather than predicting typical success, and that their empirical results show performance often exceeds these conservative bounds.