2025-11-18 マサチューセッツ工科大学（MIT）
“We’ve shown that with careful selection, you can guarantee optimal solutions with a small dataset, and we provide a method to identify exactly which data you need,” says Asu Ozdaglar.Credit: MIT News; iStock
＜関連情報＞
- https://news.mit.edu/2025/bigger-datasets-arent-always-better-1118
- https://arxiv.org/abs/2505.21692
- https://arxiv.org/pdf/2505.21692
最適な意思決定を可能にするデータとは？線形最適化の正確な特性評価 What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
Omar Bennouna, Amine Bennouna, Saurabh Amin, Asuman Ozdaglar
arXiv Submitted on 27 May 2025
DOI:https://doi.org/10.48550/arXiv.2505.21692
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.
