Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A dataset is sufficient for a linear program under cost uncertainty exactly when its span contains every direction that can change the optimal solution.

desk verdict The core geometric characterization is new and correct for open convex uncertainty sets; the hiring application and abstract overreach on closed sets, where the necessity direction fails. read the letter →

arxiv 2505.21692 v1 pith:JI2B5JYE submitted 2025-05-27 math.OC cs.LG

Omar Bennouna , Amine Bennouna , Saurabh Amin , Asuman Ozdaglar This is my paper
classification math.OCcs.LG MSC 90C0590C31
keywords linearprogrammingdatainformativenesssufficientdecisiondatasetuncertaintysetgeometriccharacterizationselectionoptimalrecovery
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks when a fixed set of linear measurements of an unknown cost vector is enough to recover the optimal decision of a linear program, without ever seeing the whole vector. The answer it proves is exact: for an open convex uncertainty set $C$ and a bounded polyhedral decision set $X$, a dataset $D$ is sufficient precisely when every extreme direction that can affect optimality, collected in $\Delta(X,C)$, lies in the span of $D$. Since this condition is purely geometric, the paper's algorithm can build a minimal sufficient dataset by finding a basis of the reachable directions, solving mixed-integer programs when $C$ is polyhedral. The underlying message is that a small, well-chosen dataset can often determine the optimal decision completely.

What carries the argument

The load-bearing object is the gap between what a dataset can see and what a linear program needs. A dataset $D$ only gives the projection of the cost vector $c$ onto $\operatorname{span} D$, while the optimal solution changes only when $c$ crosses between 'optimality cones' $\Lambda(x^*)$ of extreme points of $X$. The paper collects the crossing directions into $\Delta(X,C)$: extreme directional moves between neighboring extreme points whose separating face meets $C$. Theorem 1 says the dataset is sufficient exactly when $\operatorname{span} D$ covers all of $\Delta(X,C)$; then any two cost vectors that look identical through $D$ lie in the same optimality cone, so they have the same optimizer. The construction algorithm replaces $\Delta(X,C)$ by the equal span $\operatorname{dir}(X^*(C))$, computed iteratively with a mixed-integer program built from complementary slackness.

What would settle it

Take a bounded polyhedron $X$ with an extreme direction $\delta$ and choose an open convex $C$ that intersects the face of an optimality cone perpendicular to $\delta$. Let $D$ be any dataset whose span omits $\delta$. Theorem 1 predicts $D$ is not sufficient: there must exist $c$ and $c'$ in $C$ with equal projections on $D$ but different optimal-solution sets. Searching $C$ explicitly for that pair, or finding instead that none exists, settles the claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: a necessary and sufficient characterization of dataset sufficiency. For a bounded polyhedron $X$ and an open convex uncertainty set $C$, define $\Delta(X,C)$ to be the set of extreme directions $\delta$ of $X$ for which the face of some optimality cone perpendicular to $\delta$ intersects $C$. Then $D$ is a sufficient decision dataset exactly when $\Delta(X,C)$ is contained in the span of $D$; by Theorem 2 this is equivalent to the span of $D$ containing all differences $x_1 - x_2$ of extreme-point optima reachable under cost vectors in $C$. The paper also establishes that for open convex $C$, recovering some optimal solution for every $c \in C$ is equivalent to recovering the whole optimal-solution set (Proposition 1), and that least-squares projection onto the span of a sufficient dataset yields an optimal decision, with the guarantee extending to sufficiently small observation noise (Proposition 3).

Load-bearing premise

The characterization requires queries to return exact, noiseless values of $c^\top q$, and the necessity direction requires the uncertainty set $C$ to be open, so boundary and noisy cases are outside the main theorem.

Editorial extensions

