What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
Omar Bennouna, Amine Bennouna, Saurabh Amin, Asuman E. Ozdaglar
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.
BibTeX
@inproceedings{
bennouna2025what,
title={What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization},
author={Omar Bennouna and Amine Bennouna and Saurabh Amin and Asuman E. Ozdaglar},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=NXkUWAxSEH}
}