提出压缩数据集以高效求解未知成本的线性规划问题。
Learning Decision-Sufficient Representations for Linear Optimization
- 定义点态充分性，可在多项式时间内构造压缩数据集。
- 在独立同分布假设下，压缩规模不超过最优决策维数 $d^\star$。
- 适用于上下文线性优化，泛化误差更优，适合大规模优化场景。
我们研究如何构建压缩数据集，使其足以在未知成本向量 $c$ 位于先验集合 $ mathcal{C}$ 时恢复最优决策。Bennouna 等人给出了充分决策数据集（SDD）的精确几何刻画，其关键维度为 $d^\star$。但其算法需求解混合整数规划，计算复杂。本文证明计算 $d^\star$ 是 NP 难的，判断数据集全局充分性是 coNP 难的，解决了一个开放问题。为此，我们引入点态充分性，仅要求对单个成本向量充分，在非退化条件下给出多项式时间的割平面算法。在独立同分布成本下，进一步提出累积算法，聚合样本中的决策相关方向，得到大小至多为 $d^\star$ 的稳定压缩方案。该方法具有分布无关的 PAC 保证：在高概率下，新样本的点态充分性失败概率不超过 $\tilde{O}(d^\star/n)$，且该速率紧致（忽略对数因子）。最后，将其应用于上下文线性优化，获得压缩预测器，泛化界为 $\tilde{O}(\sqrt{d^\star/n})$，优于传统 $\tilde{O}(\sqrt{d/n})$（$d$ 为原始成本维度）。
原文摘要 · Abstract (English)
We study how to construct compressed datasets that suffice to recover optimal decisions in linear programs with an unknown cost vector $c$ lying in a prior set $\mathcal{C}$. Recent work by Bennouna et al. provides an exact geometric characterization of sufficient decision datasets (SDDs) via an intrinsic decision-relevant dimension $d^\star$. However, their algorithm for constructing minimum-size SDDs requires solving mixed-integer programs. In this paper, we establish hardness results showing that computing $d^\star$ is NP-hard and deciding whether a dataset is globally sufficient is coNP-hard, thereby resolving a recent open problem posed by Bennouna et al. To address this worst-case intractability, we introduce pointwise sufficiency, a relaxation that requires sufficiency for an individual cost vector. Under nondegeneracy, we provide a polynomial-time cutting-plane algorithm for constructing pointwise-sufficient decision datasets. In a data-driven regime with i.i.d.\ costs, we further propose a cumulative algorithm that aggregates decision-relevant directions across samples, yielding a stable compression scheme of size at most $d^\star$. This leads to a distribution-free PAC guarantee: with high probability over the training sample, the pointwise sufficiency failure probability on a fresh draw is at most $\tilde{O}(d^\star/n)$, and this rate is tight up to logarithmic factors. Finally, we apply decision-sufficient representations to contextual linear optimization, obtaining compressed predictors with generalization bounds scaling as $\tilde{O}(\sqrt{d^\star/n})$ rather than $\tilde{O}(\sqrt{d/n})$, where $d$ is the ambient cost dimension.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。