# Learning Decision-Sufficient Representations for Linear Optimization

arXiv: https://arxiv.org/abs/2603.18551 · HTML: https://mlsanity.com/paper/2603.18551/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 58 references that are in the map.
- First posted on arXiv 19 Mar 2026.

## Builds on (most cited first, 25 of 25)

- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022)
- [Compression, Generalization and Learning](https://mlsanity.com/paper/2301.12767/) (2023)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Refined bounds for algorithm configuration: The knife-edge of dual class approximability](https://mlsanity.com/paper/2006.11827/) (2020)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization](https://mlsanity.com/paper/2505.21692/) (2025)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Active Learning For Contextual Linear Optimization: A Margin-Based Approach](https://mlsanity.com/paper/2305.06584/) (2023)
- [Random projections for linear programming](https://mlsanity.com/paper/1706.02768/) (2017)
- [Pick-to-Learn for Systems and Control: Data-driven Synthesis with State-of-the-art Safety Guarantees](https://mlsanity.com/paper/2512.04781/) (2025)
- [Random projection of Linear and Semidefinite problem with linear inequalities](https://mlsanity.com/paper/2007.00242/) (2020)
- [Data Informativeness in Linear Optimization under Uncertainty](https://mlsanity.com/paper/2602.15365/) (2026)
- [Sum of Squares Certificates for Containment of H-polytopes in V-polytopes](https://mlsanity.com/paper/1409.5008/) (2014)

## Built on by (most cited first, 1 of 1)

- [Geometric Identification in Predict-Then-Optimize Learning](https://mlsanity.com/paper/2609.33472/) (2026)

## Abstract (arXiv)

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 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 tildeO(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 tildeO(√d^star/n) rather than tildeO(√d/n), where d is the ambient cost dimension.