What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916762765754368 |
|---|---|
| author | Bennouna, Omar Bennouna, Amine Amin, Saurabh Ozdaglar, Asuman |
| author_facet | Bennouna, Omar Bennouna, Amine Amin, Saurabh Ozdaglar, Asuman |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21692 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization Bennouna, Omar Bennouna, Amine Amin, Saurabh Ozdaglar, Asuman Optimization and Control Machine Learning 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. |
| title | What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2505.21692 |