Fugu-MT 論文翻訳(概要): Learning Decision-Sufficient Representations for Linear Optimization

論文の概要: Learning Decision-Sufficient Representations for Linear Optimization

arxiv url: http://arxiv.org/abs/2603.18551v1
Date: Thu, 19 Mar 2026 07:07:48 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-20 17:19:05.994124
Title: Learning Decision-Sufficient Representations for Linear Optimization
Title（参考訳）: 線形最適化のための学習決定十分表現法
Authors: Yuhan Ye, Saurabh Amin, Asuman Ozdauglar,
Abstract要約: Bennounaらによる最近の研究は、本質的な決定関連次元$dstar$を通じて十分な決定データセット(SDD)の正確な幾何学的特徴を提供する。我々は、$dstar$がNPハードであることを示し、データセットがグローバルに十分かどうかを判断することがコNPハードであることを示す硬度結果を確立する。本稿では,決定関連方向をサンプル間で集約し,最大$dstar$で安定な圧縮スキームを生成する累積アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 2.867517731896504
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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.
Abstract（参考訳）: 本研究では, 線形プログラムにおいて, コストベクトルが未知の$c$で最適決定を解くのに十分な圧縮データセットを, 予め設定した$\mathcal{C}$で構築する方法について検討する。 Bennounaらによる最近の研究は、本質的な決定関連次元$d^\star$を介して十分な決定データセット(SDD)の正確な幾何学的特徴を提供する。しかし、最小サイズのSDDを構築するアルゴリズムでは、混合整数プログラムを解く必要がある。本稿では, 計算量$d^\star$がNPハードであることを示し, データセットがグローバルに十分かどうかを判断する硬度結果を確立する。非退化性の下では、ポイントワイズ十分決定データセットを構築するための多項式時間切削平面アルゴリズムを提供する。さらに、データ駆動型システムにおいて、サンプル間で決定関連方向を集約し、最大$d^\star$で安定な圧縮スキームを生成する累積アルゴリズムを提案する。このことは、トレーニングサンプルよりも高い確率で、新鮮なドローのポイントワイズ失敗確率は、最大$\tilde{O}(d^\star/n)$であり、この割合は対数因子に強く依存する。最後に、決定十分表現を文脈線形最適化に適用し、一般化境界を持つ圧縮予測子を$\tilde{O}(\sqrt{d^\star/n})$として、$\tilde{O}(\sqrt{d/n})$ではなく$\tilde{O}(\sqrt{d/n})$としてスケーリングする。

論文の概要: Learning Decision-Sufficient Representations for Linear Optimization

関連論文リスト