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

arXiv: https://arxiv.org/abs/2505.21692 · HTML: https://mlsanity.com/paper/2505.21692/

## 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 (most cited first, 26 of 26)

- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Modern Bayesian Experimental Design](https://mlsanity.com/paper/2302.14545/) (2023)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [OpenDataVal: a Unified Benchmark for Data Valuation](https://mlsanity.com/paper/2306.10577/) (2023)
- [Fast Rates for Contextual Linear Optimization](https://mlsanity.com/paper/2011.03030/) (2020)
- [DataMIL: Selecting Data for Robot Imitation Learning with Datamodels](https://mlsanity.com/paper/2505.09603/) (2025)
- [An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference?](https://mlsanity.com/paper/2011.14999/) (2020)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [Approximation Algorithms for D-optimal Design](https://mlsanity.com/paper/1802.08372/) (2018)
- [Towards Practical Robustness Auditing for Linear Regression](https://mlsanity.com/paper/2307.16315/) (2023)
- [Experimental Design For Causal Inference Through An Optimization Lens](https://mlsanity.com/paper/2408.09607/) (2024)
- [Robustness Auditing for Linear Regression: To Singularity and Beyond](https://mlsanity.com/paper/2410.07916/) (2024)
- [Hiring Under Uncertainty](https://mlsanity.com/paper/1905.02709/) (2019)
- [Active Information Acquisition for Linear Optimization](https://mlsanity.com/paper/1709.10061/) (2017)
- [Robust Sensitivity Analysis of the Optimal Value of Linear Programming](https://mlsanity.com/paper/1509.04682/) (2015)
- [Selection and Ordering Policies for Hiring Pipelines via Linear Programming](https://mlsanity.com/paper/2210.04059/) (2022)
- [A Constructive Prophet Inequality Approach to The Adaptive ProbeMax Problem](https://mlsanity.com/paper/2210.07556/) (2022)

## Built on by (most cited first, 9 of 9)

- [Decision-Focused Sequential Experimental Design: A Directional Uncertainty-Guided Approach](https://mlsanity.com/paper/2602.05340/) (2026)
- [Bilevel Data Curation for LLM Fine-tuning: Offline Selection and Online Self-Refining Generation](https://mlsanity.com/paper/2511.21056/) (2025)
- [Cheap Thrills: Effective Amortized Optimization Using Inexpensive Labels](https://mlsanity.com/paper/2603.05495/) (2026)
- [Learning Decision-Sufficient Representations for Linear Optimization](https://mlsanity.com/paper/2603.18551/) (2026)
- [Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback](https://mlsanity.com/paper/2606.01081/) (2026)
- [Decision-Focused Learning: When and Why Traditional Prediction Models Fail](https://mlsanity.com/paper/2606.21773/) (2026)
- [DePICT: Decision-Preserving Interface for Constrained Downstream Tasks](https://mlsanity.com/paper/2610.03945/) (2026)
- [The Value of Human Expertise](https://mlsanity.com/paper/2608.26051/) (2026)
- [Geometric Identification in Predict-Then-Optimize Learning](https://mlsanity.com/paper/2609.33472/) (2026)

## 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.