What Data Enables Optimal Decisions? an Exact Characterization for Linear Optimization
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.
Cite
Text
Bennouna et al. "What Data Enables Optimal Decisions? an Exact Characterization for Linear Optimization." Advances in Neural Information Processing Systems, 2025.Markdown
[Bennouna et al. "What Data Enables Optimal Decisions? an Exact Characterization for Linear Optimization." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/bennouna2025neurips-data/)BibTeX
@inproceedings{bennouna2025neurips-data,
title = {{What Data Enables Optimal Decisions? an Exact Characterization for Linear Optimization}},
author = {Bennouna, Omar and Bennouna, Amine and Amin, Saurabh and Ozdaglar, Asuman E.},
booktitle = {Advances in Neural Information Processing Systems},
year = {2025},
url = {https://mlanthology.org/neurips/2025/bennouna2025neurips-data/}
}