If this is right

  • Data collection for a target LP becomes a finite linear-algebra problem: it suffices to find a basis of $\operatorname{dir}(X^*(C))$, and the number of queries needed is exactly its dimension.
  • With no prior knowledge ($C = \mathbb{R}^d$), only the directions in $\operatorname{Ker} A \cap F_0$ need be observed; if a dataset misses any of them, no decision rule can uniformly bound suboptimality below an arbitrarily large constant.
  • For open convex $C$, recovering one optimal solution for every $c \in C$ is equivalent to recovering the entire optimal-solution set, so sufficiency is not merely an 'any solution' relaxation.
  • In the hiring application, the number of interviews needed grows with uncertainty and depends on the geometry of hiring constraints, not naively on the size of the feasible set.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • I infer that a query's marginal value is entirely about raising the dimension of the span: a measurement that adds no new direction to $\operatorname{span} D$ is useless for the task, which gives a rank-based pricing rule for data markets.
  • I infer that the openness requirement in Theorem 1 leaves a boundary-sensitive extension: for closed convex $C$, one might restore exactness by replacing $C$ with its interior in the definition of $\Delta$, except possibly on measure-zero cost vectors; the paper does not claim this.
  • I infer a testable stability statement from Proposition 3: the size of the minimal sufficient dataset should be locally constant as the noise radius varies, jumping only when the noise ellipsoid first touches a new optimality-cone face.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies when a set of linear measurements D = {q1,...,qN} of an unknown cost vector c, known to lie in an uncertainty set C, is sufficient to recover argmin_{x in X} c^T x for a bounded polyhedron X. The main result (Theorem 1) is an iff characterization for open convex C: D is sufficient exactly when span D contains Delta(X,C), the set of extreme directions of optimality cones that interact with C. Theorem 2 identifies span Delta(X,C) with dir(X^*(C)), the span of differences of reachable optimal extreme points. Based on this, the paper proposes an iterative algorithm (Algorithm 2) that constructs a basis of dir(X^*(C)) using MILPs, and an application to hiring interview selection. Section 5 applies the characterization to a closed box uncertainty set and claims minimality of the resulting interview set.

Significance. If the main characterization holds, it is a clean and potentially useful geometric answer to a natural question in data-driven optimization: which linear functionals of the cost vector need to be observed to pin down the exact optimal solution set. The paper is careful in many ways: Remark 1 explicitly separates the openness and convexity requirements, Theorem 2 is proved constructively via a strong-connectivity argument, and Algorithm 2 is constructive and comes with a termination proof. The hiring application is a nice illustration of the qualitative finding that task structure and uncertainty shape data requirements. However, the central claim is stated more strongly in the abstract and in the application than the theorems support, and one of the two directions of the characterization fails for the closed uncertainty set used in Section 5.

major comments (3)
  1. [Section 5 and Corollary 1] The hiring application uses the closed box C = {c : exists alpha in [ell,u], eps in [-eta,eta], c = alpha^T phi + eps}, but Corollary 1 and Theorem 1 require C to be open for the necessity direction. For closed convex C the 'only if' is false, even in full dimension. Example: X = {x >= 0 : x1+x2 = 1}, C = conv{(1,1),(0,2),(1,2)}, D = {e2}. For every c in C we have c2 >= c1 with equality only at c=(1,1); observing c2 recovers the argmin exactly (the whole segment at c2=1 and {(1,0)} otherwise), so D is sufficient by Definition 1. Yet Delta(X,C) contains (-1,1), which is not in span{e2}. Thus a dataset can be sufficient while Delta(X,C) is not contained in span D. Consequently, Algorithm 3 may output strictly more queries than needed, and the claim in Section 5 that the output is the smallest sufficient interview set is not justified by the stated theory. The authors should either extend the necessity result to the closed setting under additional hypotheses, or explicitly reframe the application as using a nearby open/relaxed uncertainty set, or state the minimality claim as only conjectural.
  2. [Abstract and Section 1] The abstract states without qualification that the paper characterizes when a dataset is sufficient, and the Contributions bullet says 'We prove a necessary and sufficient condition (Theorem 1)'. Theorem 1 itself is correctly stated for open convex C, and Remark 1 notes that openness is needed only for necessity. The unqualified abstract and contribution statements are misleading, especially because the main application uses a closed C. Please qualify the abstract and the contribution statement by saying 'for open convex uncertainty sets' and note in the introduction that closed sets may behave differently, as shown by the counterexample in the previous comment.
  3. [Section 4, Algorithm 2 and Theorem 3] The linearization of complementary slackness via 1 - eps s_i >= tau_i >= eps x_i is claimed to be exact for 'eps > 0 a small constant', and Theorem 3 states that Algorithm 2 outputs a basis of dir(X^*(C)). The equivalence is exact only if eps is chosen so that eps x_i <= 1 and eps s_i <= 1 for every feasible (x,s) appearing in the MILP; the paper does not state or prove any such bound. If C is an unbounded polyhedron, the dual slacks s_i may be unbounded and no fixed epsilon can enforce the encoding. Even for bounded polyhedral C, the required bound depends on the data (A, b, C) and is not computed. This is a load-bearing gap in the correctness proof of the algorithm. Please add an explicit boundedness assumption on C (or on the feasible set of the MILP), specify how epsilon is chosen from the problem data, and prove that the chosen epsilon makes the encoding exact.
