mlsanityData to 14 Oct 2026

What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization

arXiv 2505.21692 ↗First posted 27 May 2025math.OC cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We study the fundamental question of how informative a dataset is for solving a given decision-making task. In our setting, the dataset provides partial information about unknown parameters that influence task outcomes. Focusing on linear programs, we characterize when a dataset is sufficient to recover an optimal decision, given an uncertainty set on the cost vector. Our main contribution is a sharp geometric characterization that identifies the directions of the cost vector that matter for optimality, relative to the task constraints and uncertainty set. We further develop a practical algorithm that, for a given task, constructs a minimal or least-costly sufficient dataset. Our results reveal that small, well-chosen datasets can often fully determine optimal decisions -- offering a principled foundation for task-aware data selection.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 26 of its 51 references that are in the map. First posted on arXiv 27 May 2025.

Builds on

26 of 51 references.

References · 26

  1. 2019Data Shapley: Equitable Valuation of Data for Machine Learningcited by 629
  2. 2017Smart "Predict, then Optimize"cited by 339
  3. 2019Towards Efficient Data Valuation Based on the Shapley Valuecited by 281
  4. 2022Datamodels: Predicting Predictions from Training Datacited by 189
  5. 2021Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learningcited by 165
  6. 2020Algorithms with Predictionscited by 153
  7. 2014From Predictive to Prescriptive Analyticscited by 143
  8. 2023Modern Bayesian Experimental Designcited by 125
  9. 2013Data-Driven Robust Optimizationcited by 85
  10. 2023A Survey of Contextual Optimization Methods for Decision Making under Uncertaintycited by 82
  11. 2023OpenDataVal: a Unified Benchmark for Data Valuationcited by 55
  12. 2020Fast Rates for Contextual Linear Optimizationcited by 43
14 more
  1. 2025DataMIL: Selecting Data for Robot Imitation Learning with Datamodelscited by 28
  2. 2020An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference?cited by 27
  3. 2017Uniformly bounded regret in the multi-secretary problemcited by 19
  4. 2017The Price of Information in Combinatorial Optimizationcited by 12
  5. 2023Pure Exploration in Bandits with Linear Constraintscited by 10
  6. 2018Approximation Algorithms for D-optimal Designcited by 7
  7. 2023Towards Practical Robustness Auditing for Linear Regressioncited by 6
  8. 2024Experimental Design For Causal Inference Through An Optimization Lenscited by 6
  9. 2024Robustness Auditing for Linear Regression: To Singularity and Beyondcited by 6
  10. 2019Hiring Under Uncertaintycited by 4
  11. 2017Active Information Acquisition for Linear Optimizationcited by 3
  12. 2015Robust Sensitivity Analysis of the Optimal Value of Linear Programmingcited by 2
  13. 2022Selection and Ordering Policies for Hiring Pipelines via Linear Programmingcited by 1
  14. 2022A Constructive Prophet Inequality Approach to The Adaptive ProbeMax Problemcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 8.

9 papers.

  1. 2026Decision-Focused Sequential Experimental Design: A Directional Uncertainty-Guided Approachcited by 3
  2. 2025Bilevel Data Curation for LLM Fine-tuning: Offline Selection and Online Self-Refining Generationcited by 2
  3. 2026Cheap Thrills: Effective Amortized Optimization Using Inexpensive Labelscited by 1
  4. 2026Learning Decision-Sufficient Representations for Linear Optimizationcited by 1
  5. 2026Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedbackcited by 1
  6. 2026Decision-Focused Learning: When and Why Traditional Prediction Models Failcited by 1
  7. 2026DePICT: Decision-Preserving Interface for Constrained Downstream Taskscited by 1
  8. 2026The Value of Human Expertisecited by 0
  9. 2026Geometric Identification in Predict-Then-Optimize Learningcited by 0