小而精的数据也能决定最优决策，关键在选对信息方向。
What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization
- 用几何方法识别影响最优解的关键参数方向。
- 可构造最小或最省钱的足够数据集，实现精准决策。
- 适合需要高效数据采集的优化任务设计者。
我们研究数据集对特定决策任务的启发程度。在设定中，数据仅提供影响任务结果的未知参数的部分信息。聚焦线性规划问题，我们给出了在成本向量不确定性集下，数据集足以恢复最优决策的精确条件。核心贡献是尖锐的几何刻画，明确了相对于任务约束和不确定性集，哪些成本向量方向对最优性至关重要。我们进一步提出一种实用算法，能为给定任务构建最小或最低成本的充分数据集。结果表明，小而精心选择的数据集往往能完全确定最优决策，为任务感知的数据选择提供了原则性基础。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。