minor comments (4)
  1. [Section 2, Proposition 3] Proposition 3 only shows that for sufficiently small noise, argmin of the estimated cost vector is a subset of the true argmin, not equality. This is a strictly weaker guarantee than Definition 1. The paper should state this clearly in the main text and not imply that noisy observations inherit the full exact-recovery property.
  2. [Section 2, first paragraph] 'that is where the loss L(x,theta) = theta^T x is linear' should read 'that is, the loss...'.
  3. [Section 4, Algorithm 2] The while-loop condition says 'while either of the problems ... has a solution x* with non-zero optimal value'; to be fully precise, if both min and max have zero optimal value the loop exits, and if only one has nonzero value the resampled alpha can be reused. This is minor but would help reproducibility.
  4. [Section 5, experimental setup] The hiring model is described as a 'noisy linear model' because C includes an additive noise term, but the formal sufficiency theory and Algorithm 4 assume exact queries c^T q. The role of the noise term inside C should be distinguished from observation noise; otherwise the reader may think Proposition 3 justifies the experiment.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sufficiency characterization is derived from first-principles geometry, with no fitted inputs, no load-bearing self-citations, and no prediction that reduces to its own construction.

full rationale

The paper's derivation chain is self-contained. Theorem 1 is an 'if and only if' proved from Definition 1 via the projection characterization of Proposition 2 and the geometric properties of optimality cones and extreme directions (Propositions 5-6); the proof neither assumes sufficiency nor defines relevant extreme directions in terms of it. Theorem 2, equating span Delta(X,C) with dir(X*(C)), is established by an explicit connectivity argument (Lemma 4 and the proof chain in Appendix A.6), not by stipulation. Algorithm 2 constructs a basis of dir(X*(C)) using complementary-slackness MILPs, and its correctness proof (Theorem 3) is a direct termination and dimension argument; the 'minimal sufficient dataset' output is a span condition derived from Corollary 1, not a fitted quantity. No parameter is calibrated to data and then renamed a prediction, and the external references (Blackwell, active learning, robust statistics) serve as background or comparison, not as load-bearing support; there are no self-citations at all. The paper itself candidly flags limitations (open convex uncertainty sets, noiseless observations, basis-vector query sets), and the closed-C concern raised for the hiring application is a scope/correctness issue rather than circularity: the application may overclaim the reach of Theorem 1, but it does not smuggle the theorem's conclusion into its premises. Overall, the analysis exhibits no circular dependency of the kind that would reduce the central characterization to its inputs.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard LP assumptions: bounded polyhedron, convex and open uncertainty set, exact measurements. The ad hoc epsilon in the MILP encoding is the least-supported element: it must be chosen small enough for correctness, but no bound is derived. No fitted numeric parameters are used anywhere.

free parameters (1)
  • epsilon (MILP linearization constant) = small positive constant (unspecified)
    Introduced in Algorithm 2 to encode complementarity x_i s_i = 0 via tau_i; correctness requires epsilon below a data-dependent gap that is never quantified.
assumptions (5)
  • domain assumption X is a bounded polyhedron in standard form {x >= 0 : Ax = b}.
    Used throughout Section 2 and Proposition 6 to ensure optimal solutions are attained at extreme points.
  • domain assumption The uncertainty set C is convex, and open for the necessity direction of Theorem 1.
    Theorem 1 and Corollary 1 rely on this; the paper's application uses a closed box, where only sufficiency is guaranteed.
  • domain assumption Observations are exact, noiseless linear functionals c^T q.
    The definition of sufficiency (Definition 1) and the equivalence in Proposition 2 assume exact observations; Proposition 3 only extends to sufficiently small noise.
  • ad hoc to paper There exists epsilon > 0 small enough that the binary encoding 1 - eps s_i >= tau_i >= eps x_i exactly represents the complementarity constraint x_i s_i = 0 for all feasible (x,s).
    This is the correctness premise of Algorithm 2's MILP formulation; no quantitative condition on epsilon or the data is provided.
  • standard math The random vector alpha drawn from N(0,I) detects any nonzero projection with probability 1.
    Used in Theorem 3 proof; standard Gaussian measure argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization." pith.science (2026). https://pith.science/paper/JI2B5JYE

@misc{pith2026250521692,
  author       = {Pith},
  title        = {Pith review of: What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JI2B5JYE}},
  note         = {Machine review of arXiv:2505.21692}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2505.21692 by the authors.

Figure 1
Figure 1. Optimality cones relative to X (left), relative to the origin (middle) and examples of the uncertainty sets (C and C ′ ) relative to the optimality cones (right). With the notion of optimality cones, solving a linear program for a given cost vector c amounts to finding to which optimality cone it belongs. A dataset is therefore sufficient if it enables to determine the optimality cone of each possible c ∈ C. As C al… view at source ↗
Figure 2
Figure 2. Candidates to be interviewed (in red) to make an optimal hiring decision. Num [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Bilevel Data Curation for LLM Fine-tuning: Offline Selection and Online Self-Refining Generation

    cs.LG 2025-11 reject novelty 6.0 of 10

    A bilevel data-curation method for LLM fine-tuning that selects validation-aligned offline data and reweights online self-refined responses via importance ratios.

Reference graph

Works this paper leans on

12 extracted references · 7 canonical work pages · cited by 1 Pith paper

  1. [3]

    doi: 10.1287/stsy.2018

    ISSN 1946-5238. doi: 10.1287/stsy.2018

    work page doi:10.1287/stsy.2018 1946

  2. [5]

    doi: 10.1287/educ.2024.0277

    ISBN 979-8- 9882856-2-5. doi: 10.1287/educ.2024.0277. David Blackwell. Equivalent Comparisons of Experiments.The Annals of Mathematical Statis- tics, 24(2):265–272,

    work page arXiv 2024

  3. [10]

    9781611975031.161

    doi: 10.1137/1. 9781611975031.161. Guillermo Gallego and Danny Segev. A Constructive Prophet Inequality Approach to The Adaptive ProbeMax Problem, October

    doi:10.1137/1

  4. [11]

    doi: 10.1287/moor

    ISSN 0364-765X. doi: 10.1287/moor. 2019.1041. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions, June

    arXiv 2019

  5. [1951]

    doi: 10.1525/9780520411586-009

    ISBN 978-0-520-41158-6. doi: 10.1525/9780520411586-009. S. Sherman. On a Theorem of Hardy, Littlewood, Polya, and Blackwell.Proceedings of the National Academy of Sciences of the United States of America, 37(12):826–831,

    doi:10.1525/9780520411586-009

  6. [1953]

    URLhttps://www.jstor.org/stable/2236332

    ISSN 0003-4851. URLhttps://www.jstor.org/stable/2236332. Publisher: Institute of Mathematical Statistics. Henrique de Oliveira. Blackwell’s informativeness theorem using diagrams.Games and Economic Behavior, 109:126–131, May

    work page arXiv

  7. [1979]

    doi: 10.2307/1910412

    ISSN 00129682, 14680262. doi: 10.2307/1910412. Sahil Singla. The Price of Information in Combinatorial Optimization. InProceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 2523–2532. Society for Industrial and Applied Mathematics, January

    doi:10.2307/1910412 2018

  8. [1996]

    URLhttp://www.jstor.org/stable/4355942

    ISSN 07492170. URLhttp://www.jstor.org/stable/4355942. Publisher: Institute of Mathematical Statistics. Peter J. Huber. Robust Estimation of a Location Parameter. In Samuel Kotz and Norman L. Johnson, editors,Breakthroughs in Statistics: Methodology and Distribution, pages 492–

    work page arXiv

Show all 12 references
  1. [2018]

    doi: 10.1016/j.geb.2017.12.008

    ISSN 0899-8256. doi: 10.1016/j.geb.2017.12.008. L. Le Cam. Comparison of Experiments: A Short Review.Lecture Notes-Monograph Series, 30: 127–138,

    2017 doi

  2. [2019]

    Selection and Ordering Policies for Hiring Pipelines via Linear Pro- gramming.Operations Research, 72(5):2000–2013, September

    Boris Epstein and Will Ma. Selection and Ordering Policies for Hiring Pipelines via Linear Pro- gramming.Operations Research, 72(5):2000–2013, September

    2000

  3. [2020]

    doi: 10.1017/9781108571401

    ISBN 978-1-108-57140-1 978-1-108-48682-8. doi: 10.1017/9781108571401. Jinglong Zhao. Experimental Design for Causal Inference Through an Optimization Lens. InTu- torials in Operations Research: Smarter Decisions for a Better World, INFORMS TutORials in Operations Research, cha...

    doi

  4. [2024]

    doi: 10.1287/opre.2023.0061

    ISSN 0030-364X. doi: 10.1287/opre.2023.0061. Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pages 630–631, USA, January

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.