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

2025/05/27 by Mohammed Amine Bennouna, Bennouna, Omar, Saurabh Amin +4 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Advanced Multi-Objective Optimization Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2505.21692

openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• DataMIL: Selecting Data for Robot Imitation Learning with Datamodels
• Robustness Auditing for Linear Regression: To Singularity and Beyond
• Experimental Design For Causal Inference Through An Optimization Lens
• Towards Practical Robustness Auditing for Linear Regression
• Pure Exploration in Bandits with Linear Constraints
• OpenDataVal: a Unified Benchmark for Data Valuation
• A Survey of Contextual Optimization Methods for Decision Making under Uncertainty
• Modern Bayesian Experimental Design
• A Constructive Prophet Inequality Approach to The Adaptive ProbeMax Problem
• Selection and Ordering Policies for Hiring Pipelines via Linear Programming
• Datamodels: Predicting Predictions from Training Data
• Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning
• An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference?
• Fast Rates for Contextual Linear Optimization
• Bandit Algorithms
• Algorithms with Predictions
• Hiring Under Uncertainty
• Data Shapley: Equitable Valuation of Data for Machine Learning
• Towards Efficient Data Valuation Based on the Shapley Value
• Approximation Algorithms for D-optimal Design
• The Price of Information in Combinatorial Optimization
• Smart "Predict, then Optimize"
• Active Information Acquisition for Linear Optimization
• Robust Sensitivity Analysis of the Optimal Value of Linear Programming
• From Predictive to Prescriptive Analytics
• Data-Driven Robust Optimization
• Data-driven robust optimization
• Theory and Applications of Robust Optimization
• Robust optimization ? methodology and applications
• Bayesian Experimental Design: A Review
• Equivalent Comparisons of Experiments

Cited by

• A Unified Understanding of Offline Data Selection and Online Self-refining Generation for Post-training LLMs

Related

• A Pareto Dominance Principle for Data-Driven Optimization
• Learning Linear Programs from Optimal Decisions
• Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
• Optimizer's Information Criterion: Dissecting and Correcting Bias in Data-Driven Optimization
• Optimization over Continuous and Multi-dimensional Decisions with Observational